Elliptic Curve Digital Signature Problem~ Please help me!
I'm writing the Elliptic Curve Digital Signature Algorithm (ECDSA), but just can't get it working properly. I've followed the algorithm precisely, and also solve the problem of getting negative value when implementing hash function. But still can't work. Anyone can give me any ideas? Thanks a lot!!!
Here is the sign function, and byte[] sKey is the secret key
publicstaticbyte[] sign(byte[] msg,byte[] sKey)throws Exception{
MessageDigest md = MessageDigest.getInstance("SHA-256");
byte[] zero =newbyte[]{0};
byte[] hashTemp = md.digest(msg);
BigInteger eTemp =new BigInteger(hashTemp);
BigInteger e;
if (eTemp.signum() == -1){// if the hash value is negative, change it to positive
System.out.println("hash of msg is negative, changing it to positive...");
byte[] hash = Utils.concatenate(zero, hashTemp);// concatenate byte[] zero and hashTemp using arraycopy
e =new BigInteger(hash);
}
else
e = eTemp;
Generator g =new Generator();// class of getting base point of the curve
BigInteger p = g.getP();// The large prime number
BigInteger p1 = p.subtract(BigInteger.ONE);// p1 = p - 1
byte[] secKey = sKey;
SecureRandom sRand = SecureRandom.getInstance("SHA1PRNG","SUN");
BigInteger randK, r, s;
do{
do{
do{
randK =new BigInteger(p.bitLength(), sRand);
System.out.println("Random K is: " + randK);
}while(randK.compareTo(p1) == 1 || randK.compareTo(BigInteger.ONE) == -1);
BigInteger[][] tempKey = getPubKey(randK);// get(x, y)
r = tempKey[0][0].mod(p);// r = x (mod p)
}while(r.compareTo(BigInteger.ZERO) == 0);
BigInteger secKeyInt =new BigInteger(secKey);
BigInteger numerator = (e.add(r.multiply(secKeyInt))).mod(p);
BigInteger denominator = randK.modInverse(p);
s = (numerator.multiply(denominator)).mod(p);// s = (e + r*secKey)/k (mod p)
}while(s.compareTo(BigInteger.ZERO) == 0);
System.out.println("S is: " + s);
System.out.println("R is: " + r);
byte[] partR = r.toByteArray();
byte[] partS = s.toByteArray();
byte[] sizeR = Utils.intToBytes(partR.length);// convert int to byte[4]
return Utils.concatenate(sizeR, Utils.concatenate(partR, partS));// concatenate byte[] sizeR, partR and partS
}
Here is the verify function, bytet[] pubKey is the public key, which consists of "byte length of X", "X" and "Y" (X and Y are the coordinates of the public key point).
publicstaticboolean verify(byte[] msg,byte[] sig,byte[] pubKey)throws Exception{
Generator g =new Generator();// class of getting base point of the curve
BigInteger p = g.getP();// the large prime number used in equation
BigInteger p1 = p.subtract(BigInteger.ONE);// p1 = p - 1
BigInteger a = g.getA();
PKGen pkg =new PKGen();
BigInteger TWO =new BigInteger("2");
byte[] temp = Utils.cutFirst(sig, 4);// cut the first 4 bytes, which can be converted in to int
int sizeR = Utils.bytesToInt(temp);// convert byte[] to int
byte[] restBytes = Utils.cutSecond(sig, sig.length-4);// cut the rest of the bytes other than the first 4 bytes
byte[] partR = Utils.cutFirst(restBytes, sizeR);// cut out r
byte[] partS = Utils.cutSecond(restBytes, restBytes.length-partR.length);// cut out s
BigInteger r =new BigInteger(partR);
BigInteger s =new BigInteger(partS);
System.out.println("S is: " + s);
System.out.println("R is: " + r);
if (r.compareTo(p1) == 1 || r.compareTo(BigInteger.ONE) == -1 || s.compareTo(p1) == 1 || s.compareTo(BigInteger.ONE) == -1)
returnfalse;
else{
MessageDigest md = MessageDigest.getInstance("SHA-256");
byte[] hashTemp = md.digest(msg);
byte[] zero =newbyte[]{0};
BigInteger eTemp =new BigInteger(hashTemp);
BigInteger e;
if (eTemp.signum() == -1){// if the hash value is negative, change it to positive
System.out.println("hash of msg is negative, changing it to positive...");
byte[] hash = Utils.concatenate(zero, hashTemp);
e =new BigInteger(hash);
}
else
e = eTemp;
BigInteger w = s.modInverse(p);// w = (1/s) (mod p)
BigInteger u1 = (e.multiply(w)).mod(p);// u1 = e*w (mod p)
BigInteger u2 = (r.multiply(w)).mod(p);// u2 = r*w (mod p)
System.out.println("u1 is: " + u1);
System.out.println("u2 is: " + u2);
BigInteger[][] tempA = getPubKey(u1);
System.out.println("Finished calculating u1*G\n");
BigInteger[][] tempB =new BigInteger[1][2];
byte[] xLengthByte = Utils.cutFirst(pubKey, 4);
int partXLength = Utils.bytesToInt(xLengthByte);
byte[] restPubBytes = Utils.cutSecond(pubKey, pubKey.length-4);
byte[] partX = Utils.cutFirst(restPubBytes, partXLength);
byte[] partY = Utils.cutSecond(restPubBytes, restPubBytes.length-partXLength);
BigInteger pubX =new BigInteger(partX);
BigInteger pubY =new BigInteger(partY);
BigInteger[][] doublePub = pkg.doubleP(pubX, pubY, p, a);
if (u2.equals(BigInteger.ONE)){
tempB[0][0] = pubX;
tempB[0][1] = pubY;
}
elseif (u2.equals(TWO))
tempB = doublePub;
else
tempB = pkg.getPKey(pubX, pubY, doublePub[0][0], doublePub[0][1], u2, p, a);// get point based on G (base point), which is u2*G
BigInteger[][] sigPoint = pkg.pPlusQ(tempA[0][0], tempA[0][1], tempB[0][0], tempB[0][1], p);// point add, (P+Q)
if ((sigPoint[0][0].mod(p)).compareTo(r.mod(p)) == 0)
returntrue;
else
returnfalse;
}
}
