Shocking News About Public-Key Encryption

Some reputable researchers have discovered that in the real world thousands of different people have chosen numbers with common factors for encryption. A few of those relate back to the sad story of weak keys from the Debian GNU/Linux distro from a few years ago but most appear to be accidentally produced on systems with insufficient entropy. The result is thousands of keys can be broken with the straight forward/easy process of finding common factors, O((log2 uv)2), between different public keys rather than the hard process of factoring large numbers,
O( exp((64/9 bits)1/3) log(bits2/3)). There are millions of public keys published and thousands of them have this weakness, mostly RSA keys.

“Abstract. We performed a sanity check of public keys collected on the web. Our main goal was to test the validity of the assumption that diff erent random choices are made each time keys are generated. We found that the vast majority of public keys work as intended. A more disconcerting fi nding is that two out of every one thousand RSA moduli that we collected off er no security. Our conclusion is that the validity of the assumption is questionable and that generating keys in the real world for “multiple-secrets” cryptosystems such as RSA is signi cantly riskier than for “single-secret” ones such as ElGamal or (EC)DSA which are based on Diffie-Hellman.”

Their conclusion…
“The lack of sophistication of our methods and fi ndings make it hard for us to believe that what we have presented is new, in particular to agencies and parties that are known for their curiosity in such matters. It may shed new light on NIST’s 1991 decision to adopt DSA as digital signature standard as opposed to RSA, back then a “public controversy” (cf. [7]); but note the well-known nonce-randomness concerns for ElGamal and (EC)DSA (cf. Section 4.4) and what happens if the nonce is not properly used (cf. [6]).

Factoring one 1024-bit RSA modulus would be historic. Factoring 12720 such moduli is a statistic. The former is still out of reach for the academic community (but anticipated). The latter comes as an unwelcome warning that underscores the difficulty of key generation in the real world.”

see Ron was wrong, Whit is right

About Robert Pogson

I am a retired teacher in Canada. I taught in the subject areas where I have worked for almost forty years: maths, physics, chemistry and computers. I love hunting, fishing, picking berries and mushrooms, too.
This entry was posted in technology. Bookmark the permalink.

2 Responses to Shocking News About Public-Key Encryption

  1. oiaohm says:

    General rule of computer secuirty everything Fails. The only question is will you be alive to see it.

    Interesting would be to map out who has the insecure keys and trace back to a production method if able.

  2. twitter says:

    Debian has been using ElGamal / (EC)DSA for a number of years.

Leave a Reply