Recover elliptic curve order from ECDSA signatures

Question

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?

Answer 1

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.

Answer 2

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.