Introduction to Cryptography
First off, get yourself a drink and buckle yourself in! This is a long page!
Do I know my salt? I guess so, I’ve worked with PKI for a number of years. I’m no mathematician but I understand how it works. You’re going to get an introduction of how I see it, this is both from an academic and real word point of view, real world because I did this for a living and academic perspective because of my MSc.
Cryptography has been around for as long as people wanted to hide information.
The word itself is made from the Greek work “Kryptos” which means hidden, so its really an ‘ography on hiding things.
There are examples in history where messengers would shave their heads, have a message scribed on to it (with ink one would have hoped), wait for the hair to grow back and then travel to the destination where once the head was shaved again, the message would be read. Crude but effective and as long as you have time on your hands not a problem either.
This method would still work today, but securing messages has become more sophisticated and time critical.
The general idea I’m putting across is a process to hide a message, and a process to unhide the message.
There are terms that I will use that I’ll explain below.
*Plaintext – normal text
*Cipher – A set of rules that turn Plaintext into goggledygoup
*Ciphertext – the goggledygoup
*Key – the secret used to affect how the Cipher treats the Plaintext *Encrypt(ion) – the process to turn Plaintext into Ciphertext
*Decrypt(ion) – the process to turn Ciphertext into Plaintext
The image above represents what happens during encryption. First you have the Plaintext, this is then put through a process called a cipher which is affected by a key, turning the Plaintext into Ciphertext.
To our man with his hair, think about the person who wants to send the message. The writing on the messengers head – is the Plaintext.
The cipher is to let the messengers hair grow
The Key is how quickly the messengers hair grows back and once his hair has grown, the Plaintext has effectively been hidden, or turned into Ciphertext. This is encryption…
To decrypt it, the cipher is to shave the head, and the key was more than likely a very sharp razor. This is decryption…
New meaning to don’t kill the messenger eh 🙂
CAESAR CIPHER
An example that is a little more relevant, is the Caesar Cipher. Created by Julius wanting to send his commanders information and receive it from them, he decided to jumble up the letters in the messages.
It works by first working out where in the alphabet the letter was and then changing it to another that was in a different position but a predefined number of letters away.
a b c d e f g h i j k l .m .n ..o .p .q .r .s .t .u .v .w .x .y .z
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26
Each of the letters now has a number.
So if the message ‘me’ was ‘encrypted’ using a ‘key’ of ‘1’ would give us:-
m=13, 13+1=14, 14=n
e=5, .5+1=6, ..6=f
The message would be turned into ‘nf’ which has encrypted ‘me’
The Caesar cipher is called a “symmetric’ because it only has one key, the key in my example is ‘1’ because we moved ‘1’ position.
The key to encrypt is the same key used to decrypt.
Caesar used 3, again using the picture above – we have the Plaintext ‘me’, we have the key=3, we use the cipher to move the Plaintext 3 positions to get our Ciphertext. This time it’s ‘ph’.
To get the same text back, the process is reversed, the Ciphertext is reversed positions the same number as the key, bringing back the Plaintext. This is decryption.
This generic process is known as ‘Symmetric Encryption’. One key for both encryption and decryption… – remember this point!
Using the Caesar Cipher isn’t that difficult to crack (by hand or just by thinking about it or counting with your fingers), all you need to do is search for patterns and make guesses.
For instance “the” is a very common word. Which would be “wkh”, seeing several of these would give the game away fairly easily.
So as we have got smarter, so has encryption. Google the Playfair and vigenere ciphers to see how it improved over the last few centuries. Problem is computers are a tad quick so cryptography had to keep up.
You may have heard of DES or 3DES which are symmetric ciphers, DES = Data Encryption Standard.
IBM called it Lucifer, and the US Government called it FIPS 46-3 (Federal Information Processing Standards). This is a standard which has been in use for pretty much my lifetime for encryption using a single shared key.
The problem with all single key systems is transporting that key and trying to ensure that the key hasn’t fallen into the wrong hands. Ok, send it by post… trust that? Send it by Courier – either private company or government agent, or military means… It costs and it takes time.
Publically in 1976, it all changed.
ASYMMETRIC or Public Key Encryption (PKE) In the “IEEE Transactions on Information Theory” edition in November 1976, a paper called “New Directions in Cryptography” was published. This was a paper written by Whit Diffie and Martin Hellman with influences from Ralph Merkle.
The synopsis of the paper was that two parties can communicate securely without having to share a common secret. So how?
This is where it gets complicated, so instead of sharing a key. Each party has Two Keys..
This can get very mathematical, I may explain this further in a link from this page in the future, but for the time being just get used to the fact that you can have what’s known as a ‘Public’ and ‘Private’ key to make a pair.
The way the maths work – is you can encrypt using the Public Key, and then using the Private key you can decrypt. (Read this till it sinks in)
The beauty of this is that you can then give out your public key to anyone at all. But the privacy is based on the fact that the private key stays private to you and no one else.
• Send A your Public Key
• Get A to Encrypt the Plaintext using your Public Key to create the Ciphertext
• Get A to send the Ciphertext to you
• You Decrypt the Ciphertext using your Private Key to retrieve the Plaintext
Its like giving out an open padlock, and keeping the key.
• Send your padlock to A.
• A puts a message into a box, and then locks the box by using your padlock.
• The box is then transferred by whatever means, because only you have the key to open it.
• When you get the box, you use your key to unlock the padlock and open the box to read the message.
If A sent you his open padlock, you can then send a message back by performing the same process.
Putting your open padlock in the box along with the message before locking it allows A to continue the cycle. Right, if your head is aching – I suggest you go and get another drink. This page should still be here when you are ready.
This gives the principals of Modern Day Cryptography. They (Diffie & Hellman) had the right idea but hit a wall whilst trying to implement it. It got to the point where they published the paper in Nov 1976 hoping for someone to fill in the blanks.
In just under a year, 3 students – Ronald Rivest, Adi Shamir, and Leonard Adleman after trying some 40 different ways to make it work. The first sniff at what was to come was published in August 1977, and the public release in Feb. 1978.
RSA is the first letter of the surnames of each of the 3 students that created the algorithm. in 1977. (I was two years old, I’m now guessing you weren’t even born ;-)..)
The RSA team, offered copies of its work to anyone that requested it, apparently the NSA asked them “not to” but as there was no legal basis, they didn’t stop. They weren’t the first though.
The British ‘Code Breakers’ or GCHQ (Government Communications HQ) in 1972 first had the idea. James Ellis, in a paper described “non-secret encryption”. One year later, Clifford Cocks came up with an algorithm, essentially the same as “RSA” and then the year after that Malcolm Williamson came up with the similar idea as Diffie and Hellman. Because of the nature of GCHQ none of this was ever made public until just before Christmas in 1997.
Typically british being arse about face, but the 3 from GCHQ finally got the recognition they deserved.
I had the chance to speak to Adi Shamir, when he gave a lecture on PhotoCryptograhy (kind of a quantum’esque demo) at my University. A brilliant guy with a dry sense of humour. He explained his methods very well and to meet someone who has made such an impact to this science (which effectively created my job). I say – Top Man!
I can’t remember what I asked him.. it was more than likely stupid.
Whit Diffie was also there – long blonde hair and a big cowboy hat, I remember shaking his hand, but taking more interest in the stunning assistant that was with him. Lucky sod.
KEY SIZE
I’m going to bring in a new term called bits (I’m kind of hoping you know this already), these are the 1’s and 0’s that your computer talks in. A ‘byte’ is 8 such bits. The way these numbers are displayed and used is known as binary.
Another way to explain a byte, is a letter, each key on your keyboard is mapped to an ASCII number, these are 7 or 8 bits long. A carriage return on your keyboard is 13 (In ASCII) or ‘00001101’ this is what is processed by your computer when you press it. This is just bytes 🙂
00000000 = 0
00000001 = 1
00000010 = 2
00000011 = 3
00000100 = 4
00000101 = 5
00000110 = 6
00000111 = 7
00001000 = 8
00001001 = 9
00001010 = 10
00001011 = 11
00001100 = 12
00001101 = 13
00001110 = 14
00001111 = 15
00010000 = 16
00100000 = 32
01000000 = 64
10000000 = 128
Or look at it this way..
128 064 032 016 008 004 002 001
.0…0…0…0…1…1…0…1
This is (0*128) + (0*64) + (0*32) + (0*16) + (1*8) + (1*4) + (0*2) + (1*1) = 13
If the binary digit is 1 then the digit is true, if it’s 0 then it’s false.
So a number eight can be represented by 4 bits; 16 by 5; 32 by 6 etc..
looking at this may help you to understand why RAM has gone up this way, first you had computers with 1Mb Ram, (OK, a Sinclair ZX81 with 1Kb “and a 16k Ram Pack”) and ever since the engineers managed to add another bit on the end, it’s evolved now to 512Mb, and we sit waiting for 1Gb sticks of RAM (In 2000 when I wrote this).
Anyway, we digress, so we can see that by only using 8 bits, we can have 256 combinations where all the bits are 1, this would be like saying 128+64+32+16+8+4+2+1+0 = 255 the 256th is all zeros or all one’s depending on how you look at it..
So if my key was only 8 bits long, an attacker would only have to change the key 255 times before guessing mine, and then chances are it would be somewhere in the middle.
How long would you think your computer would take to crack that? Try milliseconds if not microseconds.
The key sizes that are now considered ‘weak’ are 512 bits long (in 2000) and every time that you add an extra bit you double the amount of combinations.
So 8 bits has 2^8 which is 2 to the power of 8
or – 2x2x2x2x2x2x2x2 which is 256 combinations, not 256 bits.
times that by 2, or add another bit gives 512 combinations – get the idea?
A Million is 2^20 = 1048576
Now the weak key size 2^512
So – RSA. There are two uses for RSA, one is the process for generating keys and the other is the encryption/decryption process. I’ll concentrate on the first one here.
RSA KEY GENERATION (PKCS #1)
We’ve talked about the basics, and covered the key size, here I’ll try to bring them together.
The algorithm gets complicated but all you need to know is that by a maths process where you create these numbers. P, Q, N, D and E
Those wanting to know how it works, have a look [HERE]. You’ll need to be fairly good at maths to follow the terminology. Like the ‘Extended Euclid’s Algorithm’. You have to be comfortable with the idea of Modulus Maths and Prime numbers and numbers that are relatively prime.
Your Clock is Modulus 12 once the hand passes 12, to goes back to 1. This is MOD 12
P and Q are multiplied to Make N (N is the Modulus) N = (p * q)
E is a number less than N but relatively prime or (p-1) * (q-1)
D is a number that is the inverse modulus or E * D mod (p – 1) * (q – 1) = 1.
Your Public Key are the numbers E and N, and your Private key is D and N. P and Q are then destroyed at the time on creating the key as they are not needed. Or think of it, if P and Q were not destroyed, the security could be compromised – (Was this a play on “mind your P’s and Q’s”…?).
The strength of the RSA keys is based on the fact that if I make the numbers large enough, to calculate D from the E and N would take ages, and I mean ages. This is because I would need to find out what P an Q are in order for me to find out. This is what Factorisation is called.
A key of 512 bits took a shed load of computers about 8 months to guess or factorise back in 2000. Remember when I add another bit to the key it doubles it’s guesses.. Forward to now, we’re on 4096 keys on Root Certs to give protection of about 30 years. When Quantum computing really hits the road, most cryptosystems will be replaced with Quantum Crypto Ciphers – yeah I’ve sat in lectures on this and thought “oh, that’s nice”.
Because of this strength, you can quite happily post your public key to everyone in the world or show it on a banner on CNN 24×7 with confidence.
But this means that you should have a large key, and the private key is kept secret, if it’s compromised – it’s game over.
Wondering what an RSA Public Key looks like?
This is the public key from a certificate installed on Windows 2K: (yes there were computers back then)
3081 8902 8181 00E0 4E10 0EB8 A7EF 21CA 605A
DC9F 1E3E 8377 5A29 2EF9 4EE5 085D DEE1 CF09
C01F 44B7 07A8 4BA4 2230 3B19 0683 EEF3 AC27
78AE CAD6 402B CE79 01E1 9D56 8B36 72B1 6390
5FA0 B2C0 66A6 49C5 3CFA 26A2 62C3 D3B5 CC61
154C F23F B4E7 4508 4389 7F6A 8DD5 66FB D7FF
6400 C411 FD2C A30B 75B0 FBE5 AC26 65A3 81E6
6649 3D1D 737A 9B71 D702 0301 0001
The key is a little shorter, but to let your computer read this, the first and last few characters are ASN.1 (a language that explains the structure to your computer) See the Digital Certificate Page for a detailed explanation where I break this down even further… (I can almost hear you saying ‘yay’).
RSA KEY ENCRYPTION
So now we understand how encryption works, and what a key pair are. We’ll look at how they are used.
Say someone watched CNN and copied my Public Key into their computer and wanted to send me an email.
They would type the email, and then use my public key to encrypt the message to get the encrypted text. The email would still have the normal things like my email address and the senders details, but the main body of the email would be encrypted and secured.
This would then make its way over a very insecure channel (internet) winging its way to me. When I download and open this mail, I then use my Private key to decrypt the mail and hey presto, I see the original message that was written ‘for my eyes only’.
RSA KEY SIGNING
If you aren’t confused yet, I’ll finish you off with this next one.
We now understand how your Keys work for encryption/decryption. But they can be used in reverse to digitally sign a piece of information.
Before I explain this badly, basically its no different from me encrypting a bit of information (but with my private key) and sending it to you with my public key attached. You would wonder who it was from, but by decrypting the bit of information it can show it was from me.
The way of calculating this ‘information’ is normally created by ‘hashing’ the message, this is like saying, I’ll take every 4th character from a message (including spaces) and encrypt this to create my signature.
My Message Hello, how are you – are you bored yet.
The Hash lhay-eury
The signing I would then encrypt the hash using my Private Key and send this to you along with my Public Key.
So now the email would contain:
Message Headers (who to, who from, etc…)
My Public Key The Encrypted Hash of the message (signature)
The message itself.
You would need to use the same rules that I used to create the hash and you would create your own copy of the hash. If you don’t the whole thing doesn’t work and we have perfect encryption. (Hidden from everyone)
Then you would decrypt the ‘signature’ from the email using my Public key and this should give you the same hash that you calculated. If one bit is changed in the message, then the two hashes are not the same and you know you can’t trust the email.
All we have talked about is key pairs and cryptography, but how do you know that the Public key that I say is Mine, is actually mine?
Check out the Digital Certificates page for that.
One gold star for reading this page!
Feel free to send me comments on this page, I would like to know if you found it useful or confusing – this is a bit of a concept to understand.