idnits 2.17.1 draft-struik-lwig-curve-representations-02.txt: Checking boilerplate required by RFC 5378 and the IETF Trust (see https://trustee.ietf.org/license-info): ---------------------------------------------------------------------------- No issues found here. Checking nits according to https://www.ietf.org/id-info/1id-guidelines.txt: ---------------------------------------------------------------------------- No issues found here. Checking nits according to https://www.ietf.org/id-info/checklist : ---------------------------------------------------------------------------- ** The document seems to lack an Introduction section. Miscellaneous warnings: ---------------------------------------------------------------------------- == The copyright year in the IETF Trust and authors Copyright Line does not match the current year == The document doesn't use any RFC 2119 keywords, yet seems to have RFC 2119 boilerplate text. -- The document date (July 19, 2018) is 2106 days in the past. Is this intentional? Checking references for intended status: Informational ---------------------------------------------------------------------------- == Missing Reference: 'TBD' is mentioned on line 768, but not defined Summary: 1 error (**), 0 flaws (~~), 3 warnings (==), 1 comment (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 2 lwig R. Struik 3 Internet-Draft Struik Security Consultancy 4 Intended status: Informational July 19, 2018 5 Expires: January 20, 2019 7 Alternative Elliptic Curve Representations 8 draft-struik-lwig-curve-representations-02 10 Abstract 12 This document specifies how to represent Montgomery curves and 13 (twisted) Edwards curves as curves in short-Weierstrass form and 14 illustrates how this can be used to implement elliptic curve 15 computations using existing implementations that already implement, 16 e.g., ECDSA and ECDH using NIST prime curves. 18 Requirements Language 20 The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", 21 "SHOULD", "SHOULD NOT", "RECOMMENDED", "NOT RECOMMENDED", "MAY", and 22 "OPTIONAL" in this document are to be interpreted as described in RFC 23 2119 [RFC2119]. 25 Status of This Memo 27 This Internet-Draft is submitted in full conformance with the 28 provisions of BCP 78 and BCP 79. 30 Internet-Drafts are working documents of the Internet Engineering 31 Task Force (IETF). Note that other groups may also distribute 32 working documents as Internet-Drafts. The list of current Internet- 33 Drafts is at https://datatracker.ietf.org/drafts/current/. 35 Internet-Drafts are draft documents valid for a maximum of six months 36 and may be updated, replaced, or obsoleted by other documents at any 37 time. It is inappropriate to use Internet-Drafts as reference 38 material or to cite them other than as "work in progress." 40 This Internet-Draft will expire on January 20, 2019. 42 Copyright Notice 44 Copyright (c) 2018 IETF Trust and the persons identified as the 45 document authors. All rights reserved. 47 This document is subject to BCP 78 and the IETF Trust's Legal 48 Provisions Relating to IETF Documents 49 (https://trustee.ietf.org/license-info) in effect on the date of 50 publication of this document. Please review these documents 51 carefully, as they describe your rights and restrictions with respect 52 to this document. Code Components extracted from this document must 53 include Simplified BSD License text as described in Section 4.e of 54 the Trust Legal Provisions and are provided without warranty as 55 described in the Simplified BSD License. 57 Table of Contents 59 1. Fostering Code Reuse with New Elliptic Curves . . . . . . . . 3 60 2. Specification of Wei25519 . . . . . . . . . . . . . . . . . . 3 61 3. Example Uses . . . . . . . . . . . . . . . . . . . . . . . . 3 62 3.1. ECDSA-SHA256-25519 . . . . . . . . . . . . . . . . . . . 3 63 3.2. Other Uses . . . . . . . . . . . . . . . . . . . . . . . 4 64 4. Security Considerations . . . . . . . . . . . . . . . . . . . 4 65 5. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 4 66 6. Normative References . . . . . . . . . . . . . . . . . . . . 4 67 Appendix A. Some (non-Binary) Elliptic Curves . . . . . . . . . 6 68 A.1. Curves in short-Weierstrass Form . . . . . . . . . . . . 6 69 A.2. Montgomery Curves . . . . . . . . . . . . . . . . . . . . 6 70 A.3. Twisted Edwards Curves . . . . . . . . . . . . . . . . . 6 71 Appendix B. Elliptic Curve Group Operations . . . . . . . . . . 7 72 B.1. Group Law for Weierstrass Curves . . . . . . . . . . . . 7 73 B.2. Group Law for Montgomery Curves . . . . . . . . . . . . . 7 74 B.3. Group Law for Twisted Edwards Curves . . . . . . . . . . 8 75 Appendix C. Relationship Between Curve Models . . . . . . . . . 8 76 C.1. Mapping between twisted Edwards Curves and Montgomery 77 Curves . . . . . . . . . . . . . . . . . . . . . . . . . 8 78 C.2. Mapping between Montgomery Curves and Weierstrass Curves 9 79 C.3. Mapping between twisted Edwards Curves and Weierstrass 80 Curves . . . . . . . . . . . . . . . . . . . . . . . . . 10 81 Appendix D. Curve25519 and Cousins . . . . . . . . . . . . . . . 10 82 D.1. Curve Definition and Alternative Representations . . . . 10 83 D.2. Switching between Alternative Representations . . . . . . 10 84 D.3. Domain Parameters . . . . . . . . . . . . . . . . . . . . 12 85 Appendix E. Further Mappings . . . . . . . . . . . . . . . . . . 14 86 E.1. Isomorphic Mapping between Weierstrass Curves . . . . . . 14 87 E.2. Isogeneous Mapping between Weierstrass Curves . . . . . . 15 88 Appendix F. Further Cousins of Curve25519 . . . . . . . . . . . 15 89 F.1. Further Alternative Representations . . . . . . . . . . . 15 90 F.2. Further Switching . . . . . . . . . . . . . . . . . . . . 15 91 F.3. Further Domain Parameters . . . . . . . . . . . . . . . . 16 92 Author's Address . . . . . . . . . . . . . . . . . . . . . . . . 17 94 1. Fostering Code Reuse with New Elliptic Curves 96 It is well-known that elliptic curves can be represented using 97 different curve models. Recently, IETF standardized elliptic curves 98 that are claimed to have better performance and improved robustness 99 against "real world" attacks than curves represented in the 100 traditional "short" Weierstrass model. This draft specifies an 101 alternative representation of points of Curve25519, a so-called 102 Montgomery curve, and of points of Edwards25519, a so-called twisted 103 Edwards curve, which are both specified in [RFC7748], as points of a 104 specific so-called "short" Weierstrass curve, called Wei25519. The 105 draft also defines how to efficiently switch between these different 106 representations. 108 Use of Wei25519 allows easy definition of signature schemes and key 109 agreement schemes already specified for traditional NIST prime 110 curves, thereby allowing easy integration with existing 111 specifications, such as NIST SP 800-56a [SP-800-56a], FIPS Pub 186-4 112 [FIPS-186-4], and ANSI X9.62-2005 [ANSI-X9.62] and fostering code 113 reuse on platforms that already implement some of these schemes using 114 elliptic curve arithmetic for curves in "short" Weierstrass form (see 115 Appendix B.1). 117 2. Specification of Wei25519 119 For the specification of Wei25519 and its relationship to Curve25519 120 and Edwards25519, see Appendix D. For further details and background 121 information on elliptic curves, we refer to the other appendices. 123 The use of Wei25519 allows reuse of existing generic code that 124 implements short-Weierstrass curves, such as the NIST curve P256, to 125 also implement the CFRG curves Curve25519 and Ed25519. The draft 126 also caters to reuse of existing code where some domain parameters 127 may have been hardcoded, thereby widening the scope of applicability; 128 see Appendix F. 130 3. Example Uses 132 3.1. ECDSA-SHA256-25519 134 RFC 8032 [RFC8032] specifies the use of EdDSA, a "full" Schnorr 135 signature scheme, with instantiation by Edwards25519 and Ed448, two 136 so-called twisted Edwards curves. These curves can also be used with 137 the widely implemented signature scheme ECDSA [FIPS-186-4], by 138 instantiating ECDSA with the curve Wei25519 and hash function SHA- 139 256, where "under the hood" an implementation may carry out elliptic 140 curve scalar multiplication routines using the corresponding 141 representations of a point of the curve Wei25519 in Weierstrass form 142 as a point of the Montgomery curve Curve25519 or of the twisted 143 Edwards curve Edwards25519. (The corresponding ECDSA-SHA512-448 144 scheme arises if one were to specify a curve in short-Weierstrass 145 form corresponding to Ed448 and use the hash function SHA512.) Note 146 that, in either case, one can implement these schemes with the same 147 representation conventions as used with existing NIST specifications, 148 including bit/byte-ordering, compression functions, and the-like. 149 This allows implementations of ECDSA with the hash function SHA-256 150 and with the NIST curve P-256 or with the curve Wei25519 specified in 151 this draft to use the same implementation (instantiated with, 152 respectively, the NIST P-256 elliptic curve domain parameters or with 153 the domain parameters of curve Wei25519 specified in Appendix D). 155 3.2. Other Uses 157 Any existing specification of cryptographic schemes using elliptic 158 curves in Weierstrass form and that allows introduction of a new 159 elliptic curve (here: Wei25519) is amenable to similar constructs, 160 thus spawning "offspring" protocols, simply by instantiating these 161 using the new curve in "short" Weierstrass form, thereby allowing 162 code and/or specifications reuse and, for implementations that so 163 desire, carrying out curve computations "under the hood" on 164 Montgomery curve and twisted Edwards curve cousins hereof (where 165 these exist). This would simply require definition of a new object 166 identifier for any such envisioned "offspring" protocol. This could 167 significantly simplify standardization of schemes and help keeping 168 the resource and maintenance cost of implementations supporting 169 algorithm agility [RFC7696] at bay. 171 4. Security Considerations 173 The different representations of elliptic curve points discussed in 174 this draft are all obtained using a publicly known transformation. 175 Since this transformation is an isomorphism, this transformation maps 176 elliptic curve points to equivalent mathematical objects. 178 5. IANA Considerations 180 There is *currently* no IANA action required for this document. New 181 object identifiers would be required in case one wishes to specify 182 one or more of the "offspring" protocols exemplified in Section 3. 184 6. Normative References 186 [ANSI-X9.62] 187 ANSI X9.62-2005, "Public Key Cryptography for the 188 Financial Services Industry: The Elliptic Curve Digital 189 Signature Algorithm (ECDSA)", American National Standard 190 for Financial Services, Accredited Standards Committee X9, 191 Inc Anapolis, MD, 2005. 193 [FIPS-186-4] 194 FIPS 186-4, "Digital Signature Standard (DSS), Federal 195 Information Processing Standards Publication 186-4", US 196 Department of Commerce/National Institute of Standards and 197 Technology Gaithersburg, MD, July 2013. 199 [GECC] D. Hankerson, A.J. Menezes, S.A. Vanstone, "Guide to 200 Elliptic Curve Cryptography", New York: Springer-Verlag, 201 2004. 203 [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate 204 Requirement Levels", BCP 14, RFC 2119, 205 DOI 10.17487/RFC2119, March 1997, 206 . 208 [RFC5639] Lochter, M. and J. Merkle, "Elliptic Curve Cryptography 209 (ECC) Brainpool Standard Curves and Curve Generation", 210 RFC 5639, DOI 10.17487/RFC5639, March 2010, 211 . 213 [RFC7696] Housley, R., "Guidelines for Cryptographic Algorithm 214 Agility and Selecting Mandatory-to-Implement Algorithms", 215 BCP 201, RFC 7696, DOI 10.17487/RFC7696, November 2015, 216 . 218 [RFC7748] Langley, A., Hamburg, M., and S. Turner, "Elliptic Curves 219 for Security", RFC 7748, DOI 10.17487/RFC7748, January 220 2016, . 222 [RFC8032] Josefsson, S. and I. Liusvaara, "Edwards-Curve Digital 223 Signature Algorithm (EdDSA)", RFC 8032, 224 DOI 10.17487/RFC8032, January 2017, 225 . 227 [SP-800-56a] 228 NIST SP 800-56a, "Recommendation for Pair-Wise Key 229 Establishment Schemes Using Discrete Log Cryptography, 230 Revision 2", US Department of Commerce/National Institute 231 of Standards and Technology Gaithersburg, MD, June 2013. 233 Appendix A. Some (non-Binary) Elliptic Curves 235 A.1. Curves in short-Weierstrass Form 237 Let GF(q) denote the finite field with q elements, where q is an odd 238 prime power and where q is not divisible by three. Let W_{a,b} be 239 the Weierstrass curve with defining equation y^2 = x^3 + a*x + b, 240 where a and b are elements of GF(q) and where 4*a^3 + 27*b^2 is 241 nonzero. The points of W_{a,b} are the ordered pairs (x, y) whose 242 coordinates are elements of GF(q) and that satisfy the defining 243 equation (the so-called affine points), together with the special 244 point O (the so-called "point at infinity").This set forms a group 245 under addition, via the so-called "chord-and-tangent" rule, where the 246 point at infinity serves as the identity element. See Appendix B.1 247 for details of the group operation. 249 A.2. Montgomery Curves 251 Let GF(q) denote the finite field with q elements, where q is an odd 252 prime power. Let M_{A,B} be the Montgomery curve with defining 253 equation B*v^2 = u^3 + A*u^2 + u, where A and B are elements of GF(q) 254 with A unequal to (+/-)2 and with B nonzero. The points of M_{A,B} 255 are the ordered pairs (u, v) whose coordinates are elements of GF(q) 256 and that satisfy the defining equation (the so-called affine points), 257 together with the special point O (the so-called "point at 258 infinity").This set forms a group under addition, via the so-called 259 "chord-and-tangent" rule, where the point at infinity serves as the 260 identity element. See Appendix B.2 for details of the group 261 operation. 263 A.3. Twisted Edwards Curves 265 Let GF(q) denote the finite field with q elements, where q is an odd 266 prime power. Let E_{a,d} be the twisted Edwards curve with defining 267 equation a*x^2 + y^2 = 1+ d*x^2*y^2, where a and d are distinct 268 nonzero elements of GF(q). The points of E_{a,d} are the ordered 269 pairs (x, y) whose coordinates are elements of GF(q) and that satisfy 270 the defining equation (the so-called affine points). It can be shown 271 that this set forms a group under addition if a is a square in GF(q), 272 whereas d is not, where the point (0, 1) serves as the identity 273 element. (Note that the identity element satisfies the defining 274 equation.) See Appendix B.3 for details of the group operation. An 275 Edwards curve is a twisted Edwards curve with a=1. 277 Appendix B. Elliptic Curve Group Operations 279 B.1. Group Law for Weierstrass Curves 281 For each point P of the Weierstrass curve W_{a,b}, the point at 282 infinity O serves as identity element, i.e., P + O = O + P = P. 284 For each affine point P:=(x, y) of the Weierstrass curve W_{a,b}, the 285 point -P is the point (x, -y) and one has P + (-P) = O. 287 Let P1:=(x1, y1) and P2:=(x2, y2) be distinct affine points of the 288 Weierstrass curve W_{a,b} and let Q:=P1 + P2, where Q is not the 289 identity element. Then Q:=(x, y), where 291 x + x1 + x2 = lambda^2 and y + y1 = lambda*(x1 - x), where lambda 292 = (y2 - y1)/(x2 - x1). 294 Let P:= (x1, y1) be an affine point of the Weierstrass curve W_{a,b} 295 and let Q:=2P, where Q is not the identity element. Then Q:= (x, y), 296 where 298 x + 2*x1 = lambda^2 and y + y1 = lambda*(x1 - x), where 299 lambda=(3*x1^2 + a)/(2*y1). 301 B.2. Group Law for Montgomery Curves 303 For each point P of the Montgomery curve M_{A,B}, the point at 304 infinity O serves as identity element, i.e., P + O = O + P = P. 306 For each affine point P:=(x, y) of the Montgomery curve M_{A,B}, the 307 point -P is the point (x, -y) and one has P + (-P) = O. 309 Let P1:=(x1, y1) and P2:=(x2, y2) be distinct affine points of the 310 Montgomery curve M_{A,B} and let Q:=P1 + P2, where Q is not the 311 identity element. Then Q:=(x, y), where 313 x + x1 + x2 = B*lambda^2 - A and y + y1 = lambda*(x1 - x), where 314 lambda=(y2 - y1)/(x2 - x1). 316 Let P:= (x1, y1) be an affine point of the Montgomery curve M_{A,B} 317 and let Q:=2P, where Q is not the identity element. Then Q:= (x, y), 318 where 320 x + 2*x1 = B*lambda^2 - A and y + y1 = lambda*(x1 - x), where 321 lambda=(3*x1^2 + 2*A*x1+1)/(2*y1). 323 Alternative and more efficient group laws exist, e.g., when using the 324 so-called Montgomery ladder. Details are out of scope. 326 B.3. Group Law for Twisted Edwards Curves 328 Note: The group laws below hold for twisted Edwards curves E_{a,d} 329 where a is a square in GF(q), whereas d is not. In this case, the 330 addition formulae below are defined for each pair of points, without 331 exceptions. Generalizations of this group law to other twisted 332 Edwards curves are out of scope. 334 For each point P of the twisted Edwards curve E_{a,d}, the point 335 O=(0,1) serves as identity element, i.e., P + O = O + P = P. 337 For each point P:=(x, y) of the twisted Edwards curve E_{a,d}, the 338 point -P is the point (-x, y) and one has P + (-P) = O. 340 Let P1:=(x1, y1) and P2:=(x2, y2) be points of the twisted Edwards 341 curve E_{a,d} and let Q:=P1 + P2. Then Q:=(x, y), where 343 x = (x1*y2 + x2*y1)/(1 + d*x1*x2*y1*y2) and y = (y1*y2 - 344 a*x1*x2)/(1 - d*x1*x2*y1*y2). 346 Let P:=(x1, y1) be a point of the twisted Edwards curve E_{a,d} and 347 let Q:=2P. Then Q:=(x, y), where 349 x = (2*x1*y1)/(1 + d*x1^2*y1^2) and y = (y1^2 - a*x1^2)/(1 - 350 d*x1^2*y1^2). 352 Note that one can use the formulae for point addition to implement 353 point doubling, taking inverses and adding the identity element as 354 well (i.e., the point addition formulae are uniform and complete 355 (subject to our Note above)). 357 Appendix C. Relationship Between Curve Models 359 The non-binary curves specified in Appendix A are expressed in 360 different curve models, viz. as curves in short-Weierstrass form, as 361 Montgomery curves, or as twisted Edwards curves. These curve models 362 are related, as follows. 364 C.1. Mapping between twisted Edwards Curves and Montgomery Curves 366 One can map points of the Montgomery curve M_{A,B} to points of the 367 twisted Edwards curve E_{a,d}, where a:=(A+2)/B and d:=(A-2)/B and, 368 conversely, map points of the twisted Edwards curve E_{a,d} to points 369 of the Montgomery curve M_{A,B}, where A:=2(a+d)/(a-d) and where 370 B:=4/(a-d). For twisted Edwards curves we consider (i.e., those 371 where a is a square in GF(q), whereas d is not), this defines a one- 372 to-one correspondence, which - in fact - is an isomorphism between 373 M_{A,B} and E_{a,d}, thereby showing that, e.g., the discrete 374 logarithm problem in either curve model is equally hard. 376 For the Montgomery curves and twisted Edwards curves we consider, the 377 mapping from M_{A,B} to E_{a,d} is defined by mapping the point at 378 infinity O and the point (0, 0) of order two of M_{A,B} to, 379 respectively, the point (0, 1) and the point (0, -1) of order two of 380 E_{a,d}, while mapping each other point (u, v) of M_{A,B} to the 381 point (x, y):=(u/v, (u-1)/(u+1)) of E_{a,d}. The inverse mapping from 382 E_{a,d} to M_{A,B} is defined by mapping the point (0, 1) and the 383 point (0, -1) of order two of E_{a,d} to, respectively, the point at 384 infinity O and the point (0, 0) of order two of M_{A,B}, while each 385 other point (x, y) of E_{a,d} is mapped to the point (u, 386 v):=((1+y)/(1-y), (1+y)/((1-y)*x)) of M_{A,B}. 388 Implementations may take advantage of this mapping to carry out 389 elliptic curve group operations originally defined for a twisted 390 Edwards curve on the corresponding Montgomery curve, or vice-versa, 391 and translating the result back to the original curve, thereby 392 potentially allowing code reuse. 394 C.2. Mapping between Montgomery Curves and Weierstrass Curves 396 One can map points of the Montgomery curve M_{A,B} to points of the 397 Weierstrass curve W_{a,b}, where a:=(3-A^2)/(3*B^2) and 398 b:=(2*A^3-9*A)/(27*B^3). This defines a one-to-one correspondence, 399 which - in fact - is an isomorphism between M_{A,B} and W_{a,b}, 400 thereby showing that, e.g., the discrete logarithm problem in either 401 curve model is equally hard. 403 The mapping from M_{A,B} to W_{a,b} is defined by mapping the point 404 at infinity O of M_{A,B} to the point at infinity O of W_{a,b}, while 405 mapping each other point (u, v) of M_{A,B} to the point (x, y):=(u/ 406 B+A/(3*B), v/B) of W_{a,b}. Note that not all Weierstrass curves can 407 be injectively mapped to Montgomery curves, since the latter have a 408 point of order two and the former may not. In particular, if a 409 Weierstrass curve has prime order, such as is the case with the so- 410 called "NIST curves", this inverse mapping is not defined. 412 This mapping can be used to implement elliptic curve group operations 413 originally defined for a twisted Edwards curve or for a Montgomery 414 curve using group operations on the corresponding elliptic curve in 415 short-Weierstrass form and translating the result back to the 416 original curve, thereby potentially allowing code reuse. Note that 417 implementations for elliptic curves with short-Weierstrass form that 418 hard-code the domain parameter a to a= -3 (which value is known to 419 allow more efficient implementations) cannot always be used this way, 420 since the curve W_{a,b} may not always be expressed in terms of a 421 Weierstrass curve with a=-3 via a coordinate transformation. 423 C.3. Mapping between twisted Edwards Curves and Weierstrass Curves 425 One can map points of the twisted Edwards curve E_{a,d} to points of 426 the Weierstrass curve W_{a,b}, via function composition, where one 427 uses the isomorphic mapping between twisted Edwards curve and 428 Montgomery curves of Appendix C.1 and the one between Montgomery and 429 Weierstrass curves of Appendix C.2. Obviously, one can use function 430 composition (now using the respective inverses) to realize the 431 inverse of this mapping. 433 Appendix D. Curve25519 and Cousins 435 D.1. Curve Definition and Alternative Representations 437 The elliptic curve Curve25519 is the Montgomery curve M_{A,B} defined 438 over the prime field GF(p), with p:=2^{255}-19, where A:=486662 and 439 B:=1. This curve has order h*n, where h=8 and where n is a prime 440 number. For this curve, A^2-4 is not a square in GF(p), whereas A+2 441 is. The quadratic twist of this curve has order h1*n1, where h1=4 442 and where n1 is a prime number. For this curve, the base point is 443 the point (Gu,Gv), where Gu=9 and where Gv is an odd integer in the 444 interval [0, p-1]. 446 This curve has the same group structure as (is "isomorphic" to) the 447 twisted Edwards curve E_{a,d} defined over GF(p), with as base point 448 the point (Gx,Gy), where parameters are as specified in Appendix D.3. 449 This curve is denoted as Edwards25519. For this curve, the parameter 450 a is a square in GF(p), whereas d is not, so the group laws of 451 Appendix B.3 apply. 453 The curve is also isomorphic to the elliptic curve W_{a,b} in short- 454 Weierstrass form defined over GF(p), with as base point the point 455 (Gx',Gy'), where parameters are as specified in Appendix D.3. This 456 curve is denoted as Wei25519. 458 D.2. Switching between Alternative Representations 460 Each affine point (u,v) of Curve25519 corresponds to the point 461 (x,y):=(u + A/3,y) of Wei25519, while the point at infinity of 462 Curve25519 corresponds to the point at infinity of Wei25519. (Here, 463 we used the mapping of Appendix C.2.) Under this mapping, the base 464 point (Gu,Gv) of Curve25519 corresponds to the base point (Gx',Gy') 465 of Wei25519. The inverse mapping maps the affine point (x,y) of 466 Wei25519 to (u,v):=(x - A/3,y) of Curve25519, while mapping the point 467 at infinity of Wei25519 to the point at infinity of Curve25519. Note 468 that this mapping involves a simple shift of the first coordinate and 469 can be implemented via integer-only arithmetic as a shift of (p+A)/3 470 for the isomorphic mapping and a shift of -(p+A)/3 for its inverse, 471 where delta=(p+A)/3 is the element of GF(p) defined by 473 delta 19298681539552699237261830834781317975544997444273427339909597 474 334652188435537 476 (=0x2aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaad2 477 451) 479 The curve Edwards25519 is isomorphic to the curve Curve25519, where 480 the base point (Gu,Gv) of Curve25519 corresponds to the base point 481 (Gx,Gy) of Edwards25519 and where the point at infinity and the point 482 (0,0) of order two of Curve25519 correspond to, respectively, the 483 point (0, 1) and the point (0, -1) of order two of Edwards25519 and 484 where each other point (u, v) of Curve25519 corresponds to the point 485 (c*u/v, (u-1)/(u+1)) of Edwards25519, where c is the element of GF(p) 486 defined by 488 c sqrt(-(A+2)) 490 51042569399160536130206135233146329284152202253034631822681833788 491 666877215207 493 (=0x70d9120b 9f5ff944 2d84f723 fc03b081 3a5e2c2e b482e57d 494 3391fb55 00ba81e7) 496 (Here, we used the mapping of Appendix C.1.) The inverse mapping 497 from Edwards25519 to Curve25519 is defined by mapping the point (0, 498 1) and the point (0, -1) of order two of Edwards25519 to, 499 respectively, the point at infinity and the point (0,0) of order two 500 of Curve25519 and having each other point (x, y) of Edwards25519 501 correspond to the point ((1 + y)/(1 - y), c*(1 + y)/((1-y)*x)). 503 The curve Edwards25519 is isomorphic to the Weierstrass curve 504 Wei25519, where the base point (Gx,Gy) of Edwards25519 corresponds to 505 the base point (Gx',Gy') of Wei25519 and where the identity element 506 (0,1) and the point (0,-1) of order two of Edwards25519 correspond 507 to, respectively, the point at infinity O and the point (A/3, 0) of 508 order two of Wei25519 and where each other point (x, y) of 509 Edwards25519 corresponds to the point (x', y'):=((1+y)/(1-y)+A/3, 510 c*(1+y)/((1-y)*x)) of Wei25519, where c was defined before. (Here, 511 we used the mapping of Appendix C.3.) The inverse mapping from 512 Wei25519 to Edwards25519 is defined by mapping the point at infinity 513 O and the point (A/3, 0) of order two of Wei25519 to, respectively, 514 the identity element (0,1) and the point (0,-1) of order two of 515 Edwards25519 and having each other point (x, y) of Wei25519 516 correspond to the point (c*(3*x-A)/(3*y), (3*x-A-3)/(3*x-A+3)). 518 Note that these mappings can be easily realized in projective 519 coordinates, using a few field multiplications only, thus allowing 520 switching between alternative representations with negligible 521 relative incremental cost. 523 D.3. Domain Parameters 525 The parameters of the Montgomery curve and the corresponding 526 isomorphic curves in twisted Edwards curve and short-Weierstrass form 527 are as indicated below. Here, the domain parameters of the 528 Montgomery curve Curve25519 and of the twisted Edwards curve 529 Edwards25519 are as specified in RFC 7748; the domain parameters of 530 Wei25519 are "new". 532 General parameters (for all curve models): 534 p 2^{255}-19 536 (=0x7fffffff ffffffff ffffffff ffffffff ffffffff ffffffff 537 ffffffff ffffffed) 539 h 8 541 n 72370055773322622139731865630429942408571163593799076060019509382 542 85454250989 544 (=2^{252} + 0x14def9de a2f79cd6 5812631a 5cf5d3ed) 546 h1 4 548 n1 14474011154664524427946373126085988481603263447650325797860494125 549 407373907997 551 (=2^{253} - 0x29bdf3bd 45ef39ac b024c634 b9eba7e3) 553 Montgomery curve-specific parameters (for Curve25519): 555 A 486662 557 B 1 559 Gu 9 (=0x9) 561 Gv 14781619447589544791020593568409986887264606134616475288964881837 562 755586237401 563 (=0x20ae19a1 b8a086b4 e01edd2c 7748d14c 923d4d7e 6d7c61b2 564 29e9c5a2 7eced3d9) 566 Twisted Edwards curve-specific parameters (for Edwards25519): 568 a -1 (-0x01) 570 d -121665/121666 572 (=370957059346694393431380835087545651895421138798432190163887855 573 33085940283555) 575 (=0x52036cee 2b6ffe73 8cc74079 7779e898 00700a4d 4141d8ab 576 75eb4dca 135978a3) 578 Gx 15112221349535400772501151409588531511454012693041857206046113283 579 949847762202 581 (=0x216936d3 cd6e53fe c0a4e231 fdd6dc5c 692cc760 9525a7b2 582 c9562d60 8f25d51a) 584 Gy 4/5 586 (=463168356949264781694283940034751631413079938662562256157830336 587 03165251855960) 589 (=0x66666666 66666666 66666666 66666666 66666666 66666666 590 66666666 66666658) 592 Weierstrass curve-specific parameters (for Wei25519): 594 a 19298681539552699237261830834781317975544997444273427339909597334 595 573241639236 597 (=0x2aaaaaaa aaaaaaaa aaaaaaaa aaaaaaaa aaaaaaaa aaaaaaaa 598 aaaaaa98 4914a144) 600 b 55751746669818908907645289078257140818241103727901012315294400837 601 956729358436 603 (=0x7b425ed0 97b425ed 097b425e d097b425 ed097b42 5ed097b4 604 260b5e9c 7710c864) 606 Gx' 19298681539552699237261830834781317975544997444273427339909597334 607 652188435546 609 (=0x2aaaaaaa aaaaaaaa aaaaaaaa aaaaaaaa aaaaaaaa aaaaaaaa 610 aaaaaaaa aaad245a) 612 Gy' 14781619447589544791020593568409986887264606134616475288964881837 613 755586237401 615 (=0x20ae19a1 b8a086b4 e01edd2c 7748d14c 923d4d7e 6d7c61b2 616 29e9c5a2 7eced3d9) 618 Appendix E. Further Mappings 620 The non-binary curves specified in Appendix A are expressed in 621 different curve models, viz. as curves in short-Weierstrass form, as 622 Montgomery curves, or as twisted Edwards curves. Within each curve 623 model, further mappings exist that induce a mapping between elliptic 624 curves within each curve model. This can be exploited to force some 625 of the domain parameter to a value that allows a more efficient 626 implementation of the addition formulae. 628 E.1. Isomorphic Mapping between Weierstrass Curves 630 One can map points of the Weierstrass curve W_{a,b} to points of the 631 Weierstrass curve W_{a',b'}, where a:=a'*u^4 and b:=b'*u^6 for some 632 nonzero value u of the finite field GF(q). This defines a one-to-one 633 correspondence, which - in fact - is an isomorphism between W_{a,b} 634 and W_{a',b'}, thereby showing that, e.g., the discrete logarithm 635 problem in either curve model is equally hard. 637 The mapping from W_{a,b} to W_{a',b'} is defined by mapping the point 638 at infinity O of W_{a,b} to the point at infinity O of W_{a',b'}, 639 while mapping each other point (x, y) of W_{a,b} to the point (x', 640 y'):=(x*u^2, y*u^3) of W_{a',b'}. The inverse mapping from W_{a',b'} 641 to W_{a,b} is defined by mapping the point at infinity O of W_{a',b'} 642 to the point at infinity O of W_{a,b}, while mapping each other point 643 (x', y') of W_{a',b'} to the point (x, y):=(x/u^2, y/u^3) of W_{a,b}. 645 Implementations may take advantage of this mapping to carry out 646 elliptic curve group operations originally defined for a Weierstrass 647 curve with a generic domain parameter a on a corresponding isomorphic 648 Weierstrass curve with domain parameter a' that has a special form, 649 which is known to allow for more efficient implementations of 650 addition laws, and translating the result back to the original curve. 651 In particular, it is known that such efficiency improvements exist if 652 a'=-3 (mod p) and one uses so-called Jacobian coordinates with a 653 particular projective version of the addition laws of Appendix B.1. 654 While not all Weierstrass curves can be put into this form, all 655 traditional NIST curves have domain parameter a=-3, while all 656 Brainpool curves [RFC5639] are isomorphic to a Weierstrass curve of 657 this form. For details, we refer to [GECC]. 659 Note that implementations for elliptic curves with short-Weierstrass 660 form that hard-code the domain parameter a to a= -3 (which value is 661 known to allow more efficient implementations) cannot always be used 662 this way, since the curve W_{a,b} may not always be expressed in 663 terms of a Weierstrass curve with a'=-3 via a coordinate 664 transformation: this only holds if a'/a is a fourth power in GF(q). 665 However, even in this case, one can still express the curve W_{a,b} 666 in terms of a Weierstrass curve with small a' domain parameter, 667 thereby still allowing a more efficient implementation than with a 668 general a value. 670 E.2. Isogeneous Mapping between Weierstrass Curves 672 One can still map points of the Weierstrass curve W_{a,b} to points 673 of the Weierstrass curve W_{a',b'}, where a':=-3 (mod p), even if 674 a'/a is not a fourth power in GF(q). In that case, this mappping 675 cannot be an isomorphism (see Appendix E.1) and, thereby, does not 676 define a one-to-one correspondence. Instead, the mapping is a so- 677 called isogeny (or homomorphism). Since most elliptic curve 678 operations process points of prime order or use so-called "co-factor 679 multiplication", in practice the resulting mapping has similar 680 properties. In particular, one can still take advantage of this 681 mapping to carry out elliptic curve group operations originally 682 defined for a Weierstrass curve with domain parameter a unequal to -3 683 (mod p) on a corresponding isogenous Weierstrass curve with domain 684 parameter a'=-3 (mod p) and translating the result back to the 685 original curve. Details of this mapping are outside scope of this 686 document. 688 Appendix F. Further Cousins of Curve25519 690 F.1. Further Alternative Representations 692 The Weierstrass curve Wei25519 is isomorphic to the Weierstrass curve 693 Wei25519.2 defined over GF(p), with as base point the pair (G1x,G1y), 694 where parameters are as specified in Appendix F.3. 696 F.2. Further Switching 698 Each affine point (x,y) of Wei25519 corresponds to the point 699 (x,y):=(x*u^2,y*u^3) of Wei25519.2, where u is the element of GF(p) 700 defined by 702 u 47731687248873559672555216906496754195083410699918207029391079363 703 6321486119 705 (=0x10e26dacae93602704c7e6cff9efe595764cb5c9e04931f6fdeefc657d4e5 706 27), 708 while the point at infinity of Wei25519 corresponds to the point at 709 infinity of Wei25519.2. (Here, we used the mapping of Appendix E.1.) 710 Under this mapping, the base point (Gx',Gy') of Wei25519 corresponds 711 to the base point (G1x',G1y') of Wei25519.2. The inverse mapping 712 maps the affine point (x,y) of Wei25519.2 to (x,y):=(x/u^2,y/u^3) of 713 Wei25519, while mapping the point at infinity of Wei25519.2 to the 714 point at infinity of Wei25519. Note that this mapping (and its 715 inverse) involves a multiplication of both coordinates with fixed 716 constants u^2 and u^3 (respectively, 1/u^2 and 1/u^3), which can be 717 precomputed. 719 F.3. Further Domain Parameters 721 The parameters of the Weierstrass curve with a=2 that is isomorphic 722 with Wei25519 and the parameters of the Weierstrass curve with a=-3 723 that is isogeneous with Wei25519 are as indicated below. Both domain 724 parameter sets can be exploited directly to derive more efficient 725 point addition formulae, should an implementation facilitate this. 727 Weierstrass curve-specific parameters (with a=2): 729 a 2 (=0x2) 731 b 45793404337388339159414415854563976158160282736335993851976016290 732 777777599260 734 (=0x653e25fa 4aa43eb9 cc42c61b 806bcfd1 0e67bc23 09966e90 735 95a202fe 9aac731c) 737 G1x' 218726072268944427441327971914352883414836203960572472224621495 738 35754145422686 740 (=0x305b74fc 935f1dad d440a88e 781f0a81 09d6a68d 98c6081a 741 660528e2 0746dd5e) 743 G1y' 139436179034864291344077235766386796155987755307479919871866321 744 47013341290929 746 (=0x1ed3cedc e78b6b19 5d1c361c e1d4ef00 5b5b102c 99083780 747 bf830f7e a89021b1) 749 Weierstrass curve-specific parameters (with a=-3): 751 [NOTE: parameters indicated with TBD still to be completed, pending 752 completion of Sage calculations.] 754 a -3 755 (=0x7fffffff ffffffff ffffffff ffffffff ffffffff ffffffff 756 ffffffff ffffffea) 758 b [TBD] 760 (=0x[TBD]) 762 G2x' [TBD] 764 (=0x[TBD]) 766 G2y' [TBD] 768 (=0x[TBD]) 770 Author's Address 772 Rene Struik 773 Struik Security Consultancy 775 Email: rstruik.ext@gmail.com