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$
2
  • $\begingroup$ The "addition" is over $E$, not just over $Z/pZ$. ​ ​ $\endgroup$
    – user991
    Nov 3, 2016 at 3:10
  • $\begingroup$ @RickyDemer Oh, yeah, forgot to put that there. Thanks! $\endgroup$
    – Colin Jang
    Nov 3, 2016 at 3:12

1 Answer 1

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$
2
  • $\begingroup$ @ColinJang: if you like my answer, please upvote it $\endgroup$
    – poncho
    Nov 3, 2016 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, 2016 at 3:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.