code review 7002050: crypto/rsa: ensure that RSA keys use the full number of...

crypto/rsa: ensure that RSA keys use the full number of bits.

While half of all numbers don't have their most-significant bit set,
this is becoming increasingly impermissible for RSA moduli. In an
attempt to exclude weak keys, several bits of software either do, or
will, enforce that RSA moduli are >= 1024-bits.

However, Go often generates 1023-bit RSA moduli which this software
would then reject.

This change causes crypto/rsa to regenerate the primes in the event
that the result is shorter than requested.

It also alters crypto/rand in order to remove the performance impact
of this:

The most important change to crypto/rand is that it will now set the
top two bits in a generated prime (OpenSSL does the same thing).
Multiplying two n/2 bit numbers, where each have the top two bits set,
will always result in an n-bit product. (The effectively makes the
crypto/rsa change moot, but that seems too fragile to depend on.)

Also this change adds code to crypto/rand to rapidly eliminate some
obviously composite numbers and reduce the number of Miller-Rabin
tests needed to generate a prime.

[agl1, 2012-12-22 16:02:00]

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

I'd like you to review this change to
https://go.googlecode.com/hg/

[rsc, 2012-12-22 16:10:18]

LGTM

[minux1, 2012-12-22 21:06:33]

On Sun, Dec 23, 2012 at 12:02 AM, <agl@golang.org> wrote:

> Description:
> will always result in an n-bit product. (The effectively makes the
> crypto/rsa change moot, but that seems too fragile to depend on.)o
>
why is there a trailing o?

>
> Also this change adds code to crypto/util to rapidly eliminate some
>
it's crypto/rand/util.go. there is no such package as crypto/util.

> obviously composite numbers and reduce the number of Miller-Rabin
> tests needed to generate a prime.
>

[agl1, 2012-12-29 00:03:41]

On Sat, Dec 22, 2012 at 4:06 PM, minux <minux.ma@gmail.com> wrote:
>> will always result in an n-bit product. (The effectively makes the
>> crypto/rsa change moot, but that seems too fragile to depend on.)o
>
> why is there a trailing o?
>>
>>
>> Also this change adds code to crypto/util to rapidly eliminate some
>
> it's crypto/rand/util.go. there is no such package as crypto/util.
>>
>> obviously composite numbers and reduce the number of Miller-Rabin
>> tests needed to generate a prime.

Thanks for those. Will correct before landing.


Cheers

AGL

[agl1, 2012-12-29 00:12:30]

*** Submitted as https://code.google.com/p/go/source/detail?r=019884311591 ***

crypto/rsa: ensure that RSA keys use the full number of bits.

While half of all numbers don't have their most-significant bit set,
this is becoming increasingly impermissible for RSA moduli. In an
attempt to exclude weak keys, several bits of software either do, or
will, enforce that RSA moduli are >= 1024-bits.

However, Go often generates 1023-bit RSA moduli which this software
would then reject.

This change causes crypto/rsa to regenerate the primes in the event
that the result is shorter than requested.

It also alters crypto/rand in order to remove the performance impact
of this:

The most important change to crypto/rand is that it will now set the
top two bits in a generated prime (OpenSSL does the same thing).
Multiplying two n/2 bit numbers, where each have the top two bits set,
will always result in an n-bit product. (The effectively makes the
crypto/rsa change moot, but that seems too fragile to depend on.)

Also this change adds code to crypto/rand to rapidly eliminate some
obviously composite numbers and reduce the number of Miller-Rabin
tests needed to generate a prime.

R=rsc, minux.ma
CC=golang-dev
https://codereview.appspot.com/7002050