Re: Problems With Public Key Cryptosystems

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

  • Next message: Gregory G Rose: "Re: Encryption key length (RC4 and Blowfish)" 
    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.

  • Next message: Gregory G Rose: "Re: Encryption key length (RC4 and Blowfish)"

    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.math)
    • 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)
    Loading