Proceedings of Symposia in Applied Mathematics
Volume 62, 2005
ABSTRACT. An overview of cryptographic primitives, emphasizing public-key
(asymmetric) ciphers and fundamental algorithms from computational number
theory. Examples of protocol sketches.
A symmetric or private-key cipher is one in which knowledge of the en-
cryption key is explicitly or implicitly equivalent to knowing the decryption key.
An asymmetric or public-key cipher is one in which the encryption key is ef-
fectively public knowledge, without giving any useful information about the de-
cryption key. Until 30 years ago all ciphers were private-key. The very possibility
of public-key crypto did not exist until the secret work Ellis-Cocks-Williamson at
the UK's CESG-at-GCHQ in the 1960's, and public-domain work of Merkle, Diffie-
Hellman, and Rivest-Shamir-Adleman in the 1970's. Even more significant than
the secrecy achievable by public-key ciphers is the variety of effects achievable that
were (and continue to be) simply impossible with even the best symmetric-key ci-
phers. Key exchange and signatures (authentication) are the most notable among
well-established uses. Further examples are given in section 6.
Other articles in this volume address specific aspects of public-key cryptography
at greater length. D. Lieman's article [Lie] concerns refinements of protocols ap-
propriate to genuine practical implementations. N. Howgrave-Graham [HG] treats
proofs of security. J. Silverman's [Sil3] discusses elliptic curves. W. Whyte's [Wh]
and W.D. Banks' [Ba] articles consider the problem of designing faster cryptosys-
tems of various sorts. And I. Shparlinski [Shp2] discusses design and attacks upon
systems based upon various hidden-number problems. Given these, we will empha-
size algorithms related mostly to RSA, primality testing, and factoring attacks, as
opposed to discrete logs and/or elliptic curves, and give only simple naive forms of
protocol-ideas rather than refined forms.
By now there are many introductory texts on cryptography. Many of them are
reviewed in [L3].
1991 Mathematics Subject Classification. Primary 54C40, 14E20; Secondary 46E25, 20C20.
Key words and phrases. Cryptography, public key ciphers, RSA, trapdoor, Diffie-Hellman,
key exchange, signatures, zero-knowledge proofs, primes, factorization, primality testing, pseu-
doprimes, probable primes, computational number theory, complexity, probabilistic algorithms,
Monte Carlo methods, protocols, DES, AES, Rijndael.
© 2005 Paul Garrett