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

  • $\begingroup$ 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. $\endgroup$ – mikeazo Aug 6 '12 at 18:48
  • $\begingroup$ 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 $\endgroup$ – Vakhtang Aug 6 '12 at 19:00
  • 1
    $\begingroup$ See Modular multiplicative inverse. $\endgroup$ – mikeazo Aug 6 '12 at 19:05
  • $\begingroup$ 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. $\endgroup$ – 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.

  • 1
    $\begingroup$ While there are indeed many ways to find the inverse, the most common method is probably the extended Euclidean algorithm. $\endgroup$ – Ilmari Karonen Aug 7 '12 at 10:05
  • $\begingroup$ @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. $\endgroup$ – Thomas Aug 7 '12 at 10:44

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.