Re: [Cfrg] Adoption of draft-agl-cfrgcurve-00 as a RG document

Robert Ransom <> Tue, 20 January 2015 01:32 UTC

Return-Path: <>
Received: from localhost ( []) by (Postfix) with ESMTP id B553C1A898E for <>; Mon, 19 Jan 2015 17:32:44 -0800 (PST)
X-Virus-Scanned: amavisd-new at
X-Spam-Flag: NO
X-Spam-Score: -1.75
X-Spam-Status: No, score=-1.75 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, FREEMAIL_ENVFROM_END_DIGIT=0.25, FREEMAIL_FROM=0.001, SPF_PASS=-0.001] autolearn=no
Received: from ([]) by localhost ( []) (amavisd-new, port 10024) with ESMTP id I7j1fZl49_NL for <>; Mon, 19 Jan 2015 17:32:43 -0800 (PST)
Received: from ( [IPv6:2607:f8b0:400d:c04::233]) (using TLSv1 with cipher ECDHE-RSA-RC4-SHA (128/128 bits)) (No client certificate requested) by (Postfix) with ESMTPS id 1ED181A87D5 for <>; Mon, 19 Jan 2015 17:32:43 -0800 (PST)
Received: by with SMTP id z107so5931235qgd.10 for <>; Mon, 19 Jan 2015 17:32:42 -0800 (PST)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;; s=20120113; h=mime-version:in-reply-to:references:date:message-id:subject:from:to :cc:content-type; bh=A0KpmPlzjrkj9nNpOwgECQKXCCppQ+l9odxr18St6o0=; b=nWrdzJ72junK+9jtQlQD76ZYFk+e3XMHFFjEfKllLth430t0OIUK3C70hjOOrcbzSZ tmHAd7HlMwr+L2Aq+yCMj/WoPVxA9bvLZfIxlGeb+0qeffD1VBiRMb7FwskzbBIcLmP1 3OyjSNFdQpER1HpvV76VQvk0LYFk1ZU9MVOQMPqdcc+0n6E8hfuNnLpdQrl3LXjw5gng b+i0iqdFqIvYBlCoMocMY+Di/c1eVzAgbmotWPG9tX9IOo46UsopylPODBvmVm8g+IJ6 mVEN+SpW9J2RQcPWfJyveUXsz9yOF5zTn3yq6Um4j2KNeoCjkvt0+wUx9kPT3BLJZUu0 KZmQ==
MIME-Version: 1.0
X-Received: by with SMTP id h35mr24377200qgh.22.1421717562271; Mon, 19 Jan 2015 17:32:42 -0800 (PST)
Received: by with HTTP; Mon, 19 Jan 2015 17:32:42 -0800 (PST)
In-Reply-To: <20150119143928.GA6160@LK-Perkele-VII>
References: <> <> <20150119143928.GA6160@LK-Perkele-VII>
Date: Mon, 19 Jan 2015 17:32:42 -0800
Message-ID: <>
From: Robert Ransom <>
To: Ilari Liusvaara <>
Content-Type: text/plain; charset="UTF-8"
Archived-At: <>
Cc: "" <>
Subject: Re: [Cfrg] Adoption of draft-agl-cfrgcurve-00 as a RG document
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: Tue, 20 Jan 2015 01:32:44 -0000

On 1/19/15, Ilari Liusvaara <> wrote:
> On Sun, Jan 18, 2015 at 11:32:57PM -0800, Robert Ransom wrote:
>> * Curve3617 (also known as Curve41417) has cofactor 8, and is defined
>>   over a field of order congruent to 3 mod 4.  Accordingly, the curve
>>   selection procedure in draft-agl-cfrgcurve-00 will choose a
>>   different curve if applied to the field used for Curve3617.  (This
>>   point was previously raised to CFRG in
>>   <>.)
>>   The curve selection procedure specified in draft-agl-cfrgcurve-00
>>   will instead choose a curve with d > 2^19 (found by D. J. Bernstein
>>   (et al. ?), found again by Mike Hamburg, and found yet again and
>>   published recently by David Leon Gil), compared to d=3617 < 2^12 for
>>   Curve3617.  The parameter value for the twist-secure curve with
>>   cofactor 4 is so much larger than the parameter value for cofactor 8
>>   that the performance of at least one implementation strategy of some
>>   significance would be harmed by insisting on cofactor 4: current
>>   FPGAs contain 18-bit multipliers, and d > 2^19 almost guarantees a
>>   greater cost to multiply by the curve parameter.
> I got d=-142113 (#E<p)  (d=142114 if one additionally requires #E>p)
> These numbers are 18-bit in absolute value.

Thank you for the correction!  (David Leon Gil had reported a curve in
the isogeny class of a=1, d=-547072.)

I've recomputed the trace of the curve with a=1, d=-142113 using GP,
and it and its twist are indeed of order 4*prime.  The prime-order
subgroup of that curve has maximal multiplicative embedding degree
(r-1), and its twist's subgroup has multiplicative embedding degree
(r'-1)/4; the discriminant of its endomorphism ring is large; and the
factorizations involved in verifying those are fairly easy.

The parameter d=-142113 is still large enough to require more carrying
after multiplication by the curve parameter in an implementation which
uses 16-bit limbs and must reduce limbs to 16 bits each before
multiplication.  I'm not certain whether this would be the case for
FPGA-based implementations, but it is still enough of a difference in
parameter size that I would strongly prefer d=3617 for use with the
point format specified in draft-agl-cfrgcurve-00.

Robert Ransom