[2764] in cryptography@c2.net mail archive
using deadbeef to reduce RSA key size
daemon@ATHENA.MIT.EDU (Adam Back)
Wed May 27 21:00:44 1998
Date: Wed, 27 May 1998 23:44:22 +0100
From: Adam Back <aba@dcs.ex.ac.uk>
To: cryptography@c2.net
(The deadbeef attack[1] works by generating RSA public keys with chosen
trailing digits. For pgp 2.x keys you need to choose 32 bits for the
displayed keyid (or 64 bits for internally used keyid).)
Another use for the ability to generate public keys with chosen
trailing bits would be to standardise the trailing bits to be
"...00000000000001", which would reduce the size of the information
which must be published.
So for example if we had a 1024 bit RSA public key, we could set say
the 384 least significant bits to 383 0s followed by a 1.
There are still sufficient primes in the 2^128 numbers in the
resulting range, as the prime density is around 1/512[2] at that size,
leaving 2^119 primes to choose from which presents a much harder task
for brute force than that expected from factoring algorithms.
We could therefore represent a 1024 bit RSA public key in 640 bits (80
bytes rather than 128 bytes).
An alternative method of reducing the size would to have leading bits
set to 1. This method has the advantage of reducing statistical
leakage of the RSA key used in ciphertexts due to C being in the range
1 < C < n.
Is this safe? Is there a difference in security of setting leading
bits to 1 or trailing bits to a chosen value?
A related question is whether it is also safe to assume that anything
over 119 bits (or whatever) of entropy is wasted in generating the
primes. Ie. whether as much security could be obtained by starting
with 119 bits of entropy and spreading it to the required size by
hashing. Is this safe?
Adam
[1] I think first proposed by Greg Rose. Example method of choosing
trailing bits is to have target bits x, and set the least significant
bits of p to x, and q to "...000001". (Clearly x has to be odd).
[2] Approximate prime density is log(n) for numbers around the same
size as n
