Re: [Cfrg] 25519 naming

Robert Ransom <> Wed, 03 September 2014 08:26 UTC

Return-Path: <>
Received: from localhost ( []) by (Postfix) with ESMTP id 3C34B1A00F1 for <>; Wed, 3 Sep 2014 01:26:22 -0700 (PDT)
X-Virus-Scanned: amavisd-new at
X-Spam-Flag: NO
X-Spam-Score: -1.75
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 ([]) by localhost ( []) (amavisd-new, port 10024) with ESMTP id kxQujmnnN4kU for <>; Wed, 3 Sep 2014 01:26:21 -0700 (PDT)
Received: from ( [IPv6:2607:f8b0:400d:c04::22a]) (using TLSv1 with cipher ECDHE-RSA-RC4-SHA (128/128 bits)) (No client certificate requested) by (Postfix) with ESMTPS id 74D7D1A016C for <>; Wed, 3 Sep 2014 01:26:19 -0700 (PDT)
Received: by with SMTP id a108so8010898qge.1 for <>; Wed, 03 Sep 2014 01:26:18 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;; s=20120113; h=mime-version:in-reply-to:references:date:message-id:subject:from:to :cc:content-type; bh=eZs2oLOw+nqZOYznopjIdjDYOAjuzQb6qsb7dLR5vAo=; b=RfNk95kD/8VobGWkdZf8QfFPx72mE4Q0tNtNv6DhF9q3Tf3GR+adj+ZIIPTu5jcPgs QB4FTDZRcaRtJuU24DDq8X7s830MLMOgv2WpSwKUvjR8AVFSPXPH/7i4VOA2ryNhkOyS D/hZy8uJ82J4olL2NqVQJeHrI4rvGFW2iSXokyQy++RUUuJ9q1IviHUnMwLdB6PlV/+W 9hAqg0iype6nT/HFJqjzs5bacpA2nzQG6wlpAzVmbbkjIzUTBMZTFd56YxfDDcpNRu79 NGl+Ks1UEpgyOI8gb8SkfII2Uz8VwhlYQXcTwpID+3B3c3W5gTPwJptGnHCoxmy0KDz9 xR/Q==
MIME-Version: 1.0
X-Received: by with SMTP id f8mr1366564qab.104.1409732778674; Wed, 03 Sep 2014 01:26:18 -0700 (PDT)
Received: by with HTTP; Wed, 3 Sep 2014 01:26:18 -0700 (PDT)
In-Reply-To: <>
References: <> <> <> <>
Date: Wed, 03 Sep 2014 01:26:18 -0700
Message-ID: <>
From: Robert Ransom <>
To: Andrey Jivsov <>
Content-Type: text/plain; charset="UTF-8"
Subject: Re: [Cfrg] 25519 naming
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: Wed, 03 Sep 2014 08:26:22 -0000

On 9/2/14, Andrey Jivsov <> wrote:
> On 09/02/2014 01:28 AM, Robert Ransom wrote:
>> On 9/2/14, Andrey Jivsov <> wrote:
>>> X25519 performs 9 F(p) multiplications and squares per each bit of a
>>> scalar, for the total of 2295 F(p) operations, not counting additions.
>>> Plus there are also 265 operation for an inversion.
>>> According to the above, conversion from -1-twisted Edwards coordinates
>>> to
>>> X25519 unfortunately involves a F(p) inversion.
>>>      265/2560 ~= 10%
>>> The problem with fixing canonical coordinates seems to be the 10% penalty
>>> in
>>> conversion from Edwards coordinates to Montgomery due to F(p) inversion.
>>> I
>>> wonder if it is possible to not perform the inversion by starting with
>>> z!=1
>>> in the Montgomery formula?
>> That would cost an extra 1M per scalar bit.  1I to rescale the input
>> point is *always* faster.
> Doesn't an inverse require at least 1M (multiply or square) per scalar
> bit as well? Or, are you saying that because more of these Ms in the
> inverse are squares, this provides a small benefit?

An unoptimized inversion by exponentiation would cost up to 1M+1S per
bit of the coordinate-field order.  However:

* All coordinate fields that are currently under serious consideration
allow a structured addition chain for inversion which reduces the
number of multiplications significantly (for Curve25519, 11M+254S).
Since 1S is typically about 0.67M, that's much less than 1M per scalar
bit, even if you don't count the three least significant bits as part
of the scalar.

* All implementations must perform an inversion in order to scale
their output points anyway, so if someone decides to use a random
coordinate field, they will use the Euclidean algorithm to compute
inverses at an even lower cost than that.

>>> This would give us fixed-base optimization and dual key use that comes
>>> with
>>> Edwards formula and the speed of Montgomery for variable-base ECDH.
>> A Montgomery-form x coordinate (or its reciprocal) provides that.
>> That's why I've been arguing for a point format based on the
>> Montgomery-form x coordinate for so long, even though no one seems to
>> be listening.
> I am interested, especially in a detailed write up.

I just posted a link to one in another thread:

Robert Ransom