curve25519_dalek/
constants.rs

1// -*- mode: rust; -*-
2//
3// This file is part of curve25519-dalek.
4// Copyright (c) 2016-2021 isis lovecruft
5// Copyright (c) 2016-2019 Henry de Valence
6// See LICENSE for licensing information.
7//
8// Authors:
9// - isis agora lovecruft <[email protected]>
10// - Henry de Valence <[email protected]>
11//! Various constants, such as the Ristretto and Ed25519 basepoints.
12
13#![allow(non_snake_case)]
14
15use cfg_if::cfg_if;
16
17use crate::edwards::CompressedEdwardsY;
18use crate::montgomery::MontgomeryPoint;
19use crate::ristretto::{CompressedRistretto, RistrettoPoint};
20use crate::scalar::Scalar;
21
22#[cfg(feature = "precomputed-tables")]
23use crate::edwards::EdwardsBasepointTable;
24
25cfg_if! {
26    if #[cfg(curve25519_dalek_backend = "fiat")] {
27        #[cfg(curve25519_dalek_bits = "32")]
28        pub use crate::backend::serial::fiat_u32::constants::*;
29        #[cfg(curve25519_dalek_bits = "64")]
30        pub use crate::backend::serial::fiat_u64::constants::*;
31    } else {
32        #[cfg(curve25519_dalek_bits = "32")]
33        pub use crate::backend::serial::u32::constants::*;
34        #[cfg(curve25519_dalek_bits = "64")]
35        pub use crate::backend::serial::u64::constants::*;
36    }
37}
38
39/// The Ed25519 basepoint, in `CompressedEdwardsY` format.
40///
41/// This is the little-endian byte encoding of \\( 4/5 \pmod p \\),
42/// which is the \\(y\\)-coordinate of the Ed25519 basepoint.
43///
44/// The sign bit is 0 since the basepoint has \\(x\\) chosen to be positive.
45pub const ED25519_BASEPOINT_COMPRESSED: CompressedEdwardsY = CompressedEdwardsY([
46    0x58, 0x66, 0x66, 0x66, 0x66, 0x66, 0x66, 0x66, 0x66, 0x66, 0x66, 0x66, 0x66, 0x66, 0x66, 0x66,
47    0x66, 0x66, 0x66, 0x66, 0x66, 0x66, 0x66, 0x66, 0x66, 0x66, 0x66, 0x66, 0x66, 0x66, 0x66, 0x66,
48]);
49
50/// The X25519 basepoint, in `MontgomeryPoint` format.
51pub const X25519_BASEPOINT: MontgomeryPoint = MontgomeryPoint([
52    0x09, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
53    0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
54]);
55
56/// The Ristretto basepoint, in `CompressedRistretto` format.
57pub const RISTRETTO_BASEPOINT_COMPRESSED: CompressedRistretto = CompressedRistretto([
58    0xe2, 0xf2, 0xae, 0x0a, 0x6a, 0xbc, 0x4e, 0x71, 0xa8, 0x84, 0xa9, 0x61, 0xc5, 0x00, 0x51, 0x5f,
59    0x58, 0xe3, 0x0b, 0x6a, 0xa5, 0x82, 0xdd, 0x8d, 0xb6, 0xa6, 0x59, 0x45, 0xe0, 0x8d, 0x2d, 0x76,
60]);
61
62/// The Ristretto basepoint, as a `RistrettoPoint`.
63///
64/// This is called `_POINT` to distinguish it from `_TABLE`, which
65/// provides fast scalar multiplication.
66pub const RISTRETTO_BASEPOINT_POINT: RistrettoPoint = RistrettoPoint(ED25519_BASEPOINT_POINT);
67
68/// `BASEPOINT_ORDER` is the order of the Ristretto group and of the Ed25519 basepoint, i.e.,
69/// $$
70/// \ell = 2^\{252\} + 27742317777372353535851937790883648493.
71/// $$
72pub(crate) const BASEPOINT_ORDER: Scalar = Scalar {
73    bytes: [
74        0xed, 0xd3, 0xf5, 0x5c, 0x1a, 0x63, 0x12, 0x58, 0xd6, 0x9c, 0xf7, 0xa2, 0xde, 0xf9, 0xde,
75        0x14, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
76        0x00, 0x10,
77    ],
78};
79
80#[cfg(feature = "precomputed-tables")]
81use crate::ristretto::RistrettoBasepointTable;
82
83/// The Ristretto basepoint, as a `RistrettoBasepointTable` for scalar multiplication.
84#[cfg(feature = "precomputed-tables")]
85pub static RISTRETTO_BASEPOINT_TABLE: &RistrettoBasepointTable = unsafe {
86    // SAFETY: `RistrettoBasepointTable` is a `#[repr(transparent)]` newtype of
87    // `EdwardsBasepointTable`
88    &*(ED25519_BASEPOINT_TABLE as *const EdwardsBasepointTable as *const RistrettoBasepointTable)
89};
90
91/// X25519 low order points.
92///
93/// The output of any scalar multiplied by these points is zero. Protocols which need to ensure
94/// "contributory" behavior should reject these points.
95///
96/// Table adapted from <https://cr.yp.to/ecdh.html>.
97#[rustfmt::skip]
98pub static X25519_LOW_ORDER_POINTS: [MontgomeryPoint; 7] = [
99    // 0 (order 4)
100    MontgomeryPoint([0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00]),
101
102    // 1 (order 1)
103    MontgomeryPoint([0x01, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00]),
104
105    // 325606250916557431795983626356110631294008115727848805560023387167927233504 (order 8)
106    MontgomeryPoint([0xe0, 0xeb, 0x7a, 0x7c, 0x3b, 0x41, 0xb8, 0xae, 0x16, 0x56, 0xe3, 0xfa, 0xf1, 0x9f, 0xc4, 0x6a, 0xda, 0x09, 0x8d, 0xeb, 0x9c, 0x32, 0xb1, 0xfd, 0x86, 0x62, 0x05, 0x16, 0x5f, 0x49, 0xb8, 0x00]),
107
108    // 39382357235489614581723060781553021112529911719440698176882885853963445705823 (order 8)
109    MontgomeryPoint([0x5f, 0x9c, 0x95, 0xbc, 0xa3, 0x50, 0x8c, 0x24, 0xb1, 0xd0, 0xb1, 0x55, 0x9c, 0x83, 0xef, 0x5b, 0x04, 0x44, 0x5c, 0xc4, 0x58, 0x1c, 0x8e, 0x86, 0xd8, 0x22, 0x4e, 0xdd, 0xd0, 0x9f, 0x11, 0x57]),
110
111    // p - 1 (order 2)
112    MontgomeryPoint([0xec, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0x7f]),
113
114    // p (order 4)
115    MontgomeryPoint([0xed, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0x7f]),
116
117    // p + 1 (order 1)
118    MontgomeryPoint([0xee, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0x7f])
119];
120
121#[cfg(test)]
122mod test {
123    use crate::constants;
124    use crate::field::FieldElement;
125    use crate::montgomery::MontgomeryPoint;
126    use crate::traits::{IsIdentity, ValidityCheck};
127
128    #[test]
129    fn test_eight_torsion() {
130        for i in 0..8 {
131            let Q = constants::EIGHT_TORSION[i].mul_by_pow_2(3);
132            assert!(Q.is_valid());
133            assert!(Q.is_identity());
134        }
135    }
136
137    #[test]
138    fn test_four_torsion() {
139        for i in (0..8).filter(|i| i % 2 == 0) {
140            let Q = constants::EIGHT_TORSION[i].mul_by_pow_2(2);
141            assert!(Q.is_valid());
142            assert!(Q.is_identity());
143        }
144    }
145
146    #[test]
147    fn test_two_torsion() {
148        for i in (0..8).filter(|i| i % 4 == 0) {
149            let Q = constants::EIGHT_TORSION[i].mul_by_pow_2(1);
150            assert!(Q.is_valid());
151            assert!(Q.is_identity());
152        }
153    }
154
155    /// Test that SQRT_M1 is the positive square root of -1
156    #[test]
157    fn test_sqrt_minus_one() {
158        let minus_one = FieldElement::MINUS_ONE;
159        let sqrt_m1_sq = &constants::SQRT_M1 * &constants::SQRT_M1;
160        assert_eq!(minus_one, sqrt_m1_sq);
161        assert!(bool::from(!constants::SQRT_M1.is_negative()));
162    }
163
164    #[test]
165    fn test_sqrt_constants_sign() {
166        let minus_one = FieldElement::MINUS_ONE;
167        let (was_nonzero_square, invsqrt_m1) = minus_one.invsqrt();
168        assert!(bool::from(was_nonzero_square));
169        let sign_test_sqrt = &invsqrt_m1 * &constants::SQRT_M1;
170        assert_eq!(sign_test_sqrt, minus_one);
171    }
172
173    /// Test that d = -121665/121666
174    #[test]
175    #[cfg(all(curve25519_dalek_bits = "32", not(curve25519_dalek_backend = "fiat")))]
176    fn test_d_vs_ratio() {
177        use crate::backend::serial::u32::field::FieldElement2625;
178        let a = -&FieldElement2625([121665, 0, 0, 0, 0, 0, 0, 0, 0, 0]);
179        let b = FieldElement2625([121666, 0, 0, 0, 0, 0, 0, 0, 0, 0]);
180        let d = &a * &b.invert();
181        let d2 = &d + &d;
182        assert_eq!(d, constants::EDWARDS_D);
183        assert_eq!(d2, constants::EDWARDS_D2);
184    }
185
186    /// Test that d = -121665/121666
187    #[test]
188    #[cfg(all(curve25519_dalek_bits = "64", not(curve25519_dalek_backend = "fiat")))]
189    fn test_d_vs_ratio() {
190        use crate::backend::serial::u64::field::FieldElement51;
191        let a = -&FieldElement51([121665, 0, 0, 0, 0]);
192        let b = FieldElement51([121666, 0, 0, 0, 0]);
193        let d = &a * &b.invert();
194        let d2 = &d + &d;
195        assert_eq!(d, constants::EDWARDS_D);
196        assert_eq!(d2, constants::EDWARDS_D2);
197    }
198
199    #[test]
200    fn test_sqrt_ad_minus_one() {
201        let a = FieldElement::MINUS_ONE;
202        let ad_minus_one = &(&a * &constants::EDWARDS_D) + &a;
203        let should_be_ad_minus_one = constants::SQRT_AD_MINUS_ONE.square();
204        assert_eq!(should_be_ad_minus_one, ad_minus_one);
205    }
206
207    #[test]
208    fn low_order_point_scalar_mul() {
209        // Example scalar from RFC7748 § 5.2
210        let scalar = [
211            0xa5, 0x46, 0xe3, 0x6b, 0xf0, 0x52, 0x7c, 0x9d, 0x3b, 0x16, 0x15, 0x4b, 0x82, 0x46,
212            0x5e, 0xdd, 0x62, 0x14, 0x4c, 0x0a, 0xc1, 0xfc, 0x5a, 0x18, 0x50, 0x6a, 0x22, 0x44,
213            0xba, 0x44, 0x9a, 0xc4,
214        ];
215
216        for low_order_point in constants::X25519_LOW_ORDER_POINTS {
217            let output = low_order_point.mul_clamped(scalar);
218            assert_eq!(output, MontgomeryPoint([0; 32]));
219        }
220    }
221
222    /// Test that ED25519_SQRTAM2 squared is MONTGOMERY_A_NEG - 2
223    #[test]
224    #[cfg(feature = "digest")]
225    fn test_sqrt_a_minus_2() {
226        let one = FieldElement::ONE;
227        let a_minus_two = &(&constants::MONTGOMERY_A_NEG - &one) - &one;
228
229        assert_eq!(constants::ED25519_SQRTAM2.square(), a_minus_two)
230    }
231}
curve25519_dalek/constants.rs

curve25519_dalek/
constants.rs
