[curves] Crash Course on ECC poster

[Michael Hamburg]

The Montgomery ladder can take advantage of mixed differential addition, where R+Q is computed with the additional information that R-Q is equal to the base point P.  (It’s called “mixed” because R and Q are in projective form, but P is affine.)  Unlike ordinary addition, differential addition can be computed using just the x-coordinates of P, Q and R.  So can doubling.  Therefore, you can compute the whole ladder using only x coordinates.  You can recover y at the end, but usually people don’t.

This pair of operations — x-only mixed differential addition and doubling — is significantly faster and simpler on a Montgomery curve than on a short Weierstrass curve.  The same is not true of the ordinary addition and doubling formulas.  This is why Montgomery curves are used for ECDH, but not usually other operations.

You can take advantage of the same technique on a short Weierstrass curve, using for example co-z coordinates.  But it’s not as simple or fast as on a Montgomery curve.  Furthermore, while the mixed differential addition law is unified on a Montgomery curve, it is not unified on a short Weierstrass curve.  This makes it noticeably harder to start the ladder.

— Mike

> On Jul 8, 2015, at 5:11 PM, Ron Garret <ron at flownet.com> wrote:
> 
> Could you please elaborate on this, or point me to a reference?  According to:
> 
> https://choucroutage.com/Papers/SideChannelAttacks/ches-2002-joye.pdf <https://choucroutage.com/Papers/SideChannelAttacks/ches-2002-joye.pdf>
> 
> the Montgomery ladder “is of full generality and applies to any abelian group.”
> 
> Is it really the ladder that is more efficient for Montgomery curves, or is it just the point addition and doubling operations that are more efficient?
> 
> rg
> 
> On Jul 8, 2015, at 4:05 PM, Michael Hamburg <mike at shiftleft.org <mailto:mike at shiftleft.org>> wrote:
> 
>> The Montgomery ladder is significantly simpler and more efficient on Montgomery curves than on short Weierstrass curves.
>> 
>>> On Jul 8, 2015, at 3:38 PM, Ron Garret <ron at flownet.com <mailto:ron at flownet.com>> wrote:
>>> 
>>> “Montgomery curves are attractive because of the ladder method of scalar multiplication”
>>> 
>>> Is this actually true?  I was under the impression that the Montgomery ladder was applicable to any kind of elliptic curve.  They just both happen to have been invented by Peter Montgomery.
>>> 
>>> rg
>>> 
>>> On Jul 7, 2015, at 8:12 PM, Tony Arcieri <bascule at gmail.com <mailto:bascule at gmail.com>> wrote:
>>> 
>>>> I made this poster for the DEFCON Crypto and Privacy Village. It's intended for audiences of mixed ability levels:
>>>> 
>>>> https://i.imgur.com/hwbSRHh.png <https://i.imgur.com/hwbSRHh.png>
>>>> 
>>>> Would appreciate technical feedback on it. If you'd like to suggest copy changes, please consider design constraints (i.e. available room on the page).
>>>> 
>>>> Thanks!
>>>> 
>>>> -- 
>>>> Tony Arcieri
>>>> _______________________________________________
>>>> Curves mailing list
>>>> Curves at moderncrypto.org <mailto:Curves at moderncrypto.org>
>>>> https://moderncrypto.org/mailman/listinfo/curves <https://moderncrypto.org/mailman/listinfo/curves>
>>> 
>>> _______________________________________________
>>> Curves mailing list
>>> Curves at moderncrypto.org <mailto:Curves at moderncrypto.org>
>>> https://moderncrypto.org/mailman/listinfo/curves <https://moderncrypto.org/mailman/listinfo/curves>
>> 
> 

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://moderncrypto.org/mail-archive/curves/attachments/20150708/54886ed8/attachment.html>