is breaking RSA at least as hard as factoring or vice-versa?

[Greg Rose]

At 1:41  -0600 2006/04/02, Travis H. wrote:
>So I'm reading up on unconditionally secure authentication in Simmon's
>"Contemporary Cryptology", and he points out that with RSA, given d,
>you could calculate e (remember, this is authentication not
>encryption) if you could factor n, which relates the two.  However,
>the implication is in the less useful direction; namely, that
>factoring n is at least as hard as breaking RSA.  As of the books
>publication in 1992, it was not known whether the decryption of almost
>all ciphers for arbitrary exponents e is as hard as factoring.
>
>This is news to me!  What's the current state of knowledge?

It's conceivable that there might be a way to decrypt RSA messages 
without knowing d. If you don't know d, you still can't factor n. 
Whereas if you can factor n, you can find d, and decrypt messages. So 
the problems are not equivalent, and the RSA problem might be easier 
than the integer factorization problem. (At least, the above is my 
understanding.)

Greg.

---------------------------------------------------------------------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majordomo at metzdowd.com