crypto/rsa: handle the case of non-coprime blinds.

crypto/rsa: handle the case of non-coprime blinds.

We are dealing with the multiplicative group ℤ/pqℤ. Multiples of
either p or q are not members of the group since they cannot have an
inverse. (Such numbers are 0 in the subgroup ℤ/pℤ.)

With p and q of typical size (> 512 bits), the probability of a random
blind [1..pq-1] being a multiple of p or q is negligible. However, in
the unit tests, much smaller sizes are used and the event could occur.

This change checks the result of the ext GCD and deals with this case.

It also increases the size of p and q in the unit test as a large
number of the keys selected were p, q = 227,169.

[agl1, 2009-11-15 00:50:13]

The tests in crypto/rsa use actual random numbers (/dev/urandom), rather than
pseudo random numbers that I usually use. That might have been a mistake. I'll
have a think.

[rsc, 2009-11-15 00:55:14]

LGTM

Is it possible to turn down the number of iterations?
On the 386, crypto/rsa is a noticeable pause, maybe
because package big has no hw support yet.

[rsc, 2009-11-15 04:38:03]

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

crypto/rsa: handle the case of non-coprime blinds.

We are dealing with the multiplicative group ℤ/pqℤ. Multiples of
either p or q are not members of the group since they cannot have an
inverse. (Such numbers are 0 in the subgroup ℤ/pℤ.)

With p and q of typical size (> 512 bits), the probability of a random
blind [1..pq-1] being a multiple of p or q is negligible. However, in
the unit tests, much smaller sizes are used and the event could occur.

This change checks the result of the ext GCD and deals with this case.

It also increases the size of p and q in the unit test as a large
number of the keys selected were p, q = 227,169.

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

Committer: Russ Cox <rsc@golang.org>