Home
Education
Dissertation
Conferences
Classes taught
Data Science
PostScript
VBA
Locate
About
Send Close Add comments: (status displays here)
Got it!  This site "robinsnyder.com" uses cookies. You consent to this by clicking on "Got it!" or by continuing to use this website.  Note: This appears on each machine/browser from which this site is accessed.
The XOR operation and one-time pads
by RS  admin@robinsnyder.com : 1024 x 640
1. The XOR operation and one-time pads
A OTP (One Time Pad) cipher system that uses the cipher key one time only, and for short messages (key is longer than the message).

The most secure keys are one-time pads of random, but agreed-on keys. It is impossible to break a one-time pad. But, if the key is ever reused, then it becomes almost trivial to break that one-time pad.

That is why it is called a one-time pad. It can only (securely) be used one time.

The one-time pad was first described in 1882 and re-discovered in 1917 by Gilbert Vernam.
2. History
This is the only known secure system (unbreakable if properly used) for communication, but it has some restrictions that must be insured.

The problem with the one time pad is that of key distribution. Other message security systems are typically based on this system at an internal level, but use a more convenient way to generate a pseudo-random sequence of bits.
3. Brute force attack
Given a sequence of random bits, the problem reduces to guessing that sequence of random bits.

This is not possible, since a brute force attack is not possible (for more than a line of text) and such an attack would generate every possible random message and every possible meaningful message.
4. Exclusive or
The XOR (Exclusive Or) operation is true if both operands are different. Here is the extended truth table of the XOR operation using the caret "^N" is the exclusive or operator. Expression tree for a ^ b
a b | a b ----------- 0 0 | 0 0 0 0 1 | 0 1 1 1 0 | 1 1 0 1 1 | 1 0 1

5. One-time pad proof
Expression tree for ((m ^ k) ^ k ) = m
  • m is the message
  • k is the key

    • The proof is for one random bit and one bit of the message. Repeat for a longer message (always using a new random bit).
    k m | ( ( m k ) k ) = m --------------------------- 0 0 | ( ( 0 0 0 ) 0 0 ) 1 0 0 1 | ( ( 1 1 0 ) 1 0 ) 1 1 1 0 | ( ( 0 1 1 ) 0 1 ) 1 0 1 1 | ( ( 1 0 1 ) 1 1 ) 1 1

    The extended truth table shows that encrypting by a random bit and then applying the same operation results in the original value.
    6. Re-order and re-name the variables
    Expression tree for p = ( q ^ ( q ^ p ))
  • p is the message
  • q is the key

    • The proof is for one random bit and one bit of the message. Repeat for a longer message (always using a new random bit).
    p q | p = ( q ( q p ) ) --------------------------- 0 0 | 0 1 ( 0 0 ( 0 0 0 ) ) 0 1 | 0 1 ( 1 0 ( 1 1 0 ) ) 1 0 | 1 1 ( 0 1 ( 0 1 1 ) ) 1 1 | 1 1 ( 1 1 ( 1 0 1 ) )

    7. Key


    Here is a (pseudo-random key). In actual use, a truly random key should be used.
    8. Message#1


    Here is message#1. The message is a rectangle within the bit pattern.
    9. Encode#1


    Here is encoded message#1. Message#1 has been fully encrypted using the key.
    10. Decode#1


    Here is decoded message#1. Message#1 has been completely recovered.
    11. Message#2


    Here is message#2. The message is a diagonal slash from each opposing corner.
    12. Encode#2


    Here is encoded message#2. Message#2 has been fully encrypted using the key.
    13. Decode#2


    Here is decoded message#2. Message#2 has been completely recovered.
    14. Mixture


    Here is XOR of encoded message#1 and encoded message#2. Re-using the key results in parts of each message being clearly visible. Once a lot of the message is broken, the rest is much easier to break.
    15. Observation
    Can you see parts of message#1 and message#2 in the mixture?

    This results from using (or re-using) the same key.

    In practice, it may not be as easy as this because of aligning a re-used key with a message, but the breaking of the code is much easier than the impossible breaking of the original code (if using a truly random key).
    16. End of page
    by RS  admin@robinsnyder.com : 1024 x 640