Quote from: dabura667 on January 10, 2015, 07:09:23 AM

Quote from: Knecke on January 09, 2015, 10:14:55 PM

Hello,

i red about the flaw with reused R values in the signature of a transaction.

And i wonder if it possible that the private key is exposed when someone signs the same message with the same private key.

Remember algebra?

x + 5 = 8
Solve for x... 3 right?

What about:
x + y + 5 = 23

.... you can't tell me... can you?

However, if I told you that the SAME X and SAME Y could ALSO BE THE FOLLOWING:
x - y + 6 = 8

then you can do:
(x + y + 5) - (x - y + 6) = (23) - ( 8 )
2y - 1 = 15
2y = 16
y = 8
x - 8 + 6 = 8
x = 10

So in order to solve an equation with 2 variables you need 2 different equations that fulfill the variables. 3 for 3... 4 for 4... so on so on.

Now, signatures are just a formula that generates 2 values, r and s.

r = R.x = k x G
(where G is the generator point of the secp256k1 curve... so it is known) (R is the point gained by multiplying them, and r is that point's x value on the coordinate plane)

s = (k^-1) x (z + dr) mod N
(where k and r are from the r equation (so the same), z is the message being signed's hash, d is the private key, and N is the order of the curve (constant) )

if we see the same r value for 2 DIFFERENT transactions: (Where we know d and r are the same... AND WE KNOW k IS THE SAME since r = k x G and G never changes)
s1 - s2 = ((k^-1) x (z1 + dr)) - ((k^-1) x (z2 + dr)) mod N
s1 - s2 = (k^-1)z1 + (k^-1)dr - (k^-1)z2 - (k^-1)dr mod N
s1 - s2 = (k^-1)z1 - (k^-1)z2 mod N
k = (s1 - s2)^-1 x (z1 - z2) mod N

Since we know s1, s2 (they are in the signatures of the 2 transactions) and z1, z2 (they are the transactions themselves) we now know k.

so now we plug in:
s = (k^-1) x (z + dr) mod N
s x k = z + dr mod N
sk - z = dr mod N
d = (r^-1) x (sk - z) mod N

Since we know s, z, and r from the signature and transaction, and learned k from the solution above, we can calculate the private key.

So basically, the k value will give away your private key, and using the same r value (which means using the same k value) for two different z (transactions) allows it all to crumble down.

The solution to this is to make the k value DEPENDENT on the transaction AND the private key.

so if we generate k by performing Hash(z + d) and using that hash, if the z changes, the k WILL HAVE TO CHANGE AS WELL. same thing with if you use a different private key for a different address. because the thing being hashed will always change when the transaction changes or the private key changes, we can know that the same r value for two different transactions is impractical.

This was a very helpful way to mathematically show this.

Thank you for this.