welcome to the second of my series of lectures this academic year and thank you for coming along this year I’m taking as my theme some examples of using mathematics in in different areas and today’s lecture is about cryptography the science of transforming information so that can’t be read or understood and I’m going to look at how this subject has developed most surprisingly because it’s the subject that has secrecy at its heart and yet it is no exposing its techniques its algorithms its methods the public scrutiny and the public analysis but what is certain is that for centuries massive intellectual effort has gone into methods of securing secure account secure communication and secure storage of data because of its importance as you all know and diplomatic commercial military and economic affairs and we do know what the consequences of secure communication being broken can be quite considerable in both economic and impersonal consequences so let me start by giving you an overview of the lecture pause on that skip and there we are so I’ll introduce initially some of the key terms and the guidelines and as with every subject cryptography has its own language its own notation its own concepts and core ideas and I’m going to focus particularly upon the idea of a cipher system and that’s what’s going to run through the lecture that’s going to be the core notion and Ted suceeded ideas of encryption and decryption keys and what I want to do is to talk about some of the standard assumptions that are made about cipher systems and about the different ways that you can attack them and the other distinction I want to draw it is the important and increasingly important one between conventional cipher systems and the new public relatively new public key approach and talk about the seminal paper that introduced up the first particular example of a cipher I’m going to look at as a very straightforward easy one of no practical use whatsoever the Caesar cipher but what it does do is to illustrate some of the ideas I want to bring I to bite keys key concepts and concepts about keys and the potential weaknesses that there are in cipher systems then I’ll go on to a class of ciphers called substitution ciphers and this has these ciphers of a large number of keys an astronomical number of keys something like 4 times 10 to the 27 but it’s extremely vulnerable and it’s vulnerable due to the statistics and the structure of the English language and I’m going to be using it as an example of the fact that a large number of keys doesn’t just doesn’t mean for if you have a large number of keys it doesn’t follow that you have a secure system in order to try to avoid and the consequences that English has got a language and the statistics associated with it we’re going to look at the next approach of poly alpha alphabetic ciphers which are introduced to try to hide the statistics and the frequency analysis approach then I look because it’s such an exciting story at the one implementation of the enigma machine which is an electromechanical rotor machine and very important before and after the war and about which cheering on Bletchley Park did a lot of work but what I’m going to do is to look at another story that isn’t as well-known as how the Polish cryptographers broke the Enigma machine in the 1930s but in my large picture what I want to show from that story is that they didn’t actually break enigma they broke the way enigma was used it was very heavily dependent upon the way that enigma was used to set up the keys for any particular day then going on to modern ciphers which are all electronically based and they hinge around binary representation and the way that information is represented in a computer and there are two main subtypes cipher systems and block ciphers and the cipher systems are very good for things like digitizing speech although it doesn’t seem to have stopped the Americans listening into French conversations and what they do is they act bit by bit on the message therefore you do not have any error propagation if there’s a mistake and transmission or whatever so that’s why cipher systems are particularly useful there and the other type are more used for when you’re

trying to hold data securely or to make sure the data is authentic and hasn’t been interfered with and they are block ciphers and they can be made to depend very much upon what went earlier on in the message then I’ll come to the seminal paper the paper by and Whitman Diffie and Martin Hellman and that really is the beginning of modern public key cryptography but again we’ll be able to see from my diagram of the cipher system which is coming up in a moment the very simple basic idea that they used to kick off this whole idea of making more and more more of a cipher system public right and it’s all based upon the idea that mathematics we believe it is believed that there are certain one-way functions trapdoor functions mathematical functions that are easy to calculate one way but if you knew the answer it’s very hard to go back to the input right and at the finish I’ll just show quickly our the idea of public key cryptography can be used to provide digital signatures which are the digital analog of the ordinary written signature and in fact can also provide again security that the message has not been interfered with and changed so here’s my core underlying idea the notion of a cipher system and two people usually called Alice and Bob Alice on the left and Bob on the right wish to communicate securely so Alice wants to send a message usually called the plaintext which will be converted into ciphertext are a cryptogram and she wishes to Sara sent that to Bob in order to do it she uses two things she uses an encryption algorithm something that she does and that encryption algorithm makes use of an encryption key that converts the message into another form which is converted which is transmitted to the receiver and of course it could be intercepted on the way and you usually call the person who does the interception Eve because Eve is an eavesdropper the GUI doesn’t it and on the other side what you have is a decryption algorithm an algorithm is just a process of what to do your recipe of what to do and that takes as part of its input takes as input the cryptogram and the decryption key cryptography technically is the science of designing cipher systems and crypt analysis is the science of finding information about the plaintext without any knowledge of the decryption key and cryptology is the term for both of them now the keys are crucially important for the security of a cipher system and modern approach very much changes in the cipher system a cipher system security really resting on the significance of the keys well we can infer one thing from this particular diagram and this is of the basis of the diffie-hellman approach which is that in order to obtain the plaintext all you really need to know is the decryption key you don’t need to know the encryption key and in public key cryptography the only part of this diagram that a secret is the decryption key in public key cryptography everybody knows the encryption key everybody knows the encryption algorithm everybody knows the decryption algorithm the only thing that isn’t known as decryption is quite quite surprising notion well because of that cipher systems are usually divided into two types there’s the conventional ones which are also called symmetric ciphers and that’s one where it’s easy to deduce the decryption key from the encryption key and for many of these symmetric cipher systems the two keys are in fact the same and the systems are known as secret key or one key systems in an asymmetric or more popularly known as a public key system it’s practically impossible it’s believed to be practically impossible to deduce the decryption key from the encryption key and I’m not really talking sophisticated mathematics here the one that is used in the RSA public-key system that I’ll describe briefly at the end of described at the end of the lecture really just depends upon the fact that it’s easy to multiply two numbers together that’s an easy operation but it is very difficult to find the factors of a number to find those numbers of which a number is composed but that’s what the operation is I’ll also be introducing another mathematical operation which is the analog of finding logarithms again finding logarithms as you sure did it’s cool and probably still do in your spare

