6
$\begingroup$

I have a question regarding the random $k$ number of ECDSA encryption. As far as I know, it is possible to retrieve $k$ (and thus the private key) from two signed messages if both used the same $k$. This was done for the PlayStation 3 hack. I'm now trying to reproduce it in Python, using this library.

My problem is that the hack only works in some cases (at least I think so). I've not been able to reproduce it, so I hoped you could help me.

Initially we have two equations: $$ s_1 = k^{-1} * (z_1 + y) \mod n \\ s_2 = k^{-1} * (z_2 + y) \mod n \\ $$ (where $y = r*\mathrm{privatekey}$)

We want to get rid of y and figure out k. In all explanations I've seen so far, they'll do something like this: $$ \begin{align} s_1 - s_2 &= k^{-1} * (z_1 + y) - k^{-1} * (z_2 + y) \\ s_1 - s_2 &= k^{-1} * (z_1 - z_2) \\ \frac{s_1 - s_2}{z_1 - z_2} &= k^{-1} \\ k &= \frac{z_1 - z_2}{s_1 - s_2} \\ \end{align} $$

This doesn't work in my code, because in this hack, the modulo operation at the beginning is just ignored. If I we don't ignore it, the equation should look like this: $$ i*n + s_1 = k^{-1} * (z_1 + y) \\ j*n + s_2 = k^{-1} * (z_2 + y) \\ $$

I got rid of the modulo by adding $x*n$ to the left side, where x (i or j) is unknown. With this equation I'll just do the same thing as above but keep the $+ x*n$: $$ \begin{align} i*n + s_1 - j*n - s_2 &= k^{-1} * (z_1 - z_2) \\ \frac{s_1 - s_2 + n*(i-j)}{z_1 - z_2} &= k^{-1} \\ k &= \frac{z_1 - z_2}{s_1 - s_2 + n*(i-j)} \\ \end{align} $$

Obviously we do not know $i$ and $j$. We can ignore them if $i = j$ (as we did in the first calculation), which is only the case when $z_1$ and $z_2$ are close together or $k^{-1}$ is very small (so that it pulls the result down and therefore prevents $z_1$ or $z_2$ from making too much difference).

In theory $k^{-1}$ is pretty small (since it's $\frac{1}{k}$) and therfore the exploit works. But in practice I've seen that $k^{-1}$ is not used, but instead the smallest inverse modulo of $k \mod n$ that is a whole number is used. This number can be really large, which actually amplifies the difference between $z_1$ and $z_2$, making $i-j$ pretty large. With this implementation, I can't use the exploit as explained in theory, because I never get my exact $k$.

My questions are:

  • Mathematically, is there another way to retrieve $k$, even if the $k^{-1}$ part is really large? Maybe using some inverse modulo?

  • Why is it that many implementations use the inverse modulo instead of $k^{-1}$? (I've seen it in two libraries so far)

  • Why doesn't it work when I change the implementation to use $k^{-1}$?

Since this is part of an assignment for Uni, retrieving $k$ still has to work somehow. But I already spent too much time on it without any results. Any gurus out there that can help me? :)

$\endgroup$

1 Answer 1

6
$\begingroup$

I believe you are being confused by what $k^{-1}$ means. It doesn't mean "interpret $k$ as a real number, plug it into a calculator, and hit the $1/x$ button".

When we use the $k^{-1}$ notation, what we mean to say is that $a = k^{-1}$ is equivalent to saying that $a \times k = 1$.

You will say "doesn't that mean doing exactly what a calculator does?". Well, it would, if the multiplication was performed in the field of the reals. However, we're doing everything modulo $n$ (within the field $GF(n)$, as $n$ is prime), and so the multiplication is done modulo $n$; hence we really have $a \times k = 1 \pmod{n}$.

In this context, when we write $k^{-1}$, we really do intend the modular inverse. And, when we derive $k = \frac{z_1 - z_2}{s_1 - s_2}$, we're not ignoring the modulo operation; it's been assumed implicitly; what we really mean is $k = (z1 - z2) \times (s_1 - s_2)^{-1} \bmod n$, there $(s_1 - s_2)^{-1}$ is the multiplicative inverse (modulo $n$) of $s_1 - s_2$.

When you derive $k = \frac{z_1 - z_2}{s_1 - s_2 + n*(i-j)}$, well, since everything is done modulo $n$, including the internal additions, we effectively have $n=0$ (because, modulo $n$, those are the value), and so $i$ and $j$ drop out, and we're left with the original derivation.

Since you explicitly asked questions, I'll answer them (even if they ought to be obvious once the above has been clarified):

Mathematically, is there another way to retrieve $k$, even if the $k^{−1}$ part is really large? Maybe using some inverse modulo?

Yes, an inverse modulo is precisely what you're looking for.

Why is it that many implementations use the inverse modulo instead of $k^{−1}$? (I've seen it in two libraries so far)

The inverse modulo that the libraries do is what is meant by $k^{-1}$

Why doesn't it work when I change the implementation to use $k^{−1}$?

The mathematics of ECDSA assume that the math works out in one specific field (the field $GF(n)$); if you do the computations in a different field (say, the field of real numbers), well, it won't work.

$\endgroup$
1
  • $\begingroup$ thinking about it, i actually learned most of this in my first semester (discret mathematics). this makes me feel bad, knowing that i should've been able to solve it on my own :/ but thanks a lot for clearing things up $\endgroup$ Jun 8, 2014 at 18:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.