[cryptography] Running a keyserver is valuable OR pairwise attacks on public keys
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:
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 deﬁned by the combination of two private
polynomials. In this paper, we consider NTRU with two
different public keys deﬁned 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 coefﬁcients.
More information about the cryptography