2
$\begingroup$

I have all of the Shamir's secret shares required to Lagrange-interpolate f(0), which represents an ECDSA private key. The field of this object is secp256k1, which has associated prime number p=115792089237316195423570985008687907853269984665640564039457584007908834671663.

The Lagrange interpolation produces a negative f(0), but because curves over secp256k1 can have exactly 0 or exactly 2 y-coordinates at any x, I'm assuming I can use the absolute value of f(0).

My other understanding is that since we're working over the finite field Zp, S = f(0) (mod p). Where I'm held up is how to turn this 77-byte number (S) into the ECDSA private key.

I've tried reconstructing a wallet using S in hexadecimal as the private key, as well as the sha256 of S, but I don't believe either of those methods are correct.

Are my previous assumptions correct, and if so, how should I go from S to the ECDSA private key?

Improve this question
$\endgroup$
1
  • 1
    $\begingroup$ That number is 77 decimal digits, but 256 bits or 32 bytes using the de-facto standard of 8-bit bytes. $\endgroup$
    – dave_thompson_085
    Commented May 2, 2020 at 1:34

1 Answer 1

Reset to default
3
$\begingroup$

In ECDSA one randomly selects the private key $d_A$ from interval $[1,n-1]$, where the $n$ is the order of the Elliptic curve with $n-1$ non-trivial points, and with the point at infinity, $\mathcal O$ as the trivial point.

$n = \texttt{FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE BAAEDCE6 AF48A03B BFD25E8C D0364141}$ that is 64 bytes, or as an integer

$n = 115792089237316195423570985008687907852837564279074904382605163141518161494337$

one should prefer $S = \operatorname{Hash}(f(0)) \pmod n$ so that all the information mixed before the modulus. Actually, one can still use the original number, however, if the number is bigger than the order, it generates unnecessary bigger calculations, when this step is performed

$$s=k^{-1}(z+rd_{A})\,{\bmod {\,}}n$$

Note that the $p$ is used to represent the elements of the curve and an easy observation is that it limits the number of points of any curve $\leq p^2$. The Hasse theorem gives a tighter relation;

$$|n-(p+1)|\leq 2{\sqrt {p}}$$

Improve this answer
$\endgroup$
2
  • $\begingroup$ And while for elliptic curves in general the order $n$ may be much smaller than $p$ (or $2^m$), the X9/Certicom/NIST prime curves like secp256k1 are chosen to have cofactor 1 and thus $n$ must be, and as you can easily see is, within the Hasse bound approximately $p \pm 2 {\sqrt p}$ $\endgroup$
    – dave_thompson_085
    Commented May 2, 2020 at 1:39
  • $\begingroup$ @dave_thompson_085 yes, the Hasse bound is tighter. I want to give a small relation, now added that Thanks. $\endgroup$
    – kelalaka
    Commented May 2, 2020 at 1:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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