XOR should be an English word
Soup xor salad? This question is much clearer than Soup or salad. Why? As we are going to see in this article, the word XOR would not allow choosing soup and salad, which is not expected, but it is an allowed option when the word OR is used.
What is XOR anyway?
Comparing XOR and OR
Table for the XOR function:
Table for the OR function:
The only difference between XOR and OR happens for A=1 and B=1, where the result is 0 for XOR and 1 for OR.
Real Life, OR or XOR?
In real life we say OR, but usually the intention is actually XOR, lets see some examples:
Mom: Son, where is your father?
Son: Working on the garden OR on the couch watching the game.
One condition excludes the other, Dad can’t be at both places at the same time, he is either working on the garden or on the couch watching the game. We know Mom is sure that, given the options, he is watching the game…
Lets see all of this in a table. The Where is your father function:
|Working on the garden||On the couch||Found!||Comments|
|0||0||0||Not found! (unexpected)|
|0||1||1||on the couch (Mom knew it!)|
|1||0||1||working on the garden (improbable)|
|1||1||0||Invalid, he can’t be in two places at same time|
The function returns 1 (Found!) when the inputs are exclusive. Exclusive here with the meaning of one different from the other.
Mom: Would you please buy ice cream, chocolate OR strawberry.
Son: Here are the ice creams, chocolate and strawberry.
One condition should exclude the other, but the son, very smart, used the inclusive OR. In this case Mom’s request was ambiguous. A non ambiguous request would be: Would you please buy ice cream, chocolate XOR strawberry.
The Reason for the XOR Name
Given both examples, I have found two different reasons for the name XOR, the first one sounds more reasonable than the second, but please let me know if you have a good source for the XOR name.
- XOR, exclusive OR, is TRUE when both inputs are exclusive or not equal.
- XOR, exclusive OR, excludes one of the OR conditions, XOR excludes the condition where both inputs are TRUE.
Again, I believe explanation 1) is more logical, but naming things are not a logical.
How to get to 0xDEAD
A teaser was left in Dissecting a Minimum WebAssembly module: How to get to 0xDEAD by XORing 0xFF00 and 0x21AD?
The simplest method to get to the result is to convert the numbers to binary and then apply the XOR table bit by bit:
0xFF00 é 1111.1111.0000.0000 0x21AD é 0010.0001.1010.1101 XORing: 1101.1110.1010.1101 -> DEAD
XOR is Also an Adder, or Half of it
Below is the A+B table, compare it with the XOR table.
|1||1||0 and 1 should be added to the next bit (carry bit)|
They are the same table, the only problem with the XOR as an adder, is that it can’t generate the carry bit for the condition where A=1 and B=1. This is the reason it is called half adder.
XOR Also Utilized in Cryptography
Lets go back to the example where XORing 0xFF00 and 0x21AD results in 0xDEAD. Lets name these numbers in cryptographic terms:
0xFF00 The original message, in the clear, unencrypted(M).
0x21AD The cryptographic key, both the sender and receiver know these number, this is the shared secret(C).
0xDEAD The Encrypted message(E).
To encrypt the message we use the following XOR operation: E=XOR(M,C)
Someone (an adversary) that reads the encrypted message 0xDEAD can’t figure out the original message 0xFF00 without knowing the 0x21AD cryptographic key, but the receiver can decrypt the message into its original form by applying this XOR operation: M=XOR(E,C). Here is an example with numbers:
0xDEAD é 1101.1110.1010.1101 -> Encrypted message 0x21AD é 0010.0001.1010.1101 -> Cryptographic key XORing: 1111.1111.0000.0000 -> Original message was recovered!
In short: XOR makes cryptography possible because it allows recovering the original message:
M Original message.
C Cryptographic key
E Encrypted message.
To encrypt a message:
To decrypt the message: