Introduction to Basic Cryptography: Simple Cryptography

#Introduction #Basic #Cryptography #Simple #Cryptography

Hi welcome to this lecture on simple cryptography in today’s lecture we’re going to look at some simple cryptographic ideas that you can do by hand in order to kind of get the basic ideas of doing encryption and at the same time we’re gonna look at some terminology that we use when we talk

About cryptography so hopefully all this will give you a foundation as we jump later into more modern cryptographic techniques so is kind of an introduction the word cryptography is Greek and when you break it down you have crypto which means secret and graphy which means writing so the word cryptography is

Greek for secret writing the basic goal in cryptography is to send messages but no one but the expected recipient can read but we can do a lot more with the cryptographic primitives that we come up with but that’s kind of our simple goal at this point send messages that no one

But the expected recipient can read so let’s look at some terminology that we use the word cryptography is a method to send secret messages using a code the word crypt analysis is where we try to break the code and read those messages so these two words are kind of paired

Together cryptography is where we’re creating in deciphering the messages legitimately crypt analysis is where we’re trying to break the code in order to read those messages some work some more terminology plaintext plaintext is a message in its original form before it’s been encrypted in any way ciphertext is a message in its coded

Form after we’ve encrypted in encryption is the process of transforming plaintext in to ciphertext decryption is the process of transforming cipher text into plaintext and an encryption algorithm or a cipher is the method used for encryption so as we talk about cryptographic techniques we’re gonna do some simple ones today but more complex

Ones later how do we know if a cryptographic technique is secure like how do we know if it’s good and then a crypt analysis someone who’s trying to break it isn’t going to be able to well we don’t actually have good hard fast provable ways to verify the

Cryptography is good instead we just get lots of really smart people to try and break it so we have lots of really smart people who perform crypt analysis on a given cryptographic technique and if none of them can break it after a long time we begin to assume it’s secure and

The longer a good are longer an algorithm has gone without someone analyzing it and demonstrating a break for it the more secure we tend to think it is now as I say this you should pause for a moment and say well that seems kind of I

Don’t know strange I mean what if we’re wrong well we might be wrong and this is usually what happens so if someone comes up with a good cryptographic technique we use it for a long time and no one knows how to break it so we assume that it’s good and then eventually progress

In mathematics or in other things begins to show that there might be some weaknesses in the design of that cryptographic technique and so after that we begin to move away from it and into something else but today let’s talk about some simple ciphers and originally cryptography is performed by hand of

Course today we do it all with computers because it requires some pretty high-powered mathematics but originally people did it by hand and the goal was just to simply protect messages that were sent by couriers or individuals because you didn’t really want the courrier to be able to read the message

And you didn’t want people who might intercept the courier to be able to read the message so might have just been handwritten messages but the goal was to make sure that no one who was transmitting them or saw them could read them except the expected recipient and

In war was obviously a popular time to use something like this generals might need to send messages between army camps and you don’t necessarily want the courier or an enemy army who intercepts the courier to be able to read the message one of the earliest documented

Ciphers was used by Caesar and for that reason we call it the Caesar cipher and his sucker was pretty simple each letter in a message was substituted by another letter that was three letters away so for example if I write out my message then I might go through and every a in

The message would become a D because I’m just substituting three letters every P might become an S etc etc so it’s a simple concept but when he at the time he was using it surprisingly people weren’t able to decipher it very easily let’s do an example just to make sure we

Understand it okay so up at the top here you’ll see I’ve written the the English alphabet and I’ve just numbered all the letters 0 to 25 and I’m just doing that because so that we can do some math if we want to but I’ve just written the

Letters number them 0 to 25 and let’s say that we have a message attacked it dawn that we want to encrypt with a Caesar cipher well we’re gonna shift every letter by 3 so we’re gonna start we’re gonna take the letter A in the message we’re gonna go up here and say a

So if I go three letters 1 2 3 then that becomes that D okay fair enough I’ll jump over here to T now with the letter T I’m gonna go again 3 letters 1 2 3 and fine W alright next letter in the message is also a T and it’s going to

Have the same cipher text letter so I’m going to also make that at W again we have a as the plaintext we’ve already done that one so we’ll get back D again now we have a new one C so C if we go ahead three one two three becomes F and

