Getting key from duplicate r

[bitdrain]

Hi,

I was studying the old vulnerability that was introduced by reusing a same R when signing with the same key. I am able to proof this works for a large set of examples.

However, I have these 2 example transactions:
fae3e414425f008196f9127a01dcea59e22ab66768ce5bcb4aba260993494de1
ab1deb8544de4bb1d3319e67b1bfc354601406d4a00ecbe8cbdd7674f96e9699

that both have spent from 14tVK2JhEPsZEL7yYzMNXDYQ6dG3FnzzEY with exactly the same R value.

I get z1 and z2 in the same way (using the unlock script instead of signature and putting scripts of irrelevant inputs to 0 length). the resulting values I get are:

r    :9ac20335eb38768d2052be1dbbc3c8f6178407458e51e6b4ad22f1d91758895b
s1 : 2da94e7cb83e17d307d46c80df4f3315b17af13c4a04ef352495f1442562a290
s2 : 43273c2390b15bbe7e4d38559b1d4e6c0d63aad2c586652ec423d851df065271
z1 : 068fbde1dd7e06f4e88ae63a50f8ee07eff41c4b9586cbef1235b83281ab145d
z2 : 015b14bdc6f69058bfa8dcdc0e8bcd1fc87f4303804f200bfa6aadf627a8d5f6

This however does not result (doing inverse((r*(s2-s1)),p)) in the private key linked to 14tVK2JhEPsZEL7yYzMNXDYQ6dG3FnzzEY. I'm curious as to why this example deviates from the rest and does not work as expected. I assume my math is wrong somewhere, but since it works for many other cases I'm a bit confused and especially curious if someone knows if my values are correct here or what obvious things I could be missing.

[nc50lc]

-snip- and especially curious if someone knows if my values are correct here or what obvious things I could be missing.

All seem good except the R value is missing its first byte 0x00.
Based from the signature, its length should be 33 bytes which includes the omitted 0x00 on its front.

By the way, I didn't computed the private key, I just pointed out the missing byte.

[bitdrain]

All seem good except the R value is missing its first byte 0x00.

Thanks for pointing this out, I left it out here but it was present.

For the calculated key, these leading zeroes don't not seem to matter though. So it must be something else.

[hexan123]

     R: 009ac20335eb38768d2052be1dbbc3c8f6178407458e51e6b4ad22f1d91758895b
     S1: 16c91427cb20a7321029c311e757dfee67f5e3f9bad23266fad8bf8aaf5cac01
     Z1: e69364d551385880ddbb19338b633e2d6c17f1922817b3e3776851780b6aacb5
     S2: 43273c2390b15bbe7e4d38559b1d4e6c0d63aad2c586652ec423d851df065271
     Z2: 015b14bdc6f69058bfa8dcdc0e8bcd1fc87f4303804f200bfa6aadf627a8d5f6
PubKey: 036ee29b13e9d9f060d078bdcee464cb21aeafe5b5bc15206c5fa3c62f882c97c9

[amaclin1]

Code:

const MyKey32 R  ( QByteArray::fromHex( "9ac20335eb38768d2052be1dbbc3c8f6178407458e51e6b4ad22f1d91758895b" ) );
const MyKey32 S1 ( QByteArray::fromHex( "2da94e7cb83e17d307d46c80df4f3315b17af13c4a04ef352495f1442562a290" ) );
const MyKey32 Z1 ( QByteArray::fromHex( "068fbde1dd7e06f4e88ae63a50f8ee07eff41c4b9586cbef1235b83281ab145d" ) );
const MyKey32 S2 ( QByteArray::fromHex( "43273c2390b15bbe7e4d38559b1d4e6c0d63aad2c586652ec423d851df065271" ) );
const MyKey32 Z2 ( QByteArray::fromHex( "015b14bdc6f69058bfa8dcdc0e8bcd1fc87f4303804f200bfa6aadf627a8d5f6" ) );
const MyKey20 addr ( MyKey20::of ( "14tVK2JhEPsZEL7yYzMNXDYQ6dG3FnzzEY" ) );
const MyKey32 priv ( MyKey32::getPrivateKey ( R, S1, Z1, S2, Z2, addr ) );
_trace ( priv.toHex ( ) );

const MyKey32 MyKey32::getPrivateKey ( const MyKey32& r, const MyKey32& s1, const MyKey32& z1, const MyKey32& s2, const MyKey32& z2, const MyKey20& addr )
{ 
  // private key = (z1*s2 - z2*s1)/(r*(s1-s2))
  [skip]
}

....aaaaaaand the result is "9674578d05e0bc65284cc4db99420957858e1f57505baebb1d0d3e0d25957b7c"

hint: try to use ( ORDER - S1 ) instead of S1

[bitdrain]

hint: try to use ( ORDER - S1 ) instead of S1

oh that's it indeed! Thanks.

So I understand now we take the inverse of S1 in this case, but is there a general rule as to when this happens? Is this when S goes beyond some boundary?

[cyberzzz]

#Python3

from fastecdsa.curve import secp256k1
from fastecdsa.point import Point

def extended_gcd(aa, bb):
    lastremainder, remainder = abs(aa), abs(bb)
    x, lastx, y, lasty = 0, 1, 1, 0
    while remainder:
        lastremainder, (quotient, remainder) = remainder, divmod(lastremainder, remainder)
        x, lastx = lastx - quotient*x, x
        y, lasty = lasty - quotient*y, y
    return lastremainder, lastx * (-1 if aa < 0 else 1), lasty * (-1 if bb < 0 else 1)

