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.Nat512; 7d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root 8d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Rootpublic class SecP521R1Field 9d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root{ 10d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root // 2^521 - 1 11d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root static final int[] P = new int[]{ 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 12d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0x1FF }; 13d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root private static final int P16 = 0x1FF; 14d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root 15d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root public static void add(int[] x, int[] y, int[] z) 16d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root { 17d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root int c = Nat.add(16, x, y, z) + x[16] + y[16]; 18d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root if (c > P16 || (c == P16 && Nat.eq(16, z, P))) 19d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root { 20d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root c += Nat.inc(16, z); 21d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root c &= P16; 22d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root } 23d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root z[16] = c; 24d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root } 25d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root 26d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root public static void addOne(int[] x, int[] z) 27d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root { 28d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root int c = Nat.inc(16, x, z) + x[16]; 29d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root if (c > P16 || (c == P16 && Nat.eq(16, z, P))) 30d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root { 31d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root c += Nat.inc(16, z); 32d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root c &= P16; 33d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root } 34d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root z[16] = c; 35d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root } 36d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root 37d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root public static int[] fromBigInteger(BigInteger x) 38d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root { 39d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root int[] z = Nat.fromBigInteger(521, x); 40d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root if (Nat.eq(17, z, P)) 41d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root { 42d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root Nat.zero(17, z); 43d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root } 44d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root return z; 45d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root } 46d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root 47d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root public static void half(int[] x, int[] z) 48d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root { 49d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root int x16 = x[16]; 50d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root int c = Nat.shiftDownBit(16, x, x16, z); 51d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root z[16] = (x16 >>> 1) | (c >>> 23); 52d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root } 53d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root 54d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root public static void multiply(int[] x, int[] y, int[] z) 55d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root { 56d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root int[] tt = Nat.create(33); 57d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root implMultiply(x, y, tt); 58d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root reduce(tt, z); 59d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root } 60d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root 61d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root public static void negate(int[] x, int[] z) 62d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root { 63d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root if (Nat.isZero(17, x)) 64d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root { 65d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root Nat.zero(17, z); 66d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root } 67d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root else 68d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root { 69d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root Nat.sub(17, P, x, z); 70d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root } 71d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root } 72d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root 73d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root public static void reduce(int[] xx, int[] z) 74d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root { 75d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root// assert xx[32] >>> 18 == 0; 76d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root 77d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root int xx32 = xx[32]; 78d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root int c = Nat.shiftDownBits(16, xx, 16, 9, xx32, z, 0) >>> 23; 79d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root c += xx32 >>> 9; 80d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root c += Nat.addTo(16, xx, z); 81d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root if (c > P16 || (c == P16 && Nat.eq(16, z, P))) 82d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root { 83d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root c += Nat.inc(16, z); 84d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root c &= P16; 85d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root } 86d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root z[16] = c; 87d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root } 88d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root 89d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root public static void reduce23(int[] z) 90d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root { 91d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root int z16 = z[16]; 92d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root int c = Nat.addWordTo(16, z16 >>> 9, z) + (z16 & P16); 93d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root if (c > P16 || (c == P16 && Nat.eq(16, z, P))) 94d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root { 95d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root c += Nat.inc(16, z); 96d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root c &= P16; 97d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root } 98d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root z[16] = c; 99d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root } 100d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root 101d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root public static void square(int[] x, int[] z) 102d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root { 103d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root int[] tt = Nat.create(33); 104d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root implSquare(x, tt); 105d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root reduce(tt, z); 106d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root } 107d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root 108d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root public static void squareN(int[] x, int n, int[] z) 109d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root { 110d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root// assert n > 0; 111d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root 112d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root int[] tt = Nat.create(33); 113d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root implSquare(x, tt); 114d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root reduce(tt, z); 115d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root 116d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root while (--n > 0) 117d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root { 118d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root implSquare(z, tt); 119d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root reduce(tt, z); 120d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root } 121d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root } 122d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root 123d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root public static void subtract(int[] x, int[] y, int[] z) 124d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root { 125d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root int c = Nat.sub(16, x, y, z) + x[16] - y[16]; 126d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root if (c < 0) 127d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root { 128d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root c += Nat.dec(16, z); 129d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root c &= P16; 130d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root } 131d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root z[16] = c; 132d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root } 133d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root 134d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root public static void twice(int[] x, int[] z) 135d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root { 136d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root int x16 = x[16]; 137d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root int c = Nat.shiftUpBit(16, x, x16 << 23, z) | (x16 << 1); 138d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root z[16] = c & P16; 139d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root } 140d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root 141d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root protected static void implMultiply(int[] x, int[] y, int[] zz) 142d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root { 143d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root Nat512.mul(x, y, zz); 144d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root 145d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root int x16 = x[16], y16 = y[16]; 146d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root zz[32] = Nat.mul31BothAdd(16, x16, y, y16, x, zz, 16) + (x16 * y16); 147d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root } 148d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root 149d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root protected static void implSquare(int[] x, int[] zz) 150d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root { 151d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root Nat512.square(x, zz); 152d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root 153d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root int x16 = x[16]; 154d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root zz[32] = Nat.mulWordAddTo(16, x16 << 1, x, 0, zz, 16) + (x16 * x16); 155d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root } 156d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root} 157