[Cfrg] 25519 naming

"D. J. Bernstein" <djb@cr.yp.to> Tue, 26 August 2014 21:29 UTC

Return-Path: <djb-dsn2-1406711340.7506@cr.yp.to>
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 C1F801A87B3 for <cfrg@ietfa.amsl.com>; Tue, 26 Aug 2014 14:29:58 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: 1.301
X-Spam-Level: *
X-Spam-Status: No, score=1.301 tagged_above=-999 required=5 tests=[BAYES_80=2, RCVD_IN_DNSWL_LOW=-0.7, UNPARSEABLE_RELAY=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 quySJaX_hYKf for <cfrg@ietfa.amsl.com>; Tue, 26 Aug 2014 14:29:57 -0700 (PDT)
Received: from mace.cs.uic.edu (mace.cs.uic.edu [131.193.32.224]) by ietfa.amsl.com (Postfix) with SMTP id E6A681A8842 for <cfrg@irtf.org>; Tue, 26 Aug 2014 14:29:55 -0700 (PDT)
Received: (qmail 3160 invoked by uid 1011); 25 Aug 2014 23:43:11 -0000
Received: from unknown (unknown) by unknown with QMTP; 25 Aug 2014 23:43:11 -0000
Received: (qmail 7801 invoked by uid 1001); 25 Aug 2014 23:43:05 -0000
Date: 25 Aug 2014 23:43:05 -0000
Message-ID: <20140825234305.7799.qmail@cr.yp.to>
From: "D. J. Bernstein" <djb@cr.yp.to>
To: cfrg@irtf.org
Mail-Followup-To: cfrg@irtf.org
Archived-At: http://mailarchive.ietf.org/arch/msg/cfrg/-9LEdnzVrE5RORux3Oo_oDDRksU
Subject: [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, 26 Aug 2014 21:29:58 -0000

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