Re: [Cfrg] Safecurves draft

Bodo Moeller <> Thu, 09 January 2014 14:25 UTC

Return-Path: <>
Received: from localhost ( []) by (Postfix) with ESMTP id B13591AE339 for <>; Thu, 9 Jan 2014 06:25:34 -0800 (PST)
X-Virus-Scanned: amavisd-new at
X-Spam-Flag: NO
X-Spam-Score: -1.467
X-Spam-Status: No, score=-1.467 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, FM_FORGED_GMAIL=0.622, HELO_EQ_DE=0.35, HTML_MESSAGE=0.001, RCVD_IN_DNSWL_NONE=-0.0001, RP_MATCHES_RCVD=-0.538, SPF_HELO_PASS=-0.001, SPF_PASS=-0.001] autolearn=no
Received: from ([]) by localhost ( []) (amavisd-new, port 10024) with ESMTP id 0ZUfi7I3sycK for <>; Thu, 9 Jan 2014 06:25:33 -0800 (PST)
Received: from ( []) by (Postfix) with ESMTP id 2690B1AE325 for <>; Thu, 9 Jan 2014 06:25:33 -0800 (PST)
Received: from ( []) by (node=mrbap4) with ESMTP (Nemesis) id 0MY6Rk-1Vwsok0oNM-00UuhQ; Thu, 09 Jan 2014 15:25:22 +0100
Received: by with SMTP id gq1so3296856obb.4 for <>; Thu, 09 Jan 2014 06:25:19 -0800 (PST)
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;; s=20130820; h=mime-version:in-reply-to:references:date:message-id:subject:from:to :cc:content-type; bh=R11fZ8AD5uvaJXcKrsBRfLE5RsaSZK+QDdPovNVjePQ=; b=CTbolz93VUVhBMHDDlNYPx+4zWafqB7Eh+ScU1NRI8VUtwpxjKPGg+XDe/EbikE44f LrIMvEBhsZVKp2UyMRpDkZyGGtpChQ0/Actv0YNOOupcQRAgPdMeXOLlExiuyMBBldG9 CbKDlLSdTY3WuFHqEs8DWi7npcaMtTm/9w2YLhrs3F4XHfVedqpcN5BRtXFS85+R+gST z+eSpgx9K+G64ajOOimCikFNX7Rlv5AjGBFHWkiZWKtNEySsvXOhtBFL2Unr4GwdYq0g 48o0u1tdIg/AmeWYo6DCLHOLuKxOOf3/qzKOwZHQuKP/g4nocXotX49gPgqs6OAkKk2A 5kmA==
MIME-Version: 1.0
X-Received: by with SMTP id g4mr2401138obt.47.1389277519740; Thu, 09 Jan 2014 06:25:19 -0800 (PST)
Received: by with HTTP; Thu, 9 Jan 2014 06:25:19 -0800 (PST)
In-Reply-To: <>
References: <> <> <> <>
Date: Thu, 09 Jan 2014 15:25:19 +0100
Message-ID: <>
From: Bodo Moeller <>
To: Robert Ransom <>
Content-Type: multipart/alternative; boundary="089e0160c35e0f0a9204ef8a6109"
X-Provags-ID: V02:K0:2eZXn3Nu9vSIpxYlPMJux3D+iril94ufzmHLBnPby94 vwKHToh2JJM8dUK+S5KRKmjkce9Maxx0fNLvXlBExIbjYO4sAF VRoc0ZQQeRoEk29o7RbuM3Z6Vqw2g7pS+BJWsz2hzHBPHVwet9 0TlXfDnPl4vrfDAHcmsJaFceDxsRBpNRYXq7JZ8Al9W9meBtTI Ali2N1TjHEYi1koJ0iCQ4J9Uo39u5KrICBw7NTNeRcYTCR8iNx owz5JjC60iuLB0XIkcjdctk8JEh2ZyWC6TYLMoTuYLo8HkGBqH lSu2Y94H7JO63Dg2LPDjV0I846pLQDpHOBtpAuf2Tae4EuRSO4 7eR1fhky1KcctN0naQ2AVOzxWS+VIZFr6bGG8QfQcTNOUE7a0Z 6Z8N5oqx9Q73YbczLO2offhZzoS12zROHrDPZygEFVubtE25go xDIUc
Cc: "" <>
Subject: Re: [Cfrg] Safecurves draft
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: Thu, 09 Jan 2014 14:25:34 -0000

Robert Ransom <>:

> On 1/9/14, Bodo Moeller <> 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,
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.