3
$\begingroup$

I found a program which takes a purely alphabetical message, converts the letters to their ASCII values and combines them with the ASCII values of an alphabetical key (wrapping around when it gets to Z).

(The key being used is fully random and is required to be at least a long as the message.)

But from what I usually read about one-time pads, the message and the key are in binary, and the bits in the message is XORed with the key to produce the ciphertext. Combining the ASCII values sounds like a similar but obviously very different process.

Is this a valid way to implement a one-time pad? Or does the process merely resemble the binary XOR and doesn't have the same cryptographic properties as a one-time pad?

Improve this question
$\endgroup$
1
  • 1
    $\begingroup$ Given a sufficiently random source, generating a random byte should have no less entropy than generating eight random bits, so there should be little functional difference. You could treat the encryption as ASCII and the decryption as binary, it's fairly irrelevant. $\endgroup$
    – Phoshi
    Commented Aug 25, 2013 at 12:36

3 Answers 3

Reset to default
9
$\begingroup$

In the "Telegraphic Code to Insure Privacy and Secrecy in the Transmission of Telegrams" from 1882, Frank Miller assigned a number to around 14,000 code words. Bankers would select an "irregular" series of such words and exchange them with a remote partner. Any messages would be lined up below the next unused words on the pad for encoding. When you lined up the key with the word, you added the numbers corresponding to each (mod 14,000, essentially, though he didn't use that term). For decoding, you used subtraction.

Vernam independently patented a version in 1919 that operated character by character, using Baudot codes and XOR (though he didn't call it XOR). In Vernam's example, the plaintext A ("++---" in Baudot), and the key B ("+--++"). The resulting ciphertext is "-+-++" (G). Likewise, for decoding, G XOR B returns A.

Both methods suffice, because they provide a reversible operation. XOR was appealing for Vernam (whatever he called it to himself) because it was easy to implement in relays, because it is it's own inverse.

Your one time pad could involve any reversible operation(s) you choose, and can operate on any atom of information you choose. Similar techniques were even adapted to secure telephony solutions around the time of World War II, like SIGSALY, which added random noise to a telephone conversation, then subtracted that same noise on the other end. (Noise cancelling headphones also exploit the fact that sound waves are susceptible to what basically amounts to simple arithmetic.)

Of course, as user7576 notes, if you're just using a short key, you're not in "one time pad" territory anymore. A one time pad is supposed to be a long list of random information. If you re-use any chunk of that key, then it's no longer a "one time use" system.

The closest thing to a one-time pad with a short key might be the stream ciphers that use a pseudo-random number generator with a short seed (key). Such ciphers use the (pseudo) random output from the PRNG to simulate a one-time pad (but it's not a true one time pad, because the PRNG can be susceptible to attack).

Improve this answer
$\endgroup$
1
  • $\begingroup$ Thanks. Not sure whether to accept this one or Ponchos, but this answer had the advantage of being easier to read and having the history of how Vernam did it. $\endgroup$
    – Caleb Paul
    Commented Aug 25, 2013 at 12:47
12
$\begingroup$

Actually, one-time pad can be implemented on the basis of any finite group operation; with these requirements:

  • The pad must consist of random group members; that is, each element in this pad must have equal probability of being any specific group member, and there must not be any correlation between different entries within the pad.

  • The encrypt and the decrypt processes are slightly different; if $\oplus$ is the group operation, $P_i, C_i$ is the i-th group element of the plaintext and ciphertext, $K_i$ is the i-th element of the pad, and $Inverse(x)$ is the group inverse of the element $x$, then the encrypt process is:

$$C_i = P_i \oplus K_i$$

while the decrypt process is:

$$P_i = C_i \oplus Inverse( K_i )$$

Now, when we work in the xor group, the inverse operation is actually the identity (because each element is its own inverse), hence we usually don't explicitly call this detail out. However when we work in other groups, this distinction becomes important.

As long as the above is followed, the standard security proof for one-time-pads applies.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Would you mind expanding upon the group operation please? What would "A" ⊕ "E" be for example if the group is only the uppercase alphabet? Do I arbitrarily just decide that it's "P" as in a substitution? $\endgroup$
    – Paul Uszak
    Commented Mar 13, 2017 at 22:15
  • $\begingroup$ @PaulUszak: one easy way to define a group operation in that case is to make the letter to values from 0 to 25, add them modulo 26, and then map the result back to a letter. If we decide "A" is 0, "B" is 1, etc, then "A" ⊕ "E" = "A". $\endgroup$
    – poncho
    Commented Mar 14, 2017 at 1:22
5
$\begingroup$

In the method you reference, I believe that the XOR details are irrelevent, given the following fact:

For your method to be a one time pad, the key must be random and as long as the message. This gives the method special characteristics such as "perfect secrecy": http://en.wikipedia.org/wiki/One-time_pad#Perfect_secrecy

In the method you reference, the actual key will generally be significantly shorter than the message. (The fact that you repeat it to make it longer, is irrelevent.) So the method you reference is not a one time pad to start with, regardless of how the XORs are done.

Improve this answer
$\endgroup$
5
  • $\begingroup$ In the Github code linked at the question, there is no part of the key repeated at all, just different parts of a long key used. Of course it depends on how the key is generated, this is out of scope of that program. $\endgroup$
    – Paŭlo Ebermann
    Commented Aug 25, 2013 at 12:14
  • $\begingroup$ I've edited the original question to be more explicit: the key being used is fully random (program has a link to random.org for this purpose) and must be at least as long as the plaintext. The program throws an error if the key is too short. $\endgroup$
    – Caleb Paul
    Commented Aug 25, 2013 at 12:48
  • $\begingroup$ But then, what did you mean by saying that the letters of the message are combined with the letters of the key "wrapping around when it gets to Z"? In what sense is anything "wrapped around", if the key and message are the same length? What is the "it" that might get to 255, and what gets "wrapped around" when that occurs? I feel you should describe this more clearly, instead of expecting people to wade through the code :-) $\endgroup$
    – user7576
    Commented Aug 26, 2013 at 9:52
  • $\begingroup$ Ok maybe I get it. You combine a 7 or 8 bit message character, with a 7 or 8 bit key character, in a way that can produce a value greater than 8 bits. So to get the result to fit in a single characater, you have to "wrap the value around" to fit. Right? (PS. I haven't read the referenced code, and don't intend to. My view is, if you can describe an operation clearly in plain english, this is always preferable to having others read code, to work it out.) $\endgroup$
    – user7576
    Commented Aug 26, 2013 at 10:11
  • $\begingroup$ Ah, sorry. Simplified example: if you combine A (1) with Z (26), it'll product 27, so you wrap it back around (should've said something like mod 26) to A. But it actually uses ASCII values (65 I think for A) $\endgroup$
    – Caleb Paul
    Commented Aug 26, 2013 at 16:49

Your Answer

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

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