Re: Public Key Break Paper
John Young,
In early April we posted a message which referred to William H. Payne's paper "Public Key Cryptography is Easy to Break."
Mr. Payne has provided the 1990 5-page draft paper along with other documents, which we've added to the file at:
The paper is part of several attachments supporting Mr. Payne's charge against Sandia National Laboratory. Other documents in the file help explain why the paper is sensitive to SNL and perhaps to NSA.
I was curious to see this paper, since it would be an earth-shattering result if true, but unsurprisingly it is not as amazing as it sounds. First, it is not a general attack on public key cryptography, but rather it is a specific method for attacking RSA. Second, I remember seeing this algorithm discussed on sci.crypt in the past, probably in 1996. I don't know if it came from this same guy or if somebody else (re)discovered it. But the discussion there indicated that the algorithm was not as efficient as claimed. The claim is that it takes an amount of work proportional to the number of bits in the modulus, which would indeed be a breakthrough. Actually I think it will take about (2^n)/n iterations, making it a very poor method (*). Third, it claims to break RSA without factoring, but actually the algorithm could be used to factor n. The algorithm gives you (p-1)(q-1) or a large factor thereof, and as discussed on sci.crypt a few months ago, this is enough to let you find p and q (through a tricky method whose details I don't remember!). Hal (*) The final string of 1's will be as long as the value of the phi(n) factor being found, which will be on the order of 2^n, so there will be about 2^n 1's in the final string, more than there are atoms in the universe for numbers of interest. (You don't have to store the whole string though.) Each iteration adds at most n bits to the string, so the number of iterations must be as above.
participants (1)
-
Hal Finney