© Andy Wilson, 1998

Tips and Tricks: XOR Encryption

Following on from last monthís article on encryption, this month we will be looking at a far more secure method of encrypting strings in lingo. If you remember, last month I showed you how to encrypt a string by ëshiftingí all the characters in a message. That was enough for basic encryption. This month, however, weíre looking at an encryption scheme that is much tougher for the would-be hacker to break.

The ëXORí in XOR encryption stands for the logical ëexclusive orí function, and we will have to understand this function if we are to understand how our new encryption scheme works. In a regular OR test we compare statements of the form a OR b, and the result is TRUE if any of the constituent statements is TRUE. So, for example, if statement a is TRUE, then the whole statement is TRUE, if b is TRUE then the whole statement is TRUE. In fact, the whole statement, a OR b, is FALSE if and only if all of itís constituent statements is FALSE ñ if both a and b are FALSE. This is the logical test you are carrying out when you write something like if ((varA > 10) or (varB < 4)) then beep in lingo. Here, the statement (varA > 10) is equivalent to statement a, and the statement (varB < 4) is our statement b. Youíll hear a beep if the variable varA is greater than 10 or varB is less than 4, or both. The truth table for such a relationship is as follows:

Now, the exclusive or function works in a similar way but with one qualification ñ an exclusive or logical function evaluates to TRUE when either of the constituent statements is TRUE, but not if both are TRUE. In other words, a XOR b is TRUE if a is TRUE or b is TRUE but not if both are FALSE or both are TRUE: for the XOR function to evaluate to TRUE one of the constituent statements has to be ëexclusively trueí. This is equivalent to saying that the XOR statement evaluates to TRUE if and only if the value of the two constituent statements have different values. The truth table for this function, then, looks like this:

Iíve highlighted the one case in which the XOR test gives a different result to the OR test ñ the case where both a and b are true produces a TRUE result in the OR test but a FALSE result in the XOR test.

Thatís all the logic we need to understand for the purposes of building our encryption engine. Far more important to us is one peculiar characteristic of the XOR function. To understand this feature, imagine that we have a binary number a and we XOR it with a binary number b as follows:

To do this calculation we compare each digit in each number and XOR them to get the corresponding digit in the resulting number. We treat a 1 as a Boolean TRUE, and a 0 as Boolean FALSE. Reading from left to right, the first digit of number a, is a 1 / TRUE, the first digit of number b is also a 1, therefore the first digit of the resulting digit is 1 XOR 1 (TRUE XOR TRUE) which, as we can see from our XOR truth table above, evaluates to FALSE, or 0. This means that the first digit of our result is a 0. The second two digits in our numbers are a 0 and a 1, so the second digit of the result is a 1, and so on.

Now the interesting thing about all this is what happens if we XOR the result of this operation with the original number b:

Whatís happening here is actually very interesting. If we take the result of our original calculation and XOR it with the original number b, the result is the original number a. To see how we can make use of this, imagine that a is a message or piece of information we wish to keep secret. Now think of b as a key we are using to encrypt a, and think of the XOR result as the encrypted message. What this means is that if you and I both know the ëkey numberí, then you can use it to encrypt the original number and send the result to me, and I can then use the same key to decrypt the result.

Of course, so far we have only talked about binary numbers, and you could be forgiven for wondering what all this has to do with encrypting strings. The relevance becomes obvious as soon as you remember that in computing all characters are represented by numbers. The number value of any character can be found by using the lingo function charToNum (). So, if you want to know the numeric value of the character ëaí you can use lingo to find it as follows:

put charToNum ("a")
-- 97

Now, the number 97 is represented in binary as 01100001. If I wanted to encrypt the letter ëaí to send it to you all we would have to do is agree a ëkeyí character. If I encrypt the character using our agreed key the result would be meaningless to anyone who didnít also know the key. I could send you the encrypted information quite safely since anyone who intercepted it would be unable to decode it without the key. I, on the other hand, only need to apply the key to the encrypted result to recover the original information.

Letís pursue this example by assuming that our agreed key is the letter ëzí. The value of z is 122, which in binary is 01111010. If we XOR our information with our key we get:

