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

2006-04-08 Thread Max
Yet another paper on the topic:

Deterministic Polynomial Time Equivalence of Computing the RSA Secret
Key and Factoring
by Jean-Sebastien Coron and Alexander May
http://eprint.iacr.org/2004/208

Max

-
The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]


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

2006-04-03 Thread Sean W. Smith
Dan Boneh had an interesting paper on this topic a few years back  
giving some evidence that that breaking RSA might in fact be easier  
than factoring.However, it defines breaking RSA as being able  
to DO the private-key operation, not as knowing the private key  
(because the latter lets you factor).


Boneh and Venkatesan. Breaking RSA may not be equivalent to  
factoring. Eurocrypt '98. Springer-Verlag LNCS 1233. 1998.


--Sean

Sean W. Smith, Ph.D.  [EMAIL PROTECTED]  www.cs.dartmouth.edu/~sws/
Department of Computer Science, Dartmouth College, Hanover NH USA




-
The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]


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

2006-04-02 Thread Travis H.
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?
--
Security Guru for Hire http://www.lightconsulting.com/~travis/ --
GPG fingerprint: 9D3F 395A DAC5 5CCC 9066  151D 0A6B 4098 0C55 1484

-
The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]


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

2006-04-02 Thread Taral
On 4/2/06, Travis H. [EMAIL PROTECTED] 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.

This implication runs both ways. Given d and e (and pq), one can
compute p and q. Proving this is an exercise left to the reader.

--
Taral [EMAIL PROTECTED]
You can't prove anything.
-- Gödel's Incompetence Theorem

-
The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]


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

2006-04-02 Thread 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 [EMAIL PROTECTED]