4
$\begingroup$

The paper regarding curve25519 presents a theorem in chapter 2 (specification). The extension field $F_{p^2}$ is used in this theorem. I don't understand why this extension field is needed for the curve25519. This is how far I got:

The theorem implies that for some elliptic curves $E$ exists a unique $s \in F_p$ for every point multiplication $n \cdot Q$ ($s$ is the x-value of the resulting point). Point multiplication can be done using the Montgomery Ladder. Curve25519 has a base point $P = (9,y)$, where $y$ is not used in the Montgomery Ladder. Because $P$ is a point on the Curve, the point multiplication $P' = n \cdot P$ has also to be a point on the curve. Now one can multiply another scalar with $P'$ which again results to point on the elliptic curve. In this context, only $F_p$ should be needed for the curve25519.

Hence, I think that the extension field is only used, if you consider the point multiplication for all point $Q = (q,r)$ for every $q \in F_p$. That means $Q \notin E(F_p)$ but $Q \in E(F_{p^2})$. I don't understand why this case in considered, when it is never used.

$\endgroup$

1 Answer 1

3
$\begingroup$

I don't really know so I'll tell you my best guess: One of the design goals was "free point validation". To do this, we want to make sure that no matter what $x$-value in $F_p$ we're sent, it is a valid point on the curve.

If $x\in F_p$, then to make an elliptic curve point we need $y$ such that $y^2=x^3+488862x^2+x$. But we have no reason to expect that $x^3+488862x^2+x$ will be a quadratic residue, so in general we will need to define $y$ over $F_{p^2}$. Thus, if I send you any value $x$ in $F_p$ and tell you it's a point on the curve, you know that there is some $y\in F_{p^2}$ such that $(x,y)\in E(F_{p^2})$, but you have no guarantee that $y\in F_p$.

The key exchange uses $x$-only arithmetic, so the key exchange will never need to use the extension field in any computations. Theorem 2.1 tells us that all multiples of a point with an $x$-value in $F_p$ will also have $x$-values in $F_p$, which proves correctness of the $x$-only arithmetic, more or less. So I think the case of $Q\in E(F_{p^2})$ but $Q\notin E(F_p)$ is used, but only via an implicitly-defined $y$-value.

$\endgroup$
1
  • $\begingroup$ This is a pretty good idea! Thank you for the fast answer! $\endgroup$
    – Titanlord
    Jun 30, 2020 at 15:16

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.