Re: Weak keys for RSA ?

From: Bob Silverman (pubkeybreaker_at_aol.comstuff)
Date: 04/24/04 

Date: 24 Apr 2004 13:12:14 GMT

>Bob Silverman (who sometimes contributes here) had some
>clever ideas for how one might try to do that, but the whole
>approach has proved ineffective and worthless.
>

See:

Robert D. Silverman RSA Public Key Validation, Proc. 1999 Workshop Comp. No.
Theory & Cryptography, CCNT '99 Singapore, Birkhauser

I give zero knowledge proofs that if N = pq, then
p & q are nearly equal, that p-q is not small, that
ap - bq is not small for chosen integers a,b, and
that p,q are so-called strong primes. I also
outline how to guard against the Bach/Shallit
generalization of P+1 or P-1.

But these guard against purely exponential
factoring algorithms and do nothing to guard
against ECM or, of course GNFS. The only
way to guard against these latter is to make the
keys sufficiently large and generate them AT
RANDOM.

(the suite of)
Exponential algorithms are WORTHLESS as
attacks against 1024 bit RSA unless you suspect
that a key has been DELIBERATELY constructed
to be vulnerable to such an attack. It won't
happen by accident.

The whole idea of requiring strong primes in
standards was a marketing attack by RSA Security
competitors. Their purpose was to put as many
obstacles in the way as possible to ensure that
RSA encryption/decryption was not made into a
standard. It has ZERO technical merit.

Until I joined ANSI X9, noone there had any idea
of how to quickly generate RSA keys that were
built from so-called strong primes. Therefore, if
strong primes were required and it was very
hard to generate the keys, RSA was useless as
a standard. Unfortunately for those opposed to
RSA, it only took a little knowledge about prime
generation and the Chinese Remainder Thm. to
come up with a fast method for generating strong
primes. Poof. End of obstacle and digital sigs
using RSA became a standard shortly thereafter.
(ANSI X9.31) I tried arguing against strong primes,
but ther term itself seems to give some people a
warm fuzzy feeling.

What does have value is a Zero Knowledge Proof
that a key was randomly generated.

"You can lead a horse's ass to knowledge, but you can't make him think."

Relevant Pages

  • Re: Need RSA Encryption/Decryption Delays
    ... I have coded the Threshold RSA technique as given by Victor Shoup in ... The standard "Estimated Time to Completion" of a software project ... What is a "standard delay value"? ... or atleast the standard RSA delay values for different key size ...
    (sci.crypt)
  • Re: SF: Back to theory
    ... you could pick up a pile of RSA challenge checks ... those upset with my saying special primes, ... Now if mathematicians were honest, good folk, who are sensible, as some ... If surrogate factoring gets quietly developed, ...
    (sci.math)
  • Re: SF: Back to theory
    ... you could pick up a pile of RSA challenge checks ... those upset with my saying special primes, ... Now if mathematicians were honest, good folk, who are sensible, as some ... If surrogate factoring gets quietly developed, ...
    (sci.crypt)
  • Re: Pell equation X^2=d*Y^2+1 where d=RSA number
    ... I think i can easily push the size of d into the RSA range. ... primes from your set, and found that in every case Y has ... interesting that you aren't using continued fractions. ... The notation i'm using always has a common factor for y and d. ...
    (sci.math)
  • Re: Riemann Hypothesis and P vs NP
    ... > about cryptography with special emphasis on RSA. ... > chapter the author mentions P versus NP since factorising numbers is a ... > discover the primes used to build the RSA codes on which the security ...
    (comp.theory)
Loading