[cryptography] Duplicate primes in lots of RSA moduli

D. J. Bernstein djb at cr.yp.to
Thu Feb 16 17:47:10 EST 2012

> > 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.
> Just to make it clear, if you re-use the random input value to a DSA
> signature, you not only compromise the signature, you compromise the
> private key. In my opinion this makes DSA much more brittle then RSA
> (I wrote a paper about this for one of the early NDSS papers).

ObPlug: DSA certainly has this problem (as illustrated by the Sony PS3
disaster), but there are other discrete-log systems such as Ed25519---

---that completely eliminate this class of problems. There's no need for
any randomness after the initial key generation; the same message always
generates the same signature.

Ed25519 in particular uses just 32 bytes (256 bits) of randomness to
generate its key, and is deterministic after that. It's also reasonably
robust against deficiencies in these 256 bits: nothing goes wrong if,
e.g., the first 30% of the "random" bits are all replaced by 0, and the
system still isn't trivial to break if the first 70% of the "random"
bits are all replaced by 0.

There are of course more defenses that one can add to provide resilience
against more severe randomness deficiencies: one can start with more
random bits and hash them down to 256 bits; use repeated RDTSC calls as
auxiliary randomness input; etc. These details have essentially nothing
to do with the choice of cryptographic primitive, and the whole point of
/dev/urandom is to centralize these details and get them right rather
than having everybody reimplement them badly. It would be interesting to
understand how /dev/urandom failed for the repeated RSA primes---I'm
presuming here that /dev/urandom was in fact the main culprit.

---D. J. Bernstein
   Research Professor, Computer Science, University of Illinois at Chicago

More information about the cryptography mailing list