Applied Security Seminar

Dec 6, 1999 3PM

Selecting Cryptographic Key Sizes

by Arjen Lenstra and Eric Verheul

paper released Nov 15, 1999

## Abstract:

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.

## Discussion:

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