1
$\begingroup$

I am following along some cryptography challenges:, in particular ECDSA Nonce Reuse here (second problem): https://blog.coinbase.com/capture-the-coin-cryptography-category-solutions-fe94d82165c5

I understand all the math, except this part:

def modinv(a, modulus): return pow(a, modulus — 2, modulus)
def divmod(a, b, modulus): return (a * modinv(b, modulus)) % modulus

Why is it modulus - 2? Shouldn't it be modulus - 1? I thought the modular inverse of a mod n would be $a^{n-1}$? Since $a * a^{n-1} = a^n = 1$?

Is it something to do with the fact that the EC group is size order, but the "group in the exponential" is size order - 1? I don't really understand though. We need to compute the private key as $\frac{ks'-z}{r}$. But according to ecdsa: https://en.wikipedia.org/wiki/Elliptic_Curve_Digital_Signature_Algorithm r and s are all calculated mod n? So why are we doing n - 2? But then confusingly, k is selected in the set [1, .., n-1].

So yeah just a clear cut explanation would be helpful. Thanks.

Thanks for the help!

Oh wait, maybe this is really dumb: we just want the private key, and the private key exists in the integer multiplicative group [1, .., n-1], which is size n-1.

$\endgroup$
0
$\begingroup$

You are looking for the modular inverse of $r$

By Euler's Theorem

$$a^{\phi(m)} \equiv 1 \pmod{m}$$

Then $$a^{\phi(m)-1} \equiv a^{-1} \pmod{m}$$

Now, for a prime $p$, $\phi(p) = p-1$ then we have

$$a^{p-2} \equiv a^{-1} \pmod{p}$$


Note 1: The multiplicative group $\mathbb{Z}^*_p$ contains $p-1$ elements, the zero is not included.

Note 2: Not all elements of $\mathbb{Z}_m$ has multiplicative inverse. To have one, $x \in \{1,\ldots,m-1\}$ we must have $\gcd(m,x)=1$

Note 3: The order of Secp256k1 is prime.

$\endgroup$
2
  • $\begingroup$ Right, yeah, the private key "lives in" the exponent, which is size n - 1, so that's all we care about. $\endgroup$ – Luke Feb 28 at 23:07
  • $\begingroup$ @Luke you don't want to include $k=0$ case. $\endgroup$ – kelalaka Feb 28 at 23:15

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.