draft-ietf-lwig-curve-representations-01.txt | draft-ietf-lwig-curve-representations-02.txt | |||
---|---|---|---|---|

lwig R. Struik | lwig R. Struik | |||

Internet-Draft Struik Security Consultancy | Internet-Draft Struik Security Consultancy | |||

Intended status: Informational November 06, 2018 | Intended status: Informational March 11, 2019 | |||

Expires: May 10, 2019 | Expires: September 12, 2019 | |||

Alternative Elliptic Curve Representations | Alternative Elliptic Curve Representations | |||

draft-ietf-lwig-curve-representations-01 | draft-ietf-lwig-curve-representations-02 | |||

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 May 10, 2019. | This Internet-Draft will expire on September 12, 2019. | |||

Copyright Notice | Copyright Notice | |||

Copyright (c) 2018 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 | |||

carefully, as they describe your rights and restrictions with respect | carefully, as they describe your rights and restrictions with respect | |||

to this document. Code Components extracted from this document must | to this document. Code Components extracted from this document must | |||

include Simplified BSD License text as described in Section 4.e of | include Simplified BSD License text as described in Section 4.e of | |||

the Trust Legal Provisions and are provided without warranty as | the Trust Legal Provisions and are provided without warranty as | |||

described in the Simplified BSD License. | described in the Simplified BSD License. | |||

Table of Contents | Table of Contents | |||

1. Fostering Code Reuse with New Elliptic Curves . . . . . . . . 3 | 1. Fostering Code Reuse with New Elliptic Curves . . . . . . . . 3 | |||

2. Specification of Wei25519 . . . . . . . . . . . . . . . . . . 3 | 2. Specification of Wei25519 . . . . . . . . . . . . . . . . . . 4 | |||

3. Use of Representation Switches . . . . . . . . . . . . . . . 4 | 3. Use of Representation Switches . . . . . . . . . . . . . . . 4 | |||

4. Examples . . . . . . . . . . . . . . . . . . . . . . . . . . 5 | 4. Examples . . . . . . . . . . . . . . . . . . . . . . . . . . 5 | |||

4.1. Implementation of X25519 . . . . . . . . . . . . . . . . 5 | 4.1. Implementation of X25519 . . . . . . . . . . . . . . . . 5 | |||

4.2. Implementation of Ed25519 . . . . . . . . . . . . . . . . 5 | 4.2. Implementation of Ed25519 . . . . . . . . . . . . . . . . 6 | |||

4.3. Specification of ECDSA-SHA256-Wei25519 . . . . . . . . . 5 | 4.3. Specification of ECDSA25519 . . . . . . . . . . . . . . . 6 | |||

4.4. Other Uses . . . . . . . . . . . . . . . . . . . . . . . 6 | 4.4. Other Uses . . . . . . . . . . . . . . . . . . . . . . . 6 | |||

5. Caveats . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 | 5. Caveats . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 | |||

6. Security Considerations . . . . . . . . . . . . . . . . . . . 7 | 6. Security Considerations . . . . . . . . . . . . . . . . . . . 8 | |||

7. Privacy Considerations . . . . . . . . . . . . . . . . . . . 8 | 7. Privacy Considerations . . . . . . . . . . . . . . . . . . . 8 | |||

8. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 8 | 8. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 8 | |||

9. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . 8 | 9. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . 9 | |||

10. References . . . . . . . . . . . . . . . . . . . . . . . . . 8 | 10. References . . . . . . . . . . . . . . . . . . . . . . . . . 9 | |||

10.1. Normative References . . . . . . . . . . . . . . . . . . 8 | 10.1. Normative References . . . . . . . . . . . . . . . . . . 9 | |||

10.2. Informative References . . . . . . . . . . . . . . . . . 9 | 10.2. Informative References . . . . . . . . . . . . . . . . . 10 | |||

Appendix A. Some (non-Binary) Elliptic Curves . . . . . . . . . 10 | Appendix A. Some (non-Binary) Elliptic Curves . . . . . . . . . 10 | |||

A.1. Curves in short-Weierstrass Form . . . . . . . . . . . . 10 | A.1. Curves in short-Weierstrass Form . . . . . . . . . . . . 10 | |||

A.2. Montgomery Curves . . . . . . . . . . . . . . . . . . . . 10 | A.2. Montgomery Curves . . . . . . . . . . . . . . . . . . . . 11 | |||

A.3. Twisted Edwards Curves . . . . . . . . . . . . . . . . . 10 | A.3. Twisted Edwards Curves . . . . . . . . . . . . . . . . . 11 | |||

Appendix B. Elliptic Curve Nomenclature . . . . . . . . . . . . 11 | Appendix B. Elliptic Curve Nomenclature and Finite Fields . . . 11 | |||

Appendix C. Elliptic Curve Group Operations . . . . . . . . . . 11 | B.1. Elliptic Curve Nomenclature . . . . . . . . . . . . . . . 11 | |||

C.1. Group Law for Weierstrass Curves . . . . . . . . . . . . 11 | B.2. Finite Fields . . . . . . . . . . . . . . . . . . . . . . 13 | |||

C.2. Group Law for Montgomery Curves . . . . . . . . . . . . . 12 | Appendix C. Elliptic Curve Group Operations . . . . . . . . . . 14 | |||

C.3. Group Law for Twisted Edwards Curves . . . . . . . . . . 13 | C.1. Group Law for Weierstrass Curves . . . . . . . . . . . . 14 | |||

Appendix D. Relationship Between Curve Models . . . . . . . . . 14 | C.2. Group Law for Montgomery Curves . . . . . . . . . . . . . 15 | |||

D.1. Mapping between twisted Edwards Curves and Montgomery | C.3. Group Law for Twisted Edwards Curves . . . . . . . . . . 15 | |||

Curves . . . . . . . . . . . . . . . . . . . . . . . . . 14 | Appendix D. Relationship Between Curve Models . . . . . . . . . 16 | |||

D.2. Mapping between Montgomery Curves and Weierstrass Curves 14 | D.1. Mapping between Twisted Edwards Curves and Montgomery | |||

D.3. Mapping between twisted Edwards Curves and Weierstrass | Curves . . . . . . . . . . . . . . . . . . . . . . . . . 16 | |||

Curves . . . . . . . . . . . . . . . . . . . . . . . . . 15 | D.2. Mapping between Montgomery Curves and Weierstrass Curves 17 | |||

Appendix E. Curve25519 and Cousins . . . . . . . . . . . . . . . 15 | D.3. Mapping between Twisted Edwards Curves and Weierstrass | |||

E.1. Curve Definition and Alternative Representations . . . . 15 | Curves . . . . . . . . . . . . . . . . . . . . . . . . . 18 | |||

E.2. Switching between Alternative Representations . . . . . . 16 | Appendix E. Curve25519 and Cousins . . . . . . . . . . . . . . . 18 | |||

E.3. Domain Parameters . . . . . . . . . . . . . . . . . . . . 17 | E.1. Curve Definition and Alternative Representations . . . . 18 | |||

Appendix F. Further Mappings . . . . . . . . . . . . . . . . . . 19 | E.2. Switching between Alternative Representations . . . . . . 19 | |||

F.1. Isomorphic Mapping between Weierstrass Curves . . . . . . 19 | E.3. Domain Parameters . . . . . . . . . . . . . . . . . . . . 20 | |||

F.2. Isogenous Mapping between Weierstrass Curves . . . . . . 20 | Appendix F. Further Mappings . . . . . . . . . . . . . . . . . . 22 | |||

F.1. Isomorphic Mapping between Twisted Edwards Curves . . . . 22 | ||||

Appendix G. Further Cousins of Curve25519 . . . . . . . . . . . 21 | F.2. Isomorphic Mapping between Montgomery Curves . . . . . . 23 | |||

G.1. Further Alternative Representations . . . . . . . . . . . 21 | F.3. Isomorphic Mapping between Weierstrass Curves . . . . . . 24 | |||

G.2. Further Switching . . . . . . . . . . . . . . . . . . . . 22 | F.4. Isogenous Mapping between Weierstrass Curves . . . . . . 25 | |||

G.3. Further Domain Parameters . . . . . . . . . . . . . . . . 23 | Appendix G. Further Cousins of Curve25519 . . . . . . . . . . . 26 | |||

Appendix H. Isogeny Details . . . . . . . . . . . . . . . . . . 24 | G.1. Further Alternative Representations . . . . . . . . . . . 26 | |||

H.1. Isogeny Parameters . . . . . . . . . . . . . . . . . . . 24 | G.2. Further Switching . . . . . . . . . . . . . . . . . . . . 26 | |||

H.1.1. Coefficients of u(x) . . . . . . . . . . . . . . . . 24 | G.3. Further Domain Parameters . . . . . . . . . . . . . . . . 27 | |||

H.1.2. Coefficients of v(x) . . . . . . . . . . . . . . . . 26 | Appendix H. Isogeny Details . . . . . . . . . . . . . . . . . . 29 | |||

H.1.3. Coefficients of w(x) . . . . . . . . . . . . . . . . 29 | H.1. Isogeny Parameters . . . . . . . . . . . . . . . . . . . 29 | |||

H.2. Dual Isogeny Parameters . . . . . . . . . . . . . . . . . 30 | H.1.1. Coefficients of u(x) . . . . . . . . . . . . . . . . 29 | |||

H.2.1. Coefficients of u'(x) . . . . . . . . . . . . . . . . 30 | H.1.2. Coefficients of v(x) . . . . . . . . . . . . . . . . 31 | |||

H.2.2. Coefficients of v'(x) . . . . . . . . . . . . . . . . 32 | H.1.3. Coefficients of w(x) . . . . . . . . . . . . . . . . 34 | |||

H.2.3. Coefficients of w'(x) . . . . . . . . . . . . . . . . 35 | H.2. Dual Isogeny Parameters . . . . . . . . . . . . . . . . . 35 | |||

Author's Address . . . . . . . . . . . . . . . . . . . . . . . . 36 | H.2.1. Coefficients of u'(x) . . . . . . . . . . . . . . . . 35 | |||

H.2.2. Coefficients of v'(x) . . . . . . . . . . . . . . . . 37 | ||||

H.2.3. Coefficients of w'(x) . . . . . . . . . . . . . . . . 40 | ||||

Appendix I. Point Compression . . . . . . . . . . . . . . . . . 41 | ||||

I.1. Point Compression for Weierstrass Curves . . . . . . . . 42 | ||||

I.2. Point Compression for Montgomery Curves . . . . . . . . . 42 | ||||

I.3. Point Compression for Twisted Edwards Curves . . . . . . 43 | ||||

Appendix J. Data Conversions . . . . . . . . . . . . . . . . . . 43 | ||||

J.1. Conversion between Bit Strings and Integers . . . . . . . 43 | ||||

J.2. Conversion between Octet Strings and Integers (OS2I, | ||||

I2OS) . . . . . . . . . . . . . . . . . . . . . . . . . . 44 | ||||

J.3. Conversion between Octet Strings and Bit Strings (BS2OS, | ||||

OS2BS) . . . . . . . . . . . . . . . . . . . . . . . . . 44 | ||||

J.4. Conversion between Field Elements and Octet Strings | ||||

(FE2OS, OS2FE) . . . . . . . . . . . . . . . . . . . . . 44 | ||||

J.5. Ordering Conventions . . . . . . . . . . . . . . . . . . 45 | ||||

Appendix K. Representations for Curve25519 Family Members . . . 46 | ||||

K.1. Wei25519 . . . . . . . . . . . . . . . . . . . . . . . . 46 | ||||

Appendix L. Auxiliary Functions . . . . . . . . . . . . . . . . 46 | ||||

L.1. Square Roots in GF(q) . . . . . . . . . . . . . . . . . . 46 | ||||

L.1.1. Square Roots in GF(q), where q = 3 (mod 4) . . . . . 47 | ||||

L.1.2. Square Roots in GF(q), where q = 5 (mod 8) . . . . . 47 | ||||

L.2. Inversion . . . . . . . . . . . . . . . . . . . . . . . . 47 | ||||

Author's Address . . . . . . . . . . . . . . . . . . . . . . . . 47 | ||||

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 3, line 50 ¶ | skipping to change at page 4, line 25 ¶ | |||

elliptic curve arithmetic for curves in "short" Weierstrass form (see | elliptic curve arithmetic for curves in "short" Weierstrass form (see | |||

Appendix C.1). | Appendix C.1). | |||

2. Specification of Wei25519 | 2. Specification of Wei25519 | |||

For the specification of Wei25519 and its relationship to Curve25519 | For the specification of Wei25519 and its relationship to Curve25519 | |||

and Edwards25519, see Appendix E. For further details and background | and Edwards25519, see Appendix E. For further details and background | |||

information on elliptic curves, we refer to the other appendices. | information on elliptic curves, we refer to the other appendices. | |||

The use of Wei25519 allows reuse of existing generic code that | The use of Wei25519 allows reuse of existing generic code that | |||

implements short-Weierstrass curves, such as the NIST curve P256, to | implements short-Weierstrass curves, such as the NIST curve P-256, to | |||

also implement the CFRG curves Curve25519 and Edwards25519. We also | also implement the CFRG curves Curve25519 and Edwards25519. We also | |||

cater to reusing of existing code where some domain parameters may | cater to reusing of existing code where some domain parameters may | |||

have been hardcoded, thereby widening the scope of applicability. To | have been hardcoded, thereby widening the scope of applicability. To | |||

this end, we specify the short-Weierstrass curves Wei25519.2 and | this end, we specify the short-Weierstrass curves Wei25519.2 and | |||

Wei25519.-3, with hardcoded domain parameter a=2 and a=-3 (mod p), | Wei25519.-3, with hardcoded domain parameter a=2 and a=-3 (mod p), | |||

respectively; see Appendix G. | respectively; see Appendix G. (Here, p is the characteristic of the | |||

field over which these curves are defined.) | ||||

3. Use of Representation Switches | 3. Use of Representation Switches | |||

The curves Curve25519, Edwards25519, and Wei25519, as specified in | The curves Curve25519, Edwards25519, and Wei25519, as specified in | |||

Appendix E.3, are all isomorphic, with the transformations of | Appendix E.3, are all isomorphic, with the transformations of | |||

Appendix E.2. These transformations map the specified base point of | Appendix E.2. These transformations map the specified base point of | |||

each of these curves to the specified base point of each of the other | each of these curves to the specified base point of each of the other | |||

curves. Consequently, a public-key pair (k,R:=k*G) for any one of | curves. Consequently, a public-key pair (k,R:=k*G) for any one of | |||

these curves corresponds, via these isomorphic mappings, to the | these curves corresponds, via these isomorphic mappings, to the | |||

