Main content
Computer science theory
XOR and the one-time pad
Why must we use XOR?
Does it really matter if we used AND, OR or XOR with the one-time pad? The answer is yes, and it’s extremely important to understand why. Recall from the previous article that AND has a 75% chance of outputting 0 and a 25% chance of outputting a 1. While OR has a 25% chance of outputting 0 and 75% chance of outputting 1. While the XOR operation has a 50% chance of outputting 0 or 1.
Let’s look at a visual example to see the different scrambling effects of AND vs. OR vs. XOR by encrypting an image. Here is a digital image of Charles Babbage:
It contains thousands of tiny colored squares called pixels. Each pixel in this image can be represented as a 24 bit sequence as shown in the previous article. Let's call this our plaintext image (or message).
First let’s see what happens when we AND each bit in the image file with a stream of random bits.
AND
Notice most of the original message shines through. This happens anytime a random shift of 1 is applied, or when the plaintext is 0:
Next let’s see what happens when we OR each bit in the image file with a stream of random bits.
OR
Notice most of the original message shines through. This happens anytime a random shift of 0 is applied, or when the plaintext is 1:
Finally, let’s see what happens when we XOR each bit in the image file with a stream of random bits.
(drum roll please...)
XOR
Where did Charles go?
Notice that the plaintext only shines through 50% of the time, which results in noise as each pixel is equally likely to be 0 or 1.
This image contains no information about the original image. If we didn’t provide the shift sequence it would be impossible for you to reverse it back to the original image. You could try every possible sequence, but that would result in every possible image! How could you know it was Babbage? It's equally likely to be a picture of you or anything else you can think of.
Notice that the plaintext only shines through 50% of the time, which results in noise as each pixel is equally likely to be 0 or 1.
This image contains no information about the original image. If we didn’t provide the shift sequence it would be impossible for you to reverse it back to the original image. You could try every possible sequence, but that would result in every possible image! How could you know it was Babbage? It's equally likely to be a picture of you or anything else you can think of.
Isn’t that interesting? Makes me smile everytime I see it!
Next, let’s practice the XOR, OR and AND operators and discover some more interesting properties while doing so....
Want to join the conversation?
What if I crossed my eyes and looked at the XOR image real hard, would I be able to see a little bit of the original image? =D(16 votes)
Well, you are seeing half of the original image as it is, you just don't know which half is the image and which half is simply "noise" But in terms of actually identifying the original image, that is impossible at this point(13 votes)
The end of the article claims "This image contains no information about the original image." But is that right? In the last article, the one time pad was only a few dozen bits. Now this image is thousands of times longer. If the one time pad is short, and the message is long, doesn't information leak? (It seems like probably the encrypted version used a one time pad the same size as the image, but reading this article and the last one, you might not think so.)(4 votes)
Indeed the one time pad must be the same size as the image to prevent information from being leaked. A stream of random bits is used, so we can safely say that the size of the one time pad equals the size of the message (in this case the picture is the message).(11 votes)
What do you mean by "This happens anytime a "RANDOM SHIFT" of __ is applied..." ? What does this have to do with anything, or what does this mean? Thanks(5 votes)- In the AND demonstration, "This happens anytime a random shift of 1 is applied [...]" simply means that the original image data is unchanged when a 1 in the series of random binary digits is used to operate on the image data by means of the AND operation.
Why? Take a look at the possibilities:
Image data in random bit image data out
0 1 0
1 1 1
As you can see the image data out is the exact same as the image data in when the random bit is 1.(7 votes)
Can't we use any other boolean logic which also have the equal probability of 1 and 0 i.e. 50% for both?
For example XNOR or something beyond that?(4 votes)
My gut feeling (non-scientific) is that there are probably a number of randomizing operations but you need to ask what are the trade-offs. CPUs and GPU's can innately do XOR very fast. As to XNOR my first thought was that XNOR would be just as good but further pondering lead me to this problem:
XNOR outputs a one whenever both inputs are the SAME. So in the case of XOR the information a third party can work with is that the inputs were different. They have no way to figure out whether the key was one and the data was zero or the other way round.
I am not sure that the additional information (that both inputs are the same) would translate into a weaker cypher or not.
Mark(4 votes)
I understand why AND gives a darker picture than normal and why OR gives a lighter picture than normal, but why do they bear any resemblance to the original picture? Why don't AND and OR give the same result as XOR but lighter or darker?(3 votes)- With respect to the pixels in the original image, here's what happens:
AND:
- All the white pixels will be displayed correctly
- Half of the black pixels will be displayed correctly
OR:
- All the black pixels will be displayed correctly
- Half the white pixels will be displayed correctly
XOR:
- Half of the white pixels will be displayed correctly
- Half of the black pixels will be displayed correctly
So for the AND and OR one of the colors is being displayed correctly and the opposite color looks like noise. For XOR, both of the colors look like noise.
Hope this makes sense(3 votes)
How did you encrypt the image? Pixel over pixel or what?(3 votes)
Say that we want to encrypt this much much much smaller image with only 9 bits and we want to encrypt it using AND:
0 1 0
0 1 0
0 1 0
then let's generate a random sequence of 9 bits:
0 0 1
1 1 1
1 1 0
then we do it pixel by pixel:
0 AND 0 = 0
1 AND 0 = 0
0 AND 1 = 0
And so on...
And we get:
0 0 0
0 1 0
0 1 0
The same works for more 0's and 1's.
Note: This is only for Black and White images.
For colored images you actually encrypt the colors also because we can represent color with 0's and 1's too.(1 vote)
Can we use NANDs and NORs and XNORs and get the same desired effect, or would there be someone sort of difference?(3 votes)
Nands and Nors have the same weaknessess as Ands and Ors. But Xnor is just as strong as Nor.(1 vote)
- i have no idea what yo are talking about, yo(0 votes)
How do you undo the XOR operation? Given the pad and the final result how do you get back to the original?(2 votes)
JustXORagain, sinceXORis its own inverse.(2 votes)
So, if I may ask, the binary code can only consist of 1's and 0's. How long can this code on for.(2 votes)- As long as you have enough memory or storage, it could go on infinitely.(2 votes)
