<p>This is trivially broken.</p>
<p>Given:</p>
<ul>
<li>(1) <em>s<sub>1</sub> = (z<sub>1</sub> + r<sub>1</sub>d) / k<sub>1</sub></em></li>
<li>(2) <em>s<sub>2</sub> = (z<sub>2</sub> + r<sub>2</sub>d) / k<sub>2</sub></em></li>
<li>(3) <em>k<sub>2</sub> = k<sub>1</sub> + d</em></li>
</ul>
<p>Substituting (3) into (2), eliminating <em>k<sub>2</sub></em>:</p>
<ul>
<li>(4) <em>s<sub>2</sub> = (z<sub>2</sub> + r<sub>2</sub>d) / (k<sub>1</sub> + d)</em></li>
</ul>
<p>Solving (1) for <em>k<sub>1</sub></em>:</p>
<ul>
<li>(5) <em>k<sub>1</sub> = (z<sub>1</sub> + r<sub>1</sub>d) / s<sub>1</sub></em></li>
</ul>
<p>Substituting (5) into (4), eliminating <em>k<sub>1</sub></em>:</p>
<ul>
<li>(6) <em>s<sub>2</sub> = (z<sub>2</sub> + r<sub>2</sub>d) / ((z<sub>1</sub> + r<sub>1</sub>d) / s<sub>1</sub> + d)</em></li>
</ul>
<p>Solving (6) for <em>d</em>:</p>
<ul>
<li>(7) <em>d = (z<sub>2</sub>s<sub>1</sub> - z<sub>1</sub>s<sub>2</sub>) / (s<sub>2</sub>(r<sub>1</sub> + s<sub>1</sub>) - r<sub>2</sub>s1)</em></li>
</ul>
<p>The right hand side of which only contains public information.</p>
<p>Note that all these variables are elements of <em>F</em>, so the division symbol above refers to multiplication with the modular inverse of the denominator modulo <em>N</em>.</p>
<blockquote>
<p>k2= 0x8d98be4c0fbb5c078a442354d969fdb70021259c8cce7bf9d94339891eee0b</p>
</blockquote>
<p>I believe you're missing a &quot;45&quot; after those digits.</p>

