Sign sometimes returns signature which has different public key when recovered

[piersonleo]

Using the parameters and the methods written in the EcdsaTest,java.

Using the test key and the hash string, these are the public key x and y I got from privateKeyToPublicKey method

x: 53146990796114829813056733591563601238408213936331413724038304017435837826920
y: 76434338188085653630521464218364491598386297924034920872845236097485883390154

After signing, I used recoverToPublicKey to try get back the public. More often than not I'd recover the correct public key, but there are cases where I got a different public key, such as these cases below,

CASE 1

sig: bd6cea5143c3c586ea02e4ab58e3daa1b7b298b1b5c14bf186f22baa4d75543a4906672d7404d757dbde468236d300393fbf3ff40a127dbbc475c60a48652ad600
left: 79298872250969353446027709424429752418003674602377958136851670065310662600385
right: 37247052021121271630952653144245420212294821942485234944157732682609664576946

CASE 2

sig: 58a94dce77bdcce0f4efc35b933dcf82a4abdd3f76eca29b45518d0bf371a4e91fe6af15f9035ebd446782368d4ccbb0ef2fead6df4b9e68ea426b011e17712f00
left: 69853301847671221124547659690583053258563360101401402166707394146518710983991
right: 73599744522784624942522889815352670358712347086030800958499296043911896763139

[jumkey]

ecdsa_java/archer/algorithm/ecdsa/Ecdsa.java

Lines 100 to 106 in 9f79ebc

	BigInteger s = sRaw.multiply(NUM[2]).compareTo(N) < 0?sRaw:N.subtract(sRaw);
	BigInteger v = y.mod(NUM[2]).xor(sRaw.multiply(NUM[2]).compareTo(N) < 0?y.mod(NUM[2]):NUM[1]);
	String rs = r.toString(16), ss = s.toString(16);
	while(ss.length() < 32)
	ss = '0'+ss;

patch

--- 
+++ 
@@ -1,7 +1,9 @@
-			BigInteger s = sRaw.multiply(NUM[2]).compareTo(N) < 0?sRaw:N.subtract(sRaw);
+			BigInteger s = sRaw.multiply(NUM[2]).compareTo(N) <= 0?sRaw:N.subtract(sRaw);
 
-			BigInteger v = y.mod(NUM[2]).xor(sRaw.multiply(NUM[2]).compareTo(N) < 0?y.mod(NUM[2]):NUM[1]);
+			BigInteger v = y.and(NUM[1]).xor(sRaw.multiply(NUM[2]).compareTo(N) <= 0?NUM[0]:NUM[1]);
 
 			String rs = r.toString(16), ss = s.toString(16);
-			while(ss.length() < 32)
+			while(rs.length() < 64)
+				rs = '0'+rs;
+			while(ss.length() < 64)
 				ss = '0'+ss;