Scalar Point Multiplication for Elliptic Curve Diffie-Hellman Key Exchange

Question

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

Answer 1

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.