ed448_goldilocks/decaf/
scalar.rs

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

ed448_goldilocks/decaf/
scalar.rs
