# Why is 2 the inverse of 10?

I have one question about the ECDSA signature scheme.

When Bob wants to send a message to Alice that is to be signed she makes following things (with for example $A = (5,1)$, $d=7$, $q=19$).

1. compute hash of message $h(x) =26$

2. choose ephemeral key $k_E = 10$

3. $R = k_E · A = 10 · (5,1) = (7,11)$

4. $r = x_R = 7$

5. $s = (h(x)+d · r)·k_E^{−1} \bmod q = (26+7 · 7) · 2 ≡ 17 \bmod 19$

Formula of 5 step is: $s ≡ (h(x)+d·r)·k_E^{−1} \bmod q.$

We have $k_E = 10$, so why is $k_E^{−1} = 2$?

• Your question is very hard to follow. Why do you have kE and k^E? This site does support tex formatting, which is strongly recommended for equations. – mikeazo Aug 6 '12 at 18:48
• I mean this, please see my photo: s9.postimage.org/nmex0jz4d/CRYPTO.jpg I wanted to write, Ke and Ke^-1 in the picture its show. I don't understand how to compute Ke^-1 – Vakhtang Aug 6 '12 at 19:00
• – mikeazo Aug 6 '12 at 19:05
• I don't understand what your question is. And how is this related to blind signatures? I never even heard of a blind ECC signature scheme. – CodesInChaos Aug 6 '12 at 20:25

It looks like your main question is determining why $k{_{E}}^{-1} = 2$, correct?

As mentioned in the comments to the question, this is because it is the modular multiplicative inverse.

The multiplicative inverse is a number, $x^{-1}$, such that $x·x^{-1}=1$. However, since we are in modulo 19, we want to find $x^{-1}$ such that $x·x^{-1}\equiv1 \bmod 19$. In your posted example, since $k_{E}=10$, ${k_E}^{-1}=2$ because $10·2 = 20 \equiv 1 \bmod 19$.

There are many methods as to finding the multiplicative inverse in a modular space where it is too numerous to explain in a single answer.

• While there are indeed many ways to find the inverse, the most common method is probably the extended Euclidean algorithm. – Ilmari Karonen Aug 7 '12 at 10:05
• @IlmariKaronen another one is Euler's Theorem applied to inverses, which requires you to know the totient of the modulus (non-issue if the latter is a prime), but is convenient to implement and useful if for some reason you don't have support for negative numbers. Otherwise EEA is often the fastest and best. – Thomas Aug 7 '12 at 10:44