time there’s a relatively easy thing to do but there’s a case in which the discrete logarithm were you’re doing it in bunch of arithmetic where it actually turns out to be difficult and we’ll look at some examples of that but first of all let’s look at the security of a cipher system and bring out some of the assumptions within the subject well our diagram says that Alice and Bob must have a matching pair of keys but it may be very difficult to reach that situation you know if you want to see if you want to distribute keys they’ll have to meet up or they’ll have to have a secure channel of distribution and the management of keys the whole key life cycle which goes through key generation key distribution key usage key changing constructions are three vital to security of any cipher system and I don’t apologize for harking on about case you know if you write your PIN number and your bank card you’re just writing asking for trouble but in the eye a symmetric kiss there’s a different problem in the asymmetric kiss the encryption keys for everybody is public if I want to send a message to you I look up a directory of your public key I find your public key I go to the publicly known encryption algorithm I use your public key the encryption algorithm and the mime message I send a message to you you use your private key in order to decode it but the thing is how am I really to know who’s sending the message you know who does the public key actually belong to so this is a question of authentication and the danger of impersonation something that we’ll see and we can use certification authorities and digital signatures to try to evolve their to and resolve the problem of assessing the security of a cipher system is really exceptionally difficult well it’s it’s not an exact science at all and it is helpful not to ask for absolute security but to ask for it to be good enough in other words to be good enough for the purpose for which the cipher system is intended and helpful measure when you’re doing that is this notion of cover time which is how long you want the communication to remain secure and that will clearly depend upon the circumstances that you’re dealing with and how do you measure the cover time well again it’s a very coarse sort of way of doing it but a useful type of doing a way of doing it is to say well let’s attack the system by trying all of the possible decryption keys that there can be for it so that’s the kiss of a brute-force attack and we’ll look at some examples and in the substitution cipher of how long a brute-force attack would take by by trying all the keys but then there’s an alternative way using the structure of language that you can attack the system very easily but this at least is one way of trying to get some idea of a security of the cipher system and what you normally do is you normally have got three worst case conditions and the first one is that the Crypt analyst as a complete knowledge of the cypher system now that doesn’t mean that you have to make sure that the cypher system you have to make public the details of the cypher system you don’t have to do that there you could try to hide them in hardware you could try to hide them and software but it’s a reasonable assumption to make is that eventually they would be revealed and the polish the Polish cryptographers attack on the Enigma machine in fact they at the French intelligence espionage services had find out the wiring structure of the routers which were a key part of that machine the Germans presumably didn’t know that that had been that had been obtained but we’re more scare scenario one worst-case condition what is it very important to the manufacturers of cypher systems because it removes from them the responsibility of having to keep their there the system secret the next one is you assume that the Crypt analyst has obtained a considerable amount of the ciphertext and this is a reasonable assumption because of Eve can’t see any cipher text then there’s no point to have any encryption at all and Aviv can see ciphertext then the worst-case situation is that you can see all of it and the third worst-case scenario is to the Crypt Alice knows the plaintext equivalent of a certain amount of ciphertext so that some particular way perhaps by the structure of a communication for a letter if you know if the letter always starts off with the date the plaintext there first starts off with a theater perhaps they ends yours faithfully all the time and many military communications have got a very structured type of format then you know what appears in the cipher text come corresponding to certain bits of

