[cryptography] Duplicate primes in lots of RSA moduli

Nico Williams nico at cryptonector.com
Wed Feb 15 19:18:15 EST 2012

On Wed, Feb 15, 2012 at 5:57 PM, Peter Gutmann
<pgut001 at cs.auckland.ac.nz> wrote:
> Alexander Klimov <alserkli at inbox.ru> writes:
>>While the RSA may be easier to break if the entropy during the key
>>*generation* is low, the DSA is easier to break if the entropy during the key
>>*use* is low. Obviously, if you have access only to the public keys, the first
>>issue is more spectacular, but usually a key is used more often than generated.
> My thoughts exactly, I've always stayed away from DLP-based PKCs (except DH)
> because they're extraordinarily brittle, with RSA you have to get entropy use
> right just once, with DLP PKCs you have to get it right every single time you
> use them.  For embedded systems in particular that's just too risky.

Of course, if you're doing RSA key transport and the client selects
the key and has little or no entropy then the client still has a
problem (and the server may not know).

Most cryptographic protocols call for random keys, nonces,
confounders, IVs, and so on somewhere.  Typically the security of the
system depends to a large degree, if not entirely, on those random

What can you do with RSA keys if you can't generate good entropy?  You
can sign.  What else?  You can encrypt  messages small enough that
there's no need to generate a symmetric key for encrypting the message
(or you can chunk the message and encrypt each chunk).  Oh, there is
one thing one can do with RSA keys but without good enough entropy:
one can *ask* a remote system for entropy (the remote system encrypts
some entropy in the client's RSA public key, then signs this in the
server's public key) -- much better than having no good entropy at


More information about the cryptography mailing list