Re: [Cfrg] Proposed requirements for curve candidate evaluation

Michael Hamburg <> Mon, 11 August 2014 21:39 UTC

Return-Path: <>
Received: from localhost ( []) by (Postfix) with ESMTP id CA0171A0142 for <>; Mon, 11 Aug 2014 14:39:19 -0700 (PDT)
X-Virus-Scanned: amavisd-new at
X-Spam-Flag: NO
X-Spam-Score: 1.555
X-Spam-Level: *
X-Spam-Status: No, score=1.555 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, FH_HOST_EQ_D_D_D_D=0.765, FH_HOST_EQ_D_D_D_DB=0.888, HELO_MISMATCH_ORG=0.611, HOST_MISMATCH_NET=0.311, RDNS_DYNAMIC=0.982, SPF_HELO_PASS=-0.001, SPF_PASS=-0.001] autolearn=no
Received: from ([]) by localhost ( []) (amavisd-new, port 10024) with ESMTP id SJ484oKhH8p6 for <>; Mon, 11 Aug 2014 14:39:18 -0700 (PDT)
Received: from ( []) (using TLSv1.1 with cipher AECDH-AES256-SHA (256/256 bits)) (No client certificate requested) by (Postfix) with ESMTPS id 8E1661A013B for <>; Mon, 11 Aug 2014 14:39:18 -0700 (PDT)
Received: from [] (unknown []) by (Postfix) with ESMTPSA id 77EB53AA27; Mon, 11 Aug 2014 14:38:13 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=simple/simple;; s=sldo; t=1407793093; bh=w4HmYPXODkh5DBsmjLoTmpY+GR6/ENAH0qwXxUGq76I=; h=Subject:From:In-Reply-To:Date:Cc:References:To:From; b=QDjUxMkP8R9kAF+kCUoFrI3DcBMZP1lE3XlnMha/Kw5tOMHuFx/EN7Fe+tlT2UI5k DkK+uTQJUGl8KPH+2zzYaIBTPMgOVuJYY6vD9q6NETwFNB5VY9uYmRgVBFqZh4in7c +sWwDrsNa41CA3TGP7UufnnCoqhMpAnJhSRfaDTs=
Content-Type: text/plain; charset="utf-8"
Mime-Version: 1.0 (Mac OS X Mail 8.0 \(1971.5\))
From: Michael Hamburg <>
In-Reply-To: <>
Date: Mon, 11 Aug 2014 14:39:14 -0700
Content-Transfer-Encoding: quoted-printable
Message-Id: <>
References: <>
To: Craig Costello <>
X-Mailer: Apple Mail (2.1971.5)
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:39:19 -0000

Ah, I see.  And the original has d = 78296 for ed-512-mers, which I was also wondering about.  Thanks.

> On Aug 11, 2014, at 2:13 PM, Craig Costello <> wrote:
> 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. 
> Cheers,
> Craig
> -----Original Message-----
> From: Cfrg [] On Behalf Of Michael Hamburg
> Sent: Thursday, August 7, 2014 6:24 PM
> To: Watson Ladd
> Cc:
> 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