using System; using System.Diagnostics; using Org.BouncyCastle.Math.Raw; namespace Org.BouncyCastle.Math.EC.Custom.Sec { internal class SecT163Field { private const ulong M35 = ulong.MaxValue >> 29; private const ulong M55 = ulong.MaxValue >> 9; public static void Add(ulong[] x, ulong[] y, ulong[] z) { z[0] = x[0] ^ y[0]; z[1] = x[1] ^ y[1]; z[2] = x[2] ^ y[2]; } public static void AddExt(ulong[] xx, ulong[] yy, ulong[] zz) { zz[0] = xx[0] ^ yy[0]; zz[1] = xx[1] ^ yy[1]; zz[2] = xx[2] ^ yy[2]; zz[3] = xx[3] ^ yy[3]; zz[4] = xx[4] ^ yy[4]; zz[5] = xx[5] ^ yy[5]; } public static void AddOne(ulong[] x, ulong[] z) { z[0] = x[0] ^ 1UL; z[1] = x[1]; z[2] = x[2]; } public static ulong[] FromBigInteger(BigInteger x) { ulong[] z = Nat192.FromBigInteger64(x); Reduce29(z, 0); return z; } public static void Invert(ulong[] x, ulong[] z) { if (Nat192.IsZero64(x)) throw new InvalidOperationException(); // Itoh-Tsujii inversion with bases { 2, 3 } ulong[] t0 = Nat192.Create64(); ulong[] t1 = Nat192.Create64(); Square(x, t0); // 3 | 162 SquareN(t0, 1, t1); Multiply(t0, t1, t0); SquareN(t1, 1, t1); Multiply(t0, t1, t0); // 3 | 54 SquareN(t0, 3, t1); Multiply(t0, t1, t0); SquareN(t1, 3, t1); Multiply(t0, t1, t0); // 3 | 18 SquareN(t0, 9, t1); Multiply(t0, t1, t0); SquareN(t1, 9, t1); Multiply(t0, t1, t0); // 3 | 6 SquareN(t0, 27, t1); Multiply(t0, t1, t0); SquareN(t1, 27, t1); Multiply(t0, t1, t0); // 2 | 2 SquareN(t0, 81, t1); Multiply(t0, t1, z); } public static void Multiply(ulong[] x, ulong[] y, ulong[] z) { ulong[] tt = Nat192.CreateExt64(); ImplMultiply(x, y, tt); Reduce(tt, z); } public static void MultiplyAddToExt(ulong[] x, ulong[] y, ulong[] zz) { ulong[] tt = Nat192.CreateExt64(); ImplMultiply(x, y, tt); AddExt(zz, tt, zz); } public static void Reduce(ulong[] xx, ulong[] z) { ulong x0 = xx[0], x1 = xx[1], x2 = xx[2], x3 = xx[3], x4 = xx[4], x5 = xx[5]; x2 ^= (x5 << 29) ^ (x5 << 32) ^ (x5 << 35) ^ (x5 << 36); x3 ^= (x5 >> 35) ^ (x5 >> 32) ^ (x5 >> 29) ^ (x5 >> 28); x1 ^= (x4 << 29) ^ (x4 << 32) ^ (x4 << 35) ^ (x4 << 36); x2 ^= (x4 >> 35) ^ (x4 >> 32) ^ (x4 >> 29) ^ (x4 >> 28); x0 ^= (x3 << 29) ^ (x3 << 32) ^ (x3 << 35) ^ (x3 << 36); x1 ^= (x3 >> 35) ^ (x3 >> 32) ^ (x3 >> 29) ^ (x3 >> 28); ulong t = x2 >> 35; z[0] = x0 ^ t ^ (t << 3) ^ (t << 6) ^ (t << 7); z[1] = x1; z[2] = x2 & M35; } public static void Reduce29(ulong[] z, int zOff) { ulong z2 = z[zOff + 2], t = z2 >> 35; z[zOff ] ^= t ^ (t << 3) ^ (t << 6) ^ (t << 7); z[zOff + 2] = z2 & M35; } public static void Square(ulong[] x, ulong[] z) { ulong[] tt = Nat192.CreateExt64(); ImplSquare(x, tt); Reduce(tt, z); } public static void SquareAddToExt(ulong[] x, ulong[] zz) { ulong[] tt = Nat192.CreateExt64(); ImplSquare(x, tt); AddExt(zz, tt, zz); } public static void SquareN(ulong[] x, int n, ulong[] z) { Debug.Assert(n > 0); ulong[] tt = Nat192.CreateExt64(); ImplSquare(x, tt); Reduce(tt, z); while (--n > 0) { ImplSquare(z, tt); Reduce(tt, z); } } protected static void ImplCompactExt(ulong[] zz) { ulong z0 = zz[0], z1 = zz[1], z2 = zz[2], z3 = zz[3], z4 = zz[4], z5 = zz[5]; zz[0] = z0 ^ (z1 << 55); zz[1] = (z1 >> 9) ^ (z2 << 46); zz[2] = (z2 >> 18) ^ (z3 << 37); zz[3] = (z3 >> 27) ^ (z4 << 28); zz[4] = (z4 >> 36) ^ (z5 << 19); zz[5] = (z5 >> 45); } protected static void ImplMultiply(ulong[] x, ulong[] y, ulong[] zz) { /* * "Five-way recursion" as described in "Batch binary Edwards", Daniel J. Bernstein. */ ulong f0 = x[0], f1 = x[1], f2 = x[2]; f2 = ((f1 >> 46) ^ (f2 << 18)); f1 = ((f0 >> 55) ^ (f1 << 9)) & M55; f0 &= M55; ulong g0 = y[0], g1 = y[1], g2 = y[2]; g2 = ((g1 >> 46) ^ (g2 << 18)); g1 = ((g0 >> 55) ^ (g1 << 9)) & M55; g0 &= M55; ulong[] H = new ulong[10]; ImplMulw(f0, g0, H, 0); // H(0) 55/54 bits ImplMulw(f2, g2, H, 2); // H(INF) 55/50 bits ulong t0 = f0 ^ f1 ^ f2; ulong t1 = g0 ^ g1 ^ g2; ImplMulw(t0, t1, H, 4); // H(1) 55/54 bits ulong t2 = (f1 << 1) ^ (f2 << 2); ulong t3 = (g1 << 1) ^ (g2 << 2); ImplMulw(f0 ^ t2, g0 ^ t3, H, 6); // H(t) 55/56 bits ImplMulw(t0 ^ t2, t1 ^ t3, H, 8); // H(t + 1) 55/56 bits ulong t4 = H[6] ^ H[8]; ulong t5 = H[7] ^ H[9]; Debug.Assert(t5 >> 55 == 0); // Calculate V ulong v0 = (t4 << 1) ^ H[6]; ulong v1 = t4 ^ (t5 << 1) ^ H[7]; ulong v2 = t5; // Calculate U ulong u0 = H[0]; ulong u1 = H[1] ^ H[0] ^ H[4]; ulong u2 = H[1] ^ H[5]; // Calculate W ulong w0 = u0 ^ v0 ^ (H[2] << 4) ^ (H[2] << 1); ulong w1 = u1 ^ v1 ^ (H[3] << 4) ^ (H[3] << 1); ulong w2 = u2 ^ v2; // Propagate carries w1 ^= (w0 >> 55); w0 &= M55; w2 ^= (w1 >> 55); w1 &= M55; Debug.Assert((w0 & 1UL) == 0UL); // Divide W by t w0 = (w0 >> 1) ^ ((w1 & 1UL) << 54); w1 = (w1 >> 1) ^ ((w2 & 1UL) << 54); w2 = (w2 >> 1); // Divide W by (t + 1) w0 ^= (w0 << 1); w0 ^= (w0 << 2); w0 ^= (w0 << 4); w0 ^= (w0 << 8); w0 ^= (w0 << 16); w0 ^= (w0 << 32); w0 &= M55; w1 ^= (w0 >> 54); w1 ^= (w1 << 1); w1 ^= (w1 << 2); w1 ^= (w1 << 4); w1 ^= (w1 << 8); w1 ^= (w1 << 16); w1 ^= (w1 << 32); w1 &= M55; w2 ^= (w1 >> 54); w2 ^= (w2 << 1); w2 ^= (w2 << 2); w2 ^= (w2 << 4); w2 ^= (w2 << 8); w2 ^= (w2 << 16); w2 ^= (w2 << 32); Debug.Assert(w2 >> 52 == 0); zz[0] = u0; zz[1] = u1 ^ w0 ^ H[2]; zz[2] = u2 ^ w1 ^ w0 ^ H[3]; zz[3] = w2 ^ w1; zz[4] = w2 ^ H[2]; zz[5] = H[3]; ImplCompactExt(zz); } protected static void ImplMulw(ulong x, ulong y, ulong[] z, int zOff) { Debug.Assert(x >> 56 == 0); Debug.Assert(y >> 56 == 0); ulong[] u = new ulong[8]; //u[0] = 0; u[1] = y; u[2] = u[1] << 1; u[3] = u[2] ^ y; u[4] = u[2] << 1; u[5] = u[4] ^ y; u[6] = u[3] << 1; u[7] = u[6] ^ y; uint j = (uint)x; ulong g, h = 0, l = u[j & 3]; int k = 47; do { j = (uint)(x >> k); g = u[j & 7] ^ u[(j >> 3) & 7] << 3 ^ u[(j >> 6) & 7] << 6; l ^= (g << k); h ^= (g >> -k); } while ((k -= 9) > 0); Debug.Assert(h >> 47 == 0); z[zOff ] = l & M55; z[zOff + 1] = (l >> 55) ^ (h << 9); } protected static void ImplSquare(ulong[] x, ulong[] zz) { Interleave.Expand64To128(x[0], zz, 0); Interleave.Expand64To128(x[1], zz, 2); ulong x2 = x[2]; zz[4] = Interleave.Expand32to64((uint)x2); zz[5] = Interleave.Expand8to16((uint)(x2 >> 32)); } } }