153b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giropackage org.bouncycastle.math.ec.custom.sec; 253b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro 353b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giroimport java.math.BigInteger; 453b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro 553b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giroimport org.bouncycastle.math.ec.ECFieldElement; 653b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giroimport org.bouncycastle.math.raw.Mod; 753b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giroimport org.bouncycastle.math.raw.Nat256; 853b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giroimport org.bouncycastle.util.Arrays; 953b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro 1053b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giropublic class SecP256K1FieldElement extends ECFieldElement 1153b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro{ 1253b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro public static final BigInteger Q = SecP256K1Curve.q; 1353b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro 1453b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro protected int[] x; 1553b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro 1653b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro public SecP256K1FieldElement(BigInteger x) 1753b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro { 1853b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro if (x == null || x.signum() < 0 || x.compareTo(Q) >= 0) 1953b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro { 2053b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro throw new IllegalArgumentException("x value invalid for SecP256K1FieldElement"); 2153b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro } 2253b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro 2353b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro this.x = SecP256K1Field.fromBigInteger(x); 2453b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro } 2553b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro 2653b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro public SecP256K1FieldElement() 2753b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro { 2853b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro this.x = Nat256.create(); 2953b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro } 3053b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro 3153b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro protected SecP256K1FieldElement(int[] x) 3253b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro { 3353b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro this.x = x; 3453b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro } 3553b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro 3653b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro public boolean isZero() 3753b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro { 3853b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro return Nat256.isZero(x); 3953b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro } 4053b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro 4153b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro public boolean isOne() 4253b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro { 4353b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro return Nat256.isOne(x); 4453b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro } 4553b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro 4653b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro public boolean testBitZero() 4753b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro { 4853b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro return Nat256.getBit(x, 0) == 1; 4953b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro } 5053b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro 5153b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro public BigInteger toBigInteger() 5253b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro { 5353b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro return Nat256.toBigInteger(x); 5453b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro } 5553b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro 5653b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro public String getFieldName() 5753b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro { 5853b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro return "SecP256K1Field"; 5953b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro } 6053b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro 6153b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro public int getFieldSize() 6253b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro { 6353b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro return Q.bitLength(); 6453b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro } 6553b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro 6653b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro public ECFieldElement add(ECFieldElement b) 6753b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro { 6853b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro int[] z = Nat256.create(); 6953b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro SecP256K1Field.add(x, ((SecP256K1FieldElement)b).x, z); 7053b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro return new SecP256K1FieldElement(z); 7153b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro } 7253b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro 7353b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro public ECFieldElement addOne() 7453b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro { 7553b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro int[] z = Nat256.create(); 7653b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro SecP256K1Field.addOne(x, z); 7753b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro return new SecP256K1FieldElement(z); 7853b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro } 7953b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro 8053b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro public ECFieldElement subtract(ECFieldElement b) 8153b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro { 8253b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro int[] z = Nat256.create(); 8353b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro SecP256K1Field.subtract(x, ((SecP256K1FieldElement)b).x, z); 8453b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro return new SecP256K1FieldElement(z); 8553b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro } 8653b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro 8753b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro public ECFieldElement multiply(ECFieldElement b) 8853b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro { 8953b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro int[] z = Nat256.create(); 9053b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro SecP256K1Field.multiply(x, ((SecP256K1FieldElement)b).x, z); 9153b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro return new SecP256K1FieldElement(z); 9253b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro } 9353b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro 9453b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro public ECFieldElement divide(ECFieldElement b) 9553b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro { 9653b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro// return multiply(b.invert()); 9753b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro int[] z = Nat256.create(); 9853b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro Mod.invert(SecP256K1Field.P, ((SecP256K1FieldElement)b).x, z); 9953b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro SecP256K1Field.multiply(z, x, z); 10053b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro return new SecP256K1FieldElement(z); 10153b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro } 10253b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro 10353b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro public ECFieldElement negate() 10453b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro { 10553b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro int[] z = Nat256.create(); 10653b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro SecP256K1Field.negate(x, z); 10753b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro return new SecP256K1FieldElement(z); 10853b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro } 10953b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro 11053b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro public ECFieldElement square() 11153b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro { 11253b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro int[] z = Nat256.create(); 11353b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro SecP256K1Field.square(x, z); 11453b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro return new SecP256K1FieldElement(z); 11553b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro } 11653b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro 11753b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro public ECFieldElement invert() 11853b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro { 11953b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro// return new SecP256K1FieldElement(toBigInteger().modInverse(Q)); 12053b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro int[] z = Nat256.create(); 12153b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro Mod.invert(SecP256K1Field.P, x, z); 12253b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro return new SecP256K1FieldElement(z); 12353b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro } 12453b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro 12553b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro // D.1.4 91 12653b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro /** 12753b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro * return a sqrt root - the routine verifies that the calculation returns the right value - if 12853b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro * none exists it returns null. 12953b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro */ 13053b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro public ECFieldElement sqrt() 13153b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro { 13253b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro /* 13353b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro * Raise this element to the exponent 2^254 - 2^30 - 2^7 - 2^6 - 2^5 - 2^4 - 2^2 134bdb7b3d37025690a0434040b4e0d0623d9fa74afSergio Giro * 13553b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro * Breaking up the exponent's binary representation into "repunits", we get: 13653b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro * { 223 1s } { 1 0s } { 22 1s } { 4 0s } { 2 1s } { 2 0s} 137bdb7b3d37025690a0434040b4e0d0623d9fa74afSergio Giro * 13853b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro * Therefore we need an addition chain containing 2, 22, 223 (the lengths of the repunits) 13953b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro * We use: 1, [2], 3, 6, 9, 11, [22], 44, 88, 176, 220, [223] 14053b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro */ 14153b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro 14253b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro int[] x1 = this.x; 14353b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro if (Nat256.isZero(x1) || Nat256.isOne(x1)) 14453b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro { 14553b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro return this; 14653b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro } 14753b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro 14853b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro int[] x2 = Nat256.create(); 14953b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro SecP256K1Field.square(x1, x2); 15053b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro SecP256K1Field.multiply(x2, x1, x2); 15153b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro int[] x3 = Nat256.create(); 15253b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro SecP256K1Field.square(x2, x3); 15353b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro SecP256K1Field.multiply(x3, x1, x3); 15453b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro int[] x6 = Nat256.create(); 15553b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro SecP256K1Field.squareN(x3, 3, x6); 15653b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro SecP256K1Field.multiply(x6, x3, x6); 15753b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro int[] x9 = x6; 15853b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro SecP256K1Field.squareN(x6, 3, x9); 15953b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro SecP256K1Field.multiply(x9, x3, x9); 16053b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro int[] x11 = x9; 16153b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro SecP256K1Field.squareN(x9, 2, x11); 16253b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro SecP256K1Field.multiply(x11, x2, x11); 16353b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro int[] x22 = Nat256.create(); 16453b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro SecP256K1Field.squareN(x11, 11, x22); 16553b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro SecP256K1Field.multiply(x22, x11, x22); 16653b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro int[] x44 = x11; 16753b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro SecP256K1Field.squareN(x22, 22, x44); 16853b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro SecP256K1Field.multiply(x44, x22, x44); 16953b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro int[] x88 = Nat256.create(); 17053b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro SecP256K1Field.squareN(x44, 44, x88); 17153b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro SecP256K1Field.multiply(x88, x44, x88); 17253b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro int[] x176 = Nat256.create(); 17353b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro SecP256K1Field.squareN(x88, 88, x176); 17453b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro SecP256K1Field.multiply(x176, x88, x176); 17553b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro int[] x220 = x88; 17653b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro SecP256K1Field.squareN(x176, 44, x220); 17753b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro SecP256K1Field.multiply(x220, x44, x220); 17853b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro int[] x223 = x44; 17953b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro SecP256K1Field.squareN(x220, 3, x223); 18053b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro SecP256K1Field.multiply(x223, x3, x223); 18153b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro 18253b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro int[] t1 = x223; 18353b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro SecP256K1Field.squareN(t1, 23, t1); 18453b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro SecP256K1Field.multiply(t1, x22, t1); 18553b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro SecP256K1Field.squareN(t1, 6, t1); 18653b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro SecP256K1Field.multiply(t1, x2, t1); 18753b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro SecP256K1Field.squareN(t1, 2, t1); 18853b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro 18953b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro int[] t2 = x2; 19053b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro SecP256K1Field.square(t1, t2); 19153b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro 192bdb7b3d37025690a0434040b4e0d0623d9fa74afSergio Giro return Nat256.eq(x1, t2) ? new SecP256K1FieldElement(t1) : null; 19353b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro } 19453b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro 19553b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro public boolean equals(Object other) 19653b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro { 19753b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro if (other == this) 19853b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro { 19953b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro return true; 20053b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro } 20153b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro 20253b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro if (!(other instanceof SecP256K1FieldElement)) 20353b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro { 20453b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro return false; 20553b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro } 20653b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro 20753b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro SecP256K1FieldElement o = (SecP256K1FieldElement)other; 20853b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro return Nat256.eq(x, o.x); 20953b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro } 21053b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro 21153b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro public int hashCode() 21253b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro { 21353b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro return Q.hashCode() ^ Arrays.hashCode(x, 0, 8); 21453b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro } 21553b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro} 216