Re: cryptology, complexity, and quantum cryptology

From: Johan Wallen (johan.wallen+news_at_hut.fi)
Date: 02/16/05 

Date: Wed, 16 Feb 2005 10:08:25 +0200

Ralph Hartley <hartley@aic.nrl.navy.mil> writes:

> No one knows how to break RSA without doing the factoring problem, but to
> prove that breaking RSA is really as hard as factoring, by finding a
> reduction, would be very bad news.

Maybe not exactly what you (a generic `you', not a specific person)
are looking for, but you might want to check:
  
  Alexander May. Computing the RSA secret key is deterministic
  polynomial time equivalent to factoring. In Advances in
  Cryptology---CRYPTO 2004, volume 2152 of Lecture Notes in Computer
  Science, pages 213--219. Springer-Verlag, 2004.

  Abstract:
  We address one of the most fundamental problems concerning the RSA
  cryptoscheme: Does the knowledge of the RSA public key/ secret key
  pair (e,d) yield the factorization of N=pq in polynomial time? It is
  well-known that there is a probabilistic polynomial time algorithm
  that on input (N,e,d) outputs the factors p and q. We present the
  first deterministic polynomial time algorithm that factors N
  provided that e,d < \phi(N) and that the factors p, q are of the
  same bit-size. Our approach is an application of Coppersmith's
  technique for finding small roots of bivariate integer polynomials.
  
-- Johan

Relevant Pages

  • Re: cryptology, complexity, and quantum cryptology
    ... Alexander May. Computing the RSA secret key is deterministic ... polynomial time equivalent to factoring. ... well-known that there is a probabilistic polynomial time algorithm ...
    (sci.logic)
  • Re: cryptology, complexity, and quantum cryptology
    ... Alexander May. Computing the RSA secret key is deterministic ... polynomial time equivalent to factoring. ... well-known that there is a probabilistic polynomial time algorithm ...
    (sci.math)
  • Re: Proof factoring solution is closed form
    ... >> Whether your approach to factoring leads to anything remains to ... He has no idea what polynomial time is. ... >> The real test for you is, can you factor a sizeable RSA number? ...
    (sci.math)
  • Re: Proof factoring solution is closed form
    ... >> Whether your approach to factoring leads to anything remains to ... He has no idea what polynomial time is. ... >> The real test for you is, can you factor a sizeable RSA number? ...
    (sci.crypt)
  • Re: JSH: Ethics of a factoring solution
    ... When you post one of your solutions to the factoring problem there are ... Remember that I can find a solution to the RSA problem with a simple ... due warning and allowed time to change to a more secure method. ...
    (sci.crypt)