< draft-ietf-lwig-curve-representations-06.txt   draft-ietf-lwig-curve-representations-07.txt >
lwig R. Struik lwig R. Struik
Internet-Draft Struik Security Consultancy Internet-Draft Struik Security Consultancy
Intended status: Informational May 16, 2019 Intended status: Informational July 8, 2019
Expires: November 17, 2019 Expires: January 9, 2020
Alternative Elliptic Curve Representations Alternative Elliptic Curve Representations
draft-ietf-lwig-curve-representations-06 draft-ietf-lwig-curve-representations-07
Abstract Abstract
This document specifies how to represent Montgomery curves and This document specifies how to represent Montgomery curves and
(twisted) Edwards curves as curves in short-Weierstrass form and (twisted) Edwards curves as curves in short-Weierstrass form and
illustrates how this can be used to carry out elliptic curve illustrates how this can be used to carry out elliptic curve
computations using existing implementations of, e.g., ECDSA and ECDH computations using existing implementations of, e.g., ECDSA and ECDH
using NIST prime curves. using NIST prime curves.
Requirements Language Requirements Language
skipping to change at page 1, line 41 skipping to change at page 1, line 41
Internet-Drafts are working documents of the Internet Engineering Internet-Drafts are working documents of the Internet Engineering
Task Force (IETF). Note that other groups may also distribute Task Force (IETF). Note that other groups may also distribute
working documents as Internet-Drafts. The list of current Internet- working documents as Internet-Drafts. The list of current Internet-
Drafts is at https://datatracker.ietf.org/drafts/current/. Drafts is at https://datatracker.ietf.org/drafts/current/.
Internet-Drafts are draft documents valid for a maximum of six months Internet-Drafts are draft documents valid for a maximum of six months
and may be updated, replaced, or obsoleted by other documents at any and may be updated, replaced, or obsoleted by other documents at any
time. It is inappropriate to use Internet-Drafts as reference time. It is inappropriate to use Internet-Drafts as reference
material or to cite them other than as "work in progress." material or to cite them other than as "work in progress."
This Internet-Draft will expire on November 17, 2019. This Internet-Draft will expire on January 9, 2020.
Copyright Notice Copyright Notice
Copyright (c) 2019 IETF Trust and the persons identified as the Copyright (c) 2019 IETF Trust and the persons identified as the
document authors. All rights reserved. document authors. All rights reserved.
This document is subject to BCP 78 and the IETF Trust's Legal This document is subject to BCP 78 and the IETF Trust's Legal
Provisions Relating to IETF Documents Provisions Relating to IETF Documents
(https://trustee.ietf.org/license-info) in effect on the date of (https://trustee.ietf.org/license-info) in effect on the date of
publication of this document. Please review these documents publication of this document. Please review these documents
skipping to change at page 2, line 40 skipping to change at page 2, line 40
10.3. COSE Algorithms Registration (2/2) . . . . . . . . . . . 13 10.3. COSE Algorithms Registration (2/2) . . . . . . . . . . . 13
10.4. JOSE Elliptic Curves Registration . . . . . . . . . . . 13 10.4. JOSE Elliptic Curves Registration . . . . . . . . . . . 13
10.5. JOSE Algorithms Registration (1/2) . . . . . . . . . . . 13 10.5. JOSE Algorithms Registration (1/2) . . . . . . . . . . . 13
10.6. JOSE Algorithms Registration (2/2) . . . . . . . . . . . 14 10.6. JOSE Algorithms Registration (2/2) . . . . . . . . . . . 14
11. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . 14 11. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . 14
12. References . . . . . . . . . . . . . . . . . . . . . . . . . 14 12. References . . . . . . . . . . . . . . . . . . . . . . . . . 14
12.1. Normative References . . . . . . . . . . . . . . . . . . 14 12.1. Normative References . . . . . . . . . . . . . . . . . . 14
12.2. Informative References . . . . . . . . . . . . . . . . . 16 12.2. Informative References . . . . . . . . . . . . . . . . . 16
Appendix A. Some (non-Binary) Elliptic Curves . . . . . . . . . 17 Appendix A. Some (non-Binary) Elliptic Curves . . . . . . . . . 17
A.1. Curves in short-Weierstrass Form . . . . . . . . . . . . 17 A.1. Curves in short-Weierstrass Form . . . . . . . . . . . . 17
A.2. Montgomery Curves . . . . . . . . . . . . . . . . . . . . 17 A.2. Montgomery Curves . . . . . . . . . . . . . . . . . . . . 18
A.3. Twisted Edwards Curves . . . . . . . . . . . . . . . . . 18 A.3. Twisted Edwards Curves . . . . . . . . . . . . . . . . . 18
Appendix B. Elliptic Curve Nomenclature and Finite Fields . . . 18 Appendix B. Elliptic Curve Nomenclature and Finite Fields . . . 18
B.1. Elliptic Curve Nomenclature . . . . . . . . . . . . . . . 18 B.1. Elliptic Curve Nomenclature . . . . . . . . . . . . . . . 18
B.2. Finite Fields . . . . . . . . . . . . . . . . . . . . . . 20 B.2. Finite Fields . . . . . . . . . . . . . . . . . . . . . . 20
Appendix C. Elliptic Curve Group Operations . . . . . . . . . . 21 Appendix C. Elliptic Curve Group Operations . . . . . . . . . . 21
C.1. Group Law for Weierstrass Curves . . . . . . . . . . . . 21 C.1. Group Law for Weierstrass Curves . . . . . . . . . . . . 21
C.2. Group Law for Montgomery Curves . . . . . . . . . . . . . 21 C.2. Group Law for Montgomery Curves . . . . . . . . . . . . . 22
C.3. Group Law for Twisted Edwards Curves . . . . . . . . . . 22 C.3. Group Law for Twisted Edwards Curves . . . . . . . . . . 22
Appendix D. Relationship Between Curve Models . . . . . . . . . 23 Appendix D. Relationship Between Curve Models . . . . . . . . . 23
D.1. Mapping between Twisted Edwards Curves and Montgomery D.1. Mapping between Twisted Edwards Curves and Montgomery
Curves . . . . . . . . . . . . . . . . . . . . . . . . . 23 Curves . . . . . . . . . . . . . . . . . . . . . . . . . 24
D.2. Mapping between Montgomery Curves and Weierstrass Curves 24 D.2. Mapping between Montgomery Curves and Weierstrass Curves 24
D.3. Mapping between Twisted Edwards Curves and Weierstrass D.3. Mapping between Twisted Edwards Curves and Weierstrass
Curves . . . . . . . . . . . . . . . . . . . . . . . . . 25 Curves . . . . . . . . . . . . . . . . . . . . . . . . . 25
Appendix E. Curve25519 and Cousins . . . . . . . . . . . . . . . 25 Appendix E. Curve25519 and Cousins . . . . . . . . . . . . . . . 25
E.1. Curve Definition and Alternative Representations . . . . 25 E.1. Curve Definition and Alternative Representations . . . . 25
E.2. Switching between Alternative Representations . . . . . . 26 E.2. Switching between Alternative Representations . . . . . . 26
E.3. Domain Parameters . . . . . . . . . . . . . . . . . . . . 27 E.3. Domain Parameters . . . . . . . . . . . . . . . . . . . . 27
Appendix F. Further Mappings . . . . . . . . . . . . . . . . . . 29 Appendix F. Further Mappings . . . . . . . . . . . . . . . . . . 29
F.1. Isomorphic Mapping between Twisted Edwards Curves . . . . 29 F.1. Isomorphic Mapping between Twisted Edwards Curves . . . . 30
F.2. Isomorphic Mapping between Montgomery Curves . . . . . . 30 F.2. Isomorphic Mapping between Montgomery Curves . . . . . . 30
F.3. Isomorphic Mapping between Weierstrass Curves . . . . . . 31 F.3. Isomorphic Mapping between Weierstrass Curves . . . . . . 31
F.4. Isogenous Mapping between Weierstrass Curves . . . . . . 32 F.4. Isogenous Mapping between Weierstrass Curves . . . . . . 32
Appendix G. Further Cousins of Curve25519 . . . . . . . . . . . 33 Appendix G. Further Cousins of Curve25519 . . . . . . . . . . . 33
G.1. Further Alternative Representations . . . . . . . . . . . 33 G.1. Further Alternative Representations . . . . . . . . . . . 33
G.2. Further Switching . . . . . . . . . . . . . . . . . . . . 33 G.2. Further Switching . . . . . . . . . . . . . . . . . . . . 33
G.3. Further Domain Parameters . . . . . . . . . . . . . . . . 34 G.3. Further Domain Parameters . . . . . . . . . . . . . . . . 34
Appendix H. Isogeny Details . . . . . . . . . . . . . . . . . . 36 Appendix H. Isogeny Details . . . . . . . . . . . . . . . . . . 36
H.1. Isogeny Parameters . . . . . . . . . . . . . . . . . . . 36 H.1. Isogeny Parameters . . . . . . . . . . . . . . . . . . . 36
H.1.1. Coefficients of u(x) . . . . . . . . . . . . . . . . 36 H.1.1. Coefficients of u(x) . . . . . . . . . . . . . . . . 36
skipping to change at page 3, line 35 skipping to change at page 3, line 35
H.1.3. Coefficients of w(x) . . . . . . . . . . . . . . . . 41 H.1.3. Coefficients of w(x) . . . . . . . . . . . . . . . . 41
H.2. Dual Isogeny Parameters . . . . . . . . . . . . . . . . . 42 H.2. Dual Isogeny Parameters . . . . . . . . . . . . . . . . . 42
H.2.1. Coefficients of u'(x) . . . . . . . . . . . . . . . . 42 H.2.1. Coefficients of u'(x) . . . . . . . . . . . . . . . . 42
H.2.2. Coefficients of v'(x) . . . . . . . . . . . . . . . . 44 H.2.2. Coefficients of v'(x) . . . . . . . . . . . . . . . . 44
H.2.3. Coefficients of w'(x) . . . . . . . . . . . . . . . . 47 H.2.3. Coefficients of w'(x) . . . . . . . . . . . . . . . . 47
Appendix I. Point Compression . . . . . . . . . . . . . . . . . 48 Appendix I. Point Compression . . . . . . . . . . . . . . . . . 48
I.1. Point Compression for Weierstrass Curves . . . . . . . . 49 I.1. Point Compression for Weierstrass Curves . . . . . . . . 49
I.2. Point Compression for Montgomery Curves . . . . . . . . . 49 I.2. Point Compression for Montgomery Curves . . . . . . . . . 49
I.3. Point Compression for Twisted Edwards Curves . . . . . . 50 I.3. Point Compression for Twisted Edwards Curves . . . . . . 50
Appendix J. Data Conversions . . . . . . . . . . . . . . . . . . 51 Appendix J. Data Conversions . . . . . . . . . . . . . . . . . . 51
J.1. Conversion between Bit Strings and Integers . . . . . . . 51 J.1. Conversion between Bit Strings and Integers . . . . . . . 52
J.2. Conversion between Octet Strings and Integers (OS2I, J.2. Conversion between Octet Strings and Integers (OS2I,
I2OS) . . . . . . . . . . . . . . . . . . . . . . . . . . 51 I2OS) . . . . . . . . . . . . . . . . . . . . . . . . . . 52
J.3. Conversion between Octet Strings and Bit Strings (BS2OS, J.3. Conversion between Octet Strings and Bit Strings (BS2OS,
OS2BS) . . . . . . . . . . . . . . . . . . . . . . . . . 52 OS2BS) . . . . . . . . . . . . . . . . . . . . . . . . . 52
J.4. Conversion between Field Elements and Octet Strings J.4. Conversion between Field Elements and Octet Strings
(FE2OS, OS2FE) . . . . . . . . . . . . . . . . . . . . . 52 (FE2OS, OS2FE) . . . . . . . . . . . . . . . . . . . . . 53
J.5. Conversion between Elements of Z mod n and Octet Strings J.5. Conversion between Elements of Z mod n and Octet Strings
(ZnE2OS, OS2ZnE) . . . . . . . . . . . . . . . . . . . . 53 (ZnE2OS, OS2ZnE) . . . . . . . . . . . . . . . . . . . . 53
J.6. Ordering Conventions . . . . . . . . . . . . . . . . . . 53 J.6. Ordering Conventions . . . . . . . . . . . . . . . . . . 54
Appendix K. Representation Examples Curve25519 Family Members . 54 Appendix K. Representation Examples Curve25519 Family Members . 55
K.1. Example with Curve25519 . . . . . . . . . . . . . . . . . 55 K.1. Example with Curve25519 . . . . . . . . . . . . . . . . . 55
K.2. Example with Edwards25519 . . . . . . . . . . . . . . . . 56 K.2. Example with Edwards25519 . . . . . . . . . . . . . . . . 57
K.3. Example with Wei25519 . . . . . . . . . . . . . . . . . . 58 K.3. Example with Wei25519 . . . . . . . . . . . . . . . . . . 58
K.4. Example with Wei25519.2 . . . . . . . . . . . . . . . . . 59 K.4. Example with Wei25519.2 . . . . . . . . . . . . . . . . . 60
K.5. Example with Wei25519.-3 . . . . . . . . . . . . . . . . 61 K.5. Example with Wei25519.-3 . . . . . . . . . . . . . . . . 61
Appendix L. Auxiliary Functions . . . . . . . . . . . . . . . . 62 Appendix L. Auxiliary Functions . . . . . . . . . . . . . . . . 62
L.1. Square Roots in GF(q) . . . . . . . . . . . . . . . . . . 62 L.1. Square Roots in GF(q) . . . . . . . . . . . . . . . . . . 62
L.1.1. Square Roots in GF(q), where q = 3 (mod 4) . . . . . 62 L.1.1. Square Roots in GF(q), where q = 3 (mod 4) . . . . . 62
L.1.2. Square Roots in GF(q), where q = 5 (mod 8) . . . . . 62 L.1.2. Square Roots in GF(q), where q = 5 (mod 8) . . . . . 63
L.2. Inversion . . . . . . . . . . . . . . . . . . . . . . . . 62 L.2. Inversion . . . . . . . . . . . . . . . . . . . . . . . . 63
Author's Address . . . . . . . . . . . . . . . . . . . . . . . . 63 L.3. Mapping to Curve Points . . . . . . . . . . . . . . . . . 63
L.3.1. Mapping to Points of Weierstrass Curve . . . . . . . 63
L.3.2. Mapping to Points of Montgomery Curve . . . . . . . . 64
L.3.3. Mapping to Points of Twisted Edwards Curve . . . . . 65
L.4. Randomized Representation of Curve Points . . . . . . . . 65
Author's Address . . . . . . . . . . . . . . . . . . . . . . . . 66
1. Fostering Code Reuse with New Elliptic Curves 1. Fostering Code Reuse with New Elliptic Curves
It is well-known that elliptic curves can be represented using It is well-known that elliptic curves can be represented using
different curve models. Recently, IETF standardized elliptic curves different curve models. Recently, IETF standardized elliptic curves
that are claimed to have better performance and improved robustness that are claimed to have better performance and improved robustness
against "real world" attacks than curves represented in the against "real world" attacks than curves represented in the
traditional "short" Weierstrass model. This document specifies an traditional "short" Weierstrass model. This document specifies an
alternative representation of points of Curve25519, a so-called alternative representation of points of Curve25519, a so-called
Montgomery curve, and of points of Edwards25519, a so-called twisted Montgomery curve, and of points of Edwards25519, a so-called twisted
skipping to change at page 17, line 10 skipping to change at page 17, line 10
[Mont-Ladder] [Mont-Ladder]
P.L. Montgomery, "Speeding the Pollard and Elliptic Curve P.L. Montgomery, "Speeding the Pollard and Elliptic Curve
Methods of Factorization", Mathematics of Methods of Factorization", Mathematics of
Computation, Vol. 48, 1987. Computation, Vol. 48, 1987.
[Rosener] N. Rosener, "Evaluating the Performance of Transformations [Rosener] N. Rosener, "Evaluating the Performance of Transformations
Between Curve Representations in Elliptic Curve Between Curve Representations in Elliptic Curve
Cryptography for Constrained Device Security", Cryptography for Constrained Device Security",
M.Sc. Universitat Bremen, August 2018. M.Sc. Universitat Bremen, August 2018.
[SWUmap] E. Brier, J-S. Coron, Th. Icart, D. Madore, H. Randriam,
M. Tibouchi, "Efficient Indifferentiable Hashing into
Ordinary Elliptic Curves", CRYPTO 2010, Lecture Notes in
Computer Science, Vol. 6223, New York: Springer-Verlag,
2010.
[tEd] D.J. Bernstein, P. Birkner, M. Joye, T. Lange, C. Peters, [tEd] D.J. Bernstein, P. Birkner, M. Joye, T. Lange, C. Peters,
"Twisted Edwards Curves", Africacrypt 2008, Lecture Notes "Twisted Edwards Curves", Africacrypt 2008, Lecture Notes
in Computer Science, Vol. 5023, New York: Springer-Verlag, in Computer Science, Vol. 5023, New York: Springer-Verlag,
2008. 2008.
[tEd-Formulas] [tEd-Formulas]
H. Hisil, K.K.H. Wong, G. Carter, E. Dawson, "Twisted H. Hisil, K.K.H. Wong, G. Carter, E. Dawson, "Twisted
Edwards Curves Revisited", ASIACRYPT 2008, Lecture Notes Edwards Curves Revisited", ASIACRYPT 2008, Lecture Notes
in Computer Science, Vol. 5350, New York: Springer-Verlag, in Computer Science, Vol. 5350, New York: Springer-Verlag,
2008. 2008.
[Tibouchi]
M. Tibouchi, "Elligator Squared -- Uniform Points on
Elliptic Curves of Prime Order as Uniform Random Strings",
Financial Cryptography 2014, Lecture Notes in Computer
Science, Vol. 8437, New York: Springer-Verlag, 2014.
[Wei-Ladder] [Wei-Ladder]
T. Izu, Ts. Takagi,, "A Fast Parallel Elliptic Curve T. Izu, Ts. Takagi,, "A Fast Parallel Elliptic Curve
Multiplication Resistant Against Side Channel Attacks", Multiplication Resistant Against Side Channel Attacks",
Centre for Applied Cryptographic Research, Corr 2002-03, Centre for Applied Cryptographic Research, Corr 2002-03,
2002. 2002.
Appendix A. Some (non-Binary) Elliptic Curves Appendix A. Some (non-Binary) Elliptic Curves
A.1. Curves in short-Weierstrass Form A.1. Curves in short-Weierstrass Form
skipping to change at page 20, line 38 skipping to change at page 20, line 46
field GF(p) as a subset. If m=1, we always pick f(z):=z, so that the field GF(p) as a subset. If m=1, we always pick f(z):=z, so that the
definions of GF(p) and GF(p^1) above coincide. If m>1, then GF(q) is definions of GF(p) and GF(p^1) above coincide. If m>1, then GF(q) is
called a (nontrivial) extension field over GF(p). The number p is called a (nontrivial) extension field over GF(p). The number p is
called the characteristic of GF(q). called the characteristic of GF(q).
A field element y is called a square in GF(q) if it can be expressed A field element y is called a square in GF(q) if it can be expressed
as y:=x^2 for some x in GF(q); it is called a non-square in GF(q) as y:=x^2 for some x in GF(q); it is called a non-square in GF(q)
otherwise. If y is a square in GF(q), we denote by sqrt(y) one of otherwise. If y is a square in GF(q), we denote by sqrt(y) one of
its square roots (the other one being -sqrt(y)). For methods for its square roots (the other one being -sqrt(y)). For methods for
computing square roots and inverses in GF(q) - if these exist - see computing square roots and inverses in GF(q) - if these exist - see
Appendix L.1 and Appendix L.2, respectively. Appendix L.1 and Appendix L.2, respectively. For methods for mapping
a nonzero field element that is not a square in GF(q) to a point of a
curve, see Appendix L.3.
NOTE: The curves in Appendix E and Appendix G are all defined over a NOTE: The curves in Appendix E and Appendix G are all defined over a
prime field GF(p), thereby reducing all operations to simple modular prime field GF(p), thereby reducing all operations to simple modular
integer arithmetic. Strictly speaking we could, therefore, have integer arithmetic. Strictly speaking we could, therefore, have
refrained from introducing extension fields. Nevertheless, we refrained from introducing extension fields. Nevertheless, we
included the more general exposition, so as to accommodate potential included the more general exposition, so as to accommodate potential
introduction of new curves that are defined over a (nontrivial) introduction of new curves that are defined over a (nontrivial)
extension field at some point in the future. This includes curves extension field at some point in the future. This includes curves
proposed for post-quantum isogeny-based schemes, which are defined proposed for post-quantum isogeny-based schemes, which are defined
over a quadratic extension field (i.e., where q:=p^2), and elliptic over a quadratic extension field (i.e., where q:=p^2), and elliptic
skipping to change at page 24, line 35 skipping to change at page 24, line 47
One can map points of the Montgomery curve M_{A,B} to points of the One can map points of the Montgomery curve M_{A,B} to points of the
Weierstrass curve W_{a,b}, where a:=(3-A^2)/(3*B^2) and Weierstrass curve W_{a,b}, where a:=(3-A^2)/(3*B^2) and
b:=(2*A^3-9*A)/(27*B^3). This defines a one-to-one correspondence, b:=(2*A^3-9*A)/(27*B^3). This defines a one-to-one correspondence,
which - in fact - is an isomorphism between M_{A,B} and W_{a,b}, which - in fact - is an isomorphism between M_{A,B} and W_{a,b},
thereby showing that, e.g., the discrete logarithm problem in either thereby showing that, e.g., the discrete logarithm problem in either
curve model is equally hard. curve model is equally hard.
The mapping from M_{A,B} to W_{a,b} is defined by mapping the point The mapping from M_{A,B} to W_{a,b} is defined by mapping the point
at infinity O of M_{A,B} to the point at infinity O of W_{a,b}, while at infinity O of M_{A,B} to the point at infinity O of W_{a,b}, while
mapping each other point (u,v) of M_{A,B} to the point mapping each other point (u,v) of M_{A,B} to the point
(X,Y):=(u/B+A/(3*B),v/B) of W_{a,b}. Note that not all Weierstrass (X,Y):=((u+A/3)/B,v/B) of W_{a,b}. Note that not all Weierstrass
curves can be injectively mapped to Montgomery curves, since the curves can be injectively mapped to Montgomery curves, since the
latter have a point of order two and the former may not. In latter have a point of order two and the former may not. In
particular, if a Weierstrass curve has prime order, such as is the particular, if a Weierstrass curve has prime order, such as is the
case with the so-called "NIST curves", this inverse mapping is not case with the so-called "NIST curves", this inverse mapping is not
defined. defined.
If the Weierstrass curve W_{a,b} has a point (alpha,0) of order two If the Weierstrass curve W_{a,b} has a point (alpha,0) of order two
and c:=a+3*(alpha)^2 is a square in GF(q), one can map points of this and c:=a+3*(alpha)^2 is a square in GF(q), one can map points of this
curve to points of the Montgomery curve M_{A,B}, where A:=3*alpha/ curve to points of the Montgomery curve M_{A,B}, where A:=3*alpha/
gamma and B:=1/gamma and where gamma is any square root of c. In gamma and B:=1/gamma and where gamma is any square root of c. In
skipping to change at page 25, line 24 skipping to change at page 25, line 35
form that hard-code the domain parameter a to a= -3 (which value is form that hard-code the domain parameter a to a= -3 (which value is
known to allow more efficient implementations) cannot always be used known to allow more efficient implementations) cannot always be used
this way, since the curve W_{a,b} resulting from an isomorphic this way, since the curve W_{a,b} resulting from an isomorphic
mapping cannot always be expressed as a Weierstrass curve with a=-3 mapping cannot always be expressed as a Weierstrass curve with a=-3
via a coordinate transformation. For more details, see Appendix F. via a coordinate transformation. For more details, see Appendix F.
D.3. Mapping between Twisted Edwards Curves and Weierstrass Curves D.3. Mapping between Twisted Edwards Curves and Weierstrass Curves
One can map points of the twisted Edwards curve E_{a,d} to points of One can map points of the twisted Edwards curve E_{a,d} to points of
the Weierstrass curve W_{a,b}, via function composition, where one the Weierstrass curve W_{a,b}, via function composition, where one
uses the isomorphic mapping between twisted Edwards curve and uses the isomorphic mapping between twisted Edwards curves and
Montgomery curves of Appendix D.1 and the one between Montgomery and Montgomery curves of Appendix D.1 and the one between Montgomery and
Weierstrass curves of Appendix D.2. Obviously, one can use function Weierstrass curves of Appendix D.2. Obviously, one can use function
composition (now using the respective inverses - if these exist) to composition (now using the respective inverses - if these exist) to
realize the inverse of this mapping. realize the inverse of this mapping.
Appendix E. Curve25519 and Cousins Appendix E. Curve25519 and Cousins
E.1. Curve Definition and Alternative Representations E.1. Curve Definition and Alternative Representations
The elliptic curve Curve25519 is the Montgomery curve M_{A,B} defined The elliptic curve Curve25519 is the Montgomery curve M_{A,B} defined
skipping to change at page 49, line 29 skipping to change at page 49, line 31
where alpha:=X^3+a*X+b. If alpha is not a square in GF(q), this where alpha:=X^3+a*X+b. If alpha is not a square in GF(q), this
equation does not have a solution in GF(q) and the ordered pair (X, equation does not have a solution in GF(q) and the ordered pair (X,
t) does not correspond to a point of this curve. Otherwise, there t) does not correspond to a point of this curve. Otherwise, there
are two solutions, viz. Y=sqrt(alpha) and -Y. If alpha is a nonzero are two solutions, viz. Y=sqrt(alpha) and -Y. If alpha is a nonzero
element of GF(q), one can uniquely recover the Y-coordinate for which element of GF(q), one can uniquely recover the Y-coordinate for which
par(Y):=t and, thereby, the point P:=(X, Y). This is also the case par(Y):=t and, thereby, the point P:=(X, Y). This is also the case
if alpha=0 and t=0, in which case Y=0 and the point P has order two. if alpha=0 and t=0, in which case Y=0 and the point P has order two.
However, if alpha=0 and t=1, the ordered pair (X, t) does not However, if alpha=0 and t=1, the ordered pair (X, t) does not
correspond to the outcome of the point compression function. correspond to the outcome of the point compression function.
If the Weierstrass curve W_{a,b} has a point of order two, we extend We extend the definition of the point compression function to all
the definition of the point compression function to all points of the points of the curve W_{a,b}, by associating the (non-affine) point at
curve, by associating the (non-affine) point at infinity O with the infinity O with any ordered pair compr(O):=(X,0), where X is any
ordered pair compr(O):=(X,1), where (X,0) is any point of order two, element of GF(q) for which alpha:=X^3+a*X+b is a non-square in GF(q),
and recover this point accordingly. (Note that this corresponds to and recover this point accordingly. In this case, the point at
the case alpha=0 and t=1 above.) In this case, the point at infinity infinity O can be represented by any ordered pair (X,0) of elements
O can be represented by any ordered pair (X, 1) of elements of GF(q), of GF(q) for which X^3+a*X+b is a non-square in GF(q). Note that
where (X,0) is any point of order two. Note that this ordered pair this ordered pair does not satisfy the defining equation of the curve
does not satisfy the defining equation of the curve in question. in question. An application may fix a specific suitable value of X
or choose multiple such values and use this to encode additonal
information. Further details are out of scope.
I.2. Point Compression for Montgomery Curves I.2. Point Compression for Montgomery Curves
If P:=(u, v) is an affine point of the Montgomery curve M_{A,B} If P:=(u, v) is an affine point of the Montgomery curve M_{A,B}
defined over the field GF(q), then so is -P:=(u, -v). Since the defined over the field GF(q), then so is -P:=(u, -v). Since the
defining equation B*v^2=u^3+A*u^2+u has at most two solutions with defining equation B*v^2=u^3+A*u^2+u has at most two solutions with
fixed u-value, one can represent P by its u-coordinate and one bit of fixed u-value, one can represent P by its u-coordinate and one bit of
information that allows one to distinguish P from -P, i.e., one can information that allows one to distinguish P from -P, i.e., one can
represent P as the ordered pair compr(P):=(u, par(v)). If P is a represent P as the ordered pair compr(P):=(u, par(v)). If P is a
point of order two, one can uniquely represent P by its u-coordinate point of order two, one can uniquely represent P by its u-coordinate
skipping to change at page 50, line 51 skipping to change at page 51, line 8
-x. If alpha is a nonzero element of GF(q), one can uniquely recover -x. If alpha is a nonzero element of GF(q), one can uniquely recover
the x-coordinate for which par(x):=t and, thereby, the affine point the x-coordinate for which par(x):=t and, thereby, the affine point
P:=(x, y). This is also the case if alpha=0 and t=0, in which case P:=(x, y). This is also the case if alpha=0 and t=0, in which case
x=0 and the point P has order one or two. However, if alpha=0 and x=0 and the point P has order one or two. However, if alpha=0 and
t=1, the ordered pair (t, y) does not correspond to the outcome of t=1, the ordered pair (t, y) does not correspond to the outcome of
the point compression function. the point compression function.
Note that the point compression function is defined for all points of Note that the point compression function is defined for all points of
the twisted Edwards curve E_{a,d} (subject to the Note in the twisted Edwards curve E_{a,d} (subject to the Note in
Appendix C.3). Here, the identity element O:=(0,1) is associated Appendix C.3). Here, the identity element O:=(0,1) is associated
with the compressed point compr(O):=(0,1). with the compressed point compr(O):=(0,1). (Note that this
corresponds to the case alpha=0 and t=0 above.)
We extend the definition of the compression function further, to also
include a special marker element 'btm', by associating this marker
element with the ordered pair compr(btm):=(1,1) and recover this
marker element accordingly. (Note that this corresponds to the case
alpha=0 and t=1 above.) The marker element 'btm' can be represented
by the ordered pair (1,1) of elements of GF(q). Note that this
ordered pair does not satisfy the defining equation of the curve in
question.
Appendix J. Data Conversions Appendix J. Data Conversions
The string over some alphabet S consisting of the symbols x_{l-1}, The string over some alphabet S consisting of the symbols x_{l-1},
x_{l-2}, ..., x_1, x_0 (each in S), in this order, is denoted by x_{l-2}, ..., x_1, x_0 (each in S), in this order, is denoted by
str(x_{l-1}, x_{l-2}, ..., x_1, x_0). The length of this string str(x_{l-1}, x_{l-2}, ..., x_1, x_0). The length of this string
(over S) is the number of symbols it contains (here: l). The empty (over S) is the number of symbols it contains (here: l). The empty
string is the (unique) string of length l=0. string is the (unique) string of length l=0.
The right-concatenation of two strings X and Y (defined over the same The right-concatenation of two strings X and Y (defined over the same
skipping to change at page 57, line 45 skipping to change at page 58, line 19
f5b5da19 923d6da7, f5b5da19 923d6da7,
where the rightmost bit of the rightmost octet indicates the parity where the rightmost bit of the rightmost octet indicates the parity
of the x-coordinate of the point of Edwards25519 in question (which, of the x-coordinate of the point of Edwards25519 in question (which,
in this case, are zero and one, respectively, since x is even and x1 in this case, are zero and one, respectively, since x is even and x1
is odd). See Appendix I.3 and Appendix J for further detail on is odd). See Appendix I.3 and Appendix J for further detail on
(squeezed) point compression. (squeezed) point compression.
The scalar representation and (squeezed) point representation The scalar representation and (squeezed) point representation
illustrated above are fully consistent with the representations illustrated above are fully consistent with the representations
specified in [RFC8032]. Note that, contrary to [RFC8032], [RFC8032] specified in [RFC8032]. Note that, contrary to [RFC7748], [RFC8032]
requires unique representations of all elements of GF(p). requires unique representations of all elements of GF(p).
K.3. Example with Wei25519 K.3. Example with Wei25519
Pw=(X, Y), k*Pw=(X1, Y1), and (k+1)*Pw=(X2, Y2) with Wei25519: Pw=(X, Y), k*Pw=(X1, Y1), and (k+1)*Pw=(X2, Y2) with Wei25519:
X 14428294459702615171094958724191825368445920488283965295163094662 X 14428294459702615171094958724191825368445920488283965295163094662
783879239338 783879239338
(=0x1fe62011 89e0801e f1debed7 456a3dc7 94d3ac0b 55202fe7 (=0x1fe62011 89e0801e f1debed7 456a3dc7 94d3ac0b 55202fe7
skipping to change at page 63, line 16 skipping to change at page 63, line 37
1/y:=y^{q-2} (since y^{q-1}=1). 1/y:=y^{q-2} (since y^{q-1}=1).
Further details are out of scope. If inverses are easy to compute in Further details are out of scope. If inverses are easy to compute in
GF(q), then so are these in GF(q^2). GF(q), then so are these in GF(q^2).
The inverses of two nonzero elements y1 and y2 of GF(q) can be The inverses of two nonzero elements y1 and y2 of GF(q) can be
computed by first computing the inverse z of y1*y2 and by computed by first computing the inverse z of y1*y2 and by
subsequently computing y2*z=:1/y1 and y1*z=:1/y2. subsequently computing y2*z=:1/y1 and y1*z=:1/y2.
L.3. Mapping to Curve Points
One can map elements of GF(q) that are not a square in GF(q) to
points of a Weierstrass curve (see Appendix L.3.1), to points of a
Montgomery curve (see Appendix L.3.2), or to points of a twisted
Edwards curve (see Appendix L.3.3), under some mild conditions on the
domain parameters. Details on mappings that apply if these
conditions are not satisfied are out of scope.
L.3.1. Mapping to Points of Weierstrass Curve
The description below assumes that the domain parameters a and b of
the Weierstrass curve W_{a,b} are nonzero. For ease of exposition,
we define f(z):=z^3+a*z+b. (Note that for an affine point (X,Y) of
W_{a,b} one has Y^2=f(X).)
If t is an element of GF(q) that is not a square in GF(q) and that is
unequal to -1, then the element X:=(-b/a)*(1+1/(t+t^2)) is the unique
solution of the equation f(t*X)=t^3*f(X). Consequently, either X or
X':=t*X is the x-coordinate of an affine point of W{a,b}, depending
on whether f(X) is a square in GF(q).
a. If f(X) is a square in GF(q) and Y:=sqrt(f(X)) then t is mapped
to the point P(t):=(X, Y);
b. If f(X) is not a square in GF(q) and Y':=sqrt(f(X')), then t is
mapped to the point P(t):=(X', -Y').
Formally, this mapping is not properly defined, since a nonzero
square y:=x^2 in GF(q) has two solutions, viz. x and -x; it is
properly defined, however, if one designates for each element in
GF(q) that is a square in GF(q) precisely one square root as "the"
square root of this element. Note that always picking the square
root with zero parity (see Appendix I) satisfies this condition, as
does using one of the square root functions specified in
Appendix L.1.
If -1 is not a square in GF(q), this element is mapped to the point
at infinity O of W_{a,b}.
The set of points of W_{a,b} that arises this way has size roughly
3/8 of the order of the curve and each such point arises as image of
one or two t values. Further details are out of scope.
L.3.2. Mapping to Points of Montgomery Curve
The description below assumes that the domain parameter A of the
Montgomery curve M_{A,B} is nonzero. For ease of exposition, we
define f(z):=z^3+A*z^2+z. (Note that for an affine point (u,v) of
M_{A,B} one has B*v^2=f(u).)
If t is an element of GF(q) that is not a square in GF(q) and that is
unequal to -1, then the element u:=-(1+1/t)/A is the unique solution
of the equation f(t*u)=t^3*f(u). Consequently, either u or u':=t*u
is the u-coordinate of an affine point of M{A,B}, depending on
whether f(u)/B is a square in GF(q).
a. If f(u)/B is a square in GF(q) and v:=sqrt(f(u)/B), then t is
mapped to the point P(t):=(u, v);
b. If f(u)/B is a not a square in GF(q) and v':=sqrt(f(u')/B), then
t is mapped to the point P(t):=(u', -v').
As before, formally, this mapping is not properly defined, since a
nonzero square y:=x^2 in GF(q) has two solutions, viz. x and -x; it
is properly defined, however, if one designates for each element in
GF(q) that is a square in GF(q) precisely one square root as "the"
square root of this element. Note that always picking the square
root with zero parity (see Appendix I) satisfies this condition, as
does using one of the square root functions specified in
Appendix L.1.
If -1 is not a square in GF(q), this element is mapped to the point
at infinity O of M_{A,B}.
The set of points of M_{A,B} that arises this way has size roughly
1/2 of the order of the curve and each such point arises as image of
precisely one t value. Further details are out of scope.
L.3.3. Mapping to Points of Twisted Edwards Curve
One can map elements of GF(q) that are not a square in GF(q) to
points of the twisted Edwards curve E_{a,d} via function composition,
where one uses the mapping of Appendix L.3.1 to arrive at a point of
the Weierstrass curve W_{a,b} and where one subsequently uses the
isomorphic mapping between twisted Edwards curves and Weierstrass
curves of Appendix D.3 to arrive at a point of E_{a,d}. Another
mapping is obtained by function composition, where one instead uses
the mapping of Appendix L.3.2 to arrive at a point of the Montgomery
curve M_{A,B} and where one subsequently uses the isomorphic mapping
between twisted Edwards curves and Montgomery curves of Appendix D.1
to arrive at a point of E_{a,d}. Obviously, one can use function
composition (now using the respective pre-images - if these exist) to
realize the pre-images of either mapping.
L.4. Randomized Representation of Curve Points
The mappings of Appendix L.3.1, Appendix L.3.2, and Appendix L.3.3
allow one to represent a curve point Q as a specific element of
GF(q), provided this point arises as a point in the range of the
mapping at hand. For Montgomery curves and twisted Edwards curves,
this covers roughly half of the curve points; for Weierstrass curves,
roughly 3/8 of the curve points. One can extend the mappings above,
by mapping a pair (t1, t2) of inputs to the point Q:=P2(t1,
t2):=P(t1) + P(t2). In this case, each curve point has roughly q/4
representations as a pair (t1, t2) on average. In fact, one can show
that if the input pairs are generated uniformly at random, then the
corresponding curve points follow a distribution that is also
(statistically indistinguishable from) a uniform distribution. Here,
each pair (t1, t2) deterministically yields a curve point, whereas
for each curve point Q, a randomized algorithm yields a pair (t1, t2)
of pre-images of Q, where the expected number of randomized pre-
images one has to try is small (four if one uses the mapping of
Appendix L.3.1; two if one uses the mapping of Appendix L.3.2). For
further details, see [Tibouchi].
Author's Address Author's Address
Rene Struik Rene Struik
Struik Security Consultancy Struik Security Consultancy
Email: rstruik.ext@gmail.com Email: rstruik.ext@gmail.com
 End of changes. 23 change blocks. 
32 lines changed or deleted 178 lines changed or added

This html diff was produced by rfcdiff 1.47. The latest version is available from http://tools.ietf.org/tools/rfcdiff/