Subject: [Cfrg] Elliptic curve evaluation truths

From: "Parkinson, Sean" <[email-masked]>
Date: Tue, 25 Nov 2014 02:56:06 -0500

In hopes of reaching consensus, I thought I might start a list of known truths.
Please don't just argue against each point but instead look to refine the statements where possible.

1.       Only curves over prime fields are being considered.

2.       Good, efficient implementations of Twisted Edwards curves will faster than good, efficient implementations of short Weierstrass with the same prime.

3.       Good, efficient Montgomery curve implementations are simpler than good, efficient Twisted Edwards and short Weierstrass curve implementations.

4.       Montgomery curves cannot be used for signing/verification operations.

5.       Small co-factor curves are no weaker, in terms of small subgroup attacks, than co-factor 1 curves.

6.       Twisted Edwards and short Weierstrass but not Montgomery curves support pools of points for ephemeral DH.

7.       NIST curves are going to be in use for some time.

8.       One curve at about WF-128 is required.

9.       At least one curve with WF greater than 128 is required.

10.   Good, efficient implementations of curves using special primes are significantly faster than good, efficient implementations using random primes.

11.   There are steps in performance based on the number of words used.

12.   There are a few special primes that are significantly faster than the step they are on.

13.   The curves chosen will be used for ECDH and ECDSA.

14.   The curves will be used in TLS and certificates.

If you have more truths then please add to this list.

Sean
--
Sean Parkinson | Consultant Software Engineer | RSA, The Security Division of EMC
Office +61 7 3032 5232 | Fax +61 7 3032 5299
www.rsa.com<http://www.rsa.com>

---

From: Watson Ladd <[email-masked]>
Date: Tue, 25 Nov 2014 08:34:54 -0800

On Mon, Nov 24, 2014 at 11:56 PM, Parkinson, Sean
<[email-masked]> wrote:
> Please don’t just argue against each point but instead look to refine the
> statements where possible.
>
>
>
> 2.       Good, efficient implementations of Twisted Edwards curves will
> faster than good, efficient implementations of short Weierstrass with the
> same prime.
>
> 3.       Good, efficient Montgomery curve implementations are simpler than
> good, efficient Twisted Edwards and short Weierstrass curve implementations.
>

This is incorrect: see DJB's "Curves, Coordinates and Computation
emails". One can retrieve y-coordinates from the Montgomery ladder.
In fact, 2 and 3 both need to be reworked in light of this email.

The correct statement is that curves with a complete addition law are
easy to work with, and that the Montgomery ladder is also very simple.
Curves have a complete addition law if they are isomorphic to Edwards
curves, which is almost the same as having a point of order 4. The
Montgomery ladder works for curves with a point of order 4. (I may
have gotten the conditions somewhat wrong: this is morally correct)

How the curve is presented on the wire doesn't change this: one does a
few fast calculations to put the point retrieved from the wire in the
preferred form for calculation, and a few fast ones at the end to put
it back in the form on the wire.

This is also missing security considerations: it's easy to get
multiplication correct with a complete addition law, much harder
without one. Edwards curves always have a complete addition law, while
Twisted Edwards may or may not, depending on the value $a$ being a
quadratic residue or not.

> 6.       Twisted Edwards and short Weierstrass but not Montgomery curves
> support pools of points for ephemeral DH.

What do you mean by pools of points? Do you mean fast fixed-based
exponentiation? In that case one can do a fast fixed-based
exponentiation on the isomorphic or isogenous Edwards curve, and use a
few fast computations to get the point on the Montgomery curve.

> 10.   Good, efficient implementations of curves using special primes are
> significantly faster than good, efficient implementations using random
> primes.
>
> www.rsa.com
> _______________________________________________
> Cfrg mailing list
> [email-masked]
> http://www.irtf.org/mailman/listinfo/cfrg
>

-- 
"Those who would give up Essential Liberty to purchase a little
Temporary Safety deserve neither  Liberty nor Safety."
-- Benjamin Franklin

---

From: "Parkinson, Sean" <[email-masked]>
Date: Tue, 25 Nov 2014 19:02:22 -0500

My understanding is that because you can't efficiently perform a point add operation of two random points with Montgomery curves then signature schemes are out.
Is there inefficient algorithms for performing point add on the Montgomery curve?
I intended to not include transforming points to other curve types. So maybe,
  4. Signing and verification operations on Montgomery curves is not possible.

I'm intentionally not talking about simplicity of implementations. That is making things more complicated and hiding the 'truths'.

Sorry, 'Pools of points' was my name for the technique of having a number of pre-generated points that are then added to each other to quickly generate new points for TLS PFS.

Sean

-----Original Message-----
From: Watson Ladd [mailto:[email-masked]] 
Sent: Wednesday, 26 November 2014 2:35 AM
To: Parkinson, Sean
Cc: [email-masked]
Subject: Re: [Cfrg] Elliptic curve evaluation truths

On Mon, Nov 24, 2014 at 11:56 PM, Parkinson, Sean <[email-masked]> wrote:
> Please don’t just argue against each point but instead look to refine 
> the statements where possible.
>
>
>
> faster than good, efficient implementations of short Weierstrass with 
> the same prime.
>

