Re: [Cfrg] Safecurves draft

[Watson Ladd <[e-mail]>]

I asked Tanja about the two curves. The answer is that (A-2)/4 should
be small, but this is an efficiency problem with one of them, not
a security issue. My elligator belief was based on a misreading of a table.
I'll take out the bad one in the next version.
I'll add E521 and copy the formatting in the 01 draft, which I'll post
as soon as a few days go by the fix
Thanks for spotting the typos.

I don't want to rename curves because that induces consistency issues.
Removing dashes is a good idea.

The EFD formulas will go in appendix to address the URL problem, and
to address some people's desire for explicit formulas.
For validation I give you a point on the curve and a claimed order:
the Hasse-Weil bound plus a quick multiply does the rest. Validation
isn't normative, so I think we can refer people to safecurves.

On Wed, Jan 8, 2014 at 3:10 PM, Alyssa Rowan <[e-mail]> wrote:
> -----BEGIN PGP SIGNED MESSAGE-----
> Hash: SHA512
>
> Glad to see this one get under way.
>
> I'm strongly in favour of the meat of the proposal.
>
> I have a couple of comments (mostly typographical and/or clarity).
>
> Maybe we should give an estimate of security (bitwise). [SAFECURVES]
> calculates that and otherwise it isn't crystal-clear from the names
> which curves would be about suitable for which security level.
>
> Any particular reason why Curve1174 wasn't included, as it's in the
> same strength category as Curve25519? (See below, for roughly how it
> would look if I think we did go for it?)
>
>>> Also, is it on purpose that you didn't include E-521 in your
>>> draft?
>> I simply copied the safecurves.cr.yp.to list starting at
>> Curve25519. There is no E-521 on that list.
>
> E-521 is in the revised reference in [2013 Aranha-Barreto-Pereira-
> Ricardini] <http://eprint.iacr.org/2013/647.pdf>. It looks like djb
> and Tanja Lange haven't finished putting it through all their own
> checks yet; at present it's on some pages (fields, rho, transfers,
> discriminants) but not others (base points, rigidity).
>
> It looks like they're mid-way through checking it. It'll very probably
> pass (identical design criteria; all its peers in the same paper did).
> Put it in the draft, take it out if for some reason it doesn't?
>
>>> why are there two Montgomery curves over GF(2^383-187)?
>> It's because one has an Elligator map and the other does not.
>
> You mean, an Elligator-1 map? (They all have Elligator-2 maps.)
>
> [2013 Aranha-Barreto-Pereira-Ricardini] version 20131031:234129
> replaces Curve383187 with an M-383 prototype with the following comment:
>     "Replaced the curve over the 383-bit field by a more
>      implementation-friendly curve."
>
> A's a little higher in that exact revision, but it appears they found
> a lower suitable one in November. The final M-383 is the one
> SafeCurves reviewed, although the older Curve383187 also passed.
>
>> Some applications require it, but not all.
>
> Not sure if there's a lot of point in having two Monty curves of the
> exact same field?
>
> [Typographical notes]
>
> The parameters for E-382 seem to be are miscopied in -00. Should be
> 2^382-105, and x²+y²=1-67254x²y² (not 2^382-15 and x²+y²=1-6725254x²y²).
>
> I suggest considering taking the dashes out of the canonical names
> People are going to refer to these in config files and command lines
> and heaven knows where else, so avoiding punctuation may be convenient
> (which I guess may be why none of the other curve names I can see used
> in IETF standards have any).
>
> For consistency, perhaps Curve1174, Curve25519, and Curve3617
> could be called in the standard after the formula and prime size (as in
> [2013 ABPR]), which would make them M255, E251, and E414 respectively?
> I've done that below; how does it look?
>
> I have honestly little idea about formatting of these things (other
> than that the canonical version is ASCII, like this email), but the
> way the basepoint and order are formatted is a little bit confusing as
> it is in draft-00.
>
> With the above in mind, how about something broadly like this?
>
> ==========================================================================
>
> 2. The Curves
>
>    Each curve is given by an equation and a basepoint, together with an
>    order. All curves are elliptic. Validation information is given at
>    [SAFECURVES]. The names given in this document indicate the family:
>    safecurveExxx for Edwards curves over a prime field GF(p), and
>    safecurveMxxx for Montgomery curves over a prime field GF(p).
>
>    * safecurveE251 (also known as Curve1174) [[ Do we want this one? ]]
>      p: 2^251-9
>      formula: x^2+y^2 = 1-1174x^2y^2
>      basepoint:
>         x: 1582619097725911541954547006453739763381091388846394833492
>            296309729998839514
>            (0x037FBB0C EA308C47 9343AEE7 C029A190
>               C021D96A 492ECD65 16123F27 BCE29EDA)
>         y: 3037538013604154504764115728651437646519513534305223422754
>            827055689195992590
>            (0x06B72F82 D47FB7CC 66568411 69840E0C
>               4FE2DEE2 AF3F976B A4CCB1BF 9B46360E)
>      [[ Rigidity note: This is the Edwards mapping of the Montgomery
>         point x=4, y=192257776421116702304087124422055147834030127084
>         09058383774613284963344096.
>         <http://cr.yp.to/elligator/elligator-20130527.pdf> ]]
>      Security versus rho: 2^124.3; twist: 2^124.3; combined: 2^123.3
>      order: 2^249 - 11332719920821432534773113288178349711
>
>    * safecurveM255 (also known as Curve25519)
>      p: 2^255-19
>      formula: y^2 = x^3+486662x^2+x
>      basepoint:
>         x: 9 (0x9)
>         y: 1478161944758954479102059356840998688726460613461647528896
>            4881837755586237401
>            (0x20AE19A1 B8A086B4 E01EDD2C 7748D14C
>               923D4D7E 6D7C61B2 29E9C5A2 7ECED3D9)
>      Security versus rho: 2^125.8; twist: 2^126.3; combined: 2^124.3
>      order: 2^252 + 27742317777372353535851937790883648493
>
>    * safecurveE382
>      p: 2^382-105
>      formula: x^2+y^2 = 1-67254x^2y^2
>      basepoint:
>         x: 3914921414754292646847594472454013487047137431784830634731
>            377862923477302047857640522480241298429278603678181725699
>            (0x196F8DD0 EAB20391 E5F05BE9 6E8D20AE
>               68F84003 2B0B6435 2923BAB8 53648411
>               93517DBC E8105398 EBC0CC94 70F79603)
>         y: 17 (0x11)
>      [[ Note: <http://eprint.iacr.org/2013/647.pdf> has different
>         basepoint y=13. Check: is that just a different mapping i.e.
>         Monty vs Eddie, or has the basepoint changed? If so, why? ]]
>      Security versus rho: 2^189.8; twist: 2^189.8; combined: 2^188.8
>      order: 2^380 - 1030303207694556153926491950732314247062623204330
>                     168346855
>
>    * safecurveM383
>      p: 2^383-187
>      formula: y^2 = x^3+2065150x^2+x
>      basepoint:
>         x: 12 (0xC)
>         y: 4737623401891753997660546300375902576839617167257703725630
>            389791524463565757299203154901655432096558642117242906494
>            (0x1EC7ED04 AAF834AF 310E304B 2DA0F328
>               E7C165F0 E8988ABD 39928612 90F617AA
>               1F1B2E7D 0B6E332E 969991B6 2555E77E)
>      Security versus rho: 2^189.8; twist: 2^190.3; combined: 2^188.3
>      order: 2^380 + 1662362759313735161052197949355421533080392344557
>                     61613271
>
>    * safecurveE414 (also known as Curve3617)
>      p: 2^414-17
>      formula: x^2+y^2 = 1+3617x^2y^2
>      basepoint:
>         x: 1731988647712118917771920249882261544355695730760434081525
>            6226171904769976866975908866528699294134494857887698432266
>            169206165
>            (0x1A334905 14144330 0218C063 1C326E5F
>               CD46369F 44C03EC7 F57FF354 98A4AB4D
>               6D6BA111 301A73FA A8537C64 C4FD3812
>               F3CBC595)
>         y: 34 (0x22)
>      Security versus rho: 2^205.3; twist: 2^205.3; combined: 2^203.8
>      order: 2^411 - 3336414086375514252081017769409838517898472720041
>                     1208589594759
>
>    * safecurveM511
>      p: 2^511-187
>      formula: y^2 = x^3+530438x^2+x
>      basepoint:
>         x: 5 (0x5)
>         y: 2500410645565072423368981149139213252211568685173608590070
>            9792642482752286038997069505181278171765918786677842475821
>            24505430745177116625808811349787373477
>            (0x2FBDC0AD 8530803D 28FDBAD3 54BB488D
>               32399AC1 CF8F6E01 EE3F9638 9B90C809
>               422B9429 E8A43DBF 49308AC4 455940AB
>               E9F1DBCA 542093A8 95E30A64 AF056FA5)
>      Security versus rho: 2^253.8; twist: 2^254.3; combined: 2^252.3
>      order: 2^508 + 1072475475963574762404453151406812184207075662743
>                     4833028965540808827675062043
>
>    * safecurveE521 [[ currently awaiting Safecurves approval ]]
>      p: 2^521-1
>      formula: x^2+y^2 = 1+376014x^2y^2
>      basepoint:
>         x: 2500410645565072423368981149139213252211568685173608590070
>            9792642482752286038997069505181278171765918786677842475821
>            24505430745177116625808811349787373477
>            (0x2FBDC0AD 8530803D 28FDBAD3 54BB488D
>               32399AC1 CF8F6E01 EE3F9638 9B90C809
>               422B9429 E8A43DBF 49308AC4 455940AB
>               E9F1DBCA 542093A8 95E30A64 AF056FA5)
>         y: 6 (0x6)
>      Security versus rho: 2^259.3; twist: 2^259.3; combined: 2^258.3
>      order: 2^519 - 3375547632585017057891076304187826360719049612140
>                     51226618635150085779108655765
>
> ==========================================================================
>
> Thoughts?
>
> (_Please_ cross-check the data thoroughly; I may well have made a
> typographical or calculation error of my own, and of course, extra
> checking is a good thing! Apologies in advance if I have; thanks for
> any extra pairs of eyes.)
>
> - --
> /akr
> -----BEGIN PGP SIGNATURE-----
>
> iQIcBAEBCgAGBQJSzdriAAoJEOyEjtkWi2t6WIwP/0U70JKAV3WOnbZcMB58rtSM
> Ru7loFhn9TvU3jw/p+H2tvmeUs08hKYDUUWavp7/x1B9TX3t+j3rADsWkoN/pQQd
> obr8AMdOF6QiupCjSbeZoq+wLMIiZKX3IV0pSzaO8FpTdBrIzjXTHgPy1We8H7eC
> Wkc2VC6f6eX/qyjKm6Fh3CdySJZ2dPy0X96HBqcwOMd5/hmR7VQ4DNxMEOHEfCVA
> Z2WwwYl2xNxOQ1Dn9kb4FU6CVRCc4/7DENZ+2FrCWUp1zG/3d8mUGzpGVunOv9ed
> rKKHnR9fhYjhfNSmGuTfLHTXc5mVqmEjZzmX0u1UR1CEktEKN/Nu2DMbPHToNVAA
> D7znHER4JZ8eMf3zLTslp8Uw0QkOhJiYZpDm24qb5urBLmlu55s6tYerCFEH4hDn
> R5DUPVURTgCbnpSGolKwJ2lBz8zQxzKCi9QoWV/VDNasg0L/ADIJeJUfpqdByWAz
> jFaFSVAgmf8df7X9WflV8ZCPkuoMszNZ9iGJn7AQTqUbjsMDfvqmOLfvFHD4Srzt
> tJtmDEL62O8Wml2zHN5hG/6ltfj9EZC+hl/EBSSCG1+nMqVodic5v4+E/lLU23/x
> db+l3PCsREZIURuT7o0YxukolV+93zbNlfOtd93HgB018rSeS+PBJ3yljN25h1Aa
> 5GNONjspxg93Z219jaNX
> =FUIv
> -----END PGP SIGNATURE-----
> _______________________________________________
> 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