Re: Prime magnitude and keys...a ?
If you can get the sign of the difference between RSA(your number) and RSA(unknown key), then you can discover (unknown key) in log n time. That implies, due to the nature of RSA, that you can factor in log n time using whatever algorithm it is that makes the determination of the sign of the difference.
No, again it will allow you to find the secret key, it will not provide any information about the factors of that number. It might be used for that but as you have pointed out, it takes a long time. If I can take a cypher-text and look at the periodicity of the mod function when several false keys are provided I can narrow down the guess through a binary search. I am going up, not down (ie finding the factors which must be smaller than n). I am looking for n, not its *@$^%# factors. You are asking the wrong question. I am asking, since I can't factor the keys is there some periodicity in the mod function that I can attack.
Jim choate says:
If you can get the sign of the difference between RSA(your number) and RSA(unknown key), then you can discover (unknown key) in log n time. That implies, due to the nature of RSA, that you can factor in log n time using whatever algorithm it is that makes the determination of the sign of the difference.
No, again it will allow you to find the secret key, it will not provide any information about the factors of that number.
The two are equivalent. Unfortunately, no amount of explanation will get that into your head. I've revised my thoughts on the matter over the weekend after scribbling on a pad for a few minutes -- it should be fairly straightforward to prove that if you can get the private key given the public key that you can factor arbitrary numbers. (This is not the equivalent of saying RSA can be broken only by factoring -- it is possible that there is an algorithm to get the plaintext given the public key and the ciphertext without first determining the private key.) Anyway, no one is interested any more, and most people are likely quite unhappy to have received so much unwanted flame mail about this, so I won't reply to Jim any further. Perry
participants (2)
-
Jim choate -
Perry E. Metzger