[2771] in cryptography@c2.net mail archive
Re: using deadbeef to reduce RSA key size
daemon@ATHENA.MIT.EDU (Anonymous)
Thu May 28 12:23:51 1998
Date: Thu, 28 May 1998 16:25:12 +0200 (MET DST)
From: Anonymous <nobody@REPLAY.COM>
To: cryptography@c2.net
> 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.
>
> 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?
I don't know whether it is safe or not. I don't think anyone would
be astonished to find that there was an attack against moduli which
ended with 383 bits of zero followed by a single 1 bit. That's a lot
of mathematical structure to give an attacker a foothold. Would you
want to be the one whose key got cracked because of this?
> 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?
Probably.
