Re: [Cfrg] Safecurves draft

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