From 9c89cec327d429564bd1e7b5cb92bdaae0acd8f9 Mon Sep 17 00:00:00 2001 From: Peter Dettman Date: Thu, 6 Feb 2014 10:31:12 +0700 Subject: Initial work on the Curve25519 field implementation --- crypto/src/math/ec/custom/sec/Curve25519Field.cs | 159 +++++++++++++++++++++++ crypto/src/math/ec/custom/sec/Nat256.cs | 148 ++++++++++++++++++--- 2 files changed, 288 insertions(+), 19 deletions(-) create mode 100644 crypto/src/math/ec/custom/sec/Curve25519Field.cs (limited to 'crypto/src/math/ec/custom') diff --git a/crypto/src/math/ec/custom/sec/Curve25519Field.cs b/crypto/src/math/ec/custom/sec/Curve25519Field.cs new file mode 100644 index 000000000..be9878911 --- /dev/null +++ b/crypto/src/math/ec/custom/sec/Curve25519Field.cs @@ -0,0 +1,159 @@ +using System; +using System.Diagnostics; + +namespace Org.BouncyCastle.Math.EC.Custom.Sec +{ + internal class Curve25519Field + { + // 2^255 - 2^4 - 2^1 - 1 + internal static readonly uint[] P = new uint[]{ 0xFFFFFFED, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, + 0xFFFFFFFF, 0x7FFFFFFF }; + private const int P7 = 0x7FFFFFFF; + private static readonly uint[] PExt = new uint[]{ 0x00000169, 0x00000000, 0x00000000, 0x00000000, 0x00000000, + 0x00000000, 0x00000000, 0x00000000, 0xFFFFFFED, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, + 0xFFFFFFFF, 0x3FFFFFFF }; + private const uint PInv = 0x13; + + public static void Add(uint[] x, uint[] y, uint[] z) + { + Nat256.Add(x, y, z); + if (Nat256.Gte(z, P)) + { + Nat256.AddWord(PInv, z, 0); + z[7] &= P7; + } + } + + public static void AddExt(uint[] xx, uint[] yy, uint[] zz) + { + Nat256.AddExt(xx, yy, zz); + if (Nat256.GteExt(zz, PExt)) + { + Nat256.SubExt(zz, PExt, zz); + } + } + + public static void AddOne(uint[] x, uint[] z) + { + Nat256.Copy(x, z); + Nat256.Inc(z, 0); + if (Nat256.Gte(z, P)) + { + Nat256.AddWord(PInv, z, 0); + z[7] &= P7; + } + } + + public static uint[] FromBigInteger(BigInteger x) + { + uint[] z = Nat256.FromBigInteger(x); + if (Nat256.Gte(z, P)) + { + Nat256.AddWord(PInv, z, 0); + z[7] &= P7; + } + return z; + } + + public static void Half(uint[] x, uint[] z) + { + if ((x[0] & 1) == 0) + { + Nat.ShiftDownBit(8, x, 0, z); + } + else + { + Nat256.Add(x, P, z); + Nat.ShiftDownBit(8, z, 0); + } + } + + public static void Multiply(uint[] x, uint[] y, uint[] z) + { + uint[] tt = Nat256.CreateExt(); + Nat256.Mul(x, y, tt); + Reduce(tt, z); + } + + public static void Negate(uint[] x, uint[] z) + { + if (Nat256.IsZero(x)) + { + Nat256.Zero(z); + } + else + { + Nat256.Sub(P, x, z); + } + } + + public static void Reduce(uint[] xx, uint[] z) + { + Debug.Assert(xx[15] >> 30 == 0); + + uint xx07 = xx[7]; + Nat.ShiftUpBit(8, xx, 8, xx07, z); + uint c = Nat256.MulByWordAddTo(PInv, xx, z) << 1; + uint z07 = z[7]; + z[7] = z07 & P7; + c += (z07 >> 31) - (xx07 >> 31); + Nat256.AddWord(c * PInv, z, 0); + if (Nat256.Gte(z, P)) + { + Nat256.AddWord(PInv, z, 0); + z[7] &= P7; + } + } + + public static void Square(uint[] x, uint[] z) + { + uint[] tt = Nat256.CreateExt(); + Nat256.Square(x, tt); + Reduce(tt, z); + } + + public static void SquareN(uint[] x, int n, uint[] z) + { + // assert n > 0; + + uint[] tt = Nat256.CreateExt(); + Nat256.Square(x, tt); + Reduce(tt, z); + + while (--n > 0) + { + Nat256.Square(z, tt); + Reduce(tt, z); + } + } + + public static void Subtract(uint[] x, uint[] y, uint[] z) + { + int c = Nat256.Sub(x, y, z); + if (c != 0) + { + Nat256.SubWord(PInv, z, 0); + z[7] &= P7; + } + } + + public static void SubtractExt(uint[] xx, uint[] yy, uint[] zz) + { + int c = Nat256.SubExt(xx, yy, zz); + if (c != 0) + { + Nat256.AddExt(zz, PExt, zz); + } + } + + public static void Twice(uint[] x, uint[] z) + { + Nat256.ShiftUpBit(x, 0, z); + if (Nat256.Gte(z, P)) + { + Nat256.AddWord(PInv, z, 0); + z[7] &= P7; + } + } + } +} diff --git a/crypto/src/math/ec/custom/sec/Nat256.cs b/crypto/src/math/ec/custom/sec/Nat256.cs index 3bd329251..4e3741886 100644 --- a/crypto/src/math/ec/custom/sec/Nat256.cs +++ b/crypto/src/math/ec/custom/sec/Nat256.cs @@ -223,6 +223,15 @@ namespace Org.BouncyCastle.Math.EC.Custom.Sec return (uint)c; } + public static uint AddWord(uint x, uint[] z, int zOff) + { + Debug.Assert(zOff <= 7); + ulong c = (ulong)x + z[zOff + 0]; + z[zOff + 0] = (uint)c; + c >>= 32; + return c == 0 ? 0 : Inc(z, zOff + 1); + } + public static uint AddWordExt(uint x, uint[] zz, int zzOff) { Debug.Assert(zzOff <= 15); @@ -232,6 +241,18 @@ namespace Org.BouncyCastle.Math.EC.Custom.Sec return c == 0 ? 0 : IncExt(zz, zzOff + 1); } + public static void Copy(uint[] x, uint[] z) + { + z[0] = x[0]; + z[1] = x[1]; + z[2] = x[2]; + z[3] = x[3]; + z[4] = x[4]; + z[5] = x[5]; + z[6] = x[6]; + z[7] = x[7]; + } + public static uint[] Create() { return new uint[8]; @@ -255,6 +276,19 @@ namespace Org.BouncyCastle.Math.EC.Custom.Sec return -1; } + public static int DecExt(uint[] zz, int zzOff) + { + Debug.Assert(zzOff <= 16); + for (int i = zzOff; i < 16; ++i) + { + if (--zz[i] != uint.MaxValue) + { + return 0; + } + } + return -1; + } + public static bool Diff(uint[] x, int xOff, uint[] y, int yOff, uint[] z, int zOff) { bool pos = Gte(x, xOff, y, yOff); @@ -637,34 +671,92 @@ namespace Org.BouncyCastle.Math.EC.Custom.Sec return c; } - public static uint MulWordAddExt(uint x, uint[] yy, int yyOff, uint[] zz, int zzOff) + public static uint MulByWord(uint x, uint[] z) { - Debug.Assert(yyOff <= 8); - Debug.Assert(zzOff <= 8); ulong c = 0, xVal = x; - c += xVal * yy[yyOff + 0] + zz[zzOff + 0]; - zz[zzOff + 0] = (uint)c; + c += xVal * (ulong)z[0]; + z[0] = (uint)c; c >>= 32; - c += xVal * yy[yyOff + 1] + zz[zzOff + 1]; - zz[zzOff + 1] = (uint)c; + c += xVal * (ulong)z[1]; + z[1] = (uint)c; c >>= 32; - c += xVal * yy[yyOff + 2] + zz[zzOff + 2]; - zz[zzOff + 2] = (uint)c; + c += xVal * (ulong)z[2]; + z[2] = (uint)c; c >>= 32; - c += xVal * yy[yyOff + 3] + zz[zzOff + 3]; - zz[zzOff + 3] = (uint)c; + c += xVal * (ulong)z[3]; + z[3] = (uint)c; c >>= 32; - c += xVal * yy[yyOff + 4] + zz[zzOff + 4]; - zz[zzOff + 4] = (uint)c; + c += xVal * (ulong)z[4]; + z[4] = (uint)c; c >>= 32; - c += xVal * yy[yyOff + 5] + zz[zzOff + 5]; - zz[zzOff + 5] = (uint)c; + c += xVal * (ulong)z[5]; + z[5] = (uint)c; c >>= 32; - c += xVal * yy[yyOff + 6] + zz[zzOff + 6]; - zz[zzOff + 6] = (uint)c; + c += xVal * (ulong)z[6]; + z[6] = (uint)c; c >>= 32; - c += xVal * yy[yyOff + 7] + zz[zzOff + 7]; - zz[zzOff + 7] = (uint)c; + c += xVal * (ulong)z[7]; + z[7] = (uint)c; + c >>= 32; + return (uint)c; + } + + public static uint MulByWordAddTo(uint x, uint[] y, uint[] z) + { + ulong c = 0, xVal = x; + c += xVal * (ulong)z[0] + y[0]; + z[0] = (uint)c; + c >>= 32; + c += xVal * (ulong)z[1] + y[1]; + z[1] = (uint)c; + c >>= 32; + c += xVal * (ulong)z[2] + y[2]; + z[2] = (uint)c; + c >>= 32; + c += xVal * (ulong)z[3] + y[3]; + z[3] = (uint)c; + c >>= 32; + c += xVal * (ulong)z[4] + y[4]; + z[4] = (uint)c; + c >>= 32; + c += xVal * (ulong)z[5] + y[5]; + z[5] = (uint)c; + c >>= 32; + c += xVal * (ulong)z[6] + y[6]; + z[6] = (uint)c; + c >>= 32; + c += xVal * (ulong)z[7] + y[7]; + z[7] = (uint)c; + c >>= 32; + return (uint)c; + } + + public static uint MulWordAddTo(uint x, uint[] y, int yOff, uint[] z, int zOff) + { + ulong c = 0, xVal = x; + c += xVal * y[yOff + 0] + z[zOff + 0]; + z[zOff + 0] = (uint)c; + c >>= 32; + c += xVal * y[yOff + 1] + z[zOff + 1]; + z[zOff + 1] = (uint)c; + c >>= 32; + c += xVal * y[yOff + 2] + z[zOff + 2]; + z[zOff + 2] = (uint)c; + c >>= 32; + c += xVal * y[yOff + 3] + z[zOff + 3]; + z[zOff + 3] = (uint)c; + c >>= 32; + c += xVal * y[yOff + 4] + z[zOff + 4]; + z[zOff + 4] = (uint)c; + c >>= 32; + c += xVal * y[yOff + 5] + z[zOff + 5]; + z[zOff + 5] = (uint)c; + c >>= 32; + c += xVal * y[yOff + 6] + z[zOff + 6]; + z[zOff + 6] = (uint)c; + c >>= 32; + c += xVal * y[yOff + 7] + z[zOff + 7]; + z[zOff + 7] = (uint)c; c >>= 32; return (uint)c; } @@ -1237,6 +1329,24 @@ namespace Org.BouncyCastle.Math.EC.Custom.Sec return (int)c; } + public static int SubWord(uint x, uint[] z, int zOff) + { + Debug.Assert(zOff <= 7); + long c = (long)z[zOff + 0] - x; + z[zOff + 0] = (uint)c; + c >>= 32; + return c == 0 ? 0 : Dec(z, zOff + 1); + } + + public static int SubWordExt(uint x, uint[] zz, int zzOff) + { + Debug.Assert(zzOff <= 15); + long c = (long)zz[zzOff + 0] - x; + zz[zzOff + 0] = (uint)c; + c >>= 32; + return c == 0 ? 0 : DecExt(zz, zzOff + 1); + } + public static BigInteger ToBigInteger(uint[] x) { byte[] bs = new byte[32]; -- cgit 1.4.1