1
$\begingroup$

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?

$\endgroup$
4
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Thanks for your reply. And by the way sorry, the curve i want to mention here is y^2=x^3+24.x+13, and so other details i had entered already are correct. Here my doubt is I cannot get the same shared secret key on both side. one side it is (23,1) and "O" point at infinity on other side. How to overcome this.Please? @Lery $\endgroup$ – Poomagal Chockalingam Sep 8 '17 at 15:19
  • $\begingroup$ @PoomagalChockalingam Then you simply have a mistake in your computations, please edit your answer to explain how you compute your points. Because now $P_A$ and $P_B$ are effectively on your curve, but $7 \cdot (19,7) = (23,1)$, it is not equal to the point at infinity as you say. $\endgroup$ – Lery Sep 8 '17 at 15:32
  • $\begingroup$ @PoomagalChockalingam I've now edited my answer to use the correct curve. $\endgroup$ – Lery Sep 8 '17 at 15:55
  • $\begingroup$ Great....now I can clearly get what's Procedure to do the scalar multiplication. The problem might be in my coding. Sorry once again. An so now i can come to know that secret key can be chosen randomly from the limit (0 to n-1) where n is the order of the generator point chosen. Similarly Is there any procedure to choose the generator point, if so how to calculate the order of that particular point? can you please detail it? Thank you $\endgroup$ – Poomagal Chockalingam Sep 9 '17 at 2:32
  • $\begingroup$ @Poomagal This belongs to a new question, I think you should ask a second question about generators and their order. If you have troubles with your code, you can also ask for help on stackoverflow.com $\endgroup$ – Lery Sep 9 '17 at 8:04

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.