code review 253041: crypto/rsa: don't use safe primes.

crypto/rsa: don't use safe primes.

Previously we would require safe primes for our RSA key generation.
Since this took rather a long time, this removes the requirement that
the primes be safe.

OpenSSL doesn't use safe primes for RSA key generation either
(openssl-0.9.8l/crypto/rsa/rsa_gen.c:122)

Fixes issue 649.

[rsc, 2010-03-06 02:01:55]

LGTM

However, I am curious: does it help any to force
the two (not just one) low bits of the random choice to 1?
That would ensure that (p-1)/2 is odd, which would
be an easy factor of two.


On Fri, Mar 5, 2010 at 11:59,  <agl@golang.org> wrote:
> Reviewers: rsc,
>
> Description:
> crypto/rsa: don't use safe primes.
>
> Previously we would require safe primes for our RSA key generation.
> Since this took rather a long time, this removes the requirement that
> the primes be safe.
>
> OpenSSL doesn't use safe primes for RSA key generation either
> (openssl-0.9.8l/crypto/rsa/rsa_gen.c:122)
>
> Fixes issue 649.
>
> Please review this at http://codereview.appspot.com/253041/show
>
> Affected files:
>  M src/pkg/crypto/rsa/rsa.go
>  M src/pkg/crypto/rsa/rsa_test.go
>
>
> Index: src/pkg/crypto/rsa/rsa.go
> ===================================================================
> --- a/src/pkg/crypto/rsa/rsa.go
> +++ b/src/pkg/crypto/rsa/rsa.go
> @@ -18,16 +18,15 @@
>  var bigZero = big.NewInt(0)
>  var bigOne = big.NewInt(1)
>
> -// randomSafePrime returns a number, p, of the given size, such that p and
> -// (p-1)/2 are both prime with high probability.
> -func randomSafePrime(rand io.Reader, bits int) (p *big.Int, err os.Error) {
> +// randomPrime returns a number, p, of the given size, such that p is prime
> +// with high probability.
> +func randomPrime(rand io.Reader, bits int) (p *big.Int, err os.Error) {
>        if bits < 1 {
>                err = os.EINVAL
>        }
>
>        bytes := make([]byte, (bits+7)/8)
>        p = new(big.Int)
> -       p2 := new(big.Int)
>
>        for {
>                _, err = io.ReadFull(rand, bytes)
> @@ -42,10 +41,7 @@
>
>                p.SetBytes(bytes)
>                if big.ProbablyPrime(p, 20) {
> -                       p2.Rsh(p, 1) // p2 = (p - 1)/2
> -                       if big.ProbablyPrime(p2, 20) {
> -                               return
> -                       }
> +                       return
>                }
>        }
>
> @@ -157,12 +153,12 @@
>        totient := new(big.Int)
>
>        for {
> -               p, err := randomSafePrime(rand, bits/2)
> +               p, err := randomPrime(rand, bits/2)
>                if err != nil {
>                        return nil, err
>                }
>
> -               q, err := randomSafePrime(rand, bits/2)
> +               q, err := randomPrime(rand, bits/2)
>                if err != nil {
>                        return nil, err
>                }
> Index: src/pkg/crypto/rsa/rsa_test.go
> ===================================================================
> --- a/src/pkg/crypto/rsa/rsa_test.go
> +++ b/src/pkg/crypto/rsa/rsa_test.go
> @@ -18,7 +18,7 @@
>                t.Errorf("failed to open /dev/urandom")
>        }
>
> -       priv, err := GenerateKey(urandom, 32)
> +       priv, err := GenerateKey(urandom, 1024)
>        if err != nil {
>                t.Errorf("failed to generate key")
>        }
>
>
>

[agl1, 2010-03-08 14:25:22]

Hello rsc (cc: golang-dev@googlegroups.com),

I'd like you to review this change.

[agl1, 2010-03-08 14:25:33]

*** Submitted as http://code.google.com/p/go/source/detail?r=596599038dd4 ***

crypto/rsa: don't use safe primes.

Previously we would require safe primes for our RSA key generation.
Since this took rather a long time, this removes the requirement that
the primes be safe.

OpenSSL doesn't use safe primes for RSA key generation either
(openssl-0.9.8l/crypto/rsa/rsa_gen.c:122)

Fixes issue 649.

R=rsc
CC=golang-dev
http://codereview.appspot.com/253041

[agl1, 2010-03-08 14:29:23]

On Fri, Mar 5, 2010 at 9:01 PM, Russ Cox <rsc@golang.org> wrote:
> However, I am curious: does it help any to force
> the two (not just one) low bits of the random choice to 1?
> That would ensure that (p-1)/2 is odd, which would
> be an easy factor of two.

You're right that both LSBs should be forced to one but the code was
an order of magnitude too slow when using safe primes, not just a
factor of 2x.

I think it's also just a vestigial habit now: modern factorisation
methods don't depend on the size of the prime factors of p-1 and p+1
which is probably why OpenSSL doesn't bother.


Cheers

AGL