This is incorrect: see DJB's "Curves, Coordinates and Computation emails". One can retrieve y-coordinates from the Montgomery ladder.
In fact, 2 and 3 both need to be reworked in light of this email.

The correct statement is that curves with a complete addition law are easy to work with, and that the Montgomery ladder is also very simple.
Curves have a complete addition law if they are isomorphic to Edwards curves, which is almost the same as having a point of order 4. The Montgomery ladder works for curves with a point of order 4. (I may have gotten the conditions somewhat wrong: this is morally correct)

How the curve is presented on the wire doesn't change this: one does a few fast calculations to put the point retrieved from the wire in the preferred form for calculation, and a few fast ones at the end to put it back in the form on the wire.

This is also missing security considerations: it's easy to get multiplication correct with a complete addition law, much harder without one. Edwards curves always have a complete addition law, while Twisted Edwards may or may not, depending on the value $a$ being a quadratic residue or not.

> support pools of points for ephemeral DH.

What do you mean by pools of points? Do you mean fast fixed-based exponentiation? In that case one can do a fast fixed-based exponentiation on the isomorphic or isogenous Edwards curve, and use a few fast computations to get the point on the Montgomery curve.

--
"Those who would give up Essential Liberty to purchase a little Temporary Safety deserve neither  Liberty nor Safety."
-- Benjamin Franklin

---

From: "Parkinson, Sean" <[email-masked]>
Date: Tue, 25 Nov 2014 20:59:02 -0500

I can't say I've seen the point addition described in the literature, but always assumed that there are, and I've been assured there are equations.

How about:
4. Signing and verification operations on Montgomery curves is less efficient than on Twisted Edwards and short Weierstrass curves.

Sean

-----Original Message-----
From: Cfrg [mailto:[email-masked]] On Behalf Of Parkinson, Sean
Sent: Wednesday, 26 November 2014 10:02 AM
To: Watson Ladd
Cc: [email-masked]
Subject: Re: [Cfrg] Elliptic curve evaluation truths

Sean
--
Sean Parkinson | Consultant Software Engineer | RSA, The Security Division of EMC Office +61 7 3032 5232 | Fax +61 7 3032 5299 www.rsa.com

---

From: Michael Hamburg <[email-masked]>
Date: Tue, 25 Nov 2014 18:02:10 -0800

Usually Montgomery curves are used because they have a very simple and efficient x-only Montgomery ladder implementation, where the y coordinate is not computed, at least not in the inner loop.

It is not possible to add two points without some information about the y-coordinate.  However, if the y-coordinate is given (compressed on the wire, but uncompressed internally), then it possible to add points on a Montgomery curve.  That’s not what people will do, though.  Instead they’ll convert to (twisted) Edwards, where all the math is much simpler.  Depending on the signature form, it may be possible to verify without adding, but people probably won’t do that either.

Likewise, it is possible but not practical to use “pools of points” on a Montgomery curve.  Instead people will use Edwards form.

So I would state:

def) “Twisted Edwards” includes traditional Edwards curves with a = 1.

0) Every Montgomery curve is equivalent (isomorphic) to a Twisted Edwards curve.  Every Twisted Edwards curve is equivalent to a Montgomery or twisted Montgomery curve.  Every elliptic curve is equivalent to a short Weierstrass curve.

4) Signing and verification on a Montgomery curve practically requires using Twisted Edwards form.

6) Twisted Edwards and short Weierstrass curves support precomputed tables to speed up ephemeral DH.  Supporting this for Montgomery curves practically requires using Twisted Edwards form.

Nitpicking Watson’s claims:

Every curve supports the Montgomery ladder, often in several flavors.  Montgomery curves are used because they have a particularly simple and efficient Montgomery ladder.  A curve with a point of order 4 in some other form may have a somewhat slower or more complex Montgomery ladder than Montgomery curves.

Cheers,
— Mike

> On Nov 25, 2014, at 4:02 PM, Parkinson, Sean <[email-masked]> wrote:
>

---

From: "Paterson, Kenny" <[email-masked]>
Date: Wed, 26 Nov 2014 09:39:05 +0000

Hi Everyone,

Thanks for contributing to this thread. It's helpful in establishing some
facts that will help to inform our decision-making for people who are not
so aware of the basic issues. But, please, let's not get into huge amounts
of details here, as it will distract us from our main business.

On that front, I'm hoping we'll have some significant developments in the
next couple of days that will help us move forward with that main work of
selecting curves to recommend to the TLS WG.

Cheers

Kenny

On 26/11/2014 02:02, "Michael Hamburg" <[email-masked]> wrote:

