crypto/rsa: don't use safe primes. (issue253041)

[a...@golang.org]

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")
}

[Russ Cox]

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.

[Charlie Dorian]

You might also consider forcing the high bit to 1, so that it's an n
bit prime, rather than an n-m bit one, where m is the number of
initial zeros.

On Mar 5, 9:01 pm, Russ Cox <r...@golang.org> wrote:
> 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,  <a...@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 athttp://codereview.appspot.com/253041/show

[Russ Cox]

On Sat, Mar 6, 2010 at 04:42, Charlie Dorian <cldo...@gmail.com> wrote:
> You might also consider forcing the high bit to 1, so that it's an n
> bit prime, rather than an n-m bit one, where m is the number of
> initial zeros.

I think it does that already: bytes[0] |= 0x80.

Russ

[Adam Langley]

On Fri, Mar 5, 2010 at 9:01 PM, Russ Cox <r...@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