2
$\begingroup$

I realized that if the key is chosen randomly from a range that isn't a power of $2$, the one-time-pad leaks information about the plaintext.

For example, if the alphabet was the first 20 naturals, then if you see a 6 in the ciphertext, the plaintext letter must have been within [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 20, 21, 22, 23], so it couldn't have been 16, for example (it couldn't have been 20-23 either, but that's assumed since the alphabet is just the first 20 naturals). However, encrypting and decrypting will work fine.

How can this be exploited in general? If the alphabet is small you can line up all possibilities and try to come up with English words (like coming up with words from phone numbers, possibly?) What about if $n$ is larger?

Unrelated question, given this limitation, why do people use XOR instead of modular addition? Is it just because XOR is faster?

$\endgroup$
  • $\begingroup$ From "Claude Elwood Shannon - Collected Papers" edited by N. J. A. Sloane and Aaron D. Wyner, I understand that Claude Shannon proved that any encryption algorithm possessing these characteristics is absolutely secure: 1. The encryption keys must be random numbers of uniform distribution. 2. The keys must be shared in absolute secrecy by the sender and receiver. 3. Any key encrypting a message must be as at least as long as that message. 4. Any key used to encrypt a message must not be reused. What is the evidence that the power of 2 has anything to do with it? $\endgroup$ – James Adrian Apr 19 '16 at 15:26
  • $\begingroup$ OTP can be defined with any finite group operation (actually, latin square). However, if you use exclusive-or as your group operation, then the "uniform distribution" clause is important; exclusive-or takes elements which are a power-of-2 in size (and hence your random numbers must be uniform within that power-of-2 size). If you replace exclusive-or with, say, modular addition, that power of 2 requirement does go away. $\endgroup$ – poncho Apr 19 '16 at 16:00
  • $\begingroup$ How would you even implement xor over an alphabet that isn't a power-of-two? $\endgroup$ – CodesInChaos Apr 19 '16 at 17:36
  • 1
    $\begingroup$ Computer based implementations almost always operate on sequences of bits/bytes which obviously are powers-of-two. Classical implementations often use modular addition. $\endgroup$ – CodesInChaos Apr 19 '16 at 17:38
  • $\begingroup$ The statement as you quote it cannot be correct. Certainly there may be some "encryption algorithms" with these characteristics that are not absolutely secure, e.g. throwing away all but a few bits of the key and xoring the plaintext. $\endgroup$ – Listing Apr 23 '16 at 9:21
2
$\begingroup$

Don't think about xor over an alphabet. Only think of it over a binary encoding of an alphabet. I see what you are saying, and what you are hinting at is why Vigenere Cipher is a bad idea in general (one time pad of length $\ell$ that you use over a message of length $k$ for $\ell < k$. However, there is no "meaningful" way of implementing xor with an alphabet that is not a power of 2 as it is defined in terms of bits. Therefore, if there is no binary encoding of your alphabet, then you cannot perform xor.

As for the unrelated question, we try to avoid modular addition because 1) it is slower and 2) it makes side channel attacks possible

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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