>Usually Montgomery curves are used because they have a very simple and
>efficient x-only Montgomery ladder implementation, where the y coordinate
>is not computed, at least not in the inner loop.
>
>It is not possible to add two points without some information about the
>y-coordinate.  However, if the y-coordinate is given (compressed on the
>wire, but uncompressed internally), then it possible to add points on a
>Montgomery curve.  That¹s not what people will do, though.  Instead
>they¹ll convert to (twisted) Edwards, where all the math is much simpler.
> Depending on the signature form, it may be possible to verify without
>adding, but people probably won¹t do that either.
>
>Likewise, it is possible but not practical to use ³pools of points² on a
>Montgomery curve.  Instead people will use Edwards form.
>
>So I would state:
>
>def) ³Twisted Edwards² includes traditional Edwards curves with a = 1.
>
>0) Every Montgomery curve is equivalent (isomorphic) to a Twisted Edwards
>curve.  Every Twisted Edwards curve is equivalent to a Montgomery or
>twisted Montgomery curve.  Every elliptic curve is equivalent to a short
>Weierstrass curve.
>
>6) Twisted Edwards and short Weierstrass curves support precomputed
>tables to speed up ephemeral DH.  Supporting this for Montgomery curves
>practically requires using Twisted Edwards form.
>
>Nitpicking Watson¹s claims:
>
>Every curve supports the Montgomery ladder, often in several flavors.
>Montgomery curves are used because they have a particularly simple and
>efficient Montgomery ladder.  A curve with a point of order 4 in some
>other form may have a somewhat slower or more complex Montgomery ladder
>than Montgomery curves.
>
>Cheers,
>‹ Mike
>
>
>> My understanding is that because you can't efficiently perform a point
>>add operation of two random points with Montgomery curves then signature
>>schemes are out.
>> I'm intentionally not talking about simplicity of implementations. That
>>is making things more complicated and hiding the 'truths'.
>> 
>> Sorry, 'Pools of points' was my name for the technique of having a
>>number of pre-generated points that are then added to each other to
>>quickly generate new points for TLS PFS.
>> 
>> 
>> Sean
>> --
>>> Please don¹t just argue against each point but instead look to refine
>>Montgomery ladder works for curves with a point of order 4. (I may have
>>gotten the conditions somewhat wrong: this is morally correct)
>> 
>>preferred form for calculation, and a few fast ones at the end to put it
>>back in the form on the wire.
>> 
>>multiplication correct with a complete addition law, much harder without
>>one. Edwards curves always have a complete addition law, while Twisted
>>Edwards may or may not, depending on the value $a$ being a quadratic
>>residue or not.
>> 
>>> 
>>> 5.       Small co-factor curves are no weaker, in terms of small
>>>subgroup
>>> attacks, than co-factor 1 curves.
>>> 
>>> 12.   There are a few special primes that are significantly faster
>>>than the
>>> step they are on.
>>>

---

From: "Parkinson, Sean" <[email-masked]>
Date: Wed, 26 Nov 2014 18:31:11 -0500

Some of the statements are not as simple as they may at first appear.
By teasing out the facts from the disputed statements I was hoping to get clarity around where the groups thoughts are at.

Anyway, I am now looking forward to the significant developments!

Thanks Kenny,
Sean

-----Original Message-----
From: Paterson, Kenny [mailto:[email-masked]] 
Sent: Wednesday, 26 November 2014 7:39 PM
To: Michael Hamburg; Parkinson, Sean
Cc: [email-masked]
Subject: Re: [Cfrg] Elliptic curve evaluation truths

Hi Everyone,

Thanks for contributing to this thread. It's helpful in establishing some facts that will help to inform our decision-making for people who are not so aware of the basic issues. But, please, let's not get into huge amounts of details here, as it will distract us from our main business.

On that front, I'm hoping we'll have some significant developments in the next couple of days that will help us move forward with that main work of selecting curves to recommend to the TLS WG.

Cheers

Kenny

On 26/11/2014 02:02, "Michael Hamburg" <[email-masked]> wrote:

>efficient x-only Montgomery ladder implementation, where the y 
>coordinate is not computed, at least not in the inner loop.
>
>Likewise, it is possible but not practical to use ³pools of points² on 
>a Montgomery curve.  Instead people will use Edwards form.
>
>So I would state:
>
>0) Every Montgomery curve is equivalent (isomorphic) to a Twisted 
>Edwards curve.  Every Twisted Edwards curve is equivalent to a 
>Montgomery or twisted Montgomery curve.  Every elliptic curve is 
>equivalent to a short Weierstrass curve.
>
>< Mike
>> My understanding is that because you can't efficiently perform a 
>>point add operation of two random points with Montgomery curves then 
>>signature schemes are out.
>> I'm intentionally not talking about simplicity of implementations. 
>>That is making things more complicated and hiding the 'truths'.
>> 
>> Sean Parkinson | Consultant Software Engineer | RSA, The Security 
>>Division of EMC  Office +61 7 3032 5232 | Fax +61 7 3032 5299  
>>www.rsa.com
>> 
>> 
>>> Please don¹t just argue against each point but instead look to 
>>> refine the statements where possible.
>>> 
>>> 
>>> 
>>> faster than good, efficient implementations of short Weierstrass 
>>> with the same prime.
>>> 
>> How the curve is presented on the wire doesn't change this: one does 
>>a few fast calculations to put the point retrieved from the wire in 
>>the preferred form for calculation, and a few fast ones at the end to 
>>put it back in the form on the wire.
>> 
>>> significantly faster than good, efficient implementations using 
>>>random  primes.
>>>