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/ |