Main content
XOR bitwise operation
The ultimate shift cipher
If you’ve seen the lesson on the one-time pad, you know that it is the ultimate shift cipher. It involves the application of a random list of shifts equal to the length of the message. It’s important to understand exactly how and why the one-time pad is unbreakable, or, perfectly secret.
To understand why, we need to first introduce the AND, OR and XOR bitwise operations. Specifically why XOR must be used when performing the one-time pad on computers. Bitwise simply means that we are dealing with individual bits, or binary numbers. In any modern/computerized encryption scheme we represent our symbols using binary digits. If you forgot why, you can check out this video on Computer Memory
Encrypting Colors
Let’s begin with a visual example by encrypting the color of the Khan Academy green leaf avatar.
How do we turn a color into a number? Well, right now you are looking at HTML colors which are defined using the RGB color model. This is an additive model based on mixing some amount of red, green and blue light.
We can define exactly how much RED, GREEN and BLUE using a number from 0-255. Black is all off (0,0,0) while white is all on (255,255,255). In between there are 16 million possible colors (256 * 256 * 256). Next let’s sample the green in the Khan Academy leaf in any image editing tool:
Notice it stores it as RED=156, GREEN=181, BLUE=58.
If we express these numbers in binary we get:
RED=10011100, GREEN=10110101, BLUE=00111010.
RED=10011100, GREEN=10110101, BLUE=00111010.
We can squeeze those together as:
100111001011010100111010
Binary RGB representation of the Khan Academy green:
Application of random shifts
Now let’s say you generate a shift sequence using coin flips converted into binary as:
HTHTTHTHHHHTTHTTTTHTTHHH = 010110100001101111011000
Let’s think about how we could apply this shift sequence to our color in order to encrypt it using the one-time pad:
100111001011010100111010 + 010110100001101111011000 =
To make the one-time pad work we need to choose the correct operation so that the resulting sequence is equally likely to be any color. Let’s go over three different operations, AND, OR, XOR.
AND
The AND operator is also known as logical conjunction, and works just like multiplication.
It outputs a 1 only if all of the inputs are 1. Here is the truth table:
It outputs a 1 only if all of the inputs are 1. Here is the truth table:
0 AND 0 = 0
0 AND 1 = 0
1 AND 0 = 0
1 AND 1 = 1
Let’s try it:
100111001011010100111010 AND 010110100001101111011000 = 000110000001000100011000
This results in a very dark purple. Notice when we perform the AND operation on any binary number, the resulting sequence cannot be larger. In our color example this eliminates many possible shades as it pushes the color towards black.
OR
The OR operator is also known as logical disjunction. It outputs a 1 whenever one or more of its inputs are 1. Here is the truth table:
0 OR 0 = 0
0 OR 1 = 1
1 OR 0 = 1
1 OR 1 = 1
Let’s try it:
100111001011010100111010 OR 010110100001101111011000 = 110111101011111111111010
This results in a light purple. Notice when we perform the OR operation on any binary sequence, the resulting sequence cannot be smaller. This eliminates many possibilities as it pushes the color towards white.
XOR
The XOR operator outputs a 1 whenever the inputs do not match, which occurs when one of the two inputs is exclusively true. This is the same as addition mod 2. Here is the truth table:
0 XOR 0 = 0
0 XOR 1 = 1
1 XOR 0 = 1
1 XOR 1 = 0
Let's try it:
100111001011010100111010 XOR 010110100001101111011000 = 110001101010111011100010
This results in a slightly darker purple as compared to the OR operation. Notice when we perform the XOR operation on a binary sequence, the resulting sequence could be any possible sequence. Given some encrypted color, all we know is the original color is “equally likely to be any color”. We have no information that could improve a blind guess (1/16 million).
Finally, let’s do a visual demonstration so that we can see the one-time pad in action. Then we can earn more energy points!
Want to join the conversation?
I'm not sure to understand why XOR is more difficult to revert than AND or OR. Are the two later possibly reversible anyway? What kind of clue could Eve get from such a string if she knew it was AND-ed or OR-ed?(14 votes)
AND is not always reversible. For example, 1010 AND 1110 => 1010, but also 1011 AND 1110 => 1010, so I cannot always tell what my original number is if I use AND.
Similarly with OR, 1010 OR 1110 => 1110, but also 0000 OR 1110 => 1110.
I do not think XOR is more difficult to reverse if you know the pad (in fact it is very simple). However, it is impossible to reverse if you do not know the pad.
If Eve got a string that was AND-ed, she would know that every 1 was in the original string. Similarly, if she got a string that was OR-ed, she would know that every 0 was in the original string.(46 votes)
Is the ease of guessing the only reason why we should not use AND or OR ciphers? I was expecting the reason to be that AND and OR ciphers cannot be decrypted in many cases. As an example, if 101 is our message and 110 is our key, then the XOR-ciphertext would be 011. With the key, this can be easily decrypted to 101 again. However, the AND-ciphertext would be 100. With this and the key, we are still unable to conclude if the original text was 100 or 101. Since both are possible, this would effectively render the cipher redundant, as not even the intended recepient would be able to decipher it.(19 votes)
Exactly! It is somewhat odd that they don't mention that in the lesson, but that is a good thing to notice.(3 votes)
how are ordinary numbers converted to binary numbers(4 votes)- Suppose we want to represent a decimal number as a 8 bit binary number. Is the number divisible by 2 to the 7th power? If so, our first binary digit (bit) is 1, we subtract that power of 2 from our decimal number and keep the remainder (call it r7). If not our first bit is 0 and we use the same number as our remainder. Is this r7 divisible by 2 to the 6th power? Repeat the process to get bit 2 and r6. Continue until you get to 2 to the 0th power (or 1) which gives us our last bit. So 140 is divisible by 128 (2^7) and the remainder is 12. 12 is divisible by 8 (2^3) and leaves 4 which is divisible by 2^2. So we have one's bits in the 7, 3, and 2 places and zero's elsewhere. 140 decimal = 1000110 binary.(13 votes)
I understand how the XOR Operator is "the same as addition mod 2", as Brit describes. However, earlier in the post he also says that the OR Operator "works just like Addition Modulo 2". According to this description, how would that make the OR Operator any different than the XOR Operator?(5 votes)
I think Brit Cruise made a mistake here, only the XOR operation is like addition mod 2. He will most likely see your post here, fix the mistake. And then respond back to you. The difference with the OR operator is that while in XOR, 1 XOR 1 = 0, in OR, 1 OR 1 = 1.
As you can see in the OR case, OR is not the addition mod 2 operator, but XOR is. However, except for that case, XOR and OR are completely the same.
I hope this helps!(8 votes)
- There should be more excercises for cryptography(4 votes)
Yeah, I agree, this is kinda confusing.(2 votes)
- "Notice when we perform the AND operation on any binary number, the resulting sequence cannot be larger."
Cannot be larger than what?(2 votes)
The concept, "cannot be larger" refers to the value of the answer. The result of the AND operation pushes values lower, since the truth table gives a zero for all cases except where both inputs are a 1. So it will output a zero for 3 out of 4 possible input combinations. More zeroes in the answer will be a smaller numeric value, and this is why it resulted in a darker output - zero is black in the color map.
The concept is similar for the OR operation. Its truth table shows a result of a 1 in all cases except when both inputs are zero. This means 3 out of 4 possible cases will result in a 1 output, pushing the output toward favoring ones. All ones would be 255, which maps to white.(6 votes)
Is XOR a word, or does it stand for something(2 votes)
I believe the X is short for eXclusive, then it is an "exclusive or" check or XOR.(2 votes)
- How do you read the "XOR"? "Ex or" or "ksor" or what?(2 votes)
It's short for Exclusive OR, so "Ex or" xor "eksor" would be pretty close.(4 votes)
How could I make bianary addition with only Xor oporators? I was making a computer in Mario Maker and I need to know.(3 votes)- So is possible to use XOR and OR at the same time to get a different color since it say there is 16 million possible colors?(3 votes)