def modinv(a, m):
    g, x, y = extended_gcd(a, m)
    if g != 1:
        raise ValueError
    return x % m


def sqrt_mod(a, p):
    if pow(a, (p - 1) // 2, p) != 1:
        raise ValueError(f"No square root exists for {a} modulo {p}")
    if p % 4 == 3:
        return pow(a, (p + 1) // 4, p)
    raise ValueError("Cannot find square root for this modulus with current method")

def pub2point(pub_hex):
    x = int(pub_hex[2:66], 16)
    if len(pub_hex) < 70:
        prefix = int(pub_hex[:2], 16)
        y_square = (x**3 + secp256k1.a * x + secp256k1.b) % secp256k1.p
        y = sqrt_mod(y_square, secp256k1.p)
        if (y % 2 == 0 and prefix == 3) or (y % 2 == 1 and prefix == 2):
            y = secp256k1.p - y
    else:
        y = int(pub_hex[66:], 16)
   
    return Point(x, y, curve=secp256k1)

Q = "034903acabebcd2185bd64afa44632af51813c4ef25d34b3310d0018271c73f122"
Q = pub2point(Q)

n = 0xfffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364141
G = secp256k1.G

r = 0x9ac20335eb38768d2052be1dbbc3c8f6178407458e51e6b4ad22f1d91758895b
s2 = 0x2da94e7cb83e17d307d46c80df4f3315b17af13c4a04ef352495f1442562a290
z2 = 0x68fbde1dd7e06f4e88ae63a50f8ee07eff41c4b9586cbef1235b83281ab145d
s1 = 0x43273c2390b15bbe7e4d38559b1d4e6c0d63aad2c586652ec423d851df065271
z1 = 0x15b14bdc6f69058bfa8dcdc0e8bcd1fc87f4303804f200bfa6aadf627a8d5f6

try:
    doubler1 = ((z2 * s1 - z1 * s2) * modinv(r * (s2 - s1), n)) % n
    doubler2 = ((z2 * (-s1) - z1 * s2) * modinv(r * (s2 + s1), n)) % n
   
    if Q == doubler1 * G:
        print(f"Double R : ( X = 0x{hex(doubler1)[2:].zfill(64)} )")
    else:
        print(f"Double R : ( X = 0x{hex(doubler2)[2:].zfill(64)} )")
except ValueError as e:
    print(f"An error occurred in modular inversion: {e}")

[COBRAS]

#Python3

from fastecdsa.curve import secp256k1
from fastecdsa.point import Point

def extended_gcd(aa, bb):
    lastremainder, remainder = abs(aa), abs(bb)
    x, lastx, y, lasty = 0, 1, 1, 0
    while remainder:
        lastremainder, (quotient, remainder) = remainder, divmod(lastremainder, remainder)
        x, lastx = lastx - quotient*x, x
        y, lasty = lasty - quotient*y, y
    return lastremainder, lastx * (-1 if aa < 0 else 1), lasty * (-1 if bb < 0 else 1)

def modinv(a, m):
    g, x, y = extended_gcd(a, m)
    if g != 1:
        raise ValueError
    return x % m


def sqrt_mod(a, p):
    if pow(a, (p - 1) // 2, p) != 1:
        raise ValueError(f"No square root exists for {a} modulo {p}")
    if p % 4 == 3:
        return pow(a, (p + 1) // 4, p)
    raise ValueError("Cannot find square root for this modulus with current method")

def pub2point(pub_hex):
    x = int(pub_hex[2:66], 16)
    if len(pub_hex) < 70:
        prefix = int(pub_hex[:2], 16)
        y_square = (x**3 + secp256k1.a * x + secp256k1.b) % secp256k1.p
        y = sqrt_mod(y_square, secp256k1.p)
        if (y % 2 == 0 and prefix == 3) or (y % 2 == 1 and prefix == 2):
            y = secp256k1.p - y
    else:
        y = int(pub_hex[66:], 16)
   
    return Point(x, y, curve=secp256k1)

Q = "034903acabebcd2185bd64afa44632af51813c4ef25d34b3310d0018271c73f122"
Q = pub2point(Q)

n = 0xfffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364141
G = secp256k1.G

r = 0x9ac20335eb38768d2052be1dbbc3c8f6178407458e51e6b4ad22f1d91758895b
s2 = 0x2da94e7cb83e17d307d46c80df4f3315b17af13c4a04ef352495f1442562a290
z2 = 0x68fbde1dd7e06f4e88ae63a50f8ee07eff41c4b9586cbef1235b83281ab145d
s1 = 0x43273c2390b15bbe7e4d38559b1d4e6c0d63aad2c586652ec423d851df065271
z1 = 0x15b14bdc6f69058bfa8dcdc0e8bcd1fc87f4303804f200bfa6aadf627a8d5f6

try:
    doubler1 = ((z2 * s1 - z1 * s2) * modinv(r * (s2 - s1), n)) % n
    doubler2 = ((z2 * (-s1) - z1 * s2) * modinv(r * (s2 + s1), n)) % n
   
    if Q == doubler1 * G:
        print(f"Double R : ( X = 0x{hex(doubler1)[2:].zfill(64)} )")
    else:
        print(f"Double R : ( X = 0x{hex(doubler2)[2:].zfill(64)} )")
except ValueError as e:
    print(f"An error occurred in modular inversion: {e}")

Hi
can you modyfy r,ang get r,s,z, for same pubkey ?