<div dir="ltr"><div>Thanks for the kind comments. Its a straight-forward Edwards implementation a la Curve 41417.</div><div><br></div><div>I should have mentioned that the trace of the Frobenius is -82761451378269664604762234204878960657558723706922</div><div><br></div><div><br></div><div>Mike</div></div><div class="gmail_extra"><br><div class="gmail_quote">On Thu, Mar 19, 2015 at 5:29 PM, Mike Hamburg <span dir="ltr"><<a href="mailto:mike@shiftleft.org" target="_blank">mike@shiftleft.org</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><span><br>
<br>
On 03/19/2015 10:03 AM, Michael Scott wrote:<br>
<blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;padding-left:1ex;border-left-color:rgb(204,204,204);border-left-width:1px;border-left-style:solid">
<br>
Its nice to find a new Elliptic curve that bucks the complexity curve. Nothing nicer than more security for less cost.<br>
<br>
So introducing the Edwards curve E-3363<br>
<br>
x^2+y^2=1+11111.x^2.y^2 mod 2^336-3<br>
<br>
The modulus works particularly well with the Granger-Scott approach to modular multiplication. Observe that 336=56*6=28*12. The order is 8 times a prime, the twist is 4 times a prime. 11111 is the smallest positive value to yield a twist secure curve with cofactors less than or equal to 8. Not only is it “rigid”, it even looks rigid!<br>
<br>
</blockquote>
<br></span>
Great, that looks like a very implementation-friendly prime.<span><br>
<br>
<blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;padding-left:1ex;border-left-color:rgb(204,204,204);border-left-width:1px;border-left-style:solid">
This is merely billions of times more secure than the already secure Curve25519. It fills a gap in terms of existing proposals, coming as it does between WF-128 and WF-192. My implementation takes 333,000 cycles on a 64-bit Intel Haswell for a variable point multiplication, but it is also 32-bit-friendly. The modulus is 5 mod 8, but with Curve25519 we have gotten over that already.<br>
<br>
</blockquote>
<br></span>
Is this the Montgomery ladder, or a (twisted) Edwards implementation?  Just curious.  The timing is very good.  It hits the "Curve25519 plus roughly Karatsuba scaling" efficiency curve, and it ought to do at least as well on ARM NEON with your 28x12 layout.<span><br>
<br>
<blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;padding-left:1ex;border-left-color:rgb(204,204,204);border-left-width:1px;border-left-style:solid">
Note that with this curve we follow others in moving away from the artificial constraint imposed by the desire to use a fully saturated representation, whereby the modulus should be an exact multiple of the word-length, and the associated idea of using a Solinas prime. In my view this approach is (a) not necessarily optimal, (b) encourages non-portable implementation, and (c) is harder to make side-channel secure.<br>
<br>
At the very least Curve E-3363 provides a useful data-point on the security-cost curve.<br>
<br>
Mike<br>
</blockquote>
<br></span>
Yeah, Crandall primes are definitely a better choice than Solinas primes in most cases.  Especially when they end up with a coefficient that's both small and aligned.<br>
<br>
Thanks for this,<br>
-- another Mike<br>
</blockquote></div><br><br clear="all"><br>-- <br><div class="gmail_signature"><div dir="ltr"><div>Michael Scott</div><div>Chief Cryptographer</div><div>CertiVox Ltd</div><div>Tel (353) 86 3888746</div><div><br></div></div></div>
</div>