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

Robert Ransom <rransom.8774@gmail.com> Tue, 20 January 2015 01:32 UTC

Return-Path: <rransom.8774@gmail.com>
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 B553C1A898E for <cfrg@ietfa.amsl.com>; Mon, 19 Jan 2015 17:32:44 -0800 (PST)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -1.75
X-Spam-Level:
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 mail.ietf.org ([4.31.198.44]) by localhost (ietfa.amsl.com [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id I7j1fZl49_NL for <cfrg@ietfa.amsl.com>; Mon, 19 Jan 2015 17:32:43 -0800 (PST)
Received: from mail-qg0-x233.google.com (mail-qg0-x233.google.com [IPv6:2607:f8b0:400d:c04::233]) (using TLSv1 with cipher ECDHE-RSA-RC4-SHA (128/128 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id 1ED181A87D5 for <cfrg@irtf.org>; Mon, 19 Jan 2015 17:32:43 -0800 (PST)
Received: by mail-qg0-f51.google.com with SMTP id z107so5931235qgd.10 for <cfrg@irtf.org>; Mon, 19 Jan 2015 17:32:42 -0800 (PST)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; 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 10.140.32.166 with SMTP id h35mr24377200qgh.22.1421717562271; Mon, 19 Jan 2015 17:32:42 -0800 (PST)
Received: by 10.140.108.55 with HTTP; Mon, 19 Jan 2015 17:32:42 -0800 (PST)
In-Reply-To: <20150119143928.GA6160@LK-Perkele-VII>
References: <54AAE2CA.1080701@isode.com> <CABqy+sq7m9epnQho0gbjZzZ9pN4Y4osbuR0mypcAxHrTv_7nAA@mail.gmail.com> <20150119143928.GA6160@LK-Perkele-VII>
Date: Mon, 19 Jan 2015 17:32:42 -0800
Message-ID: <CABqy+spnYiiN1fkKD618NwzecVO-CY6Jt8Gw6ENCdVmtyToTQg@mail.gmail.com>
From: Robert Ransom <rransom.8774@gmail.com>
To: Ilari Liusvaara <ilari.liusvaara@elisanet.fi>
Content-Type: text/plain; charset=UTF-8
Archived-At: <http://mailarchive.ietf.org/arch/msg/cfrg/WsIZ9uTNKaFJvdDBnZvl8tKGlUA>
Cc: "cfrg@irtf.org" <cfrg@irtf.org>
Subject: Re: [Cfrg] Adoption of draft-agl-cfrgcurve-00 as a RG document
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: Tue, 20 Jan 2015 01:32:44 -0000

On 1/19/15, Ilari Liusvaara <ilari.liusvaara@elisanet.fi> 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
>>   <http://www.ietf.org/mail-archive/web/cfrg/current/msg05788.html>.)
>>
>>   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