Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I want to implement a crypto protocol using Elliptic Curve Cryptography. However, it requires a division which I cannot handle.

In multiplicative notation, it requires:

  1. Let $\mathbb{G}=\left \langle g \right \rangle$ be a finite cyclic group of prime order $p$.
  2. select $P \in_{R} \mathbb{G}$ and $a \in_{R} \mathbb{Z}_{p}$ and
  3. compute $S=P^\frac{1}{a}$.

In conversion between multiplicative and additive group notation, I learned that $S=P^\frac{1}{a}$ means $S=\frac{1}{a}P$ in additive notation. I only know point addition and point multiplication. Is there a way to calculate S?

share|improve this question
    
Is it division or modular inverse? –  Amzoti Aug 19 '13 at 14:46
    
I know that the modular inverse for ECC is quite easy (-P). Can I solve this problem using the modular inverse? –  Horst Lemke Aug 19 '13 at 14:49
    
Can you post the problem and an example of your issue so we can have a peek? Regards –  Amzoti Aug 19 '13 at 14:51
    
I'm not sure, how much I'm allowed to post. But I can surly name the Paper: link.springer.com/chapter/10.1007%2F11774716_17#page-1 (Page 212, Peer Registration, Step 5) - –  Horst Lemke Aug 19 '13 at 14:55
    
Sorry, I do not have access. Regards –  Amzoti Aug 19 '13 at 14:58
show 1 more comment

1 Answer

up vote 1 down vote accepted

As far as I can tell the operation being referred to is raising the point $P$ to the power $a^{-1} \in \mathbb{Z}_p$. Calculating this inverse is as Amzoti says just modular inversion, which should be fairly easy to do with the Euclidean algorithm. Then just raise $P$ to the calculated power, which can be done simply, or a bit quicker if you wish.

The reason it is written this way is probably to make it easier to read, compare $P^{(a+z)^{-1}}$ to $P^{1/(a+z)}$ as is written in the source.

share|improve this answer
    
So just for completenes, I can say: $P^{1/(a+z)}=P^{(a+z)^{-1}}=(P^{{-1}})^{(a+z)}$ which makes very much sense to me and helps me to solve the problem. –  Horst Lemke Aug 20 '13 at 6:58
1  
@HorstLemke I'm not so sure about the last equality, you should try and think of $(a+z)^{-1}$ as one object, the inverse of the element $a+z$ mod $p$, which you would first calculate (the answer can always be found in the range 1 to $p$) then apply the operation on the point this many times. –  Alex J Best Aug 20 '13 at 13:01
1  
Yes you are right. With the top solution all my tests failed. I didn't think of inverting the integer values. Now they are successfull. –  Horst Lemke Aug 20 '13 at 14:36
1  
+1 This is the only sensible interpretation. Given that in ellipctic curve crypto the prime $p$ usually has dozens (if not hundreds) of digits the point about square-and-multiply is a bit moot. I do not know of a single textbook on crypto that would not include that. No doubt you added it just to be safe :-) –  Jyrki Lahtonen Aug 21 '13 at 6:20
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.