Proceedings of Symposia in Applied Mathematics

Volume 62, 2005

Cryptographic Primitives

Paul Garrett

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.

1

© 2005 Paul Garrett

http://dx.doi.org/10.1090/psapm/062/2211870