# ECDSA: Retrieving non-random k [duplicate]

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

• Hi @PhilippMurry, please don't crosspost, I am migrating your question to crypto.se. – AviD Jun 8 '14 at 19:26