1
$\begingroup$

I have noticed that DBL/diffadd in Edward/Montgomery form almost double fast than Weierstrass form(EFD), and curve25519 is empressive high-performance.The transformation between these forms can be covered by two ModInvs at most(even two ModMults). So the scalar multiplication in specific elliptic curves like p256 or Secp256k1 could transfer to scalar_mult in Edward/Montgomery form.

  1. Could these tranformation&AdditionChain&diffAdd be faster than the ordinary MADD&w-NAF&preCom methods?

  2. Of course Curve25519 is designed for Montgomery form, but the wide spread Weierstrass curves also have well-designed prime number. To what extent will the curve parameters affected the performance of Montgomery/Edward scalar_mult?

$\endgroup$
  • $\begingroup$ I don't believe that the curves p256 or Secp256k1 can be converted to Edward/Montgomery form; curves in those forms always have a point of order 2, and p256/Secp256k1 don't have such a point $\endgroup$ – poncho Jan 24 at 3:26
  • $\begingroup$ I have refered to the answer from this question. I should have misunderstood thoes fomulars. $\endgroup$ – scv10086 Jan 24 at 5:42
  • $\begingroup$ I've just learned that Weierstrass curve converted to Montgomery curve only stand with special conditions, e.g. 4|order(E), etc. I guess the traditionnal Weierstrass curves always designed to have prime order, perhaps on account of the security level&efficiency. But if the Montgomery curve state to have 128bits security level converted to Weierstrass form with order divisible by 4 also have the same security level. What's the meaning of such principle? $\endgroup$ – scv10086 Jan 25 at 2:45
  • $\begingroup$ @scv10086 There are several caveats with non-prime order curves. Point validation is much more inefficient, small group attacks becomes possible, etc. $\endgroup$ – Ruggero Jan 25 at 13:22
2
$\begingroup$

Curves P-256 and Secp256k1 cannot be converted to Montgomery or Edwards forms because they are of prime order.

Let's take the example of Secp256k1 and try to convert it to a Montgomery curve:

A Montgomery curve $by^2=x^3+ax^2+x$ has a point of order 2. Such a point verifies $2P=\mathcal{O}$ or think of it equivalently $P=-P$ which means $(x,y)=(x,-y)$ so these points are on the $x$-axis. It is obvious then that the point $(0,0)$ on a Montgomery curve has order 2. Now given the secp256k1 curve $y^2\equiv x^3+7 \pmod p$ where $p=2^{256}-2^{32}-2^9-2^8-2^7-2^6-2^4-1$, we are looking for points on the $x$-axis which means those that satisfy $x^3 \equiv -7 \pmod p$. There is no solution to this modular cubic equation.

In general curve P-256 and Secp256k1 cannot be converted to Montgomery form because they have a prime order ($\ne 2$) and thus they cannot have a point of order $2$ (otherwise $2$ would divide a prime number beacause of Lagrange's theorem).

The same reasoning works for Edwards curve $x^2+y^2=1+dx^2y^2$ because the point $(0,-1)$ has order $2$ and the points $(\pm 1, 0)$ have order $4$.

$\endgroup$
  • $\begingroup$ this is not what wikipedia says in en.wikipedia.org/wiki/… $\endgroup$ – David 天宇 Wong Jun 3 at 16:27
  • $\begingroup$ @David天宇Wong wikipedia says you can find an equivalence of curves in general. The question here is about « specific » curves like p256 and secp256k1. These specific weierstrass curves have a prime order and the equivalence relationship doesn’t work because all montgomery and edwards curves have necessarily a composite order. $\endgroup$ – Youssef El Housni Jun 12 at 11:43
  • $\begingroup$ how right, it's only true for Montgomery -> Weierstrass. I missed "[Weierstrass] can be converted to Montgomery form if and only if $E$ has order divisible by four and satisfies the following conditions [...]" $\endgroup$ – David 天宇 Wong Jun 12 at 23:16

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.