One-Time Pad (OTP)
- Key length = message length
Invented in 1917 by Gilbert Vernam, an engineer at AT&T Corporation in the USA.
Usage
It has been proven that OTP is impossible to crack if it is used correctly. It has the perfect secrecy property and allows very fast encryption and decryption. However, the secret key must be at least as long as the message, what makes it quite inconvenient to use while sending large electronic information.
Algorithm
Both data encryption and decryption by using OTP takes place in the same way. All bytes of the message (or of the ciphertext) are added XOR to bytes of the secret key.
The bytes are added one by one, and each addition produces one output byte:
mi XOR ki = ci
ci XOR ki = mi
Using the same key repeatedly
Each part of the secret key can be used only once for encrypting exactly one part of the message (of course, of the same length). Using the same key bytes more than once, allows the attacker to discover the two original messages summed by XOR:
M1 XOR K = C1
M2 XOR K = C2
C1 XOR C2 = M1 XOR K XOR M2 XOR K = M1 XOR M2
Having two original messages summed by XOR, the intruder can try to broke the cipher, by using attacks based on language and encoding features.
Providing no integrity
It is possible to modify the ciphertext in such a way, that the receiver would not be able to detect that. What is worse, the changes have a predictable impact on the message. If the attackers know the structure of the message, they are able to change only the desired parts of the message.
m -> enc(m, k) -> m XOR k
(m XOR k) XOR p = m XOR k XOR p
m XOR k XOR p -> dec(m XOR p, k) -> m XOR p
where p is the modification added by the attacker.
Secret Sharing
OTP allows to share the secret key among a number of people. Then, the encrypted text can be decoded only when all those parties use their parts of the key. Each person will know only one subkey.
To encrypt a text of size n by using a secret key sharing by m people, it is required to prepare m*n key characters. As a result, each subkey will contain n characters and will allow to encrypt a text up n-character long.
For example, if a secret key is shared among three parties, it will be required to have all three subkeys XORed with the ciphertext in order to recover the original message.
K = K1 XOR K2 XOR K3
C = M XOR K1 XOR K2 XOR K3
M = C XOR K1 XOR K2 XOR K3
Block Diagram of OTP Algorithm
Maths:
XOR
The only operation during the OTP encryption and decryption is Exclusive Or (XOR). The key bytes are added XOR to the data bytes, one after another.
Each time, all the 8 bits in the first byte are added XOR to the 8 bits in the second bytes.
| b1 | b2 | b1 XOR b2 |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 0 |
Implementation
OTP encryption implemented in C++:
size_t len = plaintext.size() < key.size() ?
plaintext.size() : key.size();
string ciphertext;
ciphertext.resize(len);
for (size_t i = 0; i < len; ++i) {
ciphertext[i] = ((short int)plaintext[i]) ^
((short int)key[i]);
}
return ciphertext;
}
