Applied Security Seminar
Dec 6, 1999 3PM

Selecting Cryptographic Key Sizes
by Arjen Lenstra and Eric Verheul
paper released Nov 15, 1999


In this article we offer guidelines for the determination of key sizes for symmetric cryptosystems, RSA, and discrete logarithm based cryptosystems both over finite fields and over groups of elliptic curves over prime fields. Our recommendations are based on a set of explicitly formulated hypotheses, combined with existing data points about the cryptosystems.


Although nearly most failures in security are due to protocol or password weaknesses, it is still worth examining secure key sizes.

What is the official definition of a MIPS year? There are several: one is mentioned in the paper under discussion. Interestingly, in reference 29 (R.D. Silverman, "Exposing the Mythical MIPS Year"), it was implied that MIPS is a bad measure for the purposes for which is is being used. There is a vast inconsistency among difference computers, source codes, and compilers. The measure seems to be dependent upon the program, rather than the machine being used. A possibly better metric may be a direct count of arithmetic instructions per second.

Space constraint may also be an important matter to address. For example, the speed of computing the number field sieve depends on memory retrieval speed, which in turn scales in terms of space as well as time. Another example is that the matrix computation in the breaking of the RSA key is done in parallel.

Elliptic curve systems, on known algorithms and known hardware, guarantee comparable security with smaller keys. Smaller keys allow faster encryption and decryption and lower-powered devices.

Question: How do we compare key-size security in a time & space model? Some factors involved: cost, value of data, length of time to be secured. The paper assumes that cost is zero because all the computation was done on borrowed screensaver time.

Brought to you by the MIT LCS Applied Security Reading Group