1
$\begingroup$

So I'm trying to understand how the key exchange with Curve25519 works. I read the original Paper from Bernstein "Curve25519: new Diffie-Hellman speed records", but I still got some questions. First of all, this is graphic, how the key exchange should work:

enter image description here

So Alice and Bob create their own secret key by randomly choosing a number $$n\in 2^{254} + 8 \cdot \{ 0, 1, \ldots , 2^{251} - 1\}.$$ In other ECC standards, this $n$ is multiplied with a Public Point $P$, but here I don't have a public Point $P$. So that's where I don't understand the concept.

The Public string is not a point, it is a number $q \in \{0,1,\ldots,255\}^{32}$ and i don't understand, why it is only a number and not a Point.

So in other Standards, the public key of Bob and Alice is produced by multiplying the secret key with the public Point. That produces new Points, which are the public keys.

Here there is a public function also included I have no idea, what it does. That means, I can't figure out, how the shared secret key is produced.

In addition, I would like to know what the functional call of $\operatorname{Curve25519}(a,9)$ means, so what do the parameters do with my curve?

  • Can someone explain this to me? Is it possible to give me a simple example of how it works?
Improve this question
$\endgroup$

1 Answer 1

Reset to default
3
$\begingroup$

TL;DR: The public key is not a point, it is the $x$-coordinate of the point.

The base point of the curve has been chosen to be the point $G = (9,y_0)$ with $y_0>0$, and the curve Curve25519 is used in its Montgomery form given by the equation $$ y^2 = x^3 + 486662x^2 + x. $$ The main operation on elliptic curves is the scalar multiplication, and in this case, it is computed with the Montgomery ladder algorithm with formulas that use only the $x$-coordinate of the input point, and output the $x$-coordinate.

For one valid $x$-coordinate of a point $P$, there are two possible points, $P$ or $-P$, so if Alice private key is $a$, then her public key is $x([a]G)$ (the $x$-coordinate of the point $[a]G = G + G + \cdots + G$, the output of $\operatorname{Curve25519}(a,9)$). Since the $y$-coordinate is not used, then it corresponds either to the point $[a]G$ or $-[a]G$, then Bob can compute easily $x([ba]G)$, which corresponds to either $[ab]G$ or $-[ab]G$.

Basically, the $y$-coordinate is not useful to get a shared secret, and not useful for the computation since the formulas that do not use it on Montgomery curves are pretty efficient.

Improve this answer
$\endgroup$
5
  • $\begingroup$ So the base point G = (9,y_0) is the same in every key exchange? Is the public function the montgomery ladder computing the public key aG = q and also the shared public key a b G ? $\endgroup$
    – Titanlord
    Commented Mar 28, 2020 at 13:34
  • 3
    $\begingroup$ You can see on the picture you included that the base point is always the same. The Montgomery ladder is given in RFC 7748 section 5. $\endgroup$
    – user69015
    Commented Mar 28, 2020 at 13:42
  • $\begingroup$ Is there a reason, why the Point is always the same? The discrete logarithm Problem is still hard to break, but there must be a reason, why this Point has x = 9 and not e.g. x = 42. $\endgroup$
    – Titanlord
    Commented Mar 28, 2020 at 13:50
  • 1
    $\begingroup$ The point is the same so Alice and Bob can compute from the same base point. Now why 9? Well, first the order of $(9, \ldots)$ is the large prime factor of the curve cardinality. Any other point with this order could have been use, but $9$ is the smallest integer that satisfies this condition (and the point $(42, \ldots)$ has a factor $4$ in its order). $\endgroup$
    – user69015
    Commented Mar 28, 2020 at 15:40
  • $\begingroup$ Note that the rfc defines $y_0>0$. Also $[a]G = G + G + \cdots + G$ is better writing for scalar multiplication and there $\cdots$ fits better than $\ldots$, too. $\endgroup$
    – kelalaka
    Commented Mar 28, 2020 at 18:19

Your Answer

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

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