diff options
| -rw-r--r-- | crypto/src/math/ec/rfc7748/X25519.cs | 98 | ||||
| -rw-r--r-- | crypto/src/math/ec/rfc7748/X448.cs | 116 | ||||
| -rw-r--r-- | crypto/src/math/ec/rfc7748/X448Field.cs | 5 | ||||
| -rw-r--r-- | crypto/src/math/ec/rfc8032/Ed25519.cs | 702 | ||||
| -rw-r--r-- | crypto/src/math/ec/rfc8032/Ed448.cs | 532 |
5 files changed, 938 insertions, 515 deletions
diff --git a/crypto/src/math/ec/rfc7748/X25519.cs b/crypto/src/math/ec/rfc7748/X25519.cs index 1d581bb85..bf845d2f5 100644 --- a/crypto/src/math/ec/rfc7748/X25519.cs +++ b/crypto/src/math/ec/rfc7748/X25519.cs @@ -12,6 +12,8 @@ namespace Org.BouncyCastle.Math.EC.Rfc7748 public const int PointSize = 32; public const int ScalarSize = 32; + private class F : X25519Field {}; + private const int C_A = 486662; private const int C_A24 = (C_A + 2)/4; @@ -61,17 +63,17 @@ namespace Org.BouncyCastle.Math.EC.Rfc7748 private static void PointDouble(int[] x, int[] z) { - int[] A = X25519Field.Create(); - int[] B = X25519Field.Create(); - - X25519Field.Apm(x, z, A, B); - X25519Field.Sqr(A, A); - X25519Field.Sqr(B, B); - X25519Field.Mul(A, B, x); - X25519Field.Sub(A, B, A); - X25519Field.Mul(A, C_A24, z); - X25519Field.Add(z, B, z); - X25519Field.Mul(z, A, z); + int[] a = F.Create(); + int[] b = F.Create(); + + F.Apm(x, z, a, b); + F.Sqr(a, a); + F.Sqr(b, b); + F.Mul(a, b, x); + F.Sub(a, b, a); + F.Mul(a, C_A24, z); + F.Add(z, b, z); + F.Mul(z, a, z); } public static void Precompute() @@ -83,45 +85,45 @@ namespace Org.BouncyCastle.Math.EC.Rfc7748 { uint[] n = new uint[8]; DecodeScalar(k, kOff, n); - int[] x1 = X25519Field.Create(); X25519Field.Decode(u, uOff, x1); - int[] x2 = X25519Field.Create(); X25519Field.Copy(x1, 0, x2, 0); - int[] z2 = X25519Field.Create(); z2[0] = 1; - int[] x3 = X25519Field.Create(); x3[0] = 1; - int[] z3 = X25519Field.Create(); + int[] x1 = F.Create(); F.Decode(u, uOff, x1); + int[] x2 = F.Create(); F.Copy(x1, 0, x2, 0); + int[] z2 = F.Create(); z2[0] = 1; + int[] x3 = F.Create(); x3[0] = 1; + int[] z3 = F.Create(); - int[] t1 = X25519Field.Create(); - int[] t2 = X25519Field.Create(); + int[] t1 = F.Create(); + int[] t2 = F.Create(); Debug.Assert(n[7] >> 30 == 1U); int bit = 254, swap = 1; do { - X25519Field.Apm(x3, z3, t1, x3); - X25519Field.Apm(x2, z2, z3, x2); - X25519Field.Mul(t1, x2, t1); - X25519Field.Mul(x3, z3, x3); - X25519Field.Sqr(z3, z3); - X25519Field.Sqr(x2, x2); - - X25519Field.Sub(z3, x2, t2); - X25519Field.Mul(t2, C_A24, z2); - X25519Field.Add(z2, x2, z2); - X25519Field.Mul(z2, t2, z2); - X25519Field.Mul(x2, z3, x2); - - X25519Field.Apm(t1, x3, x3, z3); - X25519Field.Sqr(x3, x3); - X25519Field.Sqr(z3, z3); - X25519Field.Mul(z3, x1, z3); + F.Apm(x3, z3, t1, x3); + F.Apm(x2, z2, z3, x2); + F.Mul(t1, x2, t1); + F.Mul(x3, z3, x3); + F.Sqr(z3, z3); + F.Sqr(x2, x2); + + F.Sub(z3, x2, t2); + F.Mul(t2, C_A24, z2); + F.Add(z2, x2, z2); + F.Mul(z2, t2, z2); + F.Mul(x2, z3, x2); + + F.Apm(t1, x3, x3, z3); + F.Sqr(x3, x3); + F.Sqr(z3, z3); + F.Mul(z3, x1, z3); --bit; int word = bit >> 5, shift = bit & 0x1F; int kt = (int)(n[word] >> shift) & 1; swap ^= kt; - X25519Field.CSwap(swap, x2, x3); - X25519Field.CSwap(swap, z2, z3); + F.CSwap(swap, x2, x3); + F.CSwap(swap, z2, z3); swap = kt; } while (bit >= 3); @@ -133,27 +135,27 @@ namespace Org.BouncyCastle.Math.EC.Rfc7748 PointDouble(x2, z2); } - X25519Field.Inv(z2, z2); - X25519Field.Mul(x2, z2, x2); + F.Inv(z2, z2); + F.Mul(x2, z2, x2); - X25519Field.Normalize(x2); - X25519Field.Encode(x2, r, rOff); + F.Normalize(x2); + F.Encode(x2, r, rOff); } public static void ScalarMultBase(byte[] k, int kOff, byte[] r, int rOff) { - int[] y = X25519Field.Create(); - int[] z = X25519Field.Create(); + int[] y = F.Create(); + int[] z = F.Create(); Ed25519.ScalarMultBaseYZ(k, kOff, y, z); - X25519Field.Apm(z, y, y, z); + F.Apm(z, y, y, z); - X25519Field.Inv(z, z); - X25519Field.Mul(y, z, y); + F.Inv(z, z); + F.Mul(y, z, y); - X25519Field.Normalize(y); - X25519Field.Encode(y, r, rOff); + F.Normalize(y); + F.Encode(y, r, rOff); } } } diff --git a/crypto/src/math/ec/rfc7748/X448.cs b/crypto/src/math/ec/rfc7748/X448.cs index 4f139f23d..061a13163 100644 --- a/crypto/src/math/ec/rfc7748/X448.cs +++ b/crypto/src/math/ec/rfc7748/X448.cs @@ -12,6 +12,8 @@ namespace Org.BouncyCastle.Math.EC.Rfc7748 public const int PointSize = 56; public const int ScalarSize = 56; + private class F : X448Field {}; + private const uint C_A = 156326; private const uint C_A24 = (C_A + 2)/4; @@ -60,19 +62,19 @@ namespace Org.BouncyCastle.Math.EC.Rfc7748 private static void PointDouble(uint[] x, uint[] z) { - uint[] A = X448Field.Create(); - uint[] B = X448Field.Create(); - - //X448Field.Apm(x, z, A, B); - X448Field.Add(x, z, A); - X448Field.Sub(x, z, B); - X448Field.Sqr(A, A); - X448Field.Sqr(B, B); - X448Field.Mul(A, B, x); - X448Field.Sub(A, B, A); - X448Field.Mul(A, C_A24, z); - X448Field.Add(z, B, z); - X448Field.Mul(z, A, z); + uint[] a = F.Create(); + uint[] b = F.Create(); + + //F.Apm(x, z, a, b); + F.Add(x, z, a); + F.Sub(x, z, b); + F.Sqr(a, a); + F.Sqr(b, b); + F.Mul(a, b, x); + F.Sub(a, b, a); + F.Mul(a, C_A24, z); + F.Add(z, b, z); + F.Mul(z, a, z); } public static void Precompute() @@ -84,52 +86,52 @@ namespace Org.BouncyCastle.Math.EC.Rfc7748 { uint[] n = new uint[14]; DecodeScalar(k, kOff, n); - uint[] x1 = X448Field.Create(); X448Field.Decode(u, uOff, x1); - uint[] x2 = X448Field.Create(); X448Field.Copy(x1, 0, x2, 0); - uint[] z2 = X448Field.Create(); z2[0] = 1; - uint[] x3 = X448Field.Create(); x3[0] = 1; - uint[] z3 = X448Field.Create(); + uint[] x1 = F.Create(); F.Decode(u, uOff, x1); + uint[] x2 = F.Create(); F.Copy(x1, 0, x2, 0); + uint[] z2 = F.Create(); z2[0] = 1; + uint[] x3 = F.Create(); x3[0] = 1; + uint[] z3 = F.Create(); - uint[] t1 = X448Field.Create(); - uint[] t2 = X448Field.Create(); + uint[] t1 = F.Create(); + uint[] t2 = F.Create(); Debug.Assert(n[13] >> 31 == 1U); int bit = 447, swap = 1; do { - //X448Field.Apm(x3, z3, t1, x3); - X448Field.Add(x3, z3, t1); - X448Field.Sub(x3, z3, x3); - //X448Field.Apm(x2, z2, z3, x2); - X448Field.Add(x2, z2, z3); - X448Field.Sub(x2, z2, x2); - - X448Field.Mul(t1, x2, t1); - X448Field.Mul(x3, z3, x3); - X448Field.Sqr(z3, z3); - X448Field.Sqr(x2, x2); - - X448Field.Sub(z3, x2, t2); - X448Field.Mul(t2, C_A24, z2); - X448Field.Add(z2, x2, z2); - X448Field.Mul(z2, t2, z2); - X448Field.Mul(x2, z3, x2); - - //X448Field.Apm(t1, x3, x3, z3); - X448Field.Sub(t1, x3, z3); - X448Field.Add(t1, x3, x3); - X448Field.Sqr(x3, x3); - X448Field.Sqr(z3, z3); - X448Field.Mul(z3, x1, z3); + //F.Apm(x3, z3, t1, x3); + F.Add(x3, z3, t1); + F.Sub(x3, z3, x3); + //F.Apm(x2, z2, z3, x2); + F.Add(x2, z2, z3); + F.Sub(x2, z2, x2); + + F.Mul(t1, x2, t1); + F.Mul(x3, z3, x3); + F.Sqr(z3, z3); + F.Sqr(x2, x2); + + F.Sub(z3, x2, t2); + F.Mul(t2, C_A24, z2); + F.Add(z2, x2, z2); + F.Mul(z2, t2, z2); + F.Mul(x2, z3, x2); + + //F.Apm(t1, x3, x3, z3); + F.Sub(t1, x3, z3); + F.Add(t1, x3, x3); + F.Sqr(x3, x3); + F.Sqr(z3, z3); + F.Mul(z3, x1, z3); --bit; int word = bit >> 5, shift = bit & 0x1F; int kt = (int)(n[word] >> shift) & 1; swap ^= kt; - X448Field.CSwap(swap, x2, x3); - X448Field.CSwap(swap, z2, z3); + F.CSwap(swap, x2, x3); + F.CSwap(swap, z2, z3); swap = kt; } while (bit >= 2); @@ -141,26 +143,26 @@ namespace Org.BouncyCastle.Math.EC.Rfc7748 PointDouble(x2, z2); } - X448Field.Inv(z2, z2); - X448Field.Mul(x2, z2, x2); + F.Inv(z2, z2); + F.Mul(x2, z2, x2); - X448Field.Normalize(x2); - X448Field.Encode(x2, r, rOff); + F.Normalize(x2); + F.Encode(x2, r, rOff); } public static void ScalarMultBase(byte[] k, int kOff, byte[] r, int rOff) { - uint[] x = X448Field.Create(); - uint[] y = X448Field.Create(); + uint[] x = F.Create(); + uint[] y = F.Create(); Ed448.ScalarMultBaseXY(k, kOff, x, y); - X448Field.Inv(x, x); - X448Field.Mul(x, y, x); - X448Field.Sqr(x, x); + F.Inv(x, x); + F.Mul(x, y, x); + F.Sqr(x, x); - X448Field.Normalize(x); - X448Field.Encode(x, r, rOff); + F.Normalize(x); + F.Encode(x, r, rOff); } } } diff --git a/crypto/src/math/ec/rfc7748/X448Field.cs b/crypto/src/math/ec/rfc7748/X448Field.cs index 4d3be5cda..ef4fd4627 100644 --- a/crypto/src/math/ec/rfc7748/X448Field.cs +++ b/crypto/src/math/ec/rfc7748/X448Field.cs @@ -120,6 +120,11 @@ namespace Org.BouncyCastle.Math.EC.Rfc7748 return new uint[Size]; } + public static uint[] CreateTable(int n) + { + return new uint[Size * n]; + } + public static void CSwap(int swap, uint[] a, uint[] b) { Debug.Assert(swap >> 1 == 0); diff --git a/crypto/src/math/ec/rfc8032/Ed25519.cs b/crypto/src/math/ec/rfc8032/Ed25519.cs index 3a39ae53d..bdbe47e50 100644 --- a/crypto/src/math/ec/rfc8032/Ed25519.cs +++ b/crypto/src/math/ec/rfc8032/Ed25519.cs @@ -21,6 +21,9 @@ namespace Org.BouncyCastle.Math.EC.Rfc8032 Ed25519ph = 2, } + private class F : X25519Field {}; + + private const long M08L = 0x000000FFL; private const long M28L = 0x0FFFFFFFL; private const long M32L = 0xFFFFFFFFL; @@ -33,10 +36,15 @@ namespace Org.BouncyCastle.Math.EC.Rfc8032 public static readonly int SecretKeySize = 32; public static readonly int SignatureSize = PointBytes + ScalarBytes; - private static readonly byte[] Dom2Prefix = Strings.ToByteArray("SigEd25519 no Ed25519 collisions"); + // "SigEd25519 no Ed25519 collisions" + private static readonly byte[] Dom2Prefix = new byte[]{ 0x53, 0x69, 0x67, 0x45, 0x64, 0x32, 0x35, 0x35, 0x31, + 0x39, 0x20, 0x6e, 0x6f, 0x20, 0x45, 0x64, 0x32, 0x35, 0x35, 0x31, 0x39, 0x20, 0x63, 0x6f, 0x6c, 0x6c, 0x69, + 0x73, 0x69, 0x6f, 0x6e, 0x73 }; - private static readonly uint[] P = { 0xFFFFFFEDU, 0xFFFFFFFFU, 0xFFFFFFFFU, 0xFFFFFFFFU, 0xFFFFFFFFU, 0xFFFFFFFFU, 0xFFFFFFFFU, 0x7FFFFFFFU }; - private static readonly uint[] L = { 0x5CF5D3EDU, 0x5812631AU, 0xA2F79CD6U, 0x14DEF9DEU, 0x00000000U, 0x00000000U, 0x00000000U, 0x10000000U }; + private static readonly uint[] P = { 0xFFFFFFEDU, 0xFFFFFFFFU, 0xFFFFFFFFU, 0xFFFFFFFFU, 0xFFFFFFFFU, + 0xFFFFFFFFU, 0xFFFFFFFFU, 0x7FFFFFFFU }; + private static readonly uint[] L = { 0x5CF5D3EDU, 0x5812631AU, 0xA2F79CD6U, 0x14DEF9DEU, 0x00000000U, + 0x00000000U, 0x00000000U, 0x10000000U }; private const int L0 = unchecked((int)0xFCF5D3ED); // L0:26/-- private const int L1 = 0x012631A6; // L1:24/22 @@ -70,26 +78,32 @@ namespace Org.BouncyCastle.Math.EC.Rfc8032 private class PointAccum { - internal int[] x = X25519Field.Create(); - internal int[] y = X25519Field.Create(); - internal int[] z = X25519Field.Create(); - internal int[] u = X25519Field.Create(); - internal int[] v = X25519Field.Create(); + internal int[] x = F.Create(); + internal int[] y = F.Create(); + internal int[] z = F.Create(); + internal int[] u = F.Create(); + internal int[] v = F.Create(); + } + + private class PointAffine + { + internal int[] x = F.Create(); + internal int[] y = F.Create(); } private class PointExt { - internal int[] x = X25519Field.Create(); - internal int[] y = X25519Field.Create(); - internal int[] z = X25519Field.Create(); - internal int[] t = X25519Field.Create(); + internal int[] x = F.Create(); + internal int[] y = F.Create(); + internal int[] z = F.Create(); + internal int[] t = F.Create(); } private class PointPrecomp { - internal int[] ypx_h = X25519Field.Create(); - internal int[] ymx_h = X25519Field.Create(); - internal int[] xyd = X25519Field.Create(); + internal int[] ypx_h = F.Create(); + internal int[] ymx_h = F.Create(); + internal int[] xyd = F.Create(); } private static byte[] CalculateS(byte[] r, byte[] k, byte[] s) @@ -116,42 +130,42 @@ namespace Org.BouncyCastle.Math.EC.Rfc8032 private static int CheckPoint(int[] x, int[] y) { - int[] t = X25519Field.Create(); - int[] u = X25519Field.Create(); - int[] v = X25519Field.Create(); - - X25519Field.Sqr(x, u); - X25519Field.Sqr(y, v); - X25519Field.Mul(u, v, t); - X25519Field.Sub(v, u, v); - X25519Field.Mul(t, C_d, t); - X25519Field.AddOne(t); - X25519Field.Sub(t, v, t); - X25519Field.Normalize(t); - - return X25519Field.IsZero(t); + int[] t = F.Create(); + int[] u = F.Create(); + int[] v = F.Create(); + + F.Sqr(x, u); + F.Sqr(y, v); + F.Mul(u, v, t); + F.Sub(v, u, v); + F.Mul(t, C_d, t); + F.AddOne(t); + F.Sub(t, v, t); + F.Normalize(t); + + return F.IsZero(t); } private static int CheckPoint(int[] x, int[] y, int[] z) { - int[] t = X25519Field.Create(); - int[] u = X25519Field.Create(); - int[] v = X25519Field.Create(); - int[] w = X25519Field.Create(); - - X25519Field.Sqr(x, u); - X25519Field.Sqr(y, v); - X25519Field.Sqr(z, w); - X25519Field.Mul(u, v, t); - X25519Field.Sub(v, u, v); - X25519Field.Mul(v, w, v); - X25519Field.Sqr(w, w); - X25519Field.Mul(t, C_d, t); - X25519Field.Add(t, w, t); - X25519Field.Sub(t, v, t); - X25519Field.Normalize(t); - - return X25519Field.IsZero(t); + int[] t = F.Create(); + int[] u = F.Create(); + int[] v = F.Create(); + int[] w = F.Create(); + + F.Sqr(x, u); + F.Sqr(y, v); + F.Sqr(z, w); + F.Mul(u, v, t); + F.Sub(v, u, v); + F.Mul(v, w, v); + F.Sqr(w, w); + F.Mul(t, C_d, t); + F.Add(t, w, t); + F.Sub(t, v, t); + F.Normalize(t); + + return F.IsZero(t); } private static bool CheckPointVar(byte[] p) @@ -204,7 +218,7 @@ namespace Org.BouncyCastle.Math.EC.Rfc8032 } } - private static bool DecodePointVar(byte[] p, int pOff, bool negate, PointExt r) + private static bool DecodePointVar(byte[] p, int pOff, bool negate, PointAffine r) { byte[] py = Arrays.CopyOfRange(p, pOff, pOff + PointBytes); if (!CheckPointVar(py)) @@ -213,29 +227,28 @@ namespace Org.BouncyCastle.Math.EC.Rfc8032 int x_0 = (py[PointBytes - 1] & 0x80) >> 7; py[PointBytes - 1] &= 0x7F; - X25519Field.Decode(py, 0, r.y); + F.Decode(py, 0, r.y); - int[] u = X25519Field.Create(); - int[] v = X25519Field.Create(); + int[] u = F.Create(); + int[] v = F.Create(); - X25519Field.Sqr(r.y, u); - X25519Field.Mul(C_d, u, v); - X25519Field.SubOne(u); - X25519Field.AddOne(v); + F.Sqr(r.y, u); + F.Mul(C_d, u, v); + F.SubOne(u); + F.AddOne(v); - if (!X25519Field.SqrtRatioVar(u, v, r.x)) + if (!F.SqrtRatioVar(u, v, r.x)) return false; - X25519Field.Normalize(r.x); - if (x_0 == 1 && X25519Field.IsZeroVar(r.x)) + F.Normalize(r.x); + if (x_0 == 1 && F.IsZeroVar(r.x)) return false; if (negate ^ (x_0 != (r.x[0] & 1))) { - X25519Field.Negate(r.x, r.x); + F.Negate(r.x, r.x); } - PointExtendXY(r); return true; } @@ -248,10 +261,14 @@ namespace Org.BouncyCastle.Math.EC.Rfc8032 { if (ctx != null) { - d.BlockUpdate(Dom2Prefix, 0, Dom2Prefix.Length); - d.Update(phflag); - d.Update((byte)ctx.Length); - d.BlockUpdate(ctx, 0, ctx.Length); + int n = Dom2Prefix.Length; + byte[] t = new byte[n + 2 + ctx.Length]; + Dom2Prefix.CopyTo(t, 0); + t[n] = phflag; + t[n + 1] = (byte)ctx.Length; + ctx.CopyTo(t, n + 2); + + d.BlockUpdate(t, 0, t.Length); } } @@ -278,18 +295,18 @@ namespace Org.BouncyCastle.Math.EC.Rfc8032 private static int EncodePoint(PointAccum p, byte[] r, int rOff) { - int[] x = X25519Field.Create(); - int[] y = X25519Field.Create(); + int[] x = F.Create(); + int[] y = F.Create(); - X25519Field.Inv(p.z, y); - X25519Field.Mul(p.x, y, x); - X25519Field.Mul(p.y, y, y); - X25519Field.Normalize(x); - X25519Field.Normalize(y); + F.Inv(p.z, y); + F.Mul(p.x, y, x); + F.Mul(p.y, y, y); + F.Normalize(x); + F.Normalize(y); int result = CheckPoint(x, y); - X25519Field.Encode(y, r, rOff); + F.Encode(y, r, rOff); r[rOff + PointBytes - 1] |= (byte)((x[0] & 1) << 7); return result; @@ -314,6 +331,12 @@ namespace Org.BouncyCastle.Math.EC.Rfc8032 ScalarMultBaseEncoded(s, pk, pkOff); } + private static uint GetWindow4(uint[] x, int n) + { + int w = (int)((uint)n >> 3), b = (n & 7) << 2; + return (x[w] >> b) & 15U; + } + private static sbyte[] GetWnafVar(uint[] n, int width) { Debug.Assert(n[ScalarUints - 1] >> 28 == 0); @@ -414,8 +437,8 @@ namespace Org.BouncyCastle.Math.EC.Rfc8032 ImplSign(d, h, s, pk, 0, ctx, phflag, m, mOff, mLen, sig, sigOff); } - private static void ImplSign(byte[] sk, int skOff, byte[] pk, int pkOff, byte[] ctx, byte phflag, - byte[] m, int mOff, int mLen, byte[] sig, int sigOff) + private static void ImplSign(byte[] sk, int skOff, byte[] pk, int pkOff, byte[] ctx, byte phflag, byte[] m, + int mOff, int mLen, byte[] sig, int sigOff) { if (!CheckContextVar(ctx, phflag)) throw new ArgumentException("ctx"); @@ -432,8 +455,8 @@ namespace Org.BouncyCastle.Math.EC.Rfc8032 ImplSign(d, h, s, pk, pkOff, ctx, phflag, m, mOff, mLen, sig, sigOff); } - private static bool ImplVerify(byte[] sig, int sigOff, byte[] pk, int pkOff, byte[] ctx, byte phflag, - byte[] m, int mOff, int mLen) + private static bool ImplVerify(byte[] sig, int sigOff, byte[] pk, int pkOff, byte[] ctx, byte phflag, byte[] m, + int mOff, int mLen) { if (!CheckContextVar(ctx, phflag)) throw new ArgumentException("ctx"); @@ -447,7 +470,7 @@ namespace Org.BouncyCastle.Math.EC.Rfc8032 if (!CheckScalarVar(S)) return false; - PointExt pA = new PointExt(); + PointAffine pA = new PointAffine(); if (!DecodePointVar(pk, pkOff, true, pA)) return false; @@ -475,161 +498,238 @@ namespace Org.BouncyCastle.Math.EC.Rfc8032 return 0 != EncodePoint(pR, check, 0) && Arrays.AreEqual(check, R); } - private static void PointAddVar(bool negate, PointExt p, PointAccum r) + private static void PointAdd(PointExt p, PointAccum r) { - int[] A = X25519Field.Create(); - int[] B = X25519Field.Create(); - int[] C = X25519Field.Create(); - int[] D = X25519Field.Create(); - int[] E = r.u; - int[] F = X25519Field.Create(); - int[] G = X25519Field.Create(); - int[] H = r.v; + int[] a = F.Create(); + int[] b = F.Create(); + int[] c = F.Create(); + int[] d = F.Create(); + int[] e = r.u; + int[] f = F.Create(); + int[] g = F.Create(); + int[] h = r.v; + + F.Apm(r.y, r.x, b, a); + F.Apm(p.y, p.x, d, c); + F.Mul(a, c, a); + F.Mul(b, d, b); + F.Mul(r.u, r.v, c); + F.Mul(c, p.t, c); + F.Mul(c, C_d2, c); + F.Mul(r.z, p.z, d); + F.Add(d, d, d); + F.Apm(b, a, h, e); + F.Apm(d, c, g, f); + F.Carry(g); + F.Mul(e, f, r.x); + F.Mul(g, h, r.y); + F.Mul(f, g, r.z); + } - int[] c, d, f, g; + private static void PointAdd(PointExt p, PointExt r) + { + int[] a = F.Create(); + int[] b = F.Create(); + int[] c = F.Create(); + int[] d = F.Create(); + int[] e = F.Create(); + int[] f = F.Create(); + int[] g = F.Create(); + int[] h = F.Create(); + + F.Apm(p.y, p.x, b, a); + F.Apm(r.y, r.x, d, c); + F.Mul(a, c, a); + F.Mul(b, d, b); + F.Mul(p.t, r.t, c); + F.Mul(c, C_d2, c); + F.Mul(p.z, r.z, d); + F.Add(d, d, d); + F.Apm(b, a, h, e); + F.Apm(d, c, g, f); + F.Carry(g); + F.Mul(e, f, r.x); + F.Mul(g, h, r.y); + F.Mul(f, g, r.z); + F.Mul(e, h, r.t); + } + + private static void PointAddVar(bool negate, PointExt p, PointAccum r) + { + int[] a = F.Create(); + int[] b = F.Create(); + int[] c = F.Create(); + int[] d = F.Create(); + int[] e = r.u; + int[] f = F.Create(); + int[] g = F.Create(); + int[] h = r.v; + + int[] nc, nd, nf, ng; if (negate) { - c = D; d = C; f = G; g = F; + nc = d; nd = c; nf = g; ng = f; } else { - c = C; d = D; f = F; g = G; + nc = c; nd = d; nf = f; ng = g; } - X25519Field.Apm(r.y, r.x, B, A); - X25519Field.Apm(p.y, p.x, d, c); - X25519Field.Mul(A, C, A); - X25519Field.Mul(B, D, B); - X25519Field.Mul(r.u, r.v, C); - X25519Field.Mul(C, p.t, C); - X25519Field.Mul(C, C_d2, C); - X25519Field.Mul(r.z, p.z, D); - X25519Field.Add(D, D, D); - X25519Field.Apm(B, A, H, E); - X25519Field.Apm(D, C, g, f); - X25519Field.Carry(g); - X25519Field.Mul(E, F, r.x); - X25519Field.Mul(G, H, r.y); - X25519Field.Mul(F, G, r.z); + F.Apm(r.y, r.x, b, a); + F.Apm(p.y, p.x, nd, nc); + F.Mul(a, c, a); + F.Mul(b, d, b); + F.Mul(r.u, r.v, c); + F.Mul(c, p.t, c); + F.Mul(c, C_d2, c); + F.Mul(r.z, p.z, d); + F.Add(d, d, d); + F.Apm(b, a, h, e); + F.Apm(d, c, ng, nf); + F.Carry(ng); + F.Mul(e, f, r.x); + F.Mul(g, h, r.y); + F.Mul(f, g, r.z); } private static void PointAddVar(bool negate, PointExt p, PointExt q, PointExt r) { - int[] A = X25519Field.Create(); - int[] B = X25519Field.Create(); - int[] C = X25519Field.Create(); - int[] D = X25519Field.Create(); - int[] E = X25519Field.Create(); - int[] F = X25519Field.Create(); - int[] G = X25519Field.Create(); - int[] H = X25519Field.Create(); - - int[] c, d, f, g; + int[] a = F.Create(); + int[] b = F.Create(); + int[] c = F.Create(); + int[] d = F.Create(); + int[] e = F.Create(); + int[] f = F.Create(); + int[] g = F.Create(); + int[] h = F.Create(); + + int[] nc, nd, nf, ng; if (negate) { - c = D; d = C; f = G; g = F; + nc = d; nd = c; nf = g; ng = f; } else { - c = C; d = D; f = F; g = G; + nc = c; nd = d; nf = f; ng = g; } - X25519Field.Apm(p.y, p.x, B, A); - X25519Field.Apm(q.y, q.x, d, c); - X25519Field.Mul(A, C, A); - X25519Field.Mul(B, D, B); - X25519Field.Mul(p.t, q.t, C); - X25519Field.Mul(C, C_d2, C); - X25519Field.Mul(p.z, q.z, D); - X25519Field.Add(D, D, D); - X25519Field.Apm(B, A, H, E); - X25519Field.Apm(D, C, g, f); - X25519Field.Carry(g); - X25519Field.Mul(E, F, r.x); - X25519Field.Mul(G, H, r.y); - X25519Field.Mul(F, G, r.z); - X25519Field.Mul(E, H, r.t); + F.Apm(p.y, p.x, b, a); + F.Apm(q.y, q.x, nd, nc); + F.Mul(a, c, a); + F.Mul(b, d, b); + F.Mul(p.t, q.t, c); + F.Mul(c, C_d2, c); + F.Mul(p.z, q.z, d); + F.Add(d, d, d); + F.Apm(b, a, h, e); + F.Apm(d, c, ng, nf); + F.Carry(ng); + F.Mul(e, f, r.x); + F.Mul(g, h, r.y); + F.Mul(f, g, r.z); + F.Mul(e, h, r.t); } private static void PointAddPrecomp(PointPrecomp p, PointAccum r) { - int[] A = X25519Field.Create(); - int[] B = X25519Field.Create(); - int[] C = X25519Field.Create(); - int[] E = r.u; - int[] F = X25519Field.Create(); - int[] G = X25519Field.Create(); - int[] H = r.v; - - X25519Field.Apm(r.y, r.x, B, A); - X25519Field.Mul(A, p.ymx_h, A); - X25519Field.Mul(B, p.ypx_h, B); - X25519Field.Mul(r.u, r.v, C); - X25519Field.Mul(C, p.xyd, C); - X25519Field.Apm(B, A, H, E); - X25519Field.Apm(r.z, C, G, F); - X25519Field.Carry(G); - X25519Field.Mul(E, F, r.x); - X25519Field.Mul(G, H, r.y); - X25519Field.Mul(F, G, r.z); + int[] a = F.Create(); + int[] b = F.Create(); + int[] c = F.Create(); + int[] e = r.u; + int[] f = F.Create(); + int[] g = F.Create(); + int[] h = r.v; + + F.Apm(r.y, r.x, b, a); + F.Mul(a, p.ymx_h, a); + F.Mul(b, p.ypx_h, b); + F.Mul(r.u, r.v, c); + F.Mul(c, p.xyd, c); + F.Apm(b, a, h, e); + F.Apm(r.z, c, g, f); + F.Carry(g); + F.Mul(e, f, r.x); + F.Mul(g, h, r.y); + F.Mul(f, g, r.z); } private static PointExt PointCopy(PointAccum p) { PointExt r = new PointExt(); - X25519Field.Copy(p.x, 0, r.x, 0); - X25519Field.Copy(p.y, 0, r.y, 0); - X25519Field.Copy(p.z, 0, r.z, 0); - X25519Field.Mul(p.u, p.v, r.t); + F.Copy(p.x, 0, r.x, 0); + F.Copy(p.y, 0, r.y, 0); + F.Copy(p.z, 0, r.z, 0); + F.Mul(p.u, p.v, r.t); + return r; + } + + private static PointExt PointCopy(PointAffine p) + { + PointExt r = new PointExt(); + F.Copy(p.x, 0, r.x, 0); + F.Copy(p.y, 0, r.y, 0); + PointExtendXY(r); return r; } private static PointExt PointCopy(PointExt p) { PointExt r = new PointExt(); - X25519Field.Copy(p.x, 0, r.x, 0); - X25519Field.Copy(p.y, 0, r.y, 0); - X25519Field.Copy(p.z, 0, r.z, 0); - X25519Field.Copy(p.t, 0, r.t, 0); + PointCopy(p, r); 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); + F.Copy(p.y, 0, r.y, 0); + F.Copy(p.z, 0, r.z, 0); + F.Copy(p.t, 0, r.t, 0); + } + private static void PointDouble(PointAccum r) { - int[] A = X25519Field.Create(); - int[] B = X25519Field.Create(); - int[] C = X25519Field.Create(); - int[] E = r.u; - int[] F = X25519Field.Create(); - int[] G = X25519Field.Create(); - int[] H = r.v; - - X25519Field.Sqr(r.x, A); - X25519Field.Sqr(r.y, B); - X25519Field.Sqr(r.z, C); - X25519Field.Add(C, C, C); - X25519Field.Apm(A, B, H, G); - X25519Field.Add(r.x, r.y, E); - X25519Field.Sqr(E, E); - X25519Field.Sub(H, E, E); - X25519Field.Add(C, G, F); - X25519Field.Carry(F); - X25519Field.Mul(E, F, r.x); - X25519Field.Mul(G, H, r.y); - X25519Field.Mul(F, G, r.z); + int[] a = F.Create(); + int[] b = F.Create(); + int[] c = F.Create(); + int[] e = r.u; + int[] f = F.Create(); + int[] g = F.Create(); + int[] h = r.v; + + F.Sqr(r.x, a); + F.Sqr(r.y, b); + F.Sqr(r.z, c); + F.Add(c, c, c); + F.Apm(a, b, h, g); + F.Add(r.x, r.y, e); + F.Sqr(e, e); + F.Sub(h, e, e); + F.Add(c, g, f); + F.Carry(f); + F.Mul(e, f, r.x); + F.Mul(g, h, r.y); + F.Mul(f, g, r.z); } private static void PointExtendXY(PointAccum p) { - X25519Field.One(p.z); - X25519Field.Copy(p.x, 0, p.u, 0); - X25519Field.Copy(p.y, 0, p.v, 0); + F.One(p.z); + F.Copy(p.x, 0, p.u, 0); + F.Copy(p.y, 0, p.v, 0); } private static void PointExtendXY(PointExt p) { - X25519Field.One(p.z); - X25519Field.Mul(p.x, p.y, p.t); + F.One(p.z); + F.Mul(p.x, p.y, p.t); } private static void PointLookup(int block, int index, PointPrecomp p) @@ -637,18 +737,81 @@ namespace Org.BouncyCastle.Math.EC.Rfc8032 Debug.Assert(0 <= block && block < PrecompBlocks); Debug.Assert(0 <= index && index < PrecompPoints); - int off = block * PrecompPoints * 3 * X25519Field.Size; + int off = block * PrecompPoints * 3 * F.Size; for (int i = 0; i < PrecompPoints; ++i) { int cond = ((i ^ index) - 1) >> 31; - X25519Field.CMov(cond, precompBase, off, p.ypx_h, 0); off += X25519Field.Size; - X25519Field.CMov(cond, precompBase, off, p.ymx_h, 0); off += X25519Field.Size; - X25519Field.CMov(cond, precompBase, off, p.xyd, 0); off += X25519Field.Size; + F.CMov(cond, precompBase, off, p.ypx_h, 0); off += F.Size; + F.CMov(cond, precompBase, off, p.ymx_h, 0); off += F.Size; + F.CMov(cond, precompBase, off, p.xyd, 0); off += F.Size; + } + } + + private static void PointLookup(uint[] x, int n, int[] table, PointExt r) + { + // TODO This method is currently hardcoded to 4-bit windows and 8 precomputed points + + uint w = GetWindow4(x, n); + + int sign = (int)(w >> (4 - 1)) ^ 1; + int abs = ((int)w ^ -sign) & 7; + + Debug.Assert(sign == 0 || sign == 1); + Debug.Assert(0 <= abs && abs < 8); + + for (int i = 0, off = 0; i < 8; ++i) + { + int cond = ((i ^ abs) - 1) >> 31; + F.CMov(cond, table, off, r.x, 0); off += F.Size; + F.CMov(cond, table, off, r.y, 0); off += F.Size; + F.CMov(cond, table, off, r.z, 0); off += F.Size; + F.CMov(cond, table, off, r.t, 0); off += F.Size; + } + + F.CNegate(sign, r.x); + 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); + + PointExt q = PointCopy(p); + PointExt d = PointCopy(q); + PointAdd(q, d); + + int[] table = X25519Field.CreateTable(count * 4); + int off = 0; + + int i = 0; + for (;;) + { + X25519Field.Copy(q.x, 0, table, off); off += X25519Field.Size; + X25519Field.Copy(q.y, 0, table, off); off += X25519Field.Size; + X25519Field.Copy(q.z, 0, table, off); off += X25519Field.Size; + X25519Field.Copy(q.t, 0, table, off); off += X25519Field.Size; + + if (++i == count) + break; + + PointAdd(d, q); } + + return table; } - private static PointExt[] PointPrecompVar(PointExt p, int count) + private static PointExt[] PointPrecomputeVar(PointExt p, int count) { Debug.Assert(count > 0); @@ -666,19 +829,19 @@ namespace Org.BouncyCastle.Math.EC.Rfc8032 private static void PointSetNeutral(PointAccum p) { - X25519Field.Zero(p.x); - X25519Field.One(p.y); - X25519Field.One(p.z); - X25519Field.Zero(p.u); - X25519Field.One(p.v); + F.Zero(p.x); + F.One(p.y); + F.One(p.z); + F.Zero(p.u); + F.One(p.v); } private static void PointSetNeutral(PointExt p) { - X25519Field.Zero(p.x); - X25519Field.One(p.y); - X25519Field.One(p.z); - X25519Field.Zero(p.t); + F.Zero(p.x); + F.One(p.y); + F.One(p.z); + F.Zero(p.t); } public static void Precompute() @@ -691,19 +854,19 @@ namespace Org.BouncyCastle.Math.EC.Rfc8032 // Precomputed table for the base point in verification ladder { PointExt b = new PointExt(); - X25519Field.Copy(B_x, 0, b.x, 0); - X25519Field.Copy(B_y, 0, b.y, 0); + F.Copy(B_x, 0, b.x, 0); + F.Copy(B_y, 0, b.y, 0); PointExtendXY(b); - precompBaseTable = PointPrecompVar(b, 1 << (WnafWidthBase - 2)); + precompBaseTable = PointPrecomputeVar(b, 1 << (WnafWidthBase - 2)); } PointAccum p = new PointAccum(); - X25519Field.Copy(B_x, 0, p.x, 0); - X25519Field.Copy(B_y, 0, p.y, 0); + F.Copy(B_x, 0, p.x, 0); + F.Copy(B_y, 0, p.y, 0); PointExtendXY(p); - precompBase = new int[PrecompBlocks * PrecompPoints * 3 * X25519Field.Size]; + precompBase = F.CreateTable(PrecompBlocks * PrecompPoints * 3); int off = 0; for (int b = 0; b < PrecompBlocks; ++b) @@ -745,31 +908,65 @@ namespace Org.BouncyCastle.Math.EC.Rfc8032 Debug.Assert(k == PrecompPoints); + int[] cs = F.CreateTable(PrecompPoints); + + // TODO[ed25519] A single batch inversion across all blocks? + { + int[] u = F.Create(); + F.Copy(points[0].z, 0, u, 0); + F.Copy(u, 0, cs, 0); + + int i = 0; + while (++i < PrecompPoints) + { + F.Mul(u, points[i].z, u); + F.Copy(u, 0, cs, i * F.Size); + } + + F.Add(u, u, u); + F.InvVar(u, u); + --i; + + int[] t = F.Create(); + + while (i > 0) + { + int j = i--; + F.Copy(cs, i * F.Size, t, 0); + F.Mul(t, u, t); + F.Copy(t, 0, cs, j * F.Size); + F.Mul(u, points[j].z, u); + } + + F.Copy(u, 0, cs, 0); + } + for (int i = 0; i < PrecompPoints; ++i) { PointExt q = points[i]; - int[] x = X25519Field.Create(); - int[] y = X25519Field.Create(); + int[] x = F.Create(); + int[] y = F.Create(); - X25519Field.Add(q.z, q.z, x); - // TODO[ed25519] Batch inversion - X25519Field.InvVar(x, y); - X25519Field.Mul(q.x, y, x); - X25519Field.Mul(q.y, y, y); + //F.Add(q.z, q.z, x); + //F.InvVar(x, y); + F.Copy(cs, i * F.Size, y, 0); + + F.Mul(q.x, y, x); + F.Mul(q.y, y, y); PointPrecomp r = new PointPrecomp(); - X25519Field.Apm(y, x, r.ypx_h, r.ymx_h); - X25519Field.Mul(x, y, r.xyd); - X25519Field.Mul(r.xyd, C_d4, r.xyd); + F.Apm(y, x, r.ypx_h, r.ymx_h); + F.Mul(x, y, r.xyd); + F.Mul(r.xyd, C_d4, r.xyd); - X25519Field.Normalize(r.ypx_h); - X25519Field.Normalize(r.ymx_h); - //X25519Field.Normalize(r.xyd); + F.Normalize(r.ypx_h); + F.Normalize(r.ymx_h); + //F.Normalize(r.xyd); - X25519Field.Copy(r.ypx_h, 0, precompBase, off); off += X25519Field.Size; - X25519Field.Copy(r.ymx_h, 0, precompBase, off); off += X25519Field.Size; - X25519Field.Copy(r.xyd, 0, precompBase, off); off += X25519Field.Size; + F.Copy(r.ypx_h, 0, precompBase, off); off += F.Size; + F.Copy(r.ymx_h, 0, precompBase, off); off += F.Size; + F.Copy(r.xyd, 0, precompBase, off); off += F.Size; } } @@ -806,7 +1003,7 @@ namespace Org.BouncyCastle.Math.EC.Rfc8032 long x15 = (Decode24(n, 53) << 4) & M32L; // x15:28/-- long x16 = Decode32(n, 56) & M32L; // x16:32/-- long x17 = (Decode24(n, 60) << 4) & M32L; // x17:28/-- - long x18 = n[63] & 0xFFL; // x18:08/-- + long x18 = n[63] & M08L; // x18:08/-- long t; //x18 += (x17 >> 28); x17 &= M28L; @@ -922,18 +1119,59 @@ namespace Org.BouncyCastle.Math.EC.Rfc8032 return r; } + private static void ScalarMult(byte[] k, PointAffine p, PointAccum r) + { + 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)); + } + + 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); + + int w = 62; + for (;;) + { + PointLookup(n, w, table, q); + PointAdd(q, r); + + PointDouble(r); + PointDouble(r); + PointDouble(r); + + if (--w < 0) + break; + + PointDouble(r); + } + } + private static void ScalarMultBase(byte[] k, PointAccum r) { Precompute(); - PointSetNeutral(r); - uint[] n = new uint[ScalarUints]; DecodeScalar(k, 0, n); // Recode the scalar into signed-digit form, then group comb bits in each block { - uint c1 = Nat.CAdd(ScalarUints, ~(int)n[0] & 1, n, L, n); Debug.Assert(c1 == 0); + 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)); for (int i = 0; i < ScalarUints; ++i) @@ -944,8 +1182,10 @@ namespace Org.BouncyCastle.Math.EC.Rfc8032 PointPrecomp p = new PointPrecomp(); + PointSetNeutral(r); + int cOff = (PrecompSpacing - 1) * PrecompTeeth; - for (; ; ) + for (;;) { for (int b = 0; b < PrecompBlocks; ++b) { @@ -958,8 +1198,8 @@ namespace Org.BouncyCastle.Math.EC.Rfc8032 PointLookup(b, abs, p); - X25519Field.CSwap(sign, p.ypx_h, p.ymx_h); - X25519Field.CNegate(sign, p.xyd); + F.CSwap(sign, p.ypx_h, p.ymx_h); + F.CNegate(sign, p.xyd); PointAddPrecomp(p, r); } @@ -990,11 +1230,11 @@ namespace Org.BouncyCastle.Math.EC.Rfc8032 if (0 == CheckPoint(p.x, p.y, p.z)) throw new InvalidOperationException(); - X25519Field.Copy(p.y, 0, y, 0); - X25519Field.Copy(p.z, 0, z, 0); + F.Copy(p.y, 0, y, 0); + F.Copy(p.z, 0, z, 0); } - private static void ScalarMultStrausVar(uint[] nb, uint[] np, PointExt p, PointAccum r) + private static void ScalarMultStrausVar(uint[] nb, uint[] np, PointAffine p, PointAccum r) { Precompute(); @@ -1003,7 +1243,7 @@ namespace Org.BouncyCastle.Math.EC.Rfc8032 sbyte[] ws_b = GetWnafVar(nb, WnafWidthBase); sbyte[] ws_p = GetWnafVar(np, width); - PointExt[] tp = PointPrecompVar(p, 1 << (width - 2)); + PointExt[] tp = PointPrecomputeVar(PointCopy(p), 1 << (width - 2)); PointSetNeutral(r); diff --git a/crypto/src/math/ec/rfc8032/Ed448.cs b/crypto/src/math/ec/rfc8032/Ed448.cs index c1202dc02..bbe1bb444 100644 --- a/crypto/src/math/ec/rfc8032/Ed448.cs +++ b/crypto/src/math/ec/rfc8032/Ed448.cs @@ -20,6 +20,8 @@ namespace Org.BouncyCastle.Math.EC.Rfc8032 Ed448ph = 1, } + private class F : X448Field {}; + private const ulong M26UL = 0x03FFFFFFUL; private const ulong M28UL = 0x0FFFFFFFUL; @@ -32,13 +34,13 @@ namespace Org.BouncyCastle.Math.EC.Rfc8032 public static readonly int SecretKeySize = 57; public static readonly int SignatureSize = PointBytes + ScalarBytes; - private static readonly byte[] Dom4Prefix = Strings.ToByteArray("SigEd448"); + // "SigEd448" + private static readonly byte[] Dom4Prefix = new byte[]{ 0x53, 0x69, 0x67, 0x45, 0x64, 0x34, 0x34, 0x38 }; private static readonly uint[] P = { 0xFFFFFFFFU, 0xFFFFFFFFU, 0xFFFFFFFFU, 0xFFFFFFFFU, 0xFFFFFFFFU, 0xFFFFFFFFU, 0xFFFFFFFFU, 0xFFFFFFFEU, 0xFFFFFFFFU, 0xFFFFFFFFU, 0xFFFFFFFFU, 0xFFFFFFFFU, 0xFFFFFFFFU, 0xFFFFFFFFU }; private static readonly uint[] L = { 0xAB5844F3U, 0x2378C292U, 0x8DC58F55U, 0x216CC272U, 0xAED63690U, 0xC44EDB49U, 0x7CCA23E9U, 0xFFFFFFFFU, 0xFFFFFFFFU, 0xFFFFFFFFU, 0xFFFFFFFFU, 0xFFFFFFFFU, 0xFFFFFFFFU, 0x3FFFFFFFU }; - private static readonly BigInteger N = Nat.ToBigInteger(L.Length, L); private const int L_0 = 0x04A7BB0D; // L_0:26/24 private const int L_1 = 0x0873D6D5; // L_1:27/23 @@ -79,15 +81,15 @@ namespace Org.BouncyCastle.Math.EC.Rfc8032 private class PointExt { - internal uint[] x = X448Field.Create(); - internal uint[] y = X448Field.Create(); - internal uint[] z = X448Field.Create(); + internal uint[] x = F.Create(); + internal uint[] y = F.Create(); + internal uint[] z = F.Create(); } private class PointPrecomp { - internal uint[] x = X448Field.Create(); - internal uint[] y = X448Field.Create(); + internal uint[] x = F.Create(); + internal uint[] y = F.Create(); } private static byte[] CalculateS(byte[] r, byte[] k, byte[] s) @@ -113,42 +115,42 @@ namespace Org.BouncyCastle.Math.EC.Rfc8032 private static int CheckPoint(uint[] x, uint[] y) { - uint[] t = X448Field.Create(); - uint[] u = X448Field.Create(); - uint[] v = X448Field.Create(); - - X448Field.Sqr(x, u); - X448Field.Sqr(y, v); - X448Field.Mul(u, v, t); - X448Field.Add(u, v, u); - X448Field.Mul(t, -C_d, t); - X448Field.SubOne(t); - X448Field.Add(t, u, t); - X448Field.Normalize(t); - - return X448Field.IsZero(t); + uint[] t = F.Create(); + uint[] u = F.Create(); + uint[] v = F.Create(); + + F.Sqr(x, u); + F.Sqr(y, v); + F.Mul(u, v, t); + F.Add(u, v, u); + F.Mul(t, -C_d, t); + F.SubOne(t); + F.Add(t, u, t); + F.Normalize(t); + + return F.IsZero(t); } private static int CheckPoint(uint[] x, uint[] y, uint[] z) { - uint[] t = X448Field.Create(); - uint[] u = X448Field.Create(); - uint[] v = X448Field.Create(); - uint[] w = X448Field.Create(); - - X448Field.Sqr(x, u); - X448Field.Sqr(y, v); - X448Field.Sqr(z, w); - X448Field.Mul(u, v, t); - X448Field.Add(u, v, u); - X448Field.Mul(u, w, u); - X448Field.Sqr(w, w); - X448Field.Mul(t, -C_d, t); - X448Field.Sub(t, w, t); - X448Field.Add(t, u, t); - X448Field.Normalize(t); - - return X448Field.IsZero(t); + uint[] t = F.Create(); + uint[] u = F.Create(); + uint[] v = F.Create(); + uint[] w = F.Create(); + + F.Sqr(x, u); + F.Sqr(y, v); + F.Sqr(z, w); + F.Mul(u, v, t); + F.Add(u, v, u); + F.Mul(u, w, u); + F.Sqr(w, w); + F.Mul(t, -C_d, t); + F.Sub(t, w, t); + F.Add(t, u, t); + F.Normalize(t); + + return F.IsZero(t); } private static bool CheckPointVar(byte[] p) @@ -222,27 +224,27 @@ namespace Org.BouncyCastle.Math.EC.Rfc8032 int x_0 = (py[PointBytes - 1] & 0x80) >> 7; py[PointBytes - 1] &= 0x7F; - X448Field.Decode(py, 0, r.y); + F.Decode(py, 0, r.y); - uint[] u = X448Field.Create(); - uint[] v = X448Field.Create(); + uint[] u = F.Create(); + uint[] v = F.Create(); - X448Field.Sqr(r.y, u); - X448Field.Mul(u, (uint)-C_d, v); - X448Field.Negate(u, u); - X448Field.AddOne(u); - X448Field.AddOne(v); + F.Sqr(r.y, u); + F.Mul(u, (uint)-C_d, v); + F.Negate(u, u); + F.AddOne(u); + F.AddOne(v); - if (!X448Field.SqrtRatioVar(u, v, r.x)) + if (!F.SqrtRatioVar(u, v, r.x)) return false; - X448Field.Normalize(r.x); - if (x_0 == 1 && X448Field.IsZeroVar(r.x)) + F.Normalize(r.x); + if (x_0 == 1 && F.IsZeroVar(r.x)) return false; if (negate ^ (x_0 != (r.x[0] & 1))) { - X448Field.Negate(r.x, r.x); + F.Negate(r.x, r.x); } PointExtendXY(r); @@ -256,12 +258,16 @@ namespace Org.BouncyCastle.Math.EC.Rfc8032 Decode32(k, kOff, n, 0, ScalarUints); } - private static void Dom4(IXof d, byte x, byte[] y) + private static void Dom4(IXof d, byte phflag, byte[] ctx) { - d.BlockUpdate(Dom4Prefix, 0, Dom4Prefix.Length); - d.Update(x); - d.Update((byte)y.Length); - d.BlockUpdate(y, 0, y.Length); + int n = Dom4Prefix.Length; + byte[] t = new byte[n + 2 + ctx.Length]; + Dom4Prefix.CopyTo(t, 0); + t[n] = phflag; + t[n + 1] = (byte)ctx.Length; + ctx.CopyTo(t, n + 2); + + d.BlockUpdate(t, 0, t.Length); } private static void Encode24(uint n, byte[] bs, int off) @@ -287,18 +293,18 @@ namespace Org.BouncyCastle.Math.EC.Rfc8032 private static int EncodePoint(PointExt p, byte[] r, int rOff) { - uint[] x = X448Field.Create(); - uint[] y = X448Field.Create(); + uint[] x = F.Create(); + uint[] y = F.Create(); - X448Field.Inv(p.z, y); - X448Field.Mul(p.x, y, x); - X448Field.Mul(p.y, y, y); - X448Field.Normalize(x); - X448Field.Normalize(y); + F.Inv(p.z, y); + F.Mul(p.x, y, x); + F.Mul(p.y, y, y); + F.Normalize(x); + F.Normalize(y); int result = CheckPoint(x, y); - X448Field.Encode(y, r, rOff); + F.Encode(y, r, rOff); r[rOff + PointBytes - 1] = (byte)((x[0] & 1) << 7); return result; @@ -323,6 +329,12 @@ namespace Org.BouncyCastle.Math.EC.Rfc8032 ScalarMultBaseEncoded(s, pk, pkOff); } + private static uint GetWindow4(uint[] x, int n) + { + int w = (int)((uint)n >> 3), b = (n & 7) << 2; + return (x[w] >> b) & 15U; + } + private static sbyte[] GetWnafVar(uint[] n, int width) { Debug.Assert(n[ScalarUints - 1] >> 30 == 0U); @@ -484,123 +496,163 @@ namespace Org.BouncyCastle.Math.EC.Rfc8032 return 0 != EncodePoint(pR, check, 0) && Arrays.AreEqual(check, R); } + private static void PointAdd(PointExt p, PointExt r) + { + uint[] a = F.Create(); + uint[] b = F.Create(); + uint[] c = F.Create(); + uint[] d = F.Create(); + uint[] e = F.Create(); + uint[] f = F.Create(); + uint[] g = F.Create(); + uint[] h = F.Create(); + + F.Mul(p.z, r.z, a); + F.Sqr(a, b); + F.Mul(p.x, r.x, c); + F.Mul(p.y, r.y, d); + F.Mul(c, d, e); + F.Mul(e, -C_d, e); + //F.Apm(b, e, f, g); + F.Add(b, e, f); + F.Sub(b, e, g); + F.Add(p.x, p.y, b); + F.Add(r.x, r.y, e); + F.Mul(b, e, h); + //F.Apm(d, c, b, e); + F.Add(d, c, b); + F.Sub(d, c, e); + F.Carry(b); + F.Sub(h, b, h); + F.Mul(h, a, h); + F.Mul(e, a, e); + F.Mul(f, h, r.x); + F.Mul(e, g, r.y); + F.Mul(f, g, r.z); + } + private static void PointAddVar(bool negate, PointExt p, PointExt r) { - uint[] A = X448Field.Create(); - uint[] B = X448Field.Create(); - uint[] C = X448Field.Create(); - uint[] D = X448Field.Create(); - uint[] E = X448Field.Create(); - uint[] F = X448Field.Create(); - uint[] G = X448Field.Create(); - uint[] H = X448Field.Create(); - - uint[] b, e, f, g; + uint[] a = F.Create(); + uint[] b = F.Create(); + uint[] c = F.Create(); + uint[] d = F.Create(); + uint[] e = F.Create(); + uint[] f = F.Create(); + uint[] g = F.Create(); + uint[] h = F.Create(); + + uint[] nb, ne, nf, ng; if (negate) { - b = E; e = B; f = G; g = F; - X448Field.Sub(p.y, p.x, H); + nb = e; ne = b; nf = g; ng = f; + F.Sub(p.y, p.x, h); } else { - b = B; e = E; f = F; g = G; - X448Field.Add(p.y, p.x, H); + nb = b; ne = e; nf = f; ng = g; + F.Add(p.y, p.x, h); } - X448Field.Mul(p.z, r.z, A); - X448Field.Sqr(A, B); - X448Field.Mul(p.x, r.x, C); - X448Field.Mul(p.y, r.y, D); - X448Field.Mul(C, D, E); - X448Field.Mul(E, -C_d, E); - //X448Field.Apm(B, E, F, G); - X448Field.Add(B, E, f); - X448Field.Sub(B, E, g); - X448Field.Add(r.x, r.y, E); - X448Field.Mul(H, E, H); - //X448Field.Apm(D, C, B, E); - X448Field.Add(D, C, b); - X448Field.Sub(D, C, e); - X448Field.Carry(b); - X448Field.Sub(H, B, H); - X448Field.Mul(H, A, H); - X448Field.Mul(E, A, E); - X448Field.Mul(F, H, r.x); - X448Field.Mul(E, G, r.y); - X448Field.Mul(F, G, r.z); + F.Mul(p.z, r.z, a); + F.Sqr(a, b); + F.Mul(p.x, r.x, c); + F.Mul(p.y, r.y, d); + F.Mul(c, d, e); + F.Mul(e, -C_d, e); + //F.Apm(b, e, nf, ng); + F.Add(b, e, nf); + F.Sub(b, e, ng); + F.Add(r.x, r.y, e); + F.Mul(h, e, h); + //F.Apm(d, c, nb, ne); + F.Add(d, c, nb); + F.Sub(d, c, ne); + F.Carry(nb); + F.Sub(h, b, h); + F.Mul(h, a, h); + F.Mul(e, a, e); + F.Mul(f, h, r.x); + F.Mul(e, g, r.y); + F.Mul(f, g, r.z); } private static void PointAddPrecomp(PointPrecomp p, PointExt r) { - uint[] B = X448Field.Create(); - uint[] C = X448Field.Create(); - uint[] D = X448Field.Create(); - uint[] E = X448Field.Create(); - uint[] F = X448Field.Create(); - uint[] G = X448Field.Create(); - uint[] H = X448Field.Create(); - - X448Field.Sqr(r.z, B); - X448Field.Mul(p.x, r.x, C); - X448Field.Mul(p.y, r.y, D); - X448Field.Mul(C, D, E); - X448Field.Mul(E, -C_d, E); - //X448Field.Apm(B, E, F, G); - X448Field.Add(B, E, F); - X448Field.Sub(B, E, G); - X448Field.Add(p.x, p.y, B); - X448Field.Add(r.x, r.y, E); - X448Field.Mul(B, E, H); - //X448Field.Apm(D, C, B, E); - X448Field.Add(D, C, B); - X448Field.Sub(D, C, E); - X448Field.Carry(B); - X448Field.Sub(H, B, H); - X448Field.Mul(H, r.z, H); - X448Field.Mul(E, r.z, E); - X448Field.Mul(F, H, r.x); - X448Field.Mul(E, G, r.y); - X448Field.Mul(F, G, r.z); + uint[] b = F.Create(); + uint[] c = F.Create(); + uint[] d = F.Create(); + uint[] e = F.Create(); + uint[] f = F.Create(); + uint[] g = F.Create(); + uint[] h = F.Create(); + + F.Sqr(r.z, b); + F.Mul(p.x, r.x, c); + F.Mul(p.y, r.y, d); + F.Mul(c, d, e); + F.Mul(e, -C_d, e); + //F.Apm(b, e, f, g); + F.Add(b, e, f); + F.Sub(b, e, g); + F.Add(p.x, p.y, b); + F.Add(r.x, r.y, e); + F.Mul(b, e, h); + //F.Apm(d, c, b, e); + F.Add(d, c, b); + F.Sub(d, c, e); + F.Carry(b); + F.Sub(h, b, h); + F.Mul(h, r.z, h); + F.Mul(e, r.z, e); + F.Mul(f, h, r.x); + F.Mul(e, g, r.y); + F.Mul(f, g, r.z); } private static PointExt PointCopy(PointExt p) { PointExt r = new PointExt(); - X448Field.Copy(p.x, 0, r.x, 0); - X448Field.Copy(p.y, 0, r.y, 0); - X448Field.Copy(p.z, 0, r.z, 0); + PointCopy(p, r); return r; } + private static void PointCopy(PointExt p, PointExt r) + { + F.Copy(p.x, 0, r.x, 0); + F.Copy(p.y, 0, r.y, 0); + F.Copy(p.z, 0, r.z, 0); + } + private static void PointDouble(PointExt r) { - uint[] B = X448Field.Create(); - uint[] C = X448Field.Create(); - uint[] D = X448Field.Create(); - uint[] E = X448Field.Create(); - uint[] H = X448Field.Create(); - uint[] J = X448Field.Create(); - - X448Field.Add(r.x, r.y, B); - X448Field.Sqr(B, B); - X448Field.Sqr(r.x, C); - X448Field.Sqr(r.y, D); - X448Field.Add(C, D, E); - X448Field.Carry(E); - X448Field.Sqr(r.z, H); - X448Field.Add(H, H, H); - X448Field.Carry(H); - X448Field.Sub(E, H, J); - X448Field.Sub(B, E, B); - X448Field.Sub(C, D, C); - X448Field.Mul(B, J, r.x); - X448Field.Mul(E, C, r.y); - X448Field.Mul(E, J, r.z); + uint[] b = F.Create(); + uint[] c = F.Create(); + uint[] d = F.Create(); + uint[] e = F.Create(); + uint[] h = F.Create(); + uint[] j = F.Create(); + + F.Add(r.x, r.y, b); + F.Sqr(b, b); + F.Sqr(r.x, c); + F.Sqr(r.y, d); + F.Add(c, d, e); + F.Carry(e); + F.Sqr(r.z, h); + F.Add(h, h, h); + F.Carry(h); + F.Sub(e, h, j); + F.Sub(b, e, b); + F.Sub(c, d, c); + F.Mul(b, j, r.x); + F.Mul(e, c, r.y); + F.Mul(e, j, r.z); } private static void PointExtendXY(PointExt p) { - X448Field.One(p.z); + F.One(p.z); } private static void PointLookup(int block, int index, PointPrecomp p) @@ -608,17 +660,67 @@ namespace Org.BouncyCastle.Math.EC.Rfc8032 Debug.Assert(0 <= block && block < PrecompBlocks); Debug.Assert(0 <= index && index < PrecompPoints); - int off = block * PrecompPoints * 2 * X448Field.Size; + int off = block * PrecompPoints * 2 * F.Size; for (int i = 0; i < PrecompPoints; ++i) { int cond = ((i ^ index) - 1) >> 31; - X448Field.CMov(cond, precompBase, off, p.x, 0); off += X448Field.Size; - X448Field.CMov(cond, precompBase, off, p.y, 0); off += X448Field.Size; + F.CMov(cond, precompBase, off, p.x, 0); off += F.Size; + F.CMov(cond, precompBase, off, p.y, 0); off += F.Size; } } - private static PointExt[] PointPrecompVar(PointExt p, int count) + private static void PointLookup(uint[] x, int n, uint[] table, PointExt r) + { + // TODO This method is currently hardcoded to 4-bit windows and 8 precomputed points + + uint w = GetWindow4(x, n); + + int sign = (int)(w >> (4 - 1)) ^ 1; + int abs = ((int)w ^ -sign) & 7; + + Debug.Assert(sign == 0 || sign == 1); + Debug.Assert(0 <= abs && abs < 8); + + for (int i = 0, off = 0; i < 8; ++i) + { + int cond = ((i ^ abs) - 1) >> 31; + F.CMov(cond, table, off, r.x, 0); off += F.Size; + F.CMov(cond, table, off, r.y, 0); off += F.Size; + F.CMov(cond, table, off, r.z, 0); off += F.Size; + } + + F.CNegate(sign, r.x); + } + + private static uint[] PointPrecompute(PointExt p, int count) + { + Debug.Assert(count > 0); + + PointExt q = PointCopy(p); + PointExt d = PointCopy(q); + PointDouble(d); + + uint[] table = X448Field.CreateTable(count * 3); + int off = 0; + + int i = 0; + for (;;) + { + F.Copy(q.x, 0, table, off); off += F.Size; + F.Copy(q.y, 0, table, off); off += F.Size; + F.Copy(q.z, 0, table, off); off += F.Size; + + if (++i == count) + break; + + PointAdd(d, q); + } + + return table; + } + + private static PointExt[] PointPrecomputeVar(PointExt p, int count) { Debug.Assert(count > 0); @@ -637,9 +739,9 @@ namespace Org.BouncyCastle.Math.EC.Rfc8032 private static void PointSetNeutral(PointExt p) { - X448Field.Zero(p.x); - X448Field.One(p.y); - X448Field.One(p.z); + F.Zero(p.x); + F.One(p.y); + F.One(p.z); } public static void Precompute() @@ -650,13 +752,13 @@ namespace Org.BouncyCastle.Math.EC.Rfc8032 return; PointExt p = new PointExt(); - X448Field.Copy(B_x, 0, p.x, 0); - X448Field.Copy(B_y, 0, p.y, 0); + F.Copy(B_x, 0, p.x, 0); + F.Copy(B_y, 0, p.y, 0); PointExtendXY(p); - precompBaseTable = PointPrecompVar(p, 1 << (WnafWidthBase - 2)); + precompBaseTable = PointPrecomputeVar(p, 1 << (WnafWidthBase - 2)); - precompBase = new uint[PrecompBlocks * PrecompPoints * 2 * X448Field.Size]; + precompBase = F.CreateTable(PrecompBlocks * PrecompPoints * 2); int off = 0; for (int b = 0; b < PrecompBlocks; ++b) @@ -698,19 +800,53 @@ namespace Org.BouncyCastle.Math.EC.Rfc8032 Debug.Assert(k == PrecompPoints); + uint[] cs = F.CreateTable(PrecompPoints); + + // TODO[ed448] A single batch inversion across all blocks? + { + uint[] u = F.Create(); + F.Copy(points[0].z, 0, u, 0); + F.Copy(u, 0, cs, 0); + + int i = 0; + while (++i < PrecompPoints) + { + F.Mul(u, points[i].z, u); + F.Copy(u, 0, cs, i * F.Size); + } + + F.InvVar(u, u); + --i; + + uint[] t = F.Create(); + + while (i > 0) + { + int j = i--; + F.Copy(cs, i * F.Size, t, 0); + F.Mul(t, u, t); + F.Copy(t, 0, cs, j * F.Size); + F.Mul(u, points[j].z, u); + } + + F.Copy(u, 0, cs, 0); + } + for (int i = 0; i < PrecompPoints; ++i) { PointExt q = points[i]; - // TODO[ed448] Batch inversion - X448Field.InvVar(q.z, q.z); - X448Field.Mul(q.x, q.z, q.x); - X448Field.Mul(q.y, q.z, q.y); - //X448Field.Normalize(q.x); - //X448Field.Normalize(q.y); + //F.InvVar(q.z, q.z); + F.Copy(cs, i * F.Size, q.z, 0); - X448Field.Copy(q.x, 0, precompBase, off); off += X448Field.Size; - X448Field.Copy(q.y, 0, precompBase, off); off += X448Field.Size; + F.Mul(q.x, q.z, q.x); + F.Mul(q.y, q.z, q.y); + + //F.Normalize(q.x); + //F.Normalize(q.y); + + F.Copy(q.x, 0, precompBase, off); off += F.Size; + F.Copy(q.y, 0, precompBase, off); off += F.Size; } } @@ -1004,12 +1140,48 @@ namespace Org.BouncyCastle.Math.EC.Rfc8032 return r; } + private static void ScalarMult(byte[] k, PointExt p, PointExt r) + { + 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[] table = PointPrecompute(p, 8); + PointExt q = new PointExt(); + + PointLookup(n, 111, table, r); + + for (int w = 110; w >= 0; --w) + { + 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) { Precompute(); - PointSetNeutral(r); - uint[] n = new uint[ScalarUints + 1]; DecodeScalar(k, 0, n); @@ -1022,6 +1194,8 @@ namespace Org.BouncyCastle.Math.EC.Rfc8032 PointPrecomp p = new PointPrecomp(); + PointSetNeutral(r); + int cOff = PrecompSpacing - 1; for (;;) { @@ -1046,7 +1220,7 @@ namespace Org.BouncyCastle.Math.EC.Rfc8032 PointLookup(b, abs, p); - X448Field.CNegate(sign, p.x); + F.CNegate(sign, p.x); PointAddPrecomp(p, r); } @@ -1077,8 +1251,8 @@ namespace Org.BouncyCastle.Math.EC.Rfc8032 if (0 == CheckPoint(p.x, p.y, p.z)) throw new InvalidOperationException(); - X448Field.Copy(p.x, 0, x, 0); - X448Field.Copy(p.y, 0, y, 0); + F.Copy(p.x, 0, x, 0); + F.Copy(p.y, 0, y, 0); } private static void ScalarMultStrausVar(uint[] nb, uint[] np, PointExt p, PointExt r) @@ -1090,7 +1264,7 @@ namespace Org.BouncyCastle.Math.EC.Rfc8032 sbyte[] ws_b = GetWnafVar(nb, WnafWidthBase); sbyte[] ws_p = GetWnafVar(np, width); - PointExt[] tp = PointPrecompVar(p, 1 << (width - 2)); + PointExt[] tp = PointPrecomputeVar(p, 1 << (width - 2)); PointSetNeutral(r); |