ecdsa nonce reuse to compute the private key, modular inverse question

Question

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.

Answer 1

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.