diff options
author | Emilia Kasper <emilia@openssl.org> | 2016-04-29 19:19:58 +0200 |
---|---|---|
committer | Emilia Kasper <emilia@openssl.org> | 2016-05-05 18:51:53 +0200 |
commit | 0eadff033fea00f1b9abe0a83bf0d6637690f085 (patch) | |
tree | 4db67197d11dbea0ce2755dd06b3216ee641f3f0 /crypto/ec | |
parent | fb37410ee0cbda3c5b4a9fb48e67165e8f2c01c5 (diff) | |
download | openssl-0eadff033fea00f1b9abe0a83bf0d6637690f085.tar.gz |
Document inversion ladder in curve25519
This demystifies two for-loops that do nothing. They were used to write
the ladder in a unified way. Now that the ladder is otherwise commented,
remove the dead loops.
Reviewed-by: Matt Caswell <matt@openssl.org>
Reviewed-by: Rich Salz <rsalz@openssl.org>
Diffstat (limited to 'crypto/ec')
-rw-r--r-- | crypto/ec/curve25519.c | 53 |
1 files changed, 42 insertions, 11 deletions
diff --git a/crypto/ec/curve25519.c b/crypto/ec/curve25519.c index 3dbf4ac2ab..a7be5b8e94 100644 --- a/crypto/ec/curve25519.c +++ b/crypto/ec/curve25519.c @@ -670,60 +670,91 @@ static void fe_invert(fe out, const fe z) { fe t3; int i; + /* + * Compute z ** -1 = z ** (2 ** 255 - 19 - 2) with the exponent as + * 2 ** 255 - 21 = (2 ** 5) * (2 ** 250 - 1) + 11. + */ + + /* t0 = z ** 2 */ fe_sq(t0, z); - for (i = 1; i < 1; ++i) { - fe_sq(t0, t0); - } + + /* t1 = t0 ** (2 ** 2) = z ** 8 */ fe_sq(t1, t0); - for (i = 1; i < 2; ++i) { - fe_sq(t1, t1); - } + fe_sq(t1, t1); + + /* t1 = z * t1 = z ** 9 */ fe_mul(t1, z, t1); + /* t0 = t0 * t1 = z ** 11 -- stash t0 away for the end. */ fe_mul(t0, t0, t1); + + /* t2 = t0 ** 2 = z ** 22 */ fe_sq(t2, t0); - for (i = 1; i < 1; ++i) { - fe_sq(t2, t2); - } + + /* t1 = t1 * t2 = z ** (2 ** 5 - 1) */ fe_mul(t1, t1, t2); + + /* t2 = t1 ** (2 ** 5) = z ** ((2 ** 5) * (2 ** 5 - 1)) */ fe_sq(t2, t1); for (i = 1; i < 5; ++i) { fe_sq(t2, t2); } + + /* t1 = t1 * t2 = z ** ((2 ** 5 + 1) * (2 ** 5 - 1)) = z ** (2 ** 10 - 1) */ fe_mul(t1, t2, t1); + + /* Continuing similarly... */ + + /* t2 = z ** (2 ** 20 - 1) */ fe_sq(t2, t1); for (i = 1; i < 10; ++i) { fe_sq(t2, t2); } fe_mul(t2, t2, t1); + + /* t2 = z ** (2 ** 40 - 1) */ fe_sq(t3, t2); for (i = 1; i < 20; ++i) { fe_sq(t3, t3); } fe_mul(t2, t3, t2); - fe_sq(t2, t2); - for (i = 1; i < 10; ++i) { + + /* t2 = z ** (2 ** 10) * (2 ** 40 - 1) */ + for (i = 0; i < 10; ++i) { fe_sq(t2, t2); } + /* t1 = z ** (2 ** 50 - 1) */ fe_mul(t1, t2, t1); + + /* t2 = z ** (2 ** 100 - 1) */ fe_sq(t2, t1); for (i = 1; i < 50; ++i) { fe_sq(t2, t2); } fe_mul(t2, t2, t1); + + /* t2 = z ** (2 ** 200 - 1) */ fe_sq(t3, t2); for (i = 1; i < 100; ++i) { fe_sq(t3, t3); } fe_mul(t2, t3, t2); + + /* t2 = z ** ((2 ** 50) * (2 ** 200 - 1) */ fe_sq(t2, t2); for (i = 1; i < 50; ++i) { fe_sq(t2, t2); } + + /* t1 = z ** (2 ** 250 - 1) */ fe_mul(t1, t2, t1); + + /* t1 = z ** ((2 ** 5) * (2 ** 250 - 1)) */ fe_sq(t1, t1); for (i = 1; i < 5; ++i) { fe_sq(t1, t1); } + + /* Recall t0 = z ** 11; out = z ** (2 ** 255 - 21) */ fe_mul(out, t1, t0); } |