Title of talk

Bill Clinton, Bertie Ahern, and digital signatures
(A Maple-based introduction to public-key cryptography)

For David Joyner   (United States Naval Academy, Annapolis)

The Sixteenth Annual International Conference on
Technology in Collegiate Mathematics (ICTCM16)

Hyatt Regency O'Hare Hotel, Chicago, Illinois, USA

October 30 - November 2, 2003

John B. Cosgrave, Mathematics Department,
St. Patricks College, Drumcondra, Dublin 9, Ireland

email:       John.Cosgrave@spd.dcu.ie

website:    www.spd.dcu.ie/johnbcos

Abstract and time comment

Since 1995-96 I have taught a 3rd year undergraduate course   Number Theory and Cryptography  

( using Maple ) at St Patricks College. Before I had a web site (in June 1999), David Joyner at the United States Naval Academy (Annapolis) asked if I would allow my course Maple worksheets be displayed at their site; they are still there at:  

http://web.usna.navy.mil/~wdj/crypto.htm

Subsequently I published a fairly full outline of my 3rd year course in:

Number Theory and Cryptography  ( using Maple ) in David Joyner USNA (Ed.), Coding Theory and Cryptography: From Enigma to Geheimschreiber to Quantum Theory (Unites States Naval Academy Conference), Springer-Verlag, 2000, pp 124-143.

In September 1998 the U.S. President, Bill Clinton, and the Irish Prime Minister Bertie Ahern engaged in a 'historic, first digital signing of a treaty on e-commerce' - at Gateway 2000's Dublin plant (Gateway's then European headquarters), and using software produced by Baltimore, the Irish cyrptography company - between the U.S. and Irish governments, and in November 1998 I gave a public  lecture (using Maple) - Bill Clinton, Bertie Ahern, and digital signatures  - at my college, to explain the essential revolutionary  ideas of public-key cryptography , that lay behind our governments' signing. The Irish Times  - our leading daily newspaper - publicised my talk in advance, and invited me to contribute an explanatory article prior to my lecture (that article used to be freely available at the Times ' site, but unfortunately they now charge for access). That talk - which took me about 70 mins to deliver - is available in active Maple mws format, or in html format in the Public and Other Lectures corner of my web site.

Since November 1998 I have used that public lecture to introduce my course to my students: my aim has been to show just how much one can cover with a general public audience. My third year course then entails putting mathematical flesh  on that public lecture. My students have already studied Number Theory in their second year, that course consisting of three core areas: Congruences, the Euclidean Algorithm and its extension, and Fermat's 'little' theorem with applications, plus some other topics that I change from year to year.

Here in Chicago I offer a much revised version of my 1998 Clinton-Ahern talk to college mathematics faculty: e.g. the inclusion of the Pohlig-Hellman material is entirely new. No prior knowledge of Number Theory will be required to follow my talk, in which I will

• Briefly  explain  the difference between private- key and public -key cryptography
• Demonstrate  the Pohlig-Hellman private -key cryptographic method
• Demonstrate  a simplified element of the renowned Rivest-Shamir-Adleman   (RSA) public -key   cryptographic   method
• Illustrate  the relevance of the unsolved fast factorisation problem   to the security of the RSA method   (and, if I have time, also have a look at phi of n ...)

The core content of my 3rd year Number Theory and Cryptography course, my preparatory 2nd year Number Theory course, and related examination papers (3-hour written, 2-hour Maple, and one set of student Maple solutions) are all available at my web site: visit my home page and follow the obvious links.

A related paper of mine is: From divisibility by 6 to the Euclidean Algorithm and the RSA cryptographic method , The American Mathematical Association of Two-Year Colleges Review, Vol 19, No 1, Fall 1997, 38-45.

_______________

Time comment. Because of the amount of material I wish to cover, time constraints (45 minutes) dictate that I cannot devote as much time as I would wish even to sketchy mathematical details. The interested reader may, however, explore further, complete details of all the relevant mathematics at my web site.

In my talk, then, I will have to resort to a certain amount of hand-waving along the lines of:

• that computation used a method known as modular exponentiation using the square-and-multiply technique
• that computation used the Euclidean algorithm
• that computation used the extended  Euclidean algorithm
• what made that 'work' was Fermat's little theorem
• what made that 'work' was the 2-prime version of Fermat's little theorem (which is itself a special case of the   so-called Fermat-Euler theorem)
  
  etc