plaintext on the other hand as I believe happened certain situations where were to the British would attack certain German light boys in order to be able to read the report of that attack which was encoded using the Enigma machine and they would know certain things like where the light boy clearly was located and at what time it was attacked so that’s an example of a chosen well and can be thought of as a chosen plaintext attack what they’re doing various they’re they’re feeding the plaintext into the cipher system and looking at the resulting ciphertext so one tends to look at all of these worst case scenarios when you’re trying to assess cypher security okay so let me turn now to the simple Caesar cipher and we’ll look at some of the ways in which we can attack it and it’s a very simple cipher you may may have used it at school but I wouldn’t advise putting much reliance on it but is this nice picture from the web because it shows that it can be mechanized by means of a machine what we have here the 26 letters of the alphabet and the Caesar cipher is really just a shift cipher shift cipher and what we have in this particular one is we’ve got the alphabet around the outside so that for example of Gresham College what you do is you go to G on the outside of the Ring and if you find G which is over over here then you encode G by the corresponding letter in the inside ring which is in fact G shifted by 13 letters clockwise so G goes to T then or if we can write Ryan to it it’s there or on the outside goes to 8 so this is a Caesar cipher with a shift of 13 and the reason it’s a shift of 13 is because that’s the diagram that I could find on the web and I had to current ID how much it was but I really wanted to use a shift of 3 so here’s my cipher diagram and I want to use no in the particular case of a Caesar cipher with encryption key 3 so here an encryption key is 3 so we’re going to shift clockwise thinking of the alphabet written right on a circle clockwise by 3 so that the word message m then goes to P shifting M by 3 letters clockwise he goes to H s goes to B s goes to V and so on and just for the sake of symmetry what I’ve done is to write the decryption algorithm out in a way that maintains symmetry and I say that the decryption algorithm is rotated clockwise by 23 and that will work because if you rotate by 3 and then you rotate by 23 3 plus 23 gives you 26 and 26 is going the whole way round and brings you back to the beginning the advantage of that and if it is an advantage is that the to the encryption and decryption algorithm others IAM and it’s the encryption keys and decryption key that are different one of them is three and one of them is twenty-three of course you could write it the other way round which is you could make the keys the same namely both of them three but here you say we’ll take clockwise by three and here you say wilt it anti-clockwise by three so different ways of writing the the system item but the Caesar cipher is very easily attacked and here I have got a cryptogram AF CCP that five letter cryptogram I want to find out what is this encrypting and I’m making the assumption that it is an English word and what I have done here is to write down all the possible originating messages could be under the different encryption keys so a possible originating message is AF CCP we just leave it alone another originating message might be this if you shift it by 25 and if you look down it here what you’re essentially looking for is an English word an English meaningful word there are in fact two of them cheer and jolly and it takes quite a while to find two five letter English words that go into each other under a Caesar shift I of course you’re going to listen to me for the rest of the lecture but otherwise you should try it for a six-letter word so what we’ve done there at the point I want to draw light from this very trivial example is that just by this brute-force attack we have immediately realized 24 we’ve ruled out

all the tooth keys so all the two of the keys are real tight we can’t decide which one it is on they’re sweeter have more plaintext or with some knowledge of the context and that’s frequently what happens when you have a Britta force attack but you’re not so much finding the case as ruling keys out okay because it’s going to be useful for later on just want to oh yes I just wanted to make this other point before that the second bit of point dying is that if you’re able to do unknown plea and text attack on a Caesar cipher you only have to submit the one letter because as soon as you know what any letter goes to you know what the shift is so Caesar cipher is totally vulnerable to a known plaintext attack if you know what a goes to you know the shift I just want to show you the can be written so now that the cipher because I want to enter just modular arithmetic this seems like a very straightforward place in which to do it I’m going to write the letters of the alphabet to encode them by the numbers and 0 up to 25 a he is 0 and B is 1 and so on up to 25 that’s one way of doing it then if the encryption key is why you could describe a Caesar cipher as saying that you are X plus y you are the number corresponding to the letter to the key Y but then to take into account that we’ve got this that that has been written in a circle what you then look for is the remainder modulo 26 so you divided by 26 and find the remainder and there’s an example of it there suppose the encryption key is 18 then if you want to encrypt J the number corresponding to J is 9 9 and 18 is 27 and what’s the remainder of 27 when you divide by 26 that’s 1 and therefore J is encrypted as bheem so that’s really introducing modular arithmetic there okay let me go to an example which shows that a large number of keys doesn’t necessarily provide security and that’s the simple substitution cipher a large number of keys is necessary for security but it’s not sufficient so the key here is that you tick the alphabet there’s the alphabet at night in alphabetical order and then you put down below with some rearrangement and that will be arrangement is written in blue the key is this set of blue letters in this particular order so in order to do the encryption if we want to encrypt gresham notice the publicity that’s going out all the time not even subliminally G goes to M or goes to K and E goes to – I know so the encryption and decryption keys are equal they’re just this ordering of the letters and the encryption algorithm is you replace each letter by the one below it unlink the decryption algorithm is you do the opposite you replace each letter by the one above it so let’s look at the number of keys that there are well the number of keys are just the number of ways you can write like the alphabet the number of different orderings of writing are they alphabet and believe me there are a lot of them there are 26 choices of which letter to put in the first position 25 left and of which there is to put in the second 24 which letter to put in the third and you keep multiplying them together and you get that number that is written down there and I would even attempt to read the dice but it’s approximately 10 4 times 10 to the power 27 for with 27 zeros after it and a very large number and I have worked this out if you were able to try a billion keys each second a billion keys each second it would take nearly 13 billion years to try them all however one disadvantage of it and this the point I’m making here is that these systems are a lot of the time used by people the keys long and difficult to memorize and that’s often what forms the weakness of a cipher system and remember we’re not able to write it down or if we do write it down we have to store it securely we have to keep it safe so one thing that is frequently done is to use a key phrase in order to generate the keys many people also do that as a way of remembering their passwords as well similar idea so if you take the key phrase again Gresham College free public lectures what you do with the key free is one way of doing it would be to write down Gresham College free public lectures but as you’re doing it only have each letter once so that you remove all repetitions from the key phrase so if you were to go along it G or ele sha m no letter has been repeated Co L but then the next L of college of course already appears so that is not inserted

