1
$\begingroup$

This is the main paper for Curve25519. In section 2: Specification there is a important theorem. In this theorem Bernstein defines the function $X_0 : E(F_{p^2}) \rightarrow F_{p^2}$.

First Question: Curve25519 is a Montgomery curve and uses the projektive arithmetic, which only needs the x-coordinate. The defined functions makes a scalarmultiplication and then takes the x-coordinate from the result. Therefore why isn't it defined as $X_0 : E(F_{p}) \rightarrow F_{p}$? ( or $X_0 : F_{p} \rightarrow F_{p}$ )

Second Question: When making a scalar multiplication on a point of a elliptic curve, the result is always a point. So why is it defined as $X_0 : E(F_{p^2}) \rightarrow F_{p^2}$ and not as $X_0 : E(F_{p^2}) \rightarrow E(F_{p^2})$? One can say, that $E(F_{p^2})$ is not the x-value of a point. In this case, why is it not defined as $X_0 : E(F_{p^2}) \rightarrow F_{p}$?

$\endgroup$
  • $\begingroup$ @kelalaka Sorry, i dont rly understand what you mean. $\endgroup$ – Titanlord May 21 at 13:39
  • $\begingroup$ Functions are defined by: functions: input $\rightarrow$ output. When X is a reductions functions, that takes the result of a already calculated scalar multiplication, then why is the output in $F_{p^2}$ and not in $F_p$? $\endgroup$ – Titanlord May 21 at 13:44
2
$\begingroup$

I got the answer now! Curve25519 does not have key validation. Usually you have a point $P =(x,y)$ on a elliptic curve $E$ over $F_p$. But there is not a point $P$ on the elliptic curve for every value in $F_p$. If you make a key exchange with such a system, you will get a point, or a x-Value (using Montgomery x-only computation). Now you have to test, wether the given point is on the elliptic curve or not, because you can't calculate with a point, thats not on the curve.

Now as i said Curve25519 does not have key validation, because it takes time. But the theorem (in which $X_0$ is defined, too) in the paper about Curve25519 that says, that there is a Point for every x-Value over $F_p$. So you don't need key validation!

The bottom line of is, that you only need the extension field $F_{p^2}$, because you don't want key validation.

| improve this answer | |
$\endgroup$
  • $\begingroup$ You are right! I edited it. $\endgroup$ – Titanlord Jul 1 at 15:42
1
$\begingroup$

For your second question, if you're taking a point on $E(F_{p^2})$, both coordinates are elements of $F_{p^2}$. If you define a function $X':E(F_{p^2})\rightarrow F_p$, then it can't be extracting the x-value from the point.

If you look at the proof in appendix A, he needs to work in $F_{p^2}$ because he needs to be able to take the square root of any element.

| improve this answer | |
$\endgroup$
  • $\begingroup$ But isn't the last parameter of a function the result set? E.g. $X': (x,y) \in E \rightarrow x$ and $x \in F_p$ because X(x,y) = x. So $X: E(F_{p^2}) \rightarrow F_p$ should be enough, because the function is only for extracting the x-value? $\endgroup$ – Titanlord May 21 at 13:31
  • $\begingroup$ @Titanlord, I'm saying that if $(x,y) \in E(F_{p^2})$, then, $x\in F_{p^2}$ and $y \in F_{p^2}$ $\endgroup$ – Aman Grewal May 21 at 14:02
  • $\begingroup$ Yes, because $F_p \in F_{p^2}$. I think, that $x,y\in F_p$ is correct, too. Are there any special cases, am i wrong or does Bernstein use $F_{p^2}$ because $F_p \in F_{p^2}$ and therefore it doen't matter? $\endgroup$ – Titanlord May 21 at 16:20
  • $\begingroup$ Just a note, $F_p \not \in F_{p^2}$. You can think of $F_p \subset F_{p^2}$, which is what Bernstein does. $\endgroup$ – Aman Grewal May 21 at 21:36

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.