Cryptography, private and public-key. A limited  aim

Everyone has some rough idea that 'cryptography' is about disguising (encrypting) and recovering (decrypting) secret comminucation. It is used by governments, the military, big business, drugs barons, citizens, ...

(*The* outstanding general history reference is David Kahn's 1181 page The Codebreakers  (The Comprehensive History of Secret Communication from Ancient Times to the Internet), published by SCRIBNER , 1996 (2nd. new edition)   ISBN 0-684-83130-9. The excellent journal Cryptologia  - produced by the US Military Academy - treats the history of cryptography.)

A completely trivial - but nevertheless instructive - example to bear in mind is the so-called Caesar method  (evidently used by Julius Caesar): replace the intended text with a disguised text where every letter has been shifted 3 places cyclically in the alphabet. One receipt of the encrypted message one recovers   the original message by shifting backwards by 3 letters. Thus zebra encrypts   to  cheud decrypts to  zebra .

Before 1977 one needed to keep the encryption method secret (' private '!) otherwise   an 'enemy' who intercepted/eavesdropped the encrypted message could recover the original message.

Then, in 1977, a revolution  occured: the theoretical idea  of public-key cryptography - proposed by Diffie and Hellman in 1976 (in a nutshell they asked for an encryption method of such a nature that even if one knew  how the message had been encrypted, one could not decrypt the intercepted message in a reasonable time: many years)  - became a reality  within one year, with the work of Rivest, Shamir and Adelman.

I quote from David Kahn's PREFACE [1996] TO THE REVISED EDITION of his The Codebreakers :   "The need to revise this book existed even before it was published on September 27, 1967. I had written what I hoped would be the definitive history of the subject. I did not know at the time of such great matters as the Polish-British-American mastery   of the German Enigma cipher machine, which had such great effects on World Was II... Nor did I - or anyone else - know of things that had not yet been invented, such as public-key cryptography."

A painting  image that I use: Alice and Bob wish to communicate, and do so by using a paint and its related paint remover. Alice writes her message on a sheet, paints it over (encrypts), sends the painted sheet to Bob, who then removes the disguising paint using a coat of paint remover, and reads the underlying message. Clasically, Alice and Bob needed to keep their paints secret  (this is the essence of private-key cryptography), in the sense that some ill-minded chemist could  manufacture the second of the paints if s/he had access to the other.

In terms of that simple image, what Diffie-Hellman were asking for in 1976 - in terms of Alice and Bob - was this: could one create (and vary from time-to-time) paints publicAlice  ('public' in the sense that Alice doesn't   care  who has access to it) and privateAlice  ('private' in the sense that only Alice has access to it; more below) with these two properties:

1. A surface painted with privateAlice  (disguising the surface), and subsequently painted over with paint removing publicAlice , restores the original surface (and vice-versa, although I will not pursue that here).

2. No ill-minded chemist can realistically  (meaning: in years, say) manufacture privateAlice1  from publicAlice.

Note that in this simplified picture I have ignored  the possibility that an ill-minded interceptor could also read Alice's message if s/he had access to Alice's public paint; I am concentrating solely  on the verification that Alice is/was the author of the her message (in the 'real world' this requires the use of 'certification authorities'...)

In my 1998 Clinton-Ahern public lecture - with more time on hand - I illustrated how two parties may securely comminucate with each other using public-key cryptography. 'Securely' meaning that Alice and Bob may communicate with each other, knowing with certainty  that they are  each other, and that no ill-intentioned eaves-dropper may determine the content of their messages in a reasonable time...

Here my more modest aim is to illustrate how one party (Alice) may comminucate with another (Bob), so that Bob may feel certain  that the received message really has come  from Alice (she using her digital signature ).

(I leave it to you to ponder how Alice and Bob may securely communicate with each other so that both may know with certainty that each is the other, and no ill-intentioned eaves-dropper may determine the content of their messages in a reasonable time... You will find the details in my original, longer Clinton-Ahern talk.)

Converting text to number and number to text

Doing cryptography, we will

• convert text into numerical form according to an agreed convention
• disguise (encrypt) the resulting number
• the recipient will recover (decrypt) the original   number
• convert that number into the original  text

A convention  re ordering alphabetic and other symbols   ('a' followed by 'b', 'b' by 'c', etc. ):

This procedure converts a string of text into a number ('a' will be 01, 'b' will be 02, etc; finally   ` | ` will be 95):

Example ( Note  to anyone trying this: text must  be included within   backward quotes , ` and `).

Even junk text has a numerical form:

This recovers a string of text from a number:

No alphabetic element corresponds to 96, 97, 98, 99, nor 00:

Error, (in ln) numeric exception: division by zero

Notice the three colosely related:

Error, (in from_number) invalid range for string subscript

>

I can't resist insering this final example:

It's time to do some cryptography, private and public.

Pohlig-Hellman private -key. Rivest-Shamir-Adelman public-key.

For PH one needs:

1. a 'large' prime p

2. An integer ' e ' (the encryption power) such that gcd( e , ) = 1.  

3. An integer ' d ' (the decryption power) such that ed  leaves remainder 1   on division by   ( ).

In PH, ( e , p ) and ( d , p ) constitute the shared  'private-keys' (anyone who knows one of those keys may quickly calculate the other one, using the extended Euclidean algorithm).

Brief comments.

For a given ' p ' and 'e ' there is ONLY ONE such ' d ' between 1 and ( ).  

That ' d ' is quickly found by using the so-called extended Euclidean algorithm.

Requirement #3 is dictated by the mathematics of Fermat's so-called little  theorem (that's what I mean by hand waving...).

Without requirement #2, #3 could not even come into play...

For RSA one needs:

1. Two 'large' primes p  and q (in the real world , 'large' is not good enough, as I will demonstrate in a later section),      and then ' n ' - Alice's public modulus - is defined  by n = pq .

2. An integer ' e ' (the e ncryption power) such that gcd( e , ) = 1.
     That ' ' is ' ', the so called (Euler) phi-value of n , plays a fundamental  role...

3. An integer ' d ' (the d ecryption power) such that ed  leaves remainder 1 on division by .

In RSA, ( e , n ) is the public -key, while ( d , n ) is the private -key (and here the absolute crux  of the matter, the entire rock on which the whole system stands, is that someone who knows the public-key may NOT quickly quickly calculate the private one, providing  the constructor of the public modulus , ' n ', has done so with due   caution  (e.g., it is NOT enough merely to choose p  and q  to be 'large', as I will later demonstrate)

Brief comments.

For a given ' p ', ' q ', and 'e ' there is ONLY ONE such ' d ' between 1 and   .  

That ' d ' is quickly found - knowing   p  and q  (that ' knowing ' is a fundamental  point, and is the entire basis  for the security of the public-key method...) - by using the so-called extended Euclidean algorithm.

Requirement #3 is dictated by the mathematics of 2-prime case of Euler's generalization of Fermat's little  theorem (more hand waving...).

Again, without requirement #2, #3 could not even come into play...

A PH private -key demonstration

Suppose 'Alice' wishes to send the message ' Hi Bob, let's meet ' to 'Bob' using P-H. This is what they do:  

Here - just to let you see - is ed :

And see that ed  does leave remainder 1 on division by   ( ):

Next, Alice converts her message to a number:

Alice then encrypts that number (she lays on her coat of paint, as it were) by calculating the remainder (the least positive one) that     leaves   on division by p . I'll call the resulting number Asend , since it's that number Alice sends to Bob. That  is a remarkable  calculation, as I would like to demonstrate. First see how Maple   computes powers; I'll illustrate with  (which has 1003 digits;   in my live presentation I'll vary   that to   - which has 100,255 digits - but won't leave that output when placing this worksheet on my web site):

But see what happens if we try to compute   :

Error, numeric exception: overflow

Hardly a surprise, since  has billions upon billions of digits, and Maple can only compute powers up to a couple of million digits. It is something of a minor miracle  that one can quickly compute   the remainder that     leaves on division by p , without  computing   itself (the mathematics involved uses congruences ,   together with the so-called square-and-multiply method,   invoked by the '&' in the following Maple command):

In passing let us observe the text equivalent of that encrypted number; it is just meaningless junk (I may have to recompute with another 'p' should there be a '00' in that string in the wrong position):

And this is what Bob does to read Alice's message: he decrypts (he strips off the disuising coat of paint, as it were) by calculating the remainder (again the least positive one) that    leaves on division by p.  The   connection between e , d , and   ( )   in requirement #3, together with the mathematics of Fermat's   little   theorem (if p  is any prime, and a  is any integer not divisible by p , then    leaves remainder 1 on division by p ) -   gaurantees  that the outcome is the numerical form of the original  text:

Wonderful, yes?
(actually it's entirely elementary when you know the mathematics)

In responding to Alice, Bob may encrypt using either  power (of course in practice Alice and Bob should agree in advance on this), meaning that he may encrypt using the decryption power, as I'll quickly demonstrate:

Alice receives B_send, and then:

Two final, quick points:

• SECURITY.   It should be obvious that both Alice and Bob must keep their 'keys' - ( e , p ) and ( d , p ) - secret: anyone who knows  ( e , p ) may immediately compute d (using the extended Euclidean algorithm), or anyone who knows ( d , p ) may immediately compute e  
• SIZE OF TEXT.  If the numerical form (Anum or Bnum) of either text is greater than p , then it must  be broken down into numbers each having numerical value less than p  (think about that to see why...)

An RSA public -key ( digital signature ) demonstration

Here, with time as the enemy, I can only convey the essential   spirit  of the basic RSA idea.

Suppose 'Alice' wishes to send a message ("Hi Bob, let's meet. Alice") to Bob; then not only can she do so - in a manner similar to that you have already seen in the PH example - but she can give him a gaurantee  that she really is  the author of the message (her digital signature  comes into play here...)

Important note. Her message to him is NOT a secure  one, in the sense that anyone who intercepts her message, and who knows  her public -key, may then read her message to Bob. Also, although he can also send her a message (using her public-key) - perhaps 'Thanks Alice. Where? When? Bob' - she  however can have no  gaurantee that he  was the author, since some impostor  - knowing her public-key - could  have sent it.

(In case, as a novice, my reader objects along the lines of ' why bother with all of this public and private key stuff, why not just keep the keys secret and save a lot of bother... ', well that brings up a whole host of problems - not least the so-called transportation problem (how - in a crisis - can one securely deliver secret keys over a distance?) which I could not even begin to discuss here...)

First of all Alice chooses two 'large' primes (throwing caution to the winds):

forms their product (her public  modulus, which she will use with her private ' d ', constructed in a moment):

computes the 'Euler phi-value' of the integer nA  (that integer plays the same role in the RSA method as   ( )   did in the PH case, and I ask my reader to note the apparently trivial  remark that its calculation requires knowing  ' pA ' and ' qA ' ):

Next Alice chooses an encryption power:

Let's check if that the requirement gcd( eA , ( )( )) = 1 holds (there is only a very remote possibility that it doesn't, and I leave it to you to think about why  that is):

and computes her private -decryption power dA:

See in passing that the product of eA  and dA  does leave remainder 1 on division by   ( )( ):

Alice's public  and private  keys are then ( eA , nA ) and ( dA , nA )   (in the 'real world', a 'Certification Authority' is   the guarantor that ( eA , nA ) is her  'public-key').

Next, Alice converts her message to a number:

Alice then encrypts ANUM by using her private decryption  power ( that  is her digital signature ):

• She computes the remainder    leaves on division by n
  

I'll call the resulting number ASEND , since it's that number Alice sends to Bob.

Let us observe the text equivalent of that encrypted number is just meaningless junk; I may have to recompute with another ' n ' should there be a '00' in that string in the wrong position):

Bob then reads Alice's message by (removing the disuising coat of paint as it were, using Alice's public  paint):

• Computing the remainder that    leaves on division by n

The mathematics of two-prime version of Fermat's little  theorem gaurantees that the outcome is the numerical form of the original  text:

Two quick points, of which the first is fundamental :

• SECURITY.   Unlike the PH, private-key method, where the keys had to be kept secret, here Alice's private-key is safe  and secure , even though  her other key is allowed to be in the public domain. (The big question is: WHY?...  One might naively think as follows: knowing  ' n ' and ' e ', surely one could impersonate Alice by calculating ' d ' through factoring n , thus know ' p ' and ' q ', and so compute ' d ' from requirement #3 (as in the PH case). Ah!! There's the rub:
  
                                        FACTORING - IN GENERAL - IS HARD!!! )
  
