Wednesday, 30 January 2019

Basic Cryptography

Well, I have now finished my second semester of computer science so I guess it is time to start writing some posts on the subjects that I did so as to assist me in studying for my exams. Well, the first post will basically be an introduction to computer security, otherwise known as cryptography. This is probably one of the foundations of our modern age because, honestly, without cryptography we probably wouldn't be able to use our smart phones to check our share portfolios, or be able to withdrawal money from ATMs (or whatever you call them where ever you happen to be, but if you don't know what an ATM is, it stands for Automatic Teller Machine, but basically it is one of those machines that you use to withdrawal cash from your bank account).

I probably would also make a comment about being able to share personal information with your friends by using Facebook, but honestly, that company really seems to be having some serious issues with their security, so I guess that would be a pretty bad example.

Anyway, cryptography has been around for a very, very long time. In fact it has been around long before Charles Babbage thought up the idea of an automated calculating machine, and Ada Lovelace came up with a way of programming this hypothetical machine. I would say that it goes back as far as Julius Caesar, but honestly, it goes back even longer than that. The thing is that as long as people have been waging war against each other, people have been devising ways of sending messages in a way that if they were intercepted, they wouldn't be able to read the message.

One of the most famous codes was the German Enigma code, which was used to pass information to the troops during World War II, and was famously cracked by Alan Turing, who has earned the title of being the father of computer science. The story of how Turing cracked the code was told in that rather well known movie called the Imitation Game. Since our lecturer showed us a clip from the movie in the first lecture, I probably should do the same here.


Caesar Cypher


Anyway, enough of movie trailers and let us get on to some cryptography. Basically, we we start with a cypher that you probably heard about, or even played around with, when you were a kid. Basically it is the Caeser Cypher (and is the reason that is name popped up above). I remember when I was a kid our school library had some spy books in there. No spy books in the sense of a Tom Clancy novel, but rather books on how to be a spy, and some tricks that spies use - sort of. One of them was writing coded messages, and one of the ways was through the use of what is known as the Caesar Cypher.

Basically, the Caesar Cypher is where you take the letters of the alphabet, and shift the letters a certain numbers of spaces to the right (or the left). The traditional way was to shift it three spaces right, but that is too obvious, so you can pretty much do it as many times as you like. Below is an example:

The above table is an example of how the cypher works. So, where the letter A appears in the message, you replace it with a D. Where a B appears it is replaced with an E and so on and so forth. So, the following message:

I am a piglet

Will come out as follows:

L dp d sljohw

The problem with this cypher is that it is pretty easy to crack. In fact, I wrote a computer program that is able to crack it pretty easily. In reality, you only have 25 different combinations that you can try, and by moving through each of them you can pretty easily crack the code. In fact, the longest part of cracking the code was actually writing the program to do it, and once the program has been written and executed, it literally takes seconds to decrypt the text.

I probably should mention that cypher texts also have keys, and not surprisingly the key is what is used to decrypt, or unlock, the code. With the Caesar Cypher, the key is the number of spaces that you shift to generate the code.

Frequency Analysis

Now, as mentioned, there are only 26 (or rather 25) possible permutations with regards to the Caesar Cypher. However, what if there isn't any particular order in which the letters are arranged, such as below:

Well, that happens to be a little bit more complicated, particularly since there is somewhere in the vicinity of 288 different combinations. For those who can't do that sum in their head, that is basically 3.1×10²⁶ different combinations that you could have. Basically that is an awful lot of combinations, and to try every single one of them will take you a very, very long time, even with a computer. In fact, if a computer were to try one combination a second, it would take 9.8×10¹⁸ years to try all of those combinations. Honestly, I don't think anybody is going to be living that long.

So, do we have the perfect uncrackable code? Well, no, not quite. Guess what, I wrote a program to crack that one as well, though it is a little more involved than our Caesar Cypher. You see, the problem comes down to our language. Basically there is something known as frequency analysis. Each of the letters in our alphabet have a certain frequency in which they appear. For instance, the most common letter happens to be E, followed by T then A then O then N. This chart should help:

So, the way we crack one of these codes is by counting the number of times each of the letters appear in a passage. We then compare those letters with the chart above. Then we find the most common letters and switch them with the letters above. After about five switches we start to make out words and once we are able to make out words (the is a classic example) we are then able to knock more letters off until we have basically cracked the code.

Double Transposition

Another form of code is what is known as a double transposition cypher. What is happening here is that the letters aren't actually being changed, as is the case with the above two cyphers, but rather the position of the letters are being shifted around. So, for instance, we have the phrase 'Attack at Dawn'. The transposition cypher will then produce the phrase ' taw natt adakc'. Now, what they have done here is create a matrix, placed phrase in the matrix, and then shifted the rows and the columns. The image from the lecture notes do well to demonstrate that:

So, as you can see from above, the key is a 3x4 matrix, that is three columns and four rows. Now, we also have the permutation, namely that rows 1 and 3 have been swapped, and rows 2 and 5 have been swapped. Also, columns 2 and 3have also been swapped. Mind you, with a matrix this small, it is pretty easy to crack, but when you have larger matricies, then it becomes much, much more difficult.

Code Books

The final one we will talk about here are code books. This is where you have a book that lists a series of words and a code next to that word. Normally the code that is used are a series of numbers. The most famous one of these happens to be a telegram known as the Zimmerman telegram. This was a telegram that was sent, in code, to the Empire of Mexico by Germany during World War I. The telegram basically said that if Mexico joined the war on the side of the Germans, then when the Germans won the war they would receive portions of the United States as a reward. Not surprisingly, the telegram was intercepted, and it happened that the US also had a copy of the code book. Well, they deciphered the code, read the telegram, and not surprisingly declared war on Germany shortly after.

Anyway, here is an image of the Zimmerman Telegram:

And since we mentioned it above, here is a picture of the Enigma Machine.


In my next post, we will continue looking at cryptography, and some rather basic techniques that are used today.



Creative Commons License

Basic Cryptography by david.sarkies@internode.on.ent is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License. This license only applies to the text and any image that is within the public domain. Any images or videos that are the subject of copyright are not covered by this license. Use of these images are for illustrative purposes only are are not intended to assert ownership. If you wish to use this work commercially please feel free to contact me

No comments:

Post a Comment