[cryptography] Running a keyserver is valuable OR pairwise attacks on public keys

Tom Ritter tom at ritter.vg
Thu Sep 8 23:46:30 EDT 2011


A long time ago I read an account on a website of a test done in the 90s
on public RSA keys.  A keyserver operator was politely asked for the
entire database of public keys, and he complied (I think it was the MIT
keyserver and the researchers were at MIT, but I don't recall.)

The public keys were all analyzed and compared efficiently pairwise
(computing the GCD I believe) to see if by some small chance a
factorization would occur.  And it did - I recall the website saying it
was a very strange scenario with one of the keys not actually being
correctly semiprime and having several small factors.

I was never able to find the website giving this account again.

But the idea seems to be coming back with this paper:
http://eprint.iacr.org/2011/477.pdf

NTRU is a fast public key cryptosystem presented
in 1996 by Hoffstein, Pipher and Silverman. It operates in
the ring of truncated polynomials. In NTRU, a public key
is a polynomial defined by the combination of two private
polynomials. In this paper, we consider NTRU with two
different public keys defined by different private keys. We
present a lattice-based attack to recover the private keys
assuming that the public keys share polynomials with a suitable
number of common coefficients.

-tom



More information about the cryptography mailing list