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" <mike@shiftleft.org> 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.
>
>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 <sean.parkinson@rsa.com>
>>wrote:
>> 
>> 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
>> --
>> Sean Parkinson | Consultant Software Engineer | RSA, The Security
>>Division of EMC
>> Office +61 7 3032 5232 | Fax +61 7 3032 5299
>> www.rsa.com
>> 
>> 
>> -----Original Message-----
>> From: Watson Ladd [mailto:watsonbladd@gmail.com]
>> Sent: Wednesday, 26 November 2014 2:35 AM
>> To: Parkinson, Sean
>> Cc: cfrg@irtf.org
>> Subject: Re: [Cfrg] Elliptic curve evaluation truths
>> 
>> On Mon, Nov 24, 2014 at 11:56 PM, Parkinson, Sean
>><sean.parkinson@rsa.com> wrote:
>>> 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.
>> 
>> 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.
>> 
>>> 
>>> 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.
>> 
>> 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.
>> 
>>> 
>>> 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
>>> 
>>> 
>>> 
>>> 
>>> _______________________________________________
>>> Cfrg mailing list
>>> Cfrg@irtf.org
>>> 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
>> _______________________________________________
>> Cfrg mailing list
>> Cfrg@irtf.org
>> http://www.irtf.org/mailman/listinfo/cfrg
>
>_______________________________________________
>Cfrg mailing list
>Cfrg@irtf.org
>http://www.irtf.org/mailman/listinfo/cfrg