椭圆曲线上点的标量乘法
我正在NIST指定的曲线“p192”上实现Elliptic Curve Point算术运算。 出于测试目的，我已经在NIST例程文档中针对曲线p192采用了示例点。 我得到正确的答案，增加点和加倍点，但对于标量乘法，我的答案是不正确的。 由于这个原因，我无法达到
$ k^{-1}(kP) = P $ 哪里
$ k^{-1}.k = 1 mod p $
请帮我理解我犯错误的地方。
package a; import java.math.BigInteger; import java.security.spec.ECPoint; public class ScalarMultiply { private static final BigInteger ONE = new BigInteger("1");; static BigInteger TWO = new BigInteger("2"); static BigInteger p = new BigInteger("6277101735386680763835789423207666416083908700390324961279"); public static ECPoint scalmult(ECPoint P, BigInteger k){ ECPoint R =P,S = P; int length = k.bitLength(); //System.out.println("length is" + length); byte[] binarray = new byte[length]; for(int i=0;i<=length-1;i++){ binarray[i] = k.mod(TWO).byteValue(); k = k.divide(TWO); } for(int i=0;i 0;i--){ R = doublePoint(R); if(binarray[i]== 1) R = addPoint(R, S); } return R; } public static ECPoint addPoint(ECPoint r, ECPoint s) { BigInteger slope = (r.getAffineY().subtract(s.getAffineY())).multiply(r.getAffineX().subtract(s.getAffineX()).modInverse(p)).mod(p); BigInteger Xout = (slope.modPow(TWO, p).subtract(r.getAffineX())).subtract(s.getAffineX()).mod(p); BigInteger Yout = r.getAffineY().negate().mod(p); Yout = Yout.add(slope.multiply(r.getAffineX().subtract(Xout))).mod(p); ECPoint out = new ECPoint(Xout, Yout); return out; } public static ECPoint doublePoint(ECPoint r) { // TODO Auto-generated method stub BigInteger slope = (r.getAffineX().pow(2)).multiply(new BigInteger("3")); slope = slope.add(new BigInteger("3")); slope = slope.multiply((r.getAffineY().multiply(TWO)).modInverse(p)); BigInteger Xout = slope.pow(2).subtract(r.getAffineX().multiply(new BigInteger("2"))).mod(p); BigInteger Yout = (r.getAffineY().negate()).add(slope.multiply(r.getAffineX().subtract(Xout))).mod(p); ECPoint out = new ECPoint(Xout, Yout); return out; } }
主要类是
package a; import java.math.BigInteger; import java.security.spec.ECPoint; public class EccArithmetic { /** * @param args */ public static void main(String[] args) { BigInteger xs = new BigInteger("d458e7d127ae671b0c330266d246769353a012073e97acf8", 16); BigInteger ys = new BigInteger ("325930500d851f336bddc050cf7fb11b5673a1645086df3b", 16); BigInteger xt = new BigInteger ("f22c4395213e9ebe67ddecdd87fdbd01be16fb059b9753a4", 16); BigInteger yt = new BigInteger ("264424096af2b3597796db48f8dfb41fa9cecc97691a9c79", 16); ECPoint S = new ECPoint(xs,ys); ECPoint T = new ECPoint(xt,yt); // Verifying addition ECPoint Rst = ScalarMultiply.addPoint(S, T); BigInteger xst = new BigInteger ("48e1e4096b9b8e5ca9d0f1f077b8abf58e843894de4d0290", 16); // Specified value of x of point R for addition in NIST Routine example System.out.println("\nx-coordinate of point Rst is : " + Rst.getAffineX()); System.out.println("\ny-coordinate of point Rst is : " + Rst.getAffineY()); if(Rst.getAffineX().equals(xst)) System.out.println("Adding is correct"); //Verifying Doubling BigInteger xr = new BigInteger ("30c5bc6b8c7da25354b373dc14dd8a0eba42d25a3f6e6962", 16); // Specified value of x of point R for doubling in NIST Routine example BigInteger yr = new BigInteger ("0dde14bc4249a721c407aedbf011e2ddbbcb2968c9d889cf", 16); ECPoint R2s = new ECPoint(xr, yr); // Specified value of y of point R for doubling in NIST Routine example System.out.println("\nx-coordinate of point R2s is : " + R2s.getAffineX()); System.out.println("\ny-coordinate of point R2s is : " + R2s.getAffineY()); System.out.println("\nx-coordinate of calculated point is : " + ScalarMultiply.doublePoint(S).getAffineX()); System.out.println("\ny-coordinate of calculated point is : " + ScalarMultiply.doublePoint(S).getAffineY()); if(R2s.getAffineX().equals(ScalarMultiply.doublePoint(S).getAffineX())) System.out.println("Doubling is correct"); xr = new BigInteger("1faee4205a4f669d2d0a8f25e3bcec9a62a6952965bf6d31", 16); // Specified value of x of point R for scalar Multiplication in NIST Routine example yr = new BigInteger("5ff2cdfa508a2581892367087c696f179e7a4d7e8260fb06", 16); // Specified value of y of point R for scalar Multiplication in NIST Routine example ECPoint Rds = new ECPoint(xr, yr); BigInteger d = new BigInteger ("a78a236d60baec0c5dd41b33a542463a8255391af64c74ee", 16); //Rs = new ECPoint(ScalarMultiply.scalmult(S, d).getAffineX(), yr); System.out.println("\nx-coordinate of point Rds is : " + Rds.getAffineX()); System.out.println("\nx-coordinate of point Rds is : " + Rds.getAffineY()); System.out.println("\nx-coordinate of calculated point is : " + ScalarMultiply.scalmult(S, d).getAffineX()); System.out.println("\nx-coordinate of calculated point is : " + ScalarMultiply.scalmult(S, d).getAffineY()); if(Rds.getAffineX().equals(ScalarMultiply.scalmult(S, d).getAffineX())) System.out.println("Scalar Multiplication is correct"); } }
addPoint和doublePoint都不正确。 以下编辑过的JAVA代码执行双加标量乘法，并检查加法，加倍，标量乘法的结果是否正确：
ScalarMultiply.java
public class ScalarMultiply { private static final BigInteger ONE = new BigInteger("1");; static BigInteger TWO = new BigInteger("2"); static BigInteger p = new BigInteger("6277101735386680763835789423207666416083908700390324961279"); static BigInteger a = new BigInteger("6277101735386680763835789423207666416083908700390324961276"); public static ECPoint scalmult(ECPoint P, BigInteger kin){ //ECPoint R=P; - incorrect ECPoint R = ECPoint.POINT_INFINITY,S = P; BigInteger k = kin.mod(p); int length = k.bitLength(); //System.out.println("length is" + length); byte[] binarray = new byte[length]; for(int i=0;i<=length-1;i++){ binarray[i] = k.mod(TWO).byteValue(); k = k.divide(TWO); } /*for(int i = length-1;i >= 0;i--){ System.out.print("" + binarray[i]); }*/ for(int i = length-1;i >= 0;i--){ // i should start at length-1 not -2 because the MSB of binarry may not be 1 R = doublePoint(R); if(binarray[i]== 1) R = addPoint(R, S); } return R; } public static ECPoint addPoint(ECPoint r, ECPoint s) { if (r.equals(s)) return doublePoint(r); else if (r.equals(ECPoint.POINT_INFINITY)) return s; else if (s.equals(ECPoint.POINT_INFINITY)) return r; BigInteger slope = (r.getAffineY().subtract(s.getAffineY())).multiply(r.getAffineX().subtract(s.getAffineX()).modInverse(p)).mod(p); BigInteger Xout = (slope.modPow(TWO, p).subtract(r.getAffineX())).subtract(s.getAffineX()).mod(p); //BigInteger Yout = r.getAffineY().negate().mod(p); - incorrect BigInteger Yout = s.getAffineY().negate().mod(p); //Yout = Yout.add(slope.multiply(r.getAffineX().subtract(Xout))).mod(p); - incorrect Yout = Yout.add(slope.multiply(s.getAffineX().subtract(Xout))).mod(p); ECPoint out = new ECPoint(Xout, Yout); return out; } public static ECPoint doublePoint(ECPoint r) { if (r.equals(ECPoint.POINT_INFINITY)) return r; BigInteger slope = (r.getAffineX().pow(2)).multiply(new BigInteger("3")); //slope = slope.add(new BigInteger("3")); - incorrect slope = slope.add(a); slope = slope.multiply((r.getAffineY().multiply(TWO)).modInverse(p)); BigInteger Xout = slope.pow(2).subtract(r.getAffineX().multiply(TWO)).mod(p); BigInteger Yout = (r.getAffineY().negate()).add(slope.multiply(r.getAffineX().subtract(Xout))).mod(p); ECPoint out = new ECPoint(Xout, Yout); return out; }
EccArithmetic.java
public class EccArithmetic { public static void main(String[] args) { BigInteger xs = new BigInteger("d458e7d127ae671b0c330266d246769353a012073e97acf8", 16); BigInteger ys = new BigInteger("325930500d851f336bddc050cf7fb11b5673a1645086df3b", 16); BigInteger xt = new BigInteger("f22c4395213e9ebe67ddecdd87fdbd01be16fb059b9753a4", 16); BigInteger yt = new BigInteger("264424096af2b3597796db48f8dfb41fa9cecc97691a9c79", 16); ECPoint S = new ECPoint(xs,ys); ECPoint T = new ECPoint(xt,yt); // Verifying addition ECPoint Rst = ScalarMultiply.addPoint(S, T); BigInteger xst = new BigInteger("48e1e4096b9b8e5ca9d0f1f077b8abf58e843894de4d0290", 16); // Specified value of x of point R for addition in NIST Routine example System.out.println("\nx-coordinate of point Rst is : " + Rst.getAffineX()); System.out.println("\ny-coordinate of point Rst is : " + Rst.getAffineY()); if(Rst.getAffineX().equals(xst)) System.out.println("Adding is correct"); //Verifying Doubling BigInteger xr = new BigInteger("30c5bc6b8c7da25354b373dc14dd8a0eba42d25a3f6e6962", 16); // Specified value of x of point R for doubling in NIST Routine example BigInteger yr = new BigInteger("0dde14bc4249a721c407aedbf011e2ddbbcb2968c9d889cf", 16); ECPoint R2s = new ECPoint(xr, yr); // Specified value of y of point R for doubling in NIST Routine example System.out.println("\nx-coordinate of point R2s is : " + R2s.getAffineX()); System.out.println("\ny-coordinate of point R2s is : " + R2s.getAffineY()); System.out.println("\nx-coordinate of calculated point is : " + ScalarMultiply.doublePoint(S).getAffineX()); System.out.println("\ny-coordinate of calculated point is : " + ScalarMultiply.doublePoint(S).getAffineY()); if(R2s.getAffineX().equals(ScalarMultiply.doublePoint(S).getAffineX()) && R2s.getAffineY().equals(ScalarMultiply.doublePoint(S).getAffineY())) System.out.println("Doubling is correct"); xr = new BigInteger("1faee4205a4f669d2d0a8f25e3bcec9a62a6952965bf6d31", 16); // Specified value of x of point R for scalar Multiplication in NIST Routine example yr = new BigInteger("5ff2cdfa508a2581892367087c696f179e7a4d7e8260fb06", 16); // Specified value of y of point R for scalar Multiplication in NIST Routine example ECPoint Rds = new ECPoint(xr, yr); BigInteger d = new BigInteger("a78a236d60baec0c5dd41b33a542463a8255391af64c74ee", 16); ECPoint Rs = ScalarMultiply.scalmult(S, d); System.out.println("\nx-coordinate of point Rds is : " + Rds.getAffineX()); System.out.println("\ny-coordinate of point Rds is : " + Rds.getAffineY()); System.out.println("\nx-coordinate of calculated point is : " + Rs.getAffineX()); System.out.println("\ny-coordinate of calculated point is : " + Rs.getAffineY()); if(Rds.getAffineX().equals(Rs.getAffineX()) && Rds.getAffineY().equals(Rs.getAffineY())) System.out.println("Scalar Multiplication is correct"); } }
GregS在他的评论中提到a*(bP)不等于P ，因为底层字段F_q中的ab = 1 mod q 。
实际上正确的陈述是：如果ab = 1 mod n （ n是组G的顺序a*(bP)则a*(bP)等于P
ChaiaraHsieh建议的代码似乎也是正确的（只需在ScalarMultiply代码中将k = kin.mod(p)更改为k = kin.mod(n) ）。
虽然我更喜欢使用BouncyCastle。