# Is all of encryption based on xor?

For a long time I've been under the impression that all of encryption uses xor at its basic level.

Is this true? What other method could be used to encrypt plaintext with a key? Asymmetrically, as while as symmetrically?

There are hundreds of ciphers, aes, blowfish, ect. They are all different, but do they all rely on xor?

It is a dumb question, however it was never asked (at least on google).

• Most (if not all) modern block ciphers involve nonlinear (w.r.t. $\mathbb{F}_2$) operations. That means you have at least a few AND gates in there. – Aleph Feb 23 '16 at 22:08

You don't have to use XOR, but rather, it tends to be convenient. One of its convenient properties is that it is its own inverse. Also, XOR implements addition in $\mathbb F_{2^n}$, making XOR a key component of working in finite fields of characteristic $2$, if you want to use them in an algorithm.

The "one-time pad" is usually defined as taking a random key the same size as the input and XORing them together to produce the ciphertext. If you changed XOR to addition, whether $\mod 256$ or considering the entire input to be one large number, it would still be perfectly secure. It just wouldn't be its own inverse - decryption would require subtraction instead of addition.

RC4 was considered secure for years, and though somewhat broken in modern times, it can serve as an example. RC4's algorithm revolves around swapping bytes in an S-box, then determining a byte to XOR with the plaintext.

If you modified RC4 to do $\mod 256$ addition instead of XOR, it would have the same security as standard RC4. However, it then wouldn't be its own inverse; decryption would require an RC4 that uses $\mod 256$ subtraction.

asymmetric cryptosystems like RSA and ElGamal don't use XOR and they are based on number theory but XOR is very powerful,if you have planintext$\oplus$Key and your key is random number,but your plaintext is not random then the result of planintext$\oplus$Key is random,in other words XOR operation prevents from statistical properties attacks like frequency analysis. XOR is very fast and simple for implementation so it is a standard part of almost all symmetric cryptosystems like DES,AES,....

The NSA has called Vernam's patent (that is the same XOR ) "perhaps one of the most important in the history of cryptography"

• @akbr: Not to mention that, even if XOR has not to be part of the actual ciphering itself, it is part of many algorithms around it. See OpenBSDs HMAC function along with the key derivation function. Upvoted. – try-catch-finally Mar 21 '16 at 19:33

Most public key cryptography is based on much more than XOR, e.g., arithmetic over integer rings and fields ($\mathbb{Z}_{pq}$ for RSA, $\mathbb{Z}_{p}$ for El Gamal), additive groups of elliptic curves, multivariate polynomial rings over finite fields (NTRU).

Most symmetric key cryptography is based on XOR in addition to other field operations (at the circuit level AND is also used, see answer by @Myria above for more details).