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.)