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