K if we go ahead three one two three becomes N and if we continue that through the message we can continue to to encode it now if we wanted to decode the message so if you were just given this line of cipher text here and you weren’t actually given the plaintext

Well then you would just go through each letter and subtract three so we would start with D and we go backwards 3 1 2 3 and get a double you would go backwards 3 to become T etc etc so encryption is you’re adding 3 to each letter decryption is you’re subtracting 3 from

Each letter so I kind of did it up here just by you know drawing little marks and adding 3 and counting 3 over but if you wanted to do it a little bit more mathematically you could just translate the letter into a number add 3 so if I want to do keh keh

10 add 3 to get 13 and that gets me in but you get the same purpose we get the same end result ok so another type of simple ciphers called a shift cipher which is really not that much different than a Caesar cipher in fact it’s a

Generic version of the Caesar cipher and in this case we’ll say each letter is shifted by N and so in the Caesar cipher n was 3 but we could we could shift by any number so we’ll do that instead so we’ll do another example again we bring

Up our chart so let’s do N equals 10 for the same message ok so if I have a tacit dawn well I’m gonna start with the letter A I’m gonna add 10 to it I’m gonna do it numerically this time so 0 plus 10 is 10 that gets me K

Okay so tee okay T is 19 that plus 10 is 29 well my chart doesn’t go all the way to 29 so maybe I’ll just wrap around so I would go 1 2 3 4 5 6 7 8 9 10 becomes D and the other T also becomes d that

Hey also becomes a K we’ve already done that one and C I’ll add on 10 so I start here and I go OK 2 2 plus 10 is 12 that would be an M K 10 plus 10 is 20 that would be a you and I can continue that

For the rest of the message so my my shift cipher here when I do N equals 10 I can just shift it that way and decryption would be similar to the Caesar cipher I would subtract 10 just as you would expect okay so with a shift

Cipher um how do you break this if you’re gonna form crypt analysis on something like this if someone just gave you a ciphertext it was shifted with a shift cipher and said figure out the plaintext could you do it sure why not let’s take the brute-force approach re4 smeeting the most

Inefficient but still workable way we can think of and the brute-force approach here is to try every possible value for n that shifting key well there’s actually only 26 possible values for friend because if you move beyond 26 you’re just wrapping around and it doesn’t matter so there’s

Only 26 possible keys so could you sit down and and in you know 10 or 15 minutes try all 26 possibilities for decrypting a message sure you could that would really wouldn’t be that big of a deal so that’s very feasible that you could do by hand and it’s trivial

With a computer I mean you could write a computer program to do that and it would be disturbingly simple and easy to handle so so so a shift cipher is really not that strong of a cipher it’s really simple to encrypt and decrypt with but the the number of possible values for n

Is so small that and someone could try all of them in order to figure out what you used it would be really easy for them to decrypt to analyze that so it’s easy to do but it’s not very strong well could we make it stronger sure so let’s

Try a different type of cipher called a substitution cipher now in a substitution cipher you generate a random set of substitutions for each letter so here’s the sample chart up here as you can see I’ve written the alphabet on the first row and then below it I’ve written all

The letters but in a different order so in this case I’m setting up a substitution cipher meaning in my for every a in my plain text on my ciphertext I get a q for every be in my plaintext I get an R etc etc and all 26

Letters of the alphabet are on the top row and all 26 on the bottom there’s no repetition so I always need a one-to-one correspondence a always becomes Q when I end crypt and Q always becomes a when I decrypt in my example here so let’s do

An example with this so if my message is attack it donnnnneee and this is my random decision on the substitutions well then performing the encryption is actually pretty simple so the the a okay well a becomes Q T becomes Y a becomes Q C becomes a K becomes V and

I can continue that for the rest of the message and decryption would be just as simple except I would go in Reverse instead of looking up in the top and reading the bottom I would look up in the bottom and read at the top so you

Know q becomes a Y search for Y here it is y becomes t a becomes C etc so decryption is fairly simple as well as long as you have this table that translates the possible substitutions okay so how could I to analyze a substitution cipher well in the

Brute-force possibility I would try all possible substitution combinations right you know so and that basically boils down to how many different ways can i order the 26 letter alphabet and there’s 26 factorial ways to do that 26 times 25 times 24 times 23 etcetera etcetera etc okay so there’s 26 factorial possible

Ways that I could build a substitution table how many is that I don’t really think well in factorials so I ran to Google which has a nice big number calculator and typed in 26 factorial and what we find is that is 4 times 10 to the 26 that’s a really big number are

You gonna be able to do that by hand no I’m not gonna like manually try every possible substitution table that’s absurd that’s way too many numbers in fact even doing that with a computer while doable to try them all he’s also not going to be very efficient so that’s

Really not that helpful for us so at first glance a substitution cipher seems pretty strong because there’s a lot of possible substitution tables and the chances of someone going through all of them by hand is really low and doing it with a computer is possible but still

Not all that exciting ok so so how do we to analyze this well let’s look at our ciphertext again I’ve taken away the plaintext just so you can just look at the ciphertext and I don’t want to make a key observation in a substitution cipher the basic language features are

Preserved so as an example you can tell how often the letter occurs in the message so as we look up at this message we can see that oh well queue happens a lot and why happens quite a bit and this letter Y is duplicated and it’s one

Right after another so the features the language are preserved you can tell that this letter whatever it would be in the plain text is repeated a lot you can tell that this has the same letter twice consecutively etc etc sooo in fact I can tell that this two letter word it has

The same two letters that this word starts with you know there’s just a lot of things I can tell just by looking at the ciphertext so even though it’s not trivial for me to come up with a substitution table that was used to encrypt this I staring at it there are

Still things I can tell about it about the original message so in order to break a substitution cipher we typically use a technique called frequency analysis and as well as the language features I just described so what’s frequency analysis well it’s a crypt analysis technique described in

The 9th century by al Kindi in Iraq he was an Arab philosopher and his observation was that not all letters in a language occur with the same frequency and in addition to that we also make use of the language features that I just described and so as an example in

English is the most common letter if you analyze large chunks of English English text he is the most common letter vowels are about 40% of all letters and in English vowels tend to be separated by consonants so there tends to be a pattern with that and we have other

Interesting features too like the letter Q tends to be followed by U at cetera et cetera so there’s a lot of different things that we could see here so actually performing frequency analysis and language features on substitution ciphers is a newspaper puzzle so back when I was in university I used to watch

Students in big lecture halls in front of me who would be solving this newspaper puzzle in class instead of paying attention to lecture but if you look at it you can see that basically the designer of the puzzle just built a substitution table and picked a message

And and encoded it and they just put it in the newspaper and you’re supposed to decipher it but you use the language features to do that and people who are good at this can can solve something like this in five or ten minutes you know without really it’s

Spending too much serious mental thought on it so even though a for at first glance the substitution cipher had so many possible substitution tables that it seemed unrealistic to break it by hand by analyzing it a little bit more it becomes it becomes simple to the

Point that it’s a puzzle that you put in the newspaper so that causes us a problem because that means that a substitution cipher is also not really very good cryptography so we need to find a way to do something even stronger so another cipher that’s I’ll call it a

Strengthened version of a substitution cipher it’s called a visionnaire cipher and it’s a type of polyalphabetic cipher and polyalphabetic means that one plaintext letter can become different ciphertext letters depending where on where it is in the message and in order to do this we use a text-based key and

Some modulo arithmetic to perform the encryption frequency analysis is possible on a visionnaire cipher but it’s much much more difficult and it’s yeah it’s just it’s a lot harder you’re not gonna do this in a newspaper puzzle so let’s do an example so I I have the

Same chart that I’ve been putting up before but this time I’ve modified it just a little bit I’ve kind of doubled it you know just because we’re gonna do modulo arithmetic with some wraparound so I have the letters A to Z written in numbered 0 to 25 and then I have them

Written again and number 26 to 51 that way if we’re adding up two numbers and it wraps around it’s still easy to figure out which letter it is it’s it’s just there to simplify them doing the math on on a slide so for a visionnaire

Cipher you need a text key in this case I’m gonna pick the key monkey I like monkeys so I’ll use that as my key we’re gonna take our message attack it on and we’re gonna write our key underneath it and we’re gonna duplicate the key you

Know every time we run out of letters so I’ll just write monkey monkey and just keep repeating the key underneath your original message and then all you have to do is add up the letters so a + M a 0 M is 12 is 12 so that gets me

As my ciphertex letter T + o T is 19 oh is 14 so 19 plus 14 is 33 that gets me age as my ciphertext letter T plus n T is 19 n is 13 that gets me 32 so G is my ciphertext

Letter right here a plus K so a 0 K is 10 that gets me K as my ciphertext letter C plus he 2 plus 4 is 6 that gets me G is my ciphertext letter K + y 10 plus 24 gets from 34 which is I for my

Ciphertext letter etc etc so I could continue that process but I’m just adding my plaintext message with my key as I go through and this removes a lot of frequency analysis technique any techniques and even language features because as you look at this okay in the original plaintext the letter T was

Duplicated but in my final ciphertext the letters aren’t the same in addition in this ciphertext we see that G is used here and here but in my original message those are two different letters so we don’t have the same language features or even frequency analysis that you can

Perform now the one flaw in the Visionaire cipher is that when the key repeats well that letter will always be though then you could perform frequency analysis on repeated points so for example when Mikey starts I have a + m gets me m when Mikey repeats if my

Plaintext letter is a a plus m equals M so in this case this and this are the same and they could be analyzed that way that’s actually the way the divisionary cipher is analyzed is you analyze the ciphertext in order to try and determine what the length of the key is and then

You perform frequency analysis of letters at the same spot in the key all the way through but it’s a significantly more difficult thing to do so visionnaire cipher is much better than a substitution cipher for cryptography now would we now would we really want to use this for secret messages today no

Because you could you could run a computer program to that crypt analysis without any trouble but the concept of a Visionnaire cipher leads us to a type of cryptography that you could use today and that is provably good in fact this is the only provably secret form of cryptography it’s it’s

Security is not based on with the fact that other people don’t know how to break it we can provably show that it’s unbreakable and that’s called a one-time pad and a one-time pad is a Visionnaire cipher with a randomly chosen key that’s just as long as the message the key

Needs to be shared between the two parties the two people in the communication beforehand and that’s kind of the problem with the one-time pad that’s actually fairly difficult thing to do and the key can never be reused and like I mentioned before a one-time pad is totally unbreakable without the

Key this is the only perfect cryptography okay so let’s do an example here’s my charts again my random key is just this it’s just random it was randomly chosen and if that random key is shared between the sender and the recipient then I can do attack

At dawn I could write my random key underneath it and it’s just as long as the message it never repeats and that’s the important thing here it’s totally random and it never repeats because it doesn’t get repeated along the message and it’s just as long as the key

There’s no way to perform frequency analysis because there’s no repetition in the key and that’s what makes this unbreakable and so if I were to do the actual encryption you know going through and adding it all up I would see I would have a ciphertext but there’s no way to

Know what the original text was and the reason for that is like I said the key is totally random and just as long as the message now the difficulty here is that creating random keys that are shared between two parties that are just as long as the message is very difficult

To do in a lot of scenarios so I want to make a quick note here about all the ciphers we just looked at and all these previous techniques have two basic components and I hope you saw them as we went through the first is an algorithm

Which is something that you do to the message so in the case of a shift cipher my algorithm is well I take the letter and I number two it and then I turned it into the net to that letter the other component all these techniques have is a

Key the key is a secret that I need in order to encrypt or decrypt properly so in the case of a shift cipher the key was the the number that I shifted by in the case of a substitution cipher my algorithm was to substitute letters in

My key was the substitution table that I used in a visionnaire cipher my key was the secret word that I used and my algorithm was to repeat the key underneath my message and just add the message in the key together so when using these algorithms the key is the

Secret I mean obviously the key if if an attacker someone who is trying to read your message knew the key then they could read it without any trouble but my algorithm isn’t a secret the way a substitution cipher works is not a secret but the key I use to encrypt a

Message with it is my secret so I just wanted to emphasize that point all right so let’s summarize what we’ve talked about cryptography is a type of mathematics dedicated to secret codes we trust a cryptographic algorithm if lots of smart people can’t break it and while that may sound a little bit

I don’t know shaky in practice it seems to work pretty well but it is an important concept to understand is that other than the one-time pad we talked about today no cryptographic algorithm is is a hundred percent secure there only the security is only based on the

Fact that we don’t know how to break it we looked at four types of simple ciphers a shift cipher a substitution cipher a visionnaire cipher and a one-time pad and each of these ciphers have an algorithm that’s not a secret and the key that is a secret