that’s deleted then the e has already appeared the G has already appeared the next D is already appeared so the next new letter is F and you keep on doing that writing down each letter without repetitions until you get to the end of your phrase and then just fill in those letters of the alphabet that you haven’t written down so far and alphabetical order so it’s a relatively easy way to remember how to generate the key phrase each time all right and here I have done one with okay but aloha these large number keys of brute-force attack with each such a length of time it turns out that it’s very very easy to solve due to the statistics of the English language or and get deep any natural language and here I’ve taken a table and analysis of letters occurring in words listed and the concise Oxford Dictionary and the third column is proportions with the BS slang being the least frequent letter Q alright so this is telling us that e occurs nearly 57 times in this concise English dictionary more often than Q a occurs 43 more times or 38 times I 30 at times more frequently than the letter and as usual it’s probably easier to understand this visually it’s really saying the way I like to think of it is that this is a fingerprint of the English language right and the histogram here of the frequencies the one on the left is the frequency sorted by those which are most unpopular so starting off with e on the left hand side and on the right hand side I’ve just got the letters written right on the alphabetical order and what I’m saying if there’s a histogram is essentially characteristic of any long enough piece of English text reasonably accurately so that then points to the weakness of the substitution cipher because the substitution cipher does exactly what it says on the tin a substitution cipher substitutes so that for example if it substitutes E by W and then you do a frequency kind of all the letters in your ciphertext and you find out that W is the most frequent it’s very likely that W substitute for e and then you can look at the next four letters so that here is an example where I’ve got a particular key that I’m not telling you yet and I’ve written this message right and using a particular I’m telling you it’s a substitution cipher then what is down below it in the table is the frequency analysis for this particular text I’ve gone through it very relaxing counting how many times each of the letters occur and then I’ve done a graph off it down here so I’ve got the frequency diagram now that’s just going to be the same if if I’m right and that the statistics do work out that as the histogram we have before but it’s just going to be jumbled up in some way it’s just going to be permuted in the same way the substitution cipher permutes it so what I’m saying there and with that particular one and it’s harder to see that what we have is that this letter here which i think is that’s the one we’re going to initially substitute in for a and then looking at the other four that are most popular in the histogram substitute them and for the ones in the english-language text and we find out it comes out very quickly that the key is the one that I introduced a little while ago obtained from the freest Gresham College free public lectures and the text is just the publicity for for this particular lecture okay no few things you can perhaps think of as you’re looking at that I was very foolish in the sense that I I’d left in the the words in the cipher text and not silly you should all write it out in blocks of the same length say a Phi because there only are a couple of one letter words in English so if you know what the word length is if you leave their menu got you’ve got a good start and question that’s sort of obvious is how long is long enough I long should the ciphertext be in order to use a frequency analysis attack on it and it seems to 200 characters is long enough and avid students are able to do it with you know about a hundred because of their perseverance and how quick looking at possibilities are rather ruling out possibilities we’ve said it’s vulnerable because of the structure of

language and historically there were various other ways of trying to get around this fingerprint and one of which in a very famous cipher called the play first cipher encoded not letters but pairs of letters and had a particular way of doing that there but pairs of letters are subjective exactly the same and statistical analysis as letters certain by grams appear with particular frequency much more often than certain other by grams so general substitution things once you know that one of them is being used are very straightforward to attack so a large number of keys is not sufficient in order to assure security so what was the problem if you think back to what’s been going on the problem was Caesar cipher was subject to a known plaintext attack only one letter substitution cipher it had this fingerprint attached to it when you apply to frequency analysis what you want to do is to try to make that frequency histogram flat that all the letters in the cipher text should appear equally often various ways of doing that and come under the general heading of polyalphabetic ciphers where essentially what you’re doing is you’re using more than one substitution cipher the example I’m going to be looking at in the moment I’m going to be using it substitution ciphers in the Enigma machine with three rotors it was something like 17,576 substitution ciphers one after another and we’ll see in the example I’m going to show you how that flattens right the histogram and therefore tries to conceal the fingerprint so let me look at one particular example the Visionaire cipher which is going in this case to use it substitution ciphers and what you do is you take your plaintext you have your plaintext here age 26 V genera right then I take a key I’m going to take the key is being charles v and if the key isn’t long enough for your message what you do is just repeat the key charles v charles v and then I don’t need to use all of it and then we use the beach and their table and which is a table of substitution ciphers and if you had time to look at it for long enough they’re not just there are just simple Caesar substitution ciphers but there’s a table of them and then what I do is to for the letter A to encode the letter A I’m going to use rule C I look to the key and when I use row C of the table it tells me that this is the substitution cipher to use so in order to encode a a is going to be encoded as C so the a of the agent is encoded dying to see now the next letter I want to in court it’s G the key tells me that I should use raw edge of the thing and rule hich is I hope you’re appreciative of the effort I’ve gone into the graphics of this because otherwise I’m going to have to ask you close your eyes and imagine it but you might not have opened them again so there are anyway this tells us to use row hitch and we want to encode G and if we call from G down here it’s encoded as am we’ve just done here it’s at times like this you realize you’ve made a mistake on it and what we haven’t then the next one wanting Cody and a tell that the key tells us to encode a and rule a and the thing that we’re trying to encode is a of course just goes to itself now let’s see what that does to the signature let’s see what that does to the histogram so this is some little background about Visionnaire and what I’ve done below is to do a histogram of the frequency analysis of the plaintext and that’s what is in the upper histogram and down here after a monoalphabetic and substitution on it and as we know by now does is just to permute just to interchange the bars of the histogram but down here we’ve got the beach and error ciphertext so if you do a frequency analysis on it on the beach and err ciphertext once that that’s encoded notice how the histogram is much flatter the letters are occurring much more free and much more evenly across it ideally you would like them all to appear as often as possible so you think that’s good that’s all you know that’s progress and of course it is progress but again the ingenuity of people attacking these ciphers and you can realize it yourself if you know the length of the key word your home because if the key words of

