Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I know there are some encrypting algorithm that once the text (the message) is encrypted there is no way to decrypt it.

I can think one way of doing this: using as encryption key the current date at the encryption moment. But there is one problem wiht that: Each time you encrypt the same message the result will be different.

I think there must be some "math-algorithm" to encrypt without out the posibility to decrypt and that always the same message turns out with the same encrypted message, but I realy can't imagine how to do it.

Note: I'm posting this question in this forum and not in stackoverflow.com intentionally, it is not referred to "how to programm the algorithm", it is refered to "how is the math algorithm".

share|improve this question
3  
You're thinking of the one time pad apparently. –  J. M. Dec 15 '10 at 16:19
3  
If you want it not to be able to be decrypted, just flip each bit randomly. But I'm not sure what the use is... –  Ross Millikan Dec 15 '10 at 16:51
1  
Are you talking about cryptographic hash functions? –  Incognito Dec 15 '10 at 20:20
    
No, you can easily decrypt by simply guessing the date of encryption. Besides, as Ross said, if you won't be able to decrypt it [not even by you], so what's the use? –  muntoo Dec 15 '10 at 23:35
1  
@Diego Brute force decryptically beat up your file through all the possible dates. –  muntoo Dec 16 '10 at 17:05
show 1 more comment

3 Answers 3

up vote 8 down vote accepted

Such algorithms do exist. Which one you mean depends on what you mean by "no way to decrypt it". You refer to either:

  • A function which takes an input and generates a unique output, with there being ideally no known way to derive the input from the output. These are called hashing algorithms; examples of which include MD5, SHA256. Those links provide more detail than I possibly can.
  • A cryptosystem that is impossible for any other person but the keyholder to decrypt. This is the one time pad J.M. mentions. This is the only currently proven-secure algorithm.

Edited in because this is probably too long for comments:

Diego, no problem. They're not, as they're two different things and you're comparing apples and oranges, so to speak. A cryptosystem is designed to be hard to undo without the key, but easy if you have the key. By contrast, a hashing function should only require 1 input, be one way and give a unique output for each input. The idea is to be able to generate a unique representation of the output without being able to deduce what the output is. Why?

Well aside from verifying the unique nature of your input, a hashing function is used as part of a digital signature. In a public key cryptosystem, you may well be aware that Alice can send Bob an encrypted message using Bob's public key. However, anyone can send Bob a message using Bob's public key. If Eve has broken the cryptosystem, she could intercept Alice's message, decrypt it, change it, re-encrypt it and send it on to Bob.

How do we prevent this? Well, let $H: x\rightarrow y$ be a map from $x$ some input to $y$ some output. It is trivial to compute $H$ but impossible (ideally, the truth is just very very unlikely) to compute $H^{-1}$.

Then let $C:x,k$ be some assymetric cryptosystem Alice and Bob know, with Alice's keys $a_p$ and $a_s$ (public and secret) and likewise Bob's keys $b_p$ and $b_s$.

Now we know that as this cryptosystem is assymetric, that $C:x,b_p \rightarrow z$ where $z$ is some ciphertext (encrypted secret) and that $C:z,b_s \rightarrow x$ i.e. if you use Bob's public key to encrypt, Bob's private key using exactly the same algorithm will decrypt the process.

This we know already. However, as discussed, a man in the middle attack is possible if Eve knows Bob's secret. However, Alice can do two things:

  • Compute $C(H(x), a_s)$
  • Compute $C(x+H(x), b_p)$

And send the second one to Bob. What's the point in this? Well, Bob can reverse both "encryptions", because he holds the opposite keys (his own private and Alice's public. He is left with two things: the ciphertext and a unique hash of the ciphertext. He can also compute H(x) and compare results. If they differ, he knows the message has been tampered with.

