Re: [Cfrg] normative references

[Paul Lambert <[e-mail]>]

Watson,

>>  ⨳|> There is a significant body of work on implementing Weierstrass
>>  ⨳|curves
>>  ⨳|> (ANSI, IEEE, NIST, NSA, etc.).  Edwards, Twisted Edwards and
>>  ⨳|> Montgomery need the same level of documentation to progress.
>>  ⨳|
>>  ⨳|Or the same level of C library support. I'd much rather have everyone
>>  ⨳|copy a well-made library then write their own bugs we have to deal
>>  ⨳|with down the line/that the SIGINT people exploit. But yes, better
>>  ⨳|documentation about how to implement is necessary.
>> We're in the documentation business here - not code libraries. Plus
>>we're
>> supposed to have multiple interoperable different implementations.
>
>Do you really think everyone implementing P256 does it themselves? Or do
>they
>take example code from the Internet?
I have seen a large number of P256 implementations … few if any from the
public domain.

Existence of an open source library is not an excuse for a sloppy RFC.  If
this is the direction you are going, we would just need to write a
one-line pointer to the source code.

Real products implement in hardware, on multiple processor types … etc.

I’ve been trying to be helpful, but your arguments against well intended
suggestions is frustrating.   It’s difficult to contribute if you’re
arguing for a sloppy RFC because the code is the reference.

I was pointing to specific examples that we could emulate in a perhaps
more simple manner.  The next step would be get a summary of the relevant
details required and emulate one or more of these documents.


>>  ⨳|If we aren't specifying any twisted Edwards curves, why would we
>>  ⨳|define the formulas?
>>  ⨳|I suppose for use with Montgomery form, ala Ransom's suggestion.
>> [ ⨳]
>> Yes ... and why did you leave out Ed25519?       It's being used and
>>should at least be discussed/reviewed/
>
>It's the same as Curve25519, and not in safecurves. Let's be real
>clear: isogenies don't change anything substantial.
Substantial???
Curve22519 is not interoperable with Ed25519. What could be more
substantial.  A point on one curve would have a different x and y value
than a curve on the other.
This is one of my core issues with having mathematicians write protocols …
the apparent mathematical precision make the implementations very fuzzy.


>If you want to discuss it separately, go ahead: plenty of people have
>been discussing alternatives on this list already.
Discuss …  no, let me be clear and rephrase.  Please add Ed25519 to the
RFC.

>
>I'm also going to explain the Montgomery ladder and double-and-add on
>Edwards and that's it. RFC 6090 doesn't talk about
>radix-k either, nor does it explain Shamir's trick, or fun with the
>Brier-Joyce ladder, or w-NAF, etc.
>>
>>
>>  ⨳|
>>  ⨳|>
>>  ⨳|>   2) reuse where possible terminology and variables from
>>Weierstrass
>>  ⨳|ECC
>>  ⨳|>      E.g.  P for prime defining Fp,  n for order, h for cofactor
>>  ⨳|>          This would allow all classes of curves to viewed equally
>>in
>>  ⨳|>          an implementation catalog
>>  ⨳|>           E.g.
>>  ⨳|>
>>  ⨳|>         curveId = 'curve25519'
>>  ⨳|>         strength = 127
>>  ⨳|>         oid = None
>>  ⨳|>         p  = 2**255-19
>>  ⨳|>         a  = 486662
>>  ⨳|>         xG = 9
>>  ⨳|>         yG =
>>...

...
>
>I still don't see why this form is much better than a paragraph
>listing these things.
>
>>  ⨳|Also, different things should be written differently.
>> [ ⨳]
>>
>> On the Edwards curves with cofactors >1 I believe the strength estimate
>>may be a little less
>> than simply taking the bit length of the size / 2
>>
>> Advice on this small adjustment would be appreciated.
>
>Size of the group generated by g, not the size of the curve.
Oh … of course, thanks.

>
>>
>>
>>  ⨳|
>>  ⨳|>     Also Š long numbers should be consistently represented hex
>>  ⨳|versus
>>  ⨳|> decimal
>>  ⨳|
>>  ⨳|Why hex? Most math papers use decimal, and more importantly GP/PARI
>>  ⨳|doesn't accept hex.
>>  ⨳|MAGMA, PARI and Sage are going to be used for test vector validation.
>> [ ⨳]
>> By you maybe ...
>>
>> Hex fits better in an RFC ...  decimal would be fine also.
>
>Six of one, half-dozen of the other.
>
>>
>>  ⨳|
>>  ⨳|>     Note also - Weierstrass Œa¹ is not the same as Edwards Œa¹, but
>>  ⨳|>     can be written around Š and we should keep Edwards equations
>>  ⨳|consistent
>>  ⨳|>     where possible with literature.
>>  ⨳|
>>  ⨳|When we define DH exchange on a group yes. With setting the
>>parameters
>>  ⨳|like you did we're tempting fate.
>> Not really ... just another area for clear specification, eg:
>>
>> Suggested RFC text:
>>
>>     The ECC definitions include three classes of curves defined over
>>the field
>>     of integers modulo a prime p (Fp).  Each class of curve has an
>>equation and
>>     assoicated parameters unique to the class type.  Three classes of
>>curves
>>     are described:
>>
>>       SmallWeierstrassCurveFp       y**2 = x**3 + a*x + b  mod p
>>       EdwardsCurveFp         x**2 + y**2 = c*(1 + d*x**2 * y**2)  mod p
>>       MontgomeryCurveFp             y**2 = x**3 + a*x**2 + x  mod p
>>
>>     The defintions include for each curve type:
>>
>>       curveId - An ASCII string used to identify the curve parameters
>>       strength - an integer providing the estimated cryptographic
>>strength
>>                  of the curve as a power of 2
>>       oid - a list of integers that correspond to the associated ASN.1
>>object
>>             identifier. The oid is listed as 'None' if there is no
>>assigned oid
>>       p - The prime modulus of the group (Fp). Often p is a Mersenne
>>prime
>>           to facilitate more efficient modular inversion
>>       xG - the x-coordinate of a generator point G for the curve
>>       yG - the y-coordinate of a generator point G for the curve
>>       n  - the order of the generator point G
>>       seed - included for reference when available
>>       h - the cofactor of the curve
>>
>>     Each curve type has the following unique parameters
>>
>>       Small Wierstrass      y**2 = x**3 + a*x + b  mod p
>>         a - often set to p-3 for efficiency
>>         b - elected for the security properties of the curve shape
>>         z - used by 'twisted' Brainpool curves for isogenous transform
>>             of untwisted curve to a curve with a = p-3
>>
>>       Montgomery            y**2 = x**3 + c*x**2 + x  mod p
>>         a - selected for the security properties of the curve shape
>>
>>       Edwards               x**2 + y**2 = c*(1 + d*x**2 * y**2) mod p
>>         c - typically set to 1 so the equation is reduced to:
>>                             x**2 + y**2 = 1 + d*x**2 * y**2  mod p
>>         d - selected for the security properties of the curve shape
>>
>> Hummm .. could add Twisted Edwards to the above
>
>But none of the curves in safecurves are presented in twisted Edwards
>form,
>I'm not going to rehash short Weierstrass here, (RFC 6090 already exists).

Ok … but introducing Weierstrass allows comparisons and clarity of
specification.
No eed to fully define Weierstrass … it’s just easier to have a complete
view
of all options.

Paul


>
>Anyway, I think this conversation would be far more productive when I
>finish the revisions and put it before
>the group again. You can follow on github in between.
>
>>
>>  ⨳|
>>  ⨳|>
>>  ⨳|>
>>  ⨳|>   3) Use math representation in RFCs that maps directly to a
>>  ⨳|computer
>>  ⨳|>      language notation - Python would be a good choice for
>>  ⨳|>      readability.
>>  ⨳|>      E.g. Twisted Edwards point addition definition
>>  ⨳|>
>>  ⨳|>        x3 = ((x1*y2+x2*y1) * inv(1+d*x1*x2*y1*y2)) % p
>>  ⨳|>        y3 = ((y1*y2-a*x1*x2) * inv(1-d*x1*x2*y1*y2)) % p
>>  ⨳|
>>  ⨳|The math notation I am using maps directly to that of most CAS
>> [ ⨳]
>> No - for example:
>> " On Montgomery curves, curves of the form y^2=x^3+Ax^2+x, the typical"
>> is Ax a variable 'Ax' or A*x ... this is sloppy non-parseable notation
>
>>  ⨳|systems. Anyway, at some point I will be done with the major
>>revision,
>>  ⨳|and kick it around for comments.
>> [ ⨳]
>> CAS???
>> I prefer running code useable for a protocol implementation.
>
>So I can just copy the relevant parts of tweetnacl.c and be done with it?
>
>>
>> Paul
>>
>>  ⨳|
>>  ⨳|>
>>  ⨳|>    4) curve names need consolidation and should clearly indicate
>>  ⨳|curve
>>  ⨳|> type
>>  ⨳|
>>  ⨳|Blame Tanja. I really do not like the idea of changing existing names
>>  ⨳|especially when referring people to papers with them. SEC/NIST has
>>  ⨳|already caused enough confusing as it is.
>> [ ⨳]
>> No need to blame, just make the change but  include reference to
>>original author and curve name.
>> NIST did not add confusion ... just branded the results.
>> CFRG branding would be valuable.  More curves will happen and  a
>>consistent notation is a good thing.
>
>What do you propose for the name scheme? E,M with prime in the expc
>format is my best proposal, but this might not be unique all the time.
>>
>> Paul
>>
>>  ⨳|
>>  ⨳|>
>>  ⨳|>
>>  ⨳|>
>>  ⨳|>
>>  ⨳|> Paul
>>  ⨳|>
>>  ⨳|>
>>  ⨳|>
>>  ⨳|> >
>>  ⨳|> >David
>>  ⨳|> >
>>  ⨳|> >>
>>  ⨳|> >> Thanks,
>>  ⨳|> >>     Yaron
>>  ⨳|> >>
>>  ⨳|> >> _______________________________________________
>>  ⨳|> >> Cfrg mailing list
>>  ⨳|> >> [e-mail]
>>  ⨳|> >> http://www.irtf.org/mailman/listinfo/cfrg
>>  ⨳|> >>
>>  ⨳|> >
>>  ⨳|> >_______________________________________________
>>  ⨳|> >Cfrg mailing list
>>  ⨳|> >[e-mail]
>>  ⨳|> >http://www.irtf.org/mailman/listinfo/cfrg
>>  ⨳|>
>>  ⨳|> _______________________________________________
>>  ⨳|> Cfrg mailing list
>>  ⨳|> [e-mail]
>>  ⨳|> 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