Re: [Cfrg] Fwd: Re: Safecurves draft

Manuel Pégourié-Gonnard <> Thu, 09 January 2014 10:22 UTC

Return-Path: <>
Received: from localhost ( []) by (Postfix) with ESMTP id 5FA731AE236 for <>; Thu, 9 Jan 2014 02:22:01 -0800 (PST)
X-Virus-Scanned: amavisd-new at
X-Spam-Flag: NO
X-Spam-Score: 0.994
X-Spam-Status: No, score=0.994 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, FH_RELAY_NODNS=1.451, HELO_EQ_FR=0.35, MIME_8BIT_HEADER=0.3, RDNS_NONE=0.793] autolearn=no
Received: from ([]) by localhost ( []) (amavisd-new, port 10024) with ESMTP id jKyTVlNtRb9F for <>; Thu, 9 Jan 2014 02:22:00 -0800 (PST)
Received: from (unknown [IPv6:2001:4b98:dc0:41:216:3eff:feeb:c406]) by (Postfix) with ESMTP id 5DF251AE234 for <>; Thu, 9 Jan 2014 02:22:00 -0800 (PST)
Received: from ( []) by (Postfix) with ESMTPS id 97604161DF for <>; Thu, 9 Jan 2014 11:21:49 +0100 (CET)
Received: from [] (unknown []) by (Postfix) with ESMTPSA id AFB0E2988A for <>; Thu, 9 Jan 2014 11:21:48 +0100 (CET)
Message-ID: <>
Date: Thu, 09 Jan 2014 11:21:48 +0100
From: Manuel Pégourié-Gonnard <>
User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:24.0) Gecko/20100101 Icedove/24.1.1
MIME-Version: 1.0
References: <> <> <> <>
In-Reply-To: <>
X-Enigmail-Version: 1.6
OpenPGP: id=98EED379; url=
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: 8bit
Subject: Re: [Cfrg] Fwd: Re: 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 10:22:01 -0000

On 09/01/2014 10:50, Robert Ransom wrote:
>> About names, I'd really like the names to reflect the type of the curve
>> (Montgomery or Edwards). This is already the case for other curve families,
>> by
>> the way. So, Mxxx and Exxx seem great to me. I'd even go so far as to rename
>> Curve25519 as M255, but I'm sure there are good reasons to disagree on this
>> point.
> Remember that Curve25519's parameter is *not* minimal subject to the
> constraint of twist security with minimal cofactors -- Dr. Bernstein
> considered a slightly more subtle criterion regarding the group orders
> too.  Keep that in mind if you try to establish a systematic name for
> Curve25519.
I'm not sure it goes against my argument that the name should reflect the type
of the curve. Or did I miss something?

> I don't see the benefit of defining both a ‘safe’ Montgomery curve
> (for the present definition of “safe”) and a ‘safe’ Edwards curve over
> the same coordinate field -- every Edwards curve with minimal
> parameter can be used efficiently with Montgomery's formulas.  (The
> Montgomery-form parameter becomes the reciprocal of a small integer,
> which can be handled as efficiently as a small integer itself.)
> (For that matter, I would suggest replacing Curve25519 with the
> twisted Edwards curve a=-1, d=121665 over the same field in any new
> application or standard.)
An interesting point.

> Issue 2 is obviated by twist security for single-scalar multiplication
> of a Montgomery-form x coordinate.  It remains relevant for any
> application which operates on full points (whether transmitted
> uncompressed or compressed).
Absolutely. There was a hidden assumption that only the x coordinate be used in
my statement. Actually, I think it reinforces my point that the curves aren't
"magically" safe regardless of the how they are implemented or used in a
protocol: indeed, the fact that no public key validation is needed depends not
only on the curve (twist security), but also on the protocol (x coordinate only).

>> and to be fair point 4 is a bit easier to
>> address
>> with these curves too.
> Why 4?  The benefit of complete addition formulas is that
> implementations don't need to switch to a doubling routine when two
> points are equal.  Nothing about SafeCurves makes constant-time table
> lookups any easier.
Right, I was making an unstated assumption again, sorry for that. The assumption
was that other curves are more likely to use a larger table for performance,
while a Curve25519 implementation will generally use a ladder with no
precomputed table, so it will only have to safely swap two points, which is less
expensive than doing a constant-time lookup in a larger (say 16 or 32 points)
table. So it lessens the performance vs security conflict.