3
$\begingroup$

I need the elliptic curve order to recover the private key from two signed messages with ECDSA.

What I have:

  1. two signatures signed by the private-key I want to get
  2. the messages that have been signed
  3. the random $k$ used to sign both messages

So breaking the Cipher should go like that:

$k = (z - z')(s - s')^{-1} \bmod n$

$d = (s \times k - z) r^{-1} \bmod n$

The Calculations are clear, but the elliptic curve order $n$ is missing.
Can I calculate $n$ somehow from the signatures like I can do for $r$ and $s$? Or is there any other way to do this?

|improve this question
$\endgroup$
  • 1
    $\begingroup$ $n$ is a parameter of the curve, do you know which curve was used to sign the messages? $\endgroup$ – puzzlepalace Jun 7 '16 at 17:51
  • $\begingroup$ i dont now exactly , but i can sign the message with my own Private Key (using Python's ecdsa) and this works so i guess i will see which curve they use for the standard Signature generation. Thank you $\endgroup$ – user6431813 Jun 7 '16 at 17:54
  • $\begingroup$ I believe the default curve for the python ecdsa package is P-192 in which case $n = 6277101735386680763835789423176059013767194773182842284081$. $\endgroup$ – puzzlepalace Jun 7 '16 at 18:01
  • $\begingroup$ There's no use of a signature on a message if someone cant verify it. To verify, one must do group operation. It follows, knowledge of curve parameters is assumed. $\endgroup$ – Vadym Fedyukovych Jun 9 '16 at 16:21
3
$\begingroup$

As far as I know, the elliptic curve order $n$ (which denotes the number of points on the curve) cannot be recovered from ECDSA signatures.

It is a public data and if you know which elliptic curve has been used to sign the messages, then you should not have trouble to find it.

There are several methods to determine $n$ from the curve equation. If you want to learn more about it, you can read this at starting point.

|improve this answer
$\endgroup$
7
$\begingroup$

Actually, you can recover $n$ from ECDSA signatures (assuming that you can obtain several signatures with the same $k$ value, which means that the ECDSA signature implementation is broken); however it would require 3 such signatures (if you don't mind factoring a value circa $n^2$), or 4 such signatures (if you don't have that many resources conveniently at hand).

Each ECDSA signature has:

$$s_i = k^{-1}(h_i + rd) + m_i n$$

where:

  • $k^{-1}$ is the inverse of the (unknown) common $k$ value

  • $h_i$ is the known hash of the $i$th message signed

  • $rd$ is the common unknown product of the value $r$ (which we do know, and is constant if $k$ is constant), and the secret key $d$.

  • $n$ is the unknown curve order we're trying we're trying to recover

  • $m_i$ is the unknown value that is added as a part of the $\bmod n$ operation (it is selected to make sure $0 \le s_i < n$, however we don't care about that.

Now, if we compute $(H_3 - H_2)(s_1 - s_2) - (H_1 - H_2)(s_3 - s_2)$, you'll see that the $k^{-1}(H_i + rd)$ portions cancel out; leaving us with $m \cdot n$, with the size of $m$ approximately the same as $n$. If we can factor $mn$, we can do so and this will immediately give us $n$ (and possibly a false hit).

If $mn$ is too large for us to factor conveniently, we can then take a fourth such signature, and compute $(H_4 - H_3)(s_2 - s_3) - (H_2 - H_3)(s_4 - s_3)$; this gives us $m' \cdot n$ (for an $m'$ likely unrelated to $m$); computing $\gcd( mn, m'n )$ immediately gives us $\gcd(m, m')n$; even if $\gcd(m, m')>1$, it is likely small, and so easy to remove.

|improve this answer
$\endgroup$
  • $\begingroup$ If we know the signature was made using a standardized curve wouldn't it be easier to just check which curves' group orders divide $mn$ evenly rather than factoring $mn$? $\endgroup$ – puzzlepalace Jun 7 '16 at 20:14
  • $\begingroup$ @puzzlepalace: well, yes, if you know that it was a standard cuve, it'd be a lot easier to look it up. My answer assumed that you had no idea what curve it was... $\endgroup$ – poncho Jun 7 '16 at 20:16
  • $\begingroup$ I mentioned this only because OP seemed to indicate that the signature was generated via a fairly widely used package, but did not know what the default curve used for signing was (but in this case it seems safe to assume it is one of the standard curves). $\endgroup$ – puzzlepalace Jun 7 '16 at 20:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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