rfc9380v2.txt		rfc9380.txt
	Internet Research Task Force (IRTF) A. Faz-Hernandez		Internet Research Task Force (IRTF) A. Faz-Hernandez
	Request for Comments: 9380 Cloudflare, Inc.		Request for Comments: 9380 Cloudflare, Inc.
	Category: Informational S. Scott		Category: Informational S. Scott
	ISSN: 2070-1721 Cornell Tech		ISSN: 2070-1721 Oso Security, Inc.
	N. Sullivan		N. Sullivan
	Cloudflare, Inc.		Cloudflare, Inc.
	R. S. Wahby		R. S. Wahby
	Stanford University		Stanford University
	C. A. Wood		C. A. Wood
	Cloudflare, Inc.		Cloudflare, Inc.
	August 2023		August 2023
	Hashing to Elliptic Curves		Hashing to Elliptic Curves
	skipping to change at line 74 ¶		skipping to change at line 74 ¶
	3. Encoding Byte Strings to Elliptic Curves		3. Encoding Byte Strings to Elliptic Curves
	3.1. Domain Separation Requirements		3.1. Domain Separation Requirements
	4. Utility Functions		4. Utility Functions
	4.1. The sgn0 Function		4.1. The sgn0 Function
	5. Hashing to a Finite Field		5. Hashing to a Finite Field
	5.1. Efficiency Considerations in Extension Fields		5.1. Efficiency Considerations in Extension Fields
	5.2. hash_to_field Implementation		5.2. hash_to_field Implementation
	5.3. expand_message		5.3. expand_message
	5.3.1. expand_message_xmd		5.3.1. expand_message_xmd
	5.3.2. expand_message_xof		5.3.2. expand_message_xof
	5.3.3. Using DSTs Longer Than 255 Bytes		5.3.3. Using DSTs Longer than 255 Bytes
	5.3.4. Defining Other expand_message Variants		5.3.4. Defining Other expand_message Variants
	6. Deterministic Mappings		6. Deterministic Mappings
	6.1. Choosing a Mapping Function		6.1. Choosing a Mapping Function
	6.2. Interface		6.2. Interface
	6.3. Notation		6.3. Notation
	6.4. Sign of the Resulting Point		6.4. Sign of the Resulting Point
	6.5. Exceptional Cases		6.5. Exceptional Cases
	6.6. Mappings for Weierstrass Curves		6.6. Mappings for Weierstrass Curves
	6.6.1. Shallue-van de Woestijne Method		6.6.1. Shallue-van de Woestijne Method
	6.6.2. Simplified Shallue-van de Woestijne-Ulas Method		6.6.2. Simplified Shallue-van de Woestijne-Ulas Method
	skipping to change at line 309 ¶		skipping to change at line 309 ¶
	Certain hash-to-curve algorithms restrict the form of the curve		Certain hash-to-curve algorithms restrict the form of the curve
	equation, the characteristic of the field, or the parameters of the		equation, the characteristic of the field, or the parameters of the
	curve. For each algorithm presented, this document lists the		curve. For each algorithm presented, this document lists the
	relevant restrictions.		relevant restrictions.
	The table below summarizes quantities relevant to hashing to curves:		The table below summarizes quantities relevant to hashing to curves:
	+========+=====================+=======================+		+========+=====================+=======================+
	| Symbol | Meaning | Relevance |		| Symbol | Meaning | Relevance |
	+========+=====================+=======================+		+========+=====================+=======================+
	| F,q,p | A finite field F of | For prime fields, q = |		| F,q,p | A finite field F of | For prime fields, |
	| | characteristic p | p; otherwise, q = p^m |		| | characteristic p | q = p; otherwise, |
	| | and #F = q = p^m. | and m>1. |		| | and #F = q = p^m. | q = p^m and m>1. |
	+--------+---------------------+-----------------------+		+--------+---------------------+-----------------------+
	| E | Elliptic curve. | E is specified by an |		| E | Elliptic curve. | E is specified by an |
	| | | equation and a field |		| | | equation and a field |
	| | | F. |		| | | F. |
	+--------+---------------------+-----------------------+		+--------+---------------------+-----------------------+
	| n | Number of points on | n = h * r, for h and |		| n | Number of points on | n = h * r, for h and |
	| | the elliptic curve | r defined below. |		| | the elliptic curve | r defined below. |
	| | E. | |		| | E. | |
	+--------+---------------------+-----------------------+		+--------+---------------------+-----------------------+
	| G | A prime-order | G is a destination |		| G | A prime-order | G is a destination |
	skipping to change at line 1022 ¶		skipping to change at line 1022 ¶
	Output:		Output:
	- uniform_bytes, a byte string.		- uniform_bytes, a byte string.
	Steps:		Steps:
	1. ABORT if len_in_bytes > 65535 or len(DST) > 255		1. ABORT if len_in_bytes > 65535 or len(DST) > 255
	2. DST_prime = DST || I2OSP(len(DST), 1)		2. DST_prime = DST || I2OSP(len(DST), 1)
	3. msg_prime = msg || I2OSP(len_in_bytes, 2) || DST_prime		3. msg_prime = msg || I2OSP(len_in_bytes, 2) || DST_prime
	4. uniform_bytes = H(msg_prime, len_in_bytes)		4. uniform_bytes = H(msg_prime, len_in_bytes)
	5. return uniform_bytes		5. return uniform_bytes
	5.3.3. Using DSTs Longer Than 255 Bytes		5.3.3. Using DSTs Longer than 255 Bytes
	The expand_message variants defined in this section accept domain		The expand_message variants defined in this section accept domain
	separation tags of at most 255 bytes. If applications require a		separation tags of at most 255 bytes. If applications require a
	domain separation tag longer than 255 bytes, e.g., because of		domain separation tag longer than 255 bytes, e.g., because of
	requirements imposed by an invoking protocol, implementors MUST		requirements imposed by an invoking protocol, implementors MUST
	compute a short domain separation tag by hashing, as follows:		compute a short domain separation tag by hashing, as follows:
	* For expand_message_xmd using hash function H, DST is computed as		* For expand_message_xmd using hash function H, DST is computed as
	DST = H("H2C-OVERSIZE-DST-" || a_very_long_DST)		DST = H("H2C-OVERSIZE-DST-" || a_very_long_DST)
	skipping to change at line 1380 ¶		skipping to change at line 1380 ¶
	defined by the equation		defined by the equation
	K * t^2 = s^3 + J * s^2 + s		K * t^2 = s^3 + J * s^2 + s
	6.7.1. Elligator 2 Method		6.7.1. Elligator 2 Method
	Bernstein, Hamburg, Krasnova, and Lange give a mapping that applies		Bernstein, Hamburg, Krasnova, and Lange give a mapping that applies
	to any curve with a point of order 2 [BHKL13], which they call		to any curve with a point of order 2 [BHKL13], which they call
	Elligator 2.		Elligator 2.
	Preconditions: A Montgomery curve K * t^2 = s^3 + J * s^2 + s where J		Preconditions: A Montgomery curve K * t^2 = s^3 + J * s^2 + s where
	!= 0, K != 0, and (J^2 - 4) / K^2 is non-zero and non-square in F.		J != 0, K != 0, and (J^2 - 4) / K^2 is non-zero and non-square in F.
	Constants:		Constants:
	* J and K, the parameters of the elliptic curve.		* J and K, the parameters of the elliptic curve.
	* Z, a non-square element of F. Appendix H.3 gives a Sage script		* Z, a non-square element of F. Appendix H.3 gives a Sage script
	[SAGE] that outputs the RECOMMENDED Z.		[SAGE] that outputs the RECOMMENDED Z.
	Sign of t: This mapping fixes the sign of t as specified in [BHKL13].		Sign of t: This mapping fixes the sign of t as specified in [BHKL13].
	No additional adjustment is required.		No additional adjustment is required.
	skipping to change at line 1761 ¶		skipping to change at line 1761 ¶
	[FIPS186-4].		[FIPS186-4].
	P521_XMD:SHA-512_SSWU_RO_ is defined as follows:		P521_XMD:SHA-512_SSWU_RO_ is defined as follows:
	* encoding type: hash_to_curve (Section 3)		* encoding type: hash_to_curve (Section 3)
	* E: y^2 = x^3 + A * x + B, where		* E: y^2 = x^3 + A * x + B, where
	- A = -3		- A = -3
	- B = 0x51953eb9618e1c9a1f929a21a0b68540eea2da725b99b315f3b8b48		- B = 0x51953eb9618e1c9a1f929a21a0b68540eea2da725b99b315f3b8b4899
	9918ef109e156193951ec7e937b1652c0bd3bb1bf073573df883d2c34		18ef109e156193951ec7e937b1652c0bd3bb1bf073573df883d2c34f1ef451f
	f1ef451fd46b503f00		d46b503f00
	* p: 2^521 - 1		* p: 2^521 - 1
	* m: 1		* m: 1
	* k: 256		* k: 256
	* expand_message: expand_message_xmd (Section 5.3.1)		* expand_message: expand_message_xmd (Section 5.3.1)
	* H: SHA-512		* H: SHA-512
	skipping to change at line 1831 ¶		skipping to change at line 1831 ¶
	* h_eff: 8		* h_eff: 8
	edwards25519_XMD:SHA-512_ELL2_RO_ is identical to curve25519_XMD:SHA-		edwards25519_XMD:SHA-512_ELL2_RO_ is identical to curve25519_XMD:SHA-
	512_ELL2_RO_, except for the following parameters:		512_ELL2_RO_, except for the following parameters:
	* E: a * v^2 + w^2 = 1 + d * v^2 * w^2, where		* E: a * v^2 + w^2 = 1 + d * v^2 * w^2, where
	- a = -1		- a = -1
	- d = 0x52036cee2b6ffe738cc740797779e89800700a4d4141d8ab75eb4d		- d = 0x52036cee2b6ffe738cc740797779e89800700a4d4141d8ab75eb4dca1
	ca135978a3		35978a3
	* f: Twisted Edwards Elligator 2 method (Section 6.8.2)		* f: Twisted Edwards Elligator 2 method (Section 6.8.2)
	* M: curve25519, defined in [RFC7748], Section 4.1		* M: curve25519, defined in [RFC7748], Section 4.1
	* rational_map: the birational maps defined in [RFC7748],		* rational_map: the birational maps defined in [RFC7748],
	Section 4.1		Section 4.1
	curve25519_XMD:SHA-512_ELL2_NU_ is identical to curve25519_XMD:SHA-		curve25519_XMD:SHA-512_ELL2_NU_ is identical to curve25519_XMD:SHA-
	512_ELL2_RO_, except that the encoding type is encode_to_curve		512_ELL2_RO_, except that the encoding type is encode_to_curve
	skipping to change at line 2048 ¶		skipping to change at line 2048 ¶
	* Z: -(2 + I)		* Z: -(2 + I)
	* E': y'^2 = x'^3 + A' * x' + B', where		* E': y'^2 = x'^3 + A' * x' + B', where
	- A' = 240 * I		- A' = 240 * I
	- B' = 1012 * (1 + I)		- B' = 1012 * (1 + I)
	* iso_map: the isogeny map from E' to E given in Appendix E.3		* iso_map: the isogeny map from E' to E given in Appendix E.3
	* h_eff: 0xbc69f08f2ee75b3584c6a0ea91b352888e2a8e9145ad7689986ff031		* h_eff: 0xbc69f08f2ee75b3584c6a0ea91b352888e2a8e9145ad7689986ff0315
	508ffe1329c2f178731db956d82bf015d1212b02ec0ec69d7477c1ae954cbc066		08ffe1329c2f178731db956d82bf015d1212b02ec0ec69d7477c1ae954cbc06689
	89f6a359894c0adebbf6b4e8020005aaa95551		f6a359894c0adebbf6b4e8020005aaa95551
	BLS12381G2_XMD:SHA-256_SSWU_NU_ is identical to BLS12381G2_XMD:SHA-		BLS12381G2_XMD:SHA-256_SSWU_NU_ is identical to BLS12381G2_XMD:SHA-
	256_SSWU_RO_, except that the encoding type is encode_to_curve		256_SSWU_RO_, except that the encoding type is encode_to_curve
	(Section 3).		(Section 3).
	Note that the h_eff values for these suites are chosen for		Note that the h_eff values for these suites are chosen for
	compatibility with the fast cofactor clearing method described by		compatibility with the fast cofactor clearing method described by
	Budroni and Pintore ([BP17], Section 4.1) and are summarized in		Budroni and Pintore ([BP17], Section 4.1) and are summarized in
	Appendix G.3.		Appendix G.3.
	skipping to change at line 3324 ¶		skipping to change at line 3324 ¶
	* y = y' * y_num / y_den, where		* y = y' * y_num / y_den, where
	- y_num = k_(3,3) * x'^3 + k_(3,2) * x'^2 + k_(3,1) * x' +		- y_num = k_(3,3) * x'^3 + k_(3,2) * x'^2 + k_(3,1) * x' +
	k_(3,0)		k_(3,0)
	- y_den = x'^3 + k_(4,2) * x'^2 + k_(4,1) * x' + k_(4,0)		- y_den = x'^3 + k_(4,2) * x'^2 + k_(4,1) * x' + k_(4,0)
	The constants used to compute x_num are as follows:		The constants used to compute x_num are as follows:
	* k_(1,0) = 0x8e38e38e38e38e38e38e38e38e38e38e38e38e38e38e38e38e38e3		* k_(1,0) =0x8e38e38e38e38e38e38e38e38e38e38e38e38e38e38e38e38e38e38
	8daaaaa8c7		daaaaa8c7
	* k_(1,1) = 0x7d3d4c80bc321d5b9f315cea7fd44c5d595d2fc0bf63b92dfff104		* k_(1,1) =
	4f17c6581		0x7d3d4c80bc321d5b9f315cea7fd44c5d595d2fc0bf63b92dfff1044f17c6581
	* k_(1,2) = 0x534c328d23f234e6e2a413deca25caece4506144037c40314ecbd0		* k_(1,2) =
	b53d9dd262		0x534c328d23f234e6e2a413deca25caece4506144037c40314ecbd0b53d9dd262
	* k_(1,3) = 0x8e38e38e38e38e38e38e38e38e38e38e38e38e38e38e38e38e38e3		* k_(1,3) =
	8daaaaa88c		0x8e38e38e38e38e38e38e38e38e38e38e38e38e38e38e38e38e38e38daaaaa88c
	The constants used to compute x_den are as follows:		The constants used to compute x_den are as follows:
	* k_(2,0) = 0xd35771193d94918a9ca34ccbb7b640dd86cd409542f8487d9fe6b7		* k_(2,0) =
	45781eb49b		0xd35771193d94918a9ca34ccbb7b640dd86cd409542f8487d9fe6b745781eb49b
	* k_(2,1) = 0xedadc6f64383dc1df7c4b2d51b54225406d36b641f5e41bbc52a56		* k_(2,1) =
	612a8c6d14		0xedadc6f64383dc1df7c4b2d51b54225406d36b641f5e41bbc52a56612a8c6d14
	The constants used to compute y_num are as follows:		The constants used to compute y_num are as follows:
	* k_(3,0) = 0x4bda12f684bda12f684bda12f684bda12f684bda12f684bda12f68		* k_(3,0) =
	4b8e38e23c		0x4bda12f684bda12f684bda12f684bda12f684bda12f684bda12f684b8e38e23c
	* k_(3,1) = 0xc75e0c32d5cb7c0fa9d0a54b12a0a6d5647ab046d686da6fdffc90		* k_(3,1) =
	fc201d71a3		0xc75e0c32d5cb7c0fa9d0a54b12a0a6d5647ab046d686da6fdffc90fc201d71a3
	* k_(3,2) = 0x29a6194691f91a73715209ef6512e576722830a201be2018a765e8		* k_(3,2) =
	5a9ecee931		0x29a6194691f91a73715209ef6512e576722830a201be2018a765e85a9ecee931
	* k_(3,3) = 0x2f684bda12f684bda12f684bda12f684bda12f684bda12f684bda1		* k_(3,3) =
	2f38e38d84		0x2f684bda12f684bda12f684bda12f684bda12f684bda12f684bda12f38e38d84
	The constants used to compute y_den are as follows:		The constants used to compute y_den are as follows:
	* k_(4,0) = 0xffffffffffffffffffffffffffffffffffffffffffffffffffffff		* k_(4,0) =
	fefffff93b		0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffefffff93b
	* k_(4,1) = 0x7a06534bb8bdb49fd5e9e6632722c2989467c1bfc8e8d978dfb425		* k_(4,1) =
	d2685c2573		0x7a06534bb8bdb49fd5e9e6632722c2989467c1bfc8e8d978dfb425d2685c2573
	* k_(4,2) = 0x6484aa716545ca2cf3a70c3fa8fe337e0a3d21162f0d6299a7bf81		* k_(4,2) =
	92bfd2a76f		0x6484aa716545ca2cf3a70c3fa8fe337e0a3d21162f0d6299a7bf8192bfd2a76f
	E.2. 11-Isogeny Map for BLS12-381 G1		E.2. 11-Isogeny Map for BLS12-381 G1
	The 11-isogeny map from (x', y') on E' to (x, y) on E is given by the		The 11-isogeny map from (x', y') on E' to (x, y) on E is given by the
	following rational functions:		following rational functions:
	* x = x_num / x_den, where		* x = x_num / x_den, where
	- x_num = k_(1,11) * x'^11 + k_(1,10) * x'^10 + k_(1,9) * x'^9 +		- x_num = k_(1,11) * x'^11 + k_(1,10) * x'^10 + k_(1,9) * x'^9 +
	... + k_(1,0)		... + k_(1,0)
	skipping to change at line 4301 ¶		skipping to change at line 4301 ¶
	admits an efficiently computable endomorphism, psi, that can be used		admits an efficiently computable endomorphism, psi, that can be used
	to speed up cofactor clearing for G2 [SBCDK09] [FKR11] [BP17] (see		to speed up cofactor clearing for G2 [SBCDK09] [FKR11] [BP17] (see
	also Section 7). This section implements the endomorphism psi and a		also Section 7). This section implements the endomorphism psi and a
	fast cofactor clearing method described by Budroni and Pintore		fast cofactor clearing method described by Budroni and Pintore
	[BP17].		[BP17].
	The functions in this section operate on points whose coordinates are		The functions in this section operate on points whose coordinates are
	represented as ratios, i.e., (xn, xd, yn, yd) corresponds to the		represented as ratios, i.e., (xn, xd, yn, yd) corresponds to the
	point (xn / xd, yn / yd); see Appendix G.1 for further discussion of		point (xn / xd, yn / yd); see Appendix G.1 for further discussion of
	projective coordinates. When points are represented in affine		projective coordinates. When points are represented in affine
	coordinates, one can simply ignore the denominators (xd == 1 and yd		coordinates, one can simply ignore the denominators (xd == 1 and
	== 1).		yd == 1).
	The following function computes the Frobenius endomorphism for an		The following function computes the Frobenius endomorphism for an
	element of F = GF(p^2) with basis (1, I), where I^2 + 1 == 0 in F.		element of F = GF(p^2) with basis (1, I), where I^2 + 1 == 0 in F.
	(This is the base field of the elliptic curve E defined in		(This is the base field of the elliptic curve E defined in
	Section 8.8.2.)		Section 8.8.2.)
	frobenius(x)		frobenius(x)
	Input: x, an element of GF(p^2).		Input: x, an element of GF(p^2).
	Output: a, an element of GF(p^2).		Output: a, an element of GF(p^2).
	skipping to change at line 8044 ¶		skipping to change at line 8044 ¶
	Authors' Addresses		Authors' Addresses
	Armando Faz-Hernandez		Armando Faz-Hernandez
	Cloudflare, Inc.		Cloudflare, Inc.
	101 Townsend St		101 Townsend St
	San Francisco, CA 94107		San Francisco, CA 94107
	United States of America		United States of America
	Email: armfazh@cloudflare.com		Email: armfazh@cloudflare.com
	Sam Scott		Sam Scott
	Cornell Tech		Oso Security, Inc.
	2 West Loop Rd		335 Madison Ave
	New York, New York 10044		New York, NY 10017
	United States of America		United States of America
	Email: sam.scott@cornell.edu		Email: sam.scott89@gmail.com
	Nick Sullivan		Nick Sullivan
	Cloudflare, Inc.		Cloudflare, Inc.
	101 Townsend St		101 Townsend St
	San Francisco, CA 94107		San Francisco, CA 94107
	United States of America		United States of America
	Email: nicholas.sullivan@gmail.com		Email: nicholas.sullivan@gmail.com
	Riad S. Wahby		Riad S. Wahby
	Stanford University		Stanford University
End of changes. 24 change blocks.
	48 lines changed or deleted		48 lines changed or added
This html diff was produced by rfcdiff 1.48.