Nov 2012

One-time Pads (two proposals and investigations)

The one-time pad is a form of truly unbreakable encryption. Please start with my introductory mind rambling article, Unbreakable Encryption. This article ponders some properties of the one-time pad but doesn't introduce the more rudimentary concepts.

Properties of the binary one-time pad, two proposals^* and investigations

^*I'm not sure the casual exposition presented here rises to the level of theorum, so I'm just using the word "proposal" for this article.

Proposal:

In binary, the key and the cypher_text are symmetrical (if you combine the plain_text with one, you get the other and vs/va). As such, they are not really a "key" and a "cypher_text", but rather a mutual pair of strings which, when combined, reveal the encrypted plain_text.

Investigation of symmetry of key and cypher_text in binary:

plain_text:             010101
key:                    000111
cypher_text:            010010    (plain_text XOR key)
decypher_text:          010101    (cypher_text XOR key, should equal plain_text)
inverse_cypher_text:    000111    (plain_text XOR cypher_text, should equal key)

Q.E.D. in binary, the key and cypher_text are conceptually symmetrical. Admittedly, there is nevertheless a practical distinction: the key is the string that exists in advance and the cypher_text is the string that is generated when have a message you need to encrypt.

As a follow-up, this symmetry is also true in nonbinary one-time pads (alphabetic) with the notable necessity of a sign-flip.

plain_text:             EDBBAC
key:                    AAABBB
cypher_text:            EDBCBD    (plain_text shifted by key)
decypher_text:          EDBBAC    (cypher_text shifted by -key, should equal plain_text)
inverse_cypher_text:    AAABBB    (-plain_text shifted by cypher-text, should equal key)

The reason you don't need a sign-flip in the binary case is that modular arithmetic on binary numbers is symmetrical with respect to sign. Observe:

Bit    Shift    Result_after_wrap
0       0       0
0      +1       1
0      -1       1 (0 + -1 = -1 which wraps around to +1, i.e., -1 mod 2 = 1 (using the correct negative modulus operator))
1       0       1
1      +1       0 (1 + +1 = 2 which wraps around to 0, i.e. 2 mod 2 = 0)
1      -1       0

One might say that the binary one-time pad exhibits even symmetry while all other one-time pads exhibit odd symmetry, although I believe to do so is a pretty bad abuse of the terms even and odd symmetry.

Proposal:

It is possible to use a one-time pad to encode a message with multiple independent keys. Furthermore, such a multi-key encrypted string cannot be partially decrypted with a subset of the keys. Rather, the entire key must be known or no decryption (not even partial) is possible. This would be useful if you wanted to encrypt a message such that a group of people had to come together cooperatively to decrypt the message.

Investigation of multiple keys:

plain_text:             010101
key_1:                  000111
key_2:                  110001
key_3:                  011110
cypher_text_1_A:        010010    (plain_text XOR key_1)
cypher_text_2_A:        100011    (cypher_text_1_A XOR key_2)
final_cypher_text_A:    111101    (cypher_text_2_A XOR key_3)

Interestingly, it doesn't matter which order we encrypt in, we get the same encrypted string:

cypher_text_1_B:        001011    (plain_text XOR key_3)
cypher_text_2_B:        111010    (cypher_text_1_B XOR key_2)
final_cypher_text_B:    111101    (cypher_text_2_B XOR key_1, should equal final_cypher_text_A)

Decryption:

decypher_text_1_A:      111010    (final_cypher_text_A XOR key_1)
decypher_text_2_A:      001011    (decypher_text_1_A XOR key_2)
final_decypher_text_A:  010101    (decypher_text_2_A XOR key_3, should equal plain_text)

Interestingly, it doesn't matter which order we decrypt in:

decypher_text_1_C:      001100    (final_cypher_text_A XOR key_2)
decypher_text_2_C:      001011    (decypher_text_1_C XOR key_1)
final_decypher_text_C:  010101    (decypher_text_2_C XOR key_3, should equal plain_text)

Incidentally, for the purpose of efficiency, we can combine the keys up front into a single final_joined_key and then encrypt the plain_text in a single pass:

joined_key_1:           110110    (key_1 XOR key_2)
final_joined_key:       101000    (joined_key_1 XOR key_3)
joined_cypher_text:     111101    (plain_text XOR final_joined_key, should equal final_cypher_text_A)

Another way of conceptualizing the fact that we can precombine the keys into a single key is to simply consider all of the strings involved (all the keys in addition to the plain_text) to be a grab bag of homogenous strings which are then XORed in any arbitrary order to produce the encrypted string; the encrypted string which results from this process will never vary regardless of the order in which the strings are combined).

Incidentally, the final_joined_key (the combination of all the keys) also indicates the key-set's per-bit parity (0 where the number of 1s is even, 1 where the number of 1s is odd):

key_set_parity:         101000    (0 where key-set contains even number of 1s, 1 where key-set contains odd number of 1s, should equal final_joined_key)

Proof that partial decryption with a subset of the keys is impossible:

The realization that the multi-key encryption process is fundamentally a function of the key-set's parity (as opposed to something more mathematically nebulus such as XOR operators) proves that any subset of the keys cannot produce a partially decrypted message: A given bit-position's key-set parity will be completely unresolvable (that is to say its even/odd nature will have 50/50 odds) right up until the very last key is introduced, i.e., if there are 100 keys, then having 99 keys in hand will yield absolutely no information about a given bit-positions's key-set parity and therefore an attempt to decrypt with an incomplete joined_key will provide absolutely no decryption, not even partial decryption. To put it differently, if we gain no information about parity from a subset of the keys, and if the parity string equals the joined_key (as shown above), then we can likewise say that a subset of the keys offers no information about the joined_key either: you certainly can't accomplish partial decryption without a partial joined_key!