CC BY-SA 4.0
2022-06-11T19:58:18.873Z
Would solution (7) still hold true for k2=k1+d+1, if (7) were modified to:  d=(z2*s1-z1*s2)/(s2*(r1+S1) - 1-r2*s1-1) mod N?  I am manipulating the parameters on the small curve [N=79, P=67,G=(2,22), d=7, k1=19, r1=38, s1=36, z1=23 | k2=27, r2=17, s2=4, z2= 68].
Alfhilðr ínn Seiðkona
CC BY-SA 4.0
2022-06-11T20:20:47.067Z
You cannot fix this. If your nonce values satisfy a simple polynomial expression, it will either be trivial to break, or at least be impossible to prove it is secure. If you want a provably secure technique, your nonces need to be actually unpredictable (e.g. computed using hashes with secret input, or randomly).
Pieter Wuille
CC BY-SA 4.0
2022-06-11T21:00:35.927Z
I can generate secure random nonces without any issues.   That is not the problem.  I am trying to generate a decent honeypot for my employer so that potential employees can demonstrate their abilities.  Thus, I am playing around with signature equations and I have honestly noticed and developed a lot of different patterns (granted, using the small curve) and equations to match.  Back to your answer, I generate nonces using randomness on secp256k1 calculator, and then sign per protocols.  This question is simply for my further education. Thank you so very much, I really appreciate you.
Alfhilðr ínn Seiðkona
CC BY-SA 4.0
2022-06-12T16:32:21.433Z
It appears stackexchange butchered my earlier URL. Retry: https://tinyurl.com/429ye2ye gives the solution for `k2 = a*k1 + b*d + c`, with known constants a, b, c.
Pieter Wuille
CC BY-SA 4.0
2022-06-12T20:15:39.120Z
Thank you, that cleared up a lot of confusion on my end.  :-).   I sent you an email on your github email.  My apologies for not getting permission from your first.
Alfhilðr ínn Seiðkona
CC BY-SA 4.0
2022-06-17T15:12:05.150Z
Mr. Wuille, is there a way to ask a question that is private between two parties, so that a malicious actor cannot take advantage of the Q&A here on stackexchange? If so, will you direct me to the help section as to how? I cannot seem to find it. If not, is there any way I can ask you a question outside of the public forum? Thank you.
Alfhilðr ínn Seiðkona
CC BY-SA 4.0
2022-06-17T15:12:33.353Z
You can email me.
Pieter Wuille
CC BY-SA 4.0
2022-06-17T16:03:20.113Z
Sent the email to the address posted on github just now.  Thank you.
Alfhilðr ínn Seiðkona
CC BY-SA 4.0
2022-06-09T19:18:55.620Z
You are correct, there was a 45 on the end of the hex string, but the secp256k1 calculator would produce the incorrect result when running through the Generator Point while that was appended.  I don't know the particular reason for this, but, deleting the 45 in the calculator produced the correct R(x,y) values.  Thank you for your answer, I can see where my error was in my equations.
Alfhilðr ínn Seiðkona
CC BY-SA 4.0
2022-06-09T16:06:08.923Z
2022-06-09T16:24:32.117Z
2022-06-09T16:24:32.117Z
Pieter Wuille
<p>My question is related to weak signature vulnerability testing where a hypothetical attacker does not know the values of the nonce or private key itself, but can determine that the nonce 'k1' is increased by private key 'd' to create k2, such that:  k2 = k1+d.</p>
<p>I have searched the stack exchanges and various articles and research papers and have not found a workable solution to this problem.  My own linear algebra is not as strong as I would like it (it's been a number of years), and my attempts have not been successful.  I have used the k2 = k1+1 equations but they do not specifically produce the necessary solution of k2-k1 = d.  Other solutions for solving for k did not work, either.</p>
<p>Is there a way to find the difference of k2-k1 = d, where k1, k2, and d are unknown, where k2 = k1+d, but all other values (r, s, z) are known?</p>
<p>(I have provided the values of d, k1, and k2 for verification of possible solutions, but for the purposes of the question, assume an attacker does not know the values but can spot a relationship).</p>
<p>Let:</p>
<p>N:       Finite field of the secp256k1</p>
<p>d:       Private key</p>
<p>B(x,y):  Public key coordinates</p>
<p>k:       Private key of ECDSA nonce</p>
<p>R(x,y):  Public key coordinates of nonce</p>
<p>r:       R.x integer</p>
<p>s:       signature integer</p>
<p>z:       Hash value of message</p>
<p>N= 0xfffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364141</p>
<p>B.x= 0x7697a1f8d952c373285bd441b1716344a61748b48279be15b03538d80e60f901</p>
<p>B.y=
0x431aed8857c99064b316a0c9fb6e7cba3eeade88f44d2c31dee4fa8965740f54</p>
<p>d=
0x8b5069be43c35cbc6530d473a9f102dc57f8f5771982eba3988a7588c6e284a7</p>
<p>k1= 0x248548dcbf7ff4b25134ee12f78fadaa8283025734b905640b8c400580b869e</p>
<p>s1= 0xec585a4b0317e38b75008930607a32224b3d11a8a373ed15da32723b1418f852</p>
<p>z1= 0x12dd3658e48a15016dc1f5af7725ad3a5e7b2d6a52112dbd4a0d6df8772a141a</p>
<p>R1x= 0xb2dcf2acc6fdd003e65e8d9d77ee4d84a9c0cccbac8eb43bdeeecb69a35bab4b</p>
<p>R1y= 0x4a8774fd7ac69caf2d92154324c2280b5f29652b7f458baa28545f1b38d969b8</p>
<p>############################</p>
<p>k2= 0x8d98be4c0fbb5c078a442354d969fdb70021259c8cce7bf9d94339891eee0b</p>
<p>s2= 0x2df1c9e8b3984088ec521c92e9f001b836841e8a14cda6977072d5b23bed171e</p>
<p>z2= 0xdae540b9f50337b2dab2f226a687084e8a1758dbc73505b7ff288b01cc4dae3f</p>
<p>R2x= 0x37df00ccef04bfcf0f2b0da82a685125ddd67b9f66320a9619e6e4df7bd57439</p>
<p>R2y= 0x5ff78c4ef0caf4eff68f938ee475e2e99a7b9be31642eb0e5cb68b30a843b46b</p>
<p>Basic signature equations:</p>
<p>d= (k * s - z) * r^-1 mod N</p>
<p>k= (d * r + z) * s^-1 mod N - or- (d * a + b) mod N</p>
<p>s= (d * r + z) * k^-1 mod N</p>
<p>r= (k * s - z) * d^-1 mod N</p>
<p>z= (k * s) - (d * r) mod N</p>
<p>a= r * s^-1 mod N</p>
<p>b= z * s^-1 mod N</p>
<p>Is there a way to solve this to obtain the value k2-k1=d (k1+d-k1=d) given the equations above, or to solve either k1 or k2,  or would the k generation scheme be relatively secure from attack?</p>

<transactions><signature><ecdsa><nonce>
Can the difference be determined between two nonces k1, k2, having a linear relationship if the nonce and private key are unknown, i.e., k2 - k1 = n?
Alfhilðr ínn Seiðkona
# Can the difference be determined between two nonces k1, k2, having a linear relationship if the nonce and private key are unknown, i.e., k2 - k1 = n?

(Asked by: username_0 on 2022-06-09)

My question is related to weak signature vulnerability testing where a hypothetical attacker does not know the values of the nonce or private key itself, but can determine that the nonce 'k1' is increased by private key 'd' to create k2, such that: k2 = k1+d.

I have searched the stack exchanges and various articles and research papers and have not found a workable solution to this problem. My own linear algebra is not as strong as I would like it (it's been a number of years), and my attempts have not been successful. I have used the k2 = k1+1 equations but they do not specifically produce the necessary solution of k2-k1 = d. Other solutions for solving for k did not work, either.

Is there a way to find the difference of k2-k1 = d, where k1, k2, and d are unknown, where k2 = k1+d, but all other values (r, s, z) are known?

(I have provided the values of d, k1, and k2 for verification of possible solutions, but for the purposes of the question, assume an attacker does not know the values but can spot a relationship).

Let:

N: Finite field of the secp256k1

d: Private key

B(x,y): Public key coordinates

k: Private key of ECDSA nonce

R(x,y): Public key coordinates of nonce

r: R.x integer

s: signature integer

z: Hash value of message

N= 0xfffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364141

B.x= 0x7697a1f8d952c373285bd441b1716344a61748b48279be15b03538d80e60f901

B.y=
0x431aed8857c99064b316a0c9fb6e7cba3eeade88f44d2c31dee4fa8965740f54

d=
0x8b5069be43c35cbc6530d473a9f102dc57f8f5771982eba3988a7588c6e284a7

k1= 0x248548dcbf7ff4b25134ee12f78fadaa8283025734b905640b8c400580b869e

s1= 0xec585a4b0317e38b75008930607a32224b3d11a8a373ed15da32723b1418f852

z1= 0x12dd3658e48a15016dc1f5af7725ad3a5e7b2d6a52112dbd4a0d6df8772a141a

R1x= 0xb2dcf2acc6fdd003e65e8d9d77ee4d84a9c0cccbac8eb43bdeeecb69a35bab4b

R1y= 0x4a8774fd7ac69caf2d92154324c2280b5f29652b7f458baa28545f1b38d969b8

############################

k2= 0x8d98be4c0fbb5c078a442354d969fdb70021259c8cce7bf9d94339891eee0b

s2= 0x2df1c9e8b3984088ec521c92e9f001b836841e8a14cda6977072d5b23bed171e

z2= 0xdae540b9f50337b2dab2f226a687084e8a1758dbc73505b7ff288b01cc4dae3f

R2x= 0x37df00ccef04bfcf0f2b0da82a685125ddd67b9f66320a9619e6e4df7bd57439

R2y= 0x5ff78c4ef0caf4eff68f938ee475e2e99a7b9be31642eb0e5cb68b30a843b46b

Basic signature equations:

d= (k \* s - z) \* r^-1 mod N

k= (d \* r + z) \* s^-1 mod N - or- (d \* a + b) mod N

s= (d \* r + z) \* k^-1 mod N

r= (k \* s - z) \* d^-1 mod N

z= (k \* s) - (d \* r) mod N

a= r \* s^-1 mod N

b= z \* s^-1 mod N

Is there a way to solve this to obtain the value k2-k1=d (k1+d-k1=d) given the equations above, or to solve either k1 or k2, or would the k generation scheme be relatively secure from attack?

**Tags:** transactions, signature, ecdsa, nonce


---

## 1 answers

### Answer by username_1 on 2022-06-09. Score: 5 | Accepted answer

This is trivially broken.

Given:

* (1) *s1 = (z1 + r1d) / k1*
* (2) *s2 = (z2 + r2d) / k2*
* (3) *k2 = k1 + d*

Substituting (3) into (2), eliminating *k2*:

* (4) *s2 = (z2 + r2d) / (k1 + d)*

Solving (1) for *k1*:

* (5) *k1 = (z1 + r1d) / s1*

Substituting (5) into (4), eliminating *k1*:

* (6) *s2 = (z2 + r2d) / ((z1 + r1d) / s1 + d)*

Solving (6) for *d*:

* (7) *d = (z2s1 - z1s2) / (s2(r1 + s1) - r2s1)*

The right hand side of which only contains public information.

Note that all these variables are elements of *F*, so the division symbol above refers to multiplication with the modular inverse of the denominator modulo *N*.

> k2= 0x8d98be4c0fbb5c078a442354d969fdb70021259c8cce7bf9d94339891eee0b

I believe you're missing a "45" after those digits.

> **Comments:**
> **username_0**: You are correct, there was a 45 on the end of the hex string, but the secp256k1 calculator would produce the incorrect result when running through the Generator Point while that was appended.  I don't know the particular reason for this, but, deleting the 45 in the calculator produced the correct R(x,y) values.  Thank you for your answer, I can see where my error was in my equations.  
> **username_0**: Would solution (7) still hold true for k2=k1+d+1, if (7) were modified to:  d=(z2*s1-z1*s2)/(s2*(r1+S1) - 1-r2*s1-1) mod N?  I am manipulating the parameters on the small curve [N=79, P=67,G=(2,22), d=7, k1=19, r1=38, s1=36, z1=23 | k2=27, r2=17, s2=4, z2= 68].  
> **username_1**: You cannot fix this. If your nonce values satisfy a simple polynomial expression, it will either be trivial to break, or at least be impossible to prove it is secure. If you want a provably secure technique, your nonces need to be actually unpredictable (e.g. computed using hashes with secret input, or randomly).  
> **username_0**: I can generate secure random nonces without any issues.   That is not the problem.  I am trying to generate a decent honeypot for my employer so that potential employees can demonstrate their abilities.  Thus, I am playing around with signature equations and I have honestly noticed and developed a lot of different patterns (granted, using the small curve) and equations to match.  Back to your answer, I generate nonces using randomness on secp256k1 calculator, and then sign per protocols.  This question is simply for my further education. Thank you so very much, I really appreciate you.  
> **username_1**: It appears stackexchange butchered my earlier URL. Retry: https://tinyurl.com/429ye2ye gives the solution for `k2 = a*k1 + b*d + c`, with known constants a, b, c.  
> **username_0**: Thank you, that cleared up a lot of confusion on my end.  :-).   I sent you an email on your github email.  My apologies for not getting permission from your first.  
> **username_0**: Mr. username_1, is there a way to ask a question that is private between two parties, so that a malicious actor cannot take advantage of the Q&A here on stackexchange? If so, will you direct me to the help section as to how? I cannot seem to find it. If not, is there any way I can ask you a question outside of the public forum? Thank you.  
> **username_1**: You can email me.  
> **username_0**: Sent the email to the address posted on github just now.  Thank you.  

---

