Re: [Cfrg] 25519 naming

Robert Ransom <rransom.8774@gmail.com> Wed, 03 September 2014 08:26 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 3C34B1A00F1 for <cfrg@ietfa.amsl.com>; Wed, 3 Sep 2014 01:26:22 -0700 (PDT)
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 kxQujmnnN4kU for <cfrg@ietfa.amsl.com>; Wed, 3 Sep 2014 01:26:21 -0700 (PDT)
Received: from mail-qg0-x22a.google.com (mail-qg0-x22a.google.com [IPv6:2607:f8b0:400d:c04::22a]) (using TLSv1 with cipher ECDHE-RSA-RC4-SHA (128/128 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id 74D7D1A016C for <cfrg@irtf.org>; Wed, 3 Sep 2014 01:26:19 -0700 (PDT)
Received: by mail-qg0-f42.google.com with SMTP id a108so8010898qge.1 for <cfrg@irtf.org>; Wed, 03 Sep 2014 01:26:18 -0700 (PDT)
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; 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 10.224.20.136 with SMTP id f8mr1366564qab.104.1409732778674; Wed, 03 Sep 2014 01:26:18 -0700 (PDT)
Received: by 10.140.51.233 with HTTP; Wed, 3 Sep 2014 01:26:18 -0700 (PDT)
In-Reply-To: <540606F8.9070504@brainhub.org>
References: <20140825234305.7799.qmail@cr.yp.to> <54057D6B.9090405@brainhub.org> <CABqy+sraBmpngJu-qkDE0MbS4j8jhQ_qfTO8kaVCwMjq+-1kZg@mail.gmail.com> <540606F8.9070504@brainhub.org>
Date: Wed, 3 Sep 2014 01:26:18 -0700
Message-ID: <CABqy+sq9ODbyiYyT1FkFDnqNzzetxKLU5B9KsTtMw1=-APZX_w@mail.gmail.com>
From: Robert Ransom <rransom.8774@gmail.com>
To: Andrey Jivsov <crypto@brainhub.org>
Content-Type: text/plain; charset=UTF-8
Archived-At: http://mailarchive.ietf.org/arch/msg/cfrg/Pb7U7VHEovM4UWdH-8IUSfTgYh4
Cc: cfrg@irtf.org
Subject: Re: [Cfrg] 25519 naming
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: Wed, 03 Sep 2014 08:26:22 -0000

On 9/2/14, Andrey Jivsov <crypto@brainhub.org>; wrote:
> On 09/02/2014 01:28 AM, Robert Ransom wrote:
>> On 9/2/14, Andrey Jivsov <crypto@brainhub.org>; 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:
<http://www.ietf.org/mail-archive/web/cfrg/current/msg04800.html>


Robert Ransom