TFM:Basic Cryptography

From ProgSoc Wiki

Jump to: navigation, search

An introduction to cryptography

James Ducker

Encryption is actually not too hard to understand. The algorithms utilised today by monstrously powerful computers may be very complicated, but the principles of cryptography remain simple.

Given some text you want to encrypt, you can transpose letters (i.e. re-arrange them), diffuse letters (i.e. put fake letters in between the real ones), and substitute letters for other letters.

So long as you have some means of remembering how you created the encrypted text (or ciphertext), you can use that information to reverse the process and arrive at the original text (or cleartext). The specific information needed to decrypt your ciphertext is known as the key, and the process (or algorithm) you use to create the ciphertext is known as the cipher, which is why you decipher things.

Another way of thinking of it is that the cipher is like the lock in your front door, and the key is like, well, the key to that lock. Many different keys will fit in the lock, but only the correct key will allow the barrel to turn and the door to be opened.

Doing it for real

As a simple example, let's say I want to encrypt the words "Hello World". This means that "Hello World" is now our cleartext - the thing we are going to encrypt.

Before we begin: to make our lives easier, we're going to discard the space and just work with "HelloWorld".

First, let's start at the beginning of the text, and get every second letter:

HelloWorld
 ^ ^ ^ ^ ^
 e l W r d

So looking at every second letter we end up with e,l, W, r, d. Let's put them up front:

elWrdHlool
^^^^^

Woah.

Okay, now we will introduce diffusion. After every letter we are going to add two random junk letters, so 'e' might become 'eHk' and 'W' might become 'WvQ':

e  l  W  r  d  H  l  o  o  l
ch Da ep eq tH sT we fu UD EP

And we put all that together to get:

echlDaWepreqdtHHsTlweofuoUDlEP

That looks nothing like the original text!

Let's take it one step further and introduce some substitution. This is probably what you used to make coded messages to pass to friends as a kid (if you did that). A simple substitution would be to replace every letter with the next letter of the alphabet, or if the letter is a z, to replace it with an a. So a becomes b, j becomes k, M becomes N, and so on, so that:

echlDaWepreqdtHHsTlweofuuoUDlEP

becomes

fdimEbXfqsfreuIItUmxfpgvvpVEmFQ

What we've got now is a pretty nice little cipher. Someone with experience cracking ciphers should be able to figure it out eventually, but the average person would have no hope!

Challenge mode: apply the steps in reverse to turn the ciphertext back into the plaintext. So you would start with the cipertext, and:

  1. Un-substitute: Swap every letter for the letter before it in the alphabet (K becomes J, a becomes z, V becomes U, etc)
  2. Un-diffuse: Split it into groups of three letters, and discard the second and third letter in each group ('Jfq' becomes 'J', 'gtl' becomes 'g')
  3. Un-transpose: This one is a little trickier, because you have to work out where the transposed letters stop. Well, we know that every second letter in the cleartext was moved to the front of the, so we can take the number of letters and divide it by 2 to get the number of letters that were moved to the front of the ciphertext. So at this point we should have 10 letters, and we divide that by 2 and get 5. Now you know that the first 5 letters are the ones that were moved to the front of the text. Using this, we can pick them one by one and put them between the remaining letters.

Here's a demo:

elWrd Hlool
12345|12345

So we take '1' from the left side, and put it just after '1' on the right side,

lWrdHelool

Then do the same for '2',

WrdHellool

3, then 4:

dHelloWorl

and finally, 5:

HelloWorld

And we've now once again revealed our original message (our cleartext)!

Now, the real challenge: how do you safely tell your confidantes the key to deciphering your encrypted messages?

(I used this online password generator to make some random letters for me to use, because apparently I am too lazy to mash the keyboard.)

Personal tools