The binary result 00011011 corresponds to decimal 27. We can convert this into a character using the lingo function numToChar (). In this case the result is a control character:

put numtochar(27)
-- ""

So, if I were to send you this control character in a message, and if we had agreed to use the character "z" as our encryption / decryption key, then you could easily ëdecodeí the message to retrieve the original information ñ the letter "a". Anyone who intercepted the message on itís way would not be able to understand it since they wouldnít know the key. So far so good.

Now, you may be wondering about the relevance of an encryption method that uses a single character or number to encrypt another individual character. In fact it is easy enough to encrypt a whole string using as a key not a single letter / number, but another string. But before we do this letís look at some of the lingo we will need to do our encryption. In the first place we will need a function that converts a character into a binary. In fact we are going to be working not with binary numbers but with binary strings, which is to say that when we talk about binary numbers in what follows we are actually dealing with a string representation of such numbers.

The code we will need to convert a character into a binary string is as follows:

on charToBin character
  return decToBin (charToNum (character), 256)
end

on decToBin num, divisor
  set hiNum = num / divisor
  set loNum = num mod divisor
  set divisor = sqrt (divisor)
  set opStr = EMPTY
  if (divisor > 1) then
    set opStr = opStr & decToBin (hiNum, divisor)
    set opStr = opStr & decToBin (loNum, divisor)
  else
    return (string (hiNum) & string (loNum))
  end if
  return opStr
end

The charToBin function works by taking a character, calculating itís decimal value using the charToNum lingo function, then passing it on to the decToBin handler. The decToBin handler is recursive ñ it calls itself in order to do its work. To see what it is doing, imagine that you pass it a decimal number and follow your way through to see what it is up to. Youíll see that it works by dividing the number passed to it by successively smaller binary values (256, 128, 64, 32, 16, 8, 4, 2, 1). If the binary divisor fits into it, the resulting binary string has a "1" appended to it, otherwise it has a "0" appended. The binary value is then deducted from the original value, and the whole process is repeated on the remainder. If you are interested in how this works, study the code ñ you can type it into PREector and use the debugger to follow it through its workings. If you find it all too complicated, donít worry, all you need to understand to use this code is that it converts any character into itís corresponding binary string.

Before we go any further you might find it useful to build a handler to strip any superfluous leading 0ís from the binary result:

on trimBinary binStr
  set startPosn = offset ("1", binStr)
  if startPosn then
    set opStr = char startPosn to ¬
		length (binStr) of binStr
  else
    set opStr = "0"
  end if
  return opStr
end

We can now use these handlers as follows:

put charToBin("a")
-- "0000000001100001"
put trimBinary ("0000000001100001")
-- "1100001"
put trimBinary(chartobin("a"))
-- "1100001"

The next handler we need works in the opposite PREection, turning a binary string back into a character:

on binToDec binStr
  set binStr = trimBinary (binStr)
  set len = length (binStr)
  set binMultiplier = 1
  set outcome = 0
  repeat with x = len down to 1
    set thisBit = char x of binStr
    if (thisBit = "1") then set outcome = ¬
		outcome + binMultiplier
    set binMultiplier = binMultiplier * 2
  end repeat
  return outcome
end

The way this works is very simple. The binary string is examined from right to left. If the rightmost character (corresponding to the least significant digit) is a "1" then the binMultiplier variable, which is originally set to 1, is added to the outcome. The binMultiplier is then doubled. The next time around the loop, the next character to the left is examined, if it is a "1" then binMultiplier is added to the outcome. The binMultiplier is doubled again. And so on. Once again, you may find it interesting to follow the code through to see how it works, but all you really need to know is that the code will convert a binary string into the corresponding decimal value, just as the earlier handler converted the decimal into a binary string.

Now we need a binToChar handler that goes one step further and turns a binary value into itís character equivalent. The handler is as follows:

on binToChar binStr
  return numToChar (binToDec (binStr))
end 

Now we have two complementary handlers, so we get:

put charToBin ("a")
- - "0000000001100001"
put binToChar ("0000000001100001")
- - "a"
put binToChar (charToBin ("a"))
-- "a"

