Re: Breaking RSA & Securing RSA

From: Pubkeybreaker (Robert_silverman_at_raytheon.com)
Date: 07/11/05 

Date: 11 Jul 2005 07:18:15 -0700

Michael Scott wrote:

> I wonder has this ever been completely analysed.

Yes, it has. See my joint paper with Sam Wagstaff Jr.
"A Practical Analysis of the Elliptic Curve Factoring Algorithm".

I agree that RSA with
> two 512-bit primes, its fine to just pick random primes. But at a lower
> security levels, using say a pair of random 256-bit primes, could the
> p-1 factorisation method be faster than quadratic sieve based methods
> for a significant percentage of RSA public keys?

(1) Compare with NFS, not QS
(2) The answer is no. In over 30 years of trials with P-1, the largest
factor ever found was ~187 bits.

>Would p-1 be faster at
> any level of security?

On average? Not likely. I can split 20 digit composites with QS in ~10
milliseconds. I would expect P-1 to be much worse, on average.

For a small subset of randomly chosen small primes, the answer is yes.

Relevant Pages

  • Re: a problem in elementary number theory
    ... this technique can be applied on the test. ... So, I know the only primes I need to examines are 2, 3 and 5. ... Arguing as in my other threads, Fermat's Little Theorem and an observation of the even factors conclude the answer must be divisible ... The extra factor of 2 cannot come from p-1 or p+1 because exactly one of them is a multiple of 4. ...
    (sci.math)
  • Re: Surrogate factoring explained
    ... Meaning, all but the largest are very small (say 12 digits at most), and the ... parameters I believe the work needed to factor a 512-bit RSA moduli by p-1 ... One could also consider primes such that p+1 is smooth, ...
    (sci.crypt)
  • Re: Surrogate factoring explained
    ... Meaning, all but the largest are very small (say 12 digits at most), and the ... parameters I believe the work needed to factor a 512-bit RSA moduli by p-1 ... One could also consider primes such that p+1 is smooth, ...
    (sci.math)
  • Re: Why should the primes p and q be safe primes?
    ... >> Why should the primes p and q be safe primes (such that p-1 has a big ... > As far as I understand the situtation with RSA key sizes today it's not ...
    (sci.crypt)
  • Re: Breaking RSA & Securing RSA
    ... > There are strong primes... ... security levels, using say a pair of random 256-bit primes, could the ... p-1 factorisation method be faster than quadratic sieve based methods ... for a significant percentage of RSA public keys? ...
    (sci.crypt)