diff options
Diffstat (limited to 'crypto/src/math/ec/rfc8032')
| -rw-r--r-- | crypto/src/math/ec/rfc8032/Ed25519.cs | 49 | ||||
| -rw-r--r-- | crypto/src/math/ec/rfc8032/Ed448.cs | 56 |
2 files changed, 52 insertions, 53 deletions
diff --git a/crypto/src/math/ec/rfc8032/Ed25519.cs b/crypto/src/math/ec/rfc8032/Ed25519.cs index 8f87e3a5a..a50fdda02 100644 --- a/crypto/src/math/ec/rfc8032/Ed25519.cs +++ b/crypto/src/math/ec/rfc8032/Ed25519.cs @@ -66,6 +66,7 @@ namespace Org.BouncyCastle.Math.EC.Rfc8032 private const int WnafWidthBase = 7; + // ScalarMultBase is hard-coded for these values of blocks, teeth, spacing so they can't be freely changed private const int PrecompBlocks = 8; private const int PrecompTeeth = 4; private const int PrecompSpacing = 8; @@ -691,13 +692,6 @@ namespace Org.BouncyCastle.Math.EC.Rfc8032 return r; } - private static void PointCopy(PointAffine p, PointAccum r) - { - F.Copy(p.x, 0, r.x, 0); - F.Copy(p.y, 0, r.y, 0); - PointExtendXY(r); - } - private static void PointCopy(PointExt p, PointExt r) { F.Copy(p.x, 0, r.x, 0); @@ -785,16 +779,6 @@ namespace Org.BouncyCastle.Math.EC.Rfc8032 F.CNegate(sign, r.t); } - private static void PointLookup(int[] table, int index, PointExt r) - { - int off = F.Size * 4 * index; - - F.Copy(table, off, r.x, 0); off += F.Size; - F.Copy(table, off, r.y, 0); off += F.Size; - F.Copy(table, off, r.z, 0); off += F.Size; - F.Copy(table, off, r.t, 0); - } - private static int[] PointPrecompute(PointAffine p, int count) { Debug.Assert(count > 0); @@ -1136,46 +1120,41 @@ namespace Org.BouncyCastle.Math.EC.Rfc8032 uint[] n = new uint[ScalarUints]; DecodeScalar(k, 0, n); - Debug.Assert(0U == (n[0] & 7)); - Debug.Assert(1U == n[ScalarUints - 1] >> 30); - - Nat.ShiftDownBits(ScalarUints, n, 3, 1U); - // Recode the scalar into signed-digit form { uint c1 = Nat.CAdd(ScalarUints, ~(int)n[0] & 1, n, L, n); Debug.Assert(c1 == 0U); - uint c2 = Nat.ShiftDownBit(ScalarUints, n, 0U); Debug.Assert(c2 == (1U << 31)); + uint c2 = Nat.ShiftDownBit(ScalarUints, n, 1U); Debug.Assert(c2 == (1U << 31)); } - Debug.Assert(1U == n[ScalarUints - 1] >> 28); - int[] table = PointPrecompute(p, 8); PointExt q = new PointExt(); - // Replace first 4 doublings (2^4 * P) with 1 addition (P + 15 * P) - PointCopy(p, r); - PointLookup(table, 7, q); - PointAdd(q, r); + PointSetNeutral(r); - int w = 62; + int w = 63; for (;;) { PointLookup(n, w, table, q); PointAdd(q, r); - PointDouble(r); - PointDouble(r); - PointDouble(r); - if (--w < 0) break; - PointDouble(r); + for (int i = 0; i < 4; ++i) + { + PointDouble(r); + } } } private static void ScalarMultBase(byte[] k, PointAccum r) { + // Equivalent (but much slower) + //PointAffine p = new PointAffine(); + //F.Copy(B_x, 0, p.x, 0); + //F.Copy(B_y, 0, p.y, 0); + //ScalarMult(k, p, r); + Precompute(); uint[] n = new uint[ScalarUints]; diff --git a/crypto/src/math/ec/rfc8032/Ed448.cs b/crypto/src/math/ec/rfc8032/Ed448.cs index e0478af9f..2cde2d74c 100644 --- a/crypto/src/math/ec/rfc8032/Ed448.cs +++ b/crypto/src/math/ec/rfc8032/Ed448.cs @@ -69,9 +69,11 @@ namespace Org.BouncyCastle.Math.EC.Rfc8032 private const int WnafWidthBase = 7; + // ScalarMultBase supports varying blocks, teeth, spacing so long as their product is in range [449, 479] private const int PrecompBlocks = 5; private const int PrecompTeeth = 5; private const int PrecompSpacing = 18; + private const int PrecompRange = PrecompBlocks * PrecompTeeth * PrecompSpacing; // 448 < range < 480 private const int PrecompPoints = 1 << (PrecompTeeth - 1); private const int PrecompMask = PrecompPoints - 1; @@ -705,6 +707,15 @@ namespace Org.BouncyCastle.Math.EC.Rfc8032 F.CNegate(sign, r.x); } + private static void PointLookup15(uint[] table, PointExt r) + { + int off = F.Size * 3 * 7; + + F.Copy(table, off, r.x, 0); off += F.Size; + F.Copy(table, off, r.y, 0); off += F.Size; + F.Copy(table, off, r.z, 0); + } + private static uint[] PointPrecompute(PointExt p, int count) { Debug.Assert(count > 0); @@ -763,6 +774,9 @@ namespace Org.BouncyCastle.Math.EC.Rfc8032 if (precompBase != null) return; + Debug.Assert(PrecompRange > 448); + Debug.Assert(PrecompRange < 480); + PointExt p = new PointExt(); F.Copy(B_x, 0, p.x, 0); F.Copy(B_y, 0, p.y, 0); @@ -1157,41 +1171,46 @@ namespace Org.BouncyCastle.Math.EC.Rfc8032 uint[] n = new uint[ScalarUints]; DecodeScalar(k, 0, n); - Debug.Assert(0U == (n[0] & 3)); - Debug.Assert(1U == n[ScalarUints - 1] >> 31); - - Nat.ShiftDownBits(ScalarUints, n, 2, 0U); - // Recode the scalar into signed-digit form { - uint c1 = Nat.CAdd(ScalarUints, ~(int)n[0] & 1, n, L, n); Debug.Assert(c1 == 0U); - uint c2 = Nat.ShiftDownBit(ScalarUints, n, 1U); Debug.Assert(c2 == (1U << 31)); + uint c1 = Nat.CAdd(ScalarUints, ~(int)n[0] & 1, n, L, n); + uint c2 = Nat.ShiftDownBit(ScalarUints, n, c1); Debug.Assert(c2 == (1U << 31)); + + // NOTE: Bit 448 is implicitly set after the signed-digit recoding } uint[] table = PointPrecompute(p, 8); PointExt q = new PointExt(); - PointLookup(n, 111, table, r); + // Replace first 4 doublings (2^4 * P) with 1 addition (P + 15 * P) + PointLookup15(table, r); + PointAdd(p, r); - for (int w = 110; w >= 0; --w) + int w = 111; + for (;;) { + PointLookup(n, w, table, q); + PointAdd(q, r); + + if (--w < 0) + break; + for (int i = 0; i < 4; ++i) { PointDouble(r); } - - PointLookup(n, w, table, q); - PointAdd(q, r); - } - - for (int i = 0; i < 2; ++i) - { - PointDouble(r); } } private static void ScalarMultBase(byte[] k, PointExt r) { + // Equivalent (but much slower) + //PointExt p = new PointExt(); + //F.Copy(B_x, 0, p.x, 0); + //F.Copy(B_y, 0, p.y, 0); + //PointExtendXY(p); + //ScalarMult(k, p, r); + Precompute(); uint[] n = new uint[ScalarUints + 1]; @@ -1199,7 +1218,8 @@ namespace Org.BouncyCastle.Math.EC.Rfc8032 // Recode the scalar into signed-digit form { - n[ScalarUints] = 4U + Nat.CAdd(ScalarUints, ~(int)n[0] & 1, n, L, n); + n[ScalarUints] = (1U << (PrecompRange - 448)) + + Nat.CAdd(ScalarUints, ~(int)n[0] & 1, n, L, n); uint c = Nat.ShiftDownBit(n.Length, n, 0); Debug.Assert(c == (1U << 31)); } |