### 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!