Re: Problems With Public Key Cryptosystems

From: David Wagner (daw_at_taverner.cs.berkeley.edu)
Date: 07/14/04 

Date: Wed, 14 Jul 2004 16:19:27 +0000 (UTC)

Michael Barr wrote:
>Why does anyone even respond to this crock? The reason I am replying
>is to make the point that several years ago, Susan Landau wrote an
>article in the American Math. Monthly pointing out that there were a
>significant and constantly growing number of conditions on the prime
>factors you choose. Of the form that p-1 should not have certain
>small prime divisors. What was worrisome was that the more they look,
>the more such conditions there were. From which I inferred that you
>couldn't be sure that what seems safe today will be so tomorrow.

Actually, the number of conditions is shrinking. The bit about safe
primes, small divisors of p-1, etc., is now considered irrelevant; they
seem to have been an artifact of the old factoring algorithms. Today's
best factoring algorithms don't care whether p-1 has small factors, so
the advice today is just to generate a pair of primes uniformly at
random without worrying about special conditions.

Your conclusion is still right on, of course. We can't be sure that
what seems safe today will still be safe tomorrow.

Relevant Pages

  • Re: Problems With Public Key Cryptosystems
    ... Of the form that p-1 should not have certain ... >small prime divisors. ... >couldn't be sure that what seems safe today will be so tomorrow. ... seem to have been an artifact of the old factoring algorithms. ...
    (sci.crypt)
  • Re: El Gamal modulus question
    ... There are some attacks on discrete log which retrieve the exponent ... modulo small factors of p-1. ... far as practical security is concerned, knowing that you are safe is at ... It needs not be a generator for the whole Z* group. ...
    (sci.crypt)
  • Re: fooling primality tests
    ... "theoretically" provable algorithms with zero error. ... large prime factor [not a "safe prime" but essentially the same]. ... if P were 1028 bits then the largest factor of P-1 would be ... The algorithm is ...
    (sci.crypt)
  • Re: Problems With Public Key Cryptosystems
    ... the number of conditions is shrinking. ... The bit about safe ... > seem to have been an artifact of the old factoring algorithms. ...
    (sci.crypt)
  • Re: Problems With Public Key Cryptosystems
    ... the number of conditions is shrinking. ... The bit about safe ... > seem to have been an artifact of the old factoring algorithms. ...
    (sci.math)