Offtopic

[bytcoin]

3 Signatures with the same private key.
But different k ... k + 1, k + 2 and k + 3...respectively!
Nonce k next to each other...
Is a linear equation sufficient to expose the nonce k or private key?
------------------------------------------------------------------------------------------------------------

3045022100dcf17de661e280dbf62e03ef1655d1baaabc301da9fc6b29a63e52e7780c115d02202 0be91ddd5598e22fa43014172df5312275fbdb462a2e9855c7a7433138a4a9c01

Public key: 02c811f01a6182c8f6641fa692a997eebe4ea4241ead22bb3b98ae43e9d32fd32b

h(m): bb1e00d2027efd3085b83de2a3602a8ea49e0c9d5b821cd6291d5feefd410303
-----------------------------------------------------------------------------------------------------------

3045022100fe53a1f944263756330a54b2c5a1c5e8afb001e0074f067dd3e408349d2a9d6802207 cb830b967e8a9c471741aa6ed93ce0e13d37b6f74fc516264743faaa0c01d1e01

Public key: 02c811f01a6182c8f6641fa692a997eebe4ea4241ead22bb3b98ae43e9d32fd32b

h(m): 192ef21f00fe686738cebec491537207ae33844e912cd6ceeebfe4c7d0d7d22
-----------------------------------------------------------------------------------------------------------

304402203c35ea84367238515cdeebbc3a63ec2738026d12546328ff86e047fa2e0e211902204cd 1f87db944925614a67053684ff4d5a57d9ff6e05322411fcee70eb533cad401

Public key: 02c811f01a6182c8f6641fa692a997eebe4ea4241ead22bb3b98ae43e9d32fd32b

h(m): ae5cf4ee954c3af72ff5bec680d05c2470023bfcce300e9d9896737b504736e2
----------------------------------------------------------------------------------------------------------

[Coding Enthusiast]

It appears to be possible, the private key used here is

Code:

L2i3LvajQm9gpjHuYKhVgJ6sVYQECpEoaPzYQVtr637DWCLUPWQ6

We know the ECDSA equation is s = k⁻¹(e + rd_U) mod n. And we also know that k₂ = k₁ + 1. That means we have:
k₁     = s₁^-1(e₁ + r₁d_U)
k₁ + 1 = s₂^-1(e₂ + r₂d_U)
Subtracting these two gives:
1 = s₂^-1(e₂ + r₂d_U) - s₁^-1(e₁ + r₁d_U)
1 - s₂^-1e₂ + s₁^-1e₁ = s₂^-1r₂d_U - s₁^-1r₁d_U = (s₂^-1r₂ - s₁^-1r₁)d_U

And finally the private key is
d_U = (1 - s₂^-1e₂ + s₁^-1e₁) * (s₂^-1r₂ - s₁^-1r₁)^-1 (mod n)

Note that under normal circumstances when k is chosen randomly the difference between two ks is not possible to calculate based on the 2 points we have (r₁ and r₂) hence making it impossible to compute the private key even when more than one ECDSA signature is created using the same private key.
If it were any other way not just bitcoin but ECDSA would have became obsolete years ago when the first key reuse took place.

[NotATether]

You should mention that the first value in each list is the signature pair (r, s) concatenated together.

I suppose that making an equation out of K = kG would be the first idea, then we have

K = kG
L = kG + G
M = kG + 2G

And so on, but this kind of reduction not only gives us a discrete log to solve but we don't even know the curve points K,L,M which result.

So I think the best strategy, especially when you know r and s is to make an equation out of this:

s = k^-1(z + rP) mod n

And you already know P that's the private key. N is the curve order of secp256k1 and can be found by a simple google search. Z is the 256 left-most bits of h(m) i.e the SHA256 hash of the message.

Let's set z + rP = C some constant which we can calculate right now since we have enough information. But why are your h(m) values all different? That means you're signing different messages.

