Re: [Cfrg] Proposed requirements for curve candidate evaluation

Craig Costello <> Mon, 11 August 2014 21:13 UTC

Return-Path: <>
Received: from localhost ( []) by (Postfix) with ESMTP id 9E2221A0114 for <>; Mon, 11 Aug 2014 14:13:39 -0700 (PDT)
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, RCVD_IN_DNSWL_NONE=-0.0001, SPF_HELO_PASS=-0.001, SPF_PASS=-0.001] autolearn=ham
Received: from ([]) by localhost ( []) (amavisd-new, port 10024) with ESMTP id K-iTNxh6s86Y for <>; Mon, 11 Aug 2014 14:13:33 -0700 (PDT)
Received: from ( []) (using TLSv1 with cipher ECDHE-RSA-AES256-SHA (256/256 bits)) (No client certificate requested) by (Postfix) with ESMTPS id 61FC01A010D for <>; Mon, 11 Aug 2014 14:13:33 -0700 (PDT)
Received: from ( by ( with Microsoft SMTP Server (TLS) id 15.0.1005.10; Mon, 11 Aug 2014 21:13:31 +0000
Received: from ([]) by ([]) with mapi id 15.00.1005.008; Mon, 11 Aug 2014 21:13:31 +0000
From: Craig Costello <>
To: "" <>
Thread-Topic: [Cfrg] Proposed requirements for curve candidate evaluation
Thread-Index: Ac+1p8M4TlgY/Wd0SkayoAdFUTPGxw==
Date: Mon, 11 Aug 2014 21:13:31 +0000
Message-ID: <>
Accept-Language: en-US
Content-Language: en-US
x-originating-ip: [2001:4898:80e8:ed31::2]
x-microsoft-antispam: BCL:0;PCL:0;RULEID:;UriScan:;
x-forefront-prvs: 03008837BD
x-forefront-antispam-report: SFV:NSPM; SFS:(979002)(6009001)(51704005)(377454003)(24454002)(199002)(189002)(13464003)(74662001)(74502001)(31966008)(99396002)(80022001)(107046002)(20776003)(64706001)(77982001)(86362001)(4396001)(2351001)(21056001)(83072002)(105586002)(99286002)(79102001)(81542001)(95666004)(81342001)(85306004)(76482001)(15202345003)(106356001)(33646002)(83322001)(50986999)(101416001)(54356999)(87936001)(46102001)(92566001)(85852003)(74316001)(110136001)(19580405001)(86612001)(19580395003)(15975445006)(2656002)(76576001)(2501001)(24736002)(3826002)(108616003)(969003)(989001)(999001)(1009001)(1019001); DIR:OUT; SFP:; SCL:1; SRVR:BL2PR03MB481;; FPR:; MLV:ovrnspm; PTR:InfoNoRecords; MX:1; LANG:en;
Content-Type: text/plain; charset="utf-8"
Content-Transfer-Encoding: base64
MIME-Version: 1.0
Cc: "" <>
Subject: Re: [Cfrg] Proposed requirements for curve candidate evaluation
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: Mon, 11 Aug 2014 21:13:40 -0000

Hey Mike,

Good question, I’ll explain the difference between the “ed-521-mers” curve and E-521.

Over any chosen prime field, we searched for the twisted Edwards curve E:–x^2+y^2=1+d*x^2*y^2 with smallest *positive* d such that #E<#E’, where E’ is the quadratic twist of E. Many of our chosen primes in the preprint are 64-bit aligned, so we always take E to be the twist with the positive trace; enforcing that means that #E is also 64-bit aligned. The reason we want the smaller sized twist to correspond to the small positive d is that we wanted our implementations to be modular across different security levels – we wanted the formulas to take advantage of the “smallness” of d without worrying about its sign, so our condition became the smallest d>0 such that tr(E)>0 and both twists have cofactor 4. 

The condition d>0 with tr(E)>0 was something we decided on when working on modular implementations for the 6 NUMS curves in the MSR ECCLib release, where we also decided it was best to focus only on the twisted Edwards form of cofactor 4 curves. Originally, when we were also researching the performance of the Montgomery form, our searches prioritized curves with the smallest Montgomery constant (A+2)/4 without caring which twist it was on, so you will notice that in Table 2 of the first version of our preprint ( – posted Feb 24th), the curve “ed-521-mers” is presented in Montgomery form y^2=x^3+A*x^2+x with A=1504058. This original curve is isogenous to E-521 (Section 3.3 of our latest preprint shows why the smallest constants coincide when p==3 mod 4), but its twisted Edwards form has the negative d, so we had to search a little higher to satisfy the d>0 requirement. 


-----Original Message-----
From: Cfrg [] On Behalf Of Michael Hamburg
Sent: Thursday, August 7, 2014 6:24 PM
To: Watson Ladd
Subject: Re: [Cfrg] Proposed requirements for curve candidate evaluation

> On Aug 7, 2014, at 6:03 PM, Watson Ladd <> wrote:
> E-521 was discovered by three groups independently. There are not that 
> many primes near a power of two, and not that many choices of curve 
> shape. How would we make the process "more rigid?”

On a related note, Brian, do you know why E-521 (or rather, a curve isogenous to E-521 or its twist) isn’t the Microsoft ed-521-mers curve?  Is there something simple I’m missing here?  It seems like that gives a smaller d0 coefficient than the one you chose.

— Mike
Cfrg mailing list