# 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 "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.

You are looking for the modular inverse of $$r$$

$$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.

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