Re: [Cfrg] Safecurves draft

Alyssa Rowan <> Wed, 08 January 2014 23:10 UTC

Return-Path: <>
Received: from localhost ( []) by (Postfix) with ESMTP id 202E31AD8EB for <>; Wed, 8 Jan 2014 15:10:30 -0800 (PST)
X-Virus-Scanned: amavisd-new at
X-Spam-Flag: NO
X-Spam-Score: -1.902
X-Spam-Status: No, score=-1.902 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, SPF_HELO_PASS=-0.001, SPF_PASS=-0.001] autolearn=ham
Received: from ([]) by localhost ( []) (amavisd-new, port 10024) with ESMTP id Ivk64C0-LLNF for <>; Wed, 8 Jan 2014 15:10:25 -0800 (PST)
Received: from ( []) by (Postfix) with ESMTP id 5D2E71AD0EA for <>; Wed, 8 Jan 2014 15:10:25 -0800 (PST)
Received: from [] ( []) by (Postfix) with ESMTPSA id 902F360433 for <>; Wed, 8 Jan 2014 23:10:14 +0000 (GMT)
Message-ID: <>
Date: Wed, 08 Jan 2014 23:10:26 +0000
From: Alyssa Rowan <>
MIME-Version: 1.0
References: <> <> <>
In-Reply-To: <>
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: 8bit
Subject: Re: [Cfrg] Safecurves draft
X-Mailman-Version: 2.1.15
Precedence: list
List-Id: Crypto Forum Research Group <>
List-Unsubscribe: <>, <>
List-Archive: <>
List-Post: <>
List-Help: <>
List-Subscribe: <>, <>
X-List-Received-Date: Wed, 08 Jan 2014 23:10:30 -0000

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 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] <>. 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
        x: 1582619097725911541954547006453739763381091388846394833492
           (0x037FBB0C EA308C47 9343AEE7 C029A190
              C021D96A 492ECD65 16123F27 BCE29EDA)
        y: 3037538013604154504764115728651437646519513534305223422754
           (0x06B72F82 D47FB7CC 66568411 69840E0C
              4FE2DEE2 AF3F976B A4CCB1BF 9B46360E)
     [[ Rigidity note: This is the Edwards mapping of the Montgomery
        point x=4, y=192257776421116702304087124422055147834030127084
        <> ]]
     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
        x: 9 (0x9)
        y: 1478161944758954479102059356840998688726460613461647528896
           (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
        x: 3914921414754292646847594472454013487047137431784830634731
           (0x196F8DD0 EAB20391 E5F05BE9 6E8D20AE
              68F84003 2B0B6435 2923BAB8 53648411
              93517DBC E8105398 EBC0CC94 70F79603)
        y: 17 (0x11)
     [[ Note: <> 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

   * safecurveM383
     p: 2^383-187
     formula: y^2 = x^3+2065150x^2+x
        x: 12 (0xC)
        y: 4737623401891753997660546300375902576839617167257703725630
           (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

   * safecurveE414 (also known as Curve3617)
     p: 2^414-17
     formula: x^2+y^2 = 1+3617x^2y^2
        x: 1731988647712118917771920249882261544355695730760434081525
           (0x1A334905 14144330 0218C063 1C326E5F
              CD46369F 44C03EC7 F57FF354 98A4AB4D
              6D6BA111 301A73FA A8537C64 C4FD3812
        y: 34 (0x22)
     Security versus rho: 2^205.3; twist: 2^205.3; combined: 2^203.8
     order: 2^411 - 3336414086375514252081017769409838517898472720041

   * safecurveM511
     p: 2^511-187
     formula: y^2 = x^3+530438x^2+x
        x: 5 (0x5)
        y: 2500410645565072423368981149139213252211568685173608590070
           (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

   * safecurveE521 [[ currently awaiting Safecurves approval ]]
     p: 2^521-1
     formula: x^2+y^2 = 1+376014x^2y^2
        x: 2500410645565072423368981149139213252211568685173608590070
           (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



(_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.)

- --