How can I decrypt a message that was encrypted with a one-time pad? Would I need to get that pad, and then reverse the process? I'm confused here.
One-Time Pad is unbreakable, assuming the pad is perfectly random, kept secret, used only once, and no plaintext is known. This is due to the properties of the exclusive-or (xor) operation.
Here's its truth table:
A xor B = X A | B | X 0 | 0 | 0 0 | 1 | 1 1 | 0 | 1 1 | 1 | 0 Number of 0s in column A = 2 Number of 1s in column A = 2 Number of 0s in column B = 2 Number of 1s in column B = 2 Number of 0s in column X = 2 Number of 1s in column X = 2
Note that it introduces no bit-skew - the number of 0s and 1s in the inputs are equal to the number of 0s and 1s in the output, i.e. two of each. Furthermore, if you know only one element from a row, you cannot predict the values of the other two, since they are equally probable.
For example, let's say we know that X is 0. There's an equal probability that A = 0 and B = 0, or A = 1 and B = 1. Now let's say we know that X is 1. There's an equal probability that A = 0 and B = 1, or A = 1 and B = 0. It's impossible to predict. So, if you only know one element, you cannot possibly determine any information about A or B.
The next interesting property is that it is reversible, i.e.
A xor A = 0 B xor B = 0 A xor 0 = A B xor 0 = B A xor B xor B = A xor 0 = A A xor B xor A = B xor 0 = B
So, if we take any value and xor it with itself, the result is cancelled out and it always results in 0. This means that, if we xor a value A with a value B, then later xor that result with either A or B, we get B or A respectively. The operation is reversible.
This lends well to cryptography, because:
- xor introduces no bitskew
- xor has equally probable inputs for any given output
- given any two of A, B, X we can compute the third
As such, the following is perfectly secure:
ciphertext = message xor key
but only if message is the same length as key, key is perfectly random, key is only used once, and only one element is known to an attacker. If they know the ciphertext, but not the key or message, it's useless to them. They cannot possibly break it. In order to decrypt the message, you must know the entire key and the ciphertext.
Keep in mind that the key must be completely random, i.e. every bit must have an equal probability of being 1 or 0, and be completely independent of all other bits in the key.
This actually turns out to be rather impractical, for a few reasons:
- Generating perfectly random keys is hard. Software generators (and many hardware generators) often have minuscule biases and odd repeating properties. It's almost impossible to gain truly random data in anything but tiny amounts.
- If the attacker knows the ciphertext and can correctly guess parts of the message (e.g. he knows it's a Windows executable, and therefore must start with
MZ) he can get the corresponding key bits for the known range. These bits are useless for decrypting other parts of the message, but can reveal patterns in the key if it's poorly generated.
- You must be able to distribute the key, and your key must be equally as long as your message. If you can keep your key 100% secret between those of you who are authorised to read the message, why not just keep your message 100% secret instead?
The weak link here is your random number generator. The security of the one time pad is entirely limited by the security of your generator. Since a perfect generator is almost impossible, a perfect one-time pad is almost impossible too.
The final problem is that the key can only be used once. If you use it for two different messages, and the attacker knows both ciphertexts, he can xor them together to get the xor of the two plaintexts. This leaks all sorts of information (e.g. which bits are equal) and completely breaks the cipher.
So, in conclusion, in a perfect one-time pad you need to know the ciphertext and key in order to decrypt it, but perfect one-time pads are almost impossible.
One-time pads are extremely hard to break, in fact they are still used in some situations as if they are done correctly then they are essentially unbreakable. In a one-time pad system every character is changed by a stream of random data which is shared by both sides, without a copy of the pad you will not be able to break the code.
One of the few weaknesses in the system is the random data source. In WWII British one-time pads were being broken and they traced it to a worker whose job it was to pull random numbered balls out of a drum. The way it was supposed to work was that the worker would spin the drum, pull out a ball at random without looking at it, spin again, pick again, etc, etc. The worker started taking shortcuts by pulling out more than one ball after each spin and looking at the numbers, picking out favorites. It introduced patterns which enabled the opposition to break the pads, and lives were lost as a result.
The same is true today with pseudo-random number sources. Encryption protocols that should take millennia to break will really only last for years or decades without a true random data source.
While one-time-pad encryption is provably impossible to break, note that it is also extraordinarily rare.
Part of the definition of OTP is that the pad must contain truly random data, and truly random data can be hard to come by for computers. Instead, often the pad is composed of pseudo-random data, which is generally what you get when you ask a computer for a random number.
In this case, you no longer have unbreakable encryption. Instead, you have a message XORed with the output of a deterministic and often reversible algorithm, which can be attacked by reproducing the same pseudo-random string. This attack is particularly devastating if you know what algorithm is used and even more so if you know how the seed is generated. In such a case, the code can be cracked in a matter of seconds. But even without knowing the PRNG seed, often the pattern can be derived from the message itself.
Also, OTP encryption is particularly unwieldy because the key is as long as the encrypted message, and must somehow be transmitted to the recipient without being intercepted. Any software that claims to use OTP encryption that does not require you to exchange a key block as large as your message (or larger) is not using truly random data, and is therefore not using OTP encryption.
Also, one of the key features of OTP is that you cannot reuse old pads. If you reuse an old one even once, that can be enough to allow the code to be broken.
The question was, how can you decrypt a message that was created from one time pad, pretty sure that hasn't been answered yet.
Originally the one time pad was used with just characters, and is very basic. Let's say you have a message 'killtheking' (taken from one response), and you want to encrypt it so you need a key. For the key you need at least the same number of characters as the message, so you roll a dice which has 26 sides (one for each letter) 11 times, because there are 11 characters in the message.
Assume the result is aqheivlekrw
now we subtract the position in the alphabet of the letter in they key, from the position in the alphabet of the letter in the message, and the resulting number is the position in the alphabet of the cypher text. Wrap any letters that create a minus result as below (like if the result is 30, then use 26 - 30 = 4 or 'd'.
k - a = (11 - 1) = 10 = j
'j' is the 10th letter in the alphabet so we use that.
for the rest of the message we get:
i - g = (9 - 7) = 2 = b l - h = (12 - 8) = 4 = d l - e = (12 - 5) = 7 = g t - i = (16 - 9) = 7 = g h - v = (8 - 22) = -14 (26 - 14 = 12) = l e - l = (5 - 12) = - 7 (26 - 7 = 19) = s k - e = (11 - 5) = 6 = f i - k = (9 - 11) = -2 (26 - 2 = 24) = x n - r = (14 - 18) = -4 (26 - 4 = 22) = v g - w = (7 - 23) = -16 (26 - 16 = 10) = j
so in the end
your message = killtheking you key = agheivlekrw your cypher = jbdgglsfxvj
pass the cypher text to whomever you want to recieve it and they do the opposite of what you have done to encrypt it, they have to add the key to the cypher text:
j + a = (10 + 1 = 11) k b + g = (2 + 7 = 9) i d + h = (4 + 8 = 12) l g + e = (7 + 5 = 12) l ...
and so on.
Computers use XOR because it does the same thing and is a lot quicker and easier to implement, but to understand how it works, I found that it is good to see the 'human' usable example. So on a computer you can encrypt the message by doing:
Cypher = Message XOR Key
and decrypt it again by using:
Message = Cypher XOR Key
It is as simple as that.
one time pad could de easily cracked if you know the output format. Such as audio headers, gifs images, etc. By reverse engineering the stream back. It could be good for some sort of characters but not for some other fields where the output format could be easily identify by other means. Nothing is 100% secure nowadays.