• SIZE OF TEXT.  Here - as in the PH case - if the numerical form of the text is greater than n , then it must be broken down into sections each having numerical value less than n  (for a similar reason...)

The unsolved fast  factorization problem. RSA129 illustration

The problem of being able to perform certain calculations quickly is an enormous topic in Number Theory (a proper discussion of what 'quickly' means involves setting down precise definitions of concepts like, e.g., polynomial time ...) Here I will only remark that while, as you have actually seen:

• modular exponentiation (computing the remainder    leaves on division by m )
• the Euclidean algorithm (to compute greatest common divisor) and its extended form

may both be performed 'quickly' (indeed breath-takingly so; the Euclidean algorithm is considered one of the ten greatest algorithms in Mathematics),  BUT factoring (in general ) is currently a totally unknown barrier... There are individual factorization methods, each of which enjoys a certain limited success when applied to some numbers, but no single one that works quickly on any given candidate.
Here all that I can expect to do is to give you a flavour of what I mean, and to do so I will use a famous number known as RSA129:

It first came to public attention in Martin Gardiner's much read column in the August 1997 issue of the Scientific American . Rivest, Shamir and Adleman threw this number out as a challenge to be factored. Given the then state of mathematical knowledge (as far as factoring was concerned) and computer power, they estimated that it would take some 20,000 years to factor it, and thereby decrypt a message which used their specially constructed RSA129 as public modulus.
Briefly, a method known as the 'Quadratic Sieve' - introduced in 1981 by the US mathematician Carl Pomerance - together with thousands  of computers worldwide (organised by the Dutch mathematician Arjen Lenstra) - factored it by April 1994, and decrypted the RSA-encrypted message (which, incidentally, was: " The magic words are squeamish ossifrage. ")
Lenstra, and his co-workers found the two primes whose product was RSA129  to be the following 64-digit f1 and 65-digit f2:

