rfc9496.original   rfc9496.txt 
Crypto Forum Research Group H. de Valence Internet Research Task Force (IRTF) H. de Valence
Internet-Draft Request for Comments: 9496
Intended status: Informational J. Grigg Category: Informational J. Grigg
Expires: 29 February 2024 ISSN: 2070-1721
M. Hamburg M. Hamburg
I. Lovecruft I. Lovecruft
G. Tankersley G. Tankersley
F. Valsorda F. Valsorda
28 August 2023 December 2023
The ristretto255 and decaf448 Groups The ristretto255 and decaf448 Groups
draft-irtf-cfrg-ristretto255-decaf448-08
Abstract Abstract
This memo specifies two prime-order groups, ristretto255 and This memo specifies two prime-order groups, ristretto255 and
decaf448, suitable for safely implementing higher-level and complex decaf448, suitable for safely implementing higher-level and complex
cryptographic protocols. The ristretto255 group can be implemented cryptographic protocols. The ristretto255 group can be implemented
using Curve25519, allowing existing Curve25519 implementations to be using Curve25519, allowing existing Curve25519 implementations to be
reused and extended to provide a prime-order group. Likewise, the reused and extended to provide a prime-order group. Likewise, the
decaf448 group can be implemented using edwards448. decaf448 group can be implemented using edwards448.
This document is a product of the Crypto Forum Research Group (CFRG) This document is a product of the Crypto Forum Research Group (CFRG)
in the IRTF. in the IRTF.
Status of This Memo Status of This Memo
This Internet-Draft is submitted in full conformance with the This document is not an Internet Standards Track specification; it is
provisions of BCP 78 and BCP 79. published for informational purposes.
Internet-Drafts are working documents of the Internet Engineering
Task Force (IETF). Note that other groups may also distribute
working documents as Internet-Drafts. The list of current Internet-
Drafts is at https://datatracker.ietf.org/drafts/current/.
Internet-Drafts are draft documents valid for a maximum of six months This document is a product of the Internet Research Task Force
and may be updated, replaced, or obsoleted by other documents at any (IRTF). The IRTF publishes the results of Internet-related research
time. It is inappropriate to use Internet-Drafts as reference and development activities. These results might not be suitable for
material or to cite them other than as "work in progress." deployment. This RFC represents the consensus of the Crypto Forum
Research Group of the Internet Research Task Force (IRTF). Documents
approved for publication by the IRSG are not candidates for any level
of Internet Standard; see Section 2 of RFC 7841.
This Internet-Draft will expire on 29 February 2024. Information about the current status of this document, any errata,
and how to provide feedback on it may be obtained at
https://www.rfc-editor.org/info/rfc9496.
Copyright Notice Copyright Notice
Copyright (c) 2023 IETF Trust and the persons identified as the Copyright (c) 2023 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 (https://trustee.ietf.org/ Provisions Relating to IETF Documents
license-info) in effect on the date of publication of this document. (https://trustee.ietf.org/license-info) in effect on the date of
Please review these documents carefully, as they describe your rights publication of this document. Please review these documents
and restrictions with respect to this document. Code Components carefully, as they describe your rights and restrictions with respect
extracted from this document must include Revised BSD License text as to this document.
described in Section 4.e of the Trust Legal Provisions and are
provided without warranty as described in the Revised BSD License.
Table of Contents Table of Contents
1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . 3 1. Introduction
2. Notation and Conventions Used In This Document . . . . . . . 4 2. Notation and Conventions Used in This Document
2.1. Negative field elements . . . . . . . . . . . . . . . . . 5 2.1. Negative Field Elements
2.2. Constant time operations . . . . . . . . . . . . . . . . 5 2.2. Constant-Time Operations
3. The group abstraction . . . . . . . . . . . . . . . . . . . . 5 3. The Group Abstraction
4. ristretto255 . . . . . . . . . . . . . . . . . . . . . . . . 7 4. ristretto255
4.1. Implementation constants . . . . . . . . . . . . . . . . 7 4.1. Implementation Constants
4.2. Square root of a ratio of field elements . . . . . . . . 8 4.2. Square Root of a Ratio of Field Elements
4.3. ristretto255 group operations . . . . . . . . . . . . . . 9 4.3. ristretto255 Group Operations
4.3.1. Decode . . . . . . . . . . . . . . . . . . . . . . . 9 4.3.1. Decode
4.3.2. Encode . . . . . . . . . . . . . . . . . . . . . . . 9 4.3.2. Encode
4.3.3. Equals . . . . . . . . . . . . . . . . . . . . . . . 10 4.3.3. Equals
4.3.4. Element derivation . . . . . . . . . . . . . . . . . 11 4.3.4. Element Derivation
4.4. Scalar field . . . . . . . . . . . . . . . . . . . . . . 12 4.4. Scalar Field
5. decaf448 . . . . . . . . . . . . . . . . . . . . . . . . . . 12 5. decaf448
5.1. Implementation constants . . . . . . . . . . . . . . . . 13 5.1. Implementation Constants
5.2. Square root of a ratio of field elements . . . . . . . . 14 5.2. Square Root of a Ratio of Field Elements
5.3. decaf448 group operations . . . . . . . . . . . . . . . . 14 5.3. decaf448 Group Operations
5.3.1. Decode . . . . . . . . . . . . . . . . . . . . . . . 14 5.3.1. Decode
5.3.2. Encode . . . . . . . . . . . . . . . . . . . . . . . 15 5.3.2. Encode
5.3.3. Equals . . . . . . . . . . . . . . . . . . . . . . . 16 5.3.3. Equals
5.3.4. Element derivation . . . . . . . . . . . . . . . . . 16 5.3.4. Element Derivation
5.4. Scalar field . . . . . . . . . . . . . . . . . . . . . . 17 5.4. Scalar Field
6. API Considerations . . . . . . . . . . . . . . . . . . . . . 17 6. API Considerations
7. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 18 7. IANA Considerations
8. Security Considerations . . . . . . . . . . . . . . . . . . . 18 8. Security Considerations
9. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . 18 9. References
10. Normative References . . . . . . . . . . . . . . . . . . . . 19 9.1. Normative References
11. Informative References . . . . . . . . . . . . . . . . . . . 19 9.2. Informative References
Appendix A. Test vectors for ristretto255 . . . . . . . . . . . 20 Appendix A. Test Vectors for ristretto255
A.1. Multiples of the generator . . . . . . . . . . . . . . . 20 A.1. Multiples of the Generator
A.2. Invalid encodings . . . . . . . . . . . . . . . . . . . . 20 A.2. Invalid Encodings
A.3. Group elements from byte strings . . . . . . . . . . . . 21 A.3. Group Elements from Uniform Byte Strings
A.4. Square root of a ratio of field elements . . . . . . . . 22 A.4. Square Root of a Ratio of Field Elements
Appendix B. Test vectors for decaf448 . . . . . . . . . . . . . 23 Appendix B. Test Vectors for decaf448
B.1. Multiples of the generator . . . . . . . . . . . . . . . 23 B.1. Multiples of the Generator
B.2. Invalid encodings . . . . . . . . . . . . . . . . . . . . 24 B.2. Invalid Encodings
B.3. Group elements from uniform byte strings . . . . . . . . 26 B.3. Group Elements from Uniform Byte Strings
Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 27 Acknowledgements
Authors' Addresses
1. Introduction 1. Introduction
Decaf [Decaf] is a technique for constructing prime-order groups with Decaf [Decaf] is a technique for constructing prime-order groups with
non-malleable encodings from non-prime-order elliptic curves. nonmalleable encodings from non-prime-order elliptic curves.
Ristretto extends this technique to support cofactor-8 curves such as Ristretto extends this technique to support cofactor-8 curves such as
Curve25519 [RFC7748]. In particular, this allows an existing Curve25519 [RFC7748]. In particular, this allows an existing
Curve25519 library to provide a prime-order group with only a thin Curve25519 library to provide a prime-order group with only a thin
abstraction layer. abstraction layer.
Many group-based cryptographic protocols require the number of Many group-based cryptographic protocols require the number of
elements in the group (the group order) to be prime. Prime-order elements in the group (the group order) to be prime. Prime-order
groups are useful because every non-identity element of the group is groups are useful because every non-identity element of the group is
a generator of the entire group. This means the group has a cofactor a generator of the entire group. This means the group has a cofactor
of 1, and all elements are equivalent from the perspective of of 1, and all elements are equivalent from the perspective of
Discrete Log Hardness. hardness of the discrete logarithm problem.
Edwards curves provide a number of implementation benefits for Edwards curves provide a number of implementation benefits for
cryptography, such as complete addition formulas with no exceptional cryptography. These benefits include formulas for curve operations
points and formulas among the fastest known for curve operations. that are among the fastest currently known, and for which the
However, the group of points on the curve is not of prime order, addition formulas are complete with no exceptional points. However,
i.e., it has a cofactor larger than 1. This abstraction mismatch is the group of points on the curve is not of prime order, i.e., it has
usually handled by means of ad-hoc protocol tweaks, such as a cofactor larger than 1. This abstraction mismatch is usually
multiplying by the cofactor in an appropriate place, or not at all. handled, if it is handled at all, by means of ad hoc protocol tweaks
such as multiplying by the cofactor in an appropriate place.
Even for simple protocols such as signatures, these tweaks can cause Even for simple protocols such as signatures, these tweaks can cause
subtle issues. For instance, Ed25519 implementations may have subtle issues. For instance, Ed25519 implementations may have
different validation behavior between batched and singleton different validation behavior between batched and singleton
verification, and at least as specified in [RFC8032], the set of verification, and at least as specified in [RFC8032], the set of
valid signatures is not defined by the standard. valid signatures is not defined precisely [Ed25519ValidCrit].
For more complex protocols, careful analysis is required as the For more complex protocols, careful analysis is required as the
original security proofs may no longer apply, and the tweaks for one original security proofs may no longer apply, and the tweaks for one
protocol may have disastrous effects when applied to another (for protocol may have disastrous effects when applied to another (for
instance, the octuple-spend vulnerability in [MoneroVuln]). instance, the octuple-spend vulnerability described in [MoneroVuln]).
Decaf and Ristretto fix this abstraction mismatch in one place for Decaf and Ristretto fix this abstraction mismatch in one place for
all protocols, providing an abstraction to protocol implementors that all protocols, providing an abstraction to protocol implementors that
matches the abstraction commonly assumed in protocol specifications, matches the abstraction commonly assumed in protocol specifications
while still allowing the use of high-performance curve while still allowing the use of high-performance curve
implementations internally. The abstraction layer imposes minor implementations internally. The abstraction layer imposes minor
overhead, and only in the encoding and decoding phases. overhead but only in the encoding and decoding phases.
While Ristretto is a general method, and can be used in conjunction While Ristretto is a general method and can be used in conjunction
with any Edwards curve with cofactor 4 or 8, this document specifies with any Edwards curve with cofactor 4 or 8, this document specifies
the ristretto255 group, which can be implemented using Curve25519, the ristretto255 group, which can be implemented using Curve25519,
and the decaf448 group, which can be implemented using edwards448. and the decaf448 group, which can be implemented using edwards448.
There are other elliptic curves that can be used internally to There are other elliptic curves that can be used internally to
implement ristretto255 or decaf448, and those implementations would implement ristretto255 or decaf448; those implementations would be
be interoperable with a Curve25519- or edwards448-based one, but interoperable with one based on Curve25519 or edwards448, but those
those constructions are out-of-scope for this document. constructions are out of scope for this document.
The Ristretto construction is described and justified in detail at The Ristretto construction is described and justified in detail at
[RistrettoGroup]. [RistrettoGroup].
This document represents the consensus of the Crypto Forum Research This document represents the consensus of the Crypto Forum Research
Group (CFRG). This document is not an IETF product and is not a Group (CFRG). This document is not an IETF product and is not a
standard. standard.
2. Notation and Conventions Used In This Document 2. Notation and Conventions Used in This Document
The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT",
"SHOULD", "SHOULD NOT", "RECOMMENDED", "NOT RECOMMENDED", "MAY", and "SHOULD", "SHOULD NOT", "RECOMMENDED", "NOT RECOMMENDED", "MAY", and
"OPTIONAL" in this document are to be interpreted as described in BCP "OPTIONAL" in this document are to be interpreted as described in BCP
14 [RFC2119] [RFC8174] when, and only when, they appear in all 14 [RFC2119] [RFC8174] when, and only when, they appear in all
capitals, as shown here. capitals, as shown here.
Readers are cautioned that the term "Curve25519" has varying Readers are cautioned that the term "Curve25519" has varying
interpretations in the literature, and that the canonical meaning of interpretations in the literature and that the canonical meaning of
the term has shifted over time. Originally it referred to a specific the term has shifted over time. Originally, it referred to a
Diffie-Hellman key exchange mechanism. Over time, use shifted, and specific Diffie-Hellman key exchange mechanism. Use shifted over
"Curve25519" has been used to refer to either the abstract underlying time, and "Curve25519" has been used to refer to the abstract
curve, or its concrete representation in Montgomery form, or the underlying curve, its concrete representation in Montgomery form, or
specific Diffie-Hellman mechanism. This document uses the term the specific Diffie-Hellman mechanism. This document uses the term
"Curve25519" to refer to the abstract underlying curve, as "Curve25519" to refer to the abstract underlying curve, as
recommended in [Naming]. The abstract Edwards form of the curve we recommended in [Naming]. The abstract Edwards form of the curve we
refer to here as "Curve25519" is in [RFC7748] referred to as refer to here as "Curve25519" is referred to in [RFC7748] as
"edwards25519" and its isogenous Montgomery form is referred to as "edwards25519", and the Montgomery form that is isogenous to the
"curve25519". Edwards form is referred to in [RFC7748] as "curve25519".
Elliptic curve points in this document are represented in extended Elliptic curve points in this document are represented in extended
Edwards coordinates in the (x, y, z, t) format [Twisted], also called Edwards coordinates in the (x, y, z, t) format [Twisted], also called
extended homogeneous coordinates in Section 5.1.4 of [RFC8032]. extended homogeneous coordinates in Section 5.1.4 of [RFC8032].
Field elements are values modulo p, the Curve25519 prime 2^255 - 19 Field elements are values modulo p, the Curve25519 prime 2^255 - 19
or the edwards448 prime 2^448 - 2^224 - 1, as specified in Sections or the edwards448 prime 2^448 - 2^224 - 1, as specified in Sections
4.1 and 4.2 of [RFC7748], respectively. All formulas specify field 4.1 and 4.2 of [RFC7748], respectively. All formulas specify field
operations unless otherwise noted. The symbol ^ denotes operations unless otherwise noted. The symbol ^ denotes
exponentiation. exponentiation.
The | symbol represents a constant-time logical OR. The | symbol represents a constant-time logical OR.
The notation array[A:B] means the elements of array from A to B-1. The notation array[A:B] means the elements of array from A to B-1.
That is, it is exclusive of B. Arrays are indexed starting from 0. That is, it is exclusive of B. Arrays are indexed starting from 0.
A byte is an 8-bit entity (also known as "octet") and a byte string A byte is an 8-bit entity (also known as "octet"), and a byte string
is an ordered sequence of bytes. An N-byte string is a byte string is an ordered sequence of bytes. An N-byte string is a byte string
of N bytes in length. of N bytes in length.
Element encodings are presented as hex encoded byte strings with Element encodings are presented as hex-encoded byte strings with
whitespace added for readability. whitespace added for readability.
2.1. Negative field elements 2.1. Negative Field Elements
As in [RFC8032], given a field element e, define IS_NEGATIVE(e) as As in [RFC8032], given a field element e, define IS_NEGATIVE(e) as
TRUE if the least non-negative integer representing e is odd, and TRUE if the least nonnegative integer representing e is odd and FALSE
FALSE if it is even. This SHOULD be implemented in constant time. if it is even. This SHOULD be implemented in constant time.
2.2. Constant time operations 2.2. Constant-Time Operations
We assume that the field element implementation supports the We assume that the field element implementation supports the
following operations, which SHOULD be implemented in constant time: following operations, which SHOULD be implemented in constant time:
* CT_EQ(u, v): return TRUE if u = v, FALSE otherwise. * CT_EQ(u, v): return TRUE if u = v, FALSE otherwise.
* CT_SELECT(v IF cond ELSE u): return v if cond is TRUE, else return * CT_SELECT(v IF cond ELSE u): return v if cond is TRUE, else return
u. u.
* CT_ABS(u): return -u if IS_NEGATIVE(u), else return u. * CT_ABS(u): return -u if IS_NEGATIVE(u), else return u.
Note that CT_ABS MAY be implemented as: Note that CT_ABS MAY be implemented as:
CT_SELECT(-u IF IS_NEGATIVE(u) ELSE u) CT_SELECT(-u IF IS_NEGATIVE(u) ELSE u)
3. The group abstraction 3. The Group Abstraction
Ristretto and Decaf implement an abstract prime-order group interface Ristretto and Decaf implement an abstract prime-order group interface
that exposes only the behavior that is useful to higher-level that exposes only the behavior that is useful to higher-level
protocols, without leaking curve-related details and pitfalls. protocols, without leaking curve-related details and pitfalls.
Each abstract group exposes operations on abstract element and Each abstract group exposes operations on abstract element and
abstract scalar types. The operations defined on these types abstract scalar types. The operations defined on these types
include: decoding, encoding, equality, addition, negation, include: decoding, encoding, equality, addition, negation,
subtraction and (multi-)scalar multiplication. Each abstract group subtraction, and (multi-)scalar multiplication. Each abstract group
also exposes a deterministic function to derive abstract elements also exposes a deterministic function to derive abstract elements
from fixed-length byte strings. A description of each of these from fixed-length byte strings. A description of each of these
operations is below. operations is below.
Decoding is a function from byte strings to abstract elements with Decoding is a function from byte strings to abstract elements with
built-in validation, so that only the canonical encodings of valid built-in validation, so that only the canonical encodings of valid
elements are accepted. The built-in validation avoids the need for elements are accepted. The built-in validation avoids the need for
explicit invalid curve checks. explicit invalid curve checks.
Encoding is a function from abstract elements to byte strings. Encoding is a function from abstract elements to byte strings.
Internally, an abstract element might have more than one possible Internally, an abstract element might have more than one possible
representation -- for example, the implementation might use representation; for example, the implementation might use projective
projective coordinates. When encoding, all equivalent coordinates. When encoding, all equivalent representations of the
representations of the same element are encoded as identical byte same element are encoded as identical byte strings. Decoding the
strings. Decoding the output of the encoding function always output of the encoding function always succeeds and returns an
succeeds and returns an equivalent element to the encoding input. element equivalent to the encoding input.
The equality check reports whether two representations of an abstract The equality check reports whether two representations of an abstract
element are equivalent. element are equivalent.
The element derivation function maps deterministically from byte The element derivation function maps deterministically from byte
strings of a fixed length to abstract elements. It has two important strings of a fixed length to abstract elements. It has two important
properties. First, if the input is a uniformly random byte string, properties. First, if the input is a uniformly random byte string,
then the output is (within a negligible statistical distance of) a then the output is (within a negligible statistical distance of) a
uniformly random abstract group element. This means the function is uniformly random abstract group element. This means the function is
suitable for selecting random group elements. suitable for selecting random group elements.
Second, although the element derivation function is many-to-one and Second, although the element derivation function is many-to-one and
therefore not strictly invertible, it is not pre-image resistent. On therefore not strictly invertible, it is not pre-image resistant. On
the contrary, given an arbitrary abstract group element P, there is the contrary, given an arbitrary abstract group element P, there is
an efficient algorithm to randomly sample from byte strings that map an efficient algorithm to randomly sample from byte strings that map
to P. In some contexts this property would be a weakness, but it is to P. In some contexts, this property would be a weakness, but it is
important in some contexts: in particular, it means that a important in some contexts: in particular, it means that a
combination of a cryptographic hash function and the element combination of a cryptographic hash function and the element
derivation function is suitable for use in algorithms such as derivation function is suitable to define encoding functions such as
hash_to_curve [draft-irtf-cfrg-hash-to-curve-16]. hash_to_ristretto255 (Appendix B of [RFC9380]) and hash_to_decaf448
(Appendix C of [RFC9380]).
Addition is the group operation. The group has an identity element Addition is the group operation. The group has an identity element
and prime order l. Adding together l copies of the same element and prime order l. Adding together l copies of the same element
gives the identity. Adding the identity element to any element gives the identity. Adding the identity element to any element
returns that element unchanged. Negation returns an element that returns that element unchanged. Negation returns an element that,
added to the negation input returns the identity element. when added to the negation input, gives the identity element.
Subtraction is the addition of a negated element, and scalar Subtraction is the addition of a negated element, and scalar
multiplication is the repeated addition of an element. multiplication is the repeated addition of an element.
4. ristretto255 4. ristretto255
ristretto255 is an instantiation of the abstract prime-order group ristretto255 is an instantiation of the abstract prime-order group
interface defined in Section 3. This document describes how to interface defined in Section 3. This document describes how to
implement the ristretto255 prime-order group using Curve25519 points implement the ristretto255 prime-order group using Curve25519 points
as internal representations. as internal representations.
A "ristretto255 group element" is the abstract element of the prime A "ristretto255 group element" is the abstract element of the prime-
order group. An "element encoding" is the unique reversible encoding order group. An "element encoding" is the unique reversible encoding
of a group element. An "internal representation" is a point on the of a group element. An "internal representation" is a point on the
curve used to implement ristretto255. Each group element can have curve used to implement ristretto255. Each group element can have
multiple equivalent internal representations. multiple equivalent internal representations.
Encoding, decoding, equality, and the element derivation function are Encoding, decoding, equality, and the element derivation function are
defined in Section 4.3. Element addition, subtraction, negation, and defined in Section 4.3. Element addition, subtraction, negation, and
scalar multiplication are implemented by applying the corresponding scalar multiplication are implemented by applying the corresponding
operations directly to the internal representation. operations directly to the internal representation.
The group order is the same as the order of the Curve25519 prime- The group order is the same as the order of the Curve25519 prime-
order subgroup: order subgroup:
l = 2^252 + 27742317777372353535851937790883648493 l = 2^252 + 27742317777372353535851937790883648493
Since ristretto255 is a prime-order group, every element except the Since ristretto255 is a prime-order group, every element except the
identity is a generator, but for interoperability a canonical identity is a generator. However, for interoperability, a canonical
generator is selected, which can be internally represented by the generator is selected, which can be internally represented by the
Curve25519 basepoint, enabling reuse of existing precomputation for Curve25519 base point, enabling reuse of existing precomputation for
scalar multiplication. This is its encoding as produced by the scalar multiplication. The encoding of this canonical generator, as
function specified in Section 4.3.2: produced by the function specified in Section 4.3.2, is:
e2f2ae0a 6abc4e71 a884a961 c500515f 58e30b6a a582dd8d b6a65945 e08d2d76 e2f2ae0a 6abc4e71 a884a961 c500515f 58e30b6a a582dd8d b6a65945 e08d2d76
4.1. Implementation constants 4.1. Implementation Constants
This document references the following constant field element values This document references the following constant field element values
that are used for the implementation of group operations. that are used for the implementation of group operations.
* D = 37095705934669439343138083508754565189542113879843219016388785 * D = 37095705934669439343138083508754565189542113879843219016388785
533085940283555 533085940283555
- This is the Edwards d parameter for Curve25519, as specified in - This is the Edwards d parameter for Curve25519, as specified in
Section 4.1 of [RFC7748]. Section 4.1 of [RFC7748].
* SQRT_M1 = 19681161376707505956807079304988542015446066515923890162 * SQRT_M1 = 19681161376707505956807079304988542015446066515923890162
744021073123829784752 744021073123829784752
skipping to change at page 8, line 4 skipping to change at line 326
* D = 37095705934669439343138083508754565189542113879843219016388785 * D = 37095705934669439343138083508754565189542113879843219016388785
533085940283555 533085940283555
- This is the Edwards d parameter for Curve25519, as specified in - This is the Edwards d parameter for Curve25519, as specified in
Section 4.1 of [RFC7748]. Section 4.1 of [RFC7748].
* SQRT_M1 = 19681161376707505956807079304988542015446066515923890162 * SQRT_M1 = 19681161376707505956807079304988542015446066515923890162
744021073123829784752 744021073123829784752
* SQRT_AD_MINUS_ONE = 2506306895338462347411141415870215270124453150 * SQRT_AD_MINUS_ONE = 2506306895338462347411141415870215270124453150
2492656460079210482610430750235 2492656460079210482610430750235
* INVSQRT_A_MINUS_D = 5446930700890931692099581386874514160539359729 * INVSQRT_A_MINUS_D = 5446930700890931692099581386874514160539359729
2927456921205312896311721017578 2927456921205312896311721017578
* ONE_MINUS_D_SQ = 1159843021668779879193775521855586647937357759715 * ONE_MINUS_D_SQ = 1159843021668779879193775521855586647937357759715
417654439879720876111806838 417654439879720876111806838
* D_MINUS_ONE_SQ = 4044083434630853685810104246932319082624839914623 * D_MINUS_ONE_SQ = 4044083434630853685810104246932319082624839914623
8708352240133220865137265952 8708352240133220865137265952
4.2. Square root of a ratio of field elements 4.2. Square Root of a Ratio of Field Elements
The following function is defined on field elements, and is used to The following function is defined on field elements and is used to
implement other ristretto255 functions. This function is only used implement other ristretto255 functions. This function is only used
internally to implement some of the group operations. internally to implement some of the group operations.
On input field elements u and v, the function SQRT_RATIO_M1(u, v) On input field elements u and v, the function SQRT_RATIO_M1(u, v)
returns: returns:
* (TRUE, +sqrt(u/v)) if u and v are non-zero, and u/v is square; * (TRUE, +sqrt(u/v)) if u and v are nonzero and u/v is square in the
field;
* (TRUE, zero) if u is zero; * (TRUE, zero) if u is zero;
* (FALSE, zero) if v is zero and u is non-zero; * (FALSE, zero) if v is zero and u is nonzero; and
* (FALSE, +sqrt(SQRT_M1*(u/v))) if u and v are non-zero, and u/v is * (FALSE, +sqrt(SQRT_M1*(u/v))) if u and v are nonzero and u/v is
non-square (so SQRT_M1*(u/v) is square), non-square in the field (so SQRT_M1*(u/v) is square in the field),
where +sqrt(x) indicates the non-negative square root of x in the where +sqrt(x) indicates the nonnegative square root of x in the
field. field.
The computation is similar to Section 5.1.3 of [RFC8032], with the The computation is similar to what is described in Section 5.1.3 of
difference that if the input is non-square, the function returns a [RFC8032], with the difference that, if the input is non-square, the
result with a defined relationship to the inputs. This result is function returns a result with a defined relationship to the inputs.
used for efficient implementation of the derivation function. The This result is used for efficient implementation of the derivation
function can be refactored from an existing Ed25519 implementation. function. The function can be refactored from an existing Ed25519
implementation.
SQRT_RATIO_M1(u, v) is defined as follows: SQRT_RATIO_M1(u, v) is defined as follows:
r = (u * v^3) * (u * v^7)^((p-5)/8) // Note: (p - 5) / 8 is an integer. r = (u * v^3) * (u * v^7)^((p-5)/8) // Note: (p - 5) / 8 is an integer.
check = v * r^2 check = v * r^2
correct_sign_sqrt = CT_EQ(check, u) correct_sign_sqrt = CT_EQ(check, u)
flipped_sign_sqrt = CT_EQ(check, -u) flipped_sign_sqrt = CT_EQ(check, -u)
flipped_sign_sqrt_i = CT_EQ(check, -u*SQRT_M1) flipped_sign_sqrt_i = CT_EQ(check, -u*SQRT_M1)
r_prime = SQRT_M1 * r r_prime = SQRT_M1 * r
r = CT_SELECT(r_prime IF flipped_sign_sqrt | flipped_sign_sqrt_i ELSE r) r = CT_SELECT(r_prime IF flipped_sign_sqrt | flipped_sign_sqrt_i ELSE r)
// Choose the nonnegative square root. // Choose the nonnegative square root.
r = CT_ABS(r) r = CT_ABS(r)
was_square = correct_sign_sqrt | flipped_sign_sqrt was_square = correct_sign_sqrt | flipped_sign_sqrt
return (was_square, r) return (was_square, r)
4.3. ristretto255 group operations
4.3. ristretto255 Group Operations
This section describes the implementation of the external functions This section describes the implementation of the external functions
exposed by the ristretto255 prime-order group. exposed by the ristretto255 prime-order group.
4.3.1. Decode 4.3.1. Decode
All elements are encoded as 32-byte strings. Decoding proceeds as All elements are encoded as 32-byte strings. Decoding proceeds as
follows: follows:
1. First, interpret the string as an unsigned integer s in little- 1. Interpret the string as an unsigned integer s in little-endian
endian representation. If the length of the string is not 32 representation. If the length of the string is not 32 bytes or
bytes, or if the resulting value is >= p, decoding fails. if the resulting value is >= p, decoding fails.
* Note: unlike [RFC7748] field element decoding, the most
significant bit is not masked, and non-canonical values are | Note: Unlike the field element decoding described in [RFC7748],
rejected. The test vectors in Appendix A.2 exercise these | the most significant bit is not masked, and non-canonical
edge cases. | values are rejected. The test vectors in Appendix A.2 exercise
| these edge cases.
2. If IS_NEGATIVE(s) returns TRUE, decoding fails. 2. If IS_NEGATIVE(s) returns TRUE, decoding fails.
3. Process s as follows: 3. Process s as follows:
ss = s^2 ss = s^2
u1 = 1 - ss u1 = 1 - ss
u2 = 1 + ss u2 = 1 + ss
u2_sqr = u2^2 u2_sqr = u2^2
v = -(D * u1^2) - u2_sqr v = -(D * u1^2) - u2_sqr
(was_square, invsqrt) = SQRT_RATIO_M1(1, v * u2_sqr) (was_square, invsqrt) = SQRT_RATIO_M1(1, v * u2_sqr)
den_x = invsqrt * u2 den_x = invsqrt * u2
den_y = invsqrt * den_x * v den_y = invsqrt * den_x * v
x = CT_ABS(2 * s * den_x) x = CT_ABS(2 * s * den_x)
y = u1 * den_y y = u1 * den_y
t = x * y t = x * y
4. If was_square is FALSE, or IS_NEGATIVE(t) returns TRUE, or y = 0, 4. If was_square is FALSE, IS_NEGATIVE(t) returns TRUE, or y = 0,
decoding fails. Otherwise, return the group element represented decoding fails. Otherwise, return the group element represented
by the internal representation (x, y, 1, t) as the result of by the internal representation (x, y, 1, t) as the result of
decoding. decoding.
4.3.2. Encode 4.3.2. Encode
A group element with internal representation (x0, y0, z0, t0) is A group element with internal representation (x0, y0, z0, t0) is
encoded as follows: encoded as follows:
1. Process the internal representation into a field element s as 1. Process the internal representation into a field element s as
skipping to change at page 10, line 42 skipping to change at line 464
specifically, this is the encoding of the canonical specifically, this is the encoding of the canonical
representation of s as an integer between 0 and p-1, inclusive. representation of s as an integer between 0 and p-1, inclusive.
Note that decoding and then re-encoding a valid group element will Note that decoding and then re-encoding a valid group element will
yield an identical byte string. yield an identical byte string.
4.3.3. Equals 4.3.3. Equals
The equality function returns TRUE when two internal representations The equality function returns TRUE when two internal representations
correspond to the same group element. Note that internal correspond to the same group element. Note that internal
representations MUST NOT be compared in any other way than specified representations MUST NOT be compared in any way other than specified
here. here.
For two internal representations (x1, y1, z1, t1) and (x2, y2, z2, For two internal representations (x1, y1, z1, t1) and (x2, y2, z2,
t2), if t2), if
(x1 * y2 == y1 * x2) | (y1 * y2 == x1 * x2) CT_EQ(x1 * y2, y1 * x2) | CT_EQ(y1 * y2, x1 * x2)
evaluates to TRUE, then return TRUE. Otherwise, return FALSE. evaluates to TRUE, then return TRUE. Otherwise, return FALSE.
Note that the equality function always returns TRUE when applied to Note that the equality function always returns TRUE when applied to
an internal representation and to the internal representation an internal representation and to the internal representation
obtained by encoding and then re-decoding it. However, the internal obtained by encoding and then re-decoding it. However, the internal
representations themselves might not be identical. representations themselves might not be identical.
Implementations MAY also perform byte comparisons on the encodings of Implementations MAY also perform constant-time byte comparisons on
group elements (produced by Section 4.3.2) for an equivalent, the encodings of group elements (produced by Section 4.3.2) for an
although less efficient, result. equivalent, although less efficient, result.
4.3.4. Element derivation 4.3.4. Element Derivation
The element derivation function operates on 64-byte strings. To The element derivation function operates on 64-byte strings. To
obtain such an input from an arbitrary-length byte string, obtain such an input from an arbitrary-length byte string,
applications should use a domain-separated hash construction, the applications should use a domain-separated hash construction, the
choice of which is out-of-scope for this document. choice of which is out of scope for this document.
The element derivation function on an input string b proceeds as The element derivation function on an input string b proceeds as
follows: follows:
1. Compute P1 as MAP(b[0:32]). 1. Compute P1 as MAP(b[0:32]).
2. Compute P2 as MAP(b[32:64]). 2. Compute P2 as MAP(b[32:64]).
3. Return P1 + P2. 3. Return P1 + P2.
The MAP function is defined on 32-byte strings as: The MAP function is defined on 32-byte strings as:
1. First, mask the most significant bit in the final byte of the 1. Mask the most significant bit in the final byte of the string,
string, and interpret the string as an unsigned integer r in and interpret the string as an unsigned integer r in little-
little-endian representation. Reduce r modulo p to obtain a endian representation. Reduce r modulo p to obtain a field
field element t. element t.
* Masking the most significant bit is equivalent to interpreting * Masking the most significant bit is equivalent to interpreting
the whole string as an unsigned integer in little-endian the whole string as an unsigned integer in little-endian
representation and then reducing it modulo 2^255. representation and then reducing it modulo 2^255.
* Note: similarly to [RFC7748] field element decoding, and
unlike field element decoding in Section 4.3.1, the most | Note: Similar to the field element decoding described in
significant bit is masked, and non-canonical values are | [RFC7748], and unlike the field element decoding described in
accepted. | Section 4.3.1, the most significant bit is masked, and non-
| canonical values are accepted.
2. Process t as follows: 2. Process t as follows:
r = SQRT_M1 * t^2 r = SQRT_M1 * t^2
u = (r + 1) * ONE_MINUS_D_SQ u = (r + 1) * ONE_MINUS_D_SQ
v = (-1 - r*D) * (r + D) v = (-1 - r*D) * (r + D)
(was_square, s) = SQRT_RATIO_M1(u, v) (was_square, s) = SQRT_RATIO_M1(u, v)
s_prime = -CT_ABS(s*t) s_prime = -CT_ABS(s*t)
s = CT_SELECT(s IF was_square ELSE s_prime) s = CT_SELECT(s IF was_square ELSE s_prime)
skipping to change at page 12, line 24 skipping to change at line 533
N = c * (r - 1) * D_MINUS_ONE_SQ - v N = c * (r - 1) * D_MINUS_ONE_SQ - v
w0 = 2 * s * v w0 = 2 * s * v
w1 = N * SQRT_AD_MINUS_ONE w1 = N * SQRT_AD_MINUS_ONE
w2 = 1 - s^2 w2 = 1 - s^2
w3 = 1 + s^2 w3 = 1 + s^2
3. Return the group element represented by the internal 3. Return the group element represented by the internal
representation (w0*w3, w2*w1, w1*w3, w0*w2). representation (w0*w3, w2*w1, w1*w3, w0*w2).
4.4. Scalar field 4.4. Scalar Field
The scalars for the ristretto255 group are integers modulo the order The scalars for the ristretto255 group are integers modulo the order
l of the ristretto255 group. Note that this is the same scalar field l of the ristretto255 group. Note that this is the same scalar field
as Curve25519, allowing existing implementations to be reused. as Curve25519, allowing existing implementations to be reused.
Scalars are encoded as 32-byte strings in little-endian order. Scalars are encoded as 32-byte strings in little-endian order.
Implementations SHOULD check that any scalar s falls in the range 0 Implementations SHOULD check that any scalar s falls in the range 0
<= s < l when parsing them and reject non-canonical scalar encodings. <= s < l when parsing them and reject non-canonical scalar encodings.
Implementations SHOULD reduce scalars modulo l when encoding them as Implementations SHOULD reduce scalars modulo l when encoding them as
byte strings. Omitting these strict range checks is NOT RECOMMENDED byte strings. Omitting these strict range checks is NOT RECOMMENDED
but is allowed to enable reuse of scalar arithmetic implementations but is allowed to enable reuse of scalar arithmetic implementations
in existing Curve25519 libraries. in existing Curve25519 libraries.
Given a uniformly distributed 64-byte string b, implementations can Given a uniformly distributed 64-byte string b, implementations can
obtain a uniformly distributed scalar by interpreting the 64-byte obtain a uniformly distributed scalar by interpreting the 64-byte
string as a 512-bit unsigned integer in little-endian order and string as a 512-bit unsigned integer in little-endian order and
reducing the integer modulo l, as in [RFC8032]. To obtain such an reducing the integer modulo l, as in [RFC8032]. To obtain such an
input from an arbitrary-length byte string, applications should use a input from an arbitrary-length byte string, applications should use a
domain-separated hash construction, the choice of which is out-of- domain-separated hash construction, the choice of which is out of
scope for this document. scope for this document.
5. decaf448 5. decaf448
decaf448 is an instantiation of the abstract prime-order group decaf448 is an instantiation of the abstract prime-order group
interface defined in Section 3. This document describes how to interface defined in Section 3. This document describes how to
implement the decaf448 prime-order group using edwards448 points as implement the decaf448 prime-order group using edwards448 points as
internal representations. internal representations.
A "decaf448 group element" is the abstract element of the prime order A "decaf448 group element" is the abstract element of the prime-order
group. An "element encoding" is the unique reversible encoding of a group. An "element encoding" is the unique reversible encoding of a
group element. An "internal representation" is a point on the curve group element. An "internal representation" is a point on the curve
used to implement decaf448. Each group element can have multiple used to implement decaf448. Each group element can have multiple
equivalent internal representations. equivalent internal representations.
Encoding, decoding, equality, and the element derivation functions Encoding, decoding, equality, and the element derivation functions
are defined in Section 5.3. Element addition, subtraction, negation, are defined in Section 5.3. Element addition, subtraction, negation,
and scalar multiplication are implemented by applying the and scalar multiplication are implemented by applying the
corresponding operations directly to the internal representation. corresponding operations directly to the internal representation.
The group order is the same as the order of the edwards448 prime- The group order is the same as the order of the edwards448 prime-
order subgroup: order subgroup:
l = 2^446 - l = 2^446 -
13818066809895115352007386748515426880336692474882178609894547503885 13818066809895115352007386748515426880336692474882178609894547503885
Since decaf448 is a prime-order group, every element except the Since decaf448 is a prime-order group, every element except the
identity is a generator, but for interoperability a canonical identity is a generator; however, for interoperability, a canonical
generator is selected. This generator can be internally represented generator is selected. This generator can be internally represented
by 2*B, where B is the edwards448 basepoint, enabling reuse of by 2*B, where B is the edwards448 base point, enabling reuse of
existing precomputation for scalar multiplication. This is its existing precomputation for scalar multiplication. The encoding of
encoding as produced by the function specified in Section 5.3.2: this canonical generator, as produced by the function specified in
Section 5.3.2, is:
66666666 66666666 66666666 66666666 66666666 66666666 66666666 66666666 66666666 66666666 66666666 66666666 66666666 66666666
33333333 33333333 33333333 33333333 33333333 33333333 33333333 33333333 33333333 33333333 33333333 33333333 33333333 33333333
This repetitive constant is equal to 1/sqrt(5) in decaf448's field, This repetitive constant is equal to 1/sqrt(5) in decaf448's field,
corresponding to the curve448 base point with x = 5. corresponding to the curve448 base point with x = 5.
5.1. Implementation constants 5.1. Implementation Constants
This document references the following constant field element values This document references the following constant field element values
that are used for the implementation of group operations. that are used for the implementation of group operations.
* D = 72683872429560689054932380788800453435364136068731806028149019 * D = 72683872429560689054932380788800453435364136068731806028149019
918061232816673077268639638369867654593008888446184363736105349801 918061232816673077268639638369867654593008888446184363736105349801
8326358 8326358
- This is the Edwards d parameter for edwards448, as specified in - This is the Edwards d parameter for edwards448, as specified in
Section 4.2 of [RFC7748], and is equal to -39081 in the field. Section 4.2 of [RFC7748], and is equal to -39081 in the field.
* ONE_MINUS_D = 39082 * ONE_MINUS_D = 39082
* ONE_MINUS_TWO_D = 78163 * ONE_MINUS_TWO_D = 78163
* SQRT_MINUS_D = 989442336477322197691770048769290191284175762955299 * SQRT_MINUS_D = 989442336477322197691770048769290191284175762955299
010740998895980437021160012578568021315638965153739277122320928458 010740998895980437021160012578568021315638965153739277122320928458
83226922417596214 83226922417596214
* INVSQRT_MINUS_D = 315019913931389607337177038330951043522456072897 * INVSQRT_MINUS_D = 315019913931389607337177038330951043522456072897
266928557328499619017160722351061360252776265186336876723201881398 266928557328499619017160722351061360252776265186336876723201881398
623946864393857820716 623946864393857820716
5.2. Square root of a ratio of field elements 5.2. Square Root of a Ratio of Field Elements
The following function is defined on field elements, and is used to The following function is defined on field elements and is used to
implement other decaf448 functions. This function is only used implement other decaf448 functions. This function is only used
internally to implement some of the group operations. internally to implement some of the group operations.
On input field elements u and v, the function SQRT_RATIO_M1(u, v) On input field elements u and v, the function SQRT_RATIO_M1(u, v)
returns: returns:
* (TRUE, +sqrt(u/v)) if u and v are non-zero, and u/v is square; * (TRUE, +sqrt(u/v)) if u and v are nonzero and u/v is square in the
field;
* (TRUE, zero) if u is zero; * (TRUE, zero) if u is zero;
* (FALSE, zero) if v is zero and u is non-zero; * (FALSE, zero) if v is zero and u is nonzero; and
* (FALSE, +sqrt(-u/v)) if u and v are non-zero, and u/v is non- * (FALSE, +sqrt(-u/v)) if u and v are nonzero and u/v is non-square
square (so -(u/v) is square), in the field (so -(u/v) is square in the field),
where +sqrt(x) indicates the non-negative square root of x in the where +sqrt(x) indicates the nonnegative square root of x in the
field. field.
The computation is similar to Section 5.2.3 of [RFC8032], with the The computation is similar to what is described in Section 5.2.3 of
difference that if the input is non-square, the function returns a [RFC8032], with the difference that, if the input is non-square, the
result with a defined relationship to the inputs. This result is function returns a result with a defined relationship to the inputs.
used for efficient implementation of the derivation function. The This result is used for efficient implementation of the derivation
function can be refactored from an existing edwards448 function. The function can be refactored from an existing edwards448
implementation. implementation.
SQRT_RATIO_M1(u, v) is defined as follows: SQRT_RATIO_M1(u, v) is defined as follows:
r = u * (u * v)^((p - 3) / 4) // Note: (p - 3) / 4 is an integer. r = u * (u * v)^((p - 3) / 4) // Note: (p - 3) / 4 is an integer.
check = v * r^2 check = v * r^2
was_square = CT_EQ(check, u) was_square = CT_EQ(check, u)
// Choose the nonnegative square root. // Choose the nonnegative square root.
r = CT_ABS(r) r = CT_ABS(r)
return (was_square, r) return (was_square, r)
5.3. decaf448 group operations 5.3. decaf448 Group Operations
This section describes the implementation of the external functions This section describes the implementation of the external functions
exposed by the decaf448 prime-order group. exposed by the decaf448 prime-order group.
5.3.1. Decode 5.3.1. Decode
All elements are encoded as 56-byte strings. Decoding proceeds as All elements are encoded as 56-byte strings. Decoding proceeds as
follows: follows:
1. First, interpret the string as an unsigned integer s in little- 1. Interpret the string as an unsigned integer s in little-endian
endian representation. If the length of the string is not 56 representation. If the length of the string is not 56 bytes or
bytes, or if the resulting value is >= p, decoding fails. if the resulting value is >= p, decoding fails.
* Note: unlike [RFC7748] field element decoding, non-canonical
values are rejected. The test vectors in Appendix B.2 | Note: Unlike the field element decoding described in [RFC7748],
exercise these edge cases. | non-canonical values are rejected. The test vectors in
| Appendix B.2 exercise these edge cases.
2. If IS_NEGATIVE(s) returns TRUE, decoding fails. 2. If IS_NEGATIVE(s) returns TRUE, decoding fails.
3. Process s as follows: 3. Process s as follows:
ss = s^2 ss = s^2
u1 = 1 + ss u1 = 1 + ss
u2 = u1^2 - 4 * D * ss u2 = u1^2 - 4 * D * ss
(was_square, invsqrt) = SQRT_RATIO_M1(1, u2 * u1^2) (was_square, invsqrt) = SQRT_RATIO_M1(1, u2 * u1^2)
u3 = CT_ABS(2 * s * invsqrt * u1 * SQRT_MINUS_D) u3 = CT_ABS(2 * s * invsqrt * u1 * SQRT_MINUS_D)
x = u3 * invsqrt * u2 * INVSQRT_MINUS_D x = u3 * invsqrt * u2 * INVSQRT_MINUS_D
y = (1 - ss) * invsqrt * u1 y = (1 - ss) * invsqrt * u1
t = x * y t = x * y
4. If was_square is FALSE then decoding fails. Otherwise, return 4. If was_square is FALSE, then decoding fails. Otherwise, return
the group element represented by the internal representation (x, the group element represented by the internal representation (x,
y, 1, t) as the result of decoding. y, 1, t) as the result of decoding.
5.3.2. Encode 5.3.2. Encode
A group element with internal representation (x0, y0, z0, t0) is A group element with internal representation (x0, y0, z0, t0) is
encoded as follows: encoded as follows:
1. Process the internal representation into a field element s as 1. Process the internal representation into a field element s as
follows: follows:
skipping to change at page 16, line 9 skipping to change at line 716
specifically, this is the encoding of the canonical specifically, this is the encoding of the canonical
representation of s as an integer between 0 and p-1, inclusive. representation of s as an integer between 0 and p-1, inclusive.
Note that decoding and then re-encoding a valid group element will Note that decoding and then re-encoding a valid group element will
yield an identical byte string. yield an identical byte string.
5.3.3. Equals 5.3.3. Equals
The equality function returns TRUE when two internal representations The equality function returns TRUE when two internal representations
correspond to the same group element. Note that internal correspond to the same group element. Note that internal
representations MUST NOT be compared in any other way than specified representations MUST NOT be compared in any way other than specified
here. here.
For two internal representations (x1, y1, z1, t1) and (x2, y2, z2, For two internal representations (x1, y1, z1, t1) and (x2, y2, z2,
t2), if t2), if
x1 * y2 == y1 * x2 CT_EQ(x1 * y2, y1 * x2)
evaluates to TRUE, then return TRUE. Otherwise, return FALSE. evaluates to TRUE, then return TRUE. Otherwise, return FALSE.
Note that the equality function always returns TRUE when applied to Note that the equality function always returns TRUE when applied to
an internal representation and to the internal representation an internal representation and to the internal representation
obtained by encoding and then re-decoding it. However, the internal obtained by encoding and then re-decoding it. However, the internal
representations themselves might not be identical. representations themselves might not be identical.
Implementations MAY also perform byte comparisons on the encodings of Implementations MAY also perform constant-time byte comparisons on
group elements (produced by Section 5.3.2) for an equivalent, the encodings of group elements (produced by Section 5.3.2) for an
although less efficient, result. equivalent, although less efficient, result.
5.3.4. Element derivation 5.3.4. Element Derivation
The element derivation function operates on 112-byte strings. To The element derivation function operates on 112-byte strings. To
obtain such an input from an arbitrary-length byte string, obtain such an input from an arbitrary-length byte string,
applications should use a domain-separated hash construction, the applications should use a domain-separated hash construction, the
choice of which is out-of-scope for this document. choice of which is out of scope for this document.
The element derivation function on an input string b proceeds as The element derivation function on an input string b proceeds as
follows: follows:
1. Compute P1 as MAP(b[0:56]). 1. Compute P1 as MAP(b[0:56]).
2. Compute P2 as MAP(b[56:112]). 2. Compute P2 as MAP(b[56:112]).
3. Return P1 + P2. 3. Return P1 + P2.
The MAP function is defined on 56-byte strings as: The MAP function is defined on 56-byte strings as:
1. Interpret the string as an unsigned integer r in little-endian 1. Interpret the string as an unsigned integer r in little-endian
representation. Reduce r modulo p to obtain a field element t. representation. Reduce r modulo p to obtain a field element t.
* Note: similarly to [RFC7748] field element decoding, and | Note: Similar to the field element decoding described in
unlike field element decoding in Section 5.3.1, non-canonical | [RFC7748], and unlike the field element decoding described in
values are accepted. | Section 5.3.1, non-canonical values are accepted.
2. Process t as follows: 2. Process t as follows:
r = -t^2 r = -t^2
u0 = d * (r-1) u0 = d * (r-1)
u1 = (u0 + 1) * (u0 - r) u1 = (u0 + 1) * (u0 - r)
(was_square, v) = SQRT_RATIO_M1(ONE_MINUS_TWO_D, (r + 1) * u1) (was_square, v) = SQRT_RATIO_M1(ONE_MINUS_TWO_D, (r + 1) * u1)
v_prime = CT_SELECT(v IF was_square ELSE t * v) v_prime = CT_SELECT(v IF was_square ELSE t * v)
sgn = CT_SELECT(1 IF was_square ELSE -1) sgn = CT_SELECT(1 IF was_square ELSE -1)
s = v_prime * (r + 1) s = v_prime * (r + 1)
w0 = 2 * CT_ABS(s) w0 = 2 * CT_ABS(s)
w1 = s^2 + 1 w1 = s^2 + 1
w2 = s^2 - 1 w2 = s^2 - 1
w3 = v_prime * s * (r - 1) * ONE_MINUS_TWO_D + sgn w3 = v_prime * s * (r - 1) * ONE_MINUS_TWO_D + sgn
3. Return the group element represented by the internal 3. Return the group element represented by the internal
representation (w0*w3, w2*w1, w1*w3, w0*w2). representation (w0*w3, w2*w1, w1*w3, w0*w2).
5.4. Scalar field 5.4. Scalar Field
The scalars for the decaf448 group are integers modulo the order l of The scalars for the decaf448 group are integers modulo the order l of
the decaf448 group. Note that this is the same scalar field as the decaf448 group. Note that this is the same scalar field as
edwards448, allowing existing implementations to be reused. edwards448, allowing existing implementations to be reused.
Scalars are encoded as 56-byte strings in little-endian order. Scalars are encoded as 56-byte strings in little-endian order.
Implementations SHOULD check that any scalar s falls in the range 0 Implementations SHOULD check that any scalar s falls in the range 0
<= s < l when parsing them and reject non-canonical scalar encodings. <= s < l when parsing them and reject non-canonical scalar encodings.
Implementations SHOULD reduce scalars modulo l when encoding them as Implementations SHOULD reduce scalars modulo l when encoding them as
byte strings. Omitting these strict range checks is NOT RECOMMENDED byte strings. Omitting these strict range checks is NOT RECOMMENDED
but is allowed to enable reuse of scalar arithmetic implementations but is allowed to enable reuse of scalar arithmetic implementations
in existing edwards448 libraries. in existing edwards448 libraries.
Given a uniformly distributed 64-byte string b, implementations can Given a uniformly distributed 64-byte string b, implementations can
obtain a uniformly distributed scalar by interpreting the 64-byte obtain a uniformly distributed scalar by interpreting the 64-byte
string as a 512-bit unsigned integer in little-endian order and string as a 512-bit unsigned integer in little-endian order and
reducing the integer modulo l. To obtain such an input from an reducing the integer modulo l. To obtain such an input from an
arbitrary-length byte string, applications should use a domain- arbitrary-length byte string, applications should use a domain-
separated hash construction, the choice of which is out-of-scope for separated hash construction, the choice of which is out of scope for
this document. this document.
6. API Considerations 6. API Considerations
ristretto255 and decaf448 are abstractions which implement two prime- ristretto255 and decaf448 are abstractions that implement two prime-
order groups, and their elements are represented by curve points, but order groups. Their elements are represented by curve points, but
they are not curve points. Implementations SHOULD reflect that: the are not curve points, and implementations SHOULD reflect that fact.
type representing an element of the group SHOULD be opaque to the That is, the type representing an element of the group SHOULD be
caller, meaning they do not expose the underlying curve point or opaque to the caller, meaning they do not expose the underlying curve
field elements. Moreover, implementations SHOULD NOT expose any point or field elements. Moreover, implementations SHOULD NOT expose
internal constants or functions used in the implementation of the any internal constants or functions used in the implementation of the
group operations. group operations.
The reason for this encapsulation is that ristretto255 and decaf448 The reason for this encapsulation is that ristretto255 and decaf448
implementations can change their underlying curve without causing any implementations can change their underlying curve without causing any
breaking change. The ristretto255 and decaf448 constructions are breaking change. The ristretto255 and decaf448 constructions are
carefully designed so that this will be the case, as long as carefully designed so that this will be the case, as long as
implementations do not expose internal representations or operate on implementations do not expose internal representations or operate on
them except as described in this document. In particular, them except as described in this document. In particular,
implementations SHOULD NOT define any external ristretto255 or implementations SHOULD NOT define any external ristretto255 or
decaf448 interface as operating on arbitrary curve points, and they decaf448 interface as operating on arbitrary curve points, and they
SHOULD NOT construct group elements except via decoding, the element SHOULD NOT construct group elements except via decoding, the element
derivation function, or group operations on other valid group derivation function, or group operations on other valid group
elements per Section 3. They are however allowed to apply any elements per Section 3. However, they are allowed to apply any
optimization strategy to the internal representations as long as it optimization strategy to the internal representations as long as it
doesn't change the exposed behavior of the API. doesn't change the exposed behavior of the API.
It is RECOMMENDED that implementations do not perform a decoding and It is RECOMMENDED that implementations not perform a decoding and
encoding operation for each group operation, as it is inefficient and encoding operation for each group operation, as it is inefficient and
unnecessary. Implementations SHOULD instead provide an opaque type unnecessary. Implementations SHOULD instead provide an opaque type
to hold the internal representation through multiple operations. to hold the internal representation through multiple operations.
7. IANA Considerations 7. IANA Considerations
This document has no IANA actions. This document has no IANA actions.
8. Security Considerations 8. Security Considerations
The ristretto255 and decaf448 groups provide higher-level protocols The ristretto255 and decaf448 groups provide higher-level protocols
with the abstraction they expect: a prime-order group. Therefore, with the abstraction they expect: a prime-order group. Therefore,
it's expected to be safer for use in any situation where Curve25519 it's expected to be safer for use in any situation where Curve25519
or edwards448 is used to implement a protocol requiring a prime-order or edwards448 is used to implement a protocol requiring a prime-order
group. Note that the safety of the abstraction can be defeated by group. Note that the safety of the abstraction can be defeated by
implementations that do not follow the guidance in Section 6. implementations that do not follow the guidance in Section 6.
There is no function to test whether an elliptic curve point is a There is no function to test whether an elliptic curve point is a
valid internal representation of a group element. The decoding valid internal representation of a group element. The decoding
function always returns a valid internal representation, or an error, function always returns a valid internal representation or an error,
and allowed operations on valid internal representations return valid and operations exposed by the group per Section 3 return valid
internal representations. In this way, an implementation can internal representations when applied to valid internal
maintain the invariant that an internal representation is always representations. In this way, an implementation can maintain the
valid, so that checking is never necessary, and invalid states are invariant that an internal representation is always valid, so that
unrepresentable. checking is never necessary, and invalid states are unrepresentable.
9. Acknowledgements
The authors would like to thank Daira Hopwood, Riad S. Wahby, 9. References
Christopher Wood, and Thomas Pornin for their comments on the draft.
10. Normative References 9.1. Normative References
[RFC2119] Bradner, S., "Key words for use in RFCs to Indicate [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate
Requirement Levels", BCP 14, RFC 2119, Requirement Levels", BCP 14, RFC 2119,
DOI 10.17487/RFC2119, March 1997, DOI 10.17487/RFC2119, March 1997,
<https://www.rfc-editor.org/info/rfc2119>. <https://www.rfc-editor.org/info/rfc2119>.
[RFC8174] Leiba, B., "Ambiguity of Uppercase vs Lowercase in RFC [RFC8174] Leiba, B., "Ambiguity of Uppercase vs Lowercase in RFC
2119 Key Words", BCP 14, RFC 8174, DOI 10.17487/RFC8174, 2119 Key Words", BCP 14, RFC 8174, DOI 10.17487/RFC8174,
May 2017, <https://www.rfc-editor.org/info/rfc8174>. May 2017, <https://www.rfc-editor.org/info/rfc8174>.
11. Informative References 9.2. Informative References
[Decaf] Hamburg, M., "Decaf: Eliminating cofactors through point [Decaf] Hamburg, M., "Decaf: Eliminating cofactors through point
compression", 2015, compression", 2015,
<https://www.shiftleft.org/papers/decaf/decaf.pdf>. <https://www.shiftleft.org/papers/decaf/decaf.pdf>.
[Ed25519ValidCrit]
de Valence, H., "It's 255:19AM. Do you know what your
validation criteria are?", 4 October 2020,
<https://hdevalence.ca/blog/2020-10-04-its-25519am>.
[MoneroVuln] [MoneroVuln]
Nick, J., "Exploiting Low Order Generators in One-Time Nick, J., "Exploiting Low Order Generators in One-Time
Ring Signatures", 2017, Ring Signatures", May 2017,
<https://jonasnick.github.io/blog/2017/05/23/exploiting- <https://jonasnick.github.io/blog/2017/05/23/exploiting-
low-order-generators-in-one-time-ring-signatures/>. low-order-generators-in-one-time-ring-signatures/>.
[Naming] Bernstein, D. J., "[Cfrg] 25519 naming", 2014, [Naming] Bernstein, D. J., "Subject: [Cfrg] 25519 naming", message
to the Cfrg mailing list, 26 August 2014,
<https://mailarchive.ietf.org/arch/msg/cfrg/- <https://mailarchive.ietf.org/arch/msg/cfrg/-
9LEdnzVrE5RORux3Oo_oDDRksU/>. 9LEdnzVrE5RORux3Oo_oDDRksU/>.
[RFC7748] Langley, A., Hamburg, M., and S. Turner, "Elliptic Curves [RFC7748] Langley, A., Hamburg, M., and S. Turner, "Elliptic Curves
for Security", RFC 7748, DOI 10.17487/RFC7748, January for Security", RFC 7748, DOI 10.17487/RFC7748, January
2016, <https://www.rfc-editor.org/info/rfc7748>. 2016, <https://www.rfc-editor.org/info/rfc7748>.
[RFC8032] Josefsson, S. and I. Liusvaara, "Edwards-Curve Digital [RFC8032] Josefsson, S. and I. Liusvaara, "Edwards-Curve Digital
Signature Algorithm (EdDSA)", RFC 8032, Signature Algorithm (EdDSA)", RFC 8032,
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>.
[RFC9380] Faz-Hernandez, A., Scott, S., Sullivan, N., Wahby, R. S.,
and C. A. Wood, "Hashing to Elliptic Curves", RFC 9380,
DOI 10.17487/RFC9380, August 2023,
<https://www.rfc-editor.org/info/rfc9380>.
[RistrettoGroup] [RistrettoGroup]
de Valence, H., Lovecruft, I., Arcieri, T., and M. de Valence, H., Lovecruft, I., Arcieri, T., and M.
Hamburg, "The Ristretto Group", 2018, Hamburg, "The Ristretto Group", <https://ristretto.group>.
<https://ristretto.group>.
[Twisted] Hisil, H., Wong, K. K., Carter, G., and E. Dawson, [Twisted] Hisil, H., Wong, K. K., Carter, G., and E. Dawson,
"Twisted Edwards Curves Revisited", 2008, "Twisted Edwards Curves Revisited", Cryptology ePrint
Archive, Paper 2008/522, December 2008,
<https://eprint.iacr.org/2008/522>. <https://eprint.iacr.org/2008/522>.
[draft-irtf-cfrg-hash-to-curve-16] Appendix A. Test Vectors for ristretto255
Faz-Hernández, A., Scott, S., Sullivan, N., Wahby, R.S.,
and C.A. Wood, "Hashing to Elliptic Curves", 2022,
<https://datatracker.ietf.org/doc/draft-irtf-cfrg-hash-to-
curve/>.
Appendix A. Test vectors for ristretto255
This section contains test vectors for ristretto255. The octets are This section contains test vectors for ristretto255. The octets are
hex encoded, and whitespace is inserted for readability. hex encoded, and whitespace is inserted for readability.
A.1. Multiples of the generator A.1. Multiples of the Generator
The following are the encodings of the multiples 0 to 15 of the The following are the encodings of the multiples 0 to 15 of the
canonical generator, represented as an array of elements. That is, canonical generator, represented as an array of elements. That is,
the first entry is the encoding of the identity element, and each the first entry is the encoding of the identity element, and each
successive entry is obtained by adding the generator to the previous successive entry is obtained by adding the generator to the previous
entry. entry.
B[ 0]: 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 B[ 0]: 00000000 00000000 00000000 00000000 00000000 00000000 00000000
B[ 1]: e2f2ae0a 6abc4e71 a884a961 c500515f 58e30b6a a582dd8d b6a65945 e08d2d76 00000000
B[ 2]: 6a493210 f7499cd1 7fecb510 ae0cea23 a110e8d5 b901f8ac add3095c 73a3b919 B[ 1]: e2f2ae0a 6abc4e71 a884a961 c500515f 58e30b6a a582dd8d b6a65945
B[ 3]: 94741f5d 5d52755e ce4f23f0 44ee27d5 d1ea1e2b d196b462 166b1615 2a9d0259 e08d2d76
B[ 4]: da808627 73358b46 6ffadfe0 b3293ab3 d9fd53c5 ea6c9553 58f56832 2daf6a57 B[ 2]: 6a493210 f7499cd1 7fecb510 ae0cea23 a110e8d5 b901f8ac add3095c
B[ 5]: e882b131 016b52c1 d3337080 187cf768 423efccb b517bb49 5ab812c4 160ff44e 73a3b919
B[ 6]: f64746d3 c92b1305 0ed8d802 36a7f000 7c3b3f96 2f5ba793 d19a601e bb1df403 B[ 3]: 94741f5d 5d52755e ce4f23f0 44ee27d5 d1ea1e2b d196b462 166b1615
B[ 7]: 44f53520 926ec81f bd5a3878 45beb7df 85a96a24 ece18738 bdcfa6a7 822a176d 2a9d0259
B[ 8]: 903293d8 f2287ebe 10e2374d c1a53e0b c887e592 699f02d0 77d5263c dd55601c B[ 4]: da808627 73358b46 6ffadfe0 b3293ab3 d9fd53c5 ea6c9553 58f56832
B[ 9]: 02622ace 8f7303a3 1cafc63f 8fc48fdc 16e1c8c8 d234b2f0 d6685282 a9076031 2daf6a57
B[10]: 20706fd7 88b2720a 1ed2a5da d4952b01 f413bcf0 e7564de8 cdc81668 9e2db95f B[ 5]: e882b131 016b52c1 d3337080 187cf768 423efccb b517bb49 5ab812c4
B[11]: bce83f8b a5dd2fa5 72864c24 ba1810f9 522bc600 4afe9587 7ac73241 cafdab42 160ff44e
B[12]: e4549ee1 6b9aa030 99ca208c 67adafca fa4c3f3e 4e5303de 6026e3ca 8ff84460 B[ 6]: f64746d3 c92b1305 0ed8d802 36a7f000 7c3b3f96 2f5ba793 d19a601e
B[13]: aa52e000 df2e16f5 5fb1032f c33bc427 42dad6bd 5a8fc0be 0167436c 5948501f bb1df403
B[14]: 46376b80 f409b29d c2b5f6f0 c5259199 0896e571 6f41477c d30085ab 7f10301e B[ 7]: 44f53520 926ec81f bd5a3878 45beb7df 85a96a24 ece18738 bdcfa6a7
B[15]: e0c418f7 c8d9c4cd d7395b93 ea124f3a d99021bb 681dfc33 02a9d99a 2e53e64e 822a176d
B[ 8]: 903293d8 f2287ebe 10e2374d c1a53e0b c887e592 699f02d0 77d5263c
dd55601c
B[ 9]: 02622ace 8f7303a3 1cafc63f 8fc48fdc 16e1c8c8 d234b2f0 d6685282
a9076031
B[10]: 20706fd7 88b2720a 1ed2a5da d4952b01 f413bcf0 e7564de8 cdc81668
9e2db95f
B[11]: bce83f8b a5dd2fa5 72864c24 ba1810f9 522bc600 4afe9587 7ac73241
cafdab42
B[12]: e4549ee1 6b9aa030 99ca208c 67adafca fa4c3f3e 4e5303de 6026e3ca
8ff84460
B[13]: aa52e000 df2e16f5 5fb1032f c33bc427 42dad6bd 5a8fc0be 0167436c
5948501f
B[14]: 46376b80 f409b29d c2b5f6f0 c5259199 0896e571 6f41477c d30085ab
7f10301e
B[15]: e0c418f7 c8d9c4cd d7395b93 ea124f3a d99021bb 681dfc33 02a9d99a
2e53e64e
Note that because Note that because
B[i+1] = B[i] + B[1] B[i+1] = B[i] + B[1]
these test vectors allow testing the encoding function and the these test vectors allow testing of the encoding function and the
implementation of addition simultaneously. implementation of addition simultaneously.
A.2. Invalid encodings A.2. Invalid Encodings
These are examples of encodings that MUST be rejected according to These are examples of encodings that MUST be rejected according to
Section 4.3.1. Section 4.3.1.
# Non-canonical field encodings. # Non-canonical field encodings.
00ffffff ffffffff ffffffff ffffffff ffffffff ffffffff ffffffff ffffffff 00ffffff ffffffff ffffffff ffffffff ffffffff ffffffff ffffffff
ffffffff ffffffff ffffffff ffffffff ffffffff ffffffff ffffffff ffffff7f ffffffff
f3ffffff ffffffff ffffffff ffffffff ffffffff ffffffff ffffffff ffffff7f
edffffff ffffffff ffffffff ffffffff ffffffff ffffffff ffffffff ffffff7f
# Negative field elements. ffffffff ffffffff ffffffff ffffffff ffffffff ffffffff ffffffff
01000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 ffffff7f
01ffffff ffffffff ffffffff ffffffff ffffffff ffffffff ffffffff ffffff7f
ed57ffd8 c914fb20 1471d1c3 d245ce3c 746fcbe6 3a3679d5 1b6a516e bebe0e20
c34c4e18 26e5d403 b78e246e 88aa051c 36ccf0aa febffe13 7d148a2b f9104562
c940e5a4 404157cf b1628b10 8db051a8 d439e1a4 21394ec4 ebccb9ec 92a8ac78
47cfc549 7c53dc8e 61c91d17 fd626ffb 1c49e2bc a94eed05 2281b510 b1117a24
f1c6165d 33367351 b0da8f6e 4511010c 68174a03 b6581212 c71c0e1d 026c3c72
87260f7a 2f124951 18360f02 c26a470f 450dadf3 4a413d21 042b43b9 d93e1309
# Non-square x^2. f3ffffff ffffffff ffffffff ffffffff ffffffff ffffffff ffffffff
26948d35 ca62e643 e26a8317 7332e6b6 afeb9d08 e4268b65 0f1f5bbd 8d81d371 ffffff7f
4eac077a 713c57b4 f4397629 a4145982 c661f480 44dd3f96 427d40b1 47d9742f
de6a7b00 deadc788 eb6b6c8d 20c0ae96 c2f20190 78fa604f ee5b87d6 e989ad7b
bcab477b e20861e0 1e4a0e29 5284146a 510150d9 817763ca f1a6f4b4 22d67042
2a292df7 e32cabab bd9de088 d1d1abec 9fc0440f 637ed2fb a145094d c14bea08
f4a9e534 fc0d216c 44b218fa 0c42d996 35a0127e e2e53c71 2f706096 49fdff22
8268436f 8c412619 6cf64b3c 7ddbda90 746a3786 25f9813d d9b84570 77256731
2810e5cb c2cc4d4e ece54f61 c6f69758 e289aa7a b440b3cb eaa21995 c2f4232b
# Negative xy value. edffffff ffffffff ffffffff ffffffff ffffffff ffffffff ffffffff
3eb858e7 8f5a7254 d8c97311 74a94f76 755fd394 1c0ac937 35c07ba1 4579630e ffffff7f
a45fdc55 c76448c0 49a1ab33 f17023ed fb2be358 1e9c7aad e8a61252 15e04220
d483fe81 3c6ba647 ebbfd3ec 41adca1c 6130c2be eee9d9bf 065c8d15 1c5f396e
8a2e1d30 050198c6 5a544831 23960ccc 38aef684 8e1ec8f5 f780e852 3769ba32
32888462 f8b486c6 8ad7dd96 10be5192 bbeaf3b4 43951ac1 a8118419 d9fa097b
22714250 1b9d4355 ccba2904 04bde415 75b03769 3cef1f43 8c47f8fb f35d1165
5c37cc49 1da847cf eb9281d4 07efc41e 15144c87 6e0170b4 99a96a22 ed31e01e
44542511 7cb8c90e dcbc7c1c c0e74f74 7f2c1efa 5630a967 c64f2877 92a48a4b
# s = -1, which causes y = 0. # Negative field elements.
ecffffff ffffffff ffffffff ffffffff ffffffff ffffffff ffffffff ffffff7f 01000000 00000000 00000000 00000000 00000000 00000000 00000000
00000000
A.3. Group elements from byte strings 01ffffff ffffffff ffffffff ffffffff ffffffff ffffffff ffffffff
ffffff7f
ed57ffd8 c914fb20 1471d1c3 d245ce3c 746fcbe6 3a3679d5 1b6a516e
bebe0e20
c34c4e18 26e5d403 b78e246e 88aa051c 36ccf0aa febffe13 7d148a2b
f9104562
c940e5a4 404157cf b1628b10 8db051a8 d439e1a4 21394ec4 ebccb9ec
92a8ac78
47cfc549 7c53dc8e 61c91d17 fd626ffb 1c49e2bc a94eed05 2281b510
b1117a24
f1c6165d 33367351 b0da8f6e 4511010c 68174a03 b6581212 c71c0e1d
026c3c72
87260f7a 2f124951 18360f02 c26a470f 450dadf3 4a413d21 042b43b9
d93e1309
# Non-square x^2.
26948d35 ca62e643 e26a8317 7332e6b6 afeb9d08 e4268b65 0f1f5bbd
8d81d371
4eac077a 713c57b4 f4397629 a4145982 c661f480 44dd3f96 427d40b1
47d9742f
de6a7b00 deadc788 eb6b6c8d 20c0ae96 c2f20190 78fa604f ee5b87d6
e989ad7b
bcab477b e20861e0 1e4a0e29 5284146a 510150d9 817763ca f1a6f4b4
22d67042
2a292df7 e32cabab bd9de088 d1d1abec 9fc0440f 637ed2fb a145094d
c14bea08
f4a9e534 fc0d216c 44b218fa 0c42d996 35a0127e e2e53c71 2f706096
49fdff22
8268436f 8c412619 6cf64b3c 7ddbda90 746a3786 25f9813d d9b84570
77256731
2810e5cb c2cc4d4e ece54f61 c6f69758 e289aa7a b440b3cb eaa21995
c2f4232b
# Negative x * y value.
3eb858e7 8f5a7254 d8c97311 74a94f76 755fd394 1c0ac937 35c07ba1
4579630e
a45fdc55 c76448c0 49a1ab33 f17023ed fb2be358 1e9c7aad e8a61252
15e04220
d483fe81 3c6ba647 ebbfd3ec 41adca1c 6130c2be eee9d9bf 065c8d15
1c5f396e
8a2e1d30 050198c6 5a544831 23960ccc 38aef684 8e1ec8f5 f780e852
3769ba32
32888462 f8b486c6 8ad7dd96 10be5192 bbeaf3b4 43951ac1 a8118419
d9fa097b
22714250 1b9d4355 ccba2904 04bde415 75b03769 3cef1f43 8c47f8fb
f35d1165
5c37cc49 1da847cf eb9281d4 07efc41e 15144c87 6e0170b4 99a96a22
ed31e01e
44542511 7cb8c90e dcbc7c1c c0e74f74 7f2c1efa 5630a967 c64f2877
92a48a4b
# s = -1, which causes y = 0.
ecffffff ffffffff ffffffff ffffffff ffffffff ffffffff ffffffff
ffffff7f
A.3. Group Elements from Uniform Byte Strings
The following pairs are inputs to the element derivation function of The following pairs are inputs to the element derivation function of
Section 4.3.4, and their encoded outputs. Section 4.3.4 and their encoded outputs.
I: 5d1be09e3d0c82fc538112490e35701979d99e06ca3e2b5b54bffe8b4dc772c1 I: 5d1be09e3d0c82fc538112490e35701979d99e06ca3e2b5b54bffe8b4dc772c1
4d98b696a1bbfb5ca32c436cc61c16563790306c79eaca7705668b47dffe5bb6 4d98b696a1bbfb5ca32c436cc61c16563790306c79eaca7705668b47dffe5bb6
O: 3066f82a 1a747d45 120d1740 f1435853 1a8f04bb ffe6a819 f86dfe50 f44a0a46 O: 3066f82a 1a747d45 120d1740 f1435853 1a8f04bb ffe6a819 f86dfe50
f44a0a46
I: f116b34b8f17ceb56e8732a60d913dd10cce47a6d53bee9204be8b44f6678b27 I: f116b34b8f17ceb56e8732a60d913dd10cce47a6d53bee9204be8b44f6678b27
0102a56902e2488c46120e9276cfe54638286b9e4b3cdb470b542d46c2068d38 0102a56902e2488c46120e9276cfe54638286b9e4b3cdb470b542d46c2068d38
O: f26e5b6f 7d362d2d 2a94c5d0 e7602cb4 773c95a2 e5c31a64 f133189f a76ed61b O: f26e5b6f 7d362d2d 2a94c5d0 e7602cb4 773c95a2 e5c31a64 f133189f
a76ed61b
I: 8422e1bbdaab52938b81fd602effb6f89110e1e57208ad12d9ad767e2e25510c I: 8422e1bbdaab52938b81fd602effb6f89110e1e57208ad12d9ad767e2e25510c
27140775f9337088b982d83d7fcf0b2fa1edffe51952cbe7365e95c86eaf325c 27140775f9337088b982d83d7fcf0b2fa1edffe51952cbe7365e95c86eaf325c
O: 006ccd2a 9e6867e6 a2c5cea8 3d3302cc 9de128dd 2a9a57dd 8ee7b9d7 ffe02826 O: 006ccd2a 9e6867e6 a2c5cea8 3d3302cc 9de128dd 2a9a57dd 8ee7b9d7
ffe02826
I: ac22415129b61427bf464e17baee8db65940c233b98afce8d17c57beeb7876c2 I: ac22415129b61427bf464e17baee8db65940c233b98afce8d17c57beeb7876c2
150d15af1cb1fb824bbd14955f2b57d08d388aab431a391cfc33d5bafb5dbbaf 150d15af1cb1fb824bbd14955f2b57d08d388aab431a391cfc33d5bafb5dbbaf
O: f8f0c87c f237953c 5890aec3 99816900 5dae3eca 1fbb0454 8c635953 c817f92a O: f8f0c87c f237953c 5890aec3 99816900 5dae3eca 1fbb0454 8c635953
c817f92a
I: 165d697a1ef3d5cf3c38565beefcf88c0f282b8e7dbd28544c483432f1cec767 I: 165d697a1ef3d5cf3c38565beefcf88c0f282b8e7dbd28544c483432f1cec767
5debea8ebb4e5fe7d6f6e5db15f15587ac4d4d4a1de7191e0c1ca6664abcc413 5debea8ebb4e5fe7d6f6e5db15f15587ac4d4d4a1de7191e0c1ca6664abcc413
O: ae81e7de df20a497 e10c304a 765c1767 a42d6e06 029758d2 d7e8ef7c c4c41179 O: ae81e7de df20a497 e10c304a 765c1767 a42d6e06 029758d2 d7e8ef7c
c4c41179
I: a836e6c9a9ca9f1e8d486273ad56a78c70cf18f0ce10abb1c7172ddd605d7fd2 I: a836e6c9a9ca9f1e8d486273ad56a78c70cf18f0ce10abb1c7172ddd605d7fd2
979854f47ae1ccf204a33102095b4200e5befc0465accc263175485f0e17ea5c 979854f47ae1ccf204a33102095b4200e5befc0465accc263175485f0e17ea5c
O: e2705652 ff9f5e44 d3e841bf 1c251cf7 dddb77d1 40870d1a b2ed64f1 a9ce8628 O: e2705652 ff9f5e44 d3e841bf 1c251cf7 dddb77d1 40870d1a b2ed64f1
a9ce8628
I: 2cdc11eaeb95daf01189417cdddbf95952993aa9cb9c640eb5058d09702c7462 I: 2cdc11eaeb95daf01189417cdddbf95952993aa9cb9c640eb5058d09702c7462
2c9965a697a3b345ec24ee56335b556e677b30e6f90ac77d781064f866a3c982 2c9965a697a3b345ec24ee56335b556e677b30e6f90ac77d781064f866a3c982
O: 80bd0726 2511cdde 4863f8a7 434cef69 6750681c b9510eea 557088f7 6d9e5065 O: 80bd0726 2511cdde 4863f8a7 434cef69 6750681c b9510eea 557088f7
6d9e5065
The following element derivation function inputs all produce the same The following element derivation function inputs all produce the same
encoded output. encoded output.
I: edffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff I: edffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff
1200000000000000000000000000000000000000000000000000000000000000 1200000000000000000000000000000000000000000000000000000000000000
I: edffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff7f I: edffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff7f
ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff
I: 0000000000000000000000000000000000000000000000000000000000000080 I: 0000000000000000000000000000000000000000000000000000000000000080
ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff7f ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff7f
I: 0000000000000000000000000000000000000000000000000000000000000000 I: 0000000000000000000000000000000000000000000000000000000000000000
1200000000000000000000000000000000000000000000000000000000000080 1200000000000000000000000000000000000000000000000000000000000080
O: 30428279 1023b731 28d277bd cb5c7746 ef2eac08 dde9f298 3379cb8e 5ef0517f O: 30428279 1023b731 28d277bd cb5c7746 ef2eac08 dde9f298 3379cb8e
5ef0517f
A.4. Square root of a ratio of field elements A.4. Square Root of a Ratio of Field Elements
The following are inputs and outputs of SQRT_RATIO_M1(u, v) defined The following are inputs and outputs of SQRT_RATIO_M1(u, v) defined
in Section 4.2. The values are little-endian encodings of field in Section 4.2. The values are little-endian encodings of field
elements. elements.
u: 0000000000000000000000000000000000000000000000000000000000000000 u: 0000000000000000000000000000000000000000000000000000000000000000
v: 0000000000000000000000000000000000000000000000000000000000000000 v: 0000000000000000000000000000000000000000000000000000000000000000
was_square: TRUE was_square: TRUE
r: 0000000000000000000000000000000000000000000000000000000000000000 r: 0000000000000000000000000000000000000000000000000000000000000000
skipping to change at page 23, line 35 skipping to change at line 1150
u: 0400000000000000000000000000000000000000000000000000000000000000 u: 0400000000000000000000000000000000000000000000000000000000000000
v: 0100000000000000000000000000000000000000000000000000000000000000 v: 0100000000000000000000000000000000000000000000000000000000000000
was_square: TRUE was_square: TRUE
r: 0200000000000000000000000000000000000000000000000000000000000000 r: 0200000000000000000000000000000000000000000000000000000000000000
u: 0100000000000000000000000000000000000000000000000000000000000000 u: 0100000000000000000000000000000000000000000000000000000000000000
v: 0400000000000000000000000000000000000000000000000000000000000000 v: 0400000000000000000000000000000000000000000000000000000000000000
was_square: TRUE was_square: TRUE
r: f6ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff3f r: f6ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff3f
Appendix B. Test vectors for decaf448 Appendix B. Test Vectors for decaf448
This section contains test vectors for decaf448. The octets are hex This section contains test vectors for decaf448. The octets are hex
encoded, and whitespace is inserted for readability. encoded, and whitespace is inserted for readability.
B.1. Multiples of the generator B.1. Multiples of the Generator
The following are the encodings of the multiples 0 to 15 of the The following are the encodings of the multiples 0 to 15 of the
canonical generator, represented as an array of elements. That is, canonical generator, represented as an array of elements. That is,
the first entry is the encoding of the identity element, and each the first entry is the encoding of the identity element, and each
successive entry is obtained by adding the generator to the previous successive entry is obtained by adding the generator to the previous
entry. entry.
B[ 0]: 00000000 00000000 00000000 00000000 00000000 00000000 00000000 B[ 0]: 00000000 00000000 00000000 00000000 00000000 00000000 00000000
00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000
B[ 1]: 66666666 66666666 66666666 66666666 66666666 66666666 66666666 B[ 1]: 66666666 66666666 66666666 66666666 66666666 66666666 66666666
skipping to change at page 24, line 38 skipping to change at line 1196
3159db64 c0e139d1 80f3c89b 8296d0ae 324419c0 6fa87fc7 daaf34c1 3159db64 c0e139d1 80f3c89b 8296d0ae 324419c0 6fa87fc7 daaf34c1
B[12]: a456f936 9769e8f0 8902124a 0314c7a0 6537a06e 32411f4f 93415950 B[12]: a456f936 9769e8f0 8902124a 0314c7a0 6537a06e 32411f4f 93415950
a17badfa 7442b621 7434a3a0 5ef45be5 f10bd7b2 ef8ea00c 431edec5 a17badfa 7442b621 7434a3a0 5ef45be5 f10bd7b2 ef8ea00c 431edec5
B[13]: 186e452c 4466aa43 83b4c002 10d52e79 22dbf977 1e8b47e2 29a9b7b7 B[13]: 186e452c 4466aa43 83b4c002 10d52e79 22dbf977 1e8b47e2 29a9b7b7
3c8d10fd 7ef0b6e4 1530f91f 24a3ed9a b71fa38b 98b2fe47 46d51d68 3c8d10fd 7ef0b6e4 1530f91f 24a3ed9a b71fa38b 98b2fe47 46d51d68
B[14]: 4ae7fdca e9453f19 5a8ead5c be1a7b96 99673b52 c40ab279 27464887 B[14]: 4ae7fdca e9453f19 5a8ead5c be1a7b96 99673b52 c40ab279 27464887
be53237f 7f3a21b9 38d40d0e c9e15b1d 5130b13f fed81373 a53e2b43 be53237f 7f3a21b9 38d40d0e c9e15b1d 5130b13f fed81373 a53e2b43
B[15]: 841981c3 bfeec3f6 0cfeca75 d9d8dc17 f46cf010 6f2422b5 9aec580a B[15]: 841981c3 bfeec3f6 0cfeca75 d9d8dc17 f46cf010 6f2422b5 9aec580a
58f34227 2e3a5e57 5a055ddb 051390c5 4c24c6ec b1e0aceb 075f6056 58f34227 2e3a5e57 5a055ddb 051390c5 4c24c6ec b1e0aceb 075f6056
B.2. Invalid encodings B.2. Invalid Encodings
These are examples of encodings that MUST be rejected according to These are examples of encodings that MUST be rejected according to
Section 5.3.1. Section 5.3.1.
# Non-canonical field encodings. # Non-canonical field encodings.
8e24f838 059ee9fe f1e20912 6defe53d cd74ef9b 6304601c 6966099e 8e24f838 059ee9fe f1e20912 6defe53d cd74ef9b 6304601c 6966099e
ffffffff ffffffff ffffffff ffffffff ffffffff ffffffff ffffffff ffffffff ffffffff ffffffff ffffffff ffffffff ffffffff ffffffff
86fcc721 2bd4a0b9 80928666 dc28c444 a605ef38 e09fb569 e28d4443 86fcc721 2bd4a0b9 80928666 dc28c444 a605ef38 e09fb569 e28d4443
ffffffff ffffffff ffffffff ffffffff ffffffff ffffffff ffffffff ffffffff ffffffff ffffffff ffffffff ffffffff ffffffff ffffffff
skipping to change at page 26, line 12 skipping to change at line 1267
2ed9ffe2 ded67a37 2b181ac5 24996402 c4297062 9db03f5e 8636cbaf 2ed9ffe2 ded67a37 2b181ac5 24996402 c4297062 9db03f5e 8636cbaf
6074b523 d154a7a8 c4472c4c 353ab88c d6fec7da 7780834c c5bd5242 6074b523 d154a7a8 c4472c4c 353ab88c d6fec7da 7780834c c5bd5242
f063769e 4241e76d 815800e4 933a3a14 4327a30e c40758ad 3723a788 f063769e 4241e76d 815800e4 933a3a14 4327a30e c40758ad 3723a788
388399f7 b3f5d45b 6351eb8e ddefda7d 5bff4ee9 20d338a8 b89d8b63 388399f7 b3f5d45b 6351eb8e ddefda7d 5bff4ee9 20d338a8 b89d8b63
5a0104f1 f55d152c eb68bc13 81824998 91d90ee8 f09b4003 8ccc1e07 5a0104f1 f55d152c eb68bc13 81824998 91d90ee8 f09b4003 8ccc1e07
cb621fd4 62f781d0 45732a4f 0bda73f0 b2acf943 55424ff0 388d4b9c cb621fd4 62f781d0 45732a4f 0bda73f0 b2acf943 55424ff0 388d4b9c
B.3. Group elements from uniform byte strings B.3. Group Elements from Uniform Byte Strings
The following pairs are inputs to the element derivation function of The following pairs are inputs to the element derivation function of
Section 5.3.4, and their encoded outputs. Section 5.3.4 and their encoded outputs.
I: cbb8c991fd2f0b7e1913462d6463e4fd2ce4ccdd28274dc2ca1f4165 I: cbb8c991fd2f0b7e1913462d6463e4fd2ce4ccdd28274dc2ca1f4165
d5ee6cdccea57be3416e166fd06718a31af45a2f8e987e301be59ae6 d5ee6cdccea57be3416e166fd06718a31af45a2f8e987e301be59ae6
673e963001dbbda80df47014a21a26d6c7eb4ebe0312aa6fffb8d1b2 673e963001dbbda80df47014a21a26d6c7eb4ebe0312aa6fffb8d1b2
6bc62ca40ed51f8057a635a02c2b8c83f48fa6a2d70f58a1185902c0 6bc62ca40ed51f8057a635a02c2b8c83f48fa6a2d70f58a1185902c0
O: 0c709c96 07dbb01c 94513358 745b7c23 953d03b3 3e39c723 4e268d1d O: 0c709c96 07dbb01c 94513358 745b7c23 953d03b3 3e39c723 4e268d1d
6e24f340 14ccbc22 16b965dd 231d5327 e591dc3c 0e8844cc fd568848 6e24f340 14ccbc22 16b965dd 231d5327 e591dc3c 0e8844cc fd568848
I: b6d8da654b13c3101d6634a231569e6b85961c3f4b460a08ac4a5857 I: b6d8da654b13c3101d6634a231569e6b85961c3f4b460a08ac4a5857
069576b64428676584baa45b97701be6d0b0ba18ac28d443403b4569 069576b64428676584baa45b97701be6d0b0ba18ac28d443403b4569
skipping to change at page 27, line 19 skipping to change at line 1321
O: 7e79b00e 8e0a76a6 7c0040f6 2713b8b8 c6d6f05e 9c6d0259 2e8a22ea O: 7e79b00e 8e0a76a6 7c0040f6 2713b8b8 c6d6f05e 9c6d0259 2e8a22ea
896f5dea cc7c7df5 ed42beae 6fedb900 0285b482 aa504e27 9fd49c32 896f5dea cc7c7df5 ed42beae 6fedb900 0285b482 aa504e27 9fd49c32
I: e9fb440282e07145f1f7f5ecf3c273212cd3d26b836b41b02f108431 I: e9fb440282e07145f1f7f5ecf3c273212cd3d26b836b41b02f108431
488e5e84bd15f2418b3d92a3380dd66a374645c2a995976a015632d3 488e5e84bd15f2418b3d92a3380dd66a374645c2a995976a015632d3
6a6c2189f202fc766e1c82f50ad9189be190a1f0e8f9b9e69c9c18cc 6a6c2189f202fc766e1c82f50ad9189be190a1f0e8f9b9e69c9c18cc
98fdd885608f68bf0fdedd7b894081a63f70016a8abf04953affbefa 98fdd885608f68bf0fdedd7b894081a63f70016a8abf04953affbefa
O: 20b171cb 16be977f 15e013b9 752cf86c 54c631c4 fc8cbf7c 03c4d3ac O: 20b171cb 16be977f 15e013b9 752cf86c 54c631c4 fc8cbf7c 03c4d3ac
9b8e8640 e7b0e930 0b987fe0 ab504466 9314f6ed 1650ae03 7db853f1 9b8e8640 e7b0e930 0b987fe0 ab504466 9314f6ed 1650ae03 7db853f1
Acknowledgements
The authors would like to thank Daira Emma Hopwood, Riad S. Wahby,
Christopher Wood, and Thomas Pornin for their comments on the
document.
Authors' Addresses Authors' Addresses
Henry de Valence Henry de Valence
Email: ietf@hdevalence.ca Email: ietf@hdevalence.ca
Jack Grigg Jack Grigg
Email: ietf@jackgrigg.com Email: ietf@jackgrigg.com
Mike Hamburg Mike Hamburg
Email: ietf@shiftleft.org Email: ietf@shiftleft.org
 End of changes. 122 change blocks. 
318 lines changed or deleted 414 lines changed or added

This html diff was produced by rfcdiff 1.48.