code review 94850043: crypto/rsa: Implement a big int modular exponentiat...

crypto/rsa: Implement a big int modular exponentiation algorithm using the
montgomery ladder, and make use of it in RSA. This should be closer to
constant time, and thus help avoid side-channel attacks.

[lvh_, 2014-04-28 18:25:20]

(You might be reading this message twice because I'm not used to Rietveld and it
looks like it ate the draft; my apologies :-))

Hi :-) I reviewed this (prior to the issue opening, in case anyone's wondering
about timing) and it LGTM.

It may be useful to add one more test case:

checkExpInt(t, 186, 186, 65537)

The exponent has high bits 0b10, so if you iterate from ``BitLen() - 1`` instead
of ``- 2`` this will blow up like so:

	montgomery_test.go:19: pow(186, 186, 65537) Expected: 31497, got 31859

The very large number test also has that structure, but without a more specific
test it just looks like it breaks once you have bignums of a certain size :-) (A
comment to that effect might be useful.)

It may also be worth considering putting the test constants in hex so that it's
marginally easier to look at the bit structure through visual inspection, but
that's a minor nit, really.

hth
lvh

[alex.gaynor, 2014-04-28 20:08:00]

Hello golang-codereviews@googlegroups.com, _@lvh.cc (cc: _@lvh.io,
golang-codereviews@googlegroups.com),

I'd like you to review this change to
https://code.google.com/p/go/

[alex.gaynor, 2014-04-28 20:08:40]

On 2014/04/28 18:25:20, lvh_ wrote:
> It may be useful to add one more test case:
> 
> checkExpInt(t, 186, 186, 65537)
> 
> The exponent has high bits 0b10, so if you iterate from ``BitLen() - 1``
instead
> of ``- 2`` this will blow up like so:
> 
> 	montgomery_test.go:19: pow(186, 186, 65537) Expected: 31497, got 31859
> 
> The very large number test also has that structure, but without a more
specific
> test it just looks like it breaks once you have bignums of a certain size :-)
(A
> comment to that effect might be useful.)
> 

I've added this test case

[gobot, 2014-04-29 14:42:17]

R=agl@golang.org (assigned by r@golang.org)

[agl1, 2014-04-30 01:37:06]

https://codereview.appspot.com/94850043/diff/40001/src/pkg/crypto/rsa/rsa.go
File src/pkg/crypto/rsa/rsa.go (right):

https://codereview.appspot.com/94850043/diff/40001/src/pkg/crypto/rsa/rsa.go#...
src/pkg/crypto/rsa/rsa.go:261: func montgomeryLadderExp(a, b, c *big.Int)
*big.Int {
A Montgomery Ladder is a method of implementing scalar multiplication on
elliptic curves using differential addition.

And this function is not constant-time. See something like
https://www.imperialviolet.org/2010/04/01/ctgrind.html. (Note: the underlying
Mul and Mod functions aren't constant time either.)

[lvh_, 2014-04-30 06:12:11]

Hi agl,


Right; it certainly doesn't implement a fully constant time algorithm yet; just
one with a constant number of mults, mods and squarings, as opposed to the
current implementation, which I believe is exponentiation by squaring.

While EC is the original use case for a Montgomery ladder, it can be extended to
any abelian group, see [Joye03].

[Joye03]: http://cr.yp.to/bib/2003/joye-ladder.pdf

hth
lvh

[gobot, 2014-05-25 21:11:13]

R=close (assigned by agl@golang.org)