Why is XOR used on Cryptography?

Question

Why is XOR only used in the cryptographic algorithms, and other logic gates like OR, AND and NOR are not used?

Answer 1

The output of XOR always depends on both inputs. This is not the case for the other operations you mention.

Answer 2

It isn't exactly true to say that the XOR gate is the only one used throughout all cryptography, however it is the only two way encryption where it is used exclusively.

Here is that explained:

Imagine you have a string of binary digits '10101' and you XOR the string '10111' with it you get '00010'

now your original string is encoded and the second string becomes your key if you xor your key with your encoded string you get your original string back.

XOR allows you to easily encrypt and decrypt a string, the other logic operations don't.

If you have a longer string you can repeat your key until its long enough for example if your string was 1010010011 then you'd simple write your key twice and it would become 1011110111 and xor it with the new string

Here's a wikipedia link on the XOR cipher http://en.wikipedia.org/wiki/XOR%5Fcipher

Answer 3

I think because XOR is reversible. If you want to create hash, then you'll want to avoid XOR.

Answer 4

XOR is the only gate that's used directly because, no matter what one input is, the other input always has an effect on the output.

However, it is not the only gate used in cryptographic algorithms. That might be true of old-school cryptography, the type involving tons of bit shuffles and XORs and rotating buffers, but for prime-number-based crypto you need all kinds of mathematics that is not implemented through XOR.

Answer 5

For symmetric crypto, the only real choices operations that mix bits with the cipher and do not increase length are operations add with carry, add without carry (XOR) and compare (XNOR). Any other operation either loses bits, expands, or is not available on CPUs.

Answer 6

XOR acts like a toggle switch where you can flip specific bits on and off. If you want to "scramble" a number (a pattern of bits), you XOR it with a number. If you take that scrambled number and XOR it again with the same number, you get your original number back.

210 XOR 145 gives you  65  <-- Your "scrambled" result
 65 XOR 145 gives you 210  <-- ...and back to your original number

When you "scramble" a number (or text or any pattern of bits) with XOR, you have the basis of all cryptography.

Answer 7

XOR uses fewer transistors (4 NAND gates) than more complicated operations (e.g. ADD, MUL) which makes it good to implement in hardware when gate count is important. Furthermore, an XOR is its own inverse which makes it good for applying key material (the same code can be used for encryption and decryption) The beautifully simple AddRoundKey operation of AES is an example of this.

Answer 8

Let's consider the three common bitwise logical operators

Let's say we can choose some number (let's call it the mask) and combine it with an unknown value

• AND is about forcing some bits to zero (those that are set to zero in the mask)
• OR is about forcing some bits to one (those that are set to one in the mask)

XOR is more subtle you can't know for sure the value of any bit of the result, whatever the mask you choose. But if you apply your mask two times you get back your initial value.

In other words the purpose of AND and XOR is to remove some information, and that's definitely not what you want in cryptographic algorithms (symmetric cipher or digital signature). If you loose information you won't be able to get it back (decrypt) or signature would tolerate some minute changes in message, thus defeating it's purpose.

All that said, that is true of cryptographic algorithms, not of their implementations. Most implementations of cryptographic algorithms also use many ANDs, usually to extract individual bytes from 32 or 64 internal registers.

You typically get code like that (this is some nearly random extract of aes_core.c)

rk[ 6] = rk[ 0] ^
 (Te2[(temp >> 16) & 0xff] & 0xff000000) ^
 (Te3[(temp >>  8) & 0xff] & 0x00ff0000) ^
 (Te0[(temp      ) & 0xff] & 0x0000ff00) ^
 (Te1[(temp >> 24)       ] & 0x000000ff) ^
 rcon[i];
rk[ 7] = rk[ 1] ^ rk[ 6];
rk[ 8] = rk[ 2] ^ rk[ 7];
rk[ 9] = rk[ 3] ^ rk[ 8];

8 XORs and 7 ANDs if I count right

Answer 9

I think its simply because a given some random set of binary numbers a large number of 'OR' operations would tend towards all '1's, likewise a large number of 'AND' operations would tend towards all zeroes. Wheres a large number of 'XOR's produces a random-ish selection of ones and zeroes.

This is not to say that AND and OR are not useful - just that XOR is more useful.

The prevalence of OR/AND and XOR in cryptography is for two reasons:-

One these are lightning fast instructions.

Two they are difficult to model using conventional mathematical formulas