Why? Well, consider Eve sat gleefully with Bob's keys. She intercept's Alices message and sees it contains the two parts (she can decrypt the outer layer, Bob's message). However, now she's left with an impossible situation. She can compute the hash of her newly inserted message, but she does not know Alice's private key (if she does, the cryptosystem is truly broken). Therefore she cannot encrypt the new hash. So, if she tries to send the new message onwards, Bob will immediately be aware the system has been tampered with.

This is called a digital signature or digitally signing and is used to identify the message author as who they truly say they are. After all, only they can encrypt with their private key (allegedly). The importance of hashing in this scenario is that it generates a unique output for each given output. However, not being reversible is also desired so that it is impossible to determine what a secret is given the output. This also makes it a highly used password-storage mechanism (because in theory, you're not storing the passwords, just a unique representation of them).

As always in cryptography, someone is always trying to break hash functions. Rainbow tables are the technique used to pre-compute parts of hashes to make hash reversing easier. Note however that the longer the input, the larger the tables need to be. Hence why passwords should always be greater than 6 characters...

Finally, you may be interested to know in Hash weaknesses. If two hashes with unique input produce the same output, this is called a collision and is a serious weakness, especially if someone can work out any pattern to said collisions. MD5 is thought to suffer from some, as is SHA1. SHA2 may, also. In any case, NIST has launched SHA-3, a competition to find future hash functions offering security now and in many years to come. The finalists are available to view here.

share|improve this answer
    
I think I was looking for hashing algorithms, thanks!. Why would a "decryptable" algorithm be more secure than a non "decryptable"? –  Diego Dec 16 '10 at 12:02
    
Excelent post! I wish I could +10 it :P. I must admit I didn't totally understand all the explanation (with a litle of shame). I'm now going to re-read it. Thank you so much! –  Diego Dec 17 '10 at 13:09
    
"This is the only currently proven-secure algorithm and even that has been thrown into doubt." - The security proof of OTP is so stupidly simple that I honestly couldn't believe this when I read it. That paper and all its references appear to be written by the same person: his argument is that, if we know one of two messages is being sent, and we know the probability of one message to be 10%, then after receiving the cyphertext the probability goes up to 50/50. And since the probability has changed, OTP is insecure. (cont.) –  BlueRaja - Danny Pflughoeft Jan 17 '11 at 22:12
    
(cont.) This is obviously bogus - the probability-space has not changed, only the observer's interpretation of the probability (which it really shouldn't - the probability is still 10/90 after receiving the cyphertext). This is equivalent to throwing a loaded die, rigged to roll '6' 99% of the time, then covering up the result and claiming there is a 1/6th chance that a '3' was rolled because there are 6 possibilities. Please remove the very misleading text in your post; you'll give people the wrong idea. –  BlueRaja - Danny Pflughoeft Jan 17 '11 at 22:13
    
I've read it and am very much inclined to agree with you - I do apologise for inserting rubbish. I clearly didn't read it correctly when I was looking for articles on the subject... it's quite clearly snake oil, or inverted snake oil. –  Ninefingers Jan 17 '11 at 22:22
show 1 more comment

As J.M. commented above, the only totally secure cryptographic algorithm is the one-time pad. Because this relies on both the sender and receiver of a message to be able to have access to the same arbitrarily long random sequence, it is often not feasible. Cryptography originally relied on shared keys, from which simple ciphers, such as Vigenere, Caesar, and substitution, come from. Unfortunately, all of these algorithms are so simple that using frequency analysis can often be used to break them very quickly.

Modern cryptography is generally split into two core areas: symmetric and asymmetric algorithms. Symmetric seems to be what you are describing, so I will describe that first. In symmetric algorithms, both users must share a key, which they often pass to one another via asymmetric cryptography or using Diffie-Hellman key exchange. Once the key is known between the two parties, eavesdroppers are generally going to have a very difficult time breaking the encryption. As with all things, certain algorithms are stronger than others. Older encryption schemes like DES are not as secure as some of the newer ones like AES, and it's not infeasible to try to break the weaker ones with sufficient computing power. Asymmetric cryptography, or public key cryptography, eliminates the need to share keys between users by admitting a public key and private key for each user. To send something to someone else, you encrypt using their public key (which they publish) and only they are able to decrypt using their private key. RSA and ECC are two of the more common public key protocols.

share|improve this answer
    
+1 from me for assym/sym crypto. –  Ninefingers Dec 15 '10 at 16:51
    
In asymmetric algorithms the sender and reciever don't have to share a key, (beside the public one)?? wow.. Still, I'm looking for something wich can't be decrypted. –  Diego Dec 16 '10 at 12:00
    
@Diego Yes, the sender and receiver don't have to share a key. Anyone is able to see the public one. If you are looking for something which cannot be decrypted at all, then it sounds like you are talking about cryptographic hash functions, which Ninefingers addressed above. –  Brandon Carter Dec 16 '10 at 17:36
add comment

I can give an answer, which may seem like a joke. But you can map all text (the set of all codes) to the same result.

Say for example I map the codes ABC to 1 BDCD to 1 ABDGR to 1

there is no opportunity for decoding here. :)

share|improve this answer
    
Isn't that also called "compressing" data? Not mapping everything, just patterns, and storing it in a separate file to remember what each pattern is mapped to. If you don't store it in a separate file, you can remember it. So, the remembered thing can now be called a "key". Only if you have the key, will you know what each pattern represents. Just an example, of course. –  muntoo Dec 15 '10 at 23:39
    
You are correct as far as I can remember from coding theory class. –  picakhu Dec 16 '10 at 4:16
    
yes, you are correct, that really answer the question I've made. I just asume it woudn't be necesary to say that I don't want the same result repeating for different texts. –  Diego Dec 16 '10 at 12:05
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.