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? :)