dalek_ff_group/
field.rs

1use core::{
2  ops::{Add, AddAssign, Sub, SubAssign, Neg, Mul, MulAssign},
3  iter::{Sum, Product},
4};
5
6use zeroize::Zeroize;
7use rand_core::RngCore;
8
9use subtle::{
10  Choice, CtOption, ConstantTimeEq, ConstantTimeLess, ConditionallyNegatable,
11  ConditionallySelectable,
12};
13
14use crypto_bigint::{
15  Integer, NonZero, Encoding, U256, U512,
16  modular::constant_mod::{ResidueParams, Residue},
17  impl_modulus,
18};
19
20use group::ff::{Field, PrimeField, FieldBits, PrimeFieldBits, FromUniformBytes};
21
22use crate::{u8_from_bool, constant_time, math_op, math};
23
24// 2 ** 255 - 19
25// Uses saturating_sub because checked_sub isn't available at compile time
26const MODULUS: U256 = U256::from_u8(1).shl_vartime(255).saturating_sub(&U256::from_u8(19));
27const WIDE_MODULUS: U512 = U256::ZERO.concat(&MODULUS);
28
29impl_modulus!(
30  FieldModulus,
31  U256,
32  // 2 ** 255 - 19
33  "7fffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffed"
34);
35type ResidueType = Residue<FieldModulus, { FieldModulus::LIMBS }>;
36
37/// A constant-time implementation of the Ed25519 field.
38#[derive(Clone, Copy, PartialEq, Eq, Default, Debug, Zeroize)]
39#[repr(transparent)]
40pub struct FieldElement(ResidueType);
41
42// Square root of -1.
43// Formula from RFC-8032 (modp_sqrt_m1/sqrt8k5 z)
44// 2 ** ((MODULUS - 1) // 4) % MODULUS
45const SQRT_M1: FieldElement = FieldElement(
46  ResidueType::new(&U256::from_u8(2))
47    .pow(&MODULUS.saturating_sub(&U256::ONE).wrapping_div(&U256::from_u8(4))),
48);
49
50// Constant useful in calculating square roots (RFC-8032 sqrt8k5's exponent used to calculate y)
51const MOD_3_8: FieldElement = FieldElement(ResidueType::new(
52  &MODULUS.saturating_add(&U256::from_u8(3)).wrapping_div(&U256::from_u8(8)),
53));
54
55// Constant useful in sqrt_ratio_i (sqrt(u / v))
56const MOD_5_8: FieldElement = FieldElement(ResidueType::sub(&MOD_3_8.0, &ResidueType::ONE));
57
58fn reduce(x: U512) -> ResidueType {
59  ResidueType::new(&U256::from_le_slice(
60    &x.rem(&NonZero::new(WIDE_MODULUS).unwrap()).to_le_bytes()[.. 32],
61  ))
62}
63
64constant_time!(FieldElement, ResidueType);
65math!(
66  FieldElement,
67  FieldElement,
68  |x: ResidueType, y: ResidueType| x.add(&y),
69  |x: ResidueType, y: ResidueType| x.sub(&y),
70  |x: ResidueType, y: ResidueType| x.mul(&y)
71);
72
73macro_rules! from_wrapper {
74  ($uint: ident) => {
75    impl From<$uint> for FieldElement {
76      fn from(a: $uint) -> FieldElement {
77        Self(ResidueType::new(&U256::from(a)))
78      }
79    }
80  };
81}
82
83from_wrapper!(u8);
84from_wrapper!(u16);
85from_wrapper!(u32);
86from_wrapper!(u64);
87from_wrapper!(u128);
88
89impl Neg for FieldElement {
90  type Output = Self;
91  fn neg(self) -> Self::Output {
92    Self(self.0.neg())
93  }
94}
95
96impl Neg for &FieldElement {
97  type Output = FieldElement;
98  fn neg(self) -> Self::Output {
99    (*self).neg()
100  }
101}
102
103impl Field for FieldElement {
104  const ZERO: Self = Self(ResidueType::ZERO);
105  const ONE: Self = Self(ResidueType::ONE);
106
107  fn random(mut rng: impl RngCore) -> Self {
108    let mut bytes = [0; 64];
109    rng.fill_bytes(&mut bytes);
110    FieldElement(reduce(U512::from_le_bytes(bytes)))
111  }
112
113  fn square(&self) -> Self {
114    FieldElement(self.0.square())
115  }
116  fn double(&self) -> Self {
117    FieldElement(self.0.add(&self.0))
118  }
119
120  fn invert(&self) -> CtOption<Self> {
121    const NEG_2: FieldElement =
122      FieldElement(ResidueType::new(&MODULUS.saturating_sub(&U256::from_u8(2))));
123    CtOption::new(self.pow(NEG_2), !self.is_zero())
124  }
125
126  // RFC-8032 sqrt8k5
127  fn sqrt(&self) -> CtOption<Self> {
128    let tv1 = self.pow(MOD_3_8);
129    let tv2 = tv1 * SQRT_M1;
130    let candidate = Self::conditional_select(&tv2, &tv1, tv1.square().ct_eq(self));
131    CtOption::new(candidate, candidate.square().ct_eq(self))
132  }
133
134  fn sqrt_ratio(u: &FieldElement, v: &FieldElement) -> (Choice, FieldElement) {
135    let i = SQRT_M1;
136
137    let u = *u;
138    let v = *v;
139
140    let v3 = v.square() * v;
141    let v7 = v3.square() * v;
142    let mut r = (u * v3) * (u * v7).pow(MOD_5_8);
143
144    let check = v * r.square();
145    let correct_sign = check.ct_eq(&u);
146    let flipped_sign = check.ct_eq(&(-u));
147    let flipped_sign_i = check.ct_eq(&((-u) * i));
148
149    r.conditional_assign(&(r * i), flipped_sign | flipped_sign_i);
150
151    let r_is_negative = r.is_odd();
152    r.conditional_negate(r_is_negative);
153
154    (correct_sign | flipped_sign, r)
155  }
156}
157
158impl PrimeField for FieldElement {
159  type Repr = [u8; 32];
160
161  // Big endian representation of the modulus
162  const MODULUS: &'static str = "7fffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffed";
163
164  const NUM_BITS: u32 = 255;
165  const CAPACITY: u32 = 254;
166
167  const TWO_INV: Self = FieldElement(ResidueType::new(&U256::from_u8(2)).invert().0);
168
169  // This was calculated with the method from the ff crate docs
170  // SageMath GF(modulus).primitive_element()
171  const MULTIPLICATIVE_GENERATOR: Self = Self(ResidueType::new(&U256::from_u8(2)));
172  // This was set per the specification in the ff crate docs
173  // The number of leading zero bits in the little-endian bit representation of (modulus - 1)
174  const S: u32 = 2;
175
176  // This was calculated via the formula from the ff crate docs
177  // Self::MULTIPLICATIVE_GENERATOR ** ((modulus - 1) >> Self::S)
178  const ROOT_OF_UNITY: Self = FieldElement(ResidueType::new(&U256::from_be_hex(
179    "2b8324804fc1df0b2b4d00993dfbd7a72f431806ad2fe478c4ee1b274a0ea0b0",
180  )));
181  // Self::ROOT_OF_UNITY.invert()
182  const ROOT_OF_UNITY_INV: Self = FieldElement(Self::ROOT_OF_UNITY.0.invert().0);
183
184  // This was calculated via the formula from the ff crate docs
185  // Self::MULTIPLICATIVE_GENERATOR ** (2 ** Self::S)
186  const DELTA: Self = FieldElement(ResidueType::new(&U256::from_be_hex(
187    "0000000000000000000000000000000000000000000000000000000000000010",
188  )));
189
190  fn from_repr(bytes: [u8; 32]) -> CtOption<Self> {
191    let res = U256::from_le_bytes(bytes);
192    CtOption::new(Self(ResidueType::new(&res)), res.ct_lt(&MODULUS))
193  }
194  fn to_repr(&self) -> [u8; 32] {
195    self.0.retrieve().to_le_bytes()
196  }
197
198  fn is_odd(&self) -> Choice {
199    self.0.retrieve().is_odd()
200  }
201
202  fn from_u128(num: u128) -> Self {
203    Self::from(num)
204  }
205}
206
207impl PrimeFieldBits for FieldElement {
208  type ReprBits = [u8; 32];
209
210  fn to_le_bits(&self) -> FieldBits<Self::ReprBits> {
211    self.to_repr().into()
212  }
213
214  fn char_le_bits() -> FieldBits<Self::ReprBits> {
215    MODULUS.to_le_bytes().into()
216  }
217}
218
219impl FieldElement {
220  /// Create a FieldElement from a `crypto_bigint::U256`.
221  ///
222  /// This will reduce the `U256` by the modulus, into a member of the field.
223  pub const fn from_u256(u256: &U256) -> Self {
224    FieldElement(Residue::new(u256))
225  }
226
227  /// Create a `FieldElement` from the reduction of a 512-bit number.
228  ///
229  /// The bytes are interpreted in little-endian format.
230  pub fn wide_reduce(value: [u8; 64]) -> Self {
231    FieldElement(reduce(U512::from_le_bytes(value)))
232  }
233
234  /// Perform an exponentiation.
235  pub fn pow(&self, other: FieldElement) -> FieldElement {
236    let mut table = [FieldElement::ONE; 16];
237    table[1] = *self;
238    for i in 2 .. 16 {
239      table[i] = table[i - 1] * self;
240    }
241
242    let mut res = FieldElement::ONE;
243    let mut bits = 0;
244    for (i, mut bit) in other.to_le_bits().iter_mut().rev().enumerate() {
245      bits <<= 1;
246      let mut bit = u8_from_bool(&mut bit);
247      bits |= bit;
248      bit.zeroize();
249
250      if ((i + 1) % 4) == 0 {
251        if i != 3 {
252          for _ in 0 .. 4 {
253            res *= res;
254          }
255        }
256
257        let mut scale_by = FieldElement::ONE;
258        #[allow(clippy::needless_range_loop)]
259        for i in 0 .. 16 {
260          #[allow(clippy::cast_possible_truncation)] // Safe since 0 .. 16
261          {
262            scale_by = <_>::conditional_select(&scale_by, &table[i], bits.ct_eq(&(i as u8)));
263          }
264        }
265        res *= scale_by;
266        bits = 0;
267      }
268    }
269    res
270  }
271
272  /// The square root of u/v, as used for Ed25519 point decoding (RFC 8032 5.1.3) and within
273  /// Ristretto (5.1 Extracting an Inverse Square Root).
274  ///
275  /// The result is only a valid square root if the Choice is true.
276  /// RFC 8032 simply fails if there isn't a square root, leaving any return value undefined.
277  /// Ristretto explicitly returns 0 or sqrt((SQRT_M1 * u) / v).
278  pub fn sqrt_ratio_i(u: FieldElement, v: FieldElement) -> (Choice, FieldElement) {
279    let i = SQRT_M1;
280
281    let v3 = v.square() * v;
282    let v7 = v3.square() * v;
283    // Candidate root
284    let mut r = (u * v3) * (u * v7).pow(MOD_5_8);
285
286    // 8032 3.1
287    let check = v * r.square();
288    let correct_sign = check.ct_eq(&u);
289    // 8032 3.2 conditional
290    let neg_u = -u;
291    let flipped_sign = check.ct_eq(&neg_u);
292    // Ristretto Step 5
293    let flipped_sign_i = check.ct_eq(&(neg_u * i));
294
295    // 3.2 set
296    r.conditional_assign(&(r * i), flipped_sign | flipped_sign_i);
297
298    // Always return the even root, per Ristretto
299    // This doesn't break Ed25519 point decoding as that doesn't expect these steps to return a
300    // specific root
301    // Ed25519 points include a dedicated sign bit to determine which root to use, so at worst
302    // this is a pointless inefficiency
303    r.conditional_negate(r.is_odd());
304
305    (correct_sign | flipped_sign, r)
306  }
307}
308
309impl FromUniformBytes<64> for FieldElement {
310  fn from_uniform_bytes(bytes: &[u8; 64]) -> Self {
311    Self::wide_reduce(*bytes)
312  }
313}
314
315impl Sum<FieldElement> for FieldElement {
316  fn sum<I: Iterator<Item = FieldElement>>(iter: I) -> FieldElement {
317    let mut res = FieldElement::ZERO;
318    for item in iter {
319      res += item;
320    }
321    res
322  }
323}
324
325impl<'a> Sum<&'a FieldElement> for FieldElement {
326  fn sum<I: Iterator<Item = &'a FieldElement>>(iter: I) -> FieldElement {
327    iter.copied().sum()
328  }
329}
330
331impl Product<FieldElement> for FieldElement {
332  fn product<I: Iterator<Item = FieldElement>>(iter: I) -> FieldElement {
333    let mut res = FieldElement::ONE;
334    for item in iter {
335      res *= item;
336    }
337    res
338  }
339}
340
341impl<'a> Product<&'a FieldElement> for FieldElement {
342  fn product<I: Iterator<Item = &'a FieldElement>>(iter: I) -> FieldElement {
343    iter.copied().product()
344  }
345}
346
347#[test]
348fn test_wide_modulus() {
349  let mut wide = [0; 64];
350  wide[.. 32].copy_from_slice(&MODULUS.to_le_bytes());
351  assert_eq!(wide, WIDE_MODULUS.to_le_bytes());
352}
353
354#[test]
355fn test_sqrt_m1() {
356  // Test equivalence against the known constant value
357  const SQRT_M1_MAGIC: U256 =
358    U256::from_be_hex("2b8324804fc1df0b2b4d00993dfbd7a72f431806ad2fe478c4ee1b274a0ea0b0");
359  assert_eq!(SQRT_M1.0.retrieve(), SQRT_M1_MAGIC);
360
361  // Also test equivalence against the result of the formula from RFC-8032 (modp_sqrt_m1/sqrt8k5 z)
362  // 2 ** ((MODULUS - 1) // 4) % MODULUS
363  assert_eq!(
364    SQRT_M1,
365    FieldElement::from(2u8).pow(FieldElement(ResidueType::new(
366      &(FieldElement::ZERO - FieldElement::ONE).0.retrieve().wrapping_div(&U256::from(4u8))
367    )))
368  );
369}
370
371#[test]
372fn test_field() {
373  ff_group_tests::prime_field::test_prime_field_bits::<_, FieldElement>(&mut rand_core::OsRng);
374}
dalek_ff_group/field.rs

dalek_ff_group/
field.rs
