1d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Rootpackage org.bouncycastle.math.ec.custom.sec; 2d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root 3d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Rootimport java.math.BigInteger; 4d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root 5d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Rootimport org.bouncycastle.math.raw.Nat; 6d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Rootimport org.bouncycastle.math.raw.Nat256; 7d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root 8d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Rootpublic class SecP256K1Field 9d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root{ 10d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root // 2^256 - 2^32 - 2^9 - 2^8 - 2^7 - 2^6 - 2^4 - 1 11d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root static final int[] P = new int[]{ 0xFFFFFC2F, 0xFFFFFFFE, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 12d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root 0xFFFFFFFF, 0xFFFFFFFF }; 13d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root static final int[] PExt = new int[]{ 0x000E90A1, 0x000007A2, 0x00000001, 0x00000000, 0x00000000, 14d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root 0x00000000, 0x00000000, 0x00000000, 0xFFFFF85E, 0xFFFFFFFD, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 15d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root 0xFFFFFFFF, 0xFFFFFFFF }; 16d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root private static final int[] PExtInv = new int[]{ 0xFFF16F5F, 0xFFFFF85D, 0xFFFFFFFE, 0xFFFFFFFF, 0xFFFFFFFF, 17d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0x000007A1, 0x00000002 }; 18d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root private static final int P7 = 0xFFFFFFFF; 19d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root private static final int PExt15 = 0xFFFFFFFF; 20d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root private static final int PInv33 = 0x3D1; 21d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root 22d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root public static void add(int[] x, int[] y, int[] z) 23d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root { 24d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root int c = Nat256.add(x, y, z); 25d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root if (c != 0 || (z[7] == P7 && Nat256.gte(z, P))) 26d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root { 27d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root Nat.add33To(8, PInv33, z); 28d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root } 29d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root } 30d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root 31d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root public static void addExt(int[] xx, int[] yy, int[] zz) 32d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root { 33d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root int c = Nat.add(16, xx, yy, zz); 34d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root if (c != 0 || (zz[15] == PExt15 && Nat.gte(16, zz, PExt))) 35d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root { 36d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root if (Nat.addTo(PExtInv.length, PExtInv, zz) != 0) 37d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root { 38d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root Nat.incAt(16, zz, PExtInv.length); 39d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root } 40d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root } 41d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root } 42d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root 43d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root public static void addOne(int[] x, int[] z) 44d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root { 45d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root int c = Nat.inc(8, x, z); 46d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root if (c != 0 || (z[7] == P7 && Nat256.gte(z, P))) 47d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root { 48d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root Nat.add33To(8, PInv33, z); 49d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root } 50d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root } 51d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root 52d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root public static int[] fromBigInteger(BigInteger x) 53d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root { 54d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root int[] z = Nat256.fromBigInteger(x); 55d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root if (z[7] == P7 && Nat256.gte(z, P)) 56d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root { 57d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root Nat256.subFrom(P, z); 58d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root } 59d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root return z; 60d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root } 61d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root 62d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root public static void half(int[] x, int[] z) 63d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root { 64d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root if ((x[0] & 1) == 0) 65d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root { 66d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root Nat.shiftDownBit(8, x, 0, z); 67d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root } 68d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root else 69d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root { 70d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root int c = Nat256.add(x, P, z); 71d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root Nat.shiftDownBit(8, z, c); 72d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root } 73d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root } 74d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root 75d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root public static void multiply(int[] x, int[] y, int[] z) 76d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root { 77d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root int[] tt = Nat256.createExt(); 78d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root Nat256.mul(x, y, tt); 79d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root reduce(tt, z); 80d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root } 81d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root 82d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root public static void multiplyAddToExt(int[] x, int[] y, int[] zz) 83d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root { 84d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root int c = Nat256.mulAddTo(x, y, zz); 85d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root if (c != 0 || (zz[15] == PExt15 && Nat.gte(16, zz, PExt))) 86d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root { 87d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root if (Nat.addTo(PExtInv.length, PExtInv, zz) != 0) 88d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root { 89d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root Nat.incAt(16, zz, PExtInv.length); 90d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root } 91d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root } 92d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root } 93d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root 94d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root public static void negate(int[] x, int[] z) 95d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root { 96d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root if (Nat256.isZero(x)) 97d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root { 98d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root Nat256.zero(z); 99d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root } 100d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root else 101d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root { 102d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root Nat256.sub(P, x, z); 103d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root } 104d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root } 105d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root 106d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root public static void reduce(int[] xx, int[] z) 107d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root { 108d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root long cc = Nat256.mul33Add(PInv33, xx, 8, xx, 0, z, 0); 109d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root int c = Nat256.mul33DWordAdd(PInv33, cc, z, 0); 110d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root 111d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root // assert c == 0L || c == 1L; 112d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root 113d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root if (c != 0 || (z[7] == P7 && Nat256.gte(z, P))) 114d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root { 115d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root Nat.add33To(8, PInv33, z); 116d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root } 117d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root } 118d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root 119d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root public static void reduce32(int x, int[] z) 120d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root { 121d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root if ((x != 0 && Nat256.mul33WordAdd(PInv33, x, z, 0) != 0) 122d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root || (z[7] == P7 && Nat256.gte(z, P))) 123d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root { 124d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root Nat.add33To(8, PInv33, z); 125d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root } 126d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root } 127d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root 128d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root public static void square(int[] x, int[] z) 129d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root { 130d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root int[] tt = Nat256.createExt(); 131d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root Nat256.square(x, tt); 132d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root reduce(tt, z); 133d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root } 134d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root 135d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root public static void squareN(int[] x, int n, int[] z) 136d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root { 137d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root// assert n > 0; 138d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root 139d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root int[] tt = Nat256.createExt(); 140d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root Nat256.square(x, tt); 141d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root reduce(tt, z); 142d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root 143d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root while (--n > 0) 144d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root { 145d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root Nat256.square(z, tt); 146d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root reduce(tt, z); 147d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root } 148d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root } 149d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root 150d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root public static void subtract(int[] x, int[] y, int[] z) 151d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root { 152d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root int c = Nat256.sub(x, y, z); 153d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root if (c != 0) 154d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root { 155d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root Nat.sub33From(8, PInv33, z); 156d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root } 157d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root } 158d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root 159d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root public static void subtractExt(int[] xx, int[] yy, int[] zz) 160d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root { 161d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root int c = Nat.sub(16, xx, yy, zz); 162d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root if (c != 0) 163d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root { 164d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root if (Nat.subFrom(PExtInv.length, PExtInv, zz) != 0) 165d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root { 166d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root Nat.decAt(16, zz, PExtInv.length); 167d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root } 168d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root } 169d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root } 170d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root 171d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root public static void twice(int[] x, int[] z) 172d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root { 173d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root int c = Nat.shiftUpBit(8, x, 0, z); 174d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root if (c != 0 || (z[7] == P7 && Nat256.gte(z, P))) 175d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root { 176d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root Nat.add33To(8, PInv33, z); 177d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root } 178d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root } 179d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root} 180