ed448_goldilocks/edwards/
scalar.rs

1use crate::Ed448;
2use crate::field::{CurveWithScalar, ORDER, Scalar, ScalarBytes, WideScalarBytes};
3
4use elliptic_curve::{
5    array::Array,
6    bigint::{Limb, NonZero, U448, U704},
7    consts::{U57, U84, U88},
8    ops::Reduce,
9    scalar::FromUintUnchecked,
10};
11use subtle::{Choice, ConstantTimeEq, CtOption};
12
13impl CurveWithScalar for Ed448 {
14    type ReprSize = U57;
15
16    fn from_bytes_mod_order_wide(input: &WideScalarBytes<Self>) -> Scalar<Self> {
17        // top multiplier = 2^896 mod ℓ
18        const TOP_MULTIPLIER: U448 = U448::from_be_hex(
19            "3402a939f823b7292052bcb7e4d070af1a9cc14ba3c47c44ae17cf725ee4d8380d66de2388ea18597af32c4bc1b195d9e3539257049b9b60",
20        );
21        let value = (
22            U448::from_le_slice(&input[..56]),
23            U448::from_le_slice(&input[56..112]),
24        );
25        let mut top = [0u8; 56];
26        top[..2].copy_from_slice(&input[112..]);
27        let top = U448::from_le_slice(&top).mul_mod(&TOP_MULTIPLIER, ORDER.as_nz_ref());
28        let bottom = U448::rem_wide_vartime(value, ORDER.as_nz_ref());
29        Scalar::new(bottom.add_mod(&top, ORDER.as_nz_ref()))
30    }
31
32    fn from_canonical_bytes(bytes: &ScalarBytes<Self>) -> subtle::CtOption<Scalar<Self>> {
33        // Check that the 10 high bits are not set
34        let is_valid = bytes[56].ct_eq(&0) | (bytes[55] >> 6).ct_eq(&0);
35        let bytes: [u8; 56] = core::array::from_fn(|i| bytes[i]);
36        let candidate = Scalar::new(U448::from_le_slice(&bytes));
37
38        // underflow means candidate < ORDER, thus canonical
39        let (_, underflow) = candidate.scalar.borrowing_sub(&ORDER, Limb::ZERO);
40        let underflow = Choice::from((underflow.0 >> (Limb::BITS - 1)) as u8);
41        CtOption::new(candidate, underflow & is_valid)
42    }
43
44    fn to_repr(scalar: &Scalar<Self>) -> ScalarBytes<Self> {
45        scalar.to_bytes_rfc_8032()
46    }
47}
48
49/// [`Ed448`] scalar field.
50pub type EdwardsScalar = Scalar<Ed448>;
51
52impl EdwardsScalar {
53    /// Serialize the scalar into 57 bytes, per RFC 8032.
54    /// Byte 56 will always be zero.
55    pub fn to_bytes_rfc_8032(&self) -> EdwardsScalarBytes {
56        let mut bytes = EdwardsScalarBytes::default();
57        bytes[..56].copy_from_slice(&self.to_bytes());
58        bytes
59    }
60
61    /// Construct a `Scalar` by reducing a 912-bit little-endian integer
62    /// modulo the group order ℓ.
63    pub fn from_bytes_mod_order_wide(input: &WideEdwardsScalarBytes) -> EdwardsScalar {
64        Ed448::from_bytes_mod_order_wide(input)
65    }
66}
67
68elliptic_curve::scalar_impls!(Ed448, EdwardsScalar);
69
70/// The number of bytes needed to represent the scalar field
71pub type EdwardsScalarBytes = ScalarBytes<Ed448>;
72/// The number of bytes needed to represent the safely create a scalar from a random bytes
73pub type WideEdwardsScalarBytes = WideScalarBytes<Ed448>;
74
75impl Reduce<Array<u8, U84>> for EdwardsScalar {
76    fn reduce(value: &Array<u8, U84>) -> Self {
77        const SEMI_WIDE_MODULUS: NonZero<U704> = NonZero::<U704>::new_unwrap(U704::from_be_hex(
78            "00000000000000000000000000000000000000000000000000000000000000003fffffffffffffffffffffffffffffffffffffffffffffffffffffff7cca23e9c44edb49aed63690216cc2728dc58f552378c292ab5844f3",
79        ));
80        let mut tmp = Array::<u8, U88>::default();
81        tmp[4..].copy_from_slice(&value[..]);
82
83        let mut num = U704::from_be_slice(&tmp[..]);
84        num %= SEMI_WIDE_MODULUS;
85        let mut words = [0; U448::LIMBS];
86        words.copy_from_slice(&num.to_words()[..U448::LIMBS]);
87        Scalar::new(U448::from_words(words))
88    }
89}
90
91#[cfg(test)]
92mod test {
93    use super::*;
94    use elliptic_curve::array::Array;
95    use hash2curve::ExpandMsgXof;
96    use hex_literal::hex;
97    use proptest::property_test;
98    use shake::Shake256;
99
100    #[test]
101    fn test_basic_add() {
102        let five = EdwardsScalar::from(5u8);
103        let six = EdwardsScalar::from(6u8);
104
105        assert_eq!(five + six, EdwardsScalar::from(11u8))
106    }
107
108    #[test]
109    fn test_basic_sub() {
110        let ten = EdwardsScalar::from(10u8);
111        let five = EdwardsScalar::from(5u8);
112        assert_eq!(ten - five, EdwardsScalar::from(5u8))
113    }
114
115    #[test]
116    fn test_basic_mul() {
117        let ten = EdwardsScalar::from(10u8);
118        let five = EdwardsScalar::from(5u8);
119
120        assert_eq!(ten * five, EdwardsScalar::from(50u8))
121    }
122
123    #[test]
124    fn test_mul() {
125        let a = EdwardsScalar::new(U448::from_be_hex(
126            "1e63e8073b089f0747cf8cac2c3dc2732aae8688a8fa552ba8cb0ae8c0be082e74d657641d9ac30a087b8fb97f8ed27dc96a3c35ffb823a3",
127        ));
128
129        let b = EdwardsScalar::new(U448::from_be_hex(
130            "16c5450acae1cb680a92de2d8e59b30824e8d4991adaa0e7bc343bcbd099595b188c6b1a1e30b38b17aa6d9be416b899686eb329d8bedc42",
131        ));
132
133        let exp = EdwardsScalar::new(U448::from_be_hex(
134            "31e055c14ca389edfccd61b3203d424bb9036ff6f2d89c1e07bcd93174e9335f36a1492008a3a0e46abd26f5994c9c2b1f5b3197a18d010a",
135        ));
136
137        assert_eq!(a * b, exp)
138    }
139    #[test]
140    fn test_basic_square() {
141        let a = EdwardsScalar::new(U448::from_be_hex(
142            "3162081604b3273b930392e5d2391f9d21cc3078f22c69514bb395e08dccc4866f08f3311370f8b83fa50692f640922b7e56a34bcf5fac3d",
143        ));
144        let expected_a_squared = EdwardsScalar::new(U448::from_be_hex(
145            "1c1e32fc66b21c9c42d6e8e20487193cf6d49916421b290098f30de3713006cfe8ee9d21eeef7427f82a1fe036630c74b9acc2c2ede40f04",
146        ));
147
148        assert_eq!(a.square(), expected_a_squared)
149    }
150
151    #[test]
152    fn test_sanity_check_index_mut() {
153        let mut x = EdwardsScalar::ONE;
154        x[0] = 2;
155        assert_eq!(x, EdwardsScalar::from(2u8))
156    }
157    #[test]
158    fn test_basic_halving() {
159        let eight = EdwardsScalar::from(8u8);
160        let four = EdwardsScalar::from(4u8);
161        let two = EdwardsScalar::from(2u8);
162        assert_eq!(eight.div_by_2(), four);
163        assert_eq!(four.div_by_2(), two);
164        assert_eq!(two.div_by_2(), EdwardsScalar::ONE);
165    }
166
167    #[test]
168    fn test_equals() {
169        let a = EdwardsScalar::from(5u8);
170        let b = EdwardsScalar::from(5u8);
171        let c = EdwardsScalar::from(10u8);
172        assert_eq!(a, b);
173        assert_ne!(a, c);
174    }
175
176    #[test]
177    fn test_basic_inversion() {
178        // Test inversion from 2 to 100
179        for i in 1..=100u8 {
180            let x = EdwardsScalar::from(i);
181            let x_inv = x.invert();
182            assert_eq!(x_inv * x, EdwardsScalar::ONE)
183        }
184
185        // Inversion of zero is zero
186        let zero = EdwardsScalar::ZERO;
187        let expected_zero = zero.invert();
188        assert_eq!(expected_zero, zero)
189    }
190    #[test]
191    fn test_serialise() {
192        let scalar = EdwardsScalar::new(U448::from_be_hex(
193            "0d79f6e375d3395ed9a6c4c3c49a1433fd7c58aa38363f74e9ab2c22a22347d79988f8e01e8a309f862a9f1052fcd042b9b1ed7115598f62",
194        ));
195        let got = EdwardsScalar::from_canonical_bytes(&scalar.into()).unwrap();
196        assert_eq!(scalar, got)
197    }
198    #[test]
199    fn test_from_canonical_bytes() {
200        // ff..ff should fail
201        let mut bytes = EdwardsScalarBytes::from(hex!(
202            "ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff"
203        ));
204        bytes.reverse();
205        let s = EdwardsScalar::from_canonical_bytes(&bytes);
206        assert!(<Choice as Into<bool>>::into(s.is_none()));
207
208        // n should fail
209        let mut bytes = EdwardsScalarBytes::from(hex!(
210            "003fffffffffffffffffffffffffffffffffffffffffffffffffffffff7cca23e9c44edb49aed63690216cc2728dc58f552378c292ab5844f3"
211        ));
212        bytes.reverse();
213        let s = EdwardsScalar::from_canonical_bytes(&bytes);
214        assert!(<Choice as Into<bool>>::into(s.is_none()));
215
216        // n-1 should work
217        let mut bytes = EdwardsScalarBytes::from(hex!(
218            "003fffffffffffffffffffffffffffffffffffffffffffffffffffffff7cca23e9c44edb49aed63690216cc2728dc58f552378c292ab5844f2"
219        ));
220        bytes.reverse();
221        let s = EdwardsScalar::from_canonical_bytes(&bytes);
222        match Option::<EdwardsScalar>::from(s) {
223            Some(s) => assert_eq!(s, EdwardsScalar::ZERO - EdwardsScalar::ONE),
224            None => panic!("should not return None"),
225        };
226    }
227
228    #[test]
229    fn test_from_bytes_mod_order_wide() {
230        // n should become 0
231        let mut bytes = WideEdwardsScalarBytes::from(hex!(
232            "000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000003fffffffffffffffffffffffffffffffffffffffffffffffffffffff7cca23e9c44edb49aed63690216cc2728dc58f552378c292ab5844f3"
233        ));
234        bytes.reverse();
235        let s = EdwardsScalar::from_bytes_mod_order_wide(&bytes);
236        assert_eq!(s, EdwardsScalar::ZERO);
237
238        // n-1 should stay the same
239        let mut bytes = WideEdwardsScalarBytes::from(hex!(
240            "000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000003fffffffffffffffffffffffffffffffffffffffffffffffffffffff7cca23e9c44edb49aed63690216cc2728dc58f552378c292ab5844f2"
241        ));
242        bytes.reverse();
243        let s = EdwardsScalar::from_bytes_mod_order_wide(&bytes);
244        assert_eq!(s, EdwardsScalar::ZERO - EdwardsScalar::ONE);
245
246        // n+1 should become 1
247        let mut bytes = WideEdwardsScalarBytes::from(hex!(
248            "000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000003fffffffffffffffffffffffffffffffffffffffffffffffffffffff7cca23e9c44edb49aed63690216cc2728dc58f552378c292ab5844f4"
249        ));
250        bytes.reverse();
251        let s = EdwardsScalar::from_bytes_mod_order_wide(&bytes);
252        assert_eq!(s, EdwardsScalar::ONE);
253
254        // 2^912-1 should become 0x2939f823b7292052bcb7e4d070af1a9cc14ba3c47c44ae17cf72c985bb24b6c520e319fb37a63e29800f160787ad1d2e11883fa931e7de81
255        let bytes = WideEdwardsScalarBytes::from(hex!(
256            "ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff"
257        ));
258        let s = EdwardsScalar::from_bytes_mod_order_wide(&bytes);
259        let mut bytes = EdwardsScalarBytes::from(hex!(
260            "002939f823b7292052bcb7e4d070af1a9cc14ba3c47c44ae17cf72c985bb24b6c520e319fb37a63e29800f160787ad1d2e11883fa931e7de81"
261        ));
262        bytes.reverse();
263        let reduced = EdwardsScalar::from_canonical_bytes(&bytes).unwrap();
264        assert_eq!(s, reduced);
265    }
266
267    #[test]
268    fn test_to_bytes_rfc8032() {
269        // n-1
270        let mut bytes: [u8; 57] = hex!(
271            "003fffffffffffffffffffffffffffffffffffffffffffffffffffffff7cca23e9c44edb49aed63690216cc2728dc58f552378c292ab5844f2"
272        );
273        bytes.reverse();
274        let x = EdwardsScalar::ZERO - EdwardsScalar::ONE;
275        let candidate = x.to_bytes_rfc_8032();
276        assert_eq!(&bytes[..], &candidate[..]);
277    }
278
279    #[cfg(all(feature = "alloc", feature = "serde"))]
280    #[test]
281    fn serde() {
282        use elliptic_curve::PrimeField;
283
284        let res = serde_json::to_string(&EdwardsScalar::TWO_INV);
285        assert!(res.is_ok());
286        let sj = res.unwrap();
287
288        let res = serde_json::from_str::<EdwardsScalar>(&sj);
289        assert!(res.is_ok());
290        assert_eq!(res.unwrap(), EdwardsScalar::TWO_INV);
291
292        let res = serde_bare::to_vec(&EdwardsScalar::TWO_INV);
293        assert!(res.is_ok());
294        let sb = res.unwrap();
295        assert_eq!(sb.len(), 57);
296
297        let res = serde_bare::from_slice::<EdwardsScalar>(&sb);
298        assert!(res.is_ok());
299        assert_eq!(res.unwrap(), EdwardsScalar::TWO_INV);
300    }
301
302    #[test]
303    fn scalar_hash() {
304        let msg = b"hello world";
305        let dst = b"edwards448_XOF:SHAKE256_ELL2_RO_";
306        let res = hash2curve::hash_to_scalar::<Ed448, ExpandMsgXof<Shake256>, U84>(&[msg], &[dst])
307            .unwrap();
308        let expected: [u8; 57] = hex_literal::hex!(
309            "2d32a08f09b88275cc5f437e625696b18de718ed94559e17e4d64aafd143a8527705132178b5ce7395ea6214735387398a35913656b4951300"
310        );
311        assert_eq!(res.to_bytes_rfc_8032(), Array::from(expected));
312    }
313
314    #[property_test]
315    fn from_canonical_bytes(bytes: [u8; 57]) {
316        EdwardsScalar::from_canonical_bytes(&bytes.into());
317    }
318}
ed448_goldilocks/edwards/scalar.rs

ed448_goldilocks/edwards/
scalar.rs
