2
$\begingroup$

It's a very quick question, but I couldn't find the answer from the sources I have.

I've been coding EC based D-H key exchange, and I'm almost done with it.

So here's what I've understood so far.

  1. Michael and Nikita agree on an Elliptic Curve $E:y^2=x^3+ax+b $, a prime number $p$, and a point $P$ on $E$ over $Z/pZ$.
  2. They choose their secret numbers $m$ (for Michael) and $n$ (for Nikita).
  3. They exchange $mP$ and $nP$, each calculated by adding $P$ to itself $m$ and $n$ times over $E$ in $Z/pZ$. (I understand how the "addition" works)
  4. Now by using the $mP$ or $nP$ they got from each other and the secret number they chose ($n$ and $m$) to calculate the shared key $mnP$.

So my question is, how do you calculate $mnP$? No source I have specified what exactly it is, so I'm not sure if it is $(m \times n)P$ or $P$ added $n$ times to $mP$.

Thanks in advance!

$\endgroup$
  • $\begingroup$ The "addition" is over $E$, not just over $Z/pZ$. ​ ​ $\endgroup$ – user991 Nov 3 '16 at 3:10
  • $\begingroup$ @RickyDemer Oh, yeah, forgot to put that there. Thanks! $\endgroup$ – Colin Jang Nov 3 '16 at 3:12
4
$\begingroup$

So my question is, how do you calculate $mnP$?

For Michael, he takes the value $nP$ he received from Nikita, and adds it to itself $m$ times; that is, it's $\underbrace{nP + nP + \dots + nP}_\text{$m$ times}$, that is the value $m(nP)$.

And, of course Nikita takes the value $mP$ he received from Michael, and adds it to itself $n$ times; that is, it's $\underbrace{mP + mP + \dots + mP}_\text{$n$ times}$, that is the value $n(mP)$.

And, because we perform these operations in a mathematical group (that is, associativity holds), we have $m(nP) = n(mP) = mnP$, so they come up with the same value.

$\endgroup$
  • $\begingroup$ @ColinJang: if you like my answer, please upvote it $\endgroup$ – poncho Nov 3 '16 at 3:45
  • $\begingroup$ Already did, but as my reputation is too low, it won't be displayed, it seems. It says it will be recorded, though. @poncho $\endgroup$ – Colin Jang Nov 3 '16 at 3:51

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.