3
$\begingroup$

Is there some source of standard, vetted, efficient Montgomery elliptic curves over prime field?

I'm looking for curves $B\,y^2\equiv x^3+A\,x^2+x\pmod p$ engineered for efficient computation of scalar multiplication with $X/Z$ coordinates and Montgomery ladder, which if I'm not mistaken is faster with small* $A_{24}=(A+2)/4$, because there's a multiplication by $A_{24}$ in the point doubling formula.

Ideally I'm looking for a curve with cofactor 4 over some 256-bit prime field, which would give about one extra bit of security compared to Curve25519 (255-bit $p$, cofactor $8$, $A_{24}=121665$, which is not quite optimum for $X/Z$ computations).


* Incidentally: what's the lowest possible $|A_{24}|$ for a secure Montgomery curves over prime field when we can choose $p$ freely?

$\endgroup$
3

1 Answer 1

3
$\begingroup$

The Montgomery form of numsp256t1 matches those criteria, even if calling it "standard" is a bit of a stretch.

NUMS (Nothing Up My Sleeve) curves were curves proposed by Microsoft (Costello at al.) The curve generation algorithm and the resulting curves was proposed back in the days of the elliptic curve controversy against NIST.

They fit all known security requirements, and they were proposed in Short Weierstrass and Edwards form.

In particular numsp256t1 is defined over a 256-bit prime field (with $p= 2^{256} - 189$) an Edwards curve with cofactor=$4$. Using a 4-degree isogeny following proposition 2 of this paper it can be brought into Montgomery format, maintaining the security properties.

The resulting Montgomery curve has $B=1$, $A=61370$ (which gives $A_{24}=15343$). Its cardinality is $4 * 28948022309329048855892746252171976963404671476872247083542990644359122995957$ where $28948022309329048855892746252171976963404671476872247083542990644359122995957$ is a prime of bit-size $255$.

$\endgroup$
6
  • $\begingroup$ Great references! I'm however less than perfectly happy with $A_{24}=15343$. By choosing a different prime, wouldn't it be possible to lower $A_{24}$ (which is used as multiplier at each point doubling)? I added an incidental question about how low $|A_{24}|$ can be. $\endgroup$
    – fgrieu
    Jan 30 at 16:57
  • $\begingroup$ Yes of course, BUT the difference choice of the prime $p=2^{256} -c$ will probably result in a larger $c$, that might effect you more in performances than a smaller $A_{24}$. Also, 15343 is smaller than Curve25519's 121665. $\endgroup$
    – Ruggero
    Jan 31 at 9:59
  • $\begingroup$ [updated] It's true that for low $|A_{24}|$ the prime $p$ would have to be tweaked more (in it's low-order bits, or it's high order bits is we optimize $p$ for Montgomery modular reduction). But I think any tweak that fits a limb/word costs the same as $189$ (in software). I think that $A_{24}=-2$ leads to interesting Montgomery curve, which would I think be faster than $A_{24}=15343$, in both hardware and software. $\endgroup$
    – fgrieu
    Jan 31 at 14:26
  • $\begingroup$ @fgrieu I am not sure I understand your point. I would say that "any $A_{24}$ that fits a limb/word costs the same as $-2$". What am I missing ? $\endgroup$
    – Ruggero
    Jan 31 at 16:00
  • $\begingroup$ $A_{24}$ is used in a field computation like $W:=A_{24}\,U+V$ (with reduction mod $p$ that can be deferred to some degree). When $A_{24}=-2$ it seems possible to use shift or addition instead of multiplication, which can be faster: mulx rax,rcx,rdx reportedly has 4 cycles latency. Subtraction is less nice than addition but I think I see how to get rid of it. $\endgroup$
    – fgrieu
    Jan 31 at 17:02

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.