how to choose a random secret key for ECDH

Question

I am a beginner, I can understand the basics of ECC and elliptic curve, i can't find where I missed to understand. But I have a great doubt in ECDH regarding below. Could any of you please clarify for me? I will ask with the help of an example.

Example:

1. Let $G=(1,3)$ be the generator point with order $n=18$ for an elliptic curve $E(13,24)\bmod29$. I want to calculate Public key for both Alice and Bob.

2. Now Let the secret key of Alice be $A=5$ and of Bob be $B=7$ (such that the scalar which is multiplying with $G$ should be less than the order $n$ of the generator point).

3. Now the public key of Alice is $P_A=A\cdot G=5\cdot G=5(1,3)=(19,7)$
   and the public key of Bob is $P_B=B\cdot G=7\cdot G=7(1,3)=(15,6)$

4. Now after transmitting the public key mutually, the parties have to calculate the shared secret key.
   The shared key of Alice is $S_A=A\cdot P_B=5(15,6)=(23,1)$
   and the shared key of Bob is $S_B=B\cdot P_A=7(19,7)=\mathcal O$(Point at infinity). The shared secret supposed to be the same. But I am getting the point at infinity instead of $(23,1)$. How to overcome this?

5. My doubt is,if this is the case how can the sender and receiver get the shared key in ECDH?
   If not, kindly quote where I did mistake here and in what i misunderstood?

Answer 1

What curve are you considering, in what field, using what addition formulas?

From the data you provided, I assume you are talking about the curve of the form $y^2 = x^3 + 24x + 13$, in the field $\mathbb{Z}_{29}$ of the integer modulo $29$, because then your generator $G=(1,3)$ is effectively on the curve: $$1 + 24+ 13 \equiv 9=3^2 \pmod{29}.$$ And the public points you computed, $(19,7)$ and $(15,6)$ are effectively on the curve and correspond to the correct values.

Now, simple addition formulas for such a curve would be, given two points $P=(x_1,y_1)$ and $Q=(x_2,y_2)$, that we sum together into $R=(x_3,y_3)=P+Q$: $$ x_3= \left(\frac{y_2-y_1}{x_2-x_1}\right)^2-x_1-x_2 $$ $$ y_3=-y_1+\left(\frac{y_2-y_1}{x_2-x_1}\right)(x_1-x_3) $$ But those are not always working, most notably not if $x_1=x_2$, so we need another formula for point doubling, given $P=(x_1,y_1)$ and $R=(x_2,y_2)=2P$, we have that: $$ x_2=\left(\frac{3x_1^2+24}{2y_1}\right)^2 -2x_1 $$ $$ y_2=\left(\frac{3x_1^2+24}{2y_1}\right)(x_1-x_2)-y_1$$ and even this would only work if $y_1\neq 0$.
Remark that on that regard, Wikipedia currently forgets to precise that there are such cases where the formulas cannot be used.

Now, you have a mistake in your latest computation: you want to take $P_A=(19,7)$ and multiply by 7 using those two formulas, so: $$\begin{align} 2P_A&=(4,17) &\text{doubling}\\ 3P_A&=2P_A+P_A=(0,19) &\text{addition}\\ 4P_A&=2(2P_A)=(1,3) &\text{doubling}\\ 7P_A&=4P_A+3P_A=(23,1) &\text{addition}\end{align}$$

So as you can see, $7(19,7)\neq\mathcal{O}$ as you computed, but it really works and is equal to $(23,1)$.

Note that there exist complete formulas for such curves, see for example this paper, so that you can have just one formulas to do everything.