Menu
I am implementing Elliptic Curve Point arithmetic operation on NIST specified curve "p192". For testing purpose I have taken example points shown in NIST Routine document for the curve p192. I am getting correct answer for addition of point and doubling of point but for scalar multiplication my answers are not correct. Due to this reason I am unable to reach whether
$ k^{-1}(kP) = P $
where
$ k^{-1}.k = 1 mod p $
Please help me to understand where I am making mistakes.
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;
}
}
The main Class is
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");
}
}
824
Both addPoint and doublePoint are incorrect. The following edited JAVA code does the double-and-add scalar multiplication, and check whether the results of adding, doubling, scalar multiplying are correct:
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");
}
}
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
