1
$\begingroup$

I've been experimenting with ECDSA signatures and with how the Sony PS3 private key was leaked. Specifically where:

$$k = \frac{z_1 - z_2}{s_1 - s_2}$$ $$d_A = \frac{z_1s_2 - z_2s_1}{k(s_1 - s_2)}$$

In my case I have two (and more) ECDSA signatures that have the same $r$ and $k$, but have a differing $s$ and $d_A$. Although I know that $k$ is the same for all the signatures, I do not know the value of it - just that it is identical in each case.

Therefore, I have the values of the following:

  • $r$ for each signature (an identical $r$ for all)
  • $s$ for each signature ($s_1$, $s_2$, etc.)
  • $z$ for each signature ($z_1$, $z_2$, etc.)

I know that:

  • $k_1$ = $k_2$ = $k_3$, etc., but I do not know the value of it

I do not know:

  • $d_A$ for any of the signatures

Is it possible to calculate the value of $d_A$ for each of the signatures by using:

  • The known shared $r$ value,
  • The unknown, shared $k$ value,
  • The known individual $s$ ($s_1$, $s_2$, etc.) values, and
  • The known individual $z$ ($z_1$, $z_2$, etc.) values?

I should also add that I do also have the public key $Q_A$ for each signature but don't believe this would be of value in the above calculation.

Note: Apologies if the parameters I have used are non-standard. I've tried to use those from the ECDSA page on Wikipedia but am working from the Sony paper which uses different letters for the parameters.

How this question differs from existing question with answer on site

This similar question has two answers which are (seemingly) contradictory. The first (and accepted) answer states that it is not possible using the information that is given. The second answer states that it is possible.

My question differs from this question because in mine, $k_1 = k_2 = k_3$ (etc.). Whereas in the referenced question $k$ is unknown and is not known to be equal for $x_1$ and $x_2$ (the private keys referred to in that question).

Tried So Far

I've so far tried using an article by Andrew Corbellini that states the following:

$$k = (z_1 - z_2)(s_1 - s_2)^{-1} \bmod n$$

$$d_A = r^{-1}(sk - z) \bmod n$$

However the answer that it's yielding is incorrect for any of the signatures.

Using Gaussian Elimination

Reading this paper about key leakage with ECDSA issues, I came across section 4.3 which talks about nonce reuse across different keys and the use of Guassian elimination to calculate any of the private keys.

Consider that I have the following 3 messages that share both $k$ (unkown but equal across all three) and $r$ (known and equal across all three), with known individual $s_n$ and $z_n$ values:

$$s_1 = k^{-1}(z_1 + rd_{A_1})$$ $$s_2 = k^{-1}(z_2 + rd_{A_2})$$ $$s_3 = k^{-1}(z_3 + rd_{A_3})$$

Or rearranged to look at it with $z_n$ as the focus we get:

$$\begin{array}{rrrrr} s_1\,k&-r\,d_{A_1}&\equiv&z_1\pmod p\\ s_2\,k&-r\,d_{A_2}&\equiv&z_2\pmod p\\ s_3\,k&-r\,d_{A_3}&\equiv&z_3\pmod p\\ \end{array}$$

Can any of the $d_A$ private keys be calculated?

$\endgroup$
5
  • $\begingroup$ We have several questions about this. Did you search? $\endgroup$ – kelalaka Feb 26 at 22:39
  • $\begingroup$ @kelalaka I've read a couple of very similar questions but the answers were contradictory. I've also read some articles including andrea.corbellini.name/2015/05/30/… which seems to indicate it is possible but the suggested approach isn't working for me, hence the question. $\endgroup$ – Martin Feb 26 at 22:48
  • $\begingroup$ It would be better Q if you indicate those similar questions and why they are contradictory, too. $\endgroup$ – kelalaka Feb 26 at 22:50
  • $\begingroup$ @kelalaka I've udpated the question to reference an existing question with contradictory answers and explain how my question differs from that one. $\endgroup$ – Martin Mar 1 at 18:51
  • $\begingroup$ could you share a couple of signatures, with $z$, and the public key ? $\endgroup$ – Ruggero Mar 2 at 9:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.