Re: [Cfrg] Safecurves draft

Robert Ransom <rransom.8774@gmail.com> Thu, 09 January 2014 14:34 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 C97D71AE2E3 for <cfrg@ietfa.amsl.com>; Thu, 9 Jan 2014 06:34:30 -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 73HtVHypg3j1 for <cfrg@ietfa.amsl.com>; Thu, 9 Jan 2014 06:34:29 -0800 (PST)
Received: from mail-qa0-x232.google.com (mail-qa0-x232.google.com [IPv6:2607:f8b0:400d:c00::232]) by ietfa.amsl.com (Postfix) with ESMTP id E23E41AE30F for <cfrg@irtf.org>; Thu, 9 Jan 2014 06:34:22 -0800 (PST)
Received: by mail-qa0-f50.google.com with SMTP id cm18so1660140qab.9 for <cfrg@irtf.org>; Thu, 09 Jan 2014 06:34:13 -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=5NRHS7UKfMiuqctPmm4DCanAsE1GFnHOsA2qu0PbF9M=; b=xx7nwyk7CFZjm+cwUB1v/KecEaxoUJZd31nFgTDGNgL3CuYusfNCy+8TDcL2NZ2gwc 1XONKy0C6nwUkaXcERE9TXKztVsRwMTebDsXT/WPLP6f0wQ3No8pwM+GZO6pTBChS40s ne4gp1a+2CuvVbFRgUbwxjmwiIQ3VYGBejULrCyxfMS0k5nqiAhIL+CmSunEbxRY1GJJ EjnnmHvpBv+Khd6bggyiisv1yifbqG5z+lTv1Me2bTX0c6JACTN0GoGhjNvhECZmbrR5 NSxrrTGjfsoN5m3P/sN3ma9jdu8rwjgl+IQoy29Ol2LanVKUGvQg+0ywQ0I0iMO9Cl5D OZDA==
MIME-Version: 1.0
X-Received: by 10.49.36.161 with SMTP id r1mr8359584qej.4.1389278053266; Thu, 09 Jan 2014 06:34:13 -0800 (PST)
Received: by 10.229.181.132 with HTTP; Thu, 9 Jan 2014 06:34:13 -0800 (PST)
In-Reply-To: <CADMpkcJFk2C5DPQX9RVWphUH25atsUX2vPA7RwNf8zbmR6dXJQ@mail.gmail.com>
References: <20140109031144.6111382.52184.8264@certicom.com> <20140109094731.GA12327@netbook.cypherspace.org> <CADMpkc+giuSZgrYmusRJmj5SyN9Dcu_Mdaqx5KQPyXGMmosFUw@mail.gmail.com> <CABqy+soXxjY+fEzpHP+_yn9Y1Xtapm_9OWbgDcA_J_Lukz_YLw@mail.gmail.com> <CADMpkcJFk2C5DPQX9RVWphUH25atsUX2vPA7RwNf8zbmR6dXJQ@mail.gmail.com>
Date: Thu, 9 Jan 2014 06:34:13 -0800
Message-ID: <CABqy+soX0xVWG0+vJs-_7O1Ur_hkDW0u0acCGZYrrtEci5QRXw@mail.gmail.com>
From: Robert Ransom <rransom.8774@gmail.com>
To: Bodo Moeller <bmoeller@acm.org>
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: quoted-printable
Cc: "cfrg@irtf.org" <cfrg@irtf.org>
Subject: Re: [Cfrg] Safecurves draft
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: Thu, 09 Jan 2014 14:34:31 -0000

On 1/9/14, Bodo Moeller <bmoeller@acm.org> wrote:
> Robert Ransom <rransom.8774@gmail.com>om>:
>
>> On 1/9/14, Bodo Moeller <bmoeller@acm.org> wrote:
>> > In that context, given that the name
>> > "Curve25519" is already overloaded, and that we probably should make
>> > the
>> > Edwards representation available for DH too (in addition to EdDSA),
>>
>> No.  Montgomery-form variable-base single-scalar multiplication takes
>> 5M+4S per scalar bit; Edwards-form doublings alone (in ‘extended
>> coordinates with a=-1’) are 4M+4S (or 3M+4S if the output will only be
>> used as input to another doubling).
>
>
> As pointed out by Section 6 in http://eprint.iacr.org/2007/286.pdf,
> sliding-window multiplication using the Edwards form can be faster than
> 5M+4S per scalar bit for this curve (although that's probably no longer
> true if you want a constant-time implementation -- while the non-sliding
> window approach in Section 8 doesn't seem optimal because it's not making
> use of signed windows, I don't think the extra savings are sufficient to
> beat the Montgomery ladder).  More importantly, if you have a *fixed* base
> (which is very relevant for ephemeral ECDH), with appropriate fixed
> precomputation you won't need any double operations at all: so the total
> time for one fixed-base single-scalar multiplication and one variable-base
> signal-scalar multiplication as used in ECDH can be less than with the
> Montgomery ladder, even if you want constant time with no secret-dependent
> branches.  If you have severe space constraints, then an approach that
> involves a few hundred precomputed points is not for you, but in many
> typical scenarios this is not an issue at all.
>
> So while the Montgomery-form Curve25519 certainly has its use, allowing
> applications to negotiate a different form for ECDH would be beneficial.

Even if the party which generates a public key uses Edwards-form
points internally for that operation, whoever generates the key can
put it into Montgomery form for free before scaling, whereas whoever
receives it would need to perform an extra coordinate inversion in
order to convert from Edwards form to affine Montgomery form.  (Over
an implementation-friendly coordinate field, projective-base
Montgomery-form point multiplication is always slower than scaling
followed by affine-base Montgomery-form point multiplication.)

I really don't see any benefit to transmitting an Edwards-form point for ECDH.


Robert Ransom