ECDSA: Retrieving non-random k [duplicate]

Question

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: https://github.com/warner/python-ecdsa

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:

$s1 = k^-1 * (z1 + y) \space\%\space n$

$s2 = k^-1 * (z2 + y) \space\%\space n$

(where $y = r*privkey$)

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:

$s1 - s2 = k^{-1} * (z1 + y) - k^{-1} * (z2 + y)$

$s1 - s2 = k^{-1} * (z1 - z2)$

$(s1 - s2) / (z1 - z2) = k^{-1}$

$k = (z1 - z2) / (s1 - s2)$

This doesn't work in my code, because the modulo operation here is just ignored. It actually should look something like this:

$i*n + s1 = k^{-1} * (z1 + y)$

$j*n + s2 = k^{-1} * (z2 + y)$

I got rid of the modulo by adding $x*$n to the left side, where $x$ is unknown. Now I'll just do the same thing as above but keep the $+ x*n$:

$i*n + s1 - j*n - s2 = k^{-1} * (z1 - z2)$

$(s1 - s2) + n*(i-j) / (z1 - z2) = k^{-1}$

$k = (z1 - z2) / ((s1 - s2) + n*(i-j))$

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 $z1$ and $z2$ are close together or $k^{-1}$ is very small (so that it pulls the result down and therefore prevents $z1-2$ from making too much difference).

In theory $k^{-1}$ is pretty small 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%n that is a whole number is used. This number can be really huge, which actually amplifies the difference between $z1$ and $z2$, making $i-j$ pretty large. With this implementation, I can't use the exploit as explained in theory.

My questions are:

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

• Wy doesn't it work when I change the implementation to use $1/k$?

• Is there another way to retrieve $k$, even if the $k^{-1}$ part is really large?

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

best regards

Answer 1

What you need to know is that all equations in this context are, implicitly, understood to be modulo n. That information alone should answer all of your questions, starting with the equation k = (z1 - z2) / (s1 - s2) (modulo N), which hence means k = ((z1-z2) * modular_inverse_mod_n(s1-s2)) % n, where I tried to copy your modulus (%) operator. Specifically:

• Why not 1/k? k^-1 is the way the modular inverse of k is written in your equations, as is the (1/k) which you seem to misunderstand the way a C compiler might.
• Why doesn't 1/k work? It would if you teach the audience (interpreter/compiler?) to treat it as modular division or modular inverse.
• Is there another way? I'm not aware of a simple other way; however, one can make use of even very small information leakage (i.e. both k values have the same initial bit) to reduce the search space if you really insist on making it hard for yourself.