Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

This question already has an answer here:

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

share|improve this question

migrated from security.stackexchange.com Jun 8 at 19:26

This question came from our site for Information security professionals.

marked as duplicate by otus, CodesInChaos, e-sushi, rath, DrLecter Jun 9 at 8:34

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

    
thanks a lot! i think i'm better off there –  Philipp Murry Jun 8 at 7:31
1  
Hi @PhilippMurry, please don't crosspost, I am migrating your question to crypto.se. –  AviD Jun 8 at 19:26

1 Answer 1

up vote 1 down vote accepted

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.
share|improve this answer
    
Thanks a lot, that fixed it! My math seems to be a bit lousy, since I wasn't aware that I can replace every division with a multiplication of the inverse_modulo (which actually solved all my problems). I still don't know why this works, but I can live with that for now. –  Philipp Murry Jun 8 at 13:19

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