draft-ietf-lwig-curve-representations-20.txt		draft-ietf-lwig-curve-representations-21.txt
	lwig R. Struik		lwig R. Struik
	Internet-Draft Struik Security Consultancy		Internet-Draft Struik Security Consultancy
	Intended status: Standards Track February 17, 2021		Intended status: Informational June 9, 2021
	Expires: August 21, 2021		Expires: December 11, 2021
	Alternative Elliptic Curve Representations		Alternative Elliptic Curve Representations
	draft-ietf-lwig-curve-representations-20		draft-ietf-lwig-curve-representations-21
	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. We also provide extensive background		using NIST prime curves. We also provide extensive background
	material that may be useful for implementers of elliptic curve		material that may be useful for implementers of elliptic curve
	cryptography.		cryptography.
	skipping to change at page 1, line 44 ¶		skipping to change at page 1, line 44 ¶
	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 August 21, 2021.		This Internet-Draft will expire on December 11, 2021.
	Copyright Notice		Copyright Notice
	Copyright (c) 2021 IETF Trust and the persons identified as the		Copyright (c) 2021 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 . . . . . . . . 5		1. Fostering Code Reuse with New Elliptic Curves . . . . . . . . 5
	2. Specification of Wei25519 . . . . . . . . . . . . . . . . . . 6		2. Specification of Wei25519 . . . . . . . . . . . . . . . . . . 6
	3. Use of Representation Switches . . . . . . . . . . . . . . . 6		3. Use of Representation Switches . . . . . . . . . . . . . . . 7
	4. Examples . . . . . . . . . . . . . . . . . . . . . . . . . . 7		4. Examples . . . . . . . . . . . . . . . . . . . . . . . . . . 7
	4.1. Implementation of X25519, Specification of ECDH25519 . . 7		4.1. Implementation of X25519, Specification of ECDH25519 . . 8
	4.2. Implementation of Ed25519 . . . . . . . . . . . . . . . . 9		4.2. Implementation of Ed25519 . . . . . . . . . . . . . . . . 9
	4.3. Specification of ECDSA25519 . . . . . . . . . . . . . . . 9		4.3. Specification of ECDSA25519 . . . . . . . . . . . . . . . 9
	4.4. Other Uses (Wei448, ECDH448, ECDSA448, and Others) . . . 10		4.4. Other Uses (Wei448, ECDH448, ECDSA448, and Others) . . . 10
	5. Caveats . . . . . . . . . . . . . . . . . . . . . . . . . . . 11		5. Caveats . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
	5.1. Wire Format . . . . . . . . . . . . . . . . . . . . . . . 11		5.1. Wire Format . . . . . . . . . . . . . . . . . . . . . . . 11
	5.2. Representation Conventions . . . . . . . . . . . . . . . 11		5.2. Representation Conventions . . . . . . . . . . . . . . . 11
	5.3. Domain Parameters . . . . . . . . . . . . . . . . . . . . 11		5.3. Domain Parameters . . . . . . . . . . . . . . . . . . . . 12
	6. Implementation Considerations . . . . . . . . . . . . . . . . 12		6. Implementation Considerations . . . . . . . . . . . . . . . . 13
	7. Implementation Status . . . . . . . . . . . . . . . . . . . . 13		7. Implementation Status . . . . . . . . . . . . . . . . . . . . 14
	8. Security Considerations . . . . . . . . . . . . . . . . . . . 14		8. Security Considerations . . . . . . . . . . . . . . . . . . . 15
	9. Privacy Considerations . . . . . . . . . . . . . . . . . . . 15		9. Privacy Considerations . . . . . . . . . . . . . . . . . . . 16
	10. Using Wei25519 and Wei448 with COSE and JOSE . . . . . . . . 16		10. Using Wei25519 and Wei448 with COSE and JOSE . . . . . . . . 16
	10.1. Using Wei25519 and Wei448 Keys with COSE and JOSE . . . 16		10.1. Using Wei25519 and Wei448 Keys with COSE and JOSE . . . 16
	10.1.1. Encoding of Short-Weierstrass Curves with COSE . . . 16		10.1.1. Encoding of Short-Weierstrass Curves with COSE . . . 17
	10.1.2. Encoding of Short-Weierstrass Curves with JOSE . . . 17		10.1.2. Encoding of Short-Weierstrass Curves with JOSE . . . 18
	10.2. Using ECDSA25519 and ECDSA448 with COSE and JOSE . . . . 18		10.2. Using ECDSA25519 and ECDSA448 with COSE and JOSE . . . . 18
	10.2.1. Encoding of ECDSA Instantiations with COSE . . . . . 19		10.2.1. Encoding of ECDSA Instantiations with COSE . . . . . 19
	10.2.2. Encoding of ECDSA Instantiations with JOSE . . . . . 20		10.2.2. Encoding of ECDSA Instantiations with JOSE . . . . . 20
	10.3. Using ECDH25519 and ECDH448 with COSE and JOSE . . . . . 21		10.3. Using ECDH25519 and ECDH448 with COSE and JOSE . . . . . 21
	10.3.1. Encoding of co-factor ECDH with COSE . . . . . . . . 22		10.3.1. Encoding of co-factor ECDH with COSE . . . . . . . . 22
	10.3.2. Encoding of co-factor ECDH with JOSE . . . . . . . . 22		10.3.2. Encoding of co-factor ECDH with JOSE . . . . . . . . 22
	11. Using Wei25519 and Wei448 with PKIX and CMS . . . . . . . . . 22		11. Using Wei25519 and Wei448 with PKIX and CMS . . . . . . . . . 23
	11.1. Encoding of Short-Weierstrass Curves with PKIX . . . . . 22		11.1. Encoding of Short-Weierstrass Curves with PKIX . . . . . 23
	11.2. Encoding of ECDSA Instantiations with PKIX . . . . . . . 23		11.2. Encoding of ECDSA Instantiations with PKIX . . . . . . . 23
	11.3. Encoding of co-factor ECDH and Other Algorithms with		11.3. Encoding of co-factor ECDH and Other Algorithms with
	PKIX . . . . . . . . . . . . . . . . . . . . . . . . . . 23		PKIX . . . . . . . . . . . . . . . . . . . . . . . . . . 24
	11.4. Encoding of Elliptic-Curve-Based Algorithms with CMS . . 23		11.4. Encoding of Elliptic-Curve-Based Algorithms with CMS . . 24
	12. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 24		12. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 24
	12.1. OIDs for Use with PKIX and CMS . . . . . . . . . . . . . 24		12.1. OIDs for Use with PKIX and CMS . . . . . . . . . . . . . 24
	12.2. JOSE IANA Considerations for Wei25519 . . . . . . . . . 24		12.2. COSE/JOSE IANA Considerations for Wei25519 . . . . . . . 25
	12.2.1. JOSE Elliptic Curves Registration . . . . . . . . . 24		12.2.1. COSE Elliptic Curves Registration . . . . . . . . . 25
	12.2.2. JOSE Algorithms Registration (1/2) . . . . . . . . . 25		12.2.2. COSE Algorithms Registration (1/2) . . . . . . . . . 25
	12.2.3. JOSE Algorithms Registration (2/2) . . . . . . . . . 25		12.2.3. COSE Algorithms Registration (2/2) . . . . . . . . . 26
	12.3. JOSE IANA Considerations for Wei448 . . . . . . . . . . 26		12.2.4. JOSE Elliptic Curves Registration . . . . . . . . . 26
	12.3.1. JOSE Elliptic Curves Registration . . . . . . . . . 26		12.2.5. JOSE Algorithms Registration (1/2) . . . . . . . . . 26
	12.3.2. JOSE Algorithms Registration (1/2) . . . . . . . . . 26		12.2.6. JOSE Algorithms Registration (2/2) . . . . . . . . . 27
	12.3.3. JOSE Algorithms Registration (2/2) . . . . . . . . . 26		12.3. COSE/JOSE IANA Considerations for Wei448 . . . . . . . . 27
	13. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . 27		12.3.1. COSE Elliptic Curves Registration . . . . . . . . . 27
	14. References . . . . . . . . . . . . . . . . . . . . . . . . . 27		12.3.2. COSE Algorithms Registration (1/2) . . . . . . . . . 28
	14.1. Normative References . . . . . . . . . . . . . . . . . . 27		12.3.3. COSE Algorithms Registration (2/2) . . . . . . . . . 28
	14.2. Informative References . . . . . . . . . . . . . . . . . 30		12.3.4. JOSE Elliptic Curves Registration . . . . . . . . . 29
	Appendix A. Some (Non-Binary) Elliptic Curves . . . . . . . . . 33		12.3.5. JOSE Algorithms Registration (1/2) . . . . . . . . . 29
	A.1. Curves in Short-Weierstrass Form . . . . . . . . . . . . 33		12.3.6. JOSE Algorithms Registration (2/2) . . . . . . . . . 29
	A.2. Montgomery Curves . . . . . . . . . . . . . . . . . . . . 33		13. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . 30
	A.3. Twisted Edwards Curves . . . . . . . . . . . . . . . . . 33		14. References . . . . . . . . . . . . . . . . . . . . . . . . . 30
	Appendix B. Elliptic Curve Nomenclature and Finite Fields . . . 34		14.1. Normative References . . . . . . . . . . . . . . . . . . 30
	B.1. Elliptic Curve Nomenclature . . . . . . . . . . . . . . . 34		14.2. Informative References . . . . . . . . . . . . . . . . . 33
	B.2. Finite Fields . . . . . . . . . . . . . . . . . . . . . . 36		Appendix A. Some (Non-Binary) Elliptic Curves . . . . . . . . . 35
	Appendix C. Elliptic Curve Group Operations . . . . . . . . . . 37		A.1. Curves in Short-Weierstrass Form . . . . . . . . . . . . 35
	C.1. Group Laws for Weierstrass Curves . . . . . . . . . . . . 37		A.2. Montgomery Curves . . . . . . . . . . . . . . . . . . . . 36
	C.2. Group Laws for Montgomery Curves . . . . . . . . . . . . 38		A.3. Twisted Edwards Curves . . . . . . . . . . . . . . . . . 36
	C.3. Group Laws for Twisted Edwards Curves . . . . . . . . . . 39		Appendix B. Elliptic Curve Nomenclature and Finite Fields . . . 37
	Appendix D. Relationships Between Curve Models . . . . . . . . . 40		B.1. Elliptic Curve Nomenclature . . . . . . . . . . . . . . . 37
			B.2. Finite Fields . . . . . . . . . . . . . . . . . . . . . . 39
			Appendix C. Elliptic Curve Group Operations . . . . . . . . . . 40
			C.1. Group Laws for Weierstrass Curves . . . . . . . . . . . . 40
			C.2. Group Laws for Montgomery Curves . . . . . . . . . . . . 41
			C.3. Group Laws for Twisted Edwards Curves . . . . . . . . . . 42
			Appendix D. Relationships Between Curve Models . . . . . . . . . 43
	D.1. Mapping between Twisted Edwards Curves and Montgomery		D.1. Mapping between Twisted Edwards Curves and Montgomery
	Curves . . . . . . . . . . . . . . . . . . . . . . . . . 40		Curves . . . . . . . . . . . . . . . . . . . . . . . . . 43
	D.2. Mapping between Montgomery Curves and Weierstrass Curves 41		D.2. Mapping between Montgomery Curves and Weierstrass Curves 44
	D.3. Mapping between Twisted Edwards Curves and Weierstrass		D.3. Mapping between Twisted Edwards Curves and Weierstrass
	Curves . . . . . . . . . . . . . . . . . . . . . . . . . 42		Curves . . . . . . . . . . . . . . . . . . . . . . . . . 45
	Appendix E. Curve25519 and Cousins . . . . . . . . . . . . . . . 42		Appendix E. Curve25519 and Cousins . . . . . . . . . . . . . . . 45
	E.1. Curve Definition and Alternative Representations . . . . 42		E.1. Curve Definition and Alternative Representations . . . . 45
	E.2. Switching between Alternative Representations . . . . . . 43		E.2. Switching between Alternative Representations . . . . . . 45
	E.3. Domain Parameters . . . . . . . . . . . . . . . . . . . . 44		E.3. Domain Parameters . . . . . . . . . . . . . . . . . . . . 47
	Appendix F. Further Mappings . . . . . . . . . . . . . . . . . . 46		Appendix F. Further Mappings . . . . . . . . . . . . . . . . . . 49
	F.1. Isomorphic Mapping between Twisted Edwards Curves . . . . 46		F.1. Isomorphic Mapping between Twisted Edwards Curves . . . . 49
	F.2. Isomorphic Mapping between Montgomery Curves . . . . . . 47		F.2. Isomorphic Mapping between Montgomery Curves . . . . . . 50
	F.3. Isomorphic Mapping between Weierstrass Curves . . . . . . 48		F.3. Isomorphic Mapping between Weierstrass Curves . . . . . . 50
	F.4. Isogenous Mapping between Weierstrass Curves . . . . . . 49		F.4. Isogenous Mapping between Weierstrass Curves . . . . . . 51
	Appendix G. Further Cousins of Curve25519 . . . . . . . . . . . 50		Appendix G. Further Cousins of Curve25519 . . . . . . . . . . . 53
	G.1. Further Alternative Representations . . . . . . . . . . . 50		G.1. Further Alternative Representations . . . . . . . . . . . 53
	G.2. Further Switching . . . . . . . . . . . . . . . . . . . . 50		G.2. Further Switching . . . . . . . . . . . . . . . . . . . . 53
	G.3. Further Domain Parameters . . . . . . . . . . . . . . . . 51		G.3. Further Domain Parameters . . . . . . . . . . . . . . . . 54
	G.4. Isogeny Details . . . . . . . . . . . . . . . . . . . . . 53		G.4. Isogeny Details . . . . . . . . . . . . . . . . . . . . . 55
	G.4.1. Isogeny Parameters . . . . . . . . . . . . . . . . . 53		G.4.1. Isogeny Parameters . . . . . . . . . . . . . . . . . 56
	G.4.2. Dual Isogeny Parameters . . . . . . . . . . . . . . . 59		G.4.2. Dual Isogeny Parameters . . . . . . . . . . . . . . . 62
			Appendix H. Point Compression . . . . . . . . . . . . . . . . . 68
	Appendix H. Point Compression . . . . . . . . . . . . . . . . . 65		H.1. Point Compression for Weierstrass Curves . . . . . . . . 68
	H.1. Point Compression for Weierstrass Curves . . . . . . . . 66		H.2. Point Compression for Montgomery Curves . . . . . . . . . 69
	H.2. Point Compression for Montgomery Curves . . . . . . . . . 66		H.3. Point Compression for Twisted Edwards Curves . . . . . . 70
	H.3. Point Compression for Twisted Edwards Curves . . . . . . 67		Appendix I. Data Conversions . . . . . . . . . . . . . . . . . . 71
	Appendix I. Data Conversions . . . . . . . . . . . . . . . . . . 68		I.1. Strings and String Operations . . . . . . . . . . . . . . 71
	I.1. Strings and String Operations . . . . . . . . . . . . . . 68		I.2. Conversion between Bit Strings and Integers (BS2I, I2BS) 72
	I.2. Conversion between Bit Strings and Integers (BS2I, I2BS) 69
	I.3. Conversion between Octet Strings and Integers (OS2I,		I.3. Conversion between Octet Strings and Integers (OS2I,
	I2OS) . . . . . . . . . . . . . . . . . . . . . . . . . . 69		I2OS) . . . . . . . . . . . . . . . . . . . . . . . . . . 72
	I.4. Conversion between Octet Strings and Bit Strings (OS2BS,		I.4. Conversion between Octet Strings and Bit Strings (OS2BS,
	BS2OS) . . . . . . . . . . . . . . . . . . . . . . . . . 70		BS2OS) . . . . . . . . . . . . . . . . . . . . . . . . . 72
	I.5. Conversion between Field Elements and Octet Strings		I.5. Conversion between Field Elements and Octet Strings
	(FE2OS, OS2FE) . . . . . . . . . . . . . . . . . . . . . 70		(FE2OS, OS2FE) . . . . . . . . . . . . . . . . . . . . . 73
	I.6. Conversion between Elements of Z_n and Octet Strings		I.6. Conversion between Elements of Z_n and Octet Strings
	(ZnE2OS, OS2ZnE) . . . . . . . . . . . . . . . . . . . . 71		(ZnE2OS, OS2ZnE) . . . . . . . . . . . . . . . . . . . . 73
	I.7. Ordering Conventions . . . . . . . . . . . . . . . . . . 71		I.7. Ordering Conventions . . . . . . . . . . . . . . . . . . 74
	I.8. Conversion Between Curve Points and Octet Strings . . . . 72		I.8. Conversion Between Curve Points and Octet Strings . . . . 75
	Appendix J. Representation Examples Curve25519 Family Members . 75		Appendix J. Representation Examples Curve25519 Family Members . 77
	J.1. Example with Curve25519 . . . . . . . . . . . . . . . . . 75		J.1. Example with Curve25519 . . . . . . . . . . . . . . . . . 78
	J.2. Example with Edwards25519 . . . . . . . . . . . . . . . . 78		J.2. Example with Edwards25519 . . . . . . . . . . . . . . . . 80
	J.3. Example with Wei25519 . . . . . . . . . . . . . . . . . . 80		J.3. Example with Wei25519 . . . . . . . . . . . . . . . . . . 82
	J.4. Example with Wei25519.2 . . . . . . . . . . . . . . . . . 82		J.4. Example with Wei25519.2 . . . . . . . . . . . . . . . . . 85
	J.5. Example with Wei25519.-3 . . . . . . . . . . . . . . . . 84		J.5. Example with Wei25519.-3 . . . . . . . . . . . . . . . . 87
	Appendix K. Auxiliary Functions . . . . . . . . . . . . . . . . 86		Appendix K. Auxiliary Functions . . . . . . . . . . . . . . . . 89
	K.1. Square Roots in GF(q) . . . . . . . . . . . . . . . . . . 87		K.1. Square Roots in GF(q) . . . . . . . . . . . . . . . . . . 89
	K.1.1. Square Roots in GF(q), where q = 3 (mod 4) . . . . . 87		K.1.1. Square Roots in GF(q), where q = 3 (mod 4) . . . . . 90
	K.1.2. Square Roots in GF(q), where q = 5 (mod 8) . . . . . 87		K.1.2. Square Roots in GF(q), where q = 5 (mod 8) . . . . . 90
	K.2. Inversion . . . . . . . . . . . . . . . . . . . . . . . . 88		K.2. Inversion . . . . . . . . . . . . . . . . . . . . . . . . 90
	K.3. Mappings to Curve Points . . . . . . . . . . . . . . . . 88		K.3. Mappings to Curve Points . . . . . . . . . . . . . . . . 91
	K.3.1. Mapping to Points of Weierstrass Curve . . . . . . . 88		K.3.1. Mapping to Points of Weierstrass Curve . . . . . . . 91
	K.3.2. Mapping to Points of Montgomery Curve . . . . . . . . 90		K.3.2. Mapping to Points of Montgomery Curve . . . . . . . . 92
	K.3.3. Mapping to Points of Twisted Edwards Curve . . . . . 91		K.3.3. Mapping to Points of Twisted Edwards Curve . . . . . 93
	K.4. Mappings to High-Order Curve Points . . . . . . . . . . . 91		K.4. Mappings to High-Order Curve Points . . . . . . . . . . . 94
	K.4.1. Mapping to High-Order Points of Weierstrass Curve . . 91		K.4.1. Mapping to High-Order Points of Weierstrass Curve . . 94
	K.4.2. Mapping to High-Order Points of Montgomery Curve . . 92		K.4.2. Mapping to High-Order Points of Montgomery Curve . . 95
	K.4.3. Mapping to High-Order Points of Twisted Edwards Curve 94		K.4.3. Mapping to High-Order Points of Twisted Edwards Curve 96
	K.5. Randomized Representation of Curve Points . . . . . . . . 95		K.5. Randomized Representation of Curve Points . . . . . . . . 97
	K.6. Completing the Mappings to Curve Points . . . . . . . . . 96		K.6. Completing the Mappings to Curve Points . . . . . . . . . 98
	Appendix L. Curve secp256k1 and Friend . . . . . . . . . . . . . 99		Appendix L. Curve secp256k1 and Friend . . . . . . . . . . . . . 101
	L.1. Curve Definition and Alternative Representation . . . . . 100		L.1. Curve Definition and Alternative Representation . . . . . 102
	L.2. Switching Between Representations . . . . . . . . . . . . 100		L.2. Switching Between Representations . . . . . . . . . . . . 102
	L.3. Domain Parameters . . . . . . . . . . . . . . . . . . . . 100		L.3. Domain Parameters . . . . . . . . . . . . . . . . . . . . 102
	L.4. Isogeny Details . . . . . . . . . . . . . . . . . . . . . 102		L.4. Isogeny Details . . . . . . . . . . . . . . . . . . . . . 104
	L.4.1. Isogeny Parameters . . . . . . . . . . . . . . . . . 102		L.4.1. Isogeny Parameters . . . . . . . . . . . . . . . . . 104
	L.4.2. Dual Isogeny Parameters . . . . . . . . . . . . . . . 103		L.4.2. Dual Isogeny Parameters . . . . . . . . . . . . . . . 105
	Appendix M. Curve448 and Cousins . . . . . . . . . . . . . . . . 103		Appendix M. Curve448 and Cousins . . . . . . . . . . . . . . . . 105
	M.1. Curve Definition and Alternative Representations . . . . 103		M.1. Curve Definition and Alternative Representations . . . . 105
	M.2. Switching between Alternative Representations . . . . . . 104		M.2. Switching between Alternative Representations . . . . . . 106
	M.3. Domain Parameters . . . . . . . . . . . . . . . . . . . . 105		M.3. Domain Parameters . . . . . . . . . . . . . . . . . . . . 107
	Appendix N. Further Cousins of Curve448 . . . . . . . . . . . . 108		Appendix N. Further Cousins of Curve448 . . . . . . . . . . . . 110
	N.1. Further Alternative Representations . . . . . . . . . . . 108		N.1. Further Alternative Representations . . . . . . . . . . . 110
	N.2. Further Switching . . . . . . . . . . . . . . . . . . . . 108		N.2. Further Switching . . . . . . . . . . . . . . . . . . . . 110
	N.3. Further Domain Parameters . . . . . . . . . . . . . . . . 111		N.3. Further Domain Parameters . . . . . . . . . . . . . . . . 113
	N.4. Isogeny Details . . . . . . . . . . . . . . . . . . . . . 113		N.4. Isogeny Details . . . . . . . . . . . . . . . . . . . . . 115
	N.4.1. Isogeny Parameters . . . . . . . . . . . . . . . . . 113		N.4.1. Isogeny Parameters . . . . . . . . . . . . . . . . . 115
	N.4.2. Dual Isogeny Parameters . . . . . . . . . . . . . . . 114		N.4.2. Dual Isogeny Parameters . . . . . . . . . . . . . . . 116
	Appendix O. Representation Examples Curve448 Family Members . . 114		Appendix O. Representation Examples Curve448 Family Members . . 116
	O.1. Example with Curve448 . . . . . . . . . . . . . . . . . . 115		O.1. Example with Curve448 . . . . . . . . . . . . . . . . . . 117
	O.2. Example with Ed448 . . . . . . . . . . . . . . . . . . . 118		O.2. Example with Ed448 . . . . . . . . . . . . . . . . . . . 120
	O.3. Example with Wei448 . . . . . . . . . . . . . . . . . . . 121		O.3. Example with Wei448 . . . . . . . . . . . . . . . . . . . 123
	O.4. Example with Wei448.1 . . . . . . . . . . . . . . . . . . 124		O.4. Example with Wei448.1 . . . . . . . . . . . . . . . . . . 126
	O.5. Example with Wei448.-3 . . . . . . . . . . . . . . . . . 127		O.5. Example with Wei448.-3 . . . . . . . . . . . . . . . . . 129
	O.6. Example with Edwards448 . . . . . . . . . . . . . . . . . 129		O.6. Example with Edwards448 . . . . . . . . . . . . . . . . . 131
	Appendix P. Random Integers in Z_n . . . . . . . . . . . . . . . 132		Appendix P. Random Integers in Z_n . . . . . . . . . . . . . . . 134
	P.1. Conversion to Integers in Z_n via Modular Reduction . . . 133		P.1. Conversion to Integers in Z_n via Modular Reduction . . . 135
	P.2. Conversion to Integers in Z_n via Scaling . . . . . . . . 134		P.2. Conversion to Integers in Z_n via Scaling . . . . . . . . 136
	P.3. Conversion to Integers in Z_n via the Discard Method . . 135		P.3. Conversion to Integers in Z_n via the Discard Method . . 137
	Author's Address . . . . . . . . . . . . . . . . . . . . . . . . 135		Appendix Q. ECDSA signatures . . . . . . . . . . . . . . . . . . 137
			Q.1. ECDSA Signing Operation . . . . . . . . . . . . . . . . . 137
			Q.2. ECDSA Verification Operation . . . . . . . . . . . . . . 138
			Q.3. Representation Examples ECDSA . . . . . . . . . . . . . . 139
			Q.3.1. Example of ECDSA with Wei25519 and SHA-256 . . . . . 140
			Q.3.2. Example of ECDSA with Wei25519 and SHAKE128 . . . . . 142
			Q.3.3. Example of ECDSA with Wei448 and SHAKE256 . . . . . . 144
			Author's Address . . . . . . . . . . . . . . . . . . . . . . . . 146
	1. Fostering Code Reuse with New Elliptic Curves		1. Fostering Code Reuse with New Elliptic Curves
	Elliptic curves can be represented using different curve models.		Elliptic curves can be represented using different curve models.
	Recently, IETF standardized elliptic curves that are claimed to have		Recently, IETF standardized elliptic curves that are claimed to have
	better performance and improved robustness against "real world"		better performance and improved robustness against "real world"
	attacks than curves represented in the traditional short-Weierstrass		attacks than curves represented in the traditional short-Weierstrass
	curve model. These so-called CFRG curves [RFC7748] use the		curve model. These so-called CFRG curves [RFC7748] use the
	Montgomery curve model and the model of twisted Edwards curves.		Montgomery curve model and the model of twisted Edwards curves.
	skipping to change at page 9, line 49 ¶		skipping to change at page 10, line 15 ¶
	implementations of ECDSA with the hash function SHA-256 and with the		implementations of ECDSA with the hash function SHA-256 and with the
	NIST curve P-256 or with the curve Wei25519 specified in this		NIST curve P-256 or with the curve Wei25519 specified in this
	specification to reuse the same implementation (instantiated with,		specification to reuse the same implementation (instantiated with,
	respectively, the NIST P-256 elliptic curve domain parameters or with		respectively, the NIST P-256 elliptic curve domain parameters or with
	the domain parameters of curve Wei25519 specified in Appendix E). We		the domain parameters of curve Wei25519 specified in Appendix E). We
	denote by ECDSA25519 the instantiation of ECDSA with SHA-256 and with		denote by ECDSA25519 the instantiation of ECDSA with SHA-256 and with
	curve Wei25519, where the signature (r,s) is represented as the		curve Wei25519, where the signature (r,s) is represented as the
	right-concatenation of the integers r and s in the interval [1,n-1],		right-concatenation of the integers r and s in the interval [1,n-1],
	where n is the order of the base point of the curve in question, each		where n is the order of the base point of the curve in question, each
	represented as fixed-size octet strings in tight MSB/msb-order using		represented as fixed-size octet strings in tight MSB/msb-order using
	the Zn2OS mapping of Appendix I.6.		the ZnE2OS mapping of Appendix I.6.
	4.4. Other Uses (Wei448, ECDH448, ECDSA448, and Others)		4.4. Other Uses (Wei448, ECDH448, ECDSA448, and Others)
	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,
	thus spawning "offspring" protocols, simply by instantiating these		thus spawning "offspring" protocols, simply by instantiating these
	using the new curve in short-Weierstrass form, thereby allowing code		using the new curve in short-Weierstrass form, thereby allowing code
	and/or specifications reuse and, for implementations that so desire,		and/or specifications reuse and, for implementations that so desire,
	carrying out curve computations "under the hood" on Montgomery curve		carrying out curve computations "under the hood" on Montgomery curve
	skipping to change at page 16, line 49 ¶		skipping to change at page 17, line 24 ¶
	a. With the "EC2" type, each affine point (X, Y) is encoded by		a. With the "EC2" type, each affine point (X, Y) is encoded by
	setting the parameters "x" and "y" to the octet string		setting the parameters "x" and "y" to the octet string
	representations of the elements X and Y, respectively, in tight		representations of the elements X and Y, respectively, in tight
	MSB/msb-order, and converting each to a CBOR byte string. Each		MSB/msb-order, and converting each to a CBOR byte string. Each
	compressed point (X, t) is encoded by setting the parameter "x"		compressed point (X, t) is encoded by setting the parameter "x"
	to the octet representation of the element X, in tight MSB/msb-		to the octet representation of the element X, in tight MSB/msb-
	order, converted to a CBOR byte string, and by setting the		order, converted to a CBOR byte string, and by setting the
	parameter "y" to the CBOR false or CBOR true value, depending on		parameter "y" to the CBOR false or CBOR true value, depending on
	whether, respectively, t=0 or t=1. For representation details		whether, respectively, t=0 or t=1. For representation details
	and for details on the reverse mappings, see Appendix I.8. (Note		and for details on the reverse mappings, see Appendix I.8. (Note
	that for affine points this representation is consistent with the		that for affine points of a curve defined over a prime field this
	"EC2" representation in Section 13.1.1 of [RFC8152].)		representation is consistent with the "EC2" representation in
			Section 13.1.1 of [RFC8152].)
	b. With the "OKP" type, each point is encoded by setting the		b. With the "OKP" type, each point is encoded by setting the
	parameter "x" to the "squeezed" point representation of this		parameter "x" to the "squeezed" point representation of this
	point, in MSB/msb-order, and converting this to a CBOR byte		point, in MSB/msb-order, and converting this to a CBOR byte
	string. For representation details and for details on the		string. For representation details and for details on the
	reverse mappings, see Appendix I.8. (Note that for affine points		reverse mappings, see Appendix I.8. (Note that for affine points
	this representation is consistent with the "OKP" representation		of a curve defined over a prime field this representation is
	in Section 7.2 of [I-D.ietf-cose-rfc8152bis-algs], which affords		consistent with the "OKP" representation in Section 7.2 of
	a curve-specific octet string encoding.)		[I-D.ietf-cose-rfc8152bis-algs], which affords a curve-specific
			octet string encoding.)
	In either case, if the point is a public key (i.e., the private key		In either case, if the point is a public key (i.e., the private key
	is well-defined), the parameter "d" encodes the corresponding private		is well-defined), the parameter "d" encodes the corresponding private
	key, using the octet string representation, in tight MSB/msb-order,		key, using the octet string representation, in tight MSB/msb-order,
	and converting this to a CBOR byte string (see Appendix I.6).		and converting this to a CBOR byte string (see Appendix I.6).
	For curve points, the "crv" parameter and the parameters referenced		For curve points, the "crv" parameter and the parameters referenced
	with the applicable key type-specific settings above MUST be present		with the applicable key type-specific settings above MUST be present
	in the structure, whereas the parameter "d" MUST NOT be present,		in the structure, whereas the parameter "d" MUST NOT be present,
	while for private keys, the parameters "crv" and "d" MUST be present		while for private keys, the parameters "crv" and "d" MUST be present
	skipping to change at page 17, line 41 ¶		skipping to change at page 18, line 20 ¶
	parameter to the (unique) name of the curve in question and the "kty"		parameter to the (unique) name of the curve in question and the "kty"
	parameter to "EC" or "OKP", respectively, where key type-specific		parameter to "EC" or "OKP", respectively, where key type-specific
	settings are as follows:		settings are as follows:
	a. With the "EC" type, each affine curve point (X, Y) is encoded by		a. With the "EC" type, each affine curve point (X, Y) is encoded by
	setting the parameters "x" and "y" to the octet string		setting the parameters "x" and "y" to the octet string
	representations of the elements X and Y, respectively, in tight		representations of the elements X and Y, respectively, in tight
	MSB/msb-order, and converting each using the base64url encoding.		MSB/msb-order, and converting each using the base64url encoding.
	The point at infinity O is encoded as if this were an affine		The point at infinity O is encoded as if this were an affine
	point. For representation details and details on the reverse		point. For representation details and details on the reverse
	mappings, see Appendix I.8. (Note that for affine points this		mappings, see Appendix I.8. (Note that for affine points of a
	representation is consistent with the "EC" representation in		curve defined over a prime field this representation is
	Section 6.2 of [RFC7518]).)		consistent with the "EC" representation in Section 6.2 of
			[RFC7518]).)
	b. With the "OKP" type, each curve point is encoded by setting the		b. With the "OKP" type, each curve point is encoded by setting the
	parameter "x" to the "squeezed" point representation of this		parameter "x" to the "squeezed" point representation of this
	point, in MSB/msb-order, and converting this using the base64url		point, in MSB/msb-order, and converting this using the base64url
	encoding. For representation details and for details on the		encoding. For representation details and for details on the
	reverse mappings, see Appendix I.8. (Note that for affine points		reverse mappings, see Appendix I.8. (Note that for affine points
	this representation is consistent with the "OKP" representation		of a curve defined over a prime field this representation is
	in Section 2 of [RFC8037], which affords a curve-specific octet		consistent with the "OKP" representation in Section 2 of
	string encoding.)		[RFC8037], which affords a curve-specific octet string encoding.)
	In either case, if the point is a public key (i.e., the private key		In either case, if the point is a public key (i.e., the private key
	is well-defined), the parameter "d" encodes the corresponding private		is well-defined), the parameter "d" encodes the corresponding private
	key, using the octet string representation, in tight MSB/msb-order,		key, using the octet string representation, in tight MSB/msb-order,
	and converting this using the base64url encoding (see Appendix I.6).		and converting this using the base64url encoding (see Appendix I.6).
	For curve points, the "crv" parameter and the parameters referenced		For curve points, the "crv" parameter and the parameters referenced
	with the applicable key type-specific settings above MUST be present		with the applicable key type-specific settings above MUST be present
	in the structure, whereas the parameter "d" MUST NOT be present,		in the structure, whereas the parameter "d" MUST NOT be present,
	while for private keys, the parameters "crv" and "d" MUST be present		while for private keys, the parameters "crv" and "d" MUST be present
	skipping to change at page 24, line 35 ¶		skipping to change at page 25, line 14 ¶
	a. id-Wei25519 OBJECT IDENTIFIER ::= TBD (Requested value: {iso(1)		a. id-Wei25519 OBJECT IDENTIFIER ::= TBD (Requested value: {iso(1)
	identified-organization(3) thawte (101) 108 });		identified-organization(3) thawte (101) 108 });
	b. id-Wei448 OBJECT IDENTIFIER ::= TBD (Requested value: {iso(1)		b. id-Wei448 OBJECT IDENTIFIER ::= TBD (Requested value: {iso(1)
	identified-organization(3) thawte (101) 109 }).		identified-organization(3) thawte (101) 109 }).
	For a description of how these are used with PKIX certificates and		For a description of how these are used with PKIX certificates and
	CMS, see Section 11.		CMS, see Section 11.
	12.2. JOSE IANA Considerations for Wei25519		12.2. COSE/JOSE IANA Considerations for Wei25519
	NOTE: This draft does not request COSE IANA registrations.		12.2.1. COSE Elliptic Curves Registration
	12.2.1. JOSE Elliptic Curves Registration		This section registers the following value in the IANA "COSE Elliptic
			Curves" registry [IANA.COSE.Curves].
			Name: Wei25519;
			Value: TBD (Requested value: -1);
			Key Type: EC2 or OKP;
			Description: short-Weierstrass curve Wei25519;
			Change Controller: IESG;
			Reference: specified in Appendix E.3 of this specification; for
			encodings, see Section 10.1;
			Recommended: Yes.
			(Note that The "kty" value for Wei25519 may be "EC2" or "OKP".)
			12.2.2. COSE Algorithms Registration (1/2)
			This section registers the following value in the IANA "COSE
			Algorithms" registry [IANA.COSE.Algorithms].
			Name: ECDSA25519;
			Value: TBD (Requested value: -9);
			Description: ECDSA with SHA-256 and curve Wei25519;
			Change Controller: IESG;
			Reference: specified in Section 4.3 of this specification; for
			encodings, see Section 10.2;
			Recommended: Yes.
			12.2.3. COSE Algorithms Registration (2/2)
			This section registers the following value in the IANA "COSE
			Algorithms" registry [IANA.COSE.Algorithms].
			Name: ECDH25519;
			Value: TBD (Requested value: -24);
			Description: NIST-compliant co-factor Diffie-Hellman w/ curve
			Wei25519 and key derivation function HKDF SHA256;
			Change Controller: IESG;
			Reference: specified in Section 4.1 of this specification; for
			encodings, see Section 10.3;
			Recommended: Yes.
			12.2.4. JOSE Elliptic Curves Registration
	This section registers the following value in the IANA "JSON Web Key		This section registers the following value in the IANA "JSON Web Key
	Elliptic Curve" registry [IANA.JOSE.Curves].		Elliptic Curve" registry [IANA.JOSE.Curves].
	Curve Name: Wei25519;		Curve Name: Wei25519;
	Curve Description: short-Weierstrass curve Wei25519;		Curve Description: short-Weierstrass curve Wei25519;
	JOSE Implementation Requirements: Optional;		JOSE Implementation Requirements: Optional;
	skipping to change at page 25, line 4 ¶		skipping to change at page 26, line 38 ¶
	This section registers the following value in the IANA "JSON Web Key		This section registers the following value in the IANA "JSON Web Key
	Elliptic Curve" registry [IANA.JOSE.Curves].		Elliptic Curve" registry [IANA.JOSE.Curves].
	Curve Name: Wei25519;		Curve Name: Wei25519;
	Curve Description: short-Weierstrass curve Wei25519;		Curve Description: short-Weierstrass curve Wei25519;
	JOSE Implementation Requirements: Optional;		JOSE Implementation Requirements: Optional;
	Change Controller: IESG;		Change Controller: IESG;
	Reference: specified in Appendix E.3 of this specification; for		Reference: specified in Appendix E.3 of this specification; for
	encodings, see Section 10.1.		encodings, see Section 10.1.
	(Note that The "kty" value for Wei25519 may be "EC" or "OKP".)		(Note that The "kty" value for Wei25519 may be "EC" or "OKP".)
	12.2.2. JOSE Algorithms Registration (1/2)		12.2.5. JOSE Algorithms Registration (1/2)
	This section registers the following value in the IANA "JSON Web		This section registers the following value in the IANA "JSON Web
	Signature and Encryption Algorithms" registry [IANA.JOSE.Algorithms].		Signature and Encryption Algorithms" registry [IANA.JOSE.Algorithms].
	Algorithm Name: ECDSA25519;		Algorithm Name: ECDSA25519;
	Algorithm Description: ECDSA using SHA-256 and curve Wei25519;		Algorithm Description: ECDSA using SHA-256 and curve Wei25519;
	Algorithm Usage Locations: alg;		Algorithm Usage Locations: alg;
	JOSE Implementation Requirements: Optional;		JOSE Implementation Requirements: Optional;
	Change Controller: IESG;		Change Controller: IESG;
	Reference: specified in Section 4.3 of this specification; for		Reference: specified in Section 4.3 of this specification; for
	encodings, see Section 10.2;		encodings, see Section 10.2;
	Algorithm Analysis Document(s): Section 4.3 of this specification.		Algorithm Analysis Document(s): Section 4.3 of this specification.
	skipping to change at page 25, line 29 ¶		skipping to change at page 27, line 15 ¶
	JOSE Implementation Requirements: Optional;		JOSE Implementation Requirements: Optional;
	Change Controller: IESG;		Change Controller: IESG;
	Reference: specified in Section 4.3 of this specification; for		Reference: specified in Section 4.3 of this specification; for
	encodings, see Section 10.2;		encodings, see Section 10.2;
	Algorithm Analysis Document(s): Section 4.3 of this specification.		Algorithm Analysis Document(s): Section 4.3 of this specification.
	12.2.3. JOSE Algorithms Registration (2/2)		12.2.6. JOSE Algorithms Registration (2/2)
	This section registers the following value in the IANA "JSON Web		This section registers the following value in the IANA "JSON Web
	Signature and Encryption Algorithms" registry [IANA.JOSE.Algorithms].		Signature and Encryption Algorithms" registry [IANA.JOSE.Algorithms].
	Algorithm Name: ECDH25519;		Algorithm Name: ECDH25519;
	Algorithm Description: NIST-compliant co-factor Diffie-Hellman w/		Algorithm Description: NIST-compliant co-factor Diffie-Hellman w/
	curve Wei25519 and key derivation function HKDF SHA256;		curve Wei25519 and key derivation function HKDF SHA256;
	Algorithm Usage Locations: alg;		Algorithm Usage Locations: alg;
	JOSE Implementation Requirements: Optional;		JOSE Implementation Requirements: Optional;
	Change Controller: IESG;		Change Controller: IESG;
	Reference: specified in Section 4.1 of this specification; for		Reference: specified in Section 4.1 of this specification; for
	encodings, see Section 10.3;		encodings, see Section 10.3;
	Algorithm Analysis Document(s): Section 4.1 of this specification.		Algorithm Analysis Document(s): Section 4.1 of this specification.
	12.3. JOSE IANA Considerations for Wei448		12.3. COSE/JOSE IANA Considerations for Wei448
	NOTE: This draft does not request COSE IANA registrations.		12.3.1. COSE Elliptic Curves Registration
	12.3.1. JOSE Elliptic Curves Registration		This section registers the following value in the IANA "COSE Elliptic
			Curves" registry [IANA.COSE.Curves].
			Name: Wei448;
			Value: TBD (Requested value: -2);
			Key Type: EC2 or OKP;
			Description: short-Weierstrass curve Wei448;
			Change Controller: IESG;
			Reference: specified in Appendix M.3 of this specification; for
			encodings, see Section 10.1;
			Recommended: Yes.
			(Note that The "kty" value for Wei448 may be "EC2" or "OKP".)
			12.3.2. COSE Algorithms Registration (1/2)
			This section registers the following value in the IANA "COSE
			Algorithms" registry [IANA.COSE.Algorithms].
			Name: ECDSA448;
			Value: TBD (Requested value: -48);
			Description: ECDSA with SHAKE256 and curve Wei448;
			Change Controller: IESG;
			Reference: specified in Section 4.4 of this specification; for
			encodings, see Section 10.2;
			Recommended: Yes.
			12.3.3. COSE Algorithms Registration (2/2)
			This section registers the following value in the IANA "COSE
			Algorithms" registry [IANA.COSE.Algorithms].
			Name: ECDH448;
			Value: TBD (Requested value: -49);
			Description: NIST-compliant co-factor Diffie-Hellman w/ curve Wei448
			and key derivation function HKDF SHA512;
			Change Controller: IESG;
			Reference: specified in Section 4.4 of this specification; for
			encodings, see Section 10.1; for key derivation, see
			Section 11.1 of [RFC8152];
			Recommended: Yes.
			12.3.4. JOSE Elliptic Curves Registration
	This section registers the following value in the IANA "JSON Web Key		This section registers the following value in the IANA "JSON Web Key
	Elliptic Curve" registry [IANA.JOSE.Curves].		Elliptic Curve" registry [IANA.JOSE.Curves].
	Curve Name: Wei448;		Curve Name: Wei448;
	Curve Description: short-Weierstrass curve Wei448;		Curve Description: short-Weierstrass curve Wei448;
	JOSE Implementation Requirements: Optional;		JOSE Implementation Requirements: Optional;
	Change Controller: IESG;		Change Controller: IESG;
	Reference: specified in Appendix M.3 of this specification; for		Reference: specified in Appendix M.3 of this specification; for
	encodings, see Section 10.1.		encodings, see Section 10.1.
	(Note that The "kty" value for Wei448 may be "EC" or "OKP".)		(Note that The "kty" value for Wei448 may be "EC" or "OKP".)
	12.3.2. JOSE Algorithms Registration (1/2)		12.3.5. JOSE Algorithms Registration (1/2)
	This section registers the following value in the IANA "JSON Web		This section registers the following value in the IANA "JSON Web
	Signature and Encryption Algorithms" registry [IANA.JOSE.Algorithms].		Signature and Encryption Algorithms" registry [IANA.JOSE.Algorithms].
	Algorithm Name: ECDSA448;		Algorithm Name: ECDSA448;
	Algorithm Description: ECDSA using SHAKE256 and curve Wei448;		Algorithm Description: ECDSA using SHAKE256 and curve Wei448;
	Algorithm Usage Locations: alg;		Algorithm Usage Locations: alg;
	JOSE Implementation Requirements: Optional;		JOSE Implementation Requirements: Optional;
	Change Controller: IESG;		Change Controller: IESG;
	Reference: specified in Section 4.4 of this specification; for		Reference: specified in Section 4.4 of this specification; for
	encodings, see Section 10.2;		encodings, see Section 10.2;
	Algorithm Analysis Document(s): Section 4.4 of this specification.		Algorithm Analysis Document(s): Section 4.4 of this specification.
	12.3.3. JOSE Algorithms Registration (2/2)		12.3.6. JOSE Algorithms Registration (2/2)
	This section registers the following value in the IANA "JSON Web		This section registers the following value in the IANA "JSON Web
	Signature and Encryption Algorithms" registry [IANA.JOSE.Algorithms].		Signature and Encryption Algorithms" registry [IANA.JOSE.Algorithms].
	Algorithm Name: ECDH448;		Algorithm Name: ECDH448;
	Algorithm Description: NIST-compliant co-factor Diffie-Hellman w/		Algorithm Description: NIST-compliant co-factor Diffie-Hellman w/
	curve Wei448;		curve Wei448;
	Algorithm Usage Locations: alg;		Algorithm Usage Locations: alg;
	JOSE Implementation Requirements: Optional;		JOSE Implementation Requirements: Optional;
	Change Controller: IESG;		Change Controller: IESG;
	Reference: specified in Section 4.4 of this specification; for		Reference: specified in Section 4.4 of this specification; for
	skipping to change at page 35, line 35 ¶		skipping to change at page 38, line 23 ¶
	for generating k, see Appendix P.		for generating k, see Appendix P.
	If P is a fixed base point G of the curve, the pair (k, R:=k*G) is		If P is a fixed base point G of the curve, the pair (k, R:=k*G) is
	commonly called a public-private key pair, the integer k the private		commonly called a public-private key pair, the integer k the private
	key, and the point R the corresponding public key. The private key k		key, and 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		can be represented as an integer in the interval [0,n-1], where G has
	order n. If this representation is nonzero, R has order n;		order n. If this representation is nonzero, R has order n;
	otherwise, it has order one and is the identity element O of the		otherwise, it has order one and is the identity element O of the
	curve.		curve.
			A curve E defined over the field GF(q) has order |E| relatively close
			to q, where, in fact, |E|=q+1-t for some integer t (the so-called
			trace) with absolute value at most 2*|sqrt(q)|. This is commonly
			referred to as the Hasse bound.
	In this document, a quadratic twist of a curve E defined over a field		In this document, a quadratic twist of a curve E defined over a field
	GF(q) is a specific curve E' related to E defined over the same		GF(q) is a specific curve E' related to E defined over the same
	field, with cardinality |E'|, where |E|+|E'|=2*(q+1). If E is a		field, with cardinality |E'|, where |E|+|E'|=2*(q+1). If E is a
	curve in one of the curve models specified in this document, a		curve in one of the curve models specified in this document, a
	quadratic twist E' of this curve can be expressed using the same		quadratic twist E' of this curve can be expressed using the same
	curve model, although (naturally) with its own curve parameters (see		curve model, although (naturally) with its own curve parameters (see
	Appendix A). Points that are both points of E and E' have order one		Appendix A). Points that are both points of E and E' have order one
	or two. Two curves E and E' defined over a field GF(q) are said to		or two. 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		be isogenous if these have the same order and are said to be
	isomorphic if these have the same group structure. Note that		isomorphic if these have the same group structure. Note that
	isomorphic curves have necessarily the same order and are, thus, a		isomorphic curves have necessarily the same order and are, thus, a
	special case of isogenous curves. Further details are out of scope.		special case of isogenous curves. Further details are out of scope.
	Weierstrass curves can have prime order, whereas Montgomery curves		Curves in short-Weierstrass form can have prime order, whereas
	and twisted Edwards curves always have an order that is a multiple of		Montgomery curves and twisted Edwards curves always have an order
	four (and, thereby, a small subgroup of cardinality four).		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		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		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		is a nonzero element of GF(q), and can be uniquely recovered from
	such a representation. The latter representation is commonly called		such a representation. The latter representation is commonly called
	a representation in projective coordinates. Sometimes, yet other		a representation in projective coordinates. Sometimes, yet other
	representations are useful (e.g., representation in Jacobian		representations are useful (e.g., representation in Jacobian
	coordinates). Further details are out of scope.		coordinates). Further details are out of scope.
	The group laws in Appendix C are mostly expressed in terms of affine		The group laws in Appendix C are mostly expressed in terms of affine
	skipping to change at page 135, line 20 ¶		skipping to change at page 137, line 20 ¶
	One can show that the statistical distance of the distribution on Z_n		One can show that the statistical distance of the distribution on Z_n
	is at most roughly N/n times as large as the statistical distance of		is at most roughly N/n times as large as the statistical distance of
	the source distribution on Z_N (if the latter is relatively		the source distribution on Z_N (if the latter is relatively
	negligible compared to n/N). Details are out of scope.		negligible compared to n/N). Details are out of scope.
	Note that, under the above conditions, if N:=2^m and if n has bit-		Note that, under the above conditions, if N:=2^m and if n has bit-
	length m, this conversion function fails with probability 1- n/N		length m, this conversion function fails with probability 1- n/N
	(which is at most 1/2) and, if it succeeds, does not inflate the		(which is at most 1/2) and, if it succeeds, does not inflate the
	statistical distance by more than (roughly) a factor two.		statistical distance by more than (roughly) a factor two.
			Appendix Q. ECDSA signatures
			The ECDSA signature scheme is specified in FIPS Pub 186-4
			[FIPS-186-4], ANSI X9.2-2005 [ANSI-X9.62], SEC 1 [SEC1], and many
			other standards and can be instantiated with suitable combinations of
			short-Weierstrass curves and hash functions (that satisfy particular
			cryptographic criteria). Despite of its wide-spread use, some
			details seem less well-understood. We, therefore, provide a concise
			specification of ECDSA (for short-Weierstrass curves defined over a
			prime field GF(p)) and give some examples of ECDSA computations where
			the underlying short-Weierstrass curve has co-factor h>1 and domain
			parameter n that differs from the output size of the used hash
			function, illustrated with the curves Wei25519 and Wei448 introduced
			in this document. Our description is consistent with all
			forementioned standards.
			The signing operation takes as inputs a message m (represented as a
			bit string) and a private key d in the interval [1,n-1] and produces
			as output a signature, which is an ordered pair (r, s) of integers in
			the interval [1,n-1], where n is the order of the base point G of the
			curve in question. The signature verification operation takes as
			inputs a message m, a public key Q, and a signature (r,s) and
			produces as output the value "valid" or "invalid", depending upon
			whether the message was purportedly signed by a holder of the private
			key of the public-private key pair (d, Q) for the curve used with the
			signature scheme. Full details are provided below.
			Q.1. ECDSA Signing Operation
			The signing operation involves the following steps:
			a. Generate a random ephemeral public-private key pair (k, R:=k*G),
			by generating a random integer k in the interval [1,n-1] and
			computing R:=k*G (see, e.g., Appendix B.1);
			b. Compute k1:=(1/k) (mod n) (see, e.g., NOTE 1 of Appendix K.2);
			c. Set xR to the x-coordinate of the (affine) point R, convert this
			element of the field GF(p) to the integer r0 in the interval
			[0,p-1], and set r:= r0 (mod n), where xR is converted to r0 by
			subesequently using the FE2OS and OS2I mappings of Appendix I.5
			and Appendix I.3, respectively;
			d. Compute the hash value E:=H(m) according to the applicable hash
			function H, where E is a bit string of length hashlen;
			e. Represent E as the integer e in the interval [0, 2^l-1], where e
			is the integer representation of the l-prefix of E, using the
			BS2I mapping of Appendix I.2, and where l is the bit-length of n.
			For a definition of the l-prefix, see Appendix I.1;
			f. Compute s:= k1*(e+ r*d) (mod n);
			g. Return to the first step if r and s are not both integers in the
			interval [1,n-1];
			h. Output the ordered pair (r, s) as the signature.
			Q.2. ECDSA Verification Operation
			The verification operation involves the following steps:
			a. Check that the purported signer's public key Q is a point of the
			curve in question of order n (and output "reject" if this is not
			the case);
			b. Check that the coordinates of the purported signature (r, s) are
			both integers in the interval [1,n-1] (and output "reject" if
			this is not the case);
			c. Compute the hash value E:=H(m) according to the applicable hash
			function H, where E is a bit string of length hashlen;
			d. Represent E as the integer e in the interval [0, 2^l-1], where e
			is the integer representation of the l-prefix of E, using the
			BS2I mapping of Appendix I.2, and where l is the bit-length of n.
			(For a definition of the l-prefix, see Appendix I.1);
			e. Compute s1:=(1/s) (mod n) (see, e.g., Appendix K.2); compute u:=
			e*s1 (mod n) and v:= r*s1 (mod n);
			f. Compute the point R':= u*G+v*Q. Check whether R' is the identity
			element O of the curve (and output "reject" if this is the case);
			g. Set xR' to the x-coordinate of the (affine) point R, convert this
			element of the field GF(p) to the integer r0' in the interval
			[0,p-1], and set r':= r0' (mod n), where xR' is converted to r0'
			by subesequently using the FE2OS and OS2I mappings of
			Appendix I.5 and Appendix I.3, respectively;
			h. Output "accept" if r'=r; output "reject" otherwise.
			NOTE 1: For prime-order curves, r generally uniquely represents the
			x-coordinate of R (since, by the Hasse bound, |E|=n is relatively
			close to p). For curves with co-factor h>1, this result holds only
			if one would know r0 (mod n*h), rather than r:= r0 (mod n).
			NOTE 2: If an ECDSA signature (r, s) is valid for a particular
			message m and public key Q, then so is (r,-s) - the so-called
			malleability. Note that this corresponds to changing the ephemeral
			signing key pair (k, R) in the first step of the signing operation to
			(-k, -R), where the y-coordinates of R:=(xR, yR) and -R=(xR, -yR)
			have different parity (see Appendix H). Since any party (not just
			the signer) can recompute the ephemeral signing key R' from a valid
			signature, since R':=(1/s)(e*G+r*Q), this implies that any party can
			retroactively put the ECDSA signature in a form where the
			y-coordinate of the ephemeral signing key has a fixed parity. This
			observation can be used to put ECDSA signatures in a form that
			generally allows unique and efficient recovery of R from r for prime-
			order curves (due to NOTE 1 above) and more efficient signature
			verification methods. Further details are out of scope.
			Q.3. Representation Examples ECDSA
			We present some examples of ECDSA computations, when used with curve
			Wei25519 and SHA256 (see Appendix Q.3.1), with Wei25519 and SHAKE128
			with output size d=256 (see Appendix Q.3.2), and with Wei448 and
			SHAKE256 with output size d=512 (see Appendix Q.3.3). In each case,
			we indicate the signer's public key Q:=d*G, the ephemeral signing key
			R:=k*G ,the message m that is signed, and some intermediate values in
			the ECDSA signing operation resulting in signature (r,s). We write
			R:=(xR, yR) and Q:=(xQ, yQ), and include the ascii representation of
			message m. Note that the domain parameter n of curve Wei25519 has
			bit-size l:=253, whereas the corresponding domain parameter for
			Wei448 has bit-size l:=446.
			Q.3.1. Example of ECDSA with Wei25519 and SHA-256
			d 47941274660029138864396347947568908774951195017212284524777080461
			79444885588
			(=0x0a996146 d73d096f 6a606ad8 72e11b12 ce973033 524591c3
			ebcc630d b6368854).
			xQ 34422557393689369648095312405803933433606568476197477554293337733
			87341283644
			(=0x079c3f69 9b688181 69038c35 39c11eb5 96d09f5b 12a242b4
			ce660f13 3368c13c).
			yQ 76981661982917351630937517222412729130882368858134322156485762195
			67913357634
			(=0x110501f6 1dff511e d6c4e9b9 bfd5acbe 8bf043b8 c3e381dd
			f5771306 479ad142).
			k 17426547602876470587191777825317027698752636279275919375559360929
			53735113209
			(=0x03da4ec1 8dc83b53 5ab8857c bbd289ae 40e6d25b ba52923c
			e6b217a0 348ca9f9).
			xR 38236544880946097675798638032669186189501319930946799635186226253
			710117141679
			(=0x54891e12 88cf078e f3f1444c c1919e30 67eb5dd6 1c6f45d1
			94b9c0e1 192d7caf).
			yR 24120175139256121256267158437786975197587143475570212981221664791
			614551611968
			(=0x3553890b d265d561 032e2daa 10b9820c 4845dbf8 f6b4f432
			08f5df99 c375da40).
			r 20515169942847866059327052174542149852157381340472616051764715622
			82845886734
			(=0x04891e12 88cf078e f3f1444c c1919e2f ff907c7c ed9935a1
			dc5dd15d 4860590e).
			1/k 41122695303709273156068243481808769134600808188172269288861174824
			34446546266
			(=0x0917764a 5a76024b e9608472 bfec99be 0cffacbe 0a5a6805
			0e4e75bc 36a0d55a).
			m "example ECDSA w/ Wei25519 and SHA-256"
			(=0x65 78616d70 6c652045 43445341 20772f20 57656932 35353139
			20616e64 20534841 2d323536).
			E 10340924651306471157182528854495725311608440786255119926874295925
			4624066081637
			(=0xe49f8f34 0ac7fd87 1ca6c035 1ac83b97 2ec4711e f4a79d37
			214b6b94 c6f41365).
			e 12926155814133088946478161068119656639510550982818899908592869906
			828008260204
			(=0x1c93f1e6 8158ffb0 e394d806 a3590772 e5d88e23 de94f3a6
			e4296d72 98de826c).
			s 18145968192643101430203980459406244543409512911444833316246990876
			74236833451
			(=0x04030680 d490837e 0b50800d 5052feb3 8181da43 f14fea65
			d75fff8e 095d8eab).
			The ECDSA signature (r,s) can be represented uniquely as the 64-octet
			string
			0x04891e12 88cf078e f3f1444c c1919e2f ff907c7c ed9935a1 dc5dd15d
			4860590e
			04030680 d490837e 0b50800d 5052feb3 8181da43 f14fea65 d75fff8e
			095d8eab,
			where this string is the right-concatenation of the integers r and s,
			each represented as fixed-size octet string in tight MSB/msb-order
			using the ZnE2OS mapping of Appendix I.6. Since an ECDSA signature
			(r, s) if valid only if the ECDSA signature (r,-s) is, one can
			alternatively use the representation
			0x04891e12 88cf078e f3f1444c c1919e2f ff907c7c ed9935a1 dc5dd15d
			4860590e
			0bfcf97f 2b6f7c81 f4af7ff2 afad014c 935d1f9a b1a7b270 80b2638c
			53984542,
			with the same representation conventions.
			Q.3.2. Example of ECDSA with Wei25519 and SHAKE128
			d 50032130580855419870069268521079636534051105694026315073511374709
			23129445444
			(=0x0b0fb7de 7b857528 c16cc691 f91acb6a e6f83700 c2257210
			d9ce4a66 540f5c44).
			xQ 49674872575618115649605301860097524739691386255387989689284412105
			715250815836
			(=0x6dd2fb44 ebc47199 0558875c 338b32a0 01c04e5e 54b0239f
			931ba404 43fee35c).
			yQ 19668752079014976246249662506722644231308019872013845936101364656
			882653051514
			(=0x2b7c1e81 e0d7311a 7e73c581 ac8d7478 f5d8402e a25ecf03
			2fcf49b3 ebe3ba7a).
			k 67458228593538039868031175183537823353427877783158546151245140204
			51058711301
			(=0x0eea001c 69e39d65 a93a736f 51dab17d 3c89d712 67b95dba
			28f43e6c 6d73fb05).
			xR 22710793528316744414502819712682283876956423576126122262984645007
			656889457787
			(=0x3235da86 6c184868 db1060f4 c57414ba f9dd8bbf af94eb8e
			65a26fa8 146d9c7b).
			yR 48228386115947942380117850340406514077008333836380715701663219971
			594920954196
			(=0x6aa04c98 30a51d5a 226fc67b 6ec00aa4 66eae465 432825e3
			c8da192d 330c8954).
			r 99977679631995777258326002355330115438507449798639944497879219280
			0526704820
			(=0x0235da86 6c184868 db1060f4 c57414ba bb409e23 c6ae150b
			5d6b4658 fd8c20b4).
			1/k 16237902548817115200666748510759761693156732885271500846541777492
			82633956147
			(=0x03970860 022244d0 1cee5f2e 973372d7 2000b51d 2d75731c
			0e27428a 7e723b33).
			m "example ECDSA w/ Wei25519 and SHAKE128"
			(=0x6578 616d706c 65204543 44534120 772f2057 65693235 35313920
			616e6420 5348414b 45313238).
			E 52885769330535495835899107243770360963478954388007874330946529931
			479220563171
			(=0x74ec48e0 d8b9c37c 7ad823b5 e1d9e837 45b4c7c5 d02f2938
			1f99196f f2052ce3).
			e 66107211663169369794873884054712951204348692985009842913683162414
			34902570396
			(=0x0e9d891c 1b17386f 8f5b0476 bc3b3d06 e8b698f8 ba05e527
			03f3232d fe40a59c).
			s 21018124433820277670749322033999530145769351947494095769585139740
			41491232262
			(=0x04a5956c 6d03d578 40764c7d 33e8159a 2c875830 0b5a4228
			f585dc0f b8135606).
			The ECDSA signature (r,s) can be represented uniquely as the 64-octet
			string
			0x0235da86 6c184868 db1060f4 c57414ba bb409e23 c6ae150b 5d6b4658
			fd8c20b4
			04a5956c 6d03d578 40764c7d 33e8159a 2c875830 0b5a4228 f585dc0f
			b8135606,
			where this string is the right-concatenation of the integers r and s,
			each represented as fixed-size octet string in tight MSB/msb-order
			using the ZnE2OS mapping of Appendix I.6. Since an ECDSA signature
			(r, s) if valid only if the ECDSA signature (r,-s) is, one can
			alternatively use the representation
			0x0235da86 6c184868 db1060f4 c57414ba bb409e23 c6ae150b 5d6b4658
			fd8c20b4
			0b5a6a93 92fc2a87 bf89b382 cc17ea65 e857a1ae 979d5aad 628c870a
			a4e27de7,
			with the same representation conventions.
			Q.3.3. Example of ECDSA with Wei448 and SHAKE256
			d 83773921833883065724152755040779926324701042667680137762329241115
			92597160376444120699241862910141955866217224630560765595890572227
			9690
			(=0x1d818b12 92af6ef4 3f0ed657 b55d2ab7 a0cd1e64 516414d1
			d32ea610 dd6dddbe af65bc96 df648e6d fac1b907 6588b37e 984d5860
			7390970a).
			xQ 40351504322781497250899987383866753965468971276834772118588405333
			77140867939355980788573436893357369201402928958042617224896092079
			46142
			(=0x8e1f426a 4a1af133 ff970fe2 76693c7a eaa78786 361b1cfe
			4ccbd786 e020ba9a 0bf65a1d 5d9a128a f85c63a2 79a00139 7aca56db
			15341b9e).
			yQ 55735504615964066386264989698774850924544182484936624265048483231
			35693859362627880184586282439234602798023594054611737412667543758
			11547
			(=0xc44e5e0f 2c254d23 1dc082db 77175e8c fd37793c 22ebe200
			77905a5f 750b3c9f 4a95d4d5 4e1a1e54 d2d31689 4249252d 0c8b1c45
			1c1481db).
			k 56463034235306169014882307562036113095966844917631298686749571574
			22895909756933115614724351575144190884397720504249121444938140865
			3424
			(=0x13e308f8 2f7eb169 78a86240 a2087c59 38ad954c 5a725311
			00e2738b 93f87064 06846d1b 0348c213 5cd8f9db 21cbf970 6b70fa40
			29364070).
			xR 46421117529223435940590399200091023258880155395346929342228475577
			87411917154572694868891187346300643187653728654052509827159201295
			60118
			(=0xa37ff9a3 9734a3dc 9ccf72b7 cb3b8e5e 20d4e1f1 655c973a
			c72e4aa4 6f139529 84b1cd37 2524bf09 c4e38684 5c88cc79 e8e19242
			42398e36).
			yR 48450878695819342796480063527087959345962966106444727188216313803
			37436540801561730584163096514114057681225129685101546366763700225
			61560
			(=0xaaa6202c df8711b2 6e5a8802 6c5d86b3 2f320d89 8f48a809
			40818982 bb74e0cc 7b884f20 aad090fb 90c4c93f fd84ed56 c03451d8
			84fc7718).
			r 10079181314443091413124208805690796541198087360981026328153965618
			84491837923780980544976081512453123921447854472219263731684084102
			60560
			(=0x237ff9a3 9734a3dc 9ccf72b7 cb3b8e5e 20d4e1f1 655c973a
			c72e4aa5 757f4d55 fc1416a3 c77851e9 820a019f 40fdadcf a1f00d1c
			eb890450).
			1/k 13511362508598651506450197334516130806445911047753884276726477993
			82054003440714897722657048821186399503939251111689038388764827779
			24830
			(=0x2f96a107 4a355722 1f20fd90 aed12db3 83b3c32f 593079f4
			779e2942 3ad2b5e6 0ea15bdc a57e5827 04ed1f09 e42b8352 68428208
			502444de).
			m "example ECDSA w/ Wei448 and SHAKE256"
			(=0x6578616d 706c6520 45434453 4120772f 20576569 34343820
			616e6420 5348414b 45323536).
			E 12090734314062687821830960462859241481351750980975210807010692417
			87788290188009052883047169049228170145424614719943072950310100584
			3039685804727137826504734
			(=0xe6da473c 90ccc33d 35b6f458 dda7a718 6296d1fc f6ed5139
			49978903 10c3eb0b 448726c3 470051e9 4562c319 070156c1 36b6818b
			eb9b4c18 873fbc40 3b38001e).
			e 16386000512814751750588212096686160936149469654286309627413103110
			39082128948717862895885154262738521307509222558257976323832793566
			29766
			(=0x39b691cf 243330cf 4d6dbd16 3769e9c6 18a5b47f 3dbb544e
			5265e240 c430fac2 d121c9b0 d1c0147a 5158b0c6 41c055b0 4dada062
			fae6d306).
			s 13548644118210160703789217445495123183108197273149701428544426319
			69721549289474790694640600902913761876631795267154847305287335592
			32284
			(=0x2fb83e89 3ce77084 18cfff70 d02c01df d4c10a3f 90e0546e
			993d82ba 823b5b5b d9b62b3d 521cdbf5 c6144ade c58d1084 401c1f21
			45f3971c).
			The ECDSA signature (r,s) can be represented uniquely as the
			112-octet string
			0x237ff9a3 9734a3dc 9ccf72b7 cb3b8e5e 20d4e1f1 655c973a c72e4aa5
			757f4d55 fc1416a3 c77851e9 820a019f 40fdadcf a1f00d1c eb890450
			2fb83e89 3ce77084 18cfff70 d02c01df d4c10a3f 90e0546e 993d82ba
			823b5b5b d9b62b3d 521cdbf5 c6144ade c58d1084 401c1f21 45f3971c,
			where this string is the right-concatenation of the integers r and s,
			each represented as fixed-size octet string in tight MSB/msb-order
			using the ZnE2OS mapping of Appendix I.6. Since an ECDSA signature
			(r, s) if valid only if the ECDSA signature (r,-s) is, one can
			alternatively use the representation
			0x237ff9a3 9734a3dc 9ccf72b7 cb3b8e5e 20d4e1f1 655c973a c72e4aa5
			757f4d55 fc1416a3 c77851e9 820a019f 40fdadcf a1f00d1c eb890450
			1047c176 c3188f7b e730008f 2fd3fe20 2b3ef5c0 6f1fab91 66c27d44
			fa8ec88d ea98b00c 5cb95a9a 5b587793 c8387ed0 e35ca371 6564add7,
			with the same representation conventions.
	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. 38 change blocks.
	151 lines changed or deleted		720 lines changed or added
This html diff was produced by rfcdiff 1.48. The latest version is available from http://tools.ietf.org/tools/rfcdiff/