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?

Improve this question
$\endgroup$
6
  • $\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, 2016 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, 2016 at 16:00
  • $\begingroup$ How would you even implement xor over an alphabet that isn't a power-of-two? $\endgroup$
    – CodesInChaos
    Apr 19, 2016 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, 2016 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, 2016 at 9:21

1 Answer 1

Reset to default
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

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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