Nonce k and k +1 (ECDSA SIGNATURE)

[bytcoin]

I was informed that the same private key using k and k + 1 respectively in two different signatures was vulnerable ... I think that not all signatures generated in this way are vulnerable!
These two signatures were generated by the same private key and with nonces k and k + 1 respectively! Is there a formula or equation to make them vulnerable?

sig = 1
3045022100dcf17de661e280dbf62e03ef1655d1baaabc301da9fc6b29a63e52e7780c115d02202 0be91ddd5598e22fa43014172df5312275fbdb462a2e9855c7a7433138a4a9c01

Public key: 02c811f01a6182c8f6641fa692a997eebe4ea4241ead22bb3b98ae43e9d32fd32b

h(m): bb1e00d2027efd3085b83de2a3602a8ea49e0c9d5b821cd6291d5feefd410303

-------------------------------------------------------------------------------------------------------------------------------
sig = 2
3045022100fe53a1f944263756330a54b2c5a1c5e8afb001e0074f067dd3e408349d2a9d6802210 0a790cba1e3b60e8a75de69efd7e7af1bf0e2543137da79aed2d6409616120c3b01

Public key: 02c811f01a6182c8f6641fa692a997eebe4ea4241ead22bb3b98ae43e9d32fd32b

h(m): 3be295398c9e7048e32c7a30d413f82d7f8b3029ab37d110181744fe0acab452

--------------------------------------------------------------------------------------------------------------------------------

h1 = 84635513758865831094131084311208775267495704821994249663954751780286420288259
r1 = 99935505760319748698811422354322418311203851828465328908708024011195996180829
s1 = 14810718830809274529170993651437030466460552688297005873719201854608653306524
h2 = 27086795414784162292297506376302057554366609881154614249233399373002336547922
r2 = 115035229747891778996889965749694763606205313739267493174821202115705061416296
s2 = 75792077109774170129890375817094910949609540422199126584222852124036872408123

[mamuu]

r1/s1 mod order = r2/s2 mod order

it's same signature, no diffrent signature

Code:

k1 == 109263722787838616791900575947640359553086907200677310074463510255775504782173*x + 33373073398809441106621025265904429856170478887328914010434069704980389675914
k2 == 109263722787838616791900575947640359553086907200677310074463510255775504782173*x + 33373073398809441106621025265904429856170478887328914010434069704980389675915

sage: r1/s1%N
109263722787838616791900575947640359553086907200677310074463510255775504782173

sage: r2/s2%N
109263722787838616791900575947640359553086907200677310074463510255775504782173

[MixMAx123]

If k is not random, like here, the private key is exposed. It can be easily calculated here!
And I've already calculated this on a similar thread.
There is no need for a formula to make these transactions vulnerable, because the gate is already open here!

[BurtW]

Please check my work but I think that if you know k is being incremented then you can simply calculate the private key.

All of the variables and terminology in this post are from https://en.wikipedia.org/wiki/Elliptic_Curve_Digital_Signature_Algorithm

Given two different messages with two different signatures we have:

