9

I notice that some cryptographic algorithms involve using XOR operation with the key (Even AES uses XOR to derive the round keys). My question is why specifically XOR? How about OR or NAND or some other logic operation. I believe there is a reason behind choosing XOR instead of other logical operation but I really do not know it.

Thank you

8

XOR is an operation that can always be reversed, all information is retained. It is as simple as that. Using AND and OR may result into information loss because you cannot tell if certain bits were either 1 or 0 in the operands.

Playing a little with the python repl, we will use 19 (10011) and 5 (101) since these numbers make for good examples.

Using OR you lose the information about which of the operands had a certain bit on:

>>> bin(19|5)
'0b10111'

Isn't that 19? Yep, that's 19. The resulting number cannot tell us that it has been ORed with 5.

Using AND is the same:

>>> bin(19&5)
'0b1'

That's 1. There is not way for us to recover neither number (19 or 5) easily, we lost information again.

XOR is good for cryptographical tools because you do not lose information when XORing:

>>> bin(19^5)
'0b10110'

That's 22. Apparently that does not tell us much, but see this:

>>> bin(22^5)
'0b10011'
>>> bin(22^19)
'0b101'

You can recover either number by XORing the 22 with the other number. That's a very primitive conception of a secret key. Assuming that you and someone else can have a huge list of very big and random numbers (both of you have the same numbers), you can simply XOR messages and then securely exchange between yourselves. As long as you guys use a different number every time you communicate that is a secure algorithm. The algorithm is called an one-time pad.

  • 4
    19 decimal is 10011 binary, but you have it in several places as 10111 (which is 23 decimal). This makes the OR example not work, although the AND and XOR examples are correct. – Mike McManus Oct 14 '16 at 16:09
  • @MikeMcManus - Hahaha, that was probably the worst typo i did in here. I first did all the output in python and only then copied (the wrong pieces :) ) in here. Thanks for finding it. – grochmal Oct 14 '16 at 17:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.