<blockquote>
  <p>isn't solving for N^(-1), and hence N, becomes equivalent to finding the solution to the discrete logarithm?</p>
</blockquote>

<p>No, it is not. This does not require finding the discrete logarithm at all. Solving the discrete logarithm is finding the exponent to a known base. However in this problem we are trying to find the base and know what the exponent is. Furthermore, this known exponent is -1 for which finding the base of something raise to -1 is to raise the result to -1 again, i.e. taking the inverse of the inverse.</p>

<p>There are algorithms that exist to find the modular inverse of a number which is how N^(-1) is found in the first place. To find N, you just need to take the inverse of N^(-1) because of the identity that an inverse an inverse is the element itself.</p>

CC BY-SA 4.0
2019-03-26T18:40:46.950Z
Isn't the order of how the equation is written same as the public key generation? You have [hash(m1) - hash(m2)] as the base and N^(-1) as the exponent?
Ugam Kamat
CC BY-SA 4.0
2019-03-26T19:03:31.610Z
No. [hash(m1) - hash(m2)] is an integer, not a elliptic curve point. N^(-1) is also an integer. So this formula is just integer multiplication. It is not exponentiation nor is it curve point multiplication (the two things that have discrete log problems). Thus it is not solving any discrete logarithm.
Ava Chow
CC BY-SA 4.0
2019-03-26T19:20:36.910Z
That's what I was looking for. So since N^(-1)*[hash(m1) - hash(m2)] is just integer multiplication modulo p vs curve point addition.
Ugam Kamat
CC BY-SA 4.0
2019-03-26T18:21:03.470Z
2019-03-26T18:21:03.470Z
Ava Chow
<p>Let me rewrite your question in a different notation, where all lowercase values are integers and uppercase values are points.</p>

<ul>
<li>The group generator is <em>G</em> (a known constant).</li>
<li>The private key is <em>q</em>, its corresponding public key is <em>Q = qG</em>.</li>
<li>The nonce is <em>n</em>, its corresponding point is <em>R = nG</em>.</li>
<li>The X coordinate of <em>R</em> is <em>r</em>.</li>
<li>The hash function is <em>h(x)</em>.</li>
<li>A signature is <em>(r,s)</em>, where <em>s</em> is computed as <em>n<sup>-1</sup>(h(m) + qr)</em>.</li>
<li>A signature is valid iff <em>r = x(s<sup>-1</sup>(h(m)G + rQ))</em> (where <em>x()</em> stands for "The X coordinate of point ...")</li>
</ul>

<p>Now for the two signatures it holds that:</p>

<ul>
<li><em>s<sub>1</sub> = n<sup>-1</sup>(h(m<sub>1</sub>) + qr)</em></li>
<li><em>s<sub>2</sub> = n<sup>-1</sup>(h(m<sub>2</sub>) + qr)</em></li>
<li><em>s<sub>1</sub> - s<sub>2</sub> = n<sup>-1</sup>(h(m<sub>1</sub>) - h(m<sub>2</sub>))</em></li>
<li><em>n = (s<sub>1</sub> - s<sub>2</sub>)<sup>-1</sup>(h(m<sub>1</sub>) - h(m<sub>2</sub>))</em></li>
</ul>

<p>As <em>s<sub>1</sub></em> and <em>s<sub>2</sub></em> are just integers, <em>(s<sub>1</sub> - s<sub>2</sub>)<sup>-1</sup></em> can be trivially computed using a modular inverse; there are no elliptic curve points involved here (over which this problem would be hard).</p>

<p>Once you know <em>n</em>, you can find <em>q</em> by rewriting the first equation:</p>

<ul>
<li><em>ns<sub>1</sub> = h(m<sub>1</sub>) + qr</em></li>
<li><em>ns<sub>1</sub> - h(m<sub>1</sub>) = qr</em></li>
<li><em>q = r<sup>-1</sup>(ns<sub>1</sub> - h(m<sub>1</sub>))</em></li>
</ul>

<p>Substituting this in the earlier equations gives you:</p>

<ul>
<li><em>q = (r (s<sub>1</sub> - s<sub>2</sub>))<sup>-1</sup>(m<sub>1</sub>s<sub>2</sub> - m<sub>2</sub>s<sub>1</sub>)</em></li>
</ul>

CC BY-SA 4.0
2019-04-30T18:28:50.360Z
Apologies for the no-no of asking for clarification but I think there is something missing here. I stumbled over the following line from PWuille: A signature is valid iff r = x(s-1(h(m)G + rQ)) Problem is: there is no definition for x in this statement.
Is it a typo, and you meant to say m (the message)? In that case the question would be: how would you multiply something with a (text) message (which might be a huge PDF file), so that can’t really be it, right? Or is it a function x(anything), in which case the question is: what function is it?
To prevent me wasting precious PWuille-time I ask
Hare Brained Brian
CC BY-SA 4.0
2019-04-30T18:30:35.483Z
@Hare Brained Brian: Responding to your comment posted as an answer here: the `x(...)` above means "The X coordinate of the point ...".
Pieter Wuille
CC BY-SA 4.0
2019-03-26T19:17:27.910Z
2019-05-01T00:30:12.853Z
2019-05-01T00:30:12.853Z
Pieter Wuille
<p>I know it is well understood that it is not a good practice to use the same nonce while generating the signatures, but I am not getting the math right. </p>

<p>Assume I have some UTXOs that are controlled by my private key Q. Say I have spent two of the UTXOs using nonce 'N' to generate my signature. Now the (R,S) components of the signature are public and the transactions are public so everyone has access to them. </p>

<pre><code>S1 = N^(-1)*[hash(m1) + Q*R] mod p
</code></pre>