length it it means that the first letter and the ninth letter and out on 8 and 9 the 17th letter all come from the same substitution cipher because the key has started to repeat on the second letter and the 10th letter and this one’s easier and the 18th letter all came from the same substitution cipher and the third letter on the 11th letter and so on and we knew how to break substitution ciphers you can I do that with your eyes closed so all you have to do is define the length of the key and you could just try by guessing you know but so on but there’s a better way of doing it which was discovered by Charles Babbage and what he did was reasonable idea he looked for repetitions of letters in the ciphertext looked for repetitions of longer the better but particular group of letters in the cipher text in any argued as follows if we do if repetitions it might be the case that what’s happening there is that the same letters in plaintext are being encoded a distance apart which is a multiple of the key so you’ve got repetitions within your ciphertext you look at the distance between them and you say it could be it’s very likely that the distance between them is going to be a multiple of the length of the key so you find out what numbers divided into that and you try those various possibilities for the key and you can run through it relatively quickly you certainly can’t of you can use a machine on it all right so that brings me to one of the polyalphabetic more famous polyalphabetic ciphers the Enigma machine which has let me just go forward to it to remind myself in then back again 17,576 substitution ciphers rather than the it that we just had the moment ago and this possibly best known for the activities of the cryptographers at crypt annals at Bletchley Park Alan Turing and colleagues there were they they had a very comprehensive way of breaking it but I want to tell you perhaps a less well-known story if I the Polish crypt analyst attacked it but first of all to describe what happens if you look at the picture on the left in order to use the machine for encrypting or decrypting this is a keyboard here and you press the letter on the keyboard K corresponding to you to the message in front of you and then there’s a little plug and a little land lamp board that lights up so you press the letter A and some we’ll light up on the Lamport and that’s what the encoding off it is and it’s an electromechanical one what happens this is a when you press the letter on the keyboard an electric current is flowing through the Machine and causing the light to light up but what is it flowing through well it flows through three rotors and I think you can see here I’ve tended to and to keep them and here’s the letter A being pressed and these Reuters are touching each other the little studs on each side of them which make contact and they are cross wired all right there’s an internal wiring follow so the current coming in here will go right there will go across to here go across the Vera come down to there and then they’re reflected of something which is called the reflector and here it comes back dying across here and so on and so we’ve got your rotors there’s internal wiring which was discovered by the French espionage and so the poles knew what the wiring was I’m not the coincides with our remember worst case scenario one about the cipher system to assume that everything about it is known now the cool thing two things want to mention now is that the thing is that you press the letter A and the lump for G works up and lights up but then the first rotor root hits it reflects on it rotates by one click okay so with us the next time you were to press a there will be a different set of wires that it goes through in fact the diagram has done search this route it’s like that round up to here which is why this horizontal line no appears at the top so there’s a different pathway to be followed through reflected back so that this time a will be encoded as C and if you were to press a again the rotor will click around once more and there would be a different encoding and then once this rotor has gone round 26 times this clicks once this rotates once the middle one and then once the middle one has gone right 26 times this goes right once okay so it takes 26 times 26 times six-four to get back to the state that

