Re: [Cfrg] 25519 naming

Andrey Jivsov <crypto@brainhub.org> Tue, 02 September 2014 08:18 UTC

Return-Path: <crypto@brainhub.org>
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 C5C0F1A0114 for <cfrg@ietfa.amsl.com>; Tue, 2 Sep 2014 01:18:59 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -1.901
X-Spam-Level:
X-Spam-Status: No, score=-1.901 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, SPF_PASS=-0.001] autolearn=ham
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 KVwuDH5QChlE for <cfrg@ietfa.amsl.com>; Tue, 2 Sep 2014 01:18:57 -0700 (PDT)
Received: from qmta09.emeryville.ca.mail.comcast.net (qmta09.emeryville.ca.mail.comcast.net [IPv6:2001:558:fe2d:43:76:96:30:96]) by ietfa.amsl.com (Postfix) with ESMTP id 3B2781A0113 for <cfrg@irtf.org>; Tue, 2 Sep 2014 01:18:53 -0700 (PDT)
Received: from omta06.emeryville.ca.mail.comcast.net ([76.96.30.51]) by qmta09.emeryville.ca.mail.comcast.net with comcast id m8Jp1o00216AWCUA98Jsz3; Tue, 02 Sep 2014 08:18:52 +0000
Received: from [192.168.1.2] ([71.202.164.227]) by omta06.emeryville.ca.mail.comcast.net with comcast id m8Jr1o00E4uhcbK8S8Jrbm; Tue, 02 Sep 2014 08:18:52 +0000
Message-ID: <54057D6B.9090405@brainhub.org>
Date: Tue, 02 Sep 2014 01:18:51 -0700
From: Andrey Jivsov <crypto@brainhub.org>
User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:24.0) Gecko/20100101 Thunderbird/24.7.0
MIME-Version: 1.0
To: "cfrg@irtf.org" <cfrg@irtf.org>
References: <20140825234305.7799.qmail@cr.yp.to>
In-Reply-To: <20140825234305.7799.qmail@cr.yp.to>
Content-Type: text/plain; charset=ISO-8859-1; format=flowed
Content-Transfer-Encoding: 7bit
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=comcast.net; s=q20140121; t=1409645932; bh=iz5LG5SKWxYi/Z+YYAXqvBvAH9DbexGZTu9ocDrh+84=; h=Received:Received:Message-ID:Date:From:MIME-Version:To:Subject: Content-Type; b=dDd/nhi6fbky3mKj3QLj1Kcir89H2fqTZ615/TiceW7zJHayHW8KpVLkqqBuQlNDY T9yMbGJ6RjPTfxTxdhzCQ6BUEiz01MuMdPqRecJvrFB38DmOCqDdFUFIpO3EllLrAc rki+HPsAM7w4Ynllf4K9ECgPgwlP/iMZhRLPYqx+ZXE5qt+bX2uki8m0KX5BN1VJRI M3GqLTIJO7OlxbERk7/4ys/OaZbpZTEi3c2HDd6xcOYVHrlwaxVGg7gRsH3T66AVWA VYZgAVt4acxlUKK+6rSnpF/FaF129OpUn+d8glfRZsze6a9T9zR4xGBeegOMQkhqoM UrGHj4cDmTSdg==
Archived-At: http://mailarchive.ietf.org/arch/msg/cfrg/Cq0qICIsXRBOJLq8ltBFe97GQSE
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: Tue, 02 Sep 2014 08:19:00 -0000

On 08/25/2014 04:43 PM, D. J. Bernstein wrote:
> It has become increasingly common for "Curve25519" to refer to an
> elliptic curve, while the original paper defined "Curve25519" as an
> X-coordinate DH system using that curve. "Ed25519" unambiguously refers
> to an Edwards-coordinate signature system using that curve.
>
> Kenny and others in Toronto recommended changing terminology to clearly
> separate these three items. Let me suggest the following terminology:
>
>     * "X25519" is the recommended Montgomery-X-coordinate DH function.
>     * "Ed25519" is the recommended Edwards-coordinate signature system.
>     * "Curve25519" is the underlying elliptic curve.
>
> All relevant coordinate systems already have standard names in the
> literature, and I would suggest sticking to those names whenever it's
> necessary to discuss the coordinate systems per se:
>
>     * "Montgomery coordinates" (X,Y) satisfy Y^2 = X^3 + AX^2 + X mod
>       2^255-19, where A = 486662.
>
>     * "Short Weierstrass coordinates" (x,y) satisfy y^2 = x^3 + ax + b
>       where a = 1-A^2/3 and b = 2A^3/27-A/3. An easy transformation to
>       Montgomery coordinates is Y = y and X = x-A/3. The inverse
>       transformation is y = Y and x = X+A/3. Verification script in gp:
>
>          a = 1-A^2/3;
>          b = 2*A^3/27-A/3;
>          montgomery = Y^2-(X^3+A*X^2+X);
>          weierstrass = y^2-(x^3+a*x+b);
>          subst(subst(montgomery,Y,y),X,x-A/3) == weierstrass
>          subst(subst(weierstrass,y,Y),x,X+A/3) == montgomery
>
>     * "Untwisted Edwards coordinates" (x,y) satisfy x^2 + y^2 = 1 +
>       dx^2y^2 where d = (A-2)/(A+2). An easy transformation to Montgomery
>       coordinates is X = (1+y)/(1-y) and Y = sqrt(A+2) X/x. The inverse
>       transformation is x = sqrt(A+2) X/Y and y = (X-1)/(X+1).
>       Verification script:
>
>          A = s^2-2;
>          d = (A-2)/(A+2);
>          edwards = x^2+y^2-(1+d*x^2*y^2);
>          montgomery = Y^2-(X^3+A*X^2+X);
>          subst(subst(montgomery/Y^2,Y,s*X/x),X,(1+y)/(1-y)) == edwards/(y^2-1)
>          subst(subst(edwards/(y^2-1),x,s*X/Y),y,(X-1)/(X+1)) == montgomery/Y^2
>
>     * "-1-twisted Edwards coordinates" (X,Y) satisfy -X^2 + Y^2 = 1 -
>       dX^2Y^2, again with d = (A-2)/(A+2). An easy transformation to
>       untwisted Edwards coordinates is y = Y and x = sqrt(-1) X. The
>       inverse transformation is Y = y and X = -sqrt(-1) x.
>
> X25519 uses the Montgomery X coordinate. Ed25519 uses the -1-twisted
> Edwards X and Y coordinates, with X compressed. It's of course possible
> to instead use short Weierstrass x and y coordinates for everything (as
> required by, e.g., the ANSI and NIST ECDSA standards), but better tuning
> of the coordinate choices produces a measurable gain in speed and a
> larger gain in simplicity.
>
> ---Dan

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?

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.