<p><code>S2 = N^(-1)*[hash(m2) + Q*R] mod p</code></p>

<pre><code>S1 - S2 = N^(-1)*[hash(m1) - hash(m2)] mod p
</code></pre>

<p>Even though we know S1, S2, m1 and m2, isn't solving for N^(-1), and hence N, becomes equivalent to finding the solution to the discrete logarithm?</p>

CC BY-SA 4.0
2019-03-29T15:44:33.667Z
Possible duplicate of [How do you derive the private key from two signatures that share the same k value?](https://bitcoin.stackexchange.com/questions/73622/how-do-you-derive-the-private-key-from-two-signatures-that-share-the-same-k-valu)
MCCCS
CC BY-SA 4.0
2019-04-01T07:24:12.213Z
Not necessarily. My question asks further expansion of the answer derived from that question, asking how solving for N^(-1) is not finding a solution to the discrete logarithm problem.
Ugam Kamat
<private-key><signature><cryptography>
How can my private key be revealed if I use the same nonce while generating the signature?
Ugam Kamat
# How can my private key be revealed if I use the same nonce while generating the signature?

(Asked by: username_0 on 2019-03-26)

I know it is well understood that it is not a good practice to use the same nonce while generating the signatures, but I am not getting the math right.

Assume I have some UTXOs that are controlled by my private key Q. Say I have spent two of the UTXOs using nonce 'N' to generate my signature. Now the (R,S) components of the signature are public and the transactions are public so everyone has access to them.

```
S1 = N^(-1)*[hash(m1) + Q*R] mod p

```

`S2 = N^(-1)*[hash(m2) + Q*R] mod p`

```
S1 - S2 = N^(-1)*[hash(m1) - hash(m2)] mod p

```

Even though we know S1, S2, m1 and m2, isn't solving for N^(-1), and hence N, becomes equivalent to finding the solution to the discrete logarithm?

**Tags:** private-key, signature, cryptography

> **Comments:**
> **username_1**: Possible duplicate of [How do you derive the private key from two signatures that share the same k value?](https://bitcoin.stackexchange.com/questions/73622/how-do-you-derive-the-private-key-from-two-signatures-that-share-the-same-k-valu)  
> **username_0**: Not necessarily. My question asks further expansion of the answer derived from that question, asking how solving for N^(-1) is not finding a solution to the discrete logarithm problem.  

---

## 2 answers

### Answer by username_3 on 2019-03-26. Score: 8 | Accepted answer

Let me rewrite your question in a different notation, where all lowercase values are integers and uppercase values are points.

* The group generator is *G* (a known constant).
* The private key is *q*, its corresponding public key is *Q = qG*.
* The nonce is *n*, its corresponding point is *R = nG*.
* The X coordinate of *R* is *r*.
* The hash function is *h(x)*.
* A signature is *(r,s)*, where *s* is computed as *n-1(h(m) + qr)*.
* A signature is valid iff *r = x(s-1(h(m)G + rQ))* (where *x()* stands for "The X coordinate of point ...")

Now for the two signatures it holds that:

* *s1 = n-1(h(m1) + qr)*
* *s2 = n-1(h(m2) + qr)*
* *s1 - s2 = n-1(h(m1) - h(m2))*
* *n = (s1 - s2)-1(h(m1) - h(m2))*

As *s1* and *s2* are just integers, *(s1 - s2)-1* can be trivially computed using a modular inverse; there are no elliptic curve points involved here (over which this problem would be hard).

Once you know *n*, you can find *q* by rewriting the first equation:

* *ns1 = h(m1) + qr*
* *ns1 - h(m1) = qr*
* *q = r-1(ns1 - h(m1))*

Substituting this in the earlier equations gives you:

* *q = (r (s1 - s2))-1(m1s2 - m2s1)*

> **Comments:**
> **username_4**: Apologies for the no-no of asking for clarification but I think there is something missing here. I stumbled over the following line from PWuille: A signature is valid iff r = x(s-1(h(m)G + rQ)) Problem is: there is no definition for x in this statement. Is it a typo, and you meant to say m (the message)? In that case the question would be: how would you multiply something with a (text) message (which might be a huge PDF file), so that can’t really be it, right? Or is it a function x(anything), in which case the question is: what function is it? To prevent me wasting precious PWuille-time I ask  
> **username_3**: @username_4: Responding to your comment posted as an answer here: the `x(...)` above means "The X coordinate of the point ...".  

---

### Answer by username_2 on 2019-03-26. Score: 1

> isn't solving for N^(-1), and hence N, becomes equivalent to finding the solution to the discrete logarithm?

No, it is not. This does not require finding the discrete logarithm at all. Solving the discrete logarithm is finding the exponent to a known base. However in this problem we are trying to find the base and know what the exponent is. Furthermore, this known exponent is -1 for which finding the base of something raise to -1 is to raise the result to -1 again, i.e. taking the inverse of the inverse.

There are algorithms that exist to find the modular inverse of a number which is how N^(-1) is found in the first place. To find N, you just need to take the inverse of N^(-1) because of the identity that an inverse an inverse is the element itself.

> **Comments:**
> **username_0**: Isn't the order of how the equation is written same as the public key generation? You have [hash(m1) - hash(m2)] as the base and N^(-1) as the exponent?  
> **username_2**: No. [hash(m1) - hash(m2)] is an integer, not a elliptic curve point. N^(-1) is also an integer. So this formula is just integer multiplication. It is not exponentiation nor is it curve point multiplication (the two things that have discrete log problems). Thus it is not solving any discrete logarithm.  
> **username_0**: That's what I was looking for. So since N^(-1)*[hash(m1) - hash(m2)] is just integer multiplication modulo p vs curve point addition.  

---

