0
$\begingroup$

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 https://math.stackexchange.com/questions/471207/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?

$\endgroup$
  • $\begingroup$ Is it division or modular inverse? $\endgroup$ – Amzoti Aug 19 '13 at 14:46
  • $\begingroup$ I know that the modular inverse for ECC is quite easy (-P). Can I solve this problem using the modular inverse? $\endgroup$ – Horst Lemke Aug 19 '13 at 14:49
  • $\begingroup$ Can you post the problem and an example of your issue so we can have a peek? Regards $\endgroup$ – Amzoti Aug 19 '13 at 14:51
  • $\begingroup$ 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) - $\endgroup$ – Horst Lemke Aug 19 '13 at 14:55
  • $\begingroup$ Sorry, I do not have access. Regards $\endgroup$ – Amzoti Aug 19 '13 at 14:58
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Horst Lemke Aug 20 '13 at 6:58
  • 1
    $\begingroup$ @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. $\endgroup$ – Alex J Best Aug 20 '13 at 13:01
  • 1
    $\begingroup$ 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. $\endgroup$ – Horst Lemke Aug 20 '13 at 14:36
  • 1
    $\begingroup$ +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 :-) $\endgroup$ – Jyrki Lahtonen Aug 21 '13 at 6:20

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.