Before we get into coding our encryption engine we need to build one final utility handler. This is the handler that XORís two characters:

on xor char1, char2
  set num1 = charToBin (char1)
  set num2 = charToBin (char2)
  set len = length (num1)
  set result = EMPTY
  repeat with x = 1 to len
    if (char x of num1 <> char x of num2) then
      put "1" after result
    else
      put "0" after result
    end if
  end repeat
  return binToChar (result)
end

This works by taking two input characters, turning each into a binary string, XORing the two and converting the resulting binary string back into a character. The actual XORing of the two binaries takes place in the repeat loop. The two input binary strings are compared character by character from left to right. If the two characters are different (if one is a "1" and one a "0") then the corresponding character in the output binary is a "1". If the two input characters are the same (both are "1"s or both are "0"s) then the output character is a "0".

The point about the xor handler is that it works both as an encryption and decryption handler. If we pass a message character and a key character to it we get an encrypted character, and if we pass the encrypted character and key character we get the original message character returned:

put xor ("a","z")
-- ""
put xor ("", "z")
-- "a"

Now we have our basic handlers in place we can build on them to produce the encryption engine we need. What we want to do is to use not a single character but a whole string as our encryption key. Letís imagine that we agree to use as our key the string "aberacadabera". What we will do is use the first character of our key to encrypt the first character of the message, the second character to encrypt the second, and so on. In the likely case that the message is longer than the key, all we need to do is ëwrap aroundí and start at the beginning of the key all over again. The code for the handler that does this is as follows:

on encode inputStr, key
  set strLen = length (inputStr)
  set keyLen = length (key)
  set result = EMPTY
  
  set keyPos = 1
  repeat with x = 1 to strLen
    set thisChar = char x of inputStr
    set keyChar = char keyPos of key
    set newChar = xor (thisChar, keyChar)
    put newChar after result
    set keyPos = keyPos + 1
    if keyPos > keyLen then set keyPos = 1
  end repeat
  return result
end

Since all of the encryption in this engine is based on the xor handler, the same applies to this encode handler as applied to the xor handler itself ñ it works in both PREections. If you pass it your original message and the key, it outputs the encrypted message. If, on the other hand, you pass it the encrypted message and the key it outputs the original message. In other words, the encode handler is used both the encrypt the message and then decrypt it:

set msg = "Secret Message"
set key = "Aberacadabera"
set res = encode (msg, key)
put res
- - ""
put encode (res, key)
- - "Secret Message"

Here exactly the same handlers are applied to a longer message:

set msg = "Since all of the encryption ¬
	in this engine is based on the xor ¬
	handler, the same applies to this ¬
	handler as applied to the xor method ¬
	itself - it works in both diections."
set key = "The secret of good encryption ¬
	is to use a long key string - the ¬
	longer it is, the harder it will ¬
	be for anyone to crack your encoding."
set res = encode (msg, key)
- - hereís the encrypted message that ¬
	you send to me
put res
- - "
CE-TOFTO
N"ONIH"""
- - and here I decrypt it to recover ¬
	the original message
put encode (res, key)
-- "Since all of the encryption in this ¬
	engine is based on the xor handler, ¬
	the same applies to this handler as ¬
	applied to the xor method itself - ¬
	it works in both PREections."

The secret of good encryption is to use a long key string ñ the longer it is, the harder it will be for anyone to crack your encoding. The most secure messages of all use an encryption string longer than the message to be encrypted. That way there is no ërepetitioní in the encrypted string that could be used to reverse-engineer the encoding.

This method of encryption is far more powerful than the method we discussed last month. You can use it as the basis of some extremely secure communication systems. Use your imagination and you will be able to come up with some encryption programs that will be un-crackable to anyone except the most dedicated hacker ñ as long, that is, as you keep your key completely secret. Iíve used this technique myself in a number of projects. Most recently I used it to secure the high score messages sent from a Shockwave game back to the server as we needed to make absolutely sure that no-one could cheat the system. Iím sure that you will find this method just as useful in your own projects.

If you have any feedback, queries or ideas for future columns, send them to me at andyw@dircon.co.uk.