{VERSION 2 2 "IBM INTEL NT" "2.2" } {USTYLETAB {CSTYLE "Maple Input" -1 0 "Courier New" 0 1 255 0 0 1 0 1 0 0 1 0 0 0 0 }{CSTYLE "" -1 18 "" 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 } {CSTYLE "" 18 20 "" 0 1 0 0 255 1 0 0 0 0 0 0 0 0 0 }{PSTYLE "Normal" -1 0 1 {CSTYLE "" -1 -1 "Arial" 0 12 0 0 128 1 2 1 2 0 0 0 0 0 0 }0 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }{PSTYLE "Text Output" -1 2 1 {CSTYLE "" -1 -1 "Courier New" 1 10 0 0 255 1 0 0 0 0 0 1 3 0 0 }1 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }{PSTYLE "Warning" 2 7 1 {CSTYLE "" -1 -1 "" 0 1 0 0 255 1 0 0 0 0 0 0 1 0 0 }0 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }{PSTYLE "Err or" 7 8 1 {CSTYLE "" -1 -1 "" 0 1 255 0 255 1 0 0 0 0 0 0 0 0 0 }0 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }{PSTYLE "Maple Output" 0 11 1 {CSTYLE "" -1 -1 "" 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 }3 3 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }{PSTYLE "" 11 12 1 {CSTYLE "" -1 -1 "" 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 }1 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }} {SECT 0 {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 10 "#public.ms" }}} {EXCHG {PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 76 " \+ This entire document has been produced using 'MAPLE', the 'Comp uter" }}{PARA 0 "" 0 "" {TEXT -1 75 " Algebra Software' which \+ is installed on computers in St. Patrick's" }}{PARA 0 "" 0 "" {TEXT -1 76 " computer laboratory. Anyone who is interested in find ing out about" }}{PARA 0 "" 0 "" {TEXT -1 71 " how to obtain M APLE is welcome to ask me about it. " }}{PARA 0 "" 0 "" {TEXT -1 72 " ____________ _______________" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 68 " PUBLIC LECTURE. WED. 6th. NOV EMBER 1996." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 69 " ST. PATRICK'S COLLEGE, DRUMCONDRA, DUB LIN 9." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 0 " " }}{PARA 0 "" 0 "" {TEXT -1 49 "LECTURE TITLE: PRIME NUMBERS and" }}{PARA 0 "" 0 "" {TEXT -1 61 " \+ PUBLIC-KEY CRYPTOGRAPHY" }}{PARA 0 "" 0 "" {TEXT -1 45 " \+ " }}{PARA 0 "" 0 "" {TEXT -1 56 "LECTURER: Dr. JOHN COSGRAVE, " }} {PARA 0 "" 0 "" {TEXT -1 65 " \+ MATHEMATICS DEPARTMENT, " }}{PARA 0 "" 0 "" {TEXT -1 66 " \+ ST. PATRICK'S COLLEGE," }}{PARA 0 "" 0 "" {TEXT -1 63 " DR UMCONDRA," }}{PARA 0 "" 0 "" {TEXT -1 65 " \+ DUBLIN 9," }}{PARA 0 "" 0 "" {TEXT -1 64 " IRELAND." }} {PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 59 "E-mail: \+ johnbcos@iol.ie (home)" }}{PARA 0 "" 0 "" {TEXT -1 65 " ___________________________________ ________" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 217 "AIM of LECTURE: To explain the fundamental concept of 'public-ke y cryptography' (a revolutionary development of the past twenty years) , and to show how 'prime' numbers have played an integral role in its \+ development." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 16 "PLAN of LECTURE:" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 77 "1. What is 'Cryptography'? A very brief history fo r the period to 1976 A.D." }}{PARA 0 "" 0 "" {TEXT -1 5 " " }} {PARA 0 "" 0 "" {TEXT -1 79 "2. The fundamental idea of public-key cr yptography (Diffie and Hellman, 1976)." }}{PARA 0 "" 0 "" {TEXT -1 0 " " }}{PARA 0 "" 0 "" {TEXT -1 62 "3. A brief mathematical interlude (' modular exponentiation')." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 " " 0 "" {TEXT -1 82 "4. The realization of public-key cryptography (Ri vest, Shamir and Adleman, 1977)." }}{PARA 0 "" 0 "" {TEXT -1 2 " " }} {PARA 0 "" 0 "" {TEXT -1 50 "5. Fundamental mathematical ideas for pu blic-key." }}{PARA 0 "" 0 "" {TEXT -1 69 " __ _________________________________________" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 72 " 1. W hat is Cryptography? A brief history." }}{PARA 0 "" 0 "" {TEXT -1 0 " " }}{PARA 0 "" 0 "" {TEXT -1 121 "[ Etymology: from the Greek 'kryptos logos', meaning 'hidden word'. So 'cryptography' is 'secret' or 'hid den' writing. ]" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 216 "I will speak on this (and am not making it part of my te xt, which I only regard as the 'bones' of my talk) for about five/ten \+ minutes. At the end of this part of my lecture the key terms (no pu n intended) will be:" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 " " {TEXT -1 33 "a. plaintext (the ordinary text)" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 69 "b. encryption key (what \+ someone applies to plaintext to disguise it)" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 47 "c. ciphertext (the encrypted f orm of the text)" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 76 "d. decryption key (what one applies to ciphertext to rec over the plaintext)" }}{PARA 0 "" 0 "" {TEXT -1 69 " \+ ___________________________________________" }}{PARA 0 "" 0 " " {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 75 " \+ 2. The fundamental idea of public-key cryptography " }}{PARA 0 "" 0 " " {TEXT -1 77 " (Diffie and Hellman, Stan ford University, 1976)" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 24 "Their fundamental paper:" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 74 "'New Directions in Cryptography ', IEEE Transactions on Information Theory," }}{PARA 0 "" 0 "" {TEXT -1 80 "Vol. IT-22, No. 6, November 1976, 644-654. (IEEE is the Institu te of Electronic " }}{PARA 0 "" 0 "" {TEXT -1 26 "and Electrical Engin eers.)" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 73 "The opening sentence from their paper read: \"We stand today on the b rink " }}{PARA 0 "" 0 "" {TEXT -1 34 "of a revolution in cryptography. \" " }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 69 "In this paper they proposed the IDEA (and much, much more as well) of" } }{PARA 0 "" 0 "" {TEXT -1 70 "'public-key' (as opposed to the classica l 'private-key') cryptography." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }} {PARA 0 "" 0 "" {TEXT -1 37 "I will talk about this in my lecture." }} {PARA 0 "" 0 "" {TEXT -1 77 " ________ ____________________________________" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 88 " 3. A brief \+ mathematical interlude ('modular exponentiation')" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 73 "Question: What remainder \+ does the number 34 'leave' when divided by 13? " }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 90 "That's easy. 34 = 13*2 + 8, and so on division by 13 the number 34 'leaves' remainder 8. " }} {PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 245 "Dividing numbers by 13 is called 'doing modular arithmetic' with 'modulus' 13, and this is how one does it (in MAPLE) with the above example, follow ed rapidly with some other examples (which I will ask YOU to do in you r head before I use MAPLE):" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 10 "35 mod 13;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#\"\"*" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 40 "123437652596 959161941949 mod 5461385845;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#\"+%y$ Rw8" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 30 "100000000000000 mod \+ 100000000;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#\"\"!" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 38 "10000000000000000018 mod 100000000000;" } }{PARA 11 "" 1 "" {XPPMATH 20 "6#\"#=" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 " " 0 "" {TEXT -1 93 "Another question: What remainder does the number 3 to the power of 5 leave on division by 13?" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 376 "That's also easy. 3^5 = 243 = 13*18 + 9, and so on division by 13 the number 3 to the power of 5 le aves remainder 9. Dividing numbers by 13 is - as you know - 'doing mo dular arithmetic' with 'modulus' 13; dividing powers of numbers by 13 \+ is called 'doing modular exponentiation' with modulus 13, and it can o f course be done by the MAPLE command which you have already seen:" }} {PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 11 "3^5 mod 13;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#\"\"*" }}}{EXCHG {PARA 0 " > " 0 "" {MPLTEXT 1 0 11 "5^3 mod 13;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#\"\")" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 16 "12321^3 mod 873 ;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#\"$'R" }}}{EXCHG {PARA 0 "> " 0 " " {MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 177 "But how about finding - for example - the remain der that the number 123456789123456781234567 to the power of 987654321 987654321987654321 leaves on division by 122333444455555? " }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 13 "Let's try it:" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 73 "1 23456789123456781234567^987654321987654321987654321 mod 12233344445555 5;" }}{PARA 8 "" 1 "" {TEXT -1 35 "Error, integer too large in context " }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 48 "What does that \"Err or, object too large\" mean? " }}{PARA 0 "" 0 "" {TEXT -1 0 "" }} {PARA 0 "" 0 "" {TEXT -1 306 "It means that the number 123456789123456 781234567^987654321987654321987654321 is too large for MAPLE to handle . But not only is it too large for MAPLE to handle, it is in fact SO \+ large that even if it were calculated it would require years to write \+ it out even at a rate of billions of digits per second. " }}{PARA 0 " " 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 554 "But - as you will see later - this (the finding of the remainder) is precisely the sort of calculation that one needs to be able to do in 'public-key' crypto grahy. Number theorists have known for many years how to do this sort of calculation. It is done by a combination of methods: ordinary 'mo dular' arithmetic, together with what is called the 'square and multip ly' method. The details of this would take some time to explain, and \+ so you must allow me to skip gently by them (the details are actually \+ quite simple, and I teach them to my students)." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 244 "MAPLE has an inbuilt fac ility for doing 'modular exponentiation', and here I illustrate it wit h a few examples, starting with the ones with which you are already fa miliar, and then moving on to the one that led to the \"Error, object \+ too large\":" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 12 "3&^5 mod 13;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#\"\"* " }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 12 "5&^3 mod 13;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#\"\")" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 17 "12321&^3 mod 873;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#\"$'R" }} }{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 76 "And now - much more drama tically - the earlier \"Error\" one, and onother one:" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 74 "1234567891234567 81234567&^987654321987654321987654321 mod 122333444455555;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#\"/n1+`>LI" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 " " 0 "" {TEXT -1 12 "Instantly!!!" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }} {PARA 0 "" 0 "" {TEXT -1 44 "You see the difference in the 'commands'? " }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 159 "T he earlier command was of the form a^b mod m. In that form MAPLE was \+ being asked to FIRST calculate a^b, and THEN calculate the remainder o n division by m. " }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 172 "The latter command was of the form a&^b mod m. In that \+ form MAPLE was being asked to use modular arithmetic TOGETHER with the (INCREDIBLY FAST) square-and-multiply method." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 17 "One more example:" }} {PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 79 "208 6822056296502560265&^3548276254987776266 mod 9319872949682527201949416 49999;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#\"?c]blI-p'zmbV/vo&" }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 33 " " }}{PARA 0 "" 0 "" {TEXT -1 192 "Later you will see why we need to be able to do such cal culations. \+ ____________________________________________" }} {PARA 0 "" 0 "" {TEXT -1 28 " " }}{PARA 0 " " 0 "" {TEXT -1 77 " 4. The realization of public-key cryptography by" }}{PARA 0 "" 0 "" {TEXT -1 76 " \+ Rivest, Shamir and Adleman of MIT, 1977." }} {PARA 0 "" 0 "" {TEXT -1 77 " (MIT = the Ma ssachusetts Institute of Technology)" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 24 "Their fundamental paper:" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 163 "'A method for obtai ning digital signatures and public-key cryptosystems', Communications \+ of the ACM (Association for Computing Machines), Vol. 21, (1978), 120- 126." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 214 " Their paper began: \"An encryption method is presented with the novel \+ property that publicly revealing an encryption key does not thereby re veal the corresponding decryption key. This has two important conseque nces:" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 73 " (1) Couriers or other secure means ane not needed to transmit keys, .. . ." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 161 "( 2) A message can be \"signed\" using a privately held encryption key. \+ Anyone can verify this signature using the corresponding publicly rev ealed encryption key. " }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 191 " Signatures cannot be forged, and a signer cannot \+ later deny the validity of his signature. This has obvious applicati ons in \"electronic mail\" and \"electronic funds transfer\" systems . .. ." }}{PARA 0 "" 0 "" {TEXT -1 79 " \+ ___________________________________________" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 247 "The work of Rivest, Sham ir and Adleman first gained widespread public attention when it was br illiantly explained by Martin Garnder in his 'Scientific American' Mat hematical Games column in the August 1977 issue. The header for that \+ article read:" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 85 " \"A new kind of cipher that would tak e millions of years to break\"" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }} {PARA 0 "" 0 "" {TEXT -1 141 "It was in that article that the famous R SA_129 'challenge number' first made its appearance. I will have thing s to say about that later ... ." }}{PARA 0 "" 0 "" {TEXT -1 79 " \+ ________________________________________ ___" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 549 "W HAT IT'S ALL GOING TO BE ABOUT. In a nutshell, what I am going to att empt to explain to you reduces to this: You know what a prime number i s (2, 3, 5, 7, 11, 13, ... ). There are an 'infinite' number of them \+ (Euclid), and if I were to choose two SMALL primes and NOT reveal them to you, BUT told you their product, THEN you would have NO difficulty in telling me what the two primes were. Say, for example, I told you their product was 91; then after a moment's reflection you would be a ble to tell me that the primes I had chosen were 7 and 13." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 513 "BUT if I were to choose two 'LARGE' primes and not reveal them to you, and I told you \+ their product, then you (and not only you, but - for example - the US \+ National Security Agency) would find it VIRTUALLY IMPOSSIBLE (in a sen se which I will be more explicit about later) to tell me what the two \+ primes were. It is this (current) VIRTUAL IMPOSSIBILITY that Rivest, Shamir and Adleman exploited to create an \"unbreakable cryptographic protocol\" (there are reservations which I will explain later in the \+ lecture)." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 81 "So, keep your eye open for the PRODUCT of TWO prime numbers in wha t follows ... ." }}{PARA 0 "" 0 "" {TEXT -1 64 " \+ _______________________________" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 127 "Here I will throw you in at th e deep end, and then embark on a mathematical journey at the end of wh ich I hope you will 'know'." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 68 " \" We shall not \+ cease from exploration" }}{PARA 0 "" 0 "" {TEXT -1 65 " \+ And the end of all our exploring" }}{PARA 0 "" 0 "" {TEXT -1 67 " Will be to arrive where \+ we started" }}{PARA 0 "" 0 "" {TEXT -1 73 " \+ And know the place for the first time. \"" }}{PARA 0 "" 0 "" {TEXT -1 81 " \+ (T.S. Eliot)" }}{PARA 0 "" 0 "" {TEXT -1 63 " \+ ________________________________" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 425 "The first thing I do (an d this is elementary) is to give instructions for converting plaintext into numerical form, according to the associations: a with 1, b with \+ 2, ... , z with 26, A with 27, B with 28, ... , Z with 52, ` (the 'bac kward quote' sign) with 53, 1 with 54, 2 with 55, ... , 9 with 62, 0 w ith 63, - (the minus sign) with 64, ... , ( - the left round bracket - with 75, ... , a 'space' with 79, ... , and so on." }}{PARA 0 "" 0 " " {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 279 "[ These instructions w ere communicated to me - via the Internet - by Joe Riel, an engineer w orking in California. I sent out an enquiry via the 'Maple Users Group ' asking for help with this, and within hours I had several helpful responses, the best of which was Joe Riel's. ]" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 134 "The following is simply \+ to instruct MAPLE as to which letters (small and large case), numerals , punctuation marks, etc. I wish to use:" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 20 "`crypt/alphabet` := " }} {PARA 0 "> " 0 "" {MPLTEXT 1 0 28 "`abcdefghijklmnopqrstuvwxyz`" }} {PARA 0 "> " 0 "" {MPLTEXT 1 0 30 " .`ABCDEFGHIJKLMNOPQRSTUVWXYZ`" }} {PARA 0 "> " 0 "" {MPLTEXT 1 0 32 " .```1234567890-=~!@#$\243%^&*()_+` " }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 21 " .` ,./<>?;':\"[]\{\}|`:" }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 79 "The following sets up the association between the terms of the 'crypt/alphabet'" }}{PARA 0 "" 0 "" {TEXT -1 24 "and the numbers 1 to 95." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 51 "to_number := proc(st, str ing) local ll, nn, ss, ii;" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 42 "globa l `crypt/alphabet`; ll := length(st);" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 37 "if ll = 0 then RETURN(0) fi; nn := 1;" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 57 "for ii to ll do ss := SearchText(substring(st, ii .. \+ ii)," }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 18 "`crypt/alphabet`);" }} {PARA 0 "> " 0 "" {MPLTEXT 1 0 39 "if not type(ss, numeric) or ss = 0 \+ then" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 45 "ERROR(`the letter `.(substr ing(st, ii .. ii))" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 27 ".` is not in \+ the alphabet`)" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 25 "fi; nn := 100*nn \+ + ss od;" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 19 "nn - 10^(2*ll) end:" }} }{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 14 "Some examples:" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 46 "to_number (`Welcome to St. Patrick's College`);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#\"[o02077:H!)>)=J!4=?,U!G3_/e,-eI^J?^!\\" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 22 "And a much longer one:" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 227 "[Added afterwards for pe ople to whom I send this worksheet: This next one may lead to an 'Erro r' message ('strings') for you, and you may need to change it. I just \+ wanted to write a message with a great variety of signs in it.]" }} {PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 282 "to _number(`There are - at the moment - US$1.60 to IR\2431 (the Irish 'pu nt'). In one of George Orwell's letters (in the 4-volume Penguin edit ion) you may read that at one time the rate was US$5 to St\2431. Do y ou remember the term 'half a dollar'? It was two shillings and sixpenc e!!`);" }}{PARA 12 "" 1 "" {XPPMATH 20 "6#\"c\\mnn0.90;C4>![S6+)>29477 43>!eJ--)>,B!3_.o)))=,77:/!=+o?6!3)3Q\"=0?!e!3?!)=0-8080=!=_^-e,.3G[:2 _/e,-)eqXZ!)>,B!e+7!=!e!3?!eI\"4?!eS^,37+37!3?![5]!=!e7I,=_^-yZ^\"4?4/ 0![\"4@290U!eI6A^@Uw0e!3?![\"4w!)>=0??07!)>)G@^I#=T!eq!=:0L!o],eS^,[^. 3Gy()3U6i\")3)3>4=N!e!3?w![:Za.e,-Q'f#[0du/[13U^I^J,e!3?!37+[1e!=,!e!= 03Y" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 2 " " }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 81 "The '6767' at t he end of the output represents '!!', the double exclamation mark." }} {PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 68 "And now s ome instructions to recover a text from its numerical form:" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 33 "from_numb er := proc(nn, integer) " }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 30 "local s s, mm, ll, pp, ii, ans;" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 34 "global ` crypt/alphabet`; mm := nn;" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 43 "ll := floor(1/2*trunc(evalf(log10(mm))))+1;" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 40 "ans := ``; for ii to ll do mm := mm/100;" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 19 "pp := 100*frac(mm);" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 43 "if pp > length(`crypt/alphabet`) then ERROR" }}{PARA 0 "> " 0 " " {MPLTEXT 1 0 53 "#(`there is no letter in the alphabet corresponding `" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 45 "#.`to the number `.(convert(p p, string))) fi;" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 44 "(`there is NO m eaningful text corresponding`" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 40 ".` to the number you have inputted`) fi;" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 42 "ss := substring(`crypt/alphabet`, pp..pp);" }}{PARA 0 "> " 0 " " {MPLTEXT 1 0 36 "ans := cat(ss, ans); mm := trunc(mm)" }}{PARA 0 "> \+ " 0 "" {MPLTEXT 1 0 12 "od; ans end:" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 " " 0 "" {TEXT -1 14 "Some examples:" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }} {PARA 0 "> " 0 "" {MPLTEXT 1 0 26 "from_number(950102030495);" }} {PARA 11 "" 1 "" {XPPMATH 20 "6#%'|grabcd|grG" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 0 "" }} {PARA 0 "" 0 "" {TEXT -1 60 "And now I take the number you have just s een, and adjoin an " }}{PARA 0 "" 0 "" {TEXT -1 20 "extra 96 at the en d:" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 28 "from_number(95010203049596);" }}{PARA 8 "" 1 "" {TEXT -1 97 "Error , (in from_number) there is NO meaningful text corresponding to the nu mber you have inputted" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 82 "from_number(3005011880361 5081481805115211880120503202118058023011980191580828282);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#%CDear~John,~Your~lecture~was~so~...G" }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 204 "So much for just taking \+ a text and recasting it in numerical form according to the above assoc iations. Now to get down to the real business of sending public-key e ncrypted messages, and their decryption:" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 82 " A Co okbook for public-key encryption and decryption." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 282 "I am going to show you h ow SOMEONE can send ME a message that THEY encrypt by the 'RSA cryptog raphic protocol' (as it is called, after its creators, Rivest, Shamir \+ and Adleman), and which THEY do NOT ANYONE TO UNDERSTAND BUT ME, and s how you what I then do to decrypt THEIR message." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 85 "It is to be understood th at the above numerical associations are already agreed upon." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 266 "BEFORE anyone \+ can send me an RSA-encrypted message they have to know what is called \+ my 'public-key'. My public key is a pair of numbers (n, e). The 'n' \+ is what is called my 'public modulus', and the 'e' is my 'public encry ption power'. These are formed as follows:" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 91 "The first step is to choose a ( reasonably big - more on how big later) random prime number:" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 62 "p:=nextpr ime(56782894997592526946596965999565948474734464644);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"pG\"P*pkWtu%[fc**f'pfYp_#f(*\\*Gyc" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 47 "and then similarly choose anoth er prime number:" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 65 "q:=nextprime(7529658762856826582828448562554749438437 3773574447);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"qG\"SfWdtPP%Q%\\Zb i&[%GGeEo&Gwe'Hv" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}} {EXCHG {PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 38 "TH OSE 2 PRIME NUMBERS ARE KEPT SECRET." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 53 "And then I multiply those two prime num bers together:" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 7 "n:=p*q;" }}{PARA 12 "" 1 "" {XPPMATH 20 "6#>%\"nG\"\\q TG_$=DuLq3&Gf\">)=')[w$[2gYF5u$G2Ai&3i4_>weIJL;+**G#ebF%" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 100 "That number 'n' is my PUBLIC M ODULUS ('public' in the sense that I do NOT care who knows its value). " }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 66 "Next \+ I form my a certain number 'e', my 'public encryption power'." }} {PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 26 "That is f ormed as follows:" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 76 "First I form a VERY SPECIAL number called 'phi_n' which, \+ like p and q above," }}{PARA 0 "" 0 "" {TEXT -1 20 "is ALSO KEPT SECRE T:" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 23 "phi_n:=(p - 1)*(q - 1);" }}{PARA 12 "" 1 "" {XPPMATH 20 "6#>%&phi_ nG\"\\q%o$[vmd/+\"QI,!4r&4`1z\"R[&4ucm$G2Ai&3i4_>weIJL;+**G#ebF%" }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 400 "Having formed phi_n I th en form my 'public encryption exponent' 'e'. That is specially chosen \+ so that there is NO whole number larger than 1 which is a factor of BO TH e AND phi_n. [ And so - for example - IF p and q had been 19 and 23 , then one would NOT choose e to be 15 because 3 is a factor of BOTH 1 5 AND (19 - 1)*(23 - 1). Whereas IF e had been chosen to be 7 (say), t hen it would be alright. ]" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 59 "In practice I choose e to be a large randomly cho sen prime:" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 38 "e:=nextprime(75859825925924926296969);" }}{PARA 11 " " 1 "" {XPPMATH 20 "6#>%\"eG\"8LqHE\\#f#f#)fe(" }}}{EXCHG {PARA 0 "> \+ " 0 "" {MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 0 "" }} {PARA 0 "" 0 "" {TEXT -1 243 "I have to be CERTAIN that there is NO wh ole number larger than 1 which is a factor of BOTH e and phi_n. That i nvolves some standard mathematics (called the 'Euclidean algorithm') - the details of which need not concern you - and is checked by:" }} {PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 70 "igc d(e, phi_n); # 'igcd' stands for 'integer greatest common divisor'" } }{PARA 11 "" 1 "" {XPPMATH 20 "6#\"\"\"" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 " " 0 "" {TEXT -1 81 "The MEANING of that '1' is that the ONLY factor of BOTH e and phi_n is 1, and so " }}{PARA 0 "" 0 "" {TEXT -1 15 "here I am safe." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 81 "[ Aside: here two examples for you to see, with smaller whole numb ers involved: ]" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 13 "igcd(15, 22);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#\"\" \"" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 13 "igcd(15, 21);" }} {PARA 11 "" 1 "" {XPPMATH 20 "6#\"\"$" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 41 " \+ " }}{PARA 0 "" 0 "" {TEXT -1 410 "Having c hosen my PUBLIC encryption exponent e, I then proceed to calculate my 'PRIVATE decryption exponent' 'd'. That number d is the UNIQUE numbe r BETWEEN 1 and phi_n such that the product of e and d leaves remainde r 1 on division by phi_n. A FUNDAMENTAL mathematical point is that d \+ can ONLY be calculated by someone who KNOWS the value of phi_n, or, wh at amounts to the same thing, the values of p and q." }}{PARA 0 "" 0 " " {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 114 "Now that I have chosen - and made known my RSA 'public-key' (n, e) - I am ready to receive R SA-encrypted messages." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 146 "So, suppose someone (YOU, let us say) wanted to sen d ME an RSA-encrypted message, whose plaintext was: The money is now in your Swiss account. " }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 " " 0 "" {TEXT -1 26 "This is what you would do:" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 90 "First you would cast your text into numerical form, using the above agreed instructions: " }} {PARA 0 "" 0 "" {TEXT -1 18 " " }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 76 "numerical_form_of_text:=to_number(`The money is now i n your Swiss account`);" }}{PARA 12 "" 1 "" {XPPMATH 20 "6#>%7numerica l_form_of_textG\"go?9@:..,!)>>4BX!)=@:D![\"4!Q_T,)>4!e_S^J,e!3Y" }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 87 "and then you would check \+ to see how many digits are in the numerical form of your text:" }} {PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 31 "len gth(numerical_form_of_text);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#\"#w" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 "" 0 " " {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 57 "You also check how many digits my 'public modulus' n has:" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }} {PARA 0 "> " 0 "" {MPLTEXT 1 0 10 "length(n);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#\"#(*" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }} }{EXCHG {PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 186 " With the number which is the numerical form of your text being LESS th an my public modulus you are now ready to send me your message (I will explain in my lecture what you do otherwise)." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 20 "This is what you do:" }} {PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 193 "You take the number which is the numerical form of your text, and apply 'modul ar exponentiation' to it, using MY PUBLICLY DECLARED ENCRYPTION EXPONE NT (e) with MY PUBLICLY DECLARED MODULUS (n):" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 88 "numerical_form_of_c ipher_text:=numerical_form_of_text&^e mod n; # the transformed text " }}{PARA 12 "" 1 "" {XPPMATH 20 "6#>%>numerical_form_of_cipher_textG \"[q.[E94y%*=JnD[tNz)R*eQ\\Mo]()\\'f6:c#\\v#=oxr&)4E]3T@K'eQ$)" }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 58 "You then send me the numb er numerical_form_of_cipher_text." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }} {PARA 0 "" 0 "" {TEXT -1 72 "On receipt of your encrypted message I pr oceed to decrypt it as follows:" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }} {PARA 0 "" 0 "" {TEXT -1 238 "I would ALREADY have calculated my 'decr yption exponent' d. That number d is the UNIQUE number between 1 and p hi_n (which is HUGE when p and q are large) such that the PRODUCT of e and d leaves remainder 1 on division by the number phi_n." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 222 "The value of 'd' is calculated by using a method called the 'extended Euclidean algori thm', a simple, but remarkably powerful idea which dates from Euclid ( 300 B.C.). (This is also something which I teach to my students.)" }} {PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 69 "igc dex(e, phi_n, x, y); # the 'ex' is the 'extended Euclidean ... '" }} {PARA 11 "" 1 "" {XPPMATH 20 "6#\"\"\"" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 " " 0 "" {TEXT -1 332 "You need not be concerned with what that 'x' and \+ 'y' is about (thought I will explain it to anyone who wishes to know w hat's going on); suffice it to say that some powerful Mathematics is g oing on behind the scenes, which enables me (the one who CHOOSE the pr imes 'p' and 'q' some time ago) to calculate the 'decryption exponent' d:" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 15 "d:=x mod phi_n;" }}{PARA 12 "" 1 "" {XPPMATH 20 "6#>%\"dG\"\\q*eKR : " 0 "" {MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 246 "Now that I have the value of ' d', the numerical form of the ORIGINAL text is recovered by MY applyin g modular exponentiation to the received numerical_form_of_cipher_text , using my PUBLIC modulus n, together with my PRIVATE decryption expon ent d:" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 73 "numerical_form_of_decoded_text:=numerical_form_of_cipher_text& ^d mod n; " }}{PARA 12 "" 1 "" {XPPMATH 20 "6#>%?numerical_form_of_de coded_textG\"go?9@:..,!)>>4BX!)=@:D![\"4!Q_T,)>4!e_S^J,e!3Y" }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 113 "And I now recover the te xt of the message YOU sent to ME, by transforming the last string of d igits into text by:" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 59 "original_text:=from_number(numerical_form_of_decod ed_text);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%.original_textG%GThe~mo ney~is~now~in~your~Swiss~accountG" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 " " 0 "" {TEXT -1 142 "Suppose someone somehow eavesdropped on the above message. Could they decrypt it? They could if they knew my PRIVATE decryption exponent d." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 57 "Let's see what happens if they try GUESSING my PRIVA TE d:" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 22 "d_guess:=682569569269;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%(d_g uessG\"-p#p&pDo" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}} {EXCHG {PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 75 "Th at guessed value of d would result in the following attempted decrypti on:" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 85 "numerical_form_of_attempted_decryption:=numerical_form_of_cipher_t ext&^d_guess mod n;" }}{PARA 12 "" 1 "" {XPPMATH 20 "6#>%Gnumerical_fo rm_of_attempted_decryptionG\"[q\"p'prdk,b0^Fe07LIB1&oc8T>!poi)**[w6,#R g`bUU\"[hUyL>$4D" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}} {EXCHG {PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 79 "wh ich would now result in the following attempt at restoring the origina l text:" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 77 "attempted_original_text:=from_number(numerical_form_of_attempt ed_decryption);" }}{PARA 8 "" 1 "" {TEXT -1 97 "Error, (in from_number ) there is NO meaningful text corresponding to the number you have inp utted" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 146 "Of course IF s omeone did correctly guess my PRIVATE decryption exponent d, then they would be able to recover the text of the message you sent me." }} {PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 209 "I wish t o remind you that there is a UNIQUE value for d in the range 1 to phi_ n, and so when p and q are large then phi_n ( = (p - 1)*(q - 1) ) is l arge, and so the chances of correctly guessing it are remote." }} {PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 222 "And it's not even the case that if one quessed close to d that an eavesdropper would do any better. I will illustrate by choosing a guessed decrypti on exponent which is 1 less, and then 1 more, than the correct value o f d:" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 6 "d - 1;" }}{PARA 12 "" 1 "" {XPPMATH 20 "6#\"\\q)eKR: " 0 " " {MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 48 "numer ical_form_of_another_attempted_decryption:=" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 45 "numerical_form_of_cipher_text&^(d - 1) mod n;" }} {PARA 12 "" 1 "" {XPPMATH 20 "6#>%Onumerical_form_of_another_attempted _decryptionG\"\\qzIeeHXS6dT.6%)y " 0 "" {MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 85 "another_attempted_original_text:=from_number( numerical_form_of_attempted_decryption);" }}{PARA 8 "" 1 "" {TEXT -1 97 "Error, (in from_number) there is NO meaningful text corresponding \+ to the number you have inputted" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 38 "And now let's try the other side of d:" }}{PARA 0 "" 0 " " {TEXT -1 0 "" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 6 "d + 1;" }}{PARA 12 "" 1 "" {XPPMATH 20 "6#\"\\q!fKR: " 0 "" {MPLTEXT 1 0 0 "" } }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 52 "numerical_form_of_yet_anot her_attempted_decryption:=" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 45 "numer ical_form_of_cipher_text&^(d + 1) mod n;" }}{PARA 12 "" 1 "" {XPPMATH 20 "6#>%Snumerical_form_of_yet_another_attempted_decryptionG\"\\qa7\\6 KR#fQ!G3>/tw=6Qo!=Q0M&3Y-FsDVAbK***eOX%)=lxD3%4z^#" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 37 "yet_another_attempted_original_text:=" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 64 "from_number(numerical_form_of_yet_another_attempted_d ecryption);" }}{PARA 8 "" 1 "" {TEXT -1 97 "Error, (in from_number) th ere is NO meaningful text corresponding to the number you have inputte d" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 41 " " }}{PARA 0 "" 0 "" {TEXT -1 83 "QUESTION: Wouldn't a decryption be possible if someone KNEW the values of p and q?" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 181 "ANSWER: Of course. Anyone who knew p and q (and who is familiar with the mathematics of calculating d from phi_n (namely (p - 1)*(q - 1)) would be immediately able to calculate d." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 96 "QU ESTION: So, isn't it just a question of recovering the values of p an d q from the value of n?" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 " " 0 "" {TEXT -1 393 "[Added afterwards: When I was planning this lectu re I had mentally allowed that I would only devote about five minutes \+ to section 1 - the 'private-key' period. To my horror I found that I s pent almost twenty minutes on it, and as a result I only got to this p oint after almost one hour. I decided not to try the patience of my au dience too much, and brought my lecture to an end at that point." }} {PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 172 "As I had printed the text, and made about fifty photocopies, I was able to giv e out texts to everyone who was interested (all my copies went, and I \+ had to post more later)." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 " " 0 "" {TEXT -1 73 "There followed a period of about forty minutes of \+ questions and answers.]" }}{PARA 0 "" 0 "" {TEXT -1 72 " \+ _____________________________" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 82 " \+ 5. Fundamental mathematical ideas for public-key." }} {PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 46 "It is onl y possible to touch briefly on these." }}{PARA 0 "" 0 "" {TEXT -1 0 " " }}{PARA 0 "" 0 "" {TEXT -1 268 "Besides familarity with 'modular ari thmetic' (also known as 'clock' arithmetic, or 'congruences') and the \+ Euclidean algorithm and its 'extension', the key ideas involve the wor k of two famous mathematicians: Pierre de Fermat (1601-1667) and Leonh ard Euler (1707-1783)." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 69 "One of the very many wonderful discoveries that Ferm at made was this:" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 194 "Fermat's 'little' theorem: If p is any prime number an d a is any whole number that is NOT divisible by p, then the number a \+ to the power of (p-1), when divided by p, will leave remainder of 1." }}{PARA 0 "" 0 "" {TEXT -1 70 " \+ ______________________________" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }} {PARA 0 "" 0 "" {TEXT -1 37 "Some examples to help you understand:" }} {PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 158 "(1) Let p = 5 and a = 2, then (p-1) = 5-1 = 4, and so 2 to the power of 4 wil l leave 1 over when divided by 5: 2^4 = 16 = 5*3 + 1. So the remai nder is 1." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 171 "(2) Let p = 7 and a = 10, then (p-1) = 7-1 = 6, and so 10 to \+ the power of 6 will leave 1 over when divided by 7: 10^6 = 1000000 = 7*142857 + 1. So the remainder is 1." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 62 "You should verify some examples for \+ yourself in your own time." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 62 "Let's just quickly see some examples with much la rger numbers:" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 28 "p:=nextprime(1234564264327);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"pG\".zVEkXB\"" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 " " 0 "" {TEXT -1 54 "And now I'll choose an 'a' that is NOT divisible b y p:" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 14 "a:=8675645534;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"aG\"+Mbkv' )" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 91 "And now let us check to see what remainder a to the power of (p-1) leaves on division by p :" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 17 "a&^(p - 1) mod p;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#\"\"\"" }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 37 "And the next number after a is (a+1):" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 19 "(a+1)&^(p-1) mod p;" }}{PARA 11 "" 1 "" {XPPMATH 20 " 6#\"\"\"" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 31 "But let m e just show you these:" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "> \+ " 0 "" {MPLTEXT 1 0 42 "30&^10 mod 11; # here p = 11 and a = 30." }} {PARA 11 "" 1 "" {XPPMATH 20 "6#\"\"\"" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 59 "31&^10 mod 11; # p is still 11, but I've changed a \+ to 31." }}{PARA 11 "" 1 "" {XPPMATH 20 "6#\"\"\"" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 59 "32&^10 mod 11; # p is still 11, but I've ch anged a to 32." }}{PARA 11 "" 1 "" {XPPMATH 20 "6#\"\"\"" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 59 "33&^10 mod 11; # p is still 11, b ut I've changed a to 33." }}{PARA 11 "" 1 "" {XPPMATH 20 "6#\"\"!" }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 102 "The remainder has now co me to be 0, because - as you see - the value of a (33) IS now divisibl e by 11." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 256 "Fermat discovered this beautiful theorem in connection with his w ork on primes of the form (2^n - 1) (the subject of my other public le cture, on the recently discovered record prime 2^1257787 - 1), but he \+ was unable to give a proof that it was always true." }}{PARA 0 "" 0 " " {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 209 "The first proof was gi ven by Euler (there were many subsequent ones - including one of my ow n in 1966 for the special case when a = 2), and it was he who went on \+ to give a 'generalization' of Fermat's theorem:" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 402 "Euler's generalization o f Fermat's 'little' theorem: If n is any whole number greater than 1 \+ (prime or not) and a is any whole number such that a and n are NOT bot h divisible by any whole number greater than 1, then there is a whole \+ number WHOSE VALUE DEPENDS ONLY ON THE NUMBER n itself (which Euler ca lled phi_n) such that the number a to the power of phi_n will leave re mainder 1 when divided by n." }}{PARA 0 "" 0 "" {TEXT -1 74 " \+ _________________________________" }} {PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 64 "When n is itself a prime (the Fermat case), then phi_n = n - 1. " }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 70 "But when n is NOT a \+ prime it is NO longer the case that phi_n = n - 1." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 312 "For example: Let n = 4 ( the very first example of a NON-PRIME greater than 1); then n - 1 = 3. Now, choosing a = 7, we have a and n are NOT both divisible by any wh ole number greater than 1. And now let us calculate 7 (namely a) to th e power of n - 1 (namely 3), to see what remainder it leaves on divisi on by n:" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 87 "7^3 = 7*7*7 = 49*7 = 343 = 4*85 + 3, so it leaves 3 (and NOT 1) ov er when divided by 4." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 51 "I could give infinitely many similar examples ... ." } }{PARA 0 "" 0 "" {TEXT -1 76 " \+ ____________________________________" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 64 "So, QUESTION: WHAT is the value of phi _n when n is NOT a prime?" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 " " 0 "" {TEXT -1 97 "Euler was able to give a COMPLETE answer to this, \+ but I am going to limit myself to the following" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 407 "PARTIAL ANSWER: When a \+ number is NOT a prime then there are an INFINITE number of different p ossible shapes that it might have. It could be the product of two pri mes (which might be different or not: 15 = 3*5, 49 = 7*7, etc); it cou ld be the product of three primes (which might be different or not: 42 = 2*3*7, 12 = 2*2*3, 125 = 5*5*5, etc); it could be the product of fo ur (five, six, ... ) primes ... ." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }} {PARA 0 "" 0 "" {TEXT -1 188 "In the simplest possible case - when n i s the product of two DIFFERENT primes, p and q - Euler discovered, and was able to prove, that the value of phi_n was (p - 1)*(q - 1). So, \+ we have:" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 438 "The simplest case of Euler's generalization of Fermat's 'little' \+ theorem: Let p and q be any two DISTINCT primes, and let phi_n = (p - 1)*(q - 1). Let a be any whole number such that a and n are NOT bot h divisible by any whole number greater than 1 (and it can be shown th at that is EQUIVALENT to saying that a is NOT divisible by p, and a is NOT divisible by q). Then a to the power of phi_n will leave remaind er 1 when divided by n." }}{PARA 0 "" 0 "" {TEXT -1 79 " \+ ________________________________" }} {PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 373 "An examp le to help you gain some understanding: Let p = 3 and q = 5, and set n = p*q = 3*5 = 15. Then phi_n = phi_15 = (3 - 1)*(5 - 1) = 2*4 = 8. L et us choose a = 4. Then a (4) and n (15) are NOT both divisible by a ny whole number greater than 1, and we have: a^phi_n = 4^8 = 4*4*4*4*4 *4*4*4 = 65536 = 15*4369 + 1, and so leaves remainder 1 on division by 15 (namely n)." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 49 "You should do some similar examples for yourself." }} {PARA 0 "" 0 "" {TEXT -1 76 " _ ___________________________________" }}{PARA 0 "" 0 "" {TEXT -1 0 "" } }{PARA 0 "" 0 "" {TEXT -1 148 "It is this special case of Euler's theo rem (the two distinct primes case) that underpins the Rivest, Shamir a nd Adleman cryptographic protocol ... ." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 548 "According to an article in the Apri l 1995 issue of 'Math Horizons' (available from Mathematical Associati on of America at: 1529 Eighteenth Street, N.W., Washington, D.C., 2003 6), on reading the Diffie-Hellman paper, Rivest and Shamir (of MIT) st arted to work on attempting a realization of the public-key idea. At \+ that time they had a new colleague, Adleman. Rivest and Shamir would \+ come up with a proposal, pass it on to Adleman, and he would find a fl aw in it ... . Their forty-third proposal was the now famous RSA crypt ographic protocol ... ." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 65 " RECOMMENDED READING LIST" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 158 "Besides the original papers mentioned above (which a goo d library could obtain for you), a basic list would be vast, and so I \+ limit my list to just two books:" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }} {PARA 0 "" 0 "" {TEXT -1 21 "1. Title: Cryptology" }}{PARA 0 "" 0 "" {TEXT -1 35 " Author: Albrecht Beutelspacher" }}{PARA 0 "" 0 "" {TEXT -1 62 " Publisher: The Mathematical Association of America ( 1994)" }}{PARA 0 "" 0 "" {TEXT -1 24 " ISBN: 0-88385-504-6" }} {PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 86 "[ This is a sound basic text, and covers the history from Caesar up to modern t imes. ]" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 35 "2. Title: PGP: Pretty Good Privacy" }}{PARA 0 "" 0 "" {TEXT -1 29 " Author: Simson Garfinkel" }}{PARA 0 "" 0 "" {TEXT -1 50 " \+ Publisher: O'Reilly & Associates, Inc. (1995)" }}{PARA 0 "" 0 "" {TEXT -1 24 " ISBN: 1-56592-098-8" }}{PARA 0 "" 0 "" {TEXT -1 0 " " }}{PARA 0 "" 0 "" {TEXT -1 191 "[ The best recommendation for this b ook is surely that of Phil Zimmerman's (the creator of PGP), who said of it: \"I even learned a few new things about PGP from Simson's info rmative book.\" ]" }}{PARA 0 "" 0 "" {TEXT -1 41 " \+ " }}{PARA 0 "" 0 "" {TEXT -1 455 "Both these book s have extensive bibliographies, and Garfinkel's book includes many us eful e-mail addresses (e.g. for the Electronic Privacy Information Cen ter (US spelling) and the Electronic Frontier Foundation. Both these \+ organisations issue regular free documents on legal and political issu es relating to cryptography, and are obtainable by e-mail subscription ), Web addresses of Usenet newsgroups, and Web addresses for 'ftp-ing' free copies of PGP " }}{PARA 0 "" 0 "" {TEXT -1 9 "software." }} {PARA 0 "" 0 "" {TEXT -1 76 " \+ __________________________________" }}}}{MARK "0 0 0" 10 }{VIEWOPTS 1 1 0 1 1 1803 }