Re: [Cfrg] Chopping out curves

Watson Ladd <watsonbladd@gmail.com> Fri, 17 January 2014 15:18 UTC

Return-Path: <watsonbladd@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 10C471AE0F1 for <cfrg@ietfa.amsl.com>; Fri, 17 Jan 2014 07:18:01 -0800 (PST)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -0.878
X-Spam-Level:
X-Spam-Status: No, score=-0.878 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, FREEMAIL_FROM=0.001, SPF_PASS=-0.001, URI_HEX=1.122] 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 BSMLy12mOFrU for <cfrg@ietfa.amsl.com>; Fri, 17 Jan 2014 07:17:59 -0800 (PST)
Received: from mail-wi0-x22b.google.com (mail-wi0-x22b.google.com [IPv6:2a00:1450:400c:c05::22b]) by ietfa.amsl.com (Postfix) with ESMTP id BD0E01ACCEF for <cfrg@irtf.org>; Fri, 17 Jan 2014 07:17:58 -0800 (PST)
Received: by mail-wi0-f171.google.com with SMTP id cc10so833035wib.4 for <cfrg@irtf.org>; Fri, 17 Jan 2014 07:17:45 -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:content-transfer-encoding; bh=+qFVspZojN1GNI2YtSVzDgUwe/LULmqOArb760PGTfg=; b=tkJDVbW19MXtgkQj1D9rOTj+fEca9UXchqdOpRvApZFXe5q7W29mTsJAkJAc2/qKf+ F9z1pONMpt4WjJSRqieQ+KpWdvaLkADXIV9rH1YIABgbn9IPbvbt7sgvNEejs+6odnG/ pJiNjF2N9J37vKZ3NwyUnso/oMUvYVHWEsU6vEG9T3d2iP6FJrhUWrNo/qqYIDRIXBe/ myCqb+tbRKMwT2dn0ZBKnjbwrW+CKdY7YG0wn85tV9QE7s+f8i7mTYTL7da0t1B+t9cN 2OP2BTPj/mn0WJ98i5lQ2AgpifngvbgAQQ4Qzt2PuDpZHsMKkzBahddTQdCuV3TUBnd/ 4TNw==
MIME-Version: 1.0
X-Received: by 10.194.187.101 with SMTP id fr5mr2624313wjc.76.1389971865641; Fri, 17 Jan 2014 07:17:45 -0800 (PST)
Received: by 10.194.242.131 with HTTP; Fri, 17 Jan 2014 07:17:45 -0800 (PST)
In-Reply-To: <CABqy+soq1uvuiMRyF2FVXZoQ1gpdiO92Gj9A+Ri5FQa=5yp3-w@mail.gmail.com>
References: <CACsn0cmJX2begH0q8vOUZhP2t3CFo_2Ad71Neke4EKejoYCPRg@mail.gmail.com> <CAGZ8ZG1qF4ba3ogjHQnMwgXV+0Fj7eR44QdvuSw3GYBvNVFZBA@mail.gmail.com> <c406386b6fc67d11332141423f2f0f40.squirrel@www.trepanning.net> <CACsn0c=Eh1J81JHq=u8WsTtVK4HAJDghyisTZnM6U61jdr2KUQ@mail.gmail.com> <20140117011414.GA3413@netbook.cypherspace.org> <20140117023629.GA4435@netbook.cypherspace.org> <52D8DEC1.9060805@akr.io> <20140117124159.GA9258@netbook.cypherspace.org> <3374f0a3-9998-44e9-a052-61a4a94fe00c@email.android.com> <CABqy+soq1uvuiMRyF2FVXZoQ1gpdiO92Gj9A+Ri5FQa=5yp3-w@mail.gmail.com>
Date: Fri, 17 Jan 2014 07:17:45 -0800
Message-ID: <CACsn0cmPOzNoK4qvicQJWDmhkMcFZKAuB-krAVgZM17D2a6U3Q@mail.gmail.com>
From: Watson Ladd <watsonbladd@gmail.com>
To: Robert Ransom <rransom.8774@gmail.com>
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: quoted-printable
Cc: "cfrg@irtf.org" <cfrg@irtf.org>
Subject: Re: [Cfrg] Chopping out curves
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: Fri, 17 Jan 2014 15:18:01 -0000

On Fri, Jan 17, 2014 at 6:33 AM, Robert Ransom <rransom.8774@gmail.com> wrote:
> On 1/17/14, Alyssa Rowan <akr@akr.io> wrote:
>
>> There are arguments in favour of both the existing or a new basepoint for
>> t25519 (which is what I'll call the twisted Edwards representation of
>> Curve25519 used in Ed25519, as I'm not sure it actually has a name of its
>> own?).
>
> The curve specified as ‘T25519’ (a=121666, d=121665) in
> draft-ladd-safecurves-03 is something that Watson Ladd made up.  The
> Ed25519 signature scheme paper
> (<http://ed25519.cr.yp.to/ed25519-20110926.pdf>) specifies the a=-1
> form (a=-1, d=-121665/121666).

Actually the curve is from the 2009 Twisted Edwards paper of Lange and
Bernstein.
On reflection the a=-1, d=-121665/121666 form saves an an addition,
but the multiplication
is by a bigger number in the complete form. Anyway, I don't have
strong thoughts on the matter.
>
>> Generating a new basepoint for t25519:
>> • Elegant; we can select minimum y that satisfies SafeCurves criteria
>>   - What advantage, really, would that give in implementation?
>>   - Is it worth any perceived benefit?
>>   - Absolute rigidity would be critical to avoid potential manipulation
>> concerns

All points in [q] have random self reducible DDH problem. The only
>
> Watson Ladd actually chose a point with small Edwards-form x, not
> small Edwards-form y.
>
> There is no benefit to choosing a new basepoint, but there's also no
> benefit to using ‘T25519’ instead of the (more efficient) form
> specified for Ed25519.
>
> As you point out, using a different basepoint does prevent use of keys
> in different protocols, even when the protocols are designed to be
> safe to use with the same key material, so that's a real (and
> unnecessary) cost.

>
>> • Reverification necessary, I think.
>>   - New basepoint → new prime order → new primality tests for SafeCurve
>> script? (Damn. They're the expensive part.)
>
> ‘T25519’ is isomorphic to Curve25519, so any non-identity group
> element of odd order on T25519 generates the same group as the
> standard basepoint of Curve25519 (and has the same order).
>
>> On balance I have to say, I think I prefer keeping the basepoint Ed25519
>> already uses for t25519, but it's not a strong preference. If we do change
>> it, we do need to dot the i's and cross the t's, so to speak.
>
> I have a strong preference for throwing out T25519 and using Ed25519
> with its standard basepoint.

I'll follow that preference, but ugh, the number in front of x^2y^2 is big.
>
>
> Robert Ransom
> _______________________________________________
> Cfrg mailing list
> Cfrg@irtf.org
> http://www.irtf.org/mailman/listinfo/cfrg



-- 
"Those who would give up Essential Liberty to purchase a little
Temporary Safety deserve neither  Liberty nor Safety."
-- Benjamin Franklin