ed448_goldilocks/field/
element.rs

1use core::fmt::{self, Debug, Display, Formatter, LowerHex, UpperHex};
2use core::iter::{Product, Sum};
3use core::ops::{Add, AddAssign, Mul, MulAssign, Neg, Sub, SubAssign};
4
5use super::{ConstMontyType, MODULUS};
6use crate::{
7    AffinePoint, Decaf448, DecafPoint, Ed448, EdwardsPoint,
8    curve::twedwards::extended::ExtendedPoint as TwistedExtendedPoint,
9};
10use elliptic_curve::{
11    Field,
12    array::Array,
13    bigint::{
14        NonZero, U448, U704, Zero,
15        consts::{U28, U56, U84, U88},
16        modular::ConstMontyParams,
17    },
18    ops::{BatchInvert, Reduce},
19    zeroize::DefaultIsZeroes,
20};
21use hash2curve::MapToCurve;
22use rand_core::TryRng;
23use subtle::{
24    Choice, ConditionallyNegatable, ConditionallySelectable, ConstantTimeEq, ConstantTimeLess,
25    CtOption,
26};
27
28#[derive(Clone, Copy, Default)]
29pub struct FieldElement(pub(crate) ConstMontyType);
30
31impl Display for FieldElement {
32    fn fmt(&self, f: &mut Formatter<'_>) -> fmt::Result {
33        write!(f, "{:x}", self.0.retrieve())
34    }
35}
36
37impl Debug for FieldElement {
38    fn fmt(&self, f: &mut Formatter<'_>) -> fmt::Result {
39        write!(f, "FieldElement({:x})", self.0.retrieve())
40    }
41}
42
43impl LowerHex for FieldElement {
44    fn fmt(&self, f: &mut Formatter<'_>) -> fmt::Result {
45        write!(f, "{:x}", self.0.retrieve())
46    }
47}
48
49impl UpperHex for FieldElement {
50    fn fmt(&self, f: &mut Formatter<'_>) -> fmt::Result {
51        write!(f, "{:X}", self.0.retrieve())
52    }
53}
54
55impl BatchInvert for FieldElement {}
56
57impl ConstantTimeEq for FieldElement {
58    fn ct_eq(&self, other: &Self) -> Choice {
59        self.0.ct_eq(&other.0)
60    }
61}
62
63impl ConditionallySelectable for FieldElement {
64    fn conditional_select(a: &Self, b: &Self, choice: Choice) -> Self {
65        Self(ConstMontyType::conditional_select(&a.0, &b.0, choice))
66    }
67}
68
69impl PartialEq for FieldElement {
70    fn eq(&self, other: &FieldElement) -> bool {
71        self.ct_eq(other).into()
72    }
73}
74impl Eq for FieldElement {}
75
76impl Reduce<Array<u8, U84>> for FieldElement {
77    fn reduce(value: &Array<u8, U84>) -> Self {
78        const SEMI_WIDE_MODULUS: NonZero<U704> = NonZero::<U704>::new_unwrap(U704::from_be_hex(
79            "0000000000000000000000000000000000000000000000000000000000000000fffffffffffffffffffffffffffffffffffffffffffffffffffffffeffffffffffffffffffffffffffffffffffffffffffffffffffffffff",
80        ));
81        let mut tmp = Array::<u8, U88>::default();
82        tmp[4..].copy_from_slice(&value[..]);
83
84        let mut num = U704::from_be_slice(&tmp[..]);
85        num %= SEMI_WIDE_MODULUS;
86
87        let bytes =
88            <[u8; 56]>::try_from(&num.to_le_bytes()[..56]).expect("slice is the wrong length");
89        FieldElement(ConstMontyType::new(&U448::from_le_slice(&bytes)))
90    }
91}
92
93impl Reduce<Array<u8, U56>> for FieldElement {
94    fn reduce(value: &Array<u8, U56>) -> Self {
95        FieldElement::from_bytes(&value.0)
96    }
97}
98
99impl DefaultIsZeroes for FieldElement {}
100
101impl Add<&FieldElement> for &FieldElement {
102    type Output = FieldElement;
103
104    fn add(self, other: &FieldElement) -> FieldElement {
105        FieldElement(self.0.add(&other.0))
106    }
107}
108
109define_add_variants!(
110    LHS = FieldElement,
111    RHS = FieldElement,
112    Output = FieldElement
113);
114
115impl AddAssign for FieldElement {
116    fn add_assign(&mut self, other: FieldElement) {
117        *self = *self + other;
118    }
119}
120
121impl AddAssign<&FieldElement> for FieldElement {
122    fn add_assign(&mut self, other: &FieldElement) {
123        *self = *self + *other;
124    }
125}
126
127impl Sub<&FieldElement> for &FieldElement {
128    type Output = FieldElement;
129
130    fn sub(self, other: &FieldElement) -> FieldElement {
131        FieldElement(self.0.sub(&other.0))
132    }
133}
134
135define_sub_variants!(
136    LHS = FieldElement,
137    RHS = FieldElement,
138    Output = FieldElement
139);
140
141impl SubAssign for FieldElement {
142    fn sub_assign(&mut self, other: FieldElement) {
143        *self = *self - other;
144    }
145}
146
147impl SubAssign<&FieldElement> for FieldElement {
148    fn sub_assign(&mut self, other: &FieldElement) {
149        *self = *self - *other;
150    }
151}
152
153impl Mul<&FieldElement> for &FieldElement {
154    type Output = FieldElement;
155
156    fn mul(self, other: &FieldElement) -> FieldElement {
157        FieldElement(self.0.mul(&other.0))
158    }
159}
160
161define_mul_variants!(
162    LHS = FieldElement,
163    RHS = FieldElement,
164    Output = FieldElement
165);
166
167impl MulAssign<&FieldElement> for FieldElement {
168    fn mul_assign(&mut self, other: &FieldElement) {
169        *self = *self * *other;
170    }
171}
172
173impl MulAssign for FieldElement {
174    fn mul_assign(&mut self, other: FieldElement) {
175        *self = *self * other;
176    }
177}
178
179impl Neg for &FieldElement {
180    type Output = FieldElement;
181
182    fn neg(self) -> FieldElement {
183        -*self
184    }
185}
186
187impl Neg for FieldElement {
188    type Output = FieldElement;
189
190    fn neg(self) -> FieldElement {
191        Self(self.0.neg())
192    }
193}
194
195impl MapToCurve for Ed448 {
196    type SecurityLevel = U28;
197    type FieldElement = FieldElement;
198    type Length = U84;
199
200    fn map_to_curve(element: FieldElement) -> EdwardsPoint {
201        element.map_to_curve_elligator2().isogeny().to_edwards()
202    }
203}
204
205impl MapToCurve for Decaf448 {
206    type SecurityLevel = U28;
207    type FieldElement = FieldElement;
208    type Length = U56;
209
210    fn map_to_curve(element: FieldElement) -> DecafPoint {
211        DecafPoint(element.map_to_curve_decaf448())
212    }
213}
214
215impl Sum for FieldElement {
216    fn sum<I: Iterator<Item = Self>>(iter: I) -> Self {
217        iter.reduce(Add::add).unwrap_or(Self::ZERO)
218    }
219}
220
221impl<'a> Sum<&'a FieldElement> for FieldElement {
222    fn sum<I: Iterator<Item = &'a FieldElement>>(iter: I) -> Self {
223        iter.copied().sum()
224    }
225}
226
227impl Product for FieldElement {
228    fn product<I: Iterator<Item = Self>>(iter: I) -> Self {
229        iter.reduce(Mul::mul).unwrap_or(Self::ONE)
230    }
231}
232
233impl<'a> Product<&'a FieldElement> for FieldElement {
234    fn product<I: Iterator<Item = &'a Self>>(iter: I) -> Self {
235        iter.copied().product()
236    }
237}
238
239impl Field for FieldElement {
240    const ZERO: Self = Self::ZERO;
241    const ONE: Self = Self::ONE;
242
243    fn try_random<R: TryRng + ?Sized>(rng: &mut R) -> Result<Self, R::Error> {
244        let mut bytes = [0; 56];
245
246        loop {
247            rng.try_fill_bytes(&mut bytes)?;
248            if let Some(fe) = Self::from_repr(&bytes).into() {
249                return Ok(fe);
250            }
251        }
252    }
253
254    fn square(&self) -> Self {
255        self.square()
256    }
257
258    fn double(&self) -> Self {
259        self.double()
260    }
261
262    fn invert(&self) -> CtOption<Self> {
263        CtOption::from(self.0.invert()).map(Self)
264    }
265
266    fn sqrt(&self) -> CtOption<Self> {
267        let sqrt = self.unchecked_sqrt();
268        CtOption::new(sqrt, sqrt.square().ct_eq(self))
269    }
270
271    fn sqrt_ratio(num: &Self, div: &Self) -> (Choice, Self) {
272        let (result, is_square) = Self::sqrt_ratio(num, div);
273        (is_square, result)
274    }
275}
276
277impl FieldElement {
278    pub const A_PLUS_TWO_OVER_FOUR: Self = Self(ConstMontyType::new(&U448::from_be_hex(
279        "00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000098aa",
280    )));
281    pub const DECAF_FACTOR: Self = Self(ConstMontyType::new(&U448::from_be_hex(
282        "22d962fbeb24f7683bf68d722fa26aa0a1f1a7b8a5b8d54b64a2d780968c14ba839a66f4fd6eded260337bf6aa20ce529642ef0f45572736",
283    )));
284    pub const EDWARDS_D: Self = Self(ConstMontyType::new(&U448::from_be_hex(
285        "fffffffffffffffffffffffffffffffffffffffffffffffffffffffeffffffffffffffffffffffffffffffffffffffffffffffffffff6756",
286    )));
287    pub const J: Self = Self(ConstMontyType::new(&U448::from_u64(156326)));
288    pub const MINUS_ONE: Self = Self(ConstMontyType::new(&U448::from_be_hex(
289        "fffffffffffffffffffffffffffffffffffffffffffffffffffffffefffffffffffffffffffffffffffffffffffffffffffffffffffffffe",
290    )));
291    pub const NEG_EDWARDS_D: Self = Self(ConstMontyType::new(&U448::from_be_hex(
292        "00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000098a9",
293    )));
294    pub const NEG_FOUR_TIMES_TWISTED_D: Self = Self(ConstMontyType::new(&U448::from_be_hex(
295        "00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000262a8",
296    )));
297    pub const ONE: Self = Self(ConstMontyType::new(&U448::ONE));
298    pub const TWO: Self = Self(ConstMontyType::new(&U448::from_u64(2)));
299    pub const TWISTED_D: Self = Self(ConstMontyType::new(&U448::from_be_hex(
300        "fffffffffffffffffffffffffffffffffffffffffffffffffffffffeffffffffffffffffffffffffffffffffffffffffffffffffffff6755",
301    )));
302    pub const TWO_TIMES_TWISTED_D: Self = Self(ConstMontyType::new(&U448::from_be_hex(
303        "fffffffffffffffffffffffffffffffffffffffffffffffffffffffefffffffffffffffffffffffffffffffffffffffffffffffffffeceab",
304    )));
305    pub const Z: Self = Self(ConstMontyType::new(&U448::from_be_hex(
306        "fffffffffffffffffffffffffffffffffffffffffffffffffffffffefffffffffffffffffffffffffffffffffffffffffffffffffffffffe",
307    )));
308    pub const ZERO: Self = Self(ConstMontyType::new(&U448::ZERO));
309
310    pub fn is_negative(&self) -> Choice {
311        self.0.retrieve().is_odd().into()
312    }
313
314    pub fn is_zero(&self) -> Choice {
315        self.0.is_zero().into()
316    }
317
318    /// Inverts a field element
319    pub fn invert(&self) -> Self {
320        Self(self.0.invert().unwrap_or_default())
321    }
322
323    pub fn square(&self) -> Self {
324        Self(self.0.square())
325    }
326
327    /// Squares a field element  `n` times
328    fn square_n<const N: u32>(&self) -> FieldElement {
329        let mut result = *self;
330
331        for _ in 0..N {
332            result = result.square();
333        }
334
335        result
336    }
337
338    pub fn is_square(&self) -> Choice {
339        !Choice::from(self.0.jacobi_symbol().is_minus_one())
340    }
341
342    pub fn unchecked_sqrt(&self) -> FieldElement {
343        // Candidate root is y = x^((p+1)/4).
344        // We have: (p+1)/4 = 2^446 - 2^222
345        let z = *self;
346        let zp2 = z.square() * z;
347        let zp3 = zp2.square() * z;
348        let zp4 = zp3.square() * z;
349        let zp7 = zp4.square_n::<3>() * zp3;
350        let zp14 = zp7.square_n::<7>() * zp7;
351        let zp28 = zp14.square_n::<14>() * zp14;
352        let zp56 = zp28.square_n::<28>() * zp28;
353        let zp112 = zp56.square_n::<56>() * zp56;
354        let zp224 = zp112.square_n::<112>() * zp112;
355        zp224.square_n::<222>()
356    }
357
358    pub fn to_bytes(self) -> [u8; 56] {
359        let mut bytes = [0u8; 56];
360        bytes.copy_from_slice(&self.0.retrieve().to_le_bytes()[..56]);
361        bytes
362    }
363
364    pub fn to_bytes_extended(self) -> [u8; 57] {
365        let mut bytes = [0u8; 57];
366        bytes[..56].copy_from_slice(&self.to_bytes());
367        bytes
368    }
369
370    pub fn from_bytes(bytes: &[u8; 56]) -> Self {
371        Self(ConstMontyType::new(&U448::from_le_slice(bytes)))
372    }
373
374    pub fn from_bytes_extended(bytes: &[u8; 57]) -> Self {
375        Self(ConstMontyType::new(&U448::from_le_slice(&bytes[..56])))
376    }
377
378    pub fn from_repr(bytes: &[u8; 56]) -> CtOption<Self> {
379        let integer = U448::from_le_slice(bytes);
380        let is_some = integer.ct_lt(MODULUS::PARAMS.modulus());
381        CtOption::new(Self(ConstMontyType::new(&integer)), is_some)
382    }
383
384    pub fn double(&self) -> Self {
385        Self(self.0.double())
386    }
387
388    /// Computes the inverse square root of a field element
389    /// Returns the result and a boolean to indicate whether self
390    /// was a Quadratic residue
391    pub(crate) fn inverse_square_root(&self) -> (FieldElement, Choice) {
392        let (mut l0, mut l1, mut l2);
393
394        l1 = self.square();
395        l2 = l1 * self;
396        l1 = l2.square();
397        l2 = l1 * self;
398        l1 = l2.square_n::<3>();
399        l0 = l2 * l1;
400        l1 = l0.square_n::<3>();
401        l0 = l2 * l1;
402        l2 = l0.square_n::<9>();
403        l1 = l0 * l2;
404        l0 = l1.square();
405        l2 = l0 * self;
406        l0 = l2.square_n::<18>();
407        l2 = l1 * l0;
408        l0 = l2.square_n::<37>();
409        l1 = l2 * l0;
410        l0 = l1.square_n::<37>();
411        l1 = l2 * l0;
412        l0 = l1.square_n::<111>();
413        l2 = l1 * l0;
414        l0 = l2.square();
415        l1 = l0 * self;
416        l0 = l1.square_n::<223>();
417        l1 = l2 * l0;
418        l2 = l1.square();
419        l0 = l2 * self;
420
421        let is_residue = l0.ct_eq(&FieldElement::ONE);
422        (l1, is_residue)
423    }
424
425    /// Computes the square root ratio of two elements
426    pub(crate) fn sqrt_ratio(u: &FieldElement, v: &FieldElement) -> (FieldElement, Choice) {
427        // Compute sqrt(1/(uv))
428        let x = *u * v;
429        let (inv_sqrt_x, is_res) = x.inverse_square_root();
430        // Return u * sqrt(1/(uv)) == sqrt(u/v). However, since this trick only works
431        // for u != 0, check for that case explicitly (when u == 0 then inv_sqrt_x
432        // will be zero, which is what we want, but is_res will be 0)
433        let zero_u = u.ct_eq(&FieldElement::ZERO);
434        (inv_sqrt_x * u, zero_u | is_res)
435    }
436
437    pub(crate) fn div_by_2(&self) -> FieldElement {
438        Self(self.0.div_by_2())
439    }
440
441    pub(crate) fn map_to_curve_elligator2(&self) -> AffinePoint {
442        let mut t1 = self.square(); // 1.   t1 = u^2
443        t1 *= Self::Z; // 2.   t1 = Z * t1              // Z * u^2
444        let e1 = t1.ct_eq(&Self::MINUS_ONE); // 3.   e1 = t1 == -1            // exceptional case: Z * u^2 == -1
445        t1.conditional_assign(&Self::ZERO, e1); // 4.   t1 = CMOV(t1, 0, e1)     // if t1 == -1, set t1 = 0
446        let mut x1 = t1 + Self::ONE; // 5.   x1 = t1 + 1
447        x1 = x1.invert(); // 6.   x1 = inv0(x1)
448        x1 *= -Self::J; // 7.   x1 = -A * x1             // x1 = -A / (1 + Z * u^2)
449        let mut gx1 = x1 + Self::J; // 8.  gx1 = x1 + A
450        gx1 *= x1; // 9.  gx1 = gx1 * x1
451        gx1 += Self::ONE; // 10. gx1 = gx1 + B
452        gx1 *= x1; // 11. gx1 = gx1 * x1            // gx1 = x1^3 + A * x1^2 + B * x1
453        let x2 = -x1 - Self::J; // 12.  x2 = -x1 - A
454        let gx2 = t1 * gx1; // 13. gx2 = t1 * gx1
455        let e2 = gx1.is_square(); // 14.  e2 = is_square(gx1)
456        let x = Self::conditional_select(&x2, &x1, e2); // 15.   x = CMOV(x2, x1, e2)    // If is_square(gx1), x = x1, else x = x2
457        let y2 = Self::conditional_select(&gx2, &gx1, e2); // 16.  y2 = CMOV(gx2, gx1, e2)  // If is_square(gx1), y2 = gx1, else y2 = gx2
458        let mut y = y2.unchecked_sqrt(); // 17.   y = sqrt(y2)
459        let e3 = y.is_negative(); // 18.  e3 = sgn0(y) == 1
460        y.conditional_negate(e2 ^ e3); //       y = CMOV(-y, y, e2 xor e3)
461        AffinePoint { x, y }
462    }
463
464    // See https://www.shiftleft.org/papers/decaf/decaf.pdf#section.A.3.
465    // Implementation copied from <https://sourceforge.net/p/ed448goldilocks/code/ci/e5cc6240690d3ffdfcbdb1e4e851954b789cd5d9/tree/src/per_curve/elligator.tmpl.c#l28>.
466    pub(crate) fn map_to_curve_decaf448(&self) -> TwistedExtendedPoint {
467        const ONE_MINUS_TWO_D: FieldElement =
468            FieldElement(ConstMontyType::new(&U448::from_u64(78163)));
469
470        let r = -self.square();
471
472        let a = r - Self::ONE;
473        let b = a * Self::EDWARDS_D;
474        let a = b + Self::ONE;
475        let b = b - r;
476        let c = a * b;
477
478        let a = r + Self::ONE;
479        let n = a * ONE_MINUS_TWO_D;
480
481        let a = c * n;
482        let (b, square) = a.inverse_square_root();
483        let c = Self::conditional_select(self, &Self::ONE, square);
484        let e = b * c;
485
486        let mut a = n * e;
487        a.conditional_negate(!a.is_negative() ^ square);
488
489        let c = e * ONE_MINUS_TWO_D;
490        let b = c.square();
491        let e = r - Self::ONE;
492        let c = b * e;
493        let mut b = c * n;
494        b.conditional_negate(square);
495        let b = b - Self::ONE;
496
497        let c = a.square();
498        let a = a.double();
499        let e = c + Self::ONE;
500        let T = a * e;
501        let X = a * b;
502        let a = Self::ONE - c;
503        let Y = e * a;
504        let Z = a * b;
505
506        TwistedExtendedPoint { X, Y, Z, T }
507    }
508}
509
510#[cfg(test)]
511mod tests {
512    use super::*;
513    use elliptic_curve::consts::U32;
514    use hash2curve::{ExpandMsg, ExpandMsgXof, Expander};
515    use hex_literal::hex;
516    use shake::Shake256;
517
518    fn assert_from_okm(dst: &[u8], msgs: &[(&[u8], [u8; 56], [u8; 56])]) {
519        for (msg, expected_u0, expected_u1) in msgs {
520            let mut expander = <ExpandMsgXof<Shake256> as ExpandMsg<U32>>::expand_message(
521                &[*msg],
522                &[dst],
523                (84 * 2).try_into().unwrap(),
524            )
525            .unwrap();
526
527            let mut data = Array::<u8, U84>::default();
528            expander.fill_bytes(&mut data).unwrap();
529            let u0 = FieldElement::reduce(&data);
530
531            let mut e_u0 = *expected_u0;
532            e_u0.reverse();
533            let mut e_u1 = *expected_u1;
534            e_u1.reverse();
535
536            assert_eq!(u0.to_bytes(), e_u0);
537            expander.fill_bytes(&mut data).unwrap();
538            let u1 = FieldElement::reduce(&data);
539            assert_eq!(u1.to_bytes(), e_u1);
540        }
541    }
542
543    #[test]
544    fn from_okm_curve448() {
545        const DST: &[u8] = b"QUUX-V01-CS02-with-curve448_XOF:SHAKE256_ELL2_RO_";
546        const MSGS: &[(&[u8], [u8; 56], [u8; 56])] = &[
547            (b"", hex!("c704c7b3d3b36614cf3eedd0324fe6fe7d1402c50efd16cff89ff63f50938506280d3843478c08e24f7842f4e3ef45f6e3c4897f9d976148"), hex!("c25427dc97fff7a5ad0a78654e2c6c27b1c1127b5b53c7950cd1fd6edd2703646b25f341e73deedfebf022d1d3cecd02b93b4d585ead3ed7")),
548            (b"abc", hex!("2dd95593dfee26fe0d218d3d9a0a23d9e1a262fd1d0b602483d08415213e75e2db3c69b0a5bc89e71bcefc8c723d2b6a0cf263f02ad2aa70"), hex!("272e4c79a1290cc6d2bc4f4f9d31bf7fbe956ca303c04518f117d77c0e9d850796fc3e1e2bcb9c75e8eaaded5e150333cae9931868047c9d")),
549            (b"abcdef0123456789", hex!("6aab71a38391639f27e49eae8b1cb6b7172a1f478190ece293957e7cdb2391e7cc1c4261970d9c1bbf9c3915438f74fbd7eb5cd4d4d17ace"), hex!("c80b8380ca47a3bcbf76caa75cef0e09f3d270d5ee8f676cde11aedf41aaca6741bd81a86232bd336ccb42efad39f06542bc06a67b65909e")),
550            (b"q128_qqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqq", hex!("cb5c27e51f9c18ee8ffdb6be230f4eb4f2c2481963b2293484f08da2241c1ff59f80978e6defe9d70e34abba2fcbe12dc3a1eb2c5d3d2e4a"), hex!("c895e8afecec5466e126fa70fc4aa784b8009063afb10e3ee06a9b22318256aa8693b0c85b955cf2d6540b8ed71e729af1b8d5ca3b116cd7")),
551            (b"a512_aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa", hex!("8cba93a007bb2c801b1769e026b1fa1640b14a34cf3029db3c7fd6392745d6fec0f7870b5071d6da4402cedbbde28ae4e50ab30e1049a238"), hex!("4223746145069e4b8a981acc3404259d1a2c3ecfed5d864798a89d45f81a2c59e2d40eb1d5f0fe11478cbb2bb30246dd388cb932ad7bb330")),
552        ];
553
554        // TODO: This should be `Curve448FieldElement`.
555        assert_from_okm(DST, MSGS);
556    }
557
558    #[test]
559    fn from_okm_edwards448() {
560        const DST: &[u8] = b"QUUX-V01-CS02-with-edwards448_XOF:SHAKE256_ELL2_RO_";
561        const MSGS: &[(&[u8], [u8; 56], [u8; 56])] = &[
562            (b"", hex!("0847c5ebf957d3370b1f98fde499fb3e659996d9fc9b5707176ade785ba72cd84b8a5597c12b1024be5f510fa5ba99642c4cec7f3f69d3e7"), hex!("f8cbd8a7ae8c8deed071f3ac4b93e7cfcb8f1eac1645d699fd6d3881cb295a5d3006d9449ed7cad412a77a1fe61e84a9e41d59ef384d6f9a")),
563            (b"abc", hex!("04d975cd938ab49be3e81703d6a57cca84ed80d2ff6d4756d3f22947fb5b70ab0231f0087cbfb4b7cae73b41b0c9396b356a4831d9a14322"), hex!("2547ca887ac3db7b5fad3a098aa476e90078afe1358af6c63d677d6edfd2100bc004e0f5db94dd2560fc5b308e223241d00488c9ca6b0ef2")),
564            (b"abcdef0123456789", hex!("10659ce25588db4e4be6f7c791a79eb21a7f24aaaca76a6ca3b83b80aaf95aa328fe7d569a1ac99f9cd216edf3915d72632f1a8b990e250c"), hex!("9243e5b6c480683fd533e81f4a778349a309ce00bd163a29eb9fa8dbc8f549242bef33e030db21cffacd408d2c4264b93e476c6a8590e7aa")),
565            (b"q128_qqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqq", hex!("c80390020e578f009ead417029eff6cd0926110922db63ab98395e3bdfdd5d8a65b1a2b8d495dc8c5e59b7f3518731f7dfc0f93ace5dee4b"), hex!("1c4dc6653a445bbef2add81d8e90a6c8591a788deb91d0d3f1519a2e4a460313041b77c1b0817f2e80b388e5c3e49f37d787dc1f85e4324a")),
566            (b"a512_aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa", hex!("163c79ab0210a4b5e4f44fb19437ea965bf5431ab233ef16606f0b03c5f16a3feb7d46a5a675ce8f606e9c2bf74ee5336c54a1e54919f13f"), hex!("f99666bde4995c4088333d6c2734687e815f80a99c6da02c47df4b51f6c9d9ed466b4fecf7d9884990a8e0d0be6907fa437e0b1a27f49265")),
567        ];
568
569        assert_from_okm(DST, MSGS);
570    }
571
572    #[test]
573    fn get_constants() {
574        let m1 = -FieldElement::ONE;
575        assert_eq!(m1, FieldElement::MINUS_ONE);
576    }
577
578    #[test]
579    fn sqrt() {
580        for &n in &[1u8, 4, 9, 16, 25, 36, 49, 64] {
581            let mut bytes = [0u8; 56];
582            bytes[0] = n;
583
584            let fe = FieldElement::from_bytes(&bytes);
585            let sqrt = fe.sqrt().unwrap();
586            assert_eq!(sqrt.square(), fe);
587        }
588
589        let nine = FieldElement::from_bytes(&[
590            0x09, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
591            0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
592            0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
593            0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
594        ]);
595        let three = FieldElement::from_bytes(&[
596            0x03, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
597            0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
598            0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
599            0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
600        ]);
601        assert_eq!(three, nine.unchecked_sqrt());
602    }
603}
ed448_goldilocks/field/element.rs

ed448_goldilocks/field/
element.rs