Then we have s = k^-1C mod n and to get k on the other side we just need to find the inverse operation of modular multiplicative inverse. That's just k = s^-1C mod n.

In other words just calculating k = s^-1(z + rP) mod n for one set of (r,s,z,P[that's your privkey],n) is sufficient to find an unknown k. No need to solve a system of three equations.

[bytcoin]

It appears to be possible, the private key used here is

Code:

L2i3LvajQm9gpjHuYKhVgJ6sVYQECpEoaPzYQVtr637DWCLUPWQ6

I think you discovered the private key because I used 2 * x from a known private key

[MixMAx123]

S1 = (h1+rx1*P)/k   =>  k = (h1+rx1*P)/S1

S2 = (h2+rx2*P)/(k+1)  =>  k+1 = (h2+rx2*P)/S2

((h1+rx1*P)/S1)  + 1 = (h2+rx2*P)/S2


.........

P = (h2*S1 - h1*S2 - S2)/(rx1*S2 - rx2*S1)

[bytcoin]

It appears to be possible, the private key used here is

Code:

L2i3LvajQm9gpjHuYKhVgJ6sVYQECpEoaPzYQVtr637DWCLUPWQ6

We know the ECDSA equation is s = k⁻¹(e + rd_U) mod n. And we also know that k₂ = k₁ + 1. That means we have:
k₁     = s₁^-1(e₁ + r₁d_U)
k₁ + 1 = s₂^-1(e₂ + r₂d_U)
Subtracting these two gives:
1 = s₂^-1(e₂ + r₂d_U) - s₁^-1(e₁ + r₁d_U)
1 - s₂^-1e₂ + s₁^-1e₁ = r₂d_U - r₁d_U = (r₂ - r₁)d_U

And finally the private key is
d_U = (1 - s₂^-1e₂ + s₁^-1e₁) * (r₂ - r₁)^-1 (mod n)

Note that under normal circumstances when k is chosen randomly the difference between two ks is not possible to calculate based on the 2 points we have (r₁ and r₂) hence making it impossible to compute the private key even when more than one ECDSA signature is created using the same private key.
If it were any other way not just bitcoin but ECDSA would have became obsolete years ago when the first key reuse took place.

I fried my brain with these calculations!

[bytcoin]

You should mention that the first value in each list is the signature pair (r, s) concatenated together.

I suppose that making an equation out of K = kG would be the first idea, then we have

K = kG
L = kG + G
M = kG + 2G

And so on, but this kind of reduction not only gives us a discrete log to solve but we don't even know the curve points K,L,M which result.

So I think the best strategy, especially when you know r and s is to make an equation out of this:

s = k^-1(z + rP) mod n

And you already know P that's the private key. N is the curve order of secp256k1 and can be found by a simple google search. Z is the 256 left-most bits of h(m) i.e the SHA256 hash of the message.

Let's set z + rP = C some constant which we can calculate right now since we have enough information. But why are your h(m) values all different? That means you're signing different messages.

Then we have s = k^-1C mod n and to get k on the other side we just need to find the inverse operation of modular multiplicative inverse. That's just k = s^-1C mod n.

In other words just calculating k = s^-1(z + rP) mod n for one set of (r,s,z,P[that's your privkey],n) is sufficient to find an unknown k. No need to solve a system of three equations.

I don't even know what L and rP means ... Another one that fried my brain

[bytcoin]

S1 = (h1+rx1*P)/k   =>  k = (h1+rx1*P)/S1

S2 = (h2+rx2*P)/(k+1)  =>  k+1 = (h2+rx2*P)/S2

((h1+rx1*P)/S1)  + 1 = (h2+rx2*P)/S2


.........

P = (h2*S1 - h1*S2 - S2)/(rx1*S2 - rx2*S1)

Now I'm starting to understand... This is a formula that I wanted to understand. Thanks to everyone for the answers !!!

[NotATether]

I don't even know what L and rP means ... Another one that fried my brain

r and P are two different values, the r obviously comes from the signature, but the P is your private key. I only picked P because I couldn't think of anything better to use. And then they are multiplied together. I guess you must have thought it was all one variable.

If your h(m) is bb1e00d2027efd3085b83de2a3602a8ea49e0c9d5b821cd6291d5feefd410303, then your L is going to be the first 256 bits of that, or just bb1e00d2027efd3085b83de2a3602a8e.

[bytcoin]

S1 = (h1+rx1*P)/k   =>  k = (h1+rx1*P)/S1

S2 = (h2+rx2*P)/(k+1)  =>  k+1 = (h2+rx2*P)/S2

((h1+rx1*P)/S1)  + 1 = (h2+rx2*P)/S2


.........

P = (h2*S1 - h1*S2 - S2)/(rx1*S2 - rx2*S1)

The result is: P = 69306650794326959231508524796612169767861406547322039836662109507876595863356
What do I do now?

[bytcoin]

S1 = (h1+rx1*P)/k   =>  k = (h1+rx1*P)/S1

S2 = (h2+rx2*P)/(k+1)  =>  k+1 = (h2+rx2*P)/S2

((h1+rx1*P)/S1)  + 1 = (h2+rx2*P)/S2


.........

P = (h2*S1 - h1*S2 - S2)/(rx1*S2 - rx2*S1)

@MixMAx123From what I understand of this equation ... the attacker must have the private key, correct?

[bytcoin]

It appears to be possible, the private key used here is

Code:

L2i3LvajQm9gpjHuYKhVgJ6sVYQECpEoaPzYQVtr637DWCLUPWQ6

We know the ECDSA equation is s = k⁻¹(e + rd_U) mod n. And we also know that k₂ = k₁ + 1. That means we have:
k₁     = s₁^-1(e₁ + r₁d_U)
k₁ + 1 = s₂^-1(e₂ + r₂d_U)
Subtracting these two gives:
1 = s₂^-1(e₂ + r₂d_U) - s₁^-1(e₁ + r₁d_U)
1 - s₂^-1e₂ + s₁^-1e₁ = r₂d_U - r₁d_U = (r₂ - r₁)d_U

And finally the private key is
d_U = (1 - s₂^-1e₂ + s₁^-1e₁) * (r₂ - r₁)^-1 (mod n)

Note that under normal circumstances when k is chosen randomly the difference between two ks is not possible to calculate based on the 2 points we have (r₁ and r₂) hence making it impossible to compute the private key even when more than one ECDSA signature is created using the same private key.
If it were any other way not just bitcoin but ECDSA would have became obsolete years ago when the first key reuse took place.

@Coding Enthusiast These calculations are confusing to me ... could you simplify these calculations, or if there is another easier method you could show me?
If you want and have time, you can send DM or contact me by telegram or email

[Coding Enthusiast]

@Coding Enthusiast These calculations are confusing to me ... could you simplify these calculations, or if there is another easier method you could show me?

Only the last equation is needed. The rest are the "proof" of how to get there:
d_U = (1 - s₂^-1e₂ + s₁^-1e₁) * (s₂^-1r₂ - s₁^-1r₁)^-1 (mod n)
(There was a small mistake which is fixed now)

d_U is the private key.
r and s are the two values in the signature.
e is the message hash converted to an integer using big-endian notation.
x^-1 is modular multiplicative inverse of x mod n
The only complication is the last one, the rest is simple multiplication, addition,...

[NotATether]

@Coding Enthusiast is e1 and e2 the full message hash or so you take the leftmost L bits first? I made a Python (3) function out of it assuming the full hash is used.

Code:

def egcd(a, b):
    "Euclidean greatest common divisor"
    if a == 0:
        return (b, 0, 1)
    else:
        g, y, x = egcd(b % a, a)
        return (g, x - (b // a) * y, y)

def modinv(a, m):
    "Modular inverse"
    # in Python 3.8 you can simply return pow(a,-1,m)
    g, x, y = egcd(a, m)
    if g != 1:
        raise Exception('modular inverse does not exist')
    else:
        return x % m

def mulmod(x,y,m):
    "Modular multiplication"
    return x*y % m

def bigendian_hex2int(hm):
    "Take a little endian hex number, make it big endian and convert it to int" 
    revstr = bytearray.fromhex(hm)
    revstr.reverse()
    bigend = int("".join([hex(a)[2:] for a in revstr]), 16)
    return bigend
 
def main():
    "This gets the Private Key given two ECDSA signatures with successive nonces"
    print("Enter all inputs as hex, without leading 0x")
    s1 = int(input("Enter first s: "), 16)
    r1 = int(input("Enter first r: "), 16)
    hm1 = input("Enter first hash message in hex: ")
    s2 = int(input("Enter second s: "), 16)
    r2 = int(input("Enter second r: "), 16)
    hm2 = input("Enter second hash message in hex: ")
    n = int(input("Enter group order (the modulus): "), 16)
    
    e1 = bigendian_hex2int(hm1)
    e2 = bigendian_hex2int(hm2)
    dU = mulmod(1 - modinv(s2, n)*e2 + modinv(s1,n)*e1, modinv(modinv(s2,n)*r2 - modinv(s1,n)*r1, n), n)
    print("Private key: " + hex(dU))

if __name__ == "__main__":
    main()

Now plug in the values or r, s and hm into here and it gives you the common private key. I couldn't figure out whether the (r,s) pairs are 32 hex characters and 256 hex chars respectively or the values OP separated with spaces in the OP are r and s.

[Coding Enthusiast]

@Coding Enthusiast is e1 and e2 the full message hash or so you take the leftmost L bits first?

In ECDSA we take leftmost log₂n bits of the hash octet string only if the log₂n < 8*hashlen. In bitcoin with secp256k1 curve and SHA256 hash the two values are equal hence the entire octet string is converted to e.

I couldn't figure out whether the (r,s) pairs are 32 hex characters and 256 hex chars respectively or the values OP separated with spaces in the OP are r and s.

The first values starting with 0x30 are DER encoded signatures.

[bytcoin]

@Coding Enthusiast These calculations are confusing to me ... could you simplify these calculations, or if there is another easier method you could show me?

Only the last equation is needed. The rest are the "proof" of how to get there:
d_U = (1 - s₂^-1e₂ + s₁^-1e₁) * (s₂^-1r₂ - s₁^-1r₁)^-1 (mod n)
(There was a small mistake which is fixed now)

d_U is the private key.
r and s are the two values in the signature.
e is the message hash converted to an integer using big-endian notation.
x^-1 is modular multiplicative inverse of x mod n
The only complication is the last one, the rest is simple multiplication, addition,...

I tried to solve the first and the second signature respectively
d_U = (1 - s₂^-1e₂ + s₁^-1e₁) * (s₂^-1r₂ - s₁^-1r₁)^-1 (mod n)
25041906913603492912629482838603148556953877974558690311897389474403233806170*
87836391163832050037286569637948589985039867162624287225605962431632613849975=
109121978011525909088360135908868503435418230507773857531730397075033675637267

The correct result:
74071287274168731384314914382498140270634658281328726941106265589917762050271

I certainly did something wrong ... I forgot to mention that I am not good at modular equation, but thanks for trying to help me. I will try to solve this equation until I get the correct result

[j2002ba2]

I tried to solve the first and the second signature respectively
d_U = (1 - s₂^-1e₂ + s₁^-1e₁) * (s₂^-1r₂ - s₁^-1r₁)^-1 (mod n)
25041906913603492912629482838603148556953877974558690311897389474403233806170*
87836391163832050037286569637948589985039867162624287225605962431632613849975=
109121978011525909088360135908868503435418230507773857531730397075033675637267

The correct result:
74071287274168731384314914382498140270634658281328726941106265589917762050271

I certainly did something wrong ... I forgot to mention that I am not good at modular equation, but thanks for trying to help me. I will try to solve this equation until I get the correct result

In decimal, modulo n (the group order):
                r₁: 99935505760319748698811422354322418311203851828465328908708024011195996180829
                s₁: 14810718830809274529170993651437030466460552688297005873719201854608653306524
                e₁: 84635513758865831094131084311208775267495704821994249663954751780286420288259
                r₂: 115035229747891778996889965749694763606205313739267493174821202115705061416296
                s₂: 56412229366601912356674994073152925730313351483910294670205660420888695151902
                e₂: 711922952377524543467576566144169816136170490747613227449590530659320692002
              s₁^-1: 49589235156255394867995584868850296899036724345858375131186053009052960413985
              s₂^-1: 75860710922369590624024015031955497020040967297713867268831531011990818769063
            s₂^-1e₂: 24319896032458654235859288439366790171987421552616806414321622974227628294346
            s₁^-1e₁: 33373073398809441106621025265904429856170478887328914010434069704980389675914
            s₂^-1r₂: 102756882304321902845902604711749179835279156262963247575454606290129811589248
            s₁^-1r₁: 109263722787838616791900575947640359553086907200677310074463510255775504782173
1 - s₂^-1e₂ + s₁^-1e₁: 9053177366350786870761736826537639684183057334712107596112446730752761381569
    s₂^-1r₂ - s₁^-1r₁: 109285248753799481477573013772796728135029813341360841883596259175872468301412
 (s₂^-1r₂ - s₁^-1r₁)^-1: 88597492899895469960154264896435952736065060080234931949365434864574123803941
                d_U: 74071287274168731384314914382498140270634658281328726941106265589917762050271

[bytcoin]

I tried to solve the first and the second signature respectively
d_U = (1 - s₂^-1e₂ + s₁^-1e₁) * (s₂^-1r₂ - s₁^-1r₁)^-1 (mod n)
25041906913603492912629482838603148556953877974558690311897389474403233806170*
87836391163832050037286569637948589985039867162624287225605962431632613849975=
109121978011525909088360135908868503435418230507773857531730397075033675637267

The correct result:
74071287274168731384314914382498140270634658281328726941106265589917762050271

I certainly did something wrong ... I forgot to mention that I am not good at modular equation, but thanks for trying to help me. I will try to solve this equation until I get the correct result

In decimal, modulo n (the group order):
                r₁: 99935505760319748698811422354322418311203851828465328908708024011195996180829
                s₁: 14810718830809274529170993651437030466460552688297005873719201854608653306524
                e₁: 84635513758865831094131084311208775267495704821994249663954751780286420288259
                r₂: 115035229747891778996889965749694763606205313739267493174821202115705061416296
                s₂: 56412229366601912356674994073152925730313351483910294670205660420888695151902
                e₂: 711922952377524543467576566144169816136170490747613227449590530659320692002
              s₁^-1: 49589235156255394867995584868850296899036724345858375131186053009052960413985
              s₂^-1: 75860710922369590624024015031955497020040967297713867268831531011990818769063
            s₂^-1e₂: 24319896032458654235859288439366790171987421552616806414321622974227628294346
            s₁^-1e₁: 33373073398809441106621025265904429856170478887328914010434069704980389675914
            s₂^-1r₂: 102756882304321902845902604711749179835279156262963247575454606290129811589248
            s₁^-1r₁: 109263722787838616791900575947640359553086907200677310074463510255775504782173
1 - s₂^-1e₂ + s₁^-1e₁: 9053177366350786870761736826537639684183057334712107596112446730752761381569
    s₂^-1r₂ - s₁^-1r₁: 109285248753799481477573013772796728135029813341360841883596259175872468301412
 (s₂^-1r₂ - s₁^-1r₁)^-1: 88597492899895469960154264896435952736065060080234931949365434864574123803941
                d_U: 74071287274168731384314914382498140270634658281328726941106265589917762050271

@j2002ba2 Perfect!!!
Thank you very much!