Re: [Cfrg] Safecurves draft
Stephen Farrell <stephen.farrell@cs.tcd.ie> Wed, 08 January 2014 23:17 UTC
Return-Path: <stephen.farrell@cs.tcd.ie>
X-Original-To: cfrg@ietfa.amsl.com
Delivered-To: cfrg@ietfa.amsl.com
Received: from localhost (ietfa.amsl.com [127.0.0.1]) by ietfa.amsl.com (Postfix) with ESMTP id 34C5F1AD8F3 for <cfrg@ietfa.amsl.com>; Wed, 8 Jan 2014 15:17:45 -0800 (PST)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -2.438
X-Spam-Level:
X-Spam-Status: No, score=-2.438 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, RP_MATCHES_RCVD=-0.538] autolearn=ham
Received: from mail.ietf.org ([4.31.198.44]) by localhost (ietfa.amsl.com [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id ZxT_r23gzLls for <cfrg@ietfa.amsl.com>; Wed, 8 Jan 2014 15:17:41 -0800 (PST)
Received: from mercury.scss.tcd.ie (mercury.scss.tcd.ie [134.226.56.6]) by ietfa.amsl.com (Postfix) with ESMTP id BBA711AD8F2 for <cfrg@irtf.org>; Wed, 8 Jan 2014 15:17:40 -0800 (PST)
Received: from localhost (localhost [127.0.0.1]) by mercury.scss.tcd.ie (Postfix) with ESMTP id 196C3BE51; Wed, 8 Jan 2014 23:17:30 +0000 (GMT)
X-Virus-Scanned: Debian amavisd-new at scss.tcd.ie
Received: from mercury.scss.tcd.ie ([127.0.0.1]) by localhost (mercury.scss.tcd.ie [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id feFeT00koZSP; Wed, 8 Jan 2014 23:17:28 +0000 (GMT)
Received: from [10.87.48.14] (unknown [86.41.58.242]) by mercury.scss.tcd.ie (Postfix) with ESMTPSA id EFF59BE33; Wed, 8 Jan 2014 23:17:25 +0000 (GMT)
Message-ID: <52CDDC85.2000806@cs.tcd.ie>
Date: Wed, 08 Jan 2014 23:17:25 +0000
From: Stephen Farrell <stephen.farrell@cs.tcd.ie>
User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:24.0) Gecko/20100101 Thunderbird/24.2.0
MIME-Version: 1.0
To: Alyssa Rowan <akr@akr.io>, Watson Ladd <watsonbladd@gmail.com>
References: <CACsn0cmPj-=bfwCLJXvHSbOS_U5AfZH2vTWfrVsXwOXF4Y9hcg@mail.gmail.com> <52CD9B98.2010208@elzevir.fr> <CACsn0c=OqqF4QhW8RH-BD_wtFoBtQKfYWqsGQ0mYDxohk=VbXQ@mail.gmail.com> <52CDDAE2.50708@akr.io>
In-Reply-To: <52CDDAE2.50708@akr.io>
X-Enigmail-Version: 1.6
Content-Type: text/plain; charset="ISO-8859-1"
Content-Transfer-Encoding: 8bit
Cc: cfrg@irtf.org
Subject: Re: [Cfrg] Safecurves draft
X-BeenThere: cfrg@irtf.org
X-Mailman-Version: 2.1.15
Precedence: list
List-Id: Crypto Forum Research Group <cfrg.irtf.org>
List-Unsubscribe: <http://www.irtf.org/mailman/options/cfrg>, <mailto:cfrg-request@irtf.org?subject=unsubscribe>
List-Archive: <http://www.irtf.org/mail-archive/web/cfrg/>
List-Post: <mailto:cfrg@irtf.org>
List-Help: <mailto:cfrg-request@irtf.org?subject=help>
List-Subscribe: <http://www.irtf.org/mailman/listinfo/cfrg>, <mailto:cfrg-request@irtf.org?subject=subscribe>
X-List-Received-Date: Wed, 08 Jan 2014 23:17:45 -0000
-----BEGIN PGP SIGNED MESSAGE----- Hash: SHA1 In case it helps with formatting. A trick some people have done from time to time is to include a shell script as an appendix to a draft/RFC so that when you extract the script and run it with the draft/RFC as input it pulls out the examples/numbers and feeds them into a checker. Can't think of an example right now, but someone here will if you like the idea. S. On 01/08/2014 11:10 PM, Alyssa Rowan wrote: > 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.) > > _______________________________________________ Cfrg mailing list > Cfrg@irtf.org http://www.irtf.org/mailman/listinfo/cfrg > -----BEGIN PGP SIGNATURE----- Version: GnuPG v1.4.14 (GNU/Linux) iQEcBAEBAgAGBQJSzdyCAAoJEC88hzaAX42ipz4IAK5MH5upmdRMzL7Z6REW87Kp VEb4KlPSwlUrPOKNCjKv9UZHKU8TUmwH3rWAvprEj9QrXt/bbMo5b8MZmrheW2rr zLM/9yoMdkB2WXu2rQRNL8IOl1ip+7uD4trTOVJnHIYO4KQylDTR9u17igIdkQRY DqI0A2SdceCQ4FU6JCaXkQPZBtyI9HywE1O4UdL+m9YUidUi95CUUwm329mp2IAY Tj1ZVrxvVbAmlsHV7uk/0w0Qr/1UkOGRIVPwr3IBAgp4GM2kqNi0qMBsS20oX/E0 YuR/+vA1XRNhT2kq0O94hIJWFh0+nyjS4XZovhenHrBoNq+wWyvhh+aqLxp0Rmg= =qZyk -----END PGP SIGNATURE-----
- [Cfrg] Safecurves draft Watson Ladd
- Re: [Cfrg] Safecurves draft Stephen Farrell
- Re: [Cfrg] Safecurves draft Watson Ladd
- Re: [Cfrg] Safecurves draft Manuel Pégourié-Gonnard
- Re: [Cfrg] Safecurves draft Watson Ladd
- Re: [Cfrg] Safecurves draft Manuel Pégourié-Gonnard
- Re: [Cfrg] Safecurves draft Dan Harkins
- Re: [Cfrg] Safecurves draft Manuel Pégourié-Gonnard
- Re: [Cfrg] Safecurves draft Paul Lambert
- Re: [Cfrg] Safecurves draft Watson Ladd
- Re: [Cfrg] Safecurves draft Alyssa Rowan
- Re: [Cfrg] Safecurves draft Stephen Farrell
- Re: [Cfrg] Safecurves draft Alyssa Rowan
- Re: [Cfrg] Safecurves draft Stephen Farrell
- Re: [Cfrg] Safecurves draft Watson Ladd
- Re: [Cfrg] Safecurves draft Paul Lambert
- Re: [Cfrg] Safecurves draft Watson Ladd
- Re: [Cfrg] Safecurves draft Paul Lambert
- Re: [Cfrg] Safecurves draft Isaac Chua
- Re: [Cfrg] Safecurves draft Dan Brown
- Re: [Cfrg] Safecurves draft Manuel Pégourié-Gonnard
- [Cfrg] Fwd: Re: Safecurves draft Alyssa Rowan
- Re: [Cfrg] Fwd: Re: Safecurves draft Manuel Pégourié-Gonnard
- Re: [Cfrg] Safecurves draft Adam Back
- Re: [Cfrg] Fwd: Re: Safecurves draft Robert Ransom
- Re: [Cfrg] Fwd: Re: Safecurves draft Manuel Pégourié-Gonnard
- Re: [Cfrg] Safecurves draft Johannes Merkle
- Re: [Cfrg] Safecurves draft Bodo Moeller
- Re: [Cfrg] Safecurves draft Robert Ransom
- Re: [Cfrg] Safecurves draft Bodo Moeller
- Re: [Cfrg] Safecurves draft Robert Ransom
- Re: [Cfrg] Safecurves draft Bodo Moeller
- Re: [Cfrg] Fwd: Re: Safecurves draft Robert Ransom
- Re: [Cfrg] Safecurves draft Mike Hamburg
- Re: [Cfrg] Safecurves draft Watson Ladd
- Re: [Cfrg] Safecurves draft Jon Callas
- Re: [Cfrg] Safecurves draft Paul Lambert
- Re: [Cfrg] Safecurves draft Paul Lambert
- Re: [Cfrg] Safecurves draft Watson Ladd
- Re: [Cfrg] Safecurves draft Bodo Moeller
- Re: [Cfrg] Fwd: Re: Safecurves draft Manuel Pégourié-Gonnard
- Re: [Cfrg] Safecurves draft Robert Ransom
- Re: [Cfrg] Fwd: Re: Safecurves draft Robert Ransom