Mnożenie skalarne punktu nad krzywą eliptyczną
Implementuję operację arytmetyczną punktu krzywej eliptycznej na określonej krzywej NIST „p192”. Dla celów testowych podałem przykładowe punkty pokazane wNIST Rutynowy dokument dla krzywej p192. Otrzymuję poprawną odpowiedź na dodanie punktu i podwojenie punktu, ale dla mnożenia skalarnego moje odpowiedzi nie są poprawne. Z tego powodu nie mogę dotrzeć do tego, czy
$ k^{-1}(kP) = P $
gdzie
$ k^{-1}.k = 1 mod p $
Pomóż mi zrozumieć, gdzie popełniam błędy.
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<=length-1;i++){
System.out.print("" + binarray[i]);
}
for(int i = length - 2;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;
}
}
Główna klasa to
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");
}
}