Return-Path:
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 ; 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 ;
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 ; 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"
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
List-Unsubscribe: ,
List-Archive:
List-Post:
List-Help:
List-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