code review 5990045: crypto/rsa: fix Verify for multi-prime keys.

crypto/rsa: fix Verify for multi-prime keys.

The least common multiple is not totient/gcd.

[remyoudompheng, 2012-04-05 20:31:37]

http://codereview.appspot.com/5990045/diff/2001/src/pkg/crypto/rsa/rsa.go
File src/pkg/crypto/rsa/rsa.go (right):

http://codereview.appspot.com/5990045/diff/2001/src/pkg/crypto/rsa/rsa.go#new...
src/pkg/crypto/rsa/rsa.go:78: // Check that e and exponent(ℤ/nℤ) are coprime,
where exponent(ℤ/nℤ)=lcm(p-1,q-1,r-1,...).
why not check that de=1 mod (p-1) for each prime ?

* It implies that e is coprime to each p-1, hence to the lcm(p-1...)
* It implies that for all a coprime to n, a^de = 1 mod p, hence a^de =1 mod n.

The converse is also true. It would make the code mush easier to read, I think.

[agl1, 2012-04-06 16:41:11]

On Thu, Apr 5, 2012 at 1:31 PM,  <remyoudompheng@gmail.com> wrote:
> * It implies that e is coprime to each p-1, hence to the lcm(p-1...)

Agreed.

> * It implies that for all a coprime to n, a^de = 1 mod p, hence a^de =1
> mod n.

I'm afraid that I don't follow that.

Since we know that de ≡ 1 mod p-1, de = x*(p-1)+1, for some x.
Therefore a^de mod p = (a^(de-1) mod p) * a = (a^(x*(p-1)) mod p) * a
= 1 * a = a.

And so a^de ≡ a mod n

But, with that tweak, it does make the code easier to read, thanks!
See if you think that my comment is sufficient.


Cheers

AGL

[remyoudompheng, 2012-04-06 19:53:26]

Nice to see the code getting simpler :)

http://codereview.appspot.com/5990045/diff/4/src/pkg/crypto/rsa/rsa.go
File src/pkg/crypto/rsa/rsa.go (right):

http://codereview.appspot.com/5990045/diff/4/src/pkg/crypto/rsa/rsa.go#newcode81
src/pkg/crypto/rsa/rsa.go:81: // inverse. Therefore e is coprime to
lcm(p-1,q-1,r-1,...) =
I actaully think the story about the lcm is superfluous. It's enough to say that
a^de = a mod p for each p (hence mod n for a coprime to n).

http://codereview.appspot.com/5990045/diff/4/src/pkg/crypto/rsa/rsa.go#newcode89
src/pkg/crypto/rsa/rsa.go:89: gcd.GCD(nil, nil, de, pminus1)
are you sure you don't want gcd.Mod(de, pminus1) here (and call gcd
differently)?
checking that de is coprime to p-1 doesn't seem correct.

[agl1, 2012-04-06 21:48:20]

http://codereview.appspot.com/5990045/diff/4/src/pkg/crypto/rsa/rsa.go
File src/pkg/crypto/rsa/rsa.go (right):

http://codereview.appspot.com/5990045/diff/4/src/pkg/crypto/rsa/rsa.go#newcode81
src/pkg/crypto/rsa/rsa.go:81: // inverse. Therefore e is coprime to
lcm(p-1,q-1,r-1,...) =
On 2012/04/06 19:53:26, remyoudompheng wrote:
> I actaully think the story about the lcm is superfluous. It's enough to say
that
> a^de = a mod p for each p (hence mod n for a coprime to n).

You're right that this is superfluous in some sense, but the requirement that e
be coprime to lcm(p-1,q-1,...) is explicitly called out in PKCS#1 so I think I'd
like to leave this in here for completeness.

http://codereview.appspot.com/5990045/diff/4/src/pkg/crypto/rsa/rsa.go#newcode89
src/pkg/crypto/rsa/rsa.go:89: gcd.GCD(nil, nil, de, pminus1)
On 2012/04/06 19:53:26, remyoudompheng wrote:
> checking that de is coprime to p-1 doesn't seem correct.

(facepalm). Yep, I changed the argument and forgot to change the function. Done,
thanks.

[agl1, 2012-04-11 16:57:06]

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

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

[agl1, 2012-04-11 16:57:48]

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

crypto/rsa: fix Verify for multi-prime keys.

The least common multiple is not totient/gcd.

R=remyoudompheng
CC=golang-dev
http://codereview.appspot.com/5990045