1
$\begingroup$

I am trying to understand elliptic curve Diffie-Hellman key exchange and here is a book example which I don't understand. Given values of $G=(2,2)$ and I should calculate $203(2,2)$, which actually is $(130,203$). I can do the arithmetic for small numbers but in this case I am very confuses

$\endgroup$
  • $\begingroup$ You should give more information about your elliptic curve. You need point doubling. $\endgroup$ – kelalaka Dec 13 '18 at 22:41
  • $\begingroup$ Thank you. The curve is of order (0,4) which is the same as y^2=×^3-4 $\endgroup$ – Mariam10 Dec 13 '18 at 22:44
  • $\begingroup$ You can edit your question with this information, see at Wikipedia Elliptic_curve_point_multiplication andDoubling a point on an elliptic curve $\endgroup$ – kelalaka Dec 13 '18 at 22:48
  • $\begingroup$ @Moo the book is William Stallings- Cryptography and network security, 4th edition, example is on the top of the page 312 $\endgroup$ – Mariam10 Dec 13 '18 at 22:56
  • $\begingroup$ @Moo thank you very much. Actually i have never heard about horners rule but i googled it and probably now i can use it. Thank you a lot. $\endgroup$ – Mariam10 Dec 14 '18 at 0:16
2
$\begingroup$

From the book "Cryptography and Network Security: Principles and Practice" by W. Stallings, we have the following example.

$$y^2 = x^3 - 4 \pmod{211}$$

  • I took the liberty to correct the errors and typos in this example!
  • A generator point is $G = (2,2)$.
  • For $G = (2,2)$, one can calculate the point of infinity for this generator as $241G = O$.
  • A’s private key is $n_A = 121$, so A’s public key is $P_A = 121(2,2) = (115,48)$.
  • B’s private key is $n_B = 203(2,2)$, so B’s public key is $P_B = 203(2,2) = (130,203)$.
  • The shared secret key is $121(130,203) = 203(115,48) = (161,69)$.

Your question is how do they calculate the point multiplication $203(2,2) = (130,203)$?

Other than addition, with $n$ being a natural number, we can define another operation: scalar multiplication as $$nP = \underbrace{P + P + \cdots + P}_{n\ \text{times}}.$$

Written in that form, it may seem that computing $nP$ requires $n$ additions. If $n$ has $k$ binary digits, then our algorithm would be $O(2^k)$, which is not really good. But there are many faster algorithms. One of them is the double and add algorithm.

We have $n = 203$. Its binary representation is $11001011_2$. This binary representation can be turned into a sum of powers of two: $$\begin{array}{rcl} 203 & = & 1 \cdot 2^7 + 1 \cdot 2^6 + 0 \cdot 2^5 + 0 \cdot 2^4 + 1 \cdot 2^3 + 0 \cdot 2^2 + 1 \cdot 2^1 + 1 \cdot 2^0 \\ & = & 2^7+2^6+2^3+2^1+2^0\end{array}$$

(We have taken each binary digit of $n$ and multiplied it by a power of two.)

In view of this, we can write: $$203 \cdot P = 2^7 P + 2^6 P + 2^3 P + 2^1 P + 2^0 P$$

In words, the Double and Add algorithm works as follows:

  • Take $P$.
  • Double it, so that we get $2P$.
  • Add $2P$ to $P$ so the we get the result of $2^1P + 2^0P$.
  • Double $2P$, so that we get $2^2P$, but don't perform any addition with it.
  • Double $2^2P$ to get $2^3P$.
  • Add it to our result so that we get $2^3P + 2^1P + 2^0P$.
  • Double $2^3P$ to get $2^4P$, but don't perform any addition with it.
  • Double $2^4P$ to get $2^5P$, but don't perform any addition with it.
  • Double $2^5P$ to get $2^6P$.
  • Add it to our result so that we get $2^6P + 2^3P + 2^1P + 2^0P$.
  • Double $2^6P$ to get $2^7P$.
  • Add it to our result so that we get $2^7+ 2^6P + 2^3P + 2^1P + 2^0P$.
  • In the end, we can compute $203 \cdot P$ performing just seven doublings and four additions!

To carry out these calculations, we use the Point Addition and Point Doubling formulas while taking care regarding the point at infinity. The intermediate calculations are

  • $P = (2,2)$
  • $2P = (5,200)$
  • $2P + P = (129,56)$
  • $2^2 P = (159, 144)$
  • $2^3 P = (174, 163)$
  • $2^3 P + 2 P + P = (168, 6)$
  • $2^4 P = (181, 209)$
  • $2^5 P = (136, 11)$
  • $2^6 P = (147, 97)$
  • $2^6P + 2^3 P + 2 P + P = (32, 108)$
  • $2^7 P = (133,48)$
  • $2^7P + 2^6P + 2^3 P + 2 P + P = (130, 203)$

This verifies that $203 (2, 2) = (130, 203)$.

There are tools like SAGE, Magma, GAP, Pari/GP, Mathematica or others that you can use to do these calculations.

$\endgroup$

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.