draft-ietf-lwig-curve-representations-07.txt   draft-ietf-lwig-curve-representations-08.txt 
lwig R. Struik lwig R. Struik
Internet-Draft Struik Security Consultancy Internet-Draft Struik Security Consultancy
Intended status: Informational July 8, 2019 Intended status: Informational July 24, 2019
Expires: January 9, 2020 Expires: January 25, 2020
Alternative Elliptic Curve Representations Alternative Elliptic Curve Representations
draft-ietf-lwig-curve-representations-07 draft-ietf-lwig-curve-representations-08
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 January 9, 2020. This Internet-Draft will expire on January 25, 2020.
Copyright Notice Copyright Notice
Copyright (c) 2019 IETF Trust and the persons identified as the Copyright (c) 2019 IETF Trust and the persons identified as the
document authors. All rights reserved. document authors. All rights reserved.
This document is subject to BCP 78 and the IETF Trust's Legal This document is subject to BCP 78 and the IETF Trust's Legal
Provisions Relating to IETF Documents Provisions Relating to IETF Documents
(https://trustee.ietf.org/license-info) in effect on the date of (https://trustee.ietf.org/license-info) in effect on the date of
publication of this document. Please review these documents publication of this document. Please review these documents
skipping to change at page 2, line 17 skipping to change at page 2, line 17
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 . . . . . . . . 4 1. Fostering Code Reuse with New Elliptic Curves . . . . . . . . 4
2. Specification of Wei25519 . . . . . . . . . . . . . . . . . . 4 2. Specification of Wei25519 . . . . . . . . . . . . . . . . . . 4
3. Use of Representation Switches . . . . . . . . . . . . . . . 5 3. Use of Representation Switches . . . . . . . . . . . . . . . 5
4. Examples . . . . . . . . . . . . . . . . . . . . . . . . . . 5 4. Examples . . . . . . . . . . . . . . . . . . . . . . . . . . 6
4.1. Implementation of X25519 . . . . . . . . . . . . . . . . 6 4.1. Implementation of X25519 . . . . . . . . . . . . . . . . 6
4.2. Implementation of Ed25519 . . . . . . . . . . . . . . . . 6 4.2. Implementation of Ed25519 . . . . . . . . . . . . . . . . 6
4.3. Specification of ECDSA25519 . . . . . . . . . . . . . . . 7 4.3. Specification of ECDSA25519 . . . . . . . . . . . . . . . 7
4.4. Other Uses . . . . . . . . . . . . . . . . . . . . . . . 7 4.4. Other Uses . . . . . . . . . . . . . . . . . . . . . . . 7
5. Caveats . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 5. Caveats . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
6. Implementation Considerations . . . . . . . . . . . . . . . . 9 6. Implementation Considerations . . . . . . . . . . . . . . . . 9
7. Implementation Status . . . . . . . . . . . . . . . . . . . . 10 7. Implementation Status . . . . . . . . . . . . . . . . . . . . 10
8. Security Considerations . . . . . . . . . . . . . . . . . . . 11 8. Security Considerations . . . . . . . . . . . . . . . . . . . 11
9. Privacy Considerations . . . . . . . . . . . . . . . . . . . 12 9. Privacy Considerations . . . . . . . . . . . . . . . . . . . 12
10. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 12 10. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 12
skipping to change at page 3, line 48 skipping to change at page 3, line 48
J.3. Conversion between Octet Strings and Bit Strings (BS2OS, J.3. Conversion between Octet Strings and Bit Strings (BS2OS,
OS2BS) . . . . . . . . . . . . . . . . . . . . . . . . . 52 OS2BS) . . . . . . . . . . . . . . . . . . . . . . . . . 52
J.4. Conversion between Field Elements and Octet Strings J.4. Conversion between Field Elements and Octet Strings
(FE2OS, OS2FE) . . . . . . . . . . . . . . . . . . . . . 53 (FE2OS, OS2FE) . . . . . . . . . . . . . . . . . . . . . 53
J.5. Conversion between Elements of Z mod n and Octet Strings J.5. Conversion between Elements of Z mod n and Octet Strings
(ZnE2OS, OS2ZnE) . . . . . . . . . . . . . . . . . . . . 53 (ZnE2OS, OS2ZnE) . . . . . . . . . . . . . . . . . . . . 53
J.6. Ordering Conventions . . . . . . . . . . . . . . . . . . 54 J.6. Ordering Conventions . . . . . . . . . . . . . . . . . . 54
Appendix K. Representation Examples Curve25519 Family Members . 55 Appendix K. Representation Examples Curve25519 Family Members . 55
K.1. Example with Curve25519 . . . . . . . . . . . . . . . . . 55 K.1. Example with Curve25519 . . . . . . . . . . . . . . . . . 55
K.2. Example with Edwards25519 . . . . . . . . . . . . . . . . 57 K.2. Example with Edwards25519 . . . . . . . . . . . . . . . . 57
K.3. Example with Wei25519 . . . . . . . . . . . . . . . . . . 58 K.3. Example with Wei25519 . . . . . . . . . . . . . . . . . . 59
K.4. Example with Wei25519.2 . . . . . . . . . . . . . . . . . 60 K.4. Example with Wei25519.2 . . . . . . . . . . . . . . . . . 61
K.5. Example with Wei25519.-3 . . . . . . . . . . . . . . . . 61 K.5. Example with Wei25519.-3 . . . . . . . . . . . . . . . . 63
Appendix L. Auxiliary Functions . . . . . . . . . . . . . . . . 62 Appendix L. Auxiliary Functions . . . . . . . . . . . . . . . . 64
L.1. Square Roots in GF(q) . . . . . . . . . . . . . . . . . . 62 L.1. Square Roots in GF(q) . . . . . . . . . . . . . . . . . . 64
L.1.1. Square Roots in GF(q), where q = 3 (mod 4) . . . . . 62 L.1.1. Square Roots in GF(q), where q = 3 (mod 4) . . . . . 64
L.1.2. Square Roots in GF(q), where q = 5 (mod 8) . . . . . 63 L.1.2. Square Roots in GF(q), where q = 5 (mod 8) . . . . . 64
L.2. Inversion . . . . . . . . . . . . . . . . . . . . . . . . 63 L.2. Inversion . . . . . . . . . . . . . . . . . . . . . . . . 65
L.3. Mapping to Curve Points . . . . . . . . . . . . . . . . . 63 L.3. Mapping to Curve Points . . . . . . . . . . . . . . . . . 65
L.3.1. Mapping to Points of Weierstrass Curve . . . . . . . 63 L.3.1. Mapping to Points of Weierstrass Curve . . . . . . . 65
L.3.2. Mapping to Points of Montgomery Curve . . . . . . . . 64 L.3.2. Mapping to Points of Montgomery Curve . . . . . . . . 66
L.3.3. Mapping to Points of Twisted Edwards Curve . . . . . 65 L.3.3. Mapping to Points of Twisted Edwards Curve . . . . . 68
L.4. Randomized Representation of Curve Points . . . . . . . . 65 L.4. Randomized Representation of Curve Points . . . . . . . . 68
Author's Address . . . . . . . . . . . . . . . . . . . . . . . . 66 Appendix M. Curve secp256k1 and Friend . . . . . . . . . . . . . 68
M.1. Curve Definition and Alternative Representation . . . . . 68
M.2. Switching Between Representations . . . . . . . . . . . . 69
M.3. Domain Parameters . . . . . . . . . . . . . . . . . . . . 69
M.4. Isogeny Details . . . . . . . . . . . . . . . . . . . . . 71
M.4.1. Isogeny Parameters . . . . . . . . . . . . . . . . . 71
M.4.2. Dual Isogeny Parameters . . . . . . . . . . . . . . . 72
Author's Address . . . . . . . . . . . . . . . . . . . . . . . . 72
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 12, line 11 skipping to change at page 12, line 11
To prevent intra-protocol cross-instantiation attacks, ephemeral To prevent intra-protocol cross-instantiation attacks, ephemeral
private keys MUST NOT be reused between instantiations of ECDSA25519. private keys MUST NOT be reused between instantiations of ECDSA25519.
9. Privacy Considerations 9. 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.
The randomized representation described in Appendix L.4 allows random
curve points to be represented as random pairs of field elements,
thereby assisting in obfuscating the presence of these curve points
in some applications.
10. IANA Considerations 10. IANA Considerations
An object identifier is requested for curve Wei25519 and its use with An object identifier is requested for curve Wei25519 and its use with
ECDSA and co-factor ECDH, using the representation conventions of ECDSA and co-factor ECDH, using the representation conventions of
this document. this document.
There is *currently* no further IANA action required for this There is *currently* no further IANA action required for this
document. New object identifiers would be required in case one document. New object identifiers would be required in case one
wishes to specify one or more of the "offspring" protocols wishes to specify one or more of the "offspring" protocols
exemplified in Section 4.4. exemplified in Section 4.4.
skipping to change at page 15, line 47 skipping to change at page 15, line 47
DOI 10.17487/RFC8032, January 2017, DOI 10.17487/RFC8032, January 2017,
<https://www.rfc-editor.org/info/rfc8032>. <https://www.rfc-editor.org/info/rfc8032>.
[RFC8152] Schaad, J., "CBOR Object Signing and Encryption (COSE)", [RFC8152] Schaad, J., "CBOR Object Signing and Encryption (COSE)",
RFC 8152, DOI 10.17487/RFC8152, July 2017, RFC 8152, DOI 10.17487/RFC8152, July 2017,
<https://www.rfc-editor.org/info/rfc8152>. <https://www.rfc-editor.org/info/rfc8152>.
[SEC1] SEC1, "SEC 1: Elliptic Curve Cryptography, Version 2.0", [SEC1] SEC1, "SEC 1: Elliptic Curve Cryptography, Version 2.0",
Standards for Efficient Cryptography, , June 2009. Standards for Efficient Cryptography, , June 2009.
[SEC2] SEC2, "SEC 2: Elliptic Curve Cryptography, Version 2.0",
Standards for Efficient Cryptography, , January 2010.
[SP-800-56a] [SP-800-56a]
NIST SP 800-56a, "Recommendation for Pair-Wise Key NIST SP 800-56a, "Recommendation for Pair-Wise Key
Establishment Schemes Using Discrete Log Cryptography, Establishment Schemes Using Discrete Log Cryptography,
Revision 3", US Department of Commerce/National Institute Revision 3", US Department of Commerce/National Institute
of Standards and Technology, Gaithersburg, MD, April 2018. of Standards and Technology, Gaithersburg, MD, April 2018.
[SP-800-56c] [SP-800-56c]
NIST SP 800-56c, "Recommendation for Key-Derivation NIST SP 800-56c, "Recommendation for Key-Derivation
Methods in Key-Establishment Schemes, Revision 1", US Methods in Key-Establishment Schemes, Revision 1", US
Department of Commerce/National Institute of Standards and Department of Commerce/National Institute of Standards and
skipping to change at page 20, line 37 skipping to change at page 20, line 40
coefficients in GF(p) and two binary operations on this set: coefficients in GF(p) and two binary operations on this set:
polynomial addition and polynomial multiplication modulo the polynomial addition and polynomial multiplication modulo the
irreducible polynomial f(z). By definition, each element x of GF(q) 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 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 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 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 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 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 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 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 definitions of GF(p) and GF(p^1) above coincide. If m>1, then GF(q)
called a (nontrivial) extension field over GF(p). The number p is is called a (nontrivial) extension field over GF(p). The number p is
called the characteristic of GF(q). called the characteristic of GF(q).
A field element y is called a square in GF(q) if it can be expressed A field element y is called a square in GF(q) if it can be expressed
as y:=x^2 for some x in GF(q); it is called a non-square in GF(q) as y:=x^2 for some x in GF(q); it is called a non-square in GF(q)
otherwise. If y is a square in GF(q), we denote by sqrt(y) one of otherwise. If y is a square in GF(q), we denote by sqrt(y) one of
its square roots (the other one being -sqrt(y)). For methods for its square roots (the other one being -sqrt(y)). For methods for
computing square roots and inverses in GF(q) - if these exist - see computing square roots and inverses in GF(q) - if these exist - see
Appendix L.1 and Appendix L.2, respectively. For methods for mapping Appendix L.1 and Appendix L.2, respectively. For methods for mapping
a nonzero field element that is not a square in GF(q) to a point of a a nonzero field element that is not a square in GF(q) to a point of a
curve, see Appendix L.3. curve, see Appendix L.3.
skipping to change at page 28, line 23 skipping to change at page 28, line 23
h1 4 h1 4
n1 14474011154664524427946373126085988481603263447650325797860494125 n1 14474011154664524427946373126085988481603263447650325797860494125
407373907997 407373907997
(=2^{253} - 0x29bdf3bd 45ef39ac b024c634 b9eba7e3) (=2^{253} - 0x29bdf3bd 45ef39ac b024c634 b9eba7e3)
Montgomery curve-specific parameters (for Curve25519): Montgomery curve-specific parameters (for Curve25519):
A 486662 A 486662 (=0x076d06)
B 1 B 1 (=0x01)
Gu 9 (=0x9) Gu 9 (=0x09)
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)
skipping to change at page 34, line 37 skipping to change at page 34, line 37
Appendix F.4.) Under this isogenous mapping, the base point (GX,GY) Appendix F.4.) Under this isogenous mapping, the base point (GX,GY)
of Wei25519 corresponds to the base point (G3X,G3Y) of Wei25519.-3. of Wei25519 corresponds to the base point (G3X,G3Y) of Wei25519.-3.
The dual isogeny maps the affine point (X',Y') of Wei25519.-3 to the The dual isogeny maps the affine point (X',Y') of Wei25519.-3 to the
affine point (X,Y):=(u'(X1)/w'(X1)^2,Y1*v'(X1)/w'(X1)^3) of Wei25519, affine point (X,Y):=(u'(X1)/w'(X1)^2,Y1*v'(X1)/w'(X1)^3) of Wei25519,
where (X1,Y1)=(X'/t^2,Y'/t^3) and where u', v', and w' are the where (X1,Y1)=(X'/t^2,Y'/t^3) and where u', v', and w' are the
polynomials with coefficients in GF(p) as defined in Appendix H.2, polynomials with coefficients in GF(p) as defined in Appendix H.2,
while mapping the point at infinity O of Wei25519.-3 to the point at while mapping the point at infinity O of Wei25519.-3 to the point at
infinity O of Wei25519. Under this dual isogenous mapping, the base infinity O of Wei25519. Under this dual isogenous mapping, the base
point (G3X, G3Y) of Wei25519.-3 corresponds to a multiple of the base point (G3X, G3Y) of Wei25519.-3 corresponds to a multiple of the base
point (GX, GY) of Wei25519, where this multiple is l=47 (the degree point (GX, GY) of Wei25519, where this multiple is l=47 (the degree
of the isogeny; see the description in Appendix F.3). Note that this of the isogeny; see the description in Appendix F.4). Note that this
isogenous map (and its dual) primarily involves the evaluation of isogenous map (and its dual) primarily involves the evaluation of
three fixed polynomials involving the x-coordinate, which takes three fixed polynomials involving the x-coordinate, which takes
roughly 140 modular multiplications (or less than 5-10% relative roughly 140 modular multiplications (or less than 5-10% relative
incremental cost compared to the cost of an elliptic curve scalar incremental cost compared to the cost of an 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
skipping to change at page 37, line 32 skipping to change at page 37, line 32
24 0x677073fed43ab291e496f798fbcf217bac3f014e35d0c2fa07f041ae746a04d7 24 0x677073fed43ab291e496f798fbcf217bac3f014e35d0c2fa07f041ae746a04d7
25 0x22225388e76f9688c7d4053b50ba41d0d8b71a2f21da8353d98472243ef50170 25 0x22225388e76f9688c7d4053b50ba41d0d8b71a2f21da8353d98472243ef50170
26 0x66930b3dffdd3995a2502cef790d78b091c875192d8074bb5d5639f736400555 26 0x66930b3dffdd3995a2502cef790d78b091c875192d8074bb5d5639f736400555
27 0x79eb677c5e36971e8d64d56ebc0dedb4e9b7dd2d7b01343ebbd4d358d376e490 27 0x79eb677c5e36971e8d64d56ebc0dedb4e9b7dd2d7b01343ebbd4d358d376e490
28 0x48a204c2ca6d8636e9994842605bd648b91b637844e38d6c7dd707edce8256e2 28 0x48a204c2ca6d8636e9994842605bd648b91b637844e38d6c7dd707edce8256e2
29 0xfb3529b0d4b9ce2d70760f33e8ce997a58999718e9277caf48623d27ae6a788 29 0x0fb3529b0d4b9ce2d70760f33e8ce997a58999718e9277caf48623d27ae6a788
30 0x4352604bffd0c7d7a9ed898a2c6e7cf2512ffb89407271ba1f2c2d0ead8cc5aa 30 0x4352604bffd0c7d7a9ed898a2c6e7cf2512ffb89407271ba1f2c2d0ead8cc5aa
31 0x6667697b29785fb6f0bd5e04d828991a5fe525370216f347ec767a26e7aac936 31 0x6667697b29785fb6f0bd5e04d828991a5fe525370216f347ec767a26e7aac936
32 0x9fc950b083c56dbd989badf9887255e203c879f123a7cb28901e50aea6d64dc 32 0x09fc950b083c56dbd989badf9887255e203c879f123a7cb28901e50aea6d64dc
33 0x41e51b51b5caadd1c15436bbf37596a1d7288a5f495d6b5b1ae66f8b2942b31d 33 0x41e51b51b5caadd1c15436bbf37596a1d7288a5f495d6b5b1ae66f8b2942b31d
34 0x73b59fec709aa1cabd429e981c6284822a8b7b07620c831ab41fd31d5cf7430 34 0x073b59fec709aa1cabd429e981c6284822a8b7b07620c831ab41fd31d5cf7430
35 0x67e9b88e9a1bfbc2554107d67d814986f1b09c3107a060cba21c019a2d5dc848 35 0x67e9b88e9a1bfbc2554107d67d814986f1b09c3107a060cba21c019a2d5dc848
36 0x6881494a1066ca176c5e174713786040affb4268b19d2abf28ef4293429f89c1 36 0x6881494a1066ca176c5e174713786040affb4268b19d2abf28ef4293429f89c1
37 0x5f4d30502ff1e1ccd624e6f506569454ab771869d7483e26afc09dea0c5ccd3d 37 0x5f4d30502ff1e1ccd624e6f506569454ab771869d7483e26afc09dea0c5ccd3d
38 0x2a814cfc5859bca51e539c159955cbe729a58978b52329575d09bc6c3bf97ad 38 0x02a814cfc5859bca51e539c159955cbe729a58978b52329575d09bc6c3bf97ad
39 0x1313c8aaae20d6f4397f0d8b19e52cfcdf8d8e10fba144aec1778fd10ddf4e9c 39 0x1313c8aaae20d6f4397f0d8b19e52cfcdf8d8e10fba144aec1778fd10ddf4e9c
40 0x7008d38f434b98953a996d4cc79fcbef9502411dcdf92005f725cea7ce82ad47 40 0x7008d38f434b98953a996d4cc79fcbef9502411dcdf92005f725cea7ce82ad47
41 0x5a74d1296aaaa245ffb848f434531fa3ba9e5cb9098a7091d36c2777d4cf5a13 41 0x5a74d1296aaaa245ffb848f434531fa3ba9e5cb9098a7091d36c2777d4cf5a13
42 0x4bd3b700606397083f8038177bdaa1ac6edbba0447537582723cae0fd29341a9 42 0x4bd3b700606397083f8038177bdaa1ac6edbba0447537582723cae0fd29341a9
43 0x573453fb2b093016f3368356c786519d54ed05f5372c01723b4da520597ec217 43 0x573453fb2b093016f3368356c786519d54ed05f5372c01723b4da520597ec217
44 0x77f5c605bdb3a30d7d9c8840fce38650910d4418eed707a212c8927f41c2c812 44 0x77f5c605bdb3a30d7d9c8840fce38650910d4418eed707a212c8927f41c2c812
45 0x16d6b9f7ff57ca32350057de1204cc6d69d4ef1b255dfef8080118e2fef6ace3 45 0x16d6b9f7ff57ca32350057de1204cc6d69d4ef1b255dfef8080118e2fef6ace3
46 0x34e8595832a4021f8b5744014c6b4f7da7df0d0329e8b6b4d44c8fadad6513b7 46 0x34e8595832a4021f8b5744014c6b4f7da7df0d0329e8b6b4d44c8fadad6513b7
47 0x1 47 0x01
H.1.2. Coefficients of v(x) H.1.2. Coefficients of v(x)
0 0xf9f5eb7134e6f8dafa30c45afa58d7bfc6d4e3ccbb5de87b562fd77403972b2 0 0x0f9f5eb7134e6f8dafa30c45afa58d7bfc6d4e3ccbb5de87b562fd77403972b2
1 0x36c2dcd9e88f0d2d517a15fc453a098bbbb5a05eb6e8da906fae418a4e1a13f7 1 0x36c2dcd9e88f0d2d517a15fc453a098bbbb5a05eb6e8da906fae418a4e1a13f7
2 0xb40078302c24fa394a834880d5bf46732ca1b4894172fb7f775821276f558b3 2 0x0b40078302c24fa394a834880d5bf46732ca1b4894172fb7f775821276f558b3
3 0x53dd8e2234573f7f3f7df11e90a7bdd7b75d807f9712f521d4fb18af59aa5f26 3 0x53dd8e2234573f7f3f7df11e90a7bdd7b75d807f9712f521d4fb18af59aa5f26
4 0x6d4d7bb08de9061988a8cf6ff3beb10e933d4d2fbb8872d256a38c74c8c2ceda 4 0x6d4d7bb08de9061988a8cf6ff3beb10e933d4d2fbb8872d256a38c74c8c2ceda
5 0x71bfe5831b30e28cd0fbe1e9916ab2291c6beacc5af08e2c9165c632e61dd2f5 5 0x71bfe5831b30e28cd0fbe1e9916ab2291c6beacc5af08e2c9165c632e61dd2f5
6 0x7c524f4d17ff2ee88463da012fc12a5b67d7fb5bd0ab59f4bbf162d76be1c89c 6 0x7c524f4d17ff2ee88463da012fc12a5b67d7fb5bd0ab59f4bbf162d76be1c89c
7 0x758183d5e07878d3364e3fd4c863a5dc1fe723f48c4ab4273fc034f5454d59a4 7 0x758183d5e07878d3364e3fd4c863a5dc1fe723f48c4ab4273fc034f5454d59a4
8 0x1eb41ef2479444ecdccbc200f64bde53f434a02b6c3f485d32f14da6aa7700e1 8 0x1eb41ef2479444ecdccbc200f64bde53f434a02b6c3f485d32f14da6aa7700e1
9 0x1490f3851f016cc3cf8a1e3c16a53317253d232ed425297531b560d70770315c 9 0x1490f3851f016cc3cf8a1e3c16a53317253d232ed425297531b560d70770315c
10 0x9bc43131964e46d905c3489c9d465c3abbd26eab9371c10e429b36d4b86469c 10 0x09bc43131964e46d905c3489c9d465c3abbd26eab9371c10e429b36d4b86469c
11 0x5f27c173d94c7a413a288348d3fc88daa0bcf5af8f436a47262050f240e9be3b 11 0x5f27c173d94c7a413a288348d3fc88daa0bcf5af8f436a47262050f240e9be3b
12 0x1d20010ec741aaa393cd19f0133b35f067adab0d105babe75fe45c8ba2732ceb 12 0x1d20010ec741aaa393cd19f0133b35f067adab0d105babe75fe45c8ba2732ceb
13 0x1b3c669ae49b86be2f0c946a9ff6c48e44740d7d9804146915747c3c025996a 13 0x01b3c669ae49b86be2f0c946a9ff6c48e44740d7d9804146915747c3c025996a
14 0x24c6090f79ec13e3ae454d8f0f98e0c30a8938180595f79602f2ba013b3c10db 14 0x24c6090f79ec13e3ae454d8f0f98e0c30a8938180595f79602f2ba013b3c10db
15 0x4650c5b5648c6c43ac75a2042048c699e44437929268661726e7182a31b1532f 15 0x4650c5b5648c6c43ac75a2042048c699e44437929268661726e7182a31b1532f
16 0x957a835fb8bac3360b5008790e4c1f3389589ba74c8e8bf648b856ba7f22ba5 16 0x0957a835fb8bac3360b5008790e4c1f3389589ba74c8e8bf648b856ba7f22ba5
17 0x1cd1300bc534880f95c7885d8df04a82bd54ed3e904b0749e0e3f8cb3240c7c7 17 0x1cd1300bc534880f95c7885d8df04a82bd54ed3e904b0749e0e3f8cb3240c7c7
18 0x760b486e0d3c6ee0833b34b64b7ebc846055d4d1e0beeb6aedd5132399ada0ea 18 0x760b486e0d3c6ee0833b34b64b7ebc846055d4d1e0beeb6aedd5132399ada0ea
19 0x1c666846c63965ef7edf519d6ada738f2b676ae38ff1f4621533373931b3220e 19 0x1c666846c63965ef7edf519d6ada738f2b676ae38ff1f4621533373931b3220e
20 0x365055118b38d4bc0df86648044affea2ef33e9a392ad336444e7d15e45585d1 20 0x365055118b38d4bc0df86648044affea2ef33e9a392ad336444e7d15e45585d1
21 0x736487bde4b555abfccd3ea7ddcda98eda0d7c879664117dee906a88bc551194 21 0x736487bde4b555abfccd3ea7ddcda98eda0d7c879664117dee906a88bc551194
skipping to change at page 39, line 50 skipping to change at page 39, line 50
32 0x17cffb496c64bb89d91c8c082f4c288c3c87feabd6b08591fe5a92216c094637 32 0x17cffb496c64bb89d91c8c082f4c288c3c87feabd6b08591fe5a92216c094637
33 0x648ff88155969f54c955a1834ad227b93062bb191170dd8c4d759f79ad5da250 33 0x648ff88155969f54c955a1834ad227b93062bb191170dd8c4d759f79ad5da250
34 0x73e50900b89e5f295052b97f9d0c9edb0fc7d97b7fa5e3cfeefe33dd6a9cb223 34 0x73e50900b89e5f295052b97f9d0c9edb0fc7d97b7fa5e3cfeefe33dd6a9cb223
35 0x6afcb2f2ffe6c08508477aa4956cbd3dc864257f5059685adf2c68d4f2338f00 35 0x6afcb2f2ffe6c08508477aa4956cbd3dc864257f5059685adf2c68d4f2338f00
36 0x372fd49701954c1b8f00926a8cb4b157d4165b75d53fa0476716554bf101b74c 36 0x372fd49701954c1b8f00926a8cb4b157d4165b75d53fa0476716554bf101b74c
37 0x334ed41325f3724ff8becbf2b3443fea6d30fa543d1ca13188aceb2bdaf5f4e 37 0x0334ed41325f3724ff8becbf2b3443fea6d30fa543d1ca13188aceb2bdaf5f4e
38 0x70e629c95a94e8e1b3974acb25e18ba42f8d5991786f0931f650c283adfe82fd 38 0x70e629c95a94e8e1b3974acb25e18ba42f8d5991786f0931f650c283adfe82fd
39 0x738a625f4c62d3d645f1274e09ab344e72d441f3c0e82989d3e21e19212f23f3 39 0x738a625f4c62d3d645f1274e09ab344e72d441f3c0e82989d3e21e19212f23f3
40 0x7093737294b29f21522f5664a9941c9b476f75d443b647bd2c777040bcd12a6a 40 0x7093737294b29f21522f5664a9941c9b476f75d443b647bd2c777040bcd12a6a
41 0xa996bad5863d821ccb8b89fa329ddbe5317a46bcb32552db396bea933765436 41 0x0a996bad5863d821ccb8b89fa329ddbe5317a46bcb32552db396bea933765436
42 0x2da237e3741b75dd0264836e7ef634fc0bc36ab187ebc790591a77c257b06f53 42 0x2da237e3741b75dd0264836e7ef634fc0bc36ab187ebc790591a77c257b06f53
43 0x1902f3daa86fa4f430b57212924fdc9e40f09e809f3991a0b3a10ab186c50ee5 43 0x1902f3daa86fa4f430b57212924fdc9e40f09e809f3991a0b3a10ab186c50ee5
44 0x12baffec1bf20c921afd3cdf67a7f1d87c00d5326a3e5c83841593c214dadcb1 44 0x12baffec1bf20c921afd3cdf67a7f1d87c00d5326a3e5c83841593c214dadcb1
45 0x6460f5a68123cb9e7bc1289cd5023c0c9ccd2d98eea24484fb3825b59dcd09aa 45 0x6460f5a68123cb9e7bc1289cd5023c0c9ccd2d98eea24484fb3825b59dcd09aa
46 0x2c7d63a868ffc9f0fd034f821d84736c5bc33325ce98aba5f0d95fef6f230ec8 46 0x2c7d63a868ffc9f0fd034f821d84736c5bc33325ce98aba5f0d95fef6f230ec8
47 0x756e0063349a702db7406984c285a9b6bfba48177950d4361d8efa77408dc860 47 0x756e0063349a702db7406984c285a9b6bfba48177950d4361d8efa77408dc860
48 0x37f3e30032b21e0279738e0a2b689625447831a2ccf15c638672da9aa7255ae 48 0x037f3e30032b21e0279738e0a2b689625447831a2ccf15c638672da9aa7255ae
49 0x1107c0dbe15d6ca9e790768317a40bcf23c80f1841f03ca79dd3e3ef4ea1ae30 49 0x1107c0dbe15d6ca9e790768317a40bcf23c80f1841f03ca79dd3e3ef4ea1ae30
50 0x61ff7f25721d6206041c59a788316b09e05135a2aad94d539c65daa68b302cc2 50 0x61ff7f25721d6206041c59a788316b09e05135a2aad94d539c65daa68b302cc2
51 0x5dbfe346cbd0d61b9a3b5c42ec0518d3ae81cabcc32245060d7b0cd982b8d071 51 0x5dbfe346cbd0d61b9a3b5c42ec0518d3ae81cabcc32245060d7b0cd982b8d071
52 0x4b6595e8501e9ec3e75f46107d2fd76511764efca179f69196eb45c0aa6fade3 52 0x4b6595e8501e9ec3e75f46107d2fd76511764efca179f69196eb45c0aa6fade3
53 0x72d17a5aa7bd8a2540aa9b02d9605f2a714f44abfb4c35d518b7abc39b477870 53 0x72d17a5aa7bd8a2540aa9b02d9605f2a714f44abfb4c35d518b7abc39b477870
54 0x658d8c134bac37729ec40d27d50b637201abbf1ab4157316358953548c49cf22 54 0x658d8c134bac37729ec40d27d50b637201abbf1ab4157316358953548c49cf22
55 0x36ac53b9118581ace574d5a08f9647e6a916f92dda684a4dbc405e2646b0243f 55 0x36ac53b9118581ace574d5a08f9647e6a916f92dda684a4dbc405e2646b0243f
56 0x1917a98f387d1e323e84a0f02d53307b1dd949e1a27b0de14514f89d9c0ef4b6 56 0x1917a98f387d1e323e84a0f02d53307b1dd949e1a27b0de14514f89d9c0ef4b6
57 0x21573434fde7ce56e8777c79539479441942dba535ade8ecb77763f7eb05d797 57 0x21573434fde7ce56e8777c79539479441942dba535ade8ecb77763f7eb05d797
58 0xe0bf482dc40884719bea5503422b603f3a8edb582f52838caa6eaab6eeac7ef 58 0x0e0bf482dc40884719bea5503422b603f3a8edb582f52838caa6eaab6eeac7ef
59 0x3b0471eb53bd83e14fbc13928fe1691820349a963be8f7e9815848a53d03f5eb 59 0x3b0471eb53bd83e14fbc13928fe1691820349a963be8f7e9815848a53d03f5eb
60 0x1e92cb067b24a729c42d3abb7a1179c577970f0ab3e6b0ce8d66c5b8f7001262 60 0x1e92cb067b24a729c42d3abb7a1179c577970f0ab3e6b0ce8d66c5b8f7001262
61 0x74ea885c1ebed6f74964262402432ef184c42884fceb2f8dba3a9d67a1344dd7 61 0x74ea885c1ebed6f74964262402432ef184c42884fceb2f8dba3a9d67a1344dd7
62 0x433ebce2ce9b0dc314425cfc2b234614d3c34f2c9da9fff4fdddd1ce242d035b 62 0x433ebce2ce9b0dc314425cfc2b234614d3c34f2c9da9fff4fdddd1ce242d035b
63 0x33ac69e6be858dde7b83a9ff6f11de443128b39cec6e410e8d3b570e405ff896 63 0x33ac69e6be858dde7b83a9ff6f11de443128b39cec6e410e8d3b570e405ff896
64 0xdab71e2ae94e6530a501ed8cf3df26731dd1d41cd81578341e12dca3cb71aa3 64 0x0dab71e2ae94e6530a501ed8cf3df26731dd1d41cd81578341e12dca3cb71aa3
65 0x537f58d52d18ce5b1d5a6bd3a420e796e64173491ad43dd4d1083a7dcc7dd201 65 0x537f58d52d18ce5b1d5a6bd3a420e796e64173491ad43dd4d1083a7dcc7dd201
66 0x49c2f6afa93fdcc4e0f8128a8b06da4c75049be14edf3e103821ab604c60f8ae 66 0x49c2f6afa93fdcc4e0f8128a8b06da4c75049be14edf3e103821ab604c60f8ae
67 0x10a333eabd6135aeaa3f5f5f7e73d102e4fd7e4bf0902fc55b00da235fa1ad08 67 0x10a333eabd6135aeaa3f5f5f7e73d102e4fd7e4bf0902fc55b00da235fa1ad08
68 0xf5c86044bf6032f5102e601f2a0f73c7bce9384bedd120f3e72d78484179d9c 68 0x0f5c86044bf6032f5102e601f2a0f73c7bce9384bedd120f3e72d78484179d9c
69 0x1 69 0x01
H.1.3. Coefficients of w(x) H.1.3. Coefficients of w(x)
0 0x3da24d42421264f30939ff00203880f2b017eb3fecf8933ae61e18df8c8ba116 0 0x3da24d42421264f30939ff00203880f2b017eb3fecf8933ae61e18df8c8ba116
1 0x457f20bc393cdc9a66848ce174e2fa41d77e6dbae05a317a1fb6e3ae78760f8 1 0x0457f20bc393cdc9a66848ce174e2fa41d77e6dbae05a317a1fb6e3ae78760f8
2 0x7f608a2285c480d5c9592c435431fae94695beef79d770bb6d029c1d10a53295 2 0x7f608a2285c480d5c9592c435431fae94695beef79d770bb6d029c1d10a53295
3 0x3832accc520a485100a0a1695792465142a5572bed1b2e50e1f8f662ac7289bb 3 0x3832accc520a485100a0a1695792465142a5572bed1b2e50e1f8f662ac7289bb
4 0x2df1b0559e31b328eb34beedd5e537c3f4d7b9befb0749f75d6d0d866d26fbaa 4 0x2df1b0559e31b328eb34beedd5e537c3f4d7b9befb0749f75d6d0d866d26fbaa
5 0x25396820381d04015a9f655ddd41c74303ded05d54a7750e2f58006659adda28 5 0x25396820381d04015a9f655ddd41c74303ded05d54a7750e2f58006659adda28
6 0x6fa070a70ca2bc6d4d0795fb28d4990b2cc80cd72d48b603a8ac8c8268bef6a6 6 0x6fa070a70ca2bc6d4d0795fb28d4990b2cc80cd72d48b603a8ac8c8268bef6a6
7 0x27f488578357388b20fbc7503328e1d10de602b082b3c7b8ceb33c29fea7a0d2 7 0x27f488578357388b20fbc7503328e1d10de602b082b3c7b8ceb33c29fea7a0d2
8 0x15776851a7cabcfe84c632118306915c0c15c75068a47021968c7438d46076e6 8 0x15776851a7cabcfe84c632118306915c0c15c75068a47021968c7438d46076e6
9 0x101565b08a9af015c172fb194b940a4df25c4fb1d85f72d153efc79131d45e8f 9 0x101565b08a9af015c172fb194b940a4df25c4fb1d85f72d153efc79131d45e8f
10 0x196b0ffbf92f3229fea1dac0d74591b905ccaab6b83f905ee813ee8449f8a62c 10 0x196b0ffbf92f3229fea1dac0d74591b905ccaab6b83f905ee813ee8449f8a62c
11 0x1f55784691719f765f04ee9051ec95d5deb42ae45405a9d87833855a6d95a94 11 0x01f55784691719f765f04ee9051ec95d5deb42ae45405a9d87833855a6d95a94
12 0x628858f79cca86305739d084d365d5a9e56e51a4485d253ae3f2e4a379fa8aff 12 0x628858f79cca86305739d084d365d5a9e56e51a4485d253ae3f2e4a379fa8aff
13 0x4a842dcd943a80d1e6e1dab3622a8c4d390da1592d1e56d1c14c4d3f72dd01a5 13 0x4a842dcd943a80d1e6e1dab3622a8c4d390da1592d1e56d1c14c4d3f72dd01a5
14 0xf3bfc9cb17a1125f94766a4097d0f1018963bc11cb7bc0c7a1d94d65e282477 14 0x0f3bfc9cb17a1125f94766a4097d0f1018963bc11cb7bc0c7a1d94d65e282477
15 0x1c4bd70488c4882846500691fa7543b7ef694446d9c3e3b4707ea2c99383e53c 15 0x1c4bd70488c4882846500691fa7543b7ef694446d9c3e3b4707ea2c99383e53c
16 0x2d7017e47b24b89b0528932c4ade43f09091b91db0072e6ebdc5e777cb215e35 16 0x2d7017e47b24b89b0528932c4ade43f09091b91db0072e6ebdc5e777cb215e35
17 0x781d69243b6c86f59416f91f7decaca93eab9cdc36a184191810c56ed85e0fdc 17 0x781d69243b6c86f59416f91f7decaca93eab9cdc36a184191810c56ed85e0fdc
18 0x5f20526f4177357da40a18da054731d442ad2a5a4727322ba8ed10d32eca24fb 18 0x5f20526f4177357da40a18da054731d442ad2a5a4727322ba8ed10d32eca24fb
19 0x33e4cab64ed8a00d8012104fe8f928e6173c428eff95bbbe569ea46126a4f3cd 19 0x33e4cab64ed8a00d8012104fe8f928e6173c428eff95bbbe569ea46126a4f3cd
20 0x50555b6f07e308d33776922b6566829d122e19b25b7bbacbb0a4b1a7dc40192 20 0x050555b6f07e308d33776922b6566829d122e19b25b7bbacbb0a4b1a7dc40192
21 0x533fa4bf1e2a2aae2f979065fdbb5b667ede2f85543fddbba146aa3a4ef2d281 21 0x533fa4bf1e2a2aae2f979065fdbb5b667ede2f85543fddbba146aa3a4ef2d281
22 0x5a742cac1952010fc5aba200a635a7bed3ef868194f45b5a6a2647d6d6b289d2 22 0x5a742cac1952010fc5aba200a635a7bed3ef868194f45b5a6a2647d6d6b289d2
23 0x1 23 0x01
H.2. Dual Isogeny Parameters H.2. Dual Isogeny Parameters
H.2.1. Coefficients of u'(x) H.2.1. Coefficients of u'(x)
0 0xf0eddb584a20aaac8f1419efdd02a5cca77b21e4cfae78c49b5127d98bc5882 0 0x0f0eddb584a20aaac8f1419efdd02a5cca77b21e4cfae78c49b5127d98bc5882
1 0x7115e60d44a58630417df33dd45b8a546fa00b79fea3b2bdc449694bade87c0a 1 0x7115e60d44a58630417df33dd45b8a546fa00b79fea3b2bdc449694bade87c0a
2 0xb3f3a6f3c445c7dc1f91121275414e88c32ff3f367ba0edad4d75b7e7b94b65 2 0x0b3f3a6f3c445c7dc1f91121275414e88c32ff3f367ba0edad4d75b7e7b94b65
3 0x1eb31bb333d7048b87f2b3d4ec76d69035927b41c30274368649c87c52e1ab30 3 0x1eb31bb333d7048b87f2b3d4ec76d69035927b41c30274368649c87c52e1ab30
4 0x552c886c2044153e280832264066cce2a7da1127dc9720e2a380e9d37049ac64 4 0x552c886c2044153e280832264066cce2a7da1127dc9720e2a380e9d37049ac64
5 0x4504f27908db2e1f5840b74ae42445298755d9493141f5417c02f04d47797dda 5 0x4504f27908db2e1f5840b74ae42445298755d9493141f5417c02f04d47797dda
6 0x82c242cce1eb19698a4fa30b5affe64e5051c04ae8b52cb68d89ee85222e628 6 0x082c242cce1eb19698a4fa30b5affe64e5051c04ae8b52cb68d89ee85222e628
7 0x480473406add76cf1d77661b3ff506c038d9cdd5ad6e1ea41969430bb876d223 7 0x480473406add76cf1d77661b3ff506c038d9cdd5ad6e1ea41969430bb876d223
8 0x25f47bb506fba80c79d1763365fa9076d4c4cb6644f73ed37918074397e88588 8 0x25f47bb506fba80c79d1763365fa9076d4c4cb6644f73ed37918074397e88588
9 0x10f13ed36eab593fa20817f6bb70cac292e18d300498f6642e35cbdf772f0855 9 0x10f13ed36eab593fa20817f6bb70cac292e18d300498f6642e35cbdf772f0855
10 0x7d28329d695fb3305620f83a58df1531e89a43c7b3151d16f3b60a8246c36ade 10 0x7d28329d695fb3305620f83a58df1531e89a43c7b3151d16f3b60a8246c36ade
11 0x2c5ec8c42b16dc6409bdd2c7b4ffe9d65d7209e886badbd5f865dec35e4ab4a 11 0x02c5ec8c42b16dc6409bdd2c7b4ffe9d65d7209e886badbd5f865dec35e4ab4a
12 0x7f4f33cd50255537e6cde15a4a327a5790c37e081802654b56c956434354e133 12 0x7f4f33cd50255537e6cde15a4a327a5790c37e081802654b56c956434354e133
13 0x7d30431a121d9240c761998cf83d228237e80c3ef5c7191ec9617208e0ab8cec 13 0x7d30431a121d9240c761998cf83d228237e80c3ef5c7191ec9617208e0ab8cec
14 0x4d2a7d6609610c1deed56425a4615b92f70a507e1079b2681d96a2b874cf0630 14 0x4d2a7d6609610c1deed56425a4615b92f70a507e1079b2681d96a2b874cf0630
15 0x74676df60a9906901d1dc316c639ff6ae0fcdb02b5571d4b83fc2eedcd2936a8 15 0x74676df60a9906901d1dc316c639ff6ae0fcdb02b5571d4b83fc2eedcd2936a8
16 0x22f8212219aca01410f06eb234ed53bd5b8fbe7c08652b8002bcd1ea3cdae387 16 0x22f8212219aca01410f06eb234ed53bd5b8fbe7c08652b8002bcd1ea3cdae387
17 0x7edb04449565d7c566b934a87fadade5515f23bda1ce25daa19fff0c6a5ccc2f 17 0x7edb04449565d7c566b934a87fadade5515f23bda1ce25daa19fff0c6a5ccc2f
18 0x106ef71aa3aa34e8ecf4c07a67d03f0949d7d015ef2c1e32eb698dd3bec5a18c 18 0x106ef71aa3aa34e8ecf4c07a67d03f0949d7d015ef2c1e32eb698dd3bec5a18c
19 0x17913eb705db126ac3172447bcd811a62744d505ad0eea94cfcfdde5ca7428 19 0x0017913eb705db126ac3172447bcd811a62744d505ad0eea94cfcfdde5ca7428
20 0x2cc793e6d3b592dcf5472057a991ff1a5ab43b4680bb34c0f5faffc5307827c1 20 0x2cc793e6d3b592dcf5472057a991ff1a5ab43b4680bb34c0f5faffc5307827c1
21 0x6dafcc0b16f98300cddb5e0a7d7ff04a0e73ca558c54461781d5a5ccb1ea0122 21 0x6dafcc0b16f98300cddb5e0a7d7ff04a0e73ca558c54461781d5a5ccb1ea0122
22 0x7e418891cf222c021b0ae5f5232b9c0dc8270d4925a13174a0f0ac5e7a4c8045 22 0x7e418891cf222c021b0ae5f5232b9c0dc8270d4925a13174a0f0ac5e7a4c8045
23 0x76553bd26fecb019ead31142684789fea7754c2dc9ab9197c623f45d60749058 23 0x76553bd26fecb019ead31142684789fea7754c2dc9ab9197c623f45d60749058
24 0x693efb3f81086043656d81840902b6f3a9a4b0e8f2a5a5edf5ce1c7f50a3898e 24 0x693efb3f81086043656d81840902b6f3a9a4b0e8f2a5a5edf5ce1c7f50a3898e
25 0x46c630eac2b86d36f18a061882b756917718a359f44752a5caf41be506788921 25 0x46c630eac2b86d36f18a061882b756917718a359f44752a5caf41be506788921
26 0x1dcfa01773628753bc6f448ac11be8a3bffa0011b9284967629b827e064f614 26 0x01dcfa01773628753bc6f448ac11be8a3bffa0011b9284967629b827e064f614
27 0x8430b5b97d49b0938d1f66ecb9d2043025c6eec624f8f02042b9621b2b5cb19 27 0x08430b5b97d49b0938d1f66ecb9d2043025c6eec624f8f02042b9621b2b5cb19
28 0x66f66a6669272d47d3ec1efea36ee01d4a54ed50e9ec84475f668a5a9850f9be 28 0x66f66a6669272d47d3ec1efea36ee01d4a54ed50e9ec84475f668a5a9850f9be
29 0x539128823b5ef3e87e901ab22f06d518a9bad15f5d375b49fe1e893ab38b1345 29 0x539128823b5ef3e87e901ab22f06d518a9bad15f5d375b49fe1e893ab38b1345
30 0x2bd01c49d6fff22c213a8688924c10bf29269388a69a08d7f326695b3c213931 30 0x2bd01c49d6fff22c213a8688924c10bf29269388a69a08d7f326695b3c213931
31 0x3f7bea1baeccea3980201dc40d67c26db0e3b15b5a19b6cdac6de477aa717ac1 31 0x3f7bea1baeccea3980201dc40d67c26db0e3b15b5a19b6cdac6de477aa717ac1
32 0x6e0a72d94867807f7150fcb1233062f911b46e2ad11a3eac3c6c4c91e0f4a3fa 32 0x6e0a72d94867807f7150fcb1233062f911b46e2ad11a3eac3c6c4c91e0f4a3fa
skipping to change at page 44, line 10 skipping to change at page 44, line 10
35 0x66d185401c1d2d0b84fcf6758a6a985bf9695651271c08f4b69ce89175fb7b34 35 0x66d185401c1d2d0b84fcf6758a6a985bf9695651271c08f4b69ce89175fb7b34
36 0x2673fb8c65bc4fe41905381093429a2601c46a309c03077ca229bac7d6ccf239 36 0x2673fb8c65bc4fe41905381093429a2601c46a309c03077ca229bac7d6ccf239
37 0x1ce4d895ee601918a080de353633c82b75a3f61e8247763767d146554dd2f862 37 0x1ce4d895ee601918a080de353633c82b75a3f61e8247763767d146554dd2f862
38 0x18efa6c72fa908347547a89028a44f79f22542baa588601f2b3ed25a5e56d27c 38 0x18efa6c72fa908347547a89028a44f79f22542baa588601f2b3ed25a5e56d27c
39 0x53de362e2f8ff220f8921620a71e8faa1aa57f8886fcbb6808fa3a5560570543 39 0x53de362e2f8ff220f8921620a71e8faa1aa57f8886fcbb6808fa3a5560570543
40 0xdc29a73b97f08aa8774911474e651130ed364e8d8cffd4a80dee633aacecc47 40 0x0dc29a73b97f08aa8774911474e651130ed364e8d8cffd4a80dee633aacecc47
41 0x4e7eb8584ae4de525389d1e9300fc4480b3d9c8a5a45ecfbe33311029d8f6b99 41 0x4e7eb8584ae4de525389d1e9300fc4480b3d9c8a5a45ecfbe33311029d8f6b99
42 0x6c3cba4aa9229550fa82e1cfaee4b02f2c0cb86f79e0d412b8e32b00b7959d80 42 0x6c3cba4aa9229550fa82e1cfaee4b02f2c0cb86f79e0d412b8e32b00b7959d80
43 0x5a9d104ae585b94af68eeb16b1349776b601f97b7ce716701645b1a75b68dcf3 43 0x5a9d104ae585b94af68eeb16b1349776b601f97b7ce716701645b1a75b68dcf3
44 0x754e014b5e87af035b3d5fe6fb49f4631e32549f6341c6693c5172a6388e273e 44 0x754e014b5e87af035b3d5fe6fb49f4631e32549f6341c6693c5172a6388e273e
45 0x6710d8265118e22eaceba09566c86f642ab42da58c435083a353eaa12d866c39 45 0x6710d8265118e22eaceba09566c86f642ab42da58c435083a353eaa12d866c39
46 0x6e88ac659ce146c369f8b24c3a49f8dca547827250cf7963a455851cfc4f8d22 46 0x6e88ac659ce146c369f8b24c3a49f8dca547827250cf7963a455851cfc4f8d22
47 0x971eb5f253356cd1fde9fb21f4a4902aa5b8d804a2b57ba775dc130181ae2e8 47 0x0971eb5f253356cd1fde9fb21f4a4902aa5b8d804a2b57ba775dc130181ae2e8
H.2.2. Coefficients of v'(x) H.2.2. Coefficients of v'(x)
0 0x43c9b67cc5b16e167b55f190db61e44d48d813a7112910f10e3fd8da85d61d3 0 0x043c9b67cc5b16e167b55f190db61e44d48d813a7112910f10e3fd8da85d61d3
1 0x72046db07e0e7882ff3f0f38b54b45ca84153be47a7fd1dd8f6402e17c47966f 1 0x72046db07e0e7882ff3f0f38b54b45ca84153be47a7fd1dd8f6402e17c47966f
2 0x1593d97b65a070b6b3f879fe3dc4d1ef03c0e781c997111d5c1748f956f1ffc0 2 0x1593d97b65a070b6b3f879fe3dc4d1ef03c0e781c997111d5c1748f956f1ffc0
3 0x54e5fec076b8779338432bdc5a449e36823a0a7c905fd37f232330b026a143a0 3 0x54e5fec076b8779338432bdc5a449e36823a0a7c905fd37f232330b026a143a0
4 0x46328dd9bc336e0873abd453db472468393333fbf2010c6ac283933216e98038 4 0x46328dd9bc336e0873abd453db472468393333fbf2010c6ac283933216e98038
5 0x25d0c64de1dfe1c6d5f5f2d98ab637d8b39bcf0d886a23dabac18c80d7eb03ce 5 0x25d0c64de1dfe1c6d5f5f2d98ab637d8b39bcf0d886a23dabac18c80d7eb03ce
skipping to change at page 44, line 50 skipping to change at page 44, line 50
6 0x3a175c46b2cd8e2b313dde2d5f3097b78114a6295f283cf58a33844b0c8d8b34 6 0x3a175c46b2cd8e2b313dde2d5f3097b78114a6295f283cf58a33844b0c8d8b34
7 0x5cf4e6f745bdd61181a7d1b4db31dc4c30c84957f63cdf163bee5e466a7a8d38 7 0x5cf4e6f745bdd61181a7d1b4db31dc4c30c84957f63cdf163bee5e466a7a8d38
8 0x639071c39b723eea51cfd870478331d60396b31f39a593ebdd9b1eb543875283 8 0x639071c39b723eea51cfd870478331d60396b31f39a593ebdd9b1eb543875283
9 0x7ea8f895dcd85fc6cb2b58793789bd9246e62fa7a8c7116936876f4d8dff869b 9 0x7ea8f895dcd85fc6cb2b58793789bd9246e62fa7a8c7116936876f4d8dff869b
10 0x503818acb535bcaacf8ad44a83c213a9ce83af7c937dc9b3e5b6efedc0a7428c 10 0x503818acb535bcaacf8ad44a83c213a9ce83af7c937dc9b3e5b6efedc0a7428c
11 0xe815373920ec3cbf3f8cae20d4389d367dc4398e01691244af90edc3e6d42b8 11 0x0e815373920ec3cbf3f8cae20d4389d367dc4398e01691244af90edc3e6d42b8
12 0x7e4b23e1e0b739087f77910cc635a92a3dc184a791400cbceae056c19c853815 12 0x7e4b23e1e0b739087f77910cc635a92a3dc184a791400cbceae056c19c853815
13 0x145322201db4b5ec0a643229e07c0ab7c36e4274745689be2c19cfa8a702129d 13 0x145322201db4b5ec0a643229e07c0ab7c36e4274745689be2c19cfa8a702129d
14 0xfde79514935d9b40f52e33429621a200acc092f6e5dec14b49e73f2f59c780d 14 0x0fde79514935d9b40f52e33429621a200acc092f6e5dec14b49e73f2f59c780d
15 0x37517ac5c04dc48145a9d6e14803b8ce9cb6a5d01c6f0ad1b04ff3353d02d815 15 0x37517ac5c04dc48145a9d6e14803b8ce9cb6a5d01c6f0ad1b04ff3353d02d815
16 0x58ae96b8eefe9e80f24d3b886932fe3c27aaea810fa189c702f93987c8c97854 16 0x58ae96b8eefe9e80f24d3b886932fe3c27aaea810fa189c702f93987c8c97854
17 0x6f6402c90fa379096d5f436035bebc9d29302126e9b117887abfa7d4b3c5709a 17 0x6f6402c90fa379096d5f436035bebc9d29302126e9b117887abfa7d4b3c5709a
18 0x1dbdf2b9ec09a8defeb485cc16ea98d0d45c5b9877ff16bd04c0110d2f64961 18 0x01dbdf2b9ec09a8defeb485cc16ea98d0d45c5b9877ff16bd04c0110d2f64961
19 0x53c51706af523ab5b32291de6c6b1ee7c5cbd0a5b317218f917b12ff38421452 19 0x53c51706af523ab5b32291de6c6b1ee7c5cbd0a5b317218f917b12ff38421452
20 0x1b1051c7aec7d37a349208e3950b679d14e39f979db4fcd7b50d7d27dc918650 20 0x1b1051c7aec7d37a349208e3950b679d14e39f979db4fcd7b50d7d27dc918650
21 0x1547e8d36262d5434cfb029cdd29385353124c3c35b1423c6cca1f87910b305b 21 0x1547e8d36262d5434cfb029cdd29385353124c3c35b1423c6cca1f87910b305b
22 0x198efe984efc817835e28f704d41e4583a1e2398f7ce14045c4575d0445c6ce7 22 0x198efe984efc817835e28f704d41e4583a1e2398f7ce14045c4575d0445c6ce7
23 0x492276dfe9588ee5cd9f553d990f377935d721822ecd0333ce2eb1d4324d539c 23 0x492276dfe9588ee5cd9f553d990f377935d721822ecd0333ce2eb1d4324d539c
skipping to change at page 46, line 12 skipping to change at page 46, line 12
35 0x47adb6aecc1949f2dc9f01206cc23eb4a0c29585d475dd24dc463c5087809298 35 0x47adb6aecc1949f2dc9f01206cc23eb4a0c29585d475dd24dc463c5087809298
36 0x30d39e8b0c451a8fcf3d2abab4b86ffa374265abbe77c5903db4c1be8cec7672 36 0x30d39e8b0c451a8fcf3d2abab4b86ffa374265abbe77c5903db4c1be8cec7672
37 0x28cf47b39112297f0daeaa621f8e777875adc26f35dec0ba475c2ee148562b41 37 0x28cf47b39112297f0daeaa621f8e777875adc26f35dec0ba475c2ee148562b41
38 0x36199723cc59867e2e309fe9941cd33722c807bb2d0a06eeb41de93f1b93f2f5 38 0x36199723cc59867e2e309fe9941cd33722c807bb2d0a06eeb41de93f1b93f2f5
39 0x5cdeb1f2ee1c7d694bdd884cb1c5c22de206684e1cafb8d3adb9a33cb85e19a2 39 0x5cdeb1f2ee1c7d694bdd884cb1c5c22de206684e1cafb8d3adb9a33cb85e19a2
40 0xf6e6b3fc54c2d25871011b1499bb0ef015c6d0da802ae7eccf1d8c3fb73856c 40 0x0f6e6b3fc54c2d25871011b1499bb0ef015c6d0da802ae7eccf1d8c3fb73856c
41 0xc1422c98b672414344a9c05492b926f473f05033b9f85b8788b4bb9a080053c 41 0x0c1422c98b672414344a9c05492b926f473f05033b9f85b8788b4bb9a080053c
42 0x19a8527de35d4faacb00184e0423962247319703a815eecf355f143c2c18f17f 42 0x19a8527de35d4faacb00184e0423962247319703a815eecf355f143c2c18f17f
43 0x7812dc3313e6cf093da4617f06062e8e8969d648dfe6b5c331bccd58eb428383 43 0x7812dc3313e6cf093da4617f06062e8e8969d648dfe6b5c331bccd58eb428383
44 0x61e537180c84c79e1fd2d4f9d386e1c4f0442247605b8d8904d122ee7ef9f7be 44 0x61e537180c84c79e1fd2d4f9d386e1c4f0442247605b8d8904d122ee7ef9f7be
45 0x544d8621d05540576cfc9b58a3dab19145332b88eb0b86f4c15567c37205adf9 45 0x544d8621d05540576cfc9b58a3dab19145332b88eb0b86f4c15567c37205adf9
46 0x11be3ef96e6e07556356b51e2479436d9966b7b083892b390caec22a117aa48e 46 0x11be3ef96e6e07556356b51e2479436d9966b7b083892b390caec22a117aa48e
47 0x205cda31289cf75ab0759c14c43cb30f7287969ea3dc0d5286a3853a4d403187 47 0x205cda31289cf75ab0759c14c43cb30f7287969ea3dc0d5286a3853a4d403187
48 0x48d8fc6934f4f0a99f0f2cc59010389e2a0b20d6909bfcf8d7d0249f360acdc 48 0x048d8fc6934f4f0a99f0f2cc59010389e2a0b20d6909bfcf8d7d0249f360acdc
49 0x42cecc6d9bdca6d382e97fcea46a79c3eda2853091a8f399a2252115bf9a1454 49 0x42cecc6d9bdca6d382e97fcea46a79c3eda2853091a8f399a2252115bf9a1454
50 0x117d41b24f2f69cb3270b359c181607931f62c56d070bbd14dc9e3f9ab1432e 50 0x0117d41b24f2f69cb3270b359c181607931f62c56d070bbd14dc9e3f9ab1432e
51 0x7c51564c66f68e2ad4ce6ea0d68f920fafa375376709c606c88a0ed44207aa1e 51 0x7c51564c66f68e2ad4ce6ea0d68f920fafa375376709c606c88a0ed44207aa1e
52 0x48f25191fc8ac7d9f21adf6df23b76ccbca9cb02b815acdbebfa3f4eddc71b34 52 0x48f25191fc8ac7d9f21adf6df23b76ccbca9cb02b815acdbebfa3f4eddc71b34
53 0x4fc21a62c4688de70e28ad3d5956633fc9833bc7be09dc7bc500b7fae1e1c9a8 53 0x4fc21a62c4688de70e28ad3d5956633fc9833bc7be09dc7bc500b7fae1e1c9a8
54 0x1f23f25be0912173c3ef98e1c9990205a69d0bf2303d201d27a5499247f06789 54 0x1f23f25be0912173c3ef98e1c9990205a69d0bf2303d201d27a5499247f06789
55 0x3131495618a0ac4cb11a702f3f8bab66c4fa1066d0a741af3c92d5c246edd579 55 0x3131495618a0ac4cb11a702f3f8bab66c4fa1066d0a741af3c92d5c246edd579
56 0xd93fe40faa53913638e497328a1b47603cb062c7afc9e96278603f29fd11fd4 56 0x0d93fe40faa53913638e497328a1b47603cb062c7afc9e96278603f29fd11fd4
57 0x6b348bc59e984c91d696d1e3c3cfae44021f06f74798c787c355437fb696093d 57 0x6b348bc59e984c91d696d1e3c3cfae44021f06f74798c787c355437fb696093d
58 0x65af00e73043edcb479620c8b48098b89809d577a4071c8e33e8678829138b8a 58 0x65af00e73043edcb479620c8b48098b89809d577a4071c8e33e8678829138b8a
59 0x5e62ffb032b2ddb06591f86a46a18effd5d6ecf3f129bb2bacfd51a3739a98b6 59 0x5e62ffb032b2ddb06591f86a46a18effd5d6ecf3f129bb2bacfd51a3739a98b6
60 0x62c974ef3593fc86f7d78883b8727a2f7359a282cbc0196948e7a793e60ce1a1 60 0x62c974ef3593fc86f7d78883b8727a2f7359a282cbc0196948e7a793e60ce1a1
61 0x204d708e3f500aad64283f753e7d9bab976aa42a4ca1ce5e9d2264639e8b1110 61 0x204d708e3f500aad64283f753e7d9bab976aa42a4ca1ce5e9d2264639e8b1110
62 0xa90f0059da81a012e9d0a756809fab2ce61cb45965d4d1513a06227783ee4ea 62 0x0a90f0059da81a012e9d0a756809fab2ce61cb45965d4d1513a06227783ee4ea
63 0x39fa55971c9e833f61139c39e243d40869fd7e8a1417ee4e7719dd2dd242766f 63 0x39fa55971c9e833f61139c39e243d40869fd7e8a1417ee4e7719dd2dd242766f
64 0x22677c1e659caa324f0c74a013921facf62d0d78f273563145cc1ddccfcc4421 64 0x22677c1e659caa324f0c74a013921facf62d0d78f273563145cc1ddccfcc4421
65 0x3468cf6df7e93f7ff1fe1dd7e180a89dec3ed4f72843b4ea8a8d780011a245b2 65 0x3468cf6df7e93f7ff1fe1dd7e180a89dec3ed4f72843b4ea8a8d780011a245b2
66 0x68f75a0e2210f52a90704ed5f511918d1f6bcfcd26b462cc4975252369db6e9d 66 0x68f75a0e2210f52a90704ed5f511918d1f6bcfcd26b462cc4975252369db6e9d
67 0x6220c0699696e9bcab0fe3a80d437519bd2bdf3caef665e106b2dd47585ddd9f 67 0x6220c0699696e9bcab0fe3a80d437519bd2bdf3caef665e106b2dd47585ddd9f
skipping to change at page 47, line 44 skipping to change at page 47, line 44
4 0x57f0a593459732eef11d2e2f7085bf9adf534879ba56f7afd17c4a40d3d3477b 4 0x57f0a593459732eef11d2e2f7085bf9adf534879ba56f7afd17c4a40d3d3477b
5 0x4da04e912f145c8d1e5957e0a9e44cca83e74345b38583b70840bdfdbd0288ed 5 0x4da04e912f145c8d1e5957e0a9e44cca83e74345b38583b70840bdfdbd0288ed
6 0x7cc9c3a51a3767d9d37c6652c349adc09bfe477d99f249a2a7bc803c1c5f39ed 6 0x7cc9c3a51a3767d9d37c6652c349adc09bfe477d99f249a2a7bc803c1c5f39ed
7 0x425d7e58b8adf87eebf445b424ba308ee7880228921651995a7eab548180ad49 7 0x425d7e58b8adf87eebf445b424ba308ee7880228921651995a7eab548180ad49
8 0x48156db5c99248234c09f43fedf509005943d3d5f5d7422621617467b06d314f 8 0x48156db5c99248234c09f43fedf509005943d3d5f5d7422621617467b06d314f
9 0xd837dbbd1af32d04e2699cb026399c1928472aa1a7f0a1d3afd24bc9923456a 9 0x0d837dbbd1af32d04e2699cb026399c1928472aa1a7f0a1d3afd24bc9923456a
10 0x5b8806e0f924e67c1f207464a9d025758c078b43ddc0ea9afe9993641e5650be 10 0x5b8806e0f924e67c1f207464a9d025758c078b43ddc0ea9afe9993641e5650be
11 0x29c91284e5d14939a6c9bc848908bd9df1f8346c259bbd40f3ed65182f3a2f39 11 0x29c91284e5d14939a6c9bc848908bd9df1f8346c259bbd40f3ed65182f3a2f39
12 0x25550b0f3bceef18a6bf4a46c45bf1b92f22a76d456bfdf19d07398c80b0f946 12 0x25550b0f3bceef18a6bf4a46c45bf1b92f22a76d456bfdf19d07398c80b0f946
13 0x495d289b1db16229d7d4630cb65d52500256547401f121a9b09fb8e82cf01953 13 0x495d289b1db16229d7d4630cb65d52500256547401f121a9b09fb8e82cf01953
14 0x718c8c610ea7048a370eabfd9888c633ee31dd70f8bcc58361962bb08619963e 14 0x718c8c610ea7048a370eabfd9888c633ee31dd70f8bcc58361962bb08619963e
skipping to change at page 48, line 24 skipping to change at page 48, line 24
18 0x18b6b49c5650fb82e36e25fd4eb6decfdd40b46c37425e6597c7444a1b6afb4e 18 0x18b6b49c5650fb82e36e25fd4eb6decfdd40b46c37425e6597c7444a1b6afb4e
19 0x6868305b4f40654460aad63af3cb9151ab67c775eaac5e5df90d3aea58dee141 19 0x6868305b4f40654460aad63af3cb9151ab67c775eaac5e5df90d3aea58dee141
20 0x16bc90219a36063a22889db810730a8b719c267d538cd28fa7c0d04f124c8580 20 0x16bc90219a36063a22889db810730a8b719c267d538cd28fa7c0d04f124c8580
21 0x3628f9cf1fbe3eb559854e3b1c06a4cd6a26906b4e2d2e70616a493bba2dc574 21 0x3628f9cf1fbe3eb559854e3b1c06a4cd6a26906b4e2d2e70616a493bba2dc574
22 0x64abcc6759f1ce1ab57d41e17c2633f717064e35a7233a6682f8cf8e9538afec 22 0x64abcc6759f1ce1ab57d41e17c2633f717064e35a7233a6682f8cf8e9538afec
23 0x1 23 0x01
Appendix I. Point Compression Appendix I. Point Compression
Point compression allows a shorter representation of affine points of Point compression allows a shorter representation of affine points of
an elliptic curve by exploiting algebraic relationships between the an elliptic curve by exploiting algebraic relationships between the
coordinate values based on the defining equation of the curve in coordinate values based on the defining equation of the curve in
question. Point decompression refers to the reverse process, where question. Point decompression refers to the reverse process, where
one tries and recover the affine point from its compressed one tries and recover the affine point from its compressed
representation and information on the domain parameters of the curve. representation and information on the domain parameters of the curve.
Consequently, point compression followed by point decompression is Consequently, point compression followed by point decompression is
skipping to change at page 49, line 34 skipping to change at page 49, line 34
are two solutions, viz. Y=sqrt(alpha) and -Y. If alpha is a nonzero are two solutions, viz. Y=sqrt(alpha) and -Y. If alpha is a nonzero
element of GF(q), one can uniquely recover the Y-coordinate for which element of GF(q), one can uniquely recover the Y-coordinate for which
par(Y):=t and, thereby, the point P:=(X, Y). This is also the case par(Y):=t and, thereby, the point P:=(X, Y). This is also the case
if alpha=0 and t=0, in which case Y=0 and the point P has order two. if alpha=0 and t=0, in which case Y=0 and the point P has order two.
However, if alpha=0 and t=1, the ordered pair (X, t) does not However, if alpha=0 and t=1, the ordered pair (X, t) does not
correspond to the outcome of the point compression function. correspond to the outcome of the point compression function.
We extend the definition of the point compression function to all We extend the definition of the point compression function to all
points of the curve W_{a,b}, by associating the (non-affine) point at points of the curve W_{a,b}, by associating the (non-affine) point at
infinity O with any ordered pair compr(O):=(X,0), where X is any infinity O with any ordered pair compr(O):=(X,0), where X is any
element of GF(q) for which alpha:=X^3+a*X+b is a non-square in GF(q), element of GF(q) for which alpha:=X^3+a*X+b is not a square in GF(q),
and recover this point accordingly. In this case, the point at and recover this point accordingly. In this case, the point at
infinity O can be represented by any ordered pair (X,0) of elements infinity O can be represented by any ordered pair (X,0) of elements
of GF(q) for which X^3+a*X+b is a non-square in GF(q). Note that of GF(q) for which X^3+a*X+b is not a square in GF(q). Note that
this ordered pair does not satisfy the defining equation of the curve this ordered pair does not satisfy the defining equation of the curve
in question. An application may fix a specific suitable value of X in question. An application may fix a specific suitable value of X
or choose multiple such values and use this to encode additonal or choose multiple such values and use this to encode additonal
information. Further details are out of scope. information. Further details are out of scope.
I.2. Point Compression for Montgomery Curves I.2. Point Compression for Montgomery Curves
If P:=(u, v) is an affine point of the Montgomery curve M_{A,B} If P:=(u, v) is an affine point of the Montgomery curve M_{A,B}
defined over the field GF(q), then so is -P:=(u, -v). Since the defined over the field GF(q), then so is -P:=(u, -v). Since the
defining equation B*v^2=u^3+A*u^2+u has at most two solutions with defining equation B*v^2=u^3+A*u^2+u has at most two solutions with
skipping to change at page 57, line 7 skipping to change at page 57, line 7
The scalar representation and (squeezed) point representation The scalar representation and (squeezed) point representation
illustrated above are consistent with the representations specified illustrated above are consistent with the representations specified
in [RFC7748], except that in [RFC7748] only an affine point's in [RFC7748], except that in [RFC7748] only an affine point's
u-coordinate is represented (i.e., the v-coordinate of any point is u-coordinate is represented (i.e., the v-coordinate of any point is
always implicitly assumed to have an even value) and that the always implicitly assumed to have an even value) and that the
representation of the point at infinity is not specified. Another representation of the point at infinity is not specified. Another
difference is that [RFC7748] allows non-unique representations of difference is that [RFC7748] allows non-unique representations of
some elements of GF(p), whereas our representation conventions do not some elements of GF(p), whereas our representation conventions do not
(since tight). (since tight).
A randomized representation (t1, t2) of the point k*Pm in tight LSB/
msb order is given by
t1 409531317901122685707535715924445398426503483189854716584
37762538294289253464
(=0x5844b232 8c4586dc 62f593c5 599c2a8c e61ba893 bb052de6
77510a42 b3a68a5a)
t2 451856098332889407421278004628150814449259902023388533929
08848927625430980881
(=0x11598452 e65138dc ce948d7e d8f46a18 b640722c 8e170957
751b7729 1b26e663),
where this representation is defined in Appendix L.4 and uses the
mapping of Appendix L.3.2 with the default square root function.
K.2. Example with Edwards25519 K.2. Example with Edwards25519
Pe=(x, y), k*Pe=(x1, y1), and (k+1)*Pe=(x2, y2) with Edwards25519: Pe=(x, y), k*Pe=(x1, y1), and (k+1)*Pe=(x2, y2) with Edwards25519:
x 25301662348702136092602268236183361085863932475593120475382959053 x 25301662348702136092602268236183361085863932475593120475382959053
365387223252 365387223252
(=0x37f03bc0 1070ed12 d3218f8b ba1abb74 fd6b94eb 62033d09 (=0x37f03bc0 1070ed12 d3218f8b ba1abb74 fd6b94eb 62033d09
83851e21 d6a460d4). 83851e21 d6a460d4).
skipping to change at page 58, line 22 skipping to change at page 58, line 40
of the x-coordinate of the point of Edwards25519 in question (which, of the x-coordinate of the point of Edwards25519 in question (which,
in this case, are zero and one, respectively, since x is even and x1 in this case, are zero and one, respectively, since x is even and x1
is odd). See Appendix I.3 and Appendix J for further detail on is odd). See Appendix I.3 and Appendix J for further detail on
(squeezed) point compression. (squeezed) point compression.
The scalar representation and (squeezed) point representation The scalar representation and (squeezed) point representation
illustrated above are fully consistent with the representations illustrated above are fully consistent with the representations
specified in [RFC8032]. Note that, contrary to [RFC7748], [RFC8032] specified in [RFC8032]. Note that, contrary to [RFC7748], [RFC8032]
requires unique representations of all elements of GF(p). requires unique representations of all elements of GF(p).
A randomized representation (t1, t2) of the point k*Pe in tight LSB/
lsb order is given by
t1 577913017083163641949634219017190182170288776648725395935
97750427519399254040
(=0x181a32c5 10e06dbc ea321882 f3519055 535e289e 8faac654
82e26f61 aded23fe)
t2 454881407940919718426608573125377401686255068210624245884
05479716220480287974
(=0x672e36c5 ae353073 cdfac343 e8297b05 1b010d0f 5b1016db
dd4baf54 28068926),
where this representation is defined in Appendix L.4 and uses the
mapping of Appendix L.3.3 with the default square root function and
underlying isomorphic mapping between Edwards25519 and Curve25519 of
Appendix E.2.
K.3. Example with Wei25519 K.3. Example with Wei25519
Pw=(X, Y), k*Pw=(X1, Y1), and (k+1)*Pw=(X2, Y2) with Wei25519: Pw=(X, Y), k*Pw=(X1, Y1), and (k+1)*Pw=(X2, Y2) with Wei25519:
X 14428294459702615171094958724191825368445920488283965295163094662 X 14428294459702615171094958724191825368445920488283965295163094662
783879239338 783879239338
(=0x1fe62011 89e0801e f1debed7 456a3dc7 94d3ac0b 55202fe7 (=0x1fe62011 89e0801e f1debed7 456a3dc7 94d3ac0b 55202fe7
2a41cf12 629e56aa). 2a41cf12 629e56aa).
skipping to change at page 60, line 18 skipping to change at page 61, line 7
reverse procedure is uniquely defined, since elements of GF(p) have a reverse procedure is uniquely defined, since elements of GF(p) have a
unique fixed-size representation. The (squeezed) compressed format unique fixed-size representation. The (squeezed) compressed format
repr(Pw) corresponds to the SEC1-compliant compressed format by repr(Pw) corresponds to the SEC1-compliant compressed format by
extracting the parity bit t from the leftmost bit of the leftmost extracting the parity bit t from the leftmost bit of the leftmost
octet of repr(Pw), replacing the bit position by the value zero, and octet of repr(Pw), replacing the bit position by the value zero, and
prepending the octet string with 0x02 or 0x03, depending on whether prepending the octet string with 0x02 or 0x03, depending on whether
t=0 or t=1, respectively, where the reverse procedure is uniquely t=0 or t=1, respectively, where the reverse procedure is uniquely
defined, since GF(p) is a 255-bit prime field. For further details, defined, since GF(p) is a 255-bit prime field. For further details,
see [SEC1]. see [SEC1].
A randomized representation (t1, t2) of the point k*Pw in tight MSB/
msb order is given by
t1 446363445988889734093446280484122107283059206243307955388
84223152228795899590
(=0x62af4697 4dd469ac 96c64809 c16c8517 b6a0cee5 40ba0e2e
6dd2b36a fcc75ec6)
t2 213890166610228613105792710708385961712211281744756216061
11930888059603107561
(=0x2f49c121 8fed7912 031157ee ae066507 a972320b 6180e267
4025b006 2e67bee9),
where this representation is defined in Appendix L.4 and uses the
mapping of Appendix L.3.1 with the default square root function.
K.4. Example with Wei25519.2 K.4. Example with Wei25519.2
Pw2=(X, Y), k*Pw2=(X1, Y1), and (k+1)*Pw2=(X2, Y2) with Wei25519.2: Pw2=(X, Y), k*Pw2=(X1, Y1), and (k+1)*Pw2=(X2, Y2) with Wei25519.2:
X 17830493209951148331008014701079988862634531394137235438571836389 X 17830493209951148331008014701079988862634531394137235438571836389
227198459763 227198459763
(=0x276bb396 d766b695 bfe60ab1 3c0260dd c09f5bcf 7b3ca47c (=0x276bb396 d766b695 bfe60ab1 3c0260dd c09f5bcf 7b3ca47c
f21c8672 d1ecaf73). f21c8672 d1ecaf73).
skipping to change at page 61, line 29 skipping to change at page 62, line 35
repr(k*Pw2) =0x0e7986d2 e94354ab 8abd8806 3154536a 4dcf8e6e 65557183 repr(k*Pw2) =0x0e7986d2 e94354ab 8abd8806 3154536a 4dcf8e6e 65557183
e242192d 3b87f4e8, e242192d 3b87f4e8,
where the leftmost bit of the leftmost octet indicates the parity of where the leftmost bit of the leftmost octet indicates the parity of
the Y-coordinate of the point of Wei25519.2 in question (which, in the Y-coordinate of the point of Wei25519.2 in question (which, in
this case, are both zero, since Y and Y1 are even). See this case, are both zero, since Y and Y1 are even). See
Appendix Appendix I.1 and Appendix J for further detail on (squeezed) Appendix Appendix I.1 and Appendix J for further detail on (squeezed)
point compression. point compression.
A randomized representation (t1, t2) of the point k*Pw2 in tight MSB/
msb order is given by
t1 416669672354928148679758598803660112405431159793278161879
36189858804289581274
(=0x5c1eaaef 80f9d4af 33c119fc c99acd58 f81e7d69 999c7048
e4043a77 87a930da)
t2 361115271162391608083096560179337391059615651279123199921
18531180247832114098
(=0x4fd66668 e7174775 de44c852 92df8cfe b9832ef8 2570b3b8
fe5ec21a b2d4b3b2),
where this representation is defined in Appendix L.4 and uses the
mapping of Appendix L.3.1 with the default square root function.
K.5. Example with Wei25519.-3 K.5. Example with Wei25519.-3
Pw3=(X, Y), k*Pw3=(X1, Y1), and (k+1)*Pw3=(X2, Y2) with Wei25519.-3: Pw3=(X, Y), k*Pw3=(X1, Y1), and (k+1)*Pw3=(X2, Y2) with Wei25519.-3:
X 14780197759513083469009623947734627174363231692126610860256057394 X 14780197759513083469009623947734627174363231692126610860256057394
455099634096 455099634096
(=0x20ad4ba4 612f0586 221787b0 d01ba46c d1d8cd5a 0348ef00 (=0x20ad4ba4 612f0586 221787b0 d01ba46c d1d8cd5a 0348ef00
eb4c9272 03ca71b0). eb4c9272 03ca71b0).
skipping to change at page 62, line 37 skipping to change at page 64, line 14
repr(k*Pw3) =0x0a78a650 a39995ef dcf4de88 940d4ce9 5b2ca35c c5d70e06 repr(k*Pw3) =0x0a78a650 a39995ef dcf4de88 940d4ce9 5b2ca35c c5d70e06
63b8455e 2e04e65c, 63b8455e 2e04e65c,
where the leftmost bit of the leftmost octet indicates the parity of where the leftmost bit of the leftmost octet indicates the parity of
the Y-coordinate of the point of Wei25519.-3 in question (which, in the Y-coordinate of the point of Wei25519.-3 in question (which, in
this case, are one and zero, respectively, since Y is odd and Y1 is this case, are one and zero, respectively, since Y is odd and Y1 is
even). See Appendix I.1 and Appendix J for further detail on even). See Appendix I.1 and Appendix J for further detail on
(squeezed) point compression. (squeezed) point compression.
A randomized representation (t1, t2) of the point k*Pw3 in tight MSB/
msb order is given by
t1 573714937613596601525680684642155667097217474964816246889
88981227297409008259
(=0x7ed71d5f 566d2259 99bdb404 bfb9d6cf d2e86ccb 1894d4a6
c75e3c69 e5eb0283)
t2 269945781324580189815142015663892935722419453863927287235
57891665397640090729
(=0x3bae63c8 70f60de0 c2e35f94 d24220f1 bb6efd00 37625869
f84923de ff4c5469),
where this representation is defined in Appendix L.4 and uses the
mapping of Appendix L.3.1 with the default square root function.
Appendix L. Auxiliary Functions Appendix L. Auxiliary Functions
L.1. Square Roots in GF(q) L.1. Square Roots in GF(q)
Square roots are easy to compute in GF(q) if q = 3 (mod 4) (see 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 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. 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 If square roots are easy to compute in GF(q), then so are these in
GF(q^2). GF(q^2).
skipping to change at page 63, line 43 skipping to change at page 65, line 38
The inverses of two nonzero elements y1 and y2 of GF(q) can be The inverses of two nonzero elements y1 and y2 of GF(q) can be
computed by first computing the inverse z of y1*y2 and by computed by first computing the inverse z of y1*y2 and by
subsequently computing y2*z=:1/y1 and y1*z=:1/y2. subsequently computing y2*z=:1/y1 and y1*z=:1/y2.
L.3. Mapping to Curve Points L.3. Mapping to Curve Points
One can map elements of GF(q) that are not a square in GF(q) to One can map elements of GF(q) that are not a square in GF(q) to
points of a Weierstrass curve (see Appendix L.3.1), to points of a points of a Weierstrass curve (see Appendix L.3.1), to points of a
Montgomery curve (see Appendix L.3.2), or to points of a twisted Montgomery curve (see Appendix L.3.2), or to points of a twisted
Edwards curve (see Appendix L.3.3), under some mild conditions on the Edwards curve (see Appendix L.3.3), under some mild conditions on the
domain parameters. Details on mappings that apply if these domain parameters. Full details on mappings that apply if these
conditions are not satisfied are out of scope. conditions are not satisfied are out of scope.
L.3.1. Mapping to Points of Weierstrass Curve L.3.1. Mapping to Points of Weierstrass Curve
The description below assumes that the domain parameters a and b of The description below assumes that the domain parameters a and b of
the Weierstrass curve W_{a,b} are nonzero. For ease of exposition, the Weierstrass curve W_{a,b} are nonzero. For ease of exposition,
we define f(z):=z^3+a*z+b. (Note that for an affine point (X,Y) of we define f(z):=z^3+a*z+b. (Note that for an affine point (X,Y) of
W_{a,b} one has Y^2=f(X).) W_{a,b} one has Y^2=f(X).)
If t is an element of GF(q) that is not a square in GF(q) and that is If t is an element of GF(q) that is not a square in GF(q) and that is
unequal to -1, then the element X:=(-b/a)*(1+1/(t+t^2)) is the unique unequal to -1, then the element X:=(-b/a)*(1+1/(t+t^2)) is the unique
solution of the equation f(t*X)=t^3*f(X). Consequently, either X or solution of the equation f(t*X)=t^3*f(X) and is nonzero.
X':=t*X is the x-coordinate of an affine point of W{a,b}, depending Consequently, either X or X':=t*X is the x-coordinate of an affine
on whether f(X) is a square in GF(q). point of W{a,b}, depending on whether f(X) is a square in GF(q).
a. If f(X) is a square in GF(q) and Y:=sqrt(f(X)) then t is mapped a. If f(X) is a square in GF(q) and Y:=sqrt(f(X)), then t is mapped
to the point P(t):=(X, Y); to the point P(t):=(X, Y);
b. If f(X) is not a square in GF(q) and Y':=sqrt(f(X')), then t is b. If f(X) is not a square in GF(q) and Y':=sqrt(f(X')), then t is
mapped to the point P(t):=(X', -Y'). mapped to the point P(t):=(X', -Y').
Formally, this mapping is not properly defined, since a nonzero Formally, this mapping is not properly defined, since a nonzero
square y:=x^2 in GF(q) has two solutions, viz. x and -x; it is square y:=x^2 in GF(q) has two solutions, viz. x and -x; it is
properly defined, however, if one designates for each element in properly defined, however, if one designates for each element in
GF(q) that is a square in GF(q) precisely one square root as "the" GF(q) that is a square in GF(q) precisely one square root as "the"
square root of this element. Note that always picking the square square root of this element. Note that always picking the square
root with zero parity (see Appendix I) satisfies this condition, as root with zero parity (see Appendix I) satisfies this condition
does using one of the square root functions specified in (henceforth called the default square root function).
Appendix L.1.
If -1 is not a square in GF(q), this element is mapped to the point If -1 is not a square in GF(q), this element is mapped to the point
at infinity O of W_{a,b}. at infinity O of W_{a,b}.
The set of points of W_{a,b} that arises this way has size roughly The set of points of W_{a,b} that arises this way has size roughly
3/8 of the order of the curve and each such point arises as image of 3/8 of the order of the curve and each such point arises as image of
one or two t values. Further details are out of scope. one or two t values. Further details are out of scope.
NOTE 1: If -1 is not a square in GF(q), the mapping above yields the
point at infinity for t=-1. One can modify this mapping to always
yield an affine point, by mapping the element -1 to, e.g., the base
point G of W_{a,b} and leaving the remainder of the mapping the same.
Suitability of such a modification is application-specific. Details
are out of scope.
NOTE 2: The description above assumes that the domain parameters a
and b of the Weierstrass curve are nonzero. If this is not the case,
one can often find an isogenous curve W_{a',b'} for which the domain
parameters a' and b' are nonzero. If so, one can map elements of
GF(q) that are not a square in GF(q) to points of W_{a,b} via
function composition, where one uses the mapping above to arrive at a
point of W_{a',b'} and where one subsequently uses the dual isogeny
from W_{a',b'} to W_{a,b} to arrive at a point of W_{a,b}. As an
example, one can show that if a is zero and -4*b is a cube in GF(q)
(such as is the case with, e.g., the "BitCoin" curve secp256k1
[SEC2]), this curve is 3-isogenous to a curve with this property and
the strategy above applies (for an example with secp256k1, see
Appendix M). Further details are out of scope.
L.3.2. Mapping to Points of Montgomery Curve L.3.2. Mapping to Points of Montgomery Curve
The description below assumes that the domain parameter A of the The description below assumes that the domain parameter A of the
Montgomery curve M_{A,B} is nonzero. For ease of exposition, we Montgomery curve M_{A,B} is nonzero. For ease of exposition, we
define f(z):=z^3+A*z^2+z. (Note that for an affine point (u,v) of define f(z):=z^3+A*z^2+z. (Note that for an affine point (u,v) of
M_{A,B} one has B*v^2=f(u).) M_{A,B} one has B*v^2=f(u).)
If t is an element of GF(q) that is not a square in GF(q) and that is If t is an element of GF(q) that is not a square in GF(q) and that is
unequal to -1, then the element u:=-(1+1/t)/A is the unique solution unequal to -1, then the element u:=-(1+1/t)/A is the unique nonzero
of the equation f(t*u)=t^3*f(u). Consequently, either u or u':=t*u solution of the equation f(t*u)=t^3*f(u). Consequently, either u or
is the u-coordinate of an affine point of M{A,B}, depending on u':=t*u is the u-coordinate of an affine point of M{A,B}, depending
whether f(u)/B is a square in GF(q). on whether f(u)/B is a square in GF(q).
a. If f(u)/B is a square in GF(q) and v:=sqrt(f(u)/B), then t is a. If f(u)/B is a square in GF(q) and v:=sqrt(f(u)/B), then t is
mapped to the point P(t):=(u, v); mapped to the point P(t):=(u, v);
b. If f(u)/B is a not a square in GF(q) and v':=sqrt(f(u')/B), then b. If f(u)/B is a not a square in GF(q) and v':=sqrt(f(u')/B), then
t is mapped to the point P(t):=(u', -v'). t is mapped to the point P(t):=(u', -v').
As before, formally, this mapping is not properly defined, since a As before, formally, this mapping is not properly defined, since a
nonzero square y:=x^2 in GF(q) has two solutions, viz. x and -x; it nonzero square y:=x^2 in GF(q) has two solutions, viz. x and -x; it
is properly defined, however, if one designates for each element in is properly defined, however, if one designates for each element in
GF(q) that is a square in GF(q) precisely one square root as "the" GF(q) that is a square in GF(q) precisely one square root as "the"
square root of this element. Note that always picking the square square root of this element. Note that always picking the square
root with zero parity (see Appendix I) satisfies this condition, as root with zero parity (see Appendix I) satisfies this condition
does using one of the square root functions specified in (henceforth called the default square root function).
Appendix L.1.
If -1 is not a square in GF(q), this element is mapped to the point If -1 is not a square in GF(q), this element is mapped to the point
at infinity O of M_{A,B}. at infinity O of M_{A,B}.
The set of points of M_{A,B} that arises this way has size roughly The set of points of M_{A,B} that arises this way has size roughly
1/2 of the order of the curve and each such point arises as image of 1/2 of the order of the curve and each such point arises as image of
precisely one t value. Further details are out of scope. precisely one t value. Further details are out of scope.
NOTE 1: If -1 is not a square in GF(q), the mapping above yields the
point at infinity for t=-1. One can modify this mapping to always
yield an affine point, by mapping the element -1 to, e.g., the base
point G of M_{A,B} and leaving the remainder of the mapping the same.
Suitability of such a modification is application-specific. Details
are out of scope.
NOTE 2: The description above assumes that the domain parameter A of
the Montgomery curve is nonzero. If this is not the case, the curve
is a Weierstrass curve for which the domain parameter b is zero and
Note 2 of Appendix L.3.1 applies. If q = 3 (mod 4), an even simpler
approach is possible, where one modifies the construction above and
simply takes u:=t and u':=-t (which works, since -1 is not a square
in GF(q) and f(-t)=-f(t)). In this case, this construction can be
extended to all elements t of GF(q) and, if so, yields a 1-1 mapping
between GF(q) and all affine curve points.
L.3.3. Mapping to Points of Twisted Edwards Curve L.3.3. Mapping to Points of Twisted Edwards Curve
One can map elements of GF(q) that are not a square in GF(q) to One can map elements of GF(q) that are not a square in GF(q) to
points of the twisted Edwards curve E_{a,d} via function composition, points of the twisted Edwards curve E_{a,d} via function composition,
where one uses the mapping of Appendix L.3.1 to arrive at a point of where one uses the mapping of Appendix L.3.1 to arrive at a point of
the Weierstrass curve W_{a,b} and where one subsequently uses the the Weierstrass curve W_{a,b} and where one subsequently uses the
isomorphic mapping between twisted Edwards curves and Weierstrass isomorphic mapping between twisted Edwards curves and Weierstrass
curves of Appendix D.3 to arrive at a point of E_{a,d}. Another curves of Appendix D.3 to arrive at a point of E_{a,d}. Another
mapping is obtained by function composition, where one instead uses mapping is obtained by function composition, where one instead uses
the mapping of Appendix L.3.2 to arrive at a point of the Montgomery the mapping of Appendix L.3.2 to arrive at a point of the Montgomery
skipping to change at page 65, line 47 skipping to change at page 68, line 31
L.4. Randomized Representation of Curve Points L.4. Randomized Representation of Curve Points
The mappings of Appendix L.3.1, Appendix L.3.2, and Appendix L.3.3 The mappings of Appendix L.3.1, Appendix L.3.2, and Appendix L.3.3
allow one to represent a curve point Q as a specific element of allow one to represent a curve point Q as a specific element of
GF(q), provided this point arises as a point in the range of the GF(q), provided this point arises as a point in the range of the
mapping at hand. For Montgomery curves and twisted Edwards curves, mapping at hand. For Montgomery curves and twisted Edwards curves,
this covers roughly half of the curve points; for Weierstrass curves, this covers roughly half of the curve points; for Weierstrass curves,
roughly 3/8 of the curve points. One can extend the mappings above, roughly 3/8 of the curve points. One can extend the mappings above,
by mapping a pair (t1, t2) of inputs to the point Q:=P2(t1, by mapping a pair (t1, t2) of inputs to the point Q:=P2(t1,
t2):=P(t1) + P(t2). In this case, each curve point has roughly q/4 t2):=P(t1) + P(t2). In this case, each curve point has roughly q/4
representations as a pair (t1, t2) on average. In fact, one can show representations as an ordered pair (t1, t2) on average. In fact, one
that if the input pairs are generated uniformly at random, then the can show that if the input pairs are generated uniformly at random,
corresponding curve points follow a distribution that is also then the corresponding curve points follow a distribution that is
(statistically indistinguishable from) a uniform distribution. Here, also (statistically indistinguishable from) a uniform distribution,
each pair (t1, t2) deterministically yields a curve point, whereas and vice-versa. Here, each pair (t1, t2) deterministically yields a
for each curve point Q, a randomized algorithm yields a pair (t1, t2) curve point, whereas for each curve point Q, a randomized algorithm
of pre-images of Q, where the expected number of randomized pre- yields an ordered pair (t1, t2) of pre-images of Q, where the
images one has to try is small (four if one uses the mapping of expected number of randomized pre-images one has to try is small
Appendix L.3.1; two if one uses the mapping of Appendix L.3.2). For (four if one uses the mapping of Appendix L.3.1; two if one uses the
further details, see [Tibouchi]. mapping of Appendix L.3.2). For further details, see Algorithm 1 of
[Tibouchi].
Appendix M. Curve secp256k1 and Friend
M.1. Curve Definition and Alternative Representation
The elliptic curve secp256k1 is the Weierstrass curve W_{a,b} defined
over the prime field GF(p), with p:=2^256-2^32-2^9-2^8-2^7-2^6-2^4-1,
where a:=0 and b:=7. This curve has order h*n, where h=1 and where n
is a prime number. For this curve, domain parameter a is zero,
whereas b is not. The quadratic twist of this curve has order h1*n1,
where h1 is a 37-bit integer and where n1 is a prime number. For
this curve, the base point is the point (GX, GY).
The curve secp256k1 is 3-isogenous to the Weierstrass curve
secp256k1.m defined over GF(p), which has nonzero domain parameters a
and b and has as base point the pair (GmX,GmY), where parameters are
as specified in Appendix M.3 and where the related mappings are as
specified in Appendix M.2.
M.2. Switching Between Representations
Each affine point (X,Y) of secp256k1 corresponds to the point
(X',Y'):=(u(X)/w(X)^2,Y*v(X)/w(X)^3) of secp256k1.m, where u, v, and
w are the polynomials with coefficients in GF(p) as defined in
Appendix M.4.1, while the point at infinity of secp256k1 corresponds
to the point at infinity of secp256k1.m. Under this isogenous
mapping, the base point (GX,GY) of secp256k1 corresponds to the base
point (GmX,GmY) of secp256k1.m. The dual isogeny maps the affine
point (X',Y') of secp256k1.m to the affine point
(X,Y):=(u'(X')/w'(X')^2,Y'*v'(X')/w'(X')^3) of secp256k1, where u',
v', and w' are the polynomials with coefficients in GF(p) as defined
in Appendix M.4.2, while mapping the point at infinity O of
secp256k1.m to the point at infinity O of secp256k1. Under this dual
isogenous mapping, the base point (GmX, GmY) of secp256k1.m
corresponds to a multiple of the base point (GX, GY) of secp256k1,
where this multiple is l=3 (the degree of the isogeny; see the
description in Appendix F.4). Note that this isogenous map (and its
dual) primarily involves the evaluation of three fixed polynomials
involving the x-coordinate, which takes roughly 10 modular
multiplications (or less than 1% relative incremental cost compared
to the cost of an elliptic curve scalar multiplication).
M.3. Domain Parameters
The parameters of the curve sec256k1 and the corresponding
3-isogenous curve sec256k1.m are as indicated below. Here, the
domain parameters of the curve secp256k1 are as specified in [SEC2];
the domain parameters of secp256k1.m are "new".
General parameters (for all curves):
p 2^256-2^32-2^9-2^8-2^7-2^6-2^4-1
(=0xffffffff ffffffff ffffffff ffffffff ffffffff ffffffff
fffffffe fffffc2f)
h 1
n 11579208923731619542357098500868790785283756427907490438260516314
1518161494337
(=0xffffffff ffffffff ffffffff fffffffe baaedce6 af48a03b
bfd25e8c d0364141)
h1 23479460174521 (=0x1a 9bfcab89)
n1 10131766773001318469008702396060356387381009972480920692566974370
31
(=0x099ee564 ea5d84f5 08913936 a761b0d5 d792a426 a7779817
ae2f5b67)
Weierstrass curve-specific parameters (for secp256k1):
a 0 (=0x00)
b 7 (=0x07)
GX 55066263022277343669578718895168534326250603453777594175500187360
389116729240
(=0x79be667e f9dcbbac 55a06295 ce870b07 029bfcdb 2dce28d9
59f2815b 16f81798)
GY 32670510020758816978083085130507043184471273380659243275938904335
757337482424
(=0x483ada77 26a3c465 5da4fbfc 0e1108a8 fd17b448 a6855419
9c47d08f fb10d4b8)
Weierstrass curve-specific parameters (for secp256k1.m):
a 93991599167772749909245591943117186381494883464374162770646538702
960816911535
(=0xcfcd5c21 75e2ef7d ccdce737 770b7381 5a2f13c5 09035ca2
54a14ac9 f08974af)
b 1771 (=0x06eb)
GmX 26591621185618668069038227574782692264471832498547635565821216767
730887659845
(=0x3aca5300 959fa1d0 baf78dcf f77a616f 395e586d 67aced0a
88798129 0c279145)
GmY 67622516283223102233819216063319565850973524550533340939716651159
860372686848
(=0x9580fce5 3a170f4f b744579f f3d62086 12cd6a23 3e2de237
f976c6a7 8611c800)
M.4. Isogeny Details
The isogeny and dual isogeny are both isogenies with degree l=3.
Both are specified by a triple of polynomials u, v, and w (resp. u',
v', and w') of degree 3, 3, and 1, respectively, with coefficients in
GF(p). The coeffients of each of these polynomials are specified in
Appendix M.4.1 (for the isogeny) and in Appendix M.4.2 (for the dual
isogeny). For each polynomial in variable x, the coefficients are
tabulated as sequence of coefficients of x^0, x^1, x^2, ..., in
hexadecimal format.
M.4.1. Isogeny Parameters
M.4.1.1. Coefficients of u(x)
0 0x54
1 0xa4d89db3ed06c81e6143ec2eca9f761d8d17260dc229e1da1f73f714506872a9
2 0xcc58ffccbd9febb4a66222c7d1311d988d88c0624bcd68ec4c758a8e67dfd99b
3 0x01
M.4.1.2. Coefficients of v(x)
0 0x1c
1 0x94c7bc69befd17f2fae2e3ebf24df1f355d181fa1a8056103ba9baad4b40f029
2 0xb2857fb31c6fe18ef993342bb9c9ac64d44d209371b41d6272b04fd61bcfc851
3 0x01
M.4.1.3. Coefficients of w(x)
0 0xe62c7fe65ecff5da53311163e8988ecc46c4603125e6b476263ac546b3efeae5
1 0x01
M.4.2. Dual Isogeny Parameters
M.4.2.1. Coefficients of u'(x)
0 0x8e38e38e38e38e38e38e38e38e38e38e38e38e38e38e38e38e38e38daaaaa8c7
1 0x44cd5cd7ce55a801725891578fbe7356bd936355fd0e2f538797cecff7a37244
2 0x668d0011162006c3c889f4680f9a4b77d0d26a89e6bb87b13bd8d1cfdd600a41
3 0x8e38e38e38e38e38e38e38e38e38e38e38e38e38e38e38e38e38e38daaaaa88c
M.4.2.2. Coefficients of v'(x)
0 0x4bda12f684bda12f684bda12f684bda12f684bda12f684bda12f684b8e38e23c
1 0x519ba9c1f48f68054def6a410f0fa6e8b71c6c3b4a8958324681f6508c01fada
2 0xb34680088b100361e444fa3407cd25bbe8693544f35dc3d89dec68e76eb00338
3 0x2f684bda12f684bda12f684bda12f684bda12f684bda12f684bda12f38e38d84
M.4.2.3. Coefficients of w'(x)
0 0x4d7a804ce3901e71066ccbd44636539b2bb2df6c8e4be29d8d4fb028e43033de
1 0x01
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. 73 change blocks. 
96 lines changed or deleted 416 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/