ecdsa nonce reuse to compute the private key, modular inverse 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 &quot;group in the exponential&quot; 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.
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.