First message and signature (m, r, s)
Second message and signature (m', r', s')

From each message we can derive the z value (hash of the message) so:

First message and signature (m, r, s, z)
Second message and signature (m', r', s', z')

Therefore:  ks = z + rd_A and k's' = z' + r'd_A

Therefore:  (sk - z)/r = (s'k' - z')/r'

But in this case k' = k + 1 so:

(sk - z)/r = (s'(k + 1) - z')/r'

So all you have to do is solve for k.  All the other values:  s, z, r, s', z', and r' are all known.

(sk - z)/r = (s'(k + 1) - z')/r'

rr'[(sk - z)/r] = rr'[(s'(k + 1) - z')/r']

r'(sk - z) = r(s'(k + 1) - z')

r'sk - r'z = rs'(k + 1) - rz'

r'sk - r'z = rs'k + rs' - rz'

r'sk - rs'k = r'z + rs' - rz'

k(r's - rs') = r'z + rs' - rz'

k = (r'z + rs' - rz') / (r's - rs') all mod operations, of course.

Once you know k you can simply calculate the private key, d_A


Also note that any scheme where k' = k + n is vulnerable, n does not have to be just one.

[bytcoin]

r1/s1 mod order = r2/s2 mod order

it's same signature, no diffrent signature

Code:

k1 == 109263722787838616791900575947640359553086907200677310074463510255775504782173*x + 33373073398809441106621025265904429856170478887328914010434069704980389675914
k2 == 109263722787838616791900575947640359553086907200677310074463510255775504782173*x + 33373073398809441106621025265904429856170478887328914010434069704980389675915

sage: r1/s1%N
109263722787838616791900575947640359553086907200677310074463510255775504782173

sage: r2/s2%N
109263722787838616791900575947640359553086907200677310074463510255775504782173

My knowledge is limited, but I think 2 signatures with different h (m) r and s ... are not the same signature

[bytcoin]

If k is not random, like here, the private key is exposed. It can be easily calculated here!
And I've already calculated this on a similar thread.
There is no need for a formula to make these transactions vulnerable, because the gate is already open here!

The private key of these signatures is already known ... but no equation, formula or algebra is known to calculate these 2 signatures

[bytcoin]

Please check my work but I think that if you know k is being incremented then you can simply calculate the private key.

All of the variables and terminology in this post are from https://en.wikipedia.org/wiki/Elliptic_Curve_Digital_Signature_Algorithm

Given two different messages with two different signatures we have:

First message and signature (m, r, s)
Second message and signature (m', r', s')

From each message we can derive the z value (hash of the message) so:

First message and signature (m, r, s, z)
Second message and signature (m', r', s', z')

Therefore:  ks = z + rd_A and k's' = z' + r'd_A

Therefore:  (sk - z)/r = (s'k' - z')/r'

But in this case k' = k + 1 so:

(sk - z)/r = (s'(k + 1) - z')/r'

So all you have to do is solve for k.  All the other values:  s, z, r, s', z', and r' are all known.

(sk - z)/r = (s'(k + 1) - z')/r'

rr'[(sk - z)/r] = rr'[(s'(k + 1) - z')/r']

r'(sk - z) = r(s'(k + 1) - z')

r'sk - r'z = rs'(k + 1) - rz'

r'sk - r'z = rs'k + rs' - rz'

r'sk - rs'k = r'z + rs' - rz'

k(r's - rs') = r'z + rs' - rz'

k = (r'z + rs' - rz') / (r's - rs') all mod operations, of course.

Once you know k you can simply calculate the private key, d_A


Also note that any scheme where k' = k + n is vulnerable, n does not have to be just one.

Does not work for this 2 signatures

[MixMAx123]

If k is not random, like here, the private key is exposed. It can be easily calculated here!
And I've already calculated this on a similar thread.
There is no need for a formula to make these transactions vulnerable, because the gate is already open here!

The private key of these signatures is already known ... but no equation, formula or algebra is known to calculate these 2 signatures

Sure it's possible! The result of the calculation of signatures is only: "true" or "false".
The calculation bases for signatures are well known. It is the main task of checking the signature of every Bitcoin node, which is done 100 times per second. Your shown signatures can also be checked in this way.
The formula for this has been shown to you several times by many users and me, as well as it has been calculated here for you.
I cannot follow you and understand which questions are still unanswered for you.

[BurtW]

Please check my work but I think that if you know k is being incremented then you can simply calculate the private key.

All of the variables and terminology in this post are from https://en.wikipedia.org/wiki/Elliptic_Curve_Digital_Signature_Algorithm

Given two different messages with two different signatures we have:

First message and signature (m, r, s)
Second message and signature (m', r', s')

From each message we can derive the z value (hash of the message) so:

First message and signature (m, r, s, z)
Second message and signature (m', r', s', z')

Therefore:  ks = z + rd_A and k's' = z' + r'd_A

Therefore:  (sk - z)/r = (s'k' - z')/r'

But in this case k' = k + 1 so:

(sk - z)/r = (s'(k + 1) - z')/r'

So all you have to do is solve for k.  All the other values:  s, z, r, s', z', and r' are all known.

(sk - z)/r = (s'(k + 1) - z')/r'

rr'[(sk - z)/r] = rr'[(s'(k + 1) - z')/r']

r'(sk - z) = r(s'(k + 1) - z')

r'sk - r'z = rs'(k + 1) - rz'

r'sk - r'z = rs'k + rs' - rz'

r'sk - rs'k = r'z + rs' - rz'

k(r's - rs') = r'z + rs' - rz'

k = (r'z + rs' - rz') / (r's - rs') all mod operations, of course.

Once you know k you can simply calculate the private key, d_A


Also note that any scheme where k' = k + n is vulnerable, n does not have to be just one.

Does not work for this 2 signatures

Did you do all the operations mod n where n is the bit length of the group order?

I really think this should work, unless I made a mistake in my math.  Did you double check all my algebra?

I believe I wasted my time since there is a perfectly good solution/proof that shows how easy it is to get the private key if you know the relationship between the two k values in your other thread here:

https://bitcointalk.org/index.php?topic=5316741.msg56347059#msg56347059

[Coding Enthusiast]

I really think this should work, unless I made a mistake in my math.  Did you double check all my algebra?

The problem is that with these specific values given in OP it is not possible to compute this particular case.
Whether you use my equation in that other topic to directly compute the private key (d_u) or first compute k with your equation here then compute private key from there, you'll get 0 which you can't compute its modular multiplicative inverse (ax ≡ 1 (mod m) where a=0 doesn't have an answer).
To be specific:
s₂^-1r₂ - s₁^-1r₁ = 0
Also
r's - rs' = 0

[gmaxwell]

It's not really an ecdsa signature if you're just handed a hash.  Performing the hashing is integral to the process and without it you can generate all sorts of degenerate examples. ... including 'forged' 'signatures' for pubkeys where no one knows the private key.

[NotATether]

By revealing k, you have already made its private key vulnerable to calculate. (And I already showed you how in the thread Coding Enthusiast linked.)

That's the reason why ECDSA specifically requires that a cryptographically secure nonce k has to be chosen and not something trivial such as k+1 or k mod [some prime] or even some pseudorandom generator that derives two successive k without resetting the seed. If you use anything other than a true RNG to get k then it will always be computationally feasible to find some formula that takes two successively generated k values and the algorithm that generates the next k, that runs in polynomial time.

By definition, if you can reverse a cryptographic algorithm in polynomial time then that itself is a vulnerability.

EDIT: and to answer the question in your other thread (you didn't have to make another one), no you cannot, because the only equation in ECDSA that uses the private key, s = k^-1(z + rd_A), has an unknown k, and you can't derive the private key from a signature without it which is exactly why you're supposed to securely generate your nonce.

[bytcoin]

If k is not random, like here, the private key is exposed. It can be easily calculated here!
And I've already calculated this on a similar thread.
There is no need for a formula to make these transactions vulnerable, because the gate is already open here!

The private key of these signatures is already known ... but no equation, formula or algebra is known to calculate these 2 signatures

Sure it's possible! The result of the calculation of signatures is only: "true" or "false".
The calculation bases for signatures are well known. It is the main task of checking the signature of every Bitcoin node, which is done 100 times per second. Your shown signatures can also be checked in this way.
The formula for this has been shown to you several times by many users and me, as well as it has been calculated here for you.
I cannot follow you and understand which questions are still unanswered for you.

@MixMAx123 When I said to calculate the 2 signatures ... I was referring to the calculation to find k or x

[bytcoin]

I really think this should work, unless I made a mistake in my math.  Did you double check all my algebra?

The problem is that with these specific values given in OP it is not possible to compute this particular case.
Whether you use my equation in that other topic to directly compute the private key (d_u) or first compute k with your equation here then compute private key from there, you'll get 0 which you can't compute its modular multiplicative inverse (ax ≡ 1 (mod m) where a=0 doesn't have an answer).
To be specific:
s₂^-1r₂ - s₁^-1r₁ = 0
Also
r's - rs' = 0

@Coding Enthusiast Exactly! I believe that nobody knows any formula or equation or algebra or magic that solves this

[bytcoin]

It's not really an ecdsa signature if you're just handed a hash.  Performing the hashing is integral to the process and without it you can generate all sorts of degenerate examples. ... including 'forged' 'signatures' for pubkeys where no one knows the private key.

@gmaxwell In my point of view ... If you have h (m), r and s being a valid signature, it is a real signature yes ... but it depends only on your

[bytcoin]

I think some users didn't understand me ... Maybe it's because my English is not good and they also need to pay more attention.
English is not my language, I will try to be more objective!

1- I know the other thread! I am the author of another thread similar to this one! I managed almost everything "manually" including public keys and signatures!


2- In the other thread I was wondering if 2 signatures with the same private key and with k and k +1 was vulnerable. They said yes! So I asked them to teach me how it was calculated to discover the private key


3- On the other thread ...a second signature is different from this thread here. Although in the 2 thread 2 signatures use the same private key and were also generated with k and k +1. in the thread another... the equations, algebras and formulas worked!

p  = 115792089237316195423570985008687907852837564279074904382605163141518161494337
h1 = 84635513758865831094131084311208775267495704821994249663954751780286420288259
r1 = 99935505760319748698811422354322418311203851828465328908708024011195996180829
s1 = 14810718830809274529170993651437030466460552688297005873719201854608653306524
h2 = 711922952377524543467576566144169816136170490747613227449590530659320692002
r2 = 115035229747891778996889965749694763606205313739267493174821202115705061416296
s2 = 56412229366601912356674994073152925730313351483910294670205660420888695151902

This formulas works:

d_U = (1 - s₂^-1e₂ + s₁^-1e₁) * (s₂^-1r₂ - s₁^-1r₁)^-1 (mod n)

d = 74071287274168731384314914382498140270634658281328726941106265589917762050271

p  = 115792089237316195423570985008687907852837564279074904382605163141518161494337
h1 = 84635513758865831094131084311208775267495704821994249663954751780286420288259
r1 = 99935505760319748698811422354322418311203851828465328908708024011195996180829
s1 = 14810718830809274529170993651437030466460552688297005873719201854608653306524
h2 = 711922952377524543467576566144169816136170490747613227449590530659320692002
r2 = 115035229747891778996889965749694763606205313739267493174821202115705061416296
s2 = 56412229366601912356674994073152925730313351483910294670205660420888695151902

Replaces s1 with its modular multiplicative inverse and s2 with its modular multiplicative inverse

x = (1+s1*h1-s2*h2)/(s2*r2-s1*r1)

x = 74071287274168731384314914382498140270634658281328726941106265589917762050271


Many others work ... but the 2 signatures of this thread although it also uses the same private key and with the nonce k to k + 1...no equation or formula or algebra or magic works!

p  = 115792089237316195423570985008687907852837564279074904382605163141518161494337
h1 = 84635513758865831094131084311208775267495704821994249663954751780286420288259
r1 = 99935505760319748698811422354322418311203851828465328908708024011195996180829
s1 = 14810718830809274529170993651437030466460552688297005873719201854608653306524
h2 = 27086795414784162292297506376302057554366609881154614249233399373002336547922
r2 = 115035229747891778996889965749694763606205313739267493174821202115705061416296
s2 = 75792077109774170129890375817094910949609540422199126584222852124036872408123

d_U = (1 - s₂^-1e₂ + s₁^-1e₁) * (s₂^-1r₂ - s₁^-1r₁)^-1 (mod n)

d = 0

Does not work!

p  = 115792089237316195423570985008687907852837564279074904382605163141518161494337
h1 = 84635513758865831094131084311208775267495704821994249663954751780286420288259
r1 = 99935505760319748698811422354322418311203851828465328908708024011195996180829
s1 = 14810718830809274529170993651437030466460552688297005873719201854608653306524
h2 = 27086795414784162292297506376302057554366609881154614249233399373002336547922
r2 = 115035229747891778996889965749694763606205313739267493174821202115705061416296
s2 = 75792077109774170129890375817094910949609540422199126584222852124036872408123

Replaces s1 with its modular multiplicative inverse and s2 with its modular multiplicative inverse

x = (1+s1*h1-s2*h2)/(s2*r2-s1*r1)

x = 0

Does not work!


4- My final conclusion ... Not all signatures are vulnerable when the same private key is used and with the nonces k and k + 1 and also the 2 signatures of the first post are not vulnerable because there is no equation formula or algebra or magic to solve!


5- Thanks to everyone! I'm learning a lot from the bitcoin community!

[bytcoin]

This is more difficult
https://bitcointalk.org/index.php?topic=5317746.msg56365768#msg56365768

[bytcoin]

By revealing k, you have already made its private key vulnerable to calculate. (And I already showed you how in the thread Coding Enthusiast linked.)

That's the reason why ECDSA specifically requires that a cryptographically secure nonce k has to be chosen and not something trivial such as k+1 or k mod [some prime] or even some pseudorandom generator that derives two successive k without resetting the seed. If you use anything other than a true RNG to get k then it will always be computationally feasible to find some formula that takes two successively generated k values and the algorithm that generates the next k, that runs in polynomial time.

By definition, if you can reverse a cryptographic algorithm in polynomial time then that itself is a vulnerability.

EDIT: and to answer the question in your other thread (you didn't have to make another one), no you cannot, because the only equation in ECDSA that uses the private key, s = k^-1(z + rd_A), has an unknown k, and you can't derive the private key from a signature without it which is exactly why you're supposed to securely generate your nonce.

In the other thread... many formulas work, but in this one I believe that none work.
Maybe using Bleichenbacher’s or similar I can solve this 2 signatures of this thread
I think you need approximately 500 signatures to discover the private key

[NotATether]

In the other thread... many formulas work, but in this one I believe that none work.
Maybe using Bleichenbacher’s or similar I can solve this 2 signatures of this thread
I think you need approximately 500 signatures to discover the private key

I was going to say something similar. Have you thought of making a table of k,k+1 pairs that have no solution so we can see if there is some pattern among them? Maybe they have some property we don't know yet that makes this formula invalid.

d_U = (1 - s₂^-1e₂ + s₁^-1e₁) * (s₂^-1r₂ - s₁^-1r₁)^-1 (mod n)

[bytcoin]

In the other thread... many formulas work, but in this one I believe that none work.
Maybe using Bleichenbacher’s or similar I can solve this 2 signatures of this thread
I think you need approximately 500 signatures to discover the private key

I was going to say something similar. Have you thought of making a table of k,k+1 pairs that have no solution so we can see if there is some pattern among them? Maybe they have some property we don't know yet that makes this formula invalid.

d_U = (1 - s₂^-1e₂ + s₁^-1e₁) * (s₂^-1r₂ - s₁^-1r₁)^-1 (mod n)

@NotATether Exactly! You understand me perfectly! I think this has not yet been explored or little known ... It would be a different method. I'm doing a lot of research and calculations ... every week I'm discovering interesting things