If you're seeing this message, it means we're having trouble loading external resources on our website.

If you're behind a web filter, please make sure that the domains *.kastatic.org and *.kasandbox.org are unblocked.

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:
Screenshot of the Photoshop color picker, with green selected.
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.
We can squeeze those together as: 100111001011010100111010
Binary RGB representation of the Khan Academy green:
Green background with 100111001011010100111010 on top

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 = start text, question mark, end text
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:
0 AND 0 = 0
0 AND 10
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
dark purple
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?

  • piceratops ultimate style avatar for user max dml
    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?
    (2 votes)
    Default Khan Academy avatar avatar for user
    • aqualine ultimate style avatar for user JaniceHolz
      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.
      (41 votes)
  • blobby green style avatar for user Aalap Shah
    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.
    (18 votes)
    Default Khan Academy avatar avatar for user
  • duskpin ultimate style avatar for user Vasudev Pai
    how are ordinary numbers converted to binary numbers
    (4 votes)
    Default Khan Academy avatar avatar for user
    • piceratops ultimate style avatar for user compdoc1300
      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)
  • leaf green style avatar for user SteveSargentJr
    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)
    Default Khan Academy avatar avatar for user
    • leaf red style avatar for user Noble Mushtak
      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)
  • blobby green style avatar for user Yoel Ivan
    "Notice when we perform the AND operation on any binary number, the resulting sequence cannot be larger."
    Cannot be larger than what?
    (2 votes)
    Default Khan Academy avatar avatar for user
    • male robot hal style avatar for user wes.strubhar
      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)
  • winston default style avatar for user ☺☻☺Natth4545☺☻☺
    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)
    Default Khan Academy avatar avatar for user
  • aqualine ultimate style avatar for user dmkgigi
    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)
    Default Khan Academy avatar avatar for user
  • winston baby style avatar for user Joesufph
    Is XOR a word, or does it stand for something
    (2 votes)
    Default Khan Academy avatar avatar for user
  • leaf green style avatar for user Alexander Wu
    How do you read the "XOR"? "Ex or" or "ksor" or what?
    (2 votes)
    Default Khan Academy avatar avatar for user
  • leafers tree style avatar for user Nadeem Latif
    Concerning the AND and OR sections, it says that the resulting sequence 'cannot be larger' and 'cannot be smaller' respectively. Does this mean that an AND operator can be smaller and, vice versa for the OR operator? If so, how?
    (2 votes)
    Default Khan Academy avatar avatar for user
    • male robot hal style avatar for user Cameron
      Let's look at
      A AND B = C
      If A is 0, then the result C will always be 0
      If A is 1, then the result C may be a 0 or 1 depending on the value of B
      So no matter what, C will be <= the value of A

      Let's look at
      A OR B = C
      If A is 0, then the result C may be a 0 or 1 depending on the value of B
      If A is 1, then the result C will always be 1
      So no matter what, C will be >= the value of A

      Examples with multiple digits:
      101 AND 100 = 100
      100 <= 101

      101 OR 110 = 111
      111 >= 101

      The maximum amount of these effects are seen in the following cases:
      any number AND a number with all 0 digits = a number with all 0 digits
      a number with all 0 digits is the smallest possible number
      e.g. 101 AND 000 = 000

      any number OR a number with all 1 digits = a number with all 1 digits
      a number with all 1 digits is the largest possible number
      e.g. 101 OR 111 = 111

      Hope this makes sense
      (3 votes)