Large Primes

[Brian Gladman]

From: "Adrian Midgley" <akm@92tr.freeserve.co.uk>
To: <ukcrypto@chiark.greenend.org.uk>
Sent: Friday, August 16, 2002 8:45 PM
Subject: Re: Large Primes


How many bits should the key for a substantial narrative or summary piece of
a medical record be, in order to reasonably hope it will not be read within
the lifetime of the patient or the doctor concerned?

----------------------------------------------------------------------------
----------
There is no answer to this unless you accept that only known forms of attack
are considered. You also need to set very different lengths for symmetric
and asymmetric ciphers.

For symmetric ciphers there is a fairly simple answer if we assume:

(a) the cipher is perfect (it achieves the strength implied by its key
length), and
(b) Moore's law holds

In basic terms the cost of 'breaking' a symmetric cipher doubles for every
bit we add to its key and computing power doubles every 18 months or so.
So for every period of 18 months in the time over which we need protection
we need to add one bit to the key.

So to protect for, say, 30 years (20 18-month periods) we need to add 20
bits to whatever key length we consider safe now.   For 90 years we hence
need 60 bits on top of, say, 80 bits that are safe now, to make 140 bits in
total.  192 bit AES is hence reasonable but 256 bits might make sense - key
bits are pretty cheap these days.

However, protection over such very long periods involves other
considerations and it would make sense to encrypt with different ciphers in
sequence rather than rely on just one.

For asymmetric ciphers the situation is much more complex and the key
lengths are very dependent on which algorithm you use - RSA, DH, EC etc.

But taking RSA as an example and assuming that a 1024 bit key is safe now,
20 year protection would require a 2048 bit key and 50 year protection would
require a 4096 bit key (these are approximate figures).

But over such long time periods the biggest risk is that something
completely unknown will turn up and blow all these estimates out of the
water!

Here are some papers you might like to take a look at:

http://www.counterpane.com/keylength.pdf

http://www.cryptosavvy.com/Joc.pdf

   Brian Gladman