public-key pair (k, R':=k*G') for each of these other curves (where G | public-key pair (k, R':=k*G') for each of these other curves (where G | |||

skipping to change at page 5, line 41 ¶ | skipping to change at page 6, line 16 ¶ | |||

RFC 8032 [RFC8032] specifies Ed25519, a "full" Schnorr signature | RFC 8032 [RFC8032] specifies Ed25519, a "full" Schnorr signature | |||

scheme, with instantiation by the twisted Edwards curve Edwards25519. | scheme, with instantiation by the twisted Edwards curve Edwards25519. | |||

One can implement the computation of the ephemeral key pair for | One can implement the computation of the ephemeral key pair for | |||

Ed25519 using an existing Montgomery curve implementation by (1) | Ed25519 using an existing Montgomery curve implementation by (1) | |||

generating a public-private key pair (k, R':=k*G') for Curve25519; | generating a public-private key pair (k, R':=k*G') for Curve25519; | |||

(2) representing this public-private key as the pair (k, R:=k*G) for | (2) representing this public-private key as the pair (k, R:=k*G) for | |||

Ed25519. As before, the representation change can be implemented via | Ed25519. As before, the representation change can be implemented via | |||

a simple wrapper. Note that the Montgomery ladder specified in | a simple wrapper. Note that the Montgomery ladder specified in | |||

Section 5 of RFC7748 [RFC7748] does not provide sufficient | Section 5 of RFC7748 [RFC7748] does not provide sufficient | |||

information to reconstruct R' (since it does not compute the | information to reconstruct R':=(u, v) (since it does not compute the | |||

y-coordinate of R'). However, this deficiency can be remedied by | v-coordinate of R'). However, this deficiency can be remedied by | |||

using a slightly modified version of the Montgomery ladder that | using a slightly modified version of the Montgomery ladder that | |||

includes reconstruction of the y-coordinate of R':=k*G' at the end of | includes reconstruction of the v-coordinate of R':=k*G' at the end of | |||

hereof (which uses the v-coordinate Gv of the base point of | hereof (which uses the v-coordinate of the base point of Curve25519 | |||

Curve25519 as well). For details, see Appendix D.2. | as well). For details, see Appendix C.1. | |||

4.3. Specification of ECDSA-SHA256-Wei25519 | 4.3. Specification of ECDSA25519 | |||

FIPS Pub 186-4 [FIPS-186-4] specifies the signature scheme ECDSA and | FIPS Pub 186-4 [FIPS-186-4] specifies the signature scheme ECDSA and | |||

can be instantiated not just with the NIST prime curves, but also | can be instantiated not just with the NIST prime curves, but also | |||

with other Weierstrass curves (that satisfy additional cryptographic | with other Weierstrass curves (that satisfy additional cryptographic | |||

criteria). In particular, one can instantiate this scheme with the | criteria). In particular, one can instantiate this scheme with the | |||

Weierstrass curve Wei25519 and the hash function SHA-256, where an | Weierstrass curve Wei25519 and the hash function SHA-256, where an | |||

implementation may generate a public-private key pair for Wei25519 by | implementation may generate a public-private key pair for Wei25519 by | |||

(1) internally carrying out these computations on the Montgomery | (1) internally carrying out these computations on the Montgomery | |||

curve Curve25519, the twisted Edwards curve Edwards25519, or even the | curve Curve25519, the twisted Edwards curve Edwards25519, or even the | |||

Weierstrass curve Wei25519.-3 (with hardcoded a=-3 domain parameter); | Weierstrass curve Wei25519.-3 (with hardcoded a=-3 domain parameter); | |||

(2) representing the result as a key pair for the curve Wei25519. | (2) representing the result as a key pair for the curve Wei25519. | |||

Note that, in either case, one can implement these schemes with the | Note that, in either case, one can implement these schemes with the | |||

same representation conventions as used with existing NIST | same representation conventions as used with existing NIST | |||

specifications, including bit/byte-ordering, compression functions, | specifications, including bit/byte-ordering, compression functions, | |||

and the-like. This allows implementations of ECDSA with the hash | and the-like. This allows generic implementations of ECDSA with the | |||

function SHA-256 and with the NIST curve P-256 or with the curve | hash function SHA-256 and with the NIST curve P-256 or with the curve | |||

Wei25519 specified in this draft to use the same implementation | Wei25519 specified in this draft to use the same implementation | |||

(instantiated with, respectively, the NIST P-256 elliptic curve | (instantiated with, respectively, the NIST P-256 elliptic curve | |||

domain parameters or with the domain parameters of curve Wei25519 | domain parameters or with the domain parameters of curve Wei25519 | |||

specified in Appendix E). | specified in Appendix E). | |||

4.4. Other Uses | 4.4. Other Uses | |||

Any existing specification of cryptographic schemes using elliptic | Any existing specification of cryptographic schemes using elliptic | |||

curves in Weierstrass form and that allows introduction of a new | curves in Weierstrass form and that allows introduction of a new | |||

elliptic curve (here: Wei25519) is amenable to similar constructs, | elliptic curve (here: Wei25519) is amenable to similar constructs, | |||

skipping to change at page 6, line 40 ¶ | skipping to change at page 7, line 15 ¶ | |||

Montgomery curve and twisted Edwards curve cousins hereof (where | Montgomery curve and twisted Edwards curve cousins hereof (where | |||

these exist). This would simply require definition of a new object | these exist). This would simply require definition of a new object | |||

identifier for any such envisioned "offspring" protocol. This could | identifier for any such envisioned "offspring" protocol. This could | |||

significantly simplify standardization of schemes and help keeping | significantly simplify standardization of schemes and help keeping | |||

the resource and maintenance cost of implementations supporting | the resource and maintenance cost of implementations supporting | |||

algorithm agility [RFC7696] at bay. | algorithm agility [RFC7696] at bay. | |||

5. Caveats | 5. Caveats | |||

The examples above illustrate how specifying the Weierstrass curve | The examples above illustrate how specifying the Weierstrass curve | |||

Wei25519 may facilitate reuse of existing code and may simplify | Wei25519 (or any curve in short-Weierstrass format, for that matter) | |||

standards development. However, the following caveats apply: | may facilitate reuse of existing code and may simplify standards | |||

development. However, the following caveats apply: | ||||

1. Unfriendly wire formats. The transformations between alternative | 1. Wire format. The transformations between alternative curve | |||

curve representations can be implemented at negligible relative | representations can be implemented at negligible relative | |||

incremental cost if the curve points are represented as affine | incremental cost if the curve points are represented as affine | |||

points. If a point is represented in compressed format, | points. If a point is represented in compressed format, | |||

conversion usually requires a costly point decompression step. | conversion usually requires a costly point decompression step. | |||

This is the case in [RFC7748], where the inputs to the co-factor | This is the case in [RFC7748], where the inputs to the co-factor | |||

Diffie-Hellman scheme X25519, as well as its output, are | Diffie-Hellman scheme X25519, as well as its output, are | |||

represented in x-coordinate-only format; | represented in u-coordinate-only format. This is also the case | |||

in [RFC8032], where the EdDSA signature includes the ephemeral | ||||

signing key represented in compressed format (see Appendix I for | ||||

details); | ||||

2. Unfriendly representation conventions. While elliptic curve | 2. Representation conventions. While elliptic curve computations | |||

computations are carried-out in a field GF(q) and, thereby, | are carried-out in a field GF(q) and, thereby, involve large | |||

involve large integer arithmetic, these integers are represented | integer arithmetic, these integers are represented as bit- and | |||

as bit- and byte-strings. Here, [RFC8032] uses least- | byte-strings. Here, [RFC8032] uses least-significant-byte | |||

significant-byte (LSB)/least-significant-bit (lsb) conventions, | (LSB)/least-significant-bit (lsb) conventions, whereas [RFC7748] | |||

whereas [RFC7748] uses LSB/most-significant-bit (msb) | uses LSB/most-significant-bit (msb) conventions, and where most | |||

conventions, and where most other cryptographic specifications, | other cryptographic specifications, including NIST SP800-56a | |||

including NIST SP800-56a [SP-800-56a], FIPS Pub 186-4 | [SP-800-56a], FIPS Pub 186-4 [FIPS-186-4], and ANSI X9.62-2005 | |||

[FIPS-186-4], and ANSI X9.62-2005 [ANSI-X9.62] use MSB/msb | [ANSI-X9.62] use MSB/msb conventions. Since each pair of | |||

conventions. Since each pair of conventions is different, this | conventions is different (see Appendix J for details), this does | |||

does necessitate bit/byte representation conversions; | necessitate bit/byte representation conversions; | |||

3. Unfriendly domain parameters. All traditional NIST curves are | 3. Domain parameters. All traditional NIST curves are Weierstrass | |||

Weierstrass curve with domain parameter a=-3, while all Brainpool | curves with domain parameter a=-3, while all Brainpool curves | |||

curves [RFC5639] are isomorphic to a Weierstrass curve of this | [RFC5639] are isomorphic to a Weierstrass curve of this form. | |||

form. Thus, one can expect there to be existing Weierstrass | Thus, one can expect there to be existing Weierstrass | |||

implementations with a hardcoded a=-3 domain parameter | implementations with a hardcoded a=-3 domain parameter | |||

("Jacobian-friendly"). For those implementations, including the | ("Jacobian-friendly"). For those implementations, including the | |||

curve Wei25519 as a potential vehicle for offering support for | curve Wei25519 as a potential vehicle for offering support for | |||

the CFRG curves Curve25519 and Edwards25519 is not possible, | the CFRG curves Curve25519 and Edwards25519 is not possible, | |||

since not of the required form. Instead, one has to implement | since not of the required form. Instead, one has to implement | |||

Curve25519.-3 and include code that implements the isogeny and | Wei25519.-3 and include code that implements the isogeny and dual | |||

dual isogeny from and to Wei25519. This isogeny has degree l=47 | isogeny from and to Wei25519. This isogeny has degree l=47 and | |||

and requires roughly 9kB of storage for isogeny and dual-isogeny | requires roughly 9kB of storage for isogeny and dual-isogeny | |||

computations (see the tables in Appendix H). Note that storage | computations (see the tables in Appendix H). Note that storage | |||

would have reduced to a single 32-bye table if the curve would | would have reduced to a single 64-byte table if only the curve | |||

have been generated so as to be isomorphic to a Weierstrass curve | would have been generated so as to be isomorphic to a Weierstrass | |||

with hardcoded a=-3 parameter (this corresponds to l=1). Note: | curve with hardcoded a=-3 parameter (this corresponds to l=1). | |||

an example of such a curve is the Montgomery curve M_{A,B} over | Note: an example of such a curve is the Montgomery curve M_{A,B} | |||

GF(p) with p=2^255-19, A=-1410290, and B=1 or (if one wants the | over GF(p) with p=2^255-19, B=1, and A=-1410290 or (if one wants | |||

base point to still have u-coordinate u=9) A=-3960846. In either | the base point to still have u-coordinate u=9) A=-3960846. In | |||

case, the resulting curve has the same cryptographic properties | either case, the resulting curve has the same cryptographic | |||

as Curve25519, while being more "Jacobian-friendly". | properties as Curve25519 and the same performance (since A is a | |||

3-byte integer as is the case with the domain parameter A=486662 | ||||

used with Curve25519), while being "Jacobian-friendly" by design. | ||||

6. Security Considerations | 6. Security Considerations | |||

The different representations of elliptic curve points discussed in | The different representations of elliptic curve points discussed in | |||

this document are all obtained using a publicly known transformation, | this document are all obtained using a publicly known transformation, | |||

which is either an isomorphism or a low-degree isogeny. It is well- | which is either an isomorphism or a low-degree isogeny. It is well- | |||

known that an isomorphism maps elliptic curve points to equivalent | known that an isomorphism maps elliptic curve points to equivalent | |||

mathematical objects and that the complexity of cryptographic | mathematical objects and that the complexity of cryptographic | |||

problems (such as the discrete logarithm problem) of curves related | problems (such as the discrete logarithm problem) of curves related | |||

via a low-degree isogeny are tightly related. Thus, the use of these | via a low-degree isogeny are tightly related. Thus, the use of these | |||

skipping to change at page 8, line 19 ¶ | skipping to change at page 8, line 48 ¶ | |||

for over 15 years. | for over 15 years. | |||

7. Privacy Considerations | 7. Privacy Considerations | |||

The transformations between different curve models described in this | The transformations between different curve models described in this | |||

document are publicly known and, therefore, do not affect privacy | document are publicly known and, therefore, do not affect privacy | |||

provisions. | provisions. | |||

8. IANA Considerations | 8. IANA Considerations | |||

There is *currently* no IANA action required for this document. New | An object identifier is requested for Wei25519 and ECDSA25519, using | |||

object identifiers would be required in case one wishes to specify | the representation conventions in this document. | |||

one or more of the "offspring" protocols exemplified in Section 4. | ||||

9. Acknowledgements | 9. Acknowledgements | |||

Thanks to Nikolas Rosener for discussions surrounding implementation | Thanks to Nikolas Rosener for discussions surrounding implementation | |||

details of the techniques described in this document and to Phillip | details of the techniques described in this document and to Phillip | |||

Hallam-Baker for triggering inclusion of verbiage on the use of | Hallam-Baker for triggering inclusion of verbiage on the use of | |||

Montgomery ladders with recovery of the y-coordinate. | Montgomery ladders with recovery of the y-coordinate. Thanks to | |||

Stanislav Smyshlyaev for his careful review. | ||||

10. References | 10. References | |||

10.1. Normative References | 10.1. Normative References | |||

[ANSI-X9.62] | [ANSI-X9.62] | |||

ANSI X9.62-2005, "Public Key Cryptography for the | ANSI X9.62-2005, "Public Key Cryptography for the | |||

Financial Services Industry: The Elliptic Curve Digital | Financial Services Industry: The Elliptic Curve Digital | |||

Signature Algorithm (ECDSA)", American National Standard | Signature Algorithm (ECDSA)", American National Standard | |||

for Financial Services, Accredited Standards Committee X9, | for Financial Services, Accredited Standards Committee X9, | |||

skipping to change at page 10, line 5 ¶ | skipping to change at page 10, line 31 ¶ | |||

2003. | 2003. | |||

[GECC] D. Hankerson, A.J. Menezes, S.A. Vanstone, "Guide to | [GECC] D. Hankerson, A.J. Menezes, S.A. Vanstone, "Guide to | |||

Elliptic Curve Cryptography", New York: Springer-Verlag, | Elliptic Curve Cryptography", New York: Springer-Verlag, | |||

2004. | 2004. | |||

[HW-ECC] W.P. Liu, "How to Use the Kinets LTC ECC HW to Accelerate | [HW-ECC] W.P. Liu, "How to Use the Kinets LTC ECC HW to Accelerate | |||

Curve25519 (version 7)", NXP, | Curve25519 (version 7)", NXP, | |||

https://community.nxp.com/docs/DOC-330199, April 2017. | https://community.nxp.com/docs/DOC-330199, April 2017. | |||

[Ladder] P.L. Montgomery, "Speeding the Pollard and Elliptic Curve | ||||

Methods of Factorization", Mathematics of | ||||

Computation, Vol. 48, 1987. | ||||

[tEd-Formulas] | ||||

H. Hisil, K.K.H. Wong, G. Carter, E. Dawson, "Twisted | ||||

Edwards Curves Revisited", ASIACRYPT 2008, Lecture Notes | ||||

in Computer Science, Vol. 5350, New York: Springer-Verlag, | ||||

2008. | ||||

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

Let GF(q) denote the finite field with q elements, where q is an odd | Let GF(q) denote the finite field with q elements, where q is an odd | |||

prime power and where q is not divisible by three. Let W_{a,b} be | prime power and where q is not divisible by three. Let W_{a,b} be | |||

the Weierstrass curve with defining equation y^2 = x^3 + a*x + b, | the Weierstrass curve with defining equation Y^2 = X^3 + a*X + b, | |||

where a and b are elements of GF(q) and where 4*a^3 + 27*b^2 is | where a and b are elements of GF(q) and where 4*a^3 + 27*b^2 is | |||

nonzero. The points of W_{a,b} are the ordered pairs (x, y) whose | nonzero. The points of W_{a,b} are the ordered pairs (X, Y) whose | |||

coordinates are elements of GF(q) and that satisfy the defining | coordinates are elements of GF(q) and that satisfy the defining | |||

equation (the so-called affine points), together with the special | equation (the so-called affine points), together with the special | |||

point O (the so-called "point at infinity").This set forms a group | point O (the so-called "point at infinity"). This set forms a group | |||

under addition, via the so-called "secant-and-tangent" rule, where | under addition, via the so-called "secant-and-tangent" rule, where | |||

the point at infinity serves as the identity element. See | the point at infinity serves as the identity element. See | |||

Appendix C.1 for details of the group operation. | Appendix C.1 for details of the group operation. | |||

A.2. Montgomery Curves | A.2. Montgomery Curves | |||

Let GF(q) denote the finite field with q elements, where q is an odd | Let GF(q) denote the finite field with q elements, where q is an odd | |||

prime power. Let M_{A,B} be the Montgomery curve with defining | prime power. Let M_{A,B} be the Montgomery curve with defining | |||

equation B*v^2 = u^3 + A*u^2 + u, where A and B are elements of GF(q) | equation B*v^2 = u^3 + A*u^2 + u, where A and B are elements of GF(q) | |||

with A unequal to (+/-)2 and with B nonzero. The points of M_{A,B} | and where A is unequal to (+/-)2 and where B is nonzero. The points | |||

are the ordered pairs (u, v) whose coordinates are elements of GF(q) | of M_{A,B} are the ordered pairs (u, v) whose coordinates are | |||

and that satisfy the defining equation (the so-called affine points), | elements of GF(q) and that satisfy the defining equation (the so- | |||

together with the special point O (the so-called "point at | called affine points), together with the special point O (the so- | |||

infinity").This set forms a group under addition, via the so-called | called "point at infinity"). This set forms a group under addition, | |||

"secant-and-tangent" rule, where the point at infinity serves as the | via the so-called "secant-and-tangent" rule, where the point at | |||

identity element. See Appendix C.2 for details of the group | infinity serves as the identity element. See Appendix C.2 for | |||

operation. | details of the group operation. | |||

A.3. Twisted Edwards Curves | A.3. Twisted Edwards Curves | |||

Let GF(q) denote the finite field with q elements, where q is an odd | Let GF(q) denote the finite field with q elements, where q is an odd | |||

prime power. Let E_{a,d} be the twisted Edwards curve with defining | prime power. Let E_{a,d} be the twisted Edwards curve with defining | |||

equation a*x^2 + y^2 = 1+ d*x^2*y^2, where a and d are distinct | equation a*x^2 + y^2 = 1+ d*x^2*y^2, where a and d are distinct | |||

nonzero elements of GF(q). The points of E_{a,d} are the ordered | nonzero elements of GF(q). The points of E_{a,d} are the ordered | |||

pairs (x, y) whose coordinates are elements of GF(q) and that satisfy | pairs (x, y) whose coordinates are elements of GF(q) and that satisfy | |||

the defining equation (the so-called affine points). It can be shown | the defining equation (the so-called affine points). It can be shown | |||

that this set forms a group under addition if a is a square in GF(q), | that this set forms a group under addition if a is a square in GF(q), | |||

whereas d is not, where the point (0, 1) serves as the identity | whereas d is not, where the point O:=(0, 1) serves as the identity | |||

element. (Note that the identity element satisfies the defining | element. (Note that the identity element satisfies the defining | |||

equation.) See Appendix C.3 for details of the group operation. | equation.) See Appendix C.3 for details of the group operation. | |||

An Edwards curve is a twisted Edwards curve with a=1. | An Edwards curve is a twisted Edwards curve with a=1. | |||

Appendix B. Elliptic Curve Nomenclature | Appendix B. Elliptic Curve Nomenclature and Finite Fields | |||

B.1. Elliptic Curve Nomenclature | ||||

Each curve defined in Appendix A forms a commutative group under | Each curve defined in Appendix A forms a commutative group under | |||

addition. In Appendix C we specify the group laws, which depend on | addition (denoted by '+'). In Appendix C we specify the group laws, | |||

the curve model in question. For completeness, we here include some | which depend on the curve model in question. For completeness, we | |||

common elliptic curve nomenclature and basic properties (primarily so | here include some common elliptic curve nomenclature and basic | |||

as to keep this document self-contained). These notions are mainly | properties (primarily so as to keep this document self-contained). | |||

used in Appendix E and Appendix G and not essential for our | These notions are mainly used in Appendix E and Appendix G and not | |||

exposition. This section can be skipped at first reading. | essential for our exposition. This section can be skipped at first | |||

reading. | ||||

Any point P of a curve is a generator of the cyclic subgroup | Any point P of a curve E is a generator of the cyclic subgroup | |||

(P):={k*P | k = 0, 1, 2,...} of the curve. If (P) has cardinality l, | (P):={k*P | k = 0, 1, 2,...} of the curve. (Here, k*P denotes the | |||

then l is called the order of P. The order of a curve is the | sum of k copies of P, where 0*P is the identity element O of the | |||

cardinality of the set of its points. A curve is cyclic if it is | curve.) If (P) has cardinality l, then l is called the order of P. | |||

generated by some point of this curve. All curves of prime order are | The order of curve E is the cardinality of the set of its points, | |||

cyclic, while all curves of order |E| = h*n, where n is a large prime | commonly denoted by |E|. A curve is cyclic if it is generated by some | |||

number and where h is a small number (the so-called co-factor), have | point of this curve. All curves of prime order are cyclic, while all | |||

a large cyclic subgroup of prime order n. In this case, a generator | curves of order h*n, where n is a large prime number and where h is a | |||

of order n is called a base point, commonly denoted by G. A point of | small number (the so-called co-factor), have a large cyclic subgroup | |||

order dividing h is said to be in the small subgroup. For curves of | of prime order n. In this case, a generator of order n is called a | |||

prime order, this small subgroup is the singleton set, consisting of | base point, commonly denoted by G. A point of order dividing h is | |||

only the identity element. | said to be in the small subgroup. For curves of prime order, this | |||

small subgroup is the singleton set, consisting of only the identity | ||||

element O. If a point is not in the small subgroup, it has order at | ||||

least n. | ||||

If R is a point on a curve E that is also contained in (P), there is | If R is a point of the curve that is also contained in (P), there is | |||

a unique integer k in the interval [0, l-1] so that R=kP, where l is | a unique integer k in the interval [0, l-1] so that R=k*P, where l is | |||

the order of P. This number is called the discrete logarithm of R to | the order of P. This number is called the discrete logarithm of R to | |||

the base P. The discrete logarithm problem is the problem of finding | the base P. The discrete logarithm problem is the problem of finding | |||

the discrete logarithm of R to the base P for any two points P and R | the discrete logarithm of R to the base P for any two points P and R | |||

of the curve, if such a number exists. | of the curve, if such a number exists. | |||

A public-private key pair is an ordered pair (k, R:=kG), where G is a | If P is a fixed base point G of the curve, the pair (k, R:=k*G) is | |||

fixed base point of the curve. Here, k (the private key) is an | called a public-private key pair, the integer k the private key, and | |||

integer in the interval [0,n-1], where G has order n. | the point R the corresponding public key. The private key k can be | |||

represented as an integer in the interval [0,n-1], where G has order | ||||

n. | ||||

A quadratic twist of a curve E defined over a field GF(q) is a curve | In this document, a quadratic twist of a curve E defined over a field | |||

E' related to E, with cardinality |E|+|E'|=2*(q+1). If E is a curve | GF(q) is a curve E' related to E, with cardinality |E'|, | |||

in one of the curve models specified in this document, a quadratic | where |E|+|E'|=2*(q+1). If E is a curve in one of the curve models | |||

twist of this curve can be expressed using the same curve model, | specified in this document, a quadratic twist of this curve can be | |||

although (naturally) with different curve parameters. | expressed using the same curve model, although (naturally) with its | |||

own curve parameters. Two curves E and E' defined over a field GF(q) | ||||

are said to be isogenous if these have the same order and are said to | ||||

be isomorphic if these have the same group structure. Note that | ||||

isomorphic curves have necessarily the same order and are, thus, a | ||||

special type of isogenous curves. Further details are out of scope. | ||||

Weierstrass curves can have prime order, whereas Montgomery curves | ||||

and twisted Edwards curves always have an order that is a multiple of | ||||

four (and, thereby, a small subgroup of cardinality four). | ||||

An ordered pair (x, y) whose coordinates are elements of GF(q) can be | ||||

associated with any ordered triple of the form [x*z: y*z: z], where z | ||||

is a nonzero element of GF(q), and can be uniquely recovered from | ||||

such a representation. The latter representation is commonly called | ||||

a representation in projective coordinates. | ||||

The group laws in Appendix C are mostly expressed in terms of affine | ||||

points, but can also be expressed in terms of the representation of | ||||

these points in projective coordinates, thereby allowing clearing of | ||||

denominators. The group laws may also involve non-affine points | ||||

(such as the point at infinity O of a Weierstrass curve or of a | ||||

Montgomery curve). Those can also be represented in projective | ||||

coordinates. Further details are out of scope. | ||||

B.2. Finite Fields | ||||

The field GF(q), where q is an odd prime power, is defined as | ||||

follows. | ||||

If p is a prime number, the field GF(p) consists of the integers in | ||||

the interval [0,p-1] and two binary operations on this set: addition | ||||

and multiplication modulo p. | ||||

If q=p^m and m>0, the field GF(q) is defined in terms of an | ||||

irreducible polynomial f(z) in z of degree m with coefficients in | ||||

GF(p) (i.e., f(z) cannot be written as the product of two polynomials | ||||

in z of lower degree with coefficients in GF(p)): in this case, GF(q) | ||||

consists of the polynomials in z of degree smaller than m with | ||||

coefficients in GF(p) and two binary operations on this set: | ||||

polynomial addition and polynomial multiplication modulo the | ||||

irreducible polynomial f(z). By definition, each element x of GF(q) | ||||

is a polynomial in z of degree smaller than m and can, therefore, be | ||||

uniquely represented as a vector (x_{m-1}, x_{m-2}, ..., x_1, x_0) of | ||||

length m with coefficients in GF(p), where x_i is the coefficient of | ||||

z^i of polynomial x. Note that this representation depends on the | ||||

irreducible polynomial f(z) of the field GF(p^m) in question (which | ||||

is often fixed in practice). Note that GF(q) contains the prime | ||||

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

called a (nontrivial) extension field over GF(p). The number p is | ||||

called the characteristic of GF(q). | ||||

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

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

computing square roots and inverses in GF(q) - if these exist - see | ||||

Appendix L.1 and Appendix L.2, respectively. | ||||

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

integer arithmetic. Strictly speaking we could, therefore, have | ||||

refrained from introducing extension fields. Nevertheless, we | ||||

included the more general exposition, so as to accommodate potential | ||||

introduction of new curves that are defined over a (nontrivial) | ||||

extension field at some point in the future. This includes curves | ||||

proposed for post-quantum isogeny-based schemes, which are defined | ||||

over a quadratic extension field (i.e., where q:=p^2), and elliptic | ||||

curves used with pairing-based cryptography. The exposition in | ||||

either case is almost the same and now automatically yields, e.g., | ||||

data conversion routines for any finite field object (see | ||||

Appendix J). Readers not interested in this, could simply view all | ||||

fields as prime fields. | ||||

Appendix C. Elliptic Curve Group Operations | Appendix C. Elliptic Curve Group Operations | |||

C.1. Group Law for Weierstrass Curves | C.1. Group Law for Weierstrass Curves | |||

For each point P of the Weierstrass curve W_{a,b}, the point at | For each point P of the Weierstrass curve W_{a,b}, the point at | |||

infinity O serves as identity element, i.e., P + O = O + P = P. | infinity O serves as identity element, i.e., P + O = O + P = P. | |||

For each affine point P:=(x, y) of the Weierstrass curve W_{a,b}, the | For each affine point P:=(X, Y) of the Weierstrass curve W_{a,b}, the | |||

point -P is the point (x, -y) and one has P + (-P) = O. | point -P is the point (X, -Y) and one has P + (-P) = O. | |||

Let P1:=(x1, y1) and P2:=(x2, y2) be distinct affine points of the | Let P1:=(X1, Y1) and P2:=(X2, Y2) be distinct affine points of the | |||

Weierstrass curve W_{a,b} and let Q:=P1 + P2, where Q is not the | Weierstrass curve W_{a,b} and let Q:=P1 + P2, where Q is not the | |||

identity element. Then Q:=(x, y), where | identity element. Then Q:=(x, y), where | |||

x + x1 + x2 = lambda^2 and y + y1 = lambda*(x1 - x), where lambda | X + X1 + X2 = lambda^2 and Y + Y1 = lambda*(X1 - X), where | |||

= (y2 - y1)/(x2 - x1). | ||||

Let P:= (x1, y1) be an affine point of the Weierstrass curve W_{a,b} | lambda:= (Y2 - Y1)/(X2 - X1). | |||

and let Q:=2*P, where Q is not the identity element. Then Q:= (x, | ||||

y), where | ||||

x + 2*x1 = lambda^2 and y + y1 = lambda*(x1 - x), where | Let P:=(X1, Y1) be an affine point of the Weierstrass curve W_{a,b} | |||

lambda=(3*x1^2 + a)/(2*y1). | and let Q:=2*P, where Q is not the identity element. Then Q:=(X, Y), | |||

where | ||||

From the group law above it follows that if P=(x, y), P1=k*P=(x1, | X + 2*X1 = lambda^2 and Y + Y1 = lambda*(X1 - X), where | |||

y1), and P2=(k+1)*P=(x2, y2) are affine points of the Weierstrass | ||||

curve W_{a,b} and if y is nonzero, then the y-coordinate of P1 can be | ||||

expressed in terms of the x-coordinates of P, P1, and P2, and the | ||||

y-coordinate of P, as | ||||

y1=((x*x1+a)*(x+x1)+2*b-x2*(x-x1)^2)/(2*y). | lambda:=(3*X1^2 + a)/(2*Y1). | |||

This property allows recovery of the y-coordinate of a point P1=k*P | From the group laws above it follows that if P=(X, Y), P1=k*P=(X1, | |||

Y1), and P2=(k+1)*P=(X2, Y2) are distinct affine points of the | ||||

Weierstrass curve W_{a,b} and if Y is nonzero, then the Y-coordinate | ||||

of P1 can be expressed in terms of the X-coordinates of P, P1, and | ||||

P2, and the Y-coordinate of P, as | ||||

Y1=((X*X1+a)*(X+X1)+2*b-X2*(X-X1)^2)/(2*Y). | ||||

This property allows recovery of the Y-coordinate of a point P1=k*P | ||||

that is computed via the so-called Montgomery ladder, where P is an | that is computed via the so-called Montgomery ladder, where P is an | |||

affine point with nonzero y-coordinate. Further details are out of | affine point with nonzero Y-coordinate (i.e., it does not have order | |||

scope. | two). Further details are out of scope. | |||

C.2. Group Law for Montgomery Curves | C.2. Group Law for Montgomery Curves | |||

For each point P of the Montgomery curve M_{A,B}, the point at | For each point P of the Montgomery curve M_{A,B}, the point at | |||

infinity O serves as identity element, i.e., P + O = O + P = P. | infinity O serves as identity element, i.e., P + O = O + P = P. | |||

For each affine point P:=(x, y) of the Montgomery curve M_{A,B}, the | For each affine point P:=(u, v) of the Montgomery curve M_{A,B}, the | |||

point -P is the point (x, -y) and one has P + (-P) = O. | point -P is the point (u, -v) and one has P + (-P) = O. | |||

Let P1:=(x1, y1) and P2:=(x2, y2) be distinct affine points of the | Let P1:=(u1, v1) and P2:=(u2, v2) be distinct affine points of the | |||

Montgomery curve M_{A,B} and let Q:=P1 + P2, where Q is not the | Montgomery curve M_{A,B} and let Q:=P1 + P2, where Q is not the | |||

identity element. Then Q:=(x, y), where | identity element. Then Q:=(u, v), where | |||

x + x1 + x2 = B*lambda^2 - A and y + y1 = lambda*(x1 - x), where | u + u1 + u2 = B*lambda^2 - A and v + v1 = lambda*(u1 - u), where | |||

lambda=(y2 - y1)/(x2 - x1). | ||||

Let P:= (x1, y1) be an affine point of the Montgomery curve M_{A,B} | lambda:=(v2 - v1)/(u2 - u1). | |||

and let Q:=2*P, where Q is not the identity element. Then Q:= (x, | ||||

y), where | ||||

x + 2*x1 = B*lambda^2 - A and y + y1 = lambda*(x1 - x), where | ||||

lambda=(3*x1^2 + 2*A*x1+1)/(2*B*y1). | ||||

From the group law above it follows that if P=(x, y), P1=k*P=(x1, | Let P:=(u1, v1) be an affine point of the Montgomery curve M_{A,B} | |||

y1), and P2=(k+1)*P=(x2, y2) are affine points of the Montgomery | and let Q:=2*P, where Q is not the identity element. Then Q:=(u, v), | |||

curve M_{A,B} and if y is nonzero, then the y-coordinate of P1 can be | where | |||

expressed in terms of the x-coordinates of P, P1, and P2, and the | ||||

y-coordinate of P, as | ||||

y1=((x*x1+1)*(x+x1+2*A)-2*A-x2*(x-x1)^2)/(2*B*y). | u + 2*u1 = B*lambda^2 - A and v + v1 = lambda*(u1 - u), where | |||

This property allows recovery of the y-coordinate of a point P1=k*P | lambda:=(3*u1^2 + 2*A*u1+1)/(2*B*v1). | |||

From the group laws above it follows that if P=(u, v), P1=k*P=(u1, | ||||

v1), and P2=(k+1)*P=(u2, v2) are distinct affine points of the | ||||

Montgomery curve M_{A,B} and if v is nonzero, then the v-coordinate | ||||

of P1 can be expressed in terms of the u-coordinates of P, P1, and | ||||

P2, and the v-coordinate of P, as | ||||

v1=((u*u1+1)*(u+u1+2*A)-2*A-u2*(u-u1)^2)/(2*B*v). | ||||

This property allows recovery of the v-coordinate of a point P1=k*P | ||||

that is computed via the so-called Montgomery ladder, where P is an | that is computed via the so-called Montgomery ladder, where P is an | |||

affine point with nonzero y-coordinate. Further details are out of | affine point with nonzero v-coordinate (i.e., it does not have order | |||

scope. | one or two). Further details are out of scope. | |||

C.3. Group Law for Twisted Edwards Curves | C.3. Group Law for Twisted Edwards Curves | |||

Note: The group laws below hold for twisted Edwards curves E_{a,d} | Note: The group laws below hold for twisted Edwards curves E_{a,d} | |||

where a is a square in GF(q), whereas d is not. In this case, the | where a is a square in GF(q), whereas d is not. In this case, the | |||

addition formulae below are defined for each pair of points, without | addition formulae below are defined for each pair of points, without | |||

exceptions. Generalizations of this group law to other twisted | exceptions. Generalizations of this group law to other twisted | |||

Edwards curves are out of scope. | Edwards curves are out of scope. | |||

For each point P of the twisted Edwards curve E_{a,d}, the point | For each point P of the twisted Edwards curve E_{a,d}, the point | |||

O=(0,1) serves as identity element, i.e., P + O = O + P = P. | O:=(0,1) serves as identity element, i.e., P + O = O + P = P. | |||

For each point P:=(x, y) of the twisted Edwards curve E_{a,d}, the | For each point P:=(x, y) of the twisted Edwards curve E_{a,d}, the | |||

point -P is the point (-x, y) and one has P + (-P) = O. | point -P is the point (-x, y) and one has P + (-P) = O. | |||

Let P1:=(x1, y1) and P2:=(x2, y2) be points of the twisted Edwards | Let P1:=(x1, y1) and P2:=(x2, y2) be points of the twisted Edwards | |||

curve E_{a,d} and let Q:=P1 + P2. Then Q:=(x, y), where | curve E_{a,d} and let Q:=P1 + P2. Then Q:=(x, y), where | |||

x = (x1*y2 + x2*y1)/(1 + d*x1*x2*y1*y2) and y = (y1*y2 - | x = (x1*y2 + x2*y1)/(1 + d*x1*x2*y1*y2) and | |||

a*x1*x2)/(1 - d*x1*x2*y1*y2). | ||||

y = (y1*y2 - a*x1*x2)/(1 - d*x1*x2*y1*y2). | ||||

Let P:=(x1, y1) be a point of the twisted Edwards curve E_{a,d} and | Let P:=(x1, y1) be a point of the twisted Edwards curve E_{a,d} and | |||

let Q:=2*P. Then Q:=(x, y), where | let Q:=2*P. Then Q:=(x, y), where | |||

x = (2*x1*y1)/(1 + d*x1^2*y1^2) and y = (y1^2 - a*x1^2)/(1 - | x = (2*x1*y1)/(1 + d*x1^2*y1^2) and | |||

d*x1^2*y1^2). | ||||

Note that one can use the formulae for point addition for | y = (y1^2 - a*x1^2)/(1 - d*x1^2*y1^2). | |||

implementing point doubling, taking inverses and adding the identity | ||||

element as well (i.e., the point addition formulae are uniform and | Note that one can use the formulae for point addition for point | |||

complete (subject to our Note above)). | doubling, taking inverses, and adding the identity element as well | |||

(i.e., the point addition formulae are uniform and complete (subject | ||||

to our Note above)). | ||||

From the group laws above (subject to our Note above) it follows that | ||||

if P=(x, y), P1=k*P=(x1, y1), and P2=(k+1)*P=(x2, y2) are affine | ||||

points of the twisted Edwards curve E_{a,d} and if x is nonzero, then | ||||

the x-coordinate of P1 can be expressed in terms of the y-coordinates | ||||

of P, P1, and P2, and the x-coordinate of P, as | ||||

x1=(y*y1-y2)/(x*(a-d*y*y1*y2)). | ||||

This property allows recovery of the x-coordinate of a point P1=k*P | ||||

that is computed via the so-called Montgomery ladder, where P is an | ||||

affine point with nonzero x-coordinate (i.e., it does not have order | ||||

one or two). Further details are out of scope. | ||||

Appendix D. Relationship Between Curve Models | Appendix D. Relationship Between Curve Models | |||

The non-binary curves specified in Appendix A are expressed in | The non-binary curves specified in Appendix A are expressed in | |||

different curve models, viz. as curves in short-Weierstrass form, as | different curve models, viz. as curves in short-Weierstrass form, as | |||

Montgomery curves, or as twisted Edwards curves. These curve models | Montgomery curves, or as twisted Edwards curves. These curve models | |||

are related, as follows. | are related, as follows. | |||

D.1. Mapping between twisted Edwards Curves and Montgomery Curves | D.1. Mapping between Twisted Edwards Curves and Montgomery Curves | |||

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

twisted Edwards curve E_{a,d}, where a:=(A+2)/B and d:=(A-2)/B and, | twisted Edwards curve E_{a,d}, where a:=(A+2)/B and d:=(A-2)/B and, | |||

conversely, map points of the twisted Edwards curve E_{a,d} to points | conversely, map points of the twisted Edwards curve E_{a,d} to points | |||

of the Montgomery curve M_{A,B}, where A:=2(a+d)/(a-d) and where | of the Montgomery curve M_{A,B}, where A:=2(a+d)/(a-d) and where | |||

B:=4/(a-d). For twisted Edwards curves we consider (i.e., those | B:=4/(a-d). For twisted Edwards curves we consider (i.e., those | |||

where a is a square in GF(q), whereas d is not), this defines a one- | where a is a square in GF(q), whereas d is not), this defines a one- | |||

to-one correspondence, which - in fact - is an isomorphism between | to-one correspondence, which - in fact - is an isomorphism between | |||

M_{A,B} and E_{a,d}, thereby showing that, e.g., the discrete | M_{A,B} and E_{a,d}, thereby showing that, e.g., the discrete | |||

logarithm problem in either curve model is equally hard. | logarithm problem in either curve model is equally hard. | |||

For the Montgomery curves and twisted Edwards curves we consider, the | For the Montgomery curves and twisted Edwards curves we consider, the | |||

mapping from M_{A,B} to E_{a,d} is defined by mapping the point at | mapping from M_{A,B} to E_{a,d} is defined by mapping the point at | |||

infinity O and the point (0, 0) of order two of M_{A,B} to, | infinity O and the point (0, 0) of order two of M_{A,B} to, | |||

respectively, the point (0, 1) and the point (0, -1) of order two of | respectively, the point (0, 1) and the point (0, -1) of order two of | |||

E_{a,d}, while mapping each other point (u, v) of M_{A,B} to the | E_{a,d}, while mapping each other point (u, v) of M_{A,B} to the | |||

point (x, y):=(u/v, (u-1)/(u+1)) of E_{a,d}. The inverse mapping from | point (x,y):=(u/v,(u-1)/(u+1)) of E_{a,d}. The inverse mapping from | |||

E_{a,d} to M_{A,B} is defined by mapping the point (0, 1) and the | E_{a,d} to M_{A,B} is defined by mapping the point (0, 1) and the | |||

point (0, -1) of order two of E_{a,d} to, respectively, the point at | point (0, -1) of order two of E_{a,d} to, respectively, the point at | |||

infinity O and the point (0, 0) of order two of M_{A,B}, while each | infinity O and the point (0, 0) of order two of M_{A,B}, while each | |||

other point (x, y) of E_{a,d} is mapped to the point (u, | other point (x, y) of E_{a,d} is mapped to the point | |||

v):=((1+y)/(1-y), (1+y)/((1-y)*x)) of M_{A,B}. | (u,v):=((1+y)/(1-y),(1+y)/((1-y)*x)) of M_{A,B}. | |||

Implementations may take advantage of this mapping to carry out | Implementations may take advantage of this mapping to carry out | |||

elliptic curve group operations originally defined for a twisted | elliptic curve group operations originally defined for a twisted | |||

Edwards curve on the corresponding Montgomery curve, or vice-versa, | Edwards curve on the corresponding Montgomery curve, or vice-versa, | |||

and translating the result back to the original curve, thereby | and translating the result back to the original curve, thereby | |||

potentially allowing code reuse. | potentially allowing code reuse. | |||

D.2. Mapping between Montgomery Curves and Weierstrass Curves | D.2. Mapping between Montgomery Curves and Weierstrass Curves | |||

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 (x, y):=(u/ | mapping each other point (u,v) of M_{A,B} to the point | |||

B+A/(3*B), v/B) of W_{a,b}. Note that not all Weierstrass curves can | (X,Y):=(u/B+A/(3*B),v/B) of W_{a,b}. Note that not all Weierstrass | |||

be injectively mapped to Montgomery curves, since the latter have a | curves can be injectively mapped to Montgomery curves, since the | |||

point of order two and the former may not. In particular, if a | latter have a point of order two and the former may not. In | |||

Weierstrass curve has prime order, such as is the case with the so- | particular, if a Weierstrass curve has prime order, such as is the | |||

called "NIST curves", this inverse mapping is not defined. | case with the so-called "NIST curves", this inverse mapping is not | |||

defined. | ||||

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

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

this case, the mapping from W_{a,b} to M_{A,B} is defined by mapping | ||||

the point at infinity O of W_{a,b} to the point at infinity O of | ||||

M_{A,B}, while mapping each other point (X,Y) of W_{a,b} to the point | ||||

(u,v):=((X-alpha)/gamma,Y/gamma) of M_{A,B}. As before, this defines | ||||

a one-to-one correspondence, which - in fact - is an isomorphism | ||||

between W_{a,b} and M_{A,B}. It is easy to see that the mapping from | ||||

W_{a,b} to M_{A,B} and that from M_{A,B} to W_{a,b} (if defined) are | ||||

each other's inverse. | ||||

This mapping can be used to implement elliptic curve group operations | This mapping can be used to implement elliptic curve group operations | |||

originally defined for a twisted Edwards curve or for a Montgomery | originally defined for a twisted Edwards curve or for a Montgomery | |||

curve using group operations on the corresponding elliptic curve in | curve using group operations on the corresponding elliptic curve in | |||

short-Weierstrass form and translating the result back to the | short-Weierstrass form and translating the result back to the | |||

original curve, thereby potentially allowing code reuse. | original curve, thereby potentially allowing code reuse. | |||

Note that implementations for elliptic curves with short-Weierstrass | Note that implementations for elliptic curves with short-Weierstrass | |||

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 curve 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) to realize the | composition (now using the respective inverses - if these exist) to | |||

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

over the prime field GF(p), with p:=2^{255}-19, where A:=486662 and | over the prime field GF(p), with p:=2^{255}-19, where A:=486662 and | |||

B:=1. This curve has order h*n, where h=8 and where n is a prime | B:=1. This curve has order h*n, where h=8 and where n is a prime | |||

number. For this curve, A^2-4 is not a square in GF(p), whereas A+2 | number. For this curve, A^2-4 is not a square in GF(p), whereas A+2 | |||

is. The quadratic twist of this curve has order h1*n1, where h1=4 | is. The quadratic twist of this curve has order h1*n1, where h1=4 | |||

and where n1 is a prime number. For this curve, the base point is | and where n1 is a prime number. For this curve, the base point is | |||

the point (Gu,Gv), where Gu=9 and where Gv is an odd integer in the | the point (Gu, Gv), where Gu=9 and where Gv is an odd integer in the | |||

interval [0, p-1]. | interval [0, p-1]. | |||

This curve has the same group structure as (is "isomorphic" to) the | This curve has the same group structure as (is "isomorphic" to) the | |||

twisted Edwards curve E_{a,d} defined over GF(p), with as base point | twisted Edwards curve E_{a,d} defined over GF(p), with as base point | |||

the point (Gx,Gy), where parameters are as specified in Appendix E.3. | the point (Gx, Gy), where parameters are as specified in | |||

This curve is denoted as Edwards25519. For this curve, the parameter | Appendix E.3. This curve is denoted as Edwards25519. For this | |||

a is a square in GF(p), whereas d is not, so the group laws of | curve, the parameter a is a square in GF(p), whereas d is not, so the | |||

Appendix C.3 apply. | group laws of Appendix C.3 apply. | |||

The curve is also isomorphic to the elliptic curve W_{a,b} in short- | The curve is also isomorphic to the elliptic curve W_{a,b} in short- | |||

Weierstrass form defined over GF(p), with as base point the point | Weierstrass form defined over GF(p), with as base point the point | |||

(Gx',Gy'), where parameters are as specified in Appendix E.3. This | (GX, GY), where parameters are as specified in Appendix E.3. This | |||

curve is denoted as Wei25519. | curve is denoted as Wei25519. | |||

E.2. Switching between Alternative Representations | E.2. Switching between Alternative Representations | |||

Each affine point (u,v) of Curve25519 corresponds to the point | Each affine point (u, v) of Curve25519 corresponds to the point (X, | |||

(x,y):=(u + A/3,y) of Wei25519, while the point at infinity of | Y):=(u + A/3, v) of Wei25519, while the point at infinity of | |||

Curve25519 corresponds to the point at infinity of Wei25519. (Here, | Curve25519 corresponds to the point at infinity of Wei25519. (Here, | |||

we used the mapping of Appendix D.2.) Under this mapping, the base | we used the mappings of Appendix D.2.) Under this mapping, the base | |||

point (Gu,Gv) of Curve25519 corresponds to the base point (Gx',Gy') | point (Gu, Gv) of Curve25519 corresponds to the base point (GX, GY) | |||

of Wei25519. The inverse mapping maps the affine point (x,y) of | of Wei25519. The inverse mapping maps the affine point (X, Y) of | |||

Wei25519 to (u,v):=(x - A/3,y) of Curve25519, while mapping the point | Wei25519 to (u, v):=(X - A/3, Y) of Curve25519, while mapping the | |||

at infinity of Wei25519 to the point at infinity of Curve25519. Note | point at infinity of Wei25519 to the point at infinity of Curve25519. | |||

that this mapping involves a simple shift of the first coordinate and | Note that this mapping involves a simple shift of the first | |||

can be implemented via integer-only arithmetic as a shift of (p+A)/3 | coordinate and can be implemented via integer-only arithmetic as a | |||

for the isomorphic mapping and a shift of -(p+A)/3 for its inverse, | shift of (p+A)/3 for the isomorphic mapping and a shift of -(p+A)/3 | |||

where delta=(p+A)/3 is the element of GF(p) defined by | for its inverse, where delta=(p+A)/3 is the element of GF(p) defined | |||

by | ||||

delta 19298681539552699237261830834781317975544997444273427339909597 | delta 19298681539552699237261830834781317975544997444273427339909597 | |||

334652188435537 | 334652188435537 | |||

(=0x2aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaad2 | (=0x2aaaaaaa aaaaaaaa aaaaaaaa aaaaaaaa aaaaaaaa aaaaaaaa | |||

451) | aaaaaaaa aaad2451). | |||

(Note that, depending on the implementation details of the field | ||||

arithmetic, one may have to shift the result by +p or -p if this | ||||

integer is not in the interval [0,p-1].) | ||||

The curve Edwards25519 is isomorphic to the curve Curve25519, where | The curve Edwards25519 is isomorphic to the curve Curve25519, where | |||

the base point (Gu,Gv) of Curve25519 corresponds to the base point | the base point (Gu, Gv) of Curve25519 corresponds to the base point | |||

(Gx,Gy) of Edwards25519 and where the point at infinity and the point | (Gx,Gy) of Edwards25519 and where the point at infinity and the point | |||

(0,0) of order two of Curve25519 correspond to, respectively, the | (0,0) of order two of Curve25519 correspond to, respectively, the | |||

point (0, 1) and the point (0, -1) of order two of Edwards25519 and | point (0, 1) and the point (0, -1) of order two of Edwards25519 and | |||

where each other point (u, v) of Curve25519 corresponds to the point | where each other point (u, v) of Curve25519 corresponds to the point | |||

(c*u/v, (u-1)/(u+1)) of Edwards25519, where c is the element of GF(p) | (c*u/v, (u-1)/(u+1)) of Edwards25519, where c is the element of GF(p) | |||

defined by | defined by | |||

c sqrt(-(A+2)) | c sqrt(-(A+2)/B) | |||

51042569399160536130206135233146329284152202253034631822681833788 | 51042569399160536130206135233146329284152202253034631822681833788 | |||

666877215207 | 666877215207 | |||

(=0x70d9120b 9f5ff944 2d84f723 fc03b081 3a5e2c2e b482e57d | (=0x70d9120b 9f5ff944 2d84f723 fc03b081 3a5e2c2e b482e57d | |||

3391fb55 00ba81e7) | 3391fb55 00ba81e7). | |||

(Here, we used the mapping of Appendix D.1.) The inverse mapping | (Here, we used the mapping of Appendix D.1 and normalized this using | |||

from Edwards25519 to Curve25519 is defined by mapping the point (0, | the mapping of Appendix F.1 (where the element s of that appendix is | |||

1) and the point (0, -1) of order two of Edwards25519 to, | set to c above).) The inverse mapping from Edwards25519 to | |||

respectively, the point at infinity and the point (0,0) of order two | Curve25519 is defined by mapping the point (0, 1) and the point (0, | |||

of Curve25519 and having each other point (x, y) of Edwards25519 | -1) of order two of Edwards25519 to, respectively, the point at | |||

correspond to the point ((1 + y)/(1 - y), c*(1 + y)/((1-y)*x)). | infinity and the point (0,0) of order two of Curve25519 and having | |||

each other point (x, y) of Edwards25519 correspond to the point ((1 + | ||||

y)/(1 - y), c*(1 + y)/((1-y)*x)) of Curve25519. | ||||

The curve Edwards25519 is isomorphic to the Weierstrass curve | The curve Edwards25519 is isomorphic to the Weierstrass curve | |||

Wei25519, where the base point (Gx,Gy) of Edwards25519 corresponds to | Wei25519, where the base point (Gx, Gy) of Edwards25519 corresponds | |||

the base point (Gx',Gy') of Wei25519 and where the identity element | to the base point (GX,GY) of Wei25519 and where the identity element | |||

(0,1) and the point (0,-1) of order two of Edwards25519 correspond | (0,1) and the point (0,-1) of order two of Edwards25519 correspond | |||

to, respectively, the point at infinity O and the point (A/3, 0) of | to, respectively, the point at infinity O and the point (A/3, 0) of | |||

order two of Wei25519 and where each other point (x, y) of | order two of Wei25519 and where each other point (x, y) of | |||

Edwards25519 corresponds to the point (x', y'):=((1+y)/(1-y)+A/3, | Edwards25519 corresponds to the point (X, Y):=((1+y)/(1-y)+A/3, | |||

c*(1+y)/((1-y)*x)) of Wei25519, where c was defined before. (Here, | c*(1+y)/((1-y)*x)) of Wei25519, where c was defined before. (Here, | |||

we used the mapping of Appendix D.3.) The inverse mapping from | we used the mapping of Appendix D.3.) The inverse mapping from | |||

Wei25519 to Edwards25519 is defined by mapping the point at infinity | Wei25519 to Edwards25519 is defined by mapping the point at infinity | |||

O and the point (A/3, 0) of order two of Wei25519 to, respectively, | O and the point (A/3, 0) of order two of Wei25519 to, respectively, | |||

the identity element (0,1) and the point (0,-1) of order two of | the identity element (0,1) and the point (0,-1) of order two of | |||

Edwards25519 and having each other point (x, y) of Wei25519 | Edwards25519 and having each other point (X, Y) of Wei25519 | |||

correspond to the point (c*(3*x-A)/(3*y), (3*x-A-3)/(3*x-A+3)). | correspond to the point (c*(3*X-A)/(3*Y), (3*X-A-3)/(3*X-A+3)) of | |||

Edwards25519. | ||||

Note that these mappings can be easily realized in projective | Note that these mappings can be easily realized if points are | |||

coordinates, using a few field multiplications only, thus allowing | represented in projective coordinates, using a few field | |||

switching between alternative representations with negligible | multiplications only, thus allowing switching between alternative | |||

relative incremental cost. | curve representations with negligible relative incremental cost. | |||

E.3. Domain Parameters | E.3. Domain Parameters | |||

The parameters of the Montgomery curve and the corresponding | The parameters of the Montgomery curve and the corresponding | |||

isomorphic curves in twisted Edwards curve and short-Weierstrass form | isomorphic curves in twisted Edwards curve and short-Weierstrass form | |||

are as indicated below. Here, the domain parameters of the | are as indicated below. Here, the domain parameters of the | |||

Montgomery curve Curve25519 and of the twisted Edwards curve | Montgomery curve Curve25519 and of the twisted Edwards curve | |||

Edwards25519 are as specified in RFC 7748; the domain parameters of | Edwards25519 are as specified in [RFC7748]; the domain parameters of | |||

Wei25519 are "new". | Wei25519 are "new". | |||

General parameters (for all curve models): | General parameters (for all curve models): | |||

p 2^{255}-19 | p 2^{255}-19 | |||

(=0x7fffffff ffffffff ffffffff ffffffff ffffffff ffffffff | (=0x7fffffff ffffffff ffffffff ffffffff ffffffff ffffffff | |||

ffffffff ffffffed) | ffffffff ffffffed) | |||

h 8 | h 8 | |||

skipping to change at page 18, line 30 ¶ | skipping to change at page 21, line 37 ¶ | |||

Gv 14781619447589544791020593568409986887264606134616475288964881837 | Gv 14781619447589544791020593568409986887264606134616475288964881837 | |||

755586237401 | 755586237401 | |||

(=0x20ae19a1 b8a086b4 e01edd2c 7748d14c 923d4d7e 6d7c61b2 | (=0x20ae19a1 b8a086b4 e01edd2c 7748d14c 923d4d7e 6d7c61b2 | |||

29e9c5a2 7eced3d9) | 29e9c5a2 7eced3d9) | |||

Twisted Edwards curve-specific parameters (for Edwards25519): | Twisted Edwards curve-specific parameters (for Edwards25519): | |||

a -1 (-0x01) | a -1 (-0x01) | |||

d -121665/121666 | d -121665/121666 = - (A-2)/(A+2) | |||

(=370957059346694393431380835087545651895421138798432190163887855 | (=370957059346694393431380835087545651895421138798432190163887855 | |||

33085940283555) | 33085940283555) | |||

(=0x52036cee 2b6ffe73 8cc74079 7779e898 00700a4d 4141d8ab | (=0x52036cee 2b6ffe73 8cc74079 7779e898 00700a4d 4141d8ab | |||

75eb4dca 135978a3) | 75eb4dca 135978a3) | |||

Gx 15112221349535400772501151409588531511454012693041857206046113283 | Gx 15112221349535400772501151409588531511454012693041857206046113283 | |||

949847762202 | 949847762202 | |||

skipping to change at page 19, line 17 ¶ | skipping to change at page 22, line 24 ¶ | |||

(=0x2aaaaaaa aaaaaaaa aaaaaaaa aaaaaaaa aaaaaaaa aaaaaaaa | (=0x2aaaaaaa aaaaaaaa aaaaaaaa aaaaaaaa aaaaaaaa aaaaaaaa | |||

aaaaaa98 4914a144) | aaaaaa98 4914a144) | |||

b 55751746669818908907645289078257140818241103727901012315294400837 | b 55751746669818908907645289078257140818241103727901012315294400837 | |||

956729358436 | 956729358436 | |||

(=0x7b425ed0 97b425ed 097b425e d097b425 ed097b42 5ed097b4 | (=0x7b425ed0 97b425ed 097b425e d097b425 ed097b42 5ed097b4 | |||

260b5e9c 7710c864) | 260b5e9c 7710c864) | |||

Gx' 19298681539552699237261830834781317975544997444273427339909597334 | GX 19298681539552699237261830834781317975544997444273427339909597334 | |||

652188435546 | 652188435546 | |||

(=0x2aaaaaaa aaaaaaaa aaaaaaaa aaaaaaaa aaaaaaaa aaaaaaaa | (=0x2aaaaaaa aaaaaaaa aaaaaaaa aaaaaaaa aaaaaaaa aaaaaaaa | |||

aaaaaaaa aaad245a) | aaaaaaaa aaad245a) | |||

Gy' 14781619447589544791020593568409986887264606134616475288964881837 | GY 14781619447589544791020593568409986887264606134616475288964881837 | |||

755586237401 | 755586237401 | |||

(=0x20ae19a1 b8a086b4 e01edd2c 7748d14c 923d4d7e 6d7c61b2 | (=0x20ae19a1 b8a086b4 e01edd2c 7748d14c 923d4d7e 6d7c61b2 | |||

29e9c5a2 7eced3d9) | 29e9c5a2 7eced3d9) | |||

Appendix F. Further Mappings | Appendix F. Further Mappings | |||

The non-binary curves specified in Appendix A are expressed in | The non-binary curves specified in Appendix A are expressed in | |||

different curve models, viz. as curves in short-Weierstrass form, as | different curve models, viz. as curves in short-Weierstrass form, as | |||

Montgomery curves, or as twisted Edwards curves. Within each curve | Montgomery curves, or as twisted Edwards curves. In Appendix D we | |||

model, further mappings exist that induce a mapping between elliptic | already described relationships between these various curve models. | |||

curves within each curve model. This can be exploited to force some | Further mappings exist between elliptic curves within the same curve | |||

of the domain parameters to a value that allows a more efficient | model. These can be exploited to force some of the domain parameters | |||

implementation of the addition formulae. | to specific values that allow for a more efficient implementation of | |||

the addition formulae. | ||||

F.1. Isomorphic Mapping between Weierstrass Curves | F.1. Isomorphic Mapping between Twisted Edwards Curves | |||

One can map points of the twisted Edwards curve E_{a,d} to points of | ||||

the twisted Edwards curve E_{a',d'}, where a:=a'*s^2 and d:=d'*s^2 | ||||

for some nonzero element s of GF(q). This defines a one-to-one | ||||

correspondence, which - in fact - is an isomorphism between E_{a,d} | ||||

and E_{a',d'}. | ||||

The mapping from E_{a,d} to E_{a',d'} is defined by mapping the point | ||||

(x,y) of E_{a,d} to the point (x', y'):=(s*x, y) of E_{a',d'}. The | ||||

inverse mapping from E_{a',d'} to E_{a,d} is defined by mapping the | ||||

point (x', y') of E_{a',d'} to the point (x, y):=(x'/s, y') of | ||||

E_{a,d}. | ||||

Implementations may take advantage of this mapping to carry out | ||||

elliptic curve group operations originally defined for a twisted | ||||

Edwards curve with generic domain parameters a and d on a | ||||

corresponding isomorphic twisted Edwards curve with domain parameters | ||||

a' and d' that have a more special form, which are known to allow for | ||||

more efficient implementations of addition laws. In particular, it | ||||

is known that such efficiency improvements exist if a':=-1 (see | ||||

[tEd-Formulas]). | ||||

F.2. Isomorphic Mapping between Montgomery Curves | ||||

One can map points of the Montgomery curve M_{A,B} to points of the | ||||

Montgomery curve M_{A',B'}, where A:=A' and B:=B'*s^2 for some | ||||

nonzero element s of GF(q). This defines a one-to-one | ||||

correspondence, which - in fact - is an isomorphism between M_{A,B} | ||||

and M_{A',B'}. | ||||

The mapping from M_{A,B} to M_{A',B'} is defined by mapping the point | ||||

at infinity O of M_{A,B} to the point at infinity O of M_{A',B'}, | ||||

while mapping each other point (u,v) of M_{A,B} to the point (u', | ||||

v'):=(u, s*v) of M_{A',B'}. The inverse mapping from M_{A',B'} to | ||||

M_{A,B} is defined by mapping the point at infinity O of M_{A',B'} to | ||||

the point at infinity O of M_{A,B}, while mapping each other point | ||||

(u',v') of M_{A',B'} to the point (u,v):=(u',v'/s) of M_{A,B}. | ||||

One can also map points of the Montgomery curve M_{A,B} to points of | ||||

the Montgomery curve M_{A',B'}, where A':=-A and B':=-B. This | ||||

defines a one-to-one correspondence, which - in fact - is an | ||||

isomorphism between M_{A,B} and M_{A',B'}. | ||||

In this case, the mapping from M_{A,B} to M_{A',B'} is defined by | ||||

mapping the point at infinity O of M_{A,B} to the point at infinity O | ||||

of M_{A',B'}, while mapping each other point (u,v) of M_{A,B} to the | ||||

point (u',v'):=(-u,v) of M_{A',B'}. The inverse mapping from | ||||

M_{A',B'} to M_{A,B} is defined by mapping the point at infinity O of | ||||

M_{A',B'} to the point at infinity O of M_{A,B}, while mapping each | ||||

other point (u',v') of M_{A',B'} to the point (u,v):=(-u',v') of | ||||

M_{A,B}. | ||||

Implementations may take advantage of this mapping to carry out | ||||

elliptic curve groups operations originally defined for a Montgomery | ||||

curve with generic domain parameters A and B on a corresponding | ||||

isomorphic Montgomery curve with domain parameters A' and B' that | ||||

have a more special form, which is known to allow for more efficient | ||||

implementations of addition laws. In particular, it is known that | ||||

such efficiency improvements exist if B' assumes a small absolute | ||||

value, such as B':=(+/-)1. (see [Ladder]). | ||||

F.3. Isomorphic Mapping between Weierstrass Curves | ||||

One can map points of the Weierstrass curve W_{a,b} to points of the | One can map points of the Weierstrass curve W_{a,b} to points of the | |||

Weierstrass curve W_{a',b'}, where a:=a'*s^4 and b:=b'*s^6 for some | Weierstrass curve W_{a',b'}, where a':=a*s^4 and b':=b*s^6 for some | |||

nonzero value s of the finite field GF(q). This defines a one-to-one | nonzero element s of GF(q). This defines a one-to-one | |||

correspondence, which - in fact - is an isomorphism between W_{a,b} | correspondence, which - in fact - is an isomorphism between W_{a,b} | |||

and W_{a',b'}, thereby showing that, e.g., the discrete logarithm | and W_{a',b'}. | |||

problem in either curve model is equally hard. | ||||

The mapping from W_{a,b} to W_{a',b'} is defined by mapping the point | The mapping from W_{a,b} to W_{a',b'} is defined by mapping the point | |||

at infinity O of W_{a,b} to the point at infinity O of W_{a',b'}, | at infinity O of W_{a,b} to the point at infinity O of W_{a',b'}, | |||

while mapping each other point (x, y) of W_{a,b} to the point (x', | while mapping each other point (X,Y) of W_{a,b} to the point | |||

y'):=(x*s^2, y*s^3) of W_{a',b'}. The inverse mapping from W_{a',b'} | (X',Y'):=(X*s^2, Y*s^3) of W_{a',b'}. The inverse mapping from | |||

to W_{a,b} is defined by mapping the point at infinity O of W_{a',b'} | W_{a',b'} to W_{a,b} is defined by mapping the point at infinity O of | |||

to the point at infinity O of W_{a,b}, while mapping each other point | W_{a',b'} to the point at infinity O of W_{a,b}, while mapping each | |||

(x', y') of W_{a',b'} to the point (x, y):=(x/s^2, y/s^3) of W_{a,b}. | other point (X', Y') of W_{a',b'} to the point (X,Y):=(X'/s^2,Y'/s^3) | |||

of W_{a,b}. | ||||

Implementations may take advantage of this mapping to carry out | Implementations may take advantage of this mapping to carry out | |||

elliptic curve group operations originally defined for a Weierstrass | elliptic curve group operations originally defined for a Weierstrass | |||

curve with a generic domain parameter a on a corresponding isomorphic | curve with generic domain parameters a and b on a corresponding | |||

Weierstrass curve with domain parameter a' that has a special form, | isomorphic Weierstrass curve with domain parameter a' and b' that | |||

which is known to allow for more efficient implementations of | have a more special form, which is known to allow for more efficient | |||

addition laws, and translating the result back to the original curve. | implementations of addition laws, and translating the result back to | |||

In particular, it is known that such efficiency improvements exist if | the original curve. In particular, it is known that such efficiency | |||

a'=-3 (mod p) and one uses so-called Jacobian coordinates with a | improvements exist if a'=-3 (mod p), where p is the characteristic of | |||

particular projective version of the addition laws of Appendix C.1. | GF(q), and one uses so-called Jacobian coordinates with a particular | |||

While not all Weierstrass curves can be put into this form, all | projective version of the addition laws of Appendix C.1. While not | |||

traditional NIST curves have domain parameter a=-3, while all | all Weierstrass curves can be put into this form, all traditional | |||

Brainpool curves [RFC5639] are isomorphic to a Weierstrass curve of | NIST curves have domain parameter a=-3, while all Brainpool curves | |||

this form. | [RFC5639] are isomorphic to a Weierstrass curve of this form. | |||

Note that implementations for elliptic curves with short-Weierstrass | Note that implementations for elliptic curves with short-Weierstrass | |||

form that hard-code the domain parameter a to a= -3 cannot always be | form that hard-code the domain parameter a to a= -3 cannot always be | |||

used this way, since the curve W_{a,b} cannot always be expressed in | used this way, since the curve W_{a,b} cannot always be expressed in | |||

terms of a Weierstrass curve with a'=-3 via a coordinate | terms of a Weierstrass curve with a'=-3 via a coordinate | |||

transformation: this only holds if a'/a is a fourth power in GF(q) | transformation: this only holds if a'/a is a fourth power in GF(q) | |||

(see Section 3.1.5 of [GECC]). However, even in this case, one can | (see Section 3.1.5 of [GECC]). However, even in this case, one can | |||

still express the curve W_{a,b} as a Weierstrass curve with a small | still express the curve W_{a,b} as a Weierstrass curve with a small | |||

domain parameter value a', thereby still allowing a more efficient | domain parameter value a', thereby still allowing a more efficient | |||

implementation than with a general domain parameter value a. | implementation than with a general domain parameter value a. | |||

F.2. Isogenous Mapping between Weierstrass Curves | F.4. Isogenous Mapping between Weierstrass Curves | |||

One can still map points of the Weierstrass curve W_{a,b} to points | One can still map points of the Weierstrass curve W_{a,b} to points | |||

of the Weierstrass curve W_{a',b'}, where a':=-3 (mod p), even if | of the Weierstrass curve W_{a',b'}, where a':=-3 (mod p) and where p | |||

a'/a is not a fourth power in GF(q). In that case, this mappping | is the characteristic of GF(q), even if a'/a is not a fourth power in | |||

cannot be an isomorphism (see Appendix F.1). Instead, the mapping is | GF(q). In that case, this mappping cannot be an isomorphism (see | |||

a so-called isogeny (or homomorphism). Since most elliptic curve | Appendix F.3). Instead, the mapping is a so-called isogeny (or | |||

operations process points of prime order or use so-called "co-factor | homomorphism). Since most elliptic curve operations process points | |||

multiplication", in practice the resulting mapping has similar | of prime order or use so-called "co-factor multiplication", in | |||

properties as an isomorphism. In particular, one can still take | practice the resulting mapping has similar properties as an | |||

advantage of this mapping to carry out elliptic curve group | isomorphism. In particular, one can still take advantage of this | |||

operations originally defined for a Weierstrass curve with domain | mapping to carry out elliptic curve group operations originally | |||

parameter a unequal to -3 (mod p) on a corresponding isogenous | defined for a Weierstrass curve with domain parameter a unequal to -3 | |||

Weierstrass curve with domain parameter a'=-3 (mod p) and translating | (mod p) on a corresponding isogenous Weierstrass curve with domain | |||

the result back to the original curve. | parameter a'=-3 (mod p) and translating the result back to the | |||

original curve. | ||||

In this case, the mapping from W_{a,b} to W_{a',b'} is defined by | In this case, the mapping from W_{a,b} to W_{a',b'} is defined by | |||

mapping the point at infinity O of W_{a,b} to the point at infinity O | mapping the point at infinity O of W_{a,b} to the point at infinity O | |||

of W_{a',b'}, while mapping each other point (x, y) of W_{a,b} to the | of W_{a',b'}, while mapping each other point (X,Y) of W_{a,b} to the | |||

point (x', y'):=(u(x)/w(x)^2, y*v(x)/w(x)^3) of W_{a',b'}. Here, | point (X',Y'):=(u(X)/w(X)^2,Y*v(X)/w(X)^3) of W_{a',b'}. Here, u(X), | |||

u(x), v(x), and w(x) are polynomials that depend on the isogeny in | v(X), and w(X) are polynomials in X that depend on the isogeny in | |||

question. The inverse mapping from W_{a',b'} to W_{a,b} is again an | question. The inverse mapping from W_{a',b'} to W_{a,b} is again an | |||

isogeny and defined by mapping the point at infinity O of W_{a',b'} | isogeny and defined by mapping the point at infinity O of W_{a',b'} | |||

to the point at infinity O of W_{a,b}, while mapping each other point | to the point at infinity O of W_{a,b}, while mapping each other point | |||

(x', y') of W_{a',b'} to the point (x, y):=(u'(x')/w'(x')^2, | (X', Y') of W_{a',b'} to the point | |||

y'*v'(x')/w'(x')^3) of W_{a,b}, where -- again -- u'(x'), v'(x'), and | (X,Y):=(u'(X')/w'(X')^2,Y'*v'(X')/w'(X')^3) of W_{a,b}, where -- | |||

w'(x') are polynomials that depend on the isogeny in question. These | again -- u'(X'), v'(X'), and w'(X') are polynomials in X' that depend | |||

mappings have the property that their composition is not the identity | on the isogeny in question. These mappings have the property that | |||

mapping (as is the case with the isomorphic mappings discussed in | their composition is not the identity mapping (as was the case with | |||

Appendix F.1), but rather a fixed multiple hereof: if this multiple | the isomorphic mappings discussed in Appendix F.3), but rather a | |||

is l then the isogeny is called an isogeny of degree l (or l-isogeny) | fixed multiple hereof: if this multiple is l then the isogeny is | |||

and u, v, and w (and, similarly, u', v', and w') are polynomials of | called an isogeny of degree l (or l-isogeny) and u, v, and w (and, | |||

degrees l, 3(l-1)/2, and (l-1)/2, respectively. Note that an | similarly, u', v', and w') are polynomials of degrees l, 3*(l-1)/2, | |||

isomorphism is simply an isogeny of degree l=1. Details of how to | and (l-1)/2, respectively. Note that an isomorphism is simply an | |||

determine isogenies are outside scope of this document (for this, | isogeny of degree l=1. Details of how to determine isogenies are | |||

contact the author of this document). | outside scope of this document (for this, contact the author of this | |||

document). | ||||

Implementations may take advantage of this mapping to carry out | Implementations may take advantage of this mapping to carry out | |||

elliptic curve group operations originally defined for a Weierstrass | elliptic curve group operations originally defined for a Weierstrass | |||

curve with a generic domain parameter a on a corresponding isogenous | curve with a generic domain parameter a on a corresponding isogenous | |||

Weierstrass curve with domain parameter a'=-3 (mod p), where one can | Weierstrass curve with domain parameter a'=-3 (mod p), where one can | |||

use so-called Jacobian coordinates with a particular projective | use so-called Jacobian coordinates with a particular projective | |||

version of the addition laws of Appendix C.1. Since all traditional | version of the addition laws of Appendix C.1. Since all traditional | |||

NIST curves have domain parameter a=-3, while all Brainpool curves | NIST curves have domain parameter a=-3, while all Brainpool curves | |||

[RFC5639] are isomorphic to a Weierstrass curve of this form, this | [RFC5639] are isomorphic to a Weierstrass curve of this form, this | |||

allows taking advantage of existing implementations for these curves | allows taking advantage of existing implementations for these curves | |||

that may have a hardcoded a=-3 (mod p) domain parameter, provided one | that may have a hardcoded a=-3 (mod p) domain parameter, provided one | |||

switches back and forth to this curve form using the isogenous | switches back and forth to this curve form using the isogenous | |||

mapping in question. | mapping in question. | |||

Note that isogenous mappings can be easily realized in projective | Note that isogenous mappings can be easily realized using | |||

coordinates and involves roughly 3*l finite field multiplications, | representations in projective coordinates and involves roughly 3*l | |||

thus allowing switching between alternative representations at | finite field multiplications, thus allowing switching between | |||

relative low incremental cost compared to that of elliptic curve | alternative representations at relatively low incremental cost | |||

scalar multiplications (provided the isogeny has low degree l). | compared to that of elliptic curve scalar multiplications (provided | |||

Note, however, that this does require storage of the polynomial | the isogeny has low degree l). Note, however, that this does require | |||

coefficients of the isogeny and dual isogeny involved. This | storage of the polynomial coefficients of the isogeny and dual | |||

illustrates that low-degree isogenies are to be preferred, since an | isogeny involved. This illustrates that low-degree isogenies are to | |||

l-isogeny (usually) requires storing roughly 6*l elements of GF(q). | be preferred, since an l-isogeny (usually) requires storing roughly | |||

While there are many isogenies, we therefore only consider those with | 6*l elements of GF(q). While there are many isogenies, we therefore | |||

the desired property with lowest possible degree. | only consider those with the desired property with lowest possible | |||

degree. | ||||

Appendix G. Further Cousins of Curve25519 | Appendix G. Further Cousins of Curve25519 | |||

G.1. Further Alternative Representations | G.1. Further Alternative Representations | |||

The Weierstrass curve Wei25519 is isomorphic to the Weierstrass curve | The Weierstrass curve Wei25519 is isomorphic to the Weierstrass curve | |||

Wei25519.2 defined over GF(p), with as base point the pair | Wei25519.2 defined over GF(p), with as base point the pair (G2X,G2Y), | |||

(G1x',G1y'), and isogenous to the Weierstrass curve Wei25519.-3 | and isogenous to the Weierstrass curve Wei25519.-3 defined over | |||

defined over GF(p), with as base point the pair (G2x', G2y'), where | GF(p), with as base point the pair (G3X, G3Y), where parameters are | |||

parameters are as specified in Appendix G.3 and where the related | as specified in Appendix G.3 and where the related mappings are as | |||

mappings are as specified in Appendix G.2. | specified in Appendix G.2. | |||

G.2. Further Switching | G.2. Further Switching | |||

Each affine point (x,y) of Wei25519 corresponds to the point | Each affine point (X, Y) of Wei25519 corresponds to the point (X', | |||

(x',y'):=(x*s^2,y*s^3) of Wei25519.2, where s is the element of GF(p) | Y'):=(X*s^2,Y*s^3) of Wei25519.2, where s is the element of GF(p) | |||

defined by | defined by | |||

s 20343593038935618591794247374137143598394058341193943326473831977 | s 20343593038935618591794247374137143598394058341193943326473831977 | |||

39407761440 | 39407761440 | |||

(=0x047f6814 6d568b44 7e4552ea a5ed633d 02d62964 a2b0a120 | (=0x047f6814 6d568b44 7e4552ea a5ed633d 02d62964 a2b0a120 | |||

5e7941e9 375de020), | 5e7941e9 375de020), | |||

while the point at infinity of Wei25519 corresponds to the point at | while the point at infinity of Wei25519 corresponds to the point at | |||

infinity of Wei25519.2. (Here, we used the mapping of Appendix F.1.) | infinity of Wei25519.2. (Here, we used the mapping of Appendix F.3.) | |||

Under this mapping, the base point (Gx',Gy') of Wei25519 corresponds | Under this mapping, the base point (GX, GY) of Wei25519 corresponds | |||

to the base point (G1x',G1y') of Wei25519.2. The inverse mapping | to the base point (G2X,G2Y) of Wei25519.2. The inverse mapping maps | |||

maps the affine point (x',y') of Wei25519.2 to (x,y):=(x'/s^2,y'/s^3) | the affine point (X', Y') of Wei25519.2 to (X,Y):=(X'/s^2,Y'/s^3) of | |||

of Wei25519, while mapping the point at infinity of Wei25519.2 to the | Wei25519, while mapping the point at infinity O of Wei25519.2 to the | |||

point at infinity of Wei25519. Note that this mapping (and its | point at infinity O of Wei25519. Note that this mapping (and its | |||

inverse) involves a modular multiplication of both coordinates with | inverse) involves a modular multiplication of both coordinates with | |||

fixed constants s^2 and s^3 (respectively, 1/s^2 and 1/s^3), which | fixed constants s^2 and s^3 (respectively, 1/s^2 and 1/s^3), which | |||

can be precomputed. | can be precomputed. | |||

Each affine point (x,y) of Wei25519 corresponds to the point | Each affine point (X,Y) of Wei25519 corresponds to the point | |||

(x',y'):=(x1/t^2,y1/t^3) of Wei25519.-3, where | (X',Y'):=(X1*t^2,Y1*t^3) of Wei25519.-3, where | |||

(x1,y1)=(u(x)/w(x)^2,y*v(x)/w(x)^3), where u, v, and w are the | (X1,Y1)=(u(X)/w(X)^2,Y*v(X)/w(X)^3), where u, v, and w are the | |||

polynomials with coefficients in GF(p) as defined in Appendix H.1 and | polynomials with coefficients in GF(p) as defined in Appendix H.1 and | |||

where t is the element of GF(p) defined by | where t is the element of GF(p) defined by | |||

t 26012855558634277483276064234565597076862996895623795164528458073 | t 35728133398289175649586938605660542688691615699169662967154525084 | |||

435568115620 | 644181596229 | |||

(=0x3982c126 59ad1749 ab8bc495 bb1a9d64 c9deffc5 e7b8e601 | (=0x4efd6829 88ff8526 e189f712 5999550c e9ef729b ed1a7015 | |||

a5651992 07d48fa4), | 73b1bab8 8bfcd845), | |||

while the point at infinity of Wei25519 corresponds to the point at | while the point at infinity of Wei25519 corresponds to the point at | |||

infinity of Wei25519.-3. (Here, we used the isogenous mapping of | infinity of Wei25519.-3. (Here, we used the isogenous mapping of | |||

Appendix F.2.) Under this isogenous mapping, the base point | Appendix F.4.) Under this isogenous mapping, the base point (GX,GY) | |||

(Gx',Gy') of Wei25519 corresponds to the base point (G2x',G2y') of | of Wei25519 corresponds to the base point (G3X,G3Y) of Wei25519.-3. | |||

Wei25519.-3. The dual isogeny maps the affine point (x',y') of | The dual isogeny maps the affine point (X',Y') of Wei25519.-3 to the | |||

Wei25519.-3 to to (x,y):=(u'(x1)/w'(x1)^2,y1*v'(x1)/w'(x1)^3) of | affine point (X,Y):=(u'(X1)/w'(X1)^2,Y1*v'(x1)/w'(X1)^3) of Wei25519, | |||

Wei25519, where (x1,y1)=(x'*t^2,y'*t^3) and where u', v', and w' are | where (X1,Y1)=(X'/t^2,Y'/t^3) and where u', v', and w' are the | |||

the polynomials with coefficients in GF(p) as defined in | polynomials with coefficients in GF(p) as defined in Appendix H.2, | |||

Appendix H.2, while mapping the point at infinity of Wei25519.-3 to | while mapping the point at infinity O of Wei25519.-3 to the point at | |||

the point at infinity of Wei25519. Under this dual isogenous | infinity O of Wei25519. Under this dual isogenous mapping, the base | |||

mapping, the base point (G2x',G2y') of Wei25519.-3 corresponds to a | point (G3X, G3Y) of Wei25519.-3 corresponds to a multiple of the base | |||

multiple of the base point (Gx',Gy') of Wei25519, where this multiple | point (GX, GY) of Wei25519, where this multiple is l=47 (the degree | |||

is l=47 (the degree of the isogeny; see the description in | of the isogeny; see the description in Appendix F.3). Note that this | |||

Appendix F.1). Note that this isogenous map (and its dual) primarily | isogenous map (and its dual) primarily involves the evaluation of | |||

involves the evaluation of three fixed polynomials involving the | three fixed polynomials involving the x-coordinate, which takes | |||

x-coordinate, which takes roughly 140 modular multiplications (or | roughly 140 modular multiplications (or less than 5-10% relative | |||

less than 5-10% relative incremental cost compared to the cost of an | incremental cost compared to the cost of an elliptic curve scalar | |||

elliptic curve scalar multiplication). | multiplication). | |||

G.3. Further Domain Parameters | G.3. Further Domain Parameters | |||

The parameters of the Weierstrass curve with a=2 that is isomorphic | The parameters of the Weierstrass curve with a=2 that is isomorphic | |||

with Wei25519 and the parameters of the Weierstrass curve with a=-3 | with Wei25519 and the parameters of the Weierstrass curve with a=-3 | |||

that is isogenous with Wei25519 are as indicated below. Both domain | that is isogenous with Wei25519 are as indicated below. Both domain | |||

parameter sets can be exploited directly to derive more efficient | parameter sets can be exploited directly to derive more efficient | |||

point addition formulae, should an implementation facilitate this. | point addition formulae, should an implementation facilitate this. | |||

General parameters: same as for Wei25519 (see Appendix E.3) | General parameters: same as for Wei25519 (see Appendix E.3) | |||

skipping to change at page 23, line 35 ¶ | skipping to change at page 28, line 15 ¶ | |||

a=2): | a=2): | |||

a 2 (=0x02) | a 2 (=0x02) | |||

b 12102640281269758552371076649779977768474709596484288167752775713 | b 12102640281269758552371076649779977768474709596484288167752775713 | |||

178787220689 | 178787220689 | |||

(=0x1ac1da05 b55bc146 33bd39e4 7f94302e f19843dc f669916f | (=0x1ac1da05 b55bc146 33bd39e4 7f94302e f19843dc f669916f | |||

6a5dfd01 65538cd1) | 6a5dfd01 65538cd1) | |||

G1x' 107705531383684005184170201967961611367923681983263378231495026 | G2X 10770553138368400518417020196796161136792368198326337823149502681 | |||

81097436401658 | 097436401658 | |||

(=0x17cfeac3 78aed661 318e8634 582275b6 d9ad4def 072ea193 | (=0x17cfeac3 78aed661 318e8634 582275b6 d9ad4def 072ea193 | |||

5ee3c4e8 7a940ffa) | 5ee3c4e8 7a940ffa) | |||

G1y' 544305758615084056530986689844575286168071033325025775211614397 | G2Y 54430575861508405653098668984457528616807103332502577521161439773 | |||

7388639873869 | 88639873869 | |||

(=0x0c08a952 c55dfad6 2c4f13f1 a8f68dca dc5c331d 297a37b6 | (=0x0c08a952 c55dfad6 2c4f13f1 a8f68dca dc5c331d 297a37b6 | |||

f0d7fdcc 51e16b4d) | f0d7fdcc 51e16b4d) | |||

Weierstrass curve-specific parameters (for Wei25519.-3, i.e., with | Weierstrass curve-specific parameters (for Wei25519.-3, i.e., with | |||

a=-3): | a=-3): | |||

a -3 | a -3 | |||

(=0x7fffffff ffffffff ffffffff ffffffff ffffffff ffffffff | (=0x7fffffff ffffffff ffffffff ffffffff ffffffff ffffffff | |||

ffffffff ffffffea) | ffffffff ffffffea) | |||

b 29689592517550930188872794512874050362622433571298029721775200646 | b 29689592517550930188872794512874050362622433571298029721775200646 | |||

451501277098 | 451501277098 | |||

(=0x41a3b6bf c668778e be2954a4 b1df36d1 485ecef1 ea614295 | (=0x41a3b6bf c668778e be2954a4 b1df36d1 485ecef1 ea614295 | |||

796e1022 40891faa) | 796e1022 40891faa) | |||

G2x' 538371792299408724349427232574807773704511272123391981336972078 | G3X 53837179229940872434942723257480777370451127212339198133697207846 | |||

46219400243292 | 219400243292 | |||

(=0x7706c37b 5a84128a 3884a5d7 1811f1b5 5da3230f fb17a8ab | (=0x7706c37b 5a84128a 3884a5d7 1811f1b5 5da3230f fb17a8ab | |||

0b32e48d 31a6685c) | 0b32e48d 31a6685c) | |||

G2y' 695480730911001844144020555292799703925148674228551417730708041 | G3Y 69548073091100184414402055529279970392514867422855141773070804184 | |||

8460388229929 | 60388229929 | |||

(=0x0f60480c 7a5c0e11 40340adc 79d6a2bf 0cb57ad0 49d025dc | (=0x0f60480c 7a5c0e11 40340adc 79d6a2bf 0cb57ad0 49d025dc | |||

38d80c77 985f0329) | 38d80c77 985f0329) | |||

Appendix H. Isogeny Details | Appendix H. Isogeny Details | |||

The isogeny and dual isogeny are both isogenies with degree l=47. | The isogeny and dual isogeny are both isogenies with degree l=47. | |||

Both are specified by a triple of polynomials u, v, and w (resp. u', | Both are specified by a triple of polynomials u, v, and w (resp. u', | |||

v', and w') of degree 47, 69, and 23, respectively, with coefficients | v', and w') of degree 47, 69, and 23, respectively, with coefficients | |||

in GF(p). The coeffients of each of these polynomials are specified | in GF(p). The coeffients of each of these polynomials are specified | |||

skipping to change at page 36, line 44 ¶ | skipping to change at page 41, line 22 ¶ | |||

19 0x6868305b4f40654460aad63af3cb9151ab67c775eaac5e5df90d3aea58dee141 | 19 0x6868305b4f40654460aad63af3cb9151ab67c775eaac5e5df90d3aea58dee141 | |||

20 0x16bc90219a36063a22889db810730a8b719c267d538cd28fa7c0d04f124c8580 | 20 0x16bc90219a36063a22889db810730a8b719c267d538cd28fa7c0d04f124c8580 | |||

21 0x3628f9cf1fbe3eb559854e3b1c06a4cd6a26906b4e2d2e70616a493bba2dc574 | 21 0x3628f9cf1fbe3eb559854e3b1c06a4cd6a26906b4e2d2e70616a493bba2dc574 | |||

22 0x64abcc6759f1ce1ab57d41e17c2633f717064e35a7233a6682f8cf8e9538afec | 22 0x64abcc6759f1ce1ab57d41e17c2633f717064e35a7233a6682f8cf8e9538afec | |||

23 0x1 | 23 0x1 | |||

Appendix I. Point Compression | ||||

Point compression allows a shorter representation of affine points of | ||||

an elliptic curve by exploiting algebraic relationships between the | ||||

coordinate values based on the defining equation of the curve in | ||||

question. Point decompression refers to the reverse process, where | ||||

one tries and recover the affine point from its compressed | ||||

representation and information on the domain parameters of the curve. | ||||

Consequently, point compression followed by point decompression is | ||||

the identity map. | ||||

The description below makes use of an auxiliary function (the parity | ||||

function), which we first define for prime fields GF(p) and then | ||||

extend to all fields GF(q), where q is an odd prime power. We assume | ||||

each finite field to be unambiguously defined. | ||||

Let y be a nonzero element of GF(q). If q:=p is an odd prime number, | ||||

y and p-y can be uniquely represented as integers in the interval | ||||

[1,p-1] and have odd sum p. Consequently, one can distinguish y from | ||||

-y via the parity of this representation, i.e., via par(y):=y (mod | ||||

2). If q:=p^m, where p is an odd prime number and where m>0, both y | ||||

and -y can be uniquely represented as vectors of length m, with | ||||

coefficients in GF(p) (see Appendix B.2). In this case, the leftmost | ||||

nonzero coordinate values of y and -y are in the same position and | ||||

have representations in [1,p-1] with different parity. As a result, | ||||

one can distinguish y from -y via the parity of the representation of | ||||

this coordinate value. This extends the definition of the parity | ||||

function to any odd-size field GF(q), where one defines par(0):=0. | ||||

I.1. Point Compression for Weierstrass Curves | ||||

If P:=(X, Y) is an affine point of the Weierstrass curve W_{a,b} | ||||

defined over the field GF(q), then so is -P:=(X, -Y). Since the | ||||

defining equation Y^2=X^2+a*X+b has at most two solutions with fixed | ||||

X-value, one can represent P by its X-coordinate and one bit of | ||||

information that allows one to distinguish P from -P, i.e., one can | ||||

represent P as the ordered pair compr(P):=(X, par(Y)). If P is a | ||||

point of order two, one can uniquely represent P by its X-coordinate | ||||

alone, since Y=0 and has fixed parity. Conversely, given the ordered | ||||

pair (X, t), where X is an element of GF(q) and where t=0 or t=1, and | ||||

the domain parameters of the curve, one can use the defining equation | ||||

of the curve to try and determine candidate values for the | ||||

Y-coordinate given X, by solving the quadratic equation Y^2:=alpha, | ||||

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

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

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

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

correspond to the outcome of the point compression function. | ||||

I.2. Point Compression for Montgomery Curves | ||||

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

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

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

point of order two, one can uniquely represent P by its u-coordinate | ||||

alone, since v=0 and has fixed parity. Conversely, given the ordered | ||||

pair (u, t), where u is an element of GF(q) and where t=0 or t=1, and | ||||

the domain parameters of the curve, one can use the defining equation | ||||

of the curve to try and determine candidate values for the | ||||

v-coordinate given u, by solving the quadratic equation v^2:=alpha, | ||||

where alpha:=(u^3+A*u^2+u)/B. If alpha is not a square in GF(q), | ||||

this equation does not have a solution in GF(q) and the ordered pair | ||||

(u, t) does not correspond to a point of this curve. Otherwise, | ||||

there are two solutions, viz. v=sqrt(alpha) and -v. If alpha is a | ||||

nonzero element of GF(q), one can uniquely recover the v-coordinate | ||||

for which par(v):=t and, thereby, the affine point P:=(u, v). This | ||||

is also the case if alpha=0 and t=0, in which case v=0 and the point | ||||

P has order two. However, if alpha=0 and t=1, the ordered pair (u, | ||||

t) does not correspond to the outcome of the point compression | ||||

function. | ||||

I.3. Point Compression for Twisted Edwards Curves | ||||

If P:=(x, y) is an affine point of the twisted Edwards curve E_{a,d} | ||||

defined over the field GF(q), then so is -P:=(-x, y). Since the | ||||

defining equation a*x^2+y^2=1+d*x^2*y^2 has at most two solutions | ||||

with fixed y-value, one can represent P by its y-coordinate and one | ||||

bit of information that allows one to distinguish P from -P, i.e., | ||||

one can represent P as the ordered pair compr(P):=(par(x), y). If P | ||||

is a point of order one or two, one can uniquely represent P by its | ||||

y-coordinate alone, since x=0 and has fixed parity. Conversely, | ||||

given the ordered pair (t, y), where y is an element of GF(q) and | ||||

where t=0 or t=1, and the domain parameters of the curve, one can use | ||||

the defining equation of the curve to try and determine candidate | ||||

values for the x-coordinate given y, by solving the quadratic | ||||

equation x^2:=alpha, where alpha:=(1-y^2)/(a-d*y^2). If alpha is not | ||||

a square in GF(q), this equation does not have a solution in GF(q) | ||||

and the ordered pair (t, y) does not correspond to a point of this | ||||

curve. Otherwise, there are two solutions, viz. x=sqrt(alpha) and | ||||

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

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

t=1, the ordered pair (t, y) does not correspond to the outcome of | ||||

the point compression function. | ||||

Appendix J. Data Conversions | ||||

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

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

string is the (unique) string of length l=0. | ||||

An octet is an integer in the interval [0,256). An octet string is a | ||||

string, where the alphabet is the set of all octets. A binary string | ||||

(or bit string, for short) is a string, where the alphabet is the set | ||||

{0,1}. Note that the length of a string is defined in terms of the | ||||

underlying alphabet. | ||||

J.1. Conversion between Bit Strings and Integers | ||||

There is a 1-1 correspondence between bit strings of length l and the | ||||

integers in the interval [0, 2^l), where the bit string | ||||

X:=str(x_{l-1}, x_{l-2}, ..., x_1, x_0) corresponds to the integer | ||||

x:=x_{l-1}*2^{l-1} + x_{l-2}*2^{l-2} + ... + x_1*2 + x_0*1. (If l=0, | ||||

the empty bit string corresponds to the integer zero.) Note that | ||||

while the mapping from bit strings to integers is uniquely defined, | ||||

the inverse mapping from integers to bit strings is not, since any | ||||

non-negative integer smaller than 2^t can be represented as a bit | ||||

string of length at least t (due to leading zero coefficients in base | ||||

2 representation). The latter representation is called tight if the | ||||

bit string representation has minimal length. | ||||

J.2. Conversion between Octet Strings and Integers (OS2I, I2OS) | ||||

There is a 1-1 correspondence between octet strings of length l and | ||||

the integers in the interval [0, 256^l), where the octet string | ||||

X:=str(X_{l-1}, X_{l-2}, ..., X_1, X_0) corresponds to the integer | ||||

x:=X_{l-1}*256^{l-1} + X^{l-2}*256^{l-2} + ... + X_1*256 + X_0*1. | ||||

(If l=0, the empty string corresponds to the integer zero.) Note | ||||

that while the mapping from octet strings to integers is uniquely | ||||

defined, the inverse mapping from integers to octet strings is not, | ||||

since any non-negative integer smaller than 256^t can be represented | ||||

as an octet string of length at least t (due to leading zero | ||||

coefficients in base 256 representation). The latter representation | ||||

is called tight if the octet string representation has minimal | ||||

length. This defines the mapping OS2I from octet strings to integers | ||||

and the mapping I2OS(x,l) from non-negative integers smaller than | ||||

256^l to octet strings of length l. | ||||

J.3. Conversion between Octet Strings and Bit Strings (BS2OS, OS2BS) | ||||

There is a 1-1 correspondence between octet strings of length l and | ||||

and bit strings of length 8*l, where the octet string X:=str(X_{l-1}, | ||||

X_{l-2}, ..., X_1, X_0) corresponds to the right-concatenation of the | ||||

8-bit strings x_{l-1}, x_{l-2}, ..., x_1, x_0, where each octet X_i | ||||

corresponds to the 8-bit string x_i according to the mapping of | ||||

Appendix J.1 above. Note that the mapping from octet strings to bit | ||||

strings is uniquely defined and so is the inverse mapping from bit | ||||

strings to octet strings, if one prepends each bit string with the | ||||

smallest number of 0 bits so as to result in a bit string of length | ||||

divisible by eight (i.e., one uses pre-padding). This defines the | ||||

mapping OS2BS from octet strings to bit strings and the corresponding | ||||

mapping BS2OS from bit strings to octet strings. | ||||

J.4. Conversion between Field Elements and Octet Strings (FE2OS, OS2FE) | ||||

There is a 1-1 correspondence between elements of a fixed finite | ||||

field GF(q), where q=p^m and m>0, and vectors of length m, with | ||||

coefficients in GF(p), where each element x of GF(q) is a vector | ||||

(x_{m-1}, x_{m-2}, ..., x_1, x_0) according to the conventions of | ||||

Appendix B.2. In this case, this field element can be uniquely | ||||

represented by the right-concatenation of the octet strings X_{m-1}, | ||||

X_{m-2}, ..., X_1, X_0, where each octet string X_i corresponds to | ||||

the integer x_i in the interval [0,p-1] according to the mapping of | ||||

Appendix J.2 above. Note that both the mapping from field elements | ||||

to octet strings and the inverse mapping are only uniquely defined if | ||||

each octet string X_i has the same fixed size (e.g., the smallest | ||||

integer l so that 256^l >= p) and if all integers are reduced modulo | ||||

p. If so, the latter representation is called tight if l is minimal | ||||

so that 256^l >= p. This defines the mapping FE2OS(x,l) from field | ||||

elements to octet strings and the mapping OS2FE(X,l) from octet | ||||

strings to field elements, where the underlying field is implicit and | ||||

assumed to be known from context. In this case, the octet string has | ||||

length l*m. | ||||

J.5. Ordering Conventions | ||||

One can consider various representation functions, depending on bit- | ||||

ordering and octet-ordering conventions. | ||||

The description below makes use of an auxiliary function (the | ||||

reversion function), which we define both for bit strings and octet | ||||

strings. For a bit string [octet string] X:=str(x_{l-1}, x_{l-2}, | ||||

..., x_1, x_0), its reverse is the bit string [octet string] | ||||

X':=rev(X):=str(x_0, x_1, ..., x_{l-2}, x_{l-1}). | ||||

We now describe representations in most-significant-bit first (msb) | ||||

or least-significant-bit first (lsb) order and those in most- | ||||

significant-byte first (MSB) or least-significant-byte first (LSB) | ||||

order. | ||||

One distinguishes the following octet-string representations of | ||||

integers and field elements: | ||||

1. MSB, msb: represent field elements and integers as above, | ||||

yielding the octet string str(X_{l-1}, X_{l-2}, ..., X_1, X_0). | ||||

2. MSB, lsb: reverse the bit-order of each octet, viewed as 8-bit | ||||

string, yielding the octet string str((rev(X_{l-1}), | ||||

rev(X_{l-2}), ..., rev(X_1), rev(X_0)). | ||||

3. LSB, lsb: reverse the octet string and bit-order of each octet, | ||||

yielding the octet string str(rev(X_{0}), rev(X_{1}), ..., | ||||

rev(X_{l-2}), rev(X_{l-1})). | ||||

4. LSB, msb: reverse the octet string, yielding the octet string | ||||

str(X_{0}, X_{1}, ..., X_{l-2}, X_{l-1}). | ||||

Thus, the 2-octet string "07e3" represents the integer 2019 (=0x07e3) | ||||

in MSB/msb order, the integer 57,543 (0xe0c7) in MSB/lsb order, the | ||||

integer 51,168 (0xc7e0) in LSB/lsb order, and the integer 58,119 | ||||

(=0xe307) in LSB/msb order. | ||||

Note that, with the above data conversions, there is still some | ||||

ambiguity as to how to represent an integer or a field element as a | ||||

bit string or octet string (due to leading zeros). However, tight | ||||

representations (as defined above) are non-ambiguous. | ||||

Appendix K. Representations for Curve25519 Family Members | ||||

K.1. Wei25519 | ||||

The representation of integers, field elements, affine points, and | ||||

compressed points for the curve Wei25519 are as indicated below. | ||||

Representations are relative to the prime field GF(p), where | ||||

p=2^255-19 is one of the general domain parameters of Appendix E.3. | ||||

Each field element z of GF(p) is represented as the octet string | ||||

FE2OS(z), where one uses one the MSB/msb conventions and tight | ||||

representation, as specified in Appendix J. In particular, each | ||||

element of GF(p) is represented as a 32-byte octet string, which - | ||||

when viewed as a bit string - has the leftmost bit position set to 0. | ||||

Each affine point (X, Y) of Wei25519 is represented as the | ||||

rightconcatenation of the 32-byte octet representations for the x- | ||||

and y-coordinate of this point according to the conventions above, | ||||

i.e., it is represented as the 64-byte octet string str(FE2OS(X), | ||||

FE2OS(Y)). | ||||

For each compressed point (X, t) of Wei25519, the parity bit t (which | ||||

is an element of the field GF(2)), is represented as a 1-bit bit | ||||

string, whereas the x-coordinate X (which is an element of GF(p)), is | ||||

represented as a 32-byte octet string FE2OS(X). The result is | ||||

"squeezed", by superimposing the 1-bit representation of t on the | ||||

leftmost (unused) bit-position of the 32-byte octet representation of | ||||

X. | ||||

Each integer in the interval [0,n-1] is viewed as an element of the | ||||

prime field GF(n) and represented using MSB/msb conventions and a | ||||

tight representation. In particular, each element of GF(n) is | ||||

represented as a 32-byte octet string, which - when viewed as a bit | ||||

string - has the lefmost three bit positions set to 0. | ||||

Appendix L. Auxiliary Functions | ||||

L.1. Square Roots in GF(q) | ||||

Square roots are easy to compute in GF(q) if q = 3 (mod 4) (see | ||||

Appendix L.1.1) or if q = 5 (mod 8) (see Appendix L.1.2). Details on | ||||

how to compute square roots for other values of q are out of scope. | ||||

If square roots are easy to compute in GF(q), then so are these in | ||||

GF(q^2). | ||||

L.1.1. Square Roots in GF(q), where q = 3 (mod 4) | ||||

If y is a nonzero element of GF(q) and z:= y^{(q-3)/4}, then y is a | ||||

square in GF(q) only if y*z^2=1. If y*z^2=1, z is a square root of | ||||

1/y and y*z is a square root of y in GF(q). | ||||

L.1.2. Square Roots in GF(q), where q = 5 (mod 8) | ||||

If y is a nonzero element of GF(q) and z:=y^{z-5)/8}, then y is a | ||||

square in GF(q) only if y^2*z^4=1. | ||||

a. If y*z^2=+1, z is a square root of 1/y and y*z is a square root | ||||

of y in GF(q); | ||||

b. If y*z^2=-1, i*z is a square root of 1/y and i*y*z is a square | ||||

root of y. | ||||

Here, i is an element of GF(q) for which i^2=-1 (e.g., | ||||

i:=2^{(q-1)/4}). This field element can be precomputed. | ||||

L.2. Inversion | ||||

If y is an integer and gcd(y,n)=1, one can efficiently compute 1/y | ||||

(mod n) via the extended Euclidean Algorithm (see Section 2.2.5 of | ||||

[GECC]). One can use this algorithm as well to compute the inverse | ||||

of a nonzero element y of a prime field GF(p), since gcd(y,p)=1. | ||||

The inverse of a nonzero element y of GF(q) can be computed as | ||||

1/y:=y^{q-2} (since y^{q-1}=1). | ||||

Further details are out of scope. If inverses are easy to compute in | ||||

GF(q), then so are these in GF(q^2). | ||||

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

subsequently computing y2*z=:1/y1 and y1*z=:1/y2. | ||||

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. 107 change blocks. | ||||

347 lines changed or deleted | | 887 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/ |