Now, Maple has a command 'ifactor' (which, by default, uses the 1970's Brillhart-Morrison continued fraction method...). Here are some examples of its use:

But if I were to foolishly execute the command (which I have neutralized with the initial '#'):

the timer would stay on for MANY, MANY years ... (RSA129 does not fall quickly to the Brillhart-Morrison method).

Question.  So, it it just a matter of mere size?
Answer. No; size is only part  of the problem, and to illustrate that I will create a number  - which I will call by the name 'beyondRSA129' - as follows:

• it will be - like RSA129 itself - the product  of two primes   'P' and 'Q'
• I   will choose P to be f2 (the greater of the two primes whose product is RSA129)
• I will choose Q to be not much  greater than P (in fact I will choose it to be the very next prime after P itself)
  

Those choices automatically make 'beyondRSA129' be greater than RSA129 (hence the name).

That 130-digit number can be quickly factored by using an almost trivial method due to Fermat, and the idea behind it is simply this: 91 may be factored by trial-and-error by noting that

• 91 is not a perfect   square
• nor is   , namely 92
• nor is , namely 95,
• but ,   is   ,   giving    =  = 7*13

Even this crude procedure that I've written factors the above 130-digit number immediately:

1073816077130400819475486272224340785666856801858501936519539003127821295385023569561686898933064223684576642307425535503474310669, `is the product of`, 32769132993266709549961988190834461413177642967992942539798288533, `and`, 32769132993266709549961988190834461413177642967992942539798288793

That entirely success was however due to the arranged fact that the two primes - although both reasonably large - happened to be so relatively close to each other.  
Suppose, however, one choose them so that they were quite far apart? That's what I'm now going to do. This time I will make up another number - I will call it 'BEYONDRSA129' - as follows:

• it will be - like beyondRSA129 - the product  of two primes 'P1' and 'Q1'
• I will still choose P1 to be P
• I will now choose Q1 to be much  greater than P1

But that much larger  number can now be quickly  factored by doing this:

146481808053566948606112326494160580676597757390203425433760346556289969224977192583652803722778590707655656624536558761037114144280380743982554672552469432942539798288533, `is the product of`, 4470115461512684340891257138125051110076800700282905015819080092370422104067183317016903680000000000000001, `and`, 32769132993266709549961988190834461413177642967992942539798288533

WONDERFUL!!!  (I hope you agree...)

The mathematical ideas behind the success of that factorisation are due to an English mathematician, John Pollard (he lives outside Reading, and has a great interest in the music of Handel), and were published by him in 1974 in the Mathematical Proceedings of the Cambridge Philosophical Society, in a now famous paper. The method he develops there has become known as Pollard's  method, and with reason: i n that paper he expounds a very beautiful idea - which uses Fermat's little theorem - which enables one to factor a number, one of whose prime factors ' p ' is such   that  the number   has only relatively small  prime   factors.   That is why I was able so quickly to factor the number BEYONDRSA129. Look at how its prime factor Q1 is structured:

Can you guess what the number Q1 really is, given that I have let you see ?... See, however, the two prime factors - f1 and f2 - of the RSA129 number:

Rivest, Shamir and Adleman really knew  what they were doing in choosing their  two primes to make up their  129 digit number, RSA129...

A summary. The current security of the RSA method rests on the general difficulty of factorisation  ... . Besides the Pollard     method, there is also his rho- method (aka his Monte Carlo  method), and the Pomerance quadratic sieve method, and (Dutch mathematician) Hendrik Lenstra's elliptic curve  method, and the current dominant method: the Number Field Sieve method (introduced by Pollard, and added to by many others). The historic  creation by Agrawal, Kayal, and Saxena (India) in the summer of 2002 of a (long-sought) polynomial time algorithm for primality testing, has raised once again the possibility that someone, at some future date, may create such an algorithm for factoring (and, like A, K, and S) enter the history books...)

A bit of fun:

  (the Euler phi-value of n ), if I have time...

I would like to touch briefly  on that critical  "phi_n" ( my  notation above).    - the Euler phi function - came on the mathematical scene through Euler's classic generalization of Fermat's little theorem (I have devoted an entire section of my web site - with my personal year-2001 homage-lecture to mark the 400th anniversary of Fermat's birth - to that classic theorem):
Fermat's little  theorem. Let p  be prime, and a  be any integer not  divisible by p , then     leaves remainder 1 on division by p .

Euler's generalization of Fermat's theorem. Let n  be any natural number ( , prime or otherwise), and a  be any integer such that gcd( a , n ) = 1, then     leaves remainder 1 on division by n  (where  is the number of integers between 1 and   ( ) that share no common factor, greater than 1 , with n ).

Euler's beautiful formula for .     = n   , where the product   is evaluated over the distinct   prime divisors , ... of n .

Two examples only:

1. When n = p , is itself  a prime,    =  = ,  the ' ' of
    Fermat's little theorem.

2. When n = pq , the product of two distinct  primes,

   =  = ,  

     the ' ' of the RSA method.

Maple has a command for computing     (it requires loading Maple's Number Theory package; the items are alphabetically listed, and 'phi' is just after 'pdexpand')  

Warning, the protected name order has been redefined and unprotected

But what about, say:

Here NOW - I hope - you will see  the difference:

BUT FOR:

the computation clock comes on... Maple cannot  quickly compute    because - to do so - it needs to   factor  in order to find  and , to use Euler's formula to evaluate   , and here they have only 25 and 30 digits... That should explain to you why  earlier I had to define  'phi_nA'   (with the known  values of pA and qA) in the RSA demonstration: Maple could not  itself have carried out the computation had I used phi(nA)...

The two primary references, and a book recommendation

1. W. Diffie and M. E. Hellman, New directions in cryptography , IEEE Transactions on Information Theory IT-22 (1976), 644-654.

2. L. M. Adelman, R. L. Rivest and A. Shamir, A method for obtaining digital signatures and public-key cryptosystems , Communications of the ACM , 21 (1978), 120-126. (It made its way into the public domain the previous year)

______________________

If you don't already know of it - or do, but don't yet have a copy - then seek out In Code  ( A Mathematical Journey ) by remarkable young Irish woman Sarah Flannery, and her co-author father David Flannery (mathematician, and teacher extraordinaire). Check out (rave) reviews at the MAA and AMS web sites.