it was in before but that’s not all in order to give to the number of settings of this system to be much larger there’s introduced a plug board here where what a plug boards a bit like an old telephone exchange do you remember where you sort of electrical wires and you you connect two things together and what they do in the plug board is they choose six or seven pairs of letters to connect them together so that as you press the key there’s a swapping over of the letter before they go into the rotors then they’re reflected back through the rotors and then they’re reflected possibly at the plugboard again and then light up the lamp and I’ll show you what the numbers are in a moment okay so they’re the various components of and of course the other thing as well is that you the rulers are up here at the top and you can see there’s there’s another thing called a ring around the outside often but as Andrew Hodges says in this book that’s a tedious complication but what you can do is there letters along the top which gives you the setting of the rotors you know which way to set them off to start off with and I should also say that the rulers can be put into there in any order all right so quite a number of variation and of course I’m just giving you one example of it there were various kinds of Enigma machines with more than three rotors four or five I think some of them may have gone up to it I’m not sure and there are probably people in the audience we know a lot more about this than me but I’ll take this one is just an example of what goes on all right so let’s look at just some numbers it’s polyalphabetic first of all and 17,576 and each state the Enigma the substitution alpha that’s the swapping of pairs of letters and there’s a particular characteristic of this machine it can never encode a letter into itself and that form the basis one can think of that it’s form the basis of of cheering’s attack off and Bletchley Park that simple observation doesn’t encode a letter into itself and there’s a very good discussion of this in Tom coroners book on the pleasure of Counting where he brings you through the sort of mathematics underlying cheering’s attack and cheering and colleagues attack so let’s just do counting and the number of ruder setting this is 26 by 26 by 26 but you can have the rotors in any one of six orders you know you can choose which way to put the three of them in the plugboard connecting seven pairs of letters and that’s quite a fun thing to do to counter many ways it’s possible if you have 26 letters of the alphabet to connect them in pairs and the answer is that number that I’ve written died and I gave up when I going to calculate the total number of keys it’s just all of those multiplied together okay so we’ve got all of those large number of attacks let’s try to see what the possibilities are and it was broken by reduce key and this pictures probably take in 1932 the year he first sold it they point about his attack was high it was used so let me go to that all right code books were distributed to give the day K so all the units using it had a code book the code book would say you have to get the Reuters in this order and you have to turn them so they’re in these positions you have to use the plugboard to connect these letters that is an accord book that is distributed to every with every ending the machine I suppose but then the way of using it in 1930s was that the DES key was used to transmit a new key which the Alice and Bob were there knows whether Alice and Bob were their names I don’t know we then use to transmit a new key that would be used for all further sub subsequent communication so for example suppose the day K was my initials or gf and the sender uses it to transmit the chosen new key the sender decides to choose K J E and it was sent twice it was sent twice because they were worried about presumably corruption and transmission errors so to be able to pick that but that was the weakness that was the I’m doing that was her reduce scheme managed to crack it so with the de key setting of or gf we’ve got kje transmitted kje transmitted and it’ll come through as something then both sender and receiver switched their machine to have settings kje and communicate on from that but the thing about it rejewski seemed to know very little he knew the internal wiring he knew this he knew the machine but the only thing that he didn’t know is that on a given day all the messages that were intercepted

the first six characters were sent using the same key they were sent using the day key the key in the codebook and he knew something more he knew than all of those messages the first and fourth were in coatings of the same letter they were related just to use the word there was a relationship between them the second and fourth the third and the sixth of the first six letters and every message sent on any particular day so here is an example of just four messages and this repeats what I’ve said M and s are encoding of the same letter they are related and and why aren coatings of the same letter as our K and an E and Q and I’m starting to write that in a table here this is saying that E and Q there’s a under secure they’re related I’m saying that K and N or related K and there’s n it’s related I’m saying that N and Y are related have I do not know n why I’m saying that M&S orally now if you put a as you would have lots and lots of messages coming through your exam on the first six letters awesome you’re going to be able to complete that table and what we’ve got is that done down here that a and L are related B and G in other words not saying that you find some message in which a is the first letter and L is the force this is saying you find some message in which Q the first letter and D is that so what you’ve got here is a rearrangement of the alphabet down below without relationship and then you do something quite clever and it’s related to the notion of a mathematical object called a group which actually underlies so much so many of the ideas that I’m going to be mentioning in fact will be part of the conversation next time on what he did was he just started to unwrap what’s called the cycle structure of what’s below the line so he would start off with a letter here a goes to L then L goes to W W goes to F f goes to M M goes to s s goes to j j goes to C C goes to or and/or goes back to a so you’ve got the cycle going from a up to a which it’s got nine links then you look at the letter that doesn’t appear here such as B and you do the same thing and you get that that’s a cycle of length three and this is a cycle of length seven this is a cycle of length seven the amazing thing is that these cycles ends nine three seven and seven those numbers those cycle lengths are independent of the plugboard settings if you have a different plug board setting okay you’ll get different letters in the cycles but their lengths will be the same and you will have a cycle structure for the second and fifth letters and you will have a cycle structure for the third and the sixth letters so what regis key and colleagues did was they spent a year putting the rotors and all the three different orders adjusting them to all the different positions they could and they drew up the table of all the different cycle settings that there were for all the different 17,576 rotor settings when they got a message through particular day they look to see what the cycle structure was they looked at their table of what it was they would know what the rotor settings is and then strength they decoupled the plug settings from the rotor settings and then it actually is fairly straightforward to the terminal clock settings are quite remarkable and I think quite pretty because it’s it’s technically easier than what cheering did but it does show you how human ingenuity and analysis and mathematics oh we just gave us one of the first sort of mathematicians that were recruited to be involved with with this of course it’s highly dependent in the way it was used and it was no good once they changed their system here so coming to modern algorithms where you have information represented using bit strings within the computer and different ways in which you can do it and encoding systems really depend upon by modifying the bit codes and there’s a system called xor which is a way of adding together the only two numbers that you have are 0 and 1 and this is essentially addition modulo 2 which is bringing modular win down here I have for example a message 1 0 0 1 1 and this is the keys key for it 1 1 0 0 1 and you are these numbers modulo 2 or the way I like to think of it which is nicer is that if you’ve got a 1 in the key stream it changes the letter above it if you’ve got a 0 in the key stream it leaves the letter above it alone so here’s a 1 in

