Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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

share|improve this question
    
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
1  
See Modular multiplicative inverse. –  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
add comment

1 Answer 1

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.

share|improve this answer
1  
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
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.