Re: [Cfrg] Safecurves draft

[Alyssa Rowan <[e-mail]>]

-----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-----