the key stream so it changes that letter in to 0 here’s a 1 it changes that letter 0 into 1 here’s a 0 that leaves that letter alone here’s a 0 it leaves that letter alone here’s a 1 it changes that letter that’s used in particular in cipher systems and in a stream cipher here what you get is a key and it comes back to our charles v using a the key idea you have a short key and you have various ways of generating a long key strength that you then combine with the message ok this is the thing that use usually to digitize and voice communications because it doesn’t have this error propagation if you make a mistake encoding one digit it’s not going to affect and it’s the sort of subsequent ones but it is vulnerable to a known plaintext attack because if you can dictate what the plaintext is in order to be encoded then it can then you can try to identify what the rule is identifying the keystream so there’s that disadvantage to it another thing originally a known plaintext was used in the system was initially used in these identification Friend or Foe radars to try to avoid and so if you’re doing data encryption and off you want stored it and out there a cipher system it’s not a very good way of doing it because you’re able to recover portions of it better way of doing it is to use a block cipher so you you choose a block length and you encode and the various blocks of it but remember our example back to the substitution cipher if you’ve got enough you’ll be able to start to build up the statistics of what the encoding is and that leaves you vulnerable to substitutions once you know the corresponding plaintext and cipher texts maybe just substituting now one for the other will be all that you need you needn’t even don’t need to know what the key is so there’s systems various ways of of getting error propagation coming into it one of them is called cipher block chaining and all that happens here the only thing you need to take out of this complicated sort of diagram is you’ve got the plaintext broken up into blocks along the top but when it comes down here and seen coded the encoding of the first block forms part of the encoding of the next block the encoding of the second block comes up and forms part of the encoding of the third block which means that a change in the message of just one or two letters earlier on will change all subsequent letters quite considerably so you get this massive ripple effect going through and it helps to guarantee the fact that our message has not been interfered with okay so if I come to this very important and influential paper by Whitfield Diffie and Martin Hellman on new directions and cryptography does say in its introduction the two kinds of problems that they were concerned about addressing and the problems are concerned about addressing is the need for secure key distribution channels because this is an expanding world expanding number of objects that are communicating with each other and some way of supplying a written signature on the paper which I’ve given the reference to at the end is well worth why reading it’s very accessible and it’s very thoughtful and I’m it’s written from the perspective of 1976 so so do I’ve given a way of reference for it so you’ll be able to just pull it down have a look at it and it’s got a nice sort of historical and section of the very end of it okay all right turns out that what they need to do is to find something is easy to do one way but difficult to do the other and the thing that they use here are called discrete logarithms now ordinary logarithms are relatively easy to calculate in fact one of my predecessors the first digression professor of geometry Henry Briggs calculated 30,000 logarithms to 14 decimal places and real logarithms are relatively easy to calculate because they behave sensibly if one number is bigger than another the logarithm is bigger okay but discrete logarithms aren’t like that here for example pick a prime say 17 and the reason I’m picking a prime is that again the integers naught 1 2 3 4 5 up as far as 16 because 17 is a prime form one of these group things that I’ll be mentioning next time and then if you look at it if y equals 10 to the X if the mod 17 weren’t there you know the rest of the sentence is 1 you’ve probably seen a lot

of times y equals 10 to the X then X is the logarithm of Y all right but here we’re saying if y equals 10 to the X mod 17 what we mean is that when you work our 10 to the X I’ll show you in a moment then you call X the discrete logarithm of Y so here for example what are we going to have look at 10 to the 7 it’s easy to calculate n to the seven divide 17 into it and the answer is five so the discrete logarithm of five is seven discrete logarithm of five or seven now here you come ten to the three ten to the three work out what it is it’s a thousand divided by 17 and the remainder is fourteen so the discrete logarithm of fourteen as three but notice immediately it should have behaving strangely you know sevens the discrete logarithm of Phi put fourteen is bigger but it’s discrete logarithm is 3 so this Greek logarithms don’t go all over the place they jump all over the place and the crux that you have to take from that that’s quite a lot there to absorb if you are meta before is that knowing the red number it’s easy to calculate the blue all you have to do is to multiply a certain part of ten and divide by 17 and find the remainder but it’s much harder if you know the blue number define out what the red number is but it’s hard to find X if you know why for example it equals 10 to the X mod 17 what’s X the answer is in the handout but it might be right okay let’s see how I feel him in you that’s the cool thing it’s a one way function a trapdoor function easy to fall in very hard to get out okay another example is usually given that I find quite helpful is that imagine you’re in a room locked in a room with them a copy of the London phone directory somebody can show to you the name and address of somebody and ask for the telephone number you look it up because the names are given alphabetically and you hand back the telephone number somebody tells you what on the other hand if somebody tells you what the telephone number is and asks you what the Niemen addresses of the person hey hold on alright okay so that that kind of suit in question so it’s discrete logarithms that are used here I’m just repeating essentially what I said before but knowing why it’s hard to find X no let’s see her Alice and Bob can use that in order to decide upon a key without meeting or without using a secure courier and in fact dude on a communication channel that Eve can listen to and they don’t care that Eve is listening because the discrete logarithms are hard to calculate so the way that they did it was that here we have two discrete logarithmic calculations I’ve got here Alice’s private key is seven Alice’s private key is the discrete logarithm of five our public key is fine so she publishes five but only she knows that ten to the power of seven has got a remainder of 5 the numbers are naughty I hope you appreciate that this done with numbers of you know a hundred thousand of dentures and three hundred binary digits and so on now Bob’s private key is three and as public key is fourteen in other words Bob publishes 14 all right but only Bob knows that you get 14 as being the remainder of ten to the three thousand and divided by 17 right so here I’m just saying five to Bob and then the algorithm to form the shared message is here the message key for Alice is going to be the public key of Bob right the public key of Bob to Alice’s private key the message key for Bob is the public key of Alice Ted bulbs private key and the amazing thing is that the mathematic shows you that they’re the same the reason they’re the same is because if you had a chance to unpack as you will do when you go home and the slide you will see that they are both 10 to the 3 x 3 x 7 mod 17 and the other one is 10 to the power of 7 x 3 mod 17 so they shared this common key 6 and that’s the one they should use for subsequent messaging all relies upon this and this business of being able to find the sorry the difficulty of doing discrete logarithms and then just to finish when we look at public key systems the idea of about a public key system this is our

cypher system just done another way from this particular source the Oh everything here is public except this everything in that diagram is public except that the most pop are very important one is the RSA public key system devised by Rivest Shamir and Adleman here and it’s named after their initials and I quite like it having it here on a on a t-shirt here where you can put it and it’s just an algorithm and it really is quite nice it describes it quite nicely you choose two big primes 100 decimal digit may even be more than asked assume lis going up all the time you form the number N equals P times Q it’s very easy to do that to multiply two Prime’s together alright then this is still bulb doing it and you take the number P minus 1 Q minus 1 that’s the number you’re going to be divided with defined remainders on you find two other numbers and again it’s reasonably easy to do this to find two numbers a and de for encryption D for decryption that leave a remainder one when divided by that too many details coming at you to absorb it but just notice what the steps are then – and then what do you publish well you publish your public key and on the key for encryption then to encrypt you raise your message m to the power of E and find what the remainder it has when you divide by n in order to decode you take the ciphertext the C you raise it to the D power and you find what its remainder is to the power and that works one thing undoes the other thing and that’s the reason for that is because that the remainders of this particular number here I can form one of those mathematical objects and called called a group under these two operations do each other if your is M to the power of E and then take that result and raise it to the power of D you get back to where you started the same as we had the example had before was ten to the power of three times seven and ten to the power of seven times three and you can use that idea to deviate just more detail there to form for example a digital signature and the cool thing and not when you have a look at it later on is that I’m sending a message here encoded using my private key you can decode it using my public key so you know it must be me because I’m the only person who could have used my private key to encode it because you’re decoding it using my public key brilliant very clever very simple okay then to finish not and I have to say although I’ve used diffie-hellman the 76 paper in my discussion it turns out that many of the main principles and techniques of public key cryptography have been developed and earlier in the 1970s by James Ellis Clifford Cox and Malcolm Williams and at the UK government’s communique electronic security grip the work was classified and not made public for over two decades that’s interesting I think the speculated what else may be secret at the moment a lot of work research money is going into cryptographic research because the security communications are becoming more and more important because of e-commerce and furious other reasons and it’ll just matter to large organizations the banks and commerce retailers and so on it bothers to ordinary individuals and in order to show you our topic of this topic is in The Guardian last Saturday in the money section the headline was pay us to Hunter Pines or we will lock your computer forever and apparently the thing that’s being downloaded they’re calling ransomware and if you inappropriately click on something it encrypts your files using public key cryptography and then you get a message saying that they’ll send you the private key if you will send them two hundred pines otherwise you’ll never be able to gather that I’ve tried to convince you off here so if there’s one thing I hope that you’ve learned from this lecture is that when you get home backup your computer so look forward to seeing you this is in the hand I’d also add on to that the pleasure of counting by Tom corner and hopefully see you symmetries and groups for Christmas treat on early Christmas tree Tuesday the 19th November thank you