The X-Factor (OR The Power of XOR)

Once upon a time, a girl (non-computer scientist) had bought two pieces of cake for coffee. She asked her nerdy boy-friend: ‘Do you want this one or that one?’ He said ‘Thanks!’ and he quickly moved both pieces onto his plate. If you know why he behaved this way, you know you’re into computer science. 😀

What the girl should have said is something like that: ‘Do you want this one XOR that one?‘ (which could be translated for normal people as ‘You may freely choose either this one or that piece of cake.‘)

Most of our real-life decisions are being based on XOR logic rather than just OR. X stands for eXclusive, which means that one of the conditions (namely the condition involving ‘both‘) is excluded.

Not only in real-life, but also in computer science, the XOR is a fundamental logic function. As we will see later in this article, it is used in numerous important technical applications.

The XOR function is usually described by a logic symbol, a truth table, or a boolean equation (or all three of them 😉 ).

1. Adding numbers

In binary system 0+0=0, 0+1=1, 1+0=1, and 1+1=0 ‘carry 1’. If you compare the bold printed numbers with the x-column in the truth table above, it is easy to find out that the sum is the result of an XOR function between both summands.

Thus, a simple electronic circuit that is capable of adding two bits looks like this.

The second logic gate beside the XOR function is being used to generate the carry bit. The carry bit is only set to 1, if  both summands are 1 (which means logic AND).

When adding larger numbers you need to XOR each digit of the number, including the carry bit that is to be considered in all digits except in the least significant bit.

2. OTP (One-Time Pad) Encryption

The result of A XOR B is a measure of “how different A is from B” (or vice versa). If a bit of a word A is different from the same bit of a word B, the resulting bit is 1.

This fact is being used in cryptography. Let us assume you have a piece of plain text, e.g. FLY, which you would like to encrypt with a secret word (key), e.g. EST. This can be easily accomplished by using an XOR function between FLY and EST. So let’s do FLY xor EST (both texts written in 8bit ASCII Code, of course).

01000110 01001100 01011001 (FLY)
01000101 01010011 01010100 (EST)
-------------------------- xor
00000011 00011111 00001101 (encrypted message)
==========================

The result of FLY xor EST is the encrypted message. It is a bit pattern that doesn’t seem to make any sense. If we tried to ASCII-translate this message back into characters, we would only get a bunch of senseless control characters.

Remember, that the resulting bit pattern describes which bits are different between the original plain text and the secret key. In a binary system there aren’t too many options for a bit to be ‘different’, which allows us to decrypt the message in exactly in the same way.

01000101 01010011 01010100 (EST)
00000011 00011111 00001101 (encrypted message)
-------------------------- xor
01000110 01001100 01011001 (FLY)
==========================

This is totally fly, isn’t it?

Although this method of encryption/decryption is amazingly safe, there are some deficiencies. Firstly, it relies on a secret key which needs to be transported from the sender to the receiver. From history we know that this phase can get you into deep shit …

Secondly, if your key is shorter than your message you would probably repeat the key over and over again. Any repetition inevitably adds redundancy to your encrypted message, which makes it easier to break the code. (I won’t describe here how this works, but some of you, dear readers, will have the honor to encounter a similar assignment in your final exam. 😉 )

3. Generating Random Numbers

I know that some of you have made different experience, but your computer is a deterministic machine that always behaves in a logical and predictable way. So it is virtually impossible to use a computer for generating real random numbers.

There are hundreds of different algorithms that allow to generate pseudo-random numbers based on a so-called seed. The seed is a number or a bit pattern that is fed into an algorithm which calculates a sequence of numbers that looks pretty much random. To make the seed less predictable, it is chosen from system time, recent mouse movement, keystrokes since login, etc.

In many applications, however, a cheap and simple pseudo-random generator will do the job. All you need is a linear shift register and – look and behold – an XOR function.

The result of the XOR function is fed back into the rightmost bit of the linear shift register. The two leftmost bits of the shift register form the input of the XOR gate. Although the sequence of numbers will repeat after (2^n) – 1 states, the sequence itself seems to be random. There are numerous ways how to build a pseudo-random generator from a linear shift register that is fed back by one or more XOR gates. This one is not very sophisticated, but in many cases it will be sufficient enough.

Check this out for more information on linear feedback shift registers (LFSR): http://en.wikipedia.org/wiki/Linear_feedback_shift_register

Hint: Write a C program that simulates this principle (an excellent exercise on masking and bit shifting)!

See you,

— Andre M. Maier

Advertisements

About bitjunkie

Teacher, Lecturer, and BITJUNKIE ...
This entry was posted in Bit-Twiddling, Uncategorized and tagged , , , . Bookmark the permalink.