1 // -*- mode: rust; -*-
2 //
3 // This file is part of curve25519-dalek.
4 // Copyright (c) 2016-2021 isis agora lovecruft
5 // Copyright (c) 2016-2019 Henry de Valence
6 // See LICENSE for licensing information.
7 //
8 // Authors:
9 // - Isis Agora Lovecruft <isis@patternsinthevoid.net>
10 // - Henry de Valence <hdevalence@hdevalence.ca>
11 
12 //! Field arithmetic modulo \\(p = 2\^{255} - 19\\).
13 //!
14 //! The `curve25519_dalek::field` module provides a type alias
15 //! `curve25519_dalek::field::FieldElement` to a field element type
16 //! defined in the `backend` module; either `FieldElement51` or
17 //! `FieldElement2625`.
18 //!
19 //! Field operations defined in terms of machine
20 //! operations, such as field multiplication or squaring, are defined in
21 //! the backend implementation.
22 //!
23 //! Field operations defined in terms of other field operations, such as
24 //! field inversion or square roots, are defined here.
25 
26 use core::cmp::{Eq, PartialEq};
27 
28 use subtle::ConditionallySelectable;
29 use subtle::ConditionallyNegatable;
30 use subtle::Choice;
31 use subtle::ConstantTimeEq;
32 
33 use constants;
34 use backend;
35 
36 #[cfg(feature = "fiat_u32_backend")]
37 pub use backend::serial::fiat_u32::field::*;
38 #[cfg(feature = "fiat_u64_backend")]
39 pub use backend::serial::fiat_u64::field::*;
40 /// A `FieldElement` represents an element of the field
41 /// \\( \mathbb Z / (2\^{255} - 19)\\).
42 ///
43 /// The `FieldElement` type is an alias for one of the platform-specific
44 /// implementations.
45 /// Using formally-verified field arithmetic from fiat-crypto
46 #[cfg(feature = "fiat_u32_backend")]
47 pub type FieldElement = backend::serial::fiat_u32::field::FieldElement2625;
48 #[cfg(feature = "fiat_u64_backend")]
49 pub type FieldElement = backend::serial::fiat_u64::field::FieldElement51;
50 
51 #[cfg(feature = "u64_backend")]
52 pub use backend::serial::u64::field::*;
53 /// A `FieldElement` represents an element of the field
54 /// \\( \mathbb Z / (2\^{255} - 19)\\).
55 ///
56 /// The `FieldElement` type is an alias for one of the platform-specific
57 /// implementations.
58 #[cfg(feature = "u64_backend")]
59 pub type FieldElement = backend::serial::u64::field::FieldElement51;
60 
61 #[cfg(feature = "u32_backend")]
62 pub use backend::serial::u32::field::*;
63 /// A `FieldElement` represents an element of the field
64 /// \\( \mathbb Z / (2\^{255} - 19)\\).
65 ///
66 /// The `FieldElement` type is an alias for one of the platform-specific
67 /// implementations.
68 #[cfg(feature = "u32_backend")]
69 pub type FieldElement = backend::serial::u32::field::FieldElement2625;
70 
71 impl Eq for FieldElement {}
72 
73 impl PartialEq for FieldElement {
74     fn eq(&self, other: &FieldElement) -> bool {
75         self.ct_eq(other).unwrap_u8() == 1u8
76     }
77 }
78 
79 impl ConstantTimeEq for FieldElement {
80     /// Test equality between two `FieldElement`s.  Since the
81     /// internal representation is not canonical, the field elements
82     /// are normalized to wire format before comparison.
83     fn ct_eq(&self, other: &FieldElement) -> Choice {
84         self.to_bytes().ct_eq(&other.to_bytes())
85     }
86 }
87 
88 impl FieldElement {
89     /// Determine if this `FieldElement` is negative, in the sense
90     /// used in the ed25519 paper: `x` is negative if the low bit is
91     /// set.
92     ///
93     /// # Return
94     ///
95     /// If negative, return `Choice(1)`.  Otherwise, return `Choice(0)`.
96     pub fn is_negative(&self) -> Choice {
97         let bytes = self.to_bytes();
98         (bytes[0] & 1).into()
99     }
100 
101     /// Determine if this `FieldElement` is zero.
102     ///
103     /// # Return
104     ///
105     /// If zero, return `Choice(1)`.  Otherwise, return `Choice(0)`.
106     pub fn is_zero(&self) -> Choice {
107         let zero = [0u8; 32];
108         let bytes = self.to_bytes();
109 
110         bytes.ct_eq(&zero)
111     }
112 
113     /// Compute (self^(2^250-1), self^11), used as a helper function
114     /// within invert() and pow22523().
115     fn pow22501(&self) -> (FieldElement, FieldElement) {
116         // Instead of managing which temporary variables are used
117         // for what, we define as many as we need and leave stack
118         // allocation to the compiler
119         //
120         // Each temporary variable t_i is of the form (self)^e_i.
121         // Squaring t_i corresponds to multiplying e_i by 2,
122         // so the pow2k function shifts e_i left by k places.
123         // Multiplying t_i and t_j corresponds to adding e_i + e_j.
124         //
125         // Temporary t_i                      Nonzero bits of e_i
126         //
127         let t0  = self.square();           // 1         e_0 = 2^1
128         let t1  = t0.square().square();    // 3         e_1 = 2^3
129         let t2  = self * &t1;              // 3,0       e_2 = 2^3 + 2^0
130         let t3  = &t0 * &t2;               // 3,1,0
131         let t4  = t3.square();             // 4,2,1
132         let t5  = &t2 * &t4;               // 4,3,2,1,0
133         let t6  = t5.pow2k(5);             // 9,8,7,6,5
134         let t7  = &t6 * &t5;               // 9,8,7,6,5,4,3,2,1,0
135         let t8  = t7.pow2k(10);            // 19..10
136         let t9  = &t8 * &t7;               // 19..0
137         let t10 = t9.pow2k(20);            // 39..20
138         let t11 = &t10 * &t9;              // 39..0
139         let t12 = t11.pow2k(10);           // 49..10
140         let t13 = &t12 * &t7;              // 49..0
141         let t14 = t13.pow2k(50);           // 99..50
142         let t15 = &t14 * &t13;             // 99..0
143         let t16 = t15.pow2k(100);          // 199..100
144         let t17 = &t16 * &t15;             // 199..0
145         let t18 = t17.pow2k(50);           // 249..50
146         let t19 = &t18 * &t13;             // 249..0
147 
148         (t19, t3)
149     }
150 
151     /// Given a slice of public `FieldElements`, replace each with its inverse.
152     ///
153     /// All input `FieldElements` **MUST** be nonzero.
154     #[cfg(feature = "alloc")]
155     pub fn batch_invert(inputs: &mut [FieldElement]) {
156         // Montgomery’s Trick and Fast Implementation of Masked AES
157         // Genelle, Prouff and Quisquater
158         // Section 3.2
159 
160         let n = inputs.len();
161         let mut scratch = vec![FieldElement::one(); n];
162 
163         // Keep an accumulator of all of the previous products
164         let mut acc = FieldElement::one();
165 
166         // Pass through the input vector, recording the previous
167         // products in the scratch space
168         for (input, scratch) in inputs.iter().zip(scratch.iter_mut()) {
169             *scratch = acc;
170             acc = &acc * input;
171         }
172 
173 	// acc is nonzero iff all inputs are nonzero
174         assert_eq!(acc.is_zero().unwrap_u8(), 0);
175 
176         // Compute the inverse of all products
177         acc = acc.invert();
178 
179         // Pass through the vector backwards to compute the inverses
180         // in place
181         for (input, scratch) in inputs.iter_mut().rev().zip(scratch.into_iter().rev()) {
182             let tmp = &acc * input;
183             *input = &acc * &scratch;
184             acc = tmp;
185         }
186     }
187 
188     /// Given a nonzero field element, compute its inverse.
189     ///
190     /// The inverse is computed as self^(p-2), since
191     /// x^(p-2)x = x^(p-1) = 1 (mod p).
192     ///
193     /// This function returns zero on input zero.
194     pub fn invert(&self) -> FieldElement {
195         // The bits of p-2 = 2^255 -19 -2 are 11010111111...11.
196         //
197         //                                 nonzero bits of exponent
198         let (t19, t3) = self.pow22501();   // t19: 249..0 ; t3: 3,1,0
199         let t20 = t19.pow2k(5);            // 254..5
200         let t21 = &t20 * &t3;              // 254..5,3,1,0
201 
202         t21
203     }
204 
205     /// Raise this field element to the power (p-5)/8 = 2^252 -3.
206     fn pow_p58(&self) -> FieldElement {
207         // The bits of (p-5)/8 are 101111.....11.
208         //
209         //                                 nonzero bits of exponent
210         let (t19, _) = self.pow22501();    // 249..0
211         let t20 = t19.pow2k(2);            // 251..2
212         let t21 = self * &t20;             // 251..2,0
213 
214         t21
215     }
216 
217     /// Given `FieldElements` `u` and `v`, compute either `sqrt(u/v)`
218     /// or `sqrt(i*u/v)` in constant time.
219     ///
220     /// This function always returns the nonnegative square root.
221     ///
222     /// # Return
223     ///
224     /// - `(Choice(1), +sqrt(u/v))  ` if `v` is nonzero and `u/v` is square;
225     /// - `(Choice(1), zero)        ` if `u` is zero;
226     /// - `(Choice(0), zero)        ` if `v` is zero and `u` is nonzero;
227     /// - `(Choice(0), +sqrt(i*u/v))` if `u/v` is nonsquare (so `i*u/v` is square).
228     ///
229     pub fn sqrt_ratio_i(u: &FieldElement, v: &FieldElement) -> (Choice, FieldElement) {
230         // Using the same trick as in ed25519 decoding, we merge the
231         // inversion, the square root, and the square test as follows.
232         //
233         // To compute sqrt(α), we can compute β = α^((p+3)/8).
234         // Then β^2 = ±α, so multiplying β by sqrt(-1) if necessary
235         // gives sqrt(α).
236         //
237         // To compute 1/sqrt(α), we observe that
238         //    1/β = α^(p-1 - (p+3)/8) = α^((7p-11)/8)
239         //                            = α^3 * (α^7)^((p-5)/8).
240         //
241         // We can therefore compute sqrt(u/v) = sqrt(u)/sqrt(v)
242         // by first computing
243         //    r = u^((p+3)/8) v^(p-1-(p+3)/8)
244         //      = u u^((p-5)/8) v^3 (v^7)^((p-5)/8)
245         //      = (uv^3) (uv^7)^((p-5)/8).
246         //
247         // If v is nonzero and u/v is square, then r^2 = ±u/v,
248         //                                     so vr^2 = ±u.
249         // If vr^2 =  u, then sqrt(u/v) = r.
250         // If vr^2 = -u, then sqrt(u/v) = r*sqrt(-1).
251         //
252         // If v is zero, r is also zero.
253 
254         let v3 = &v.square()  * v;
255         let v7 = &v3.square() * v;
256         let mut r = &(u * &v3) * &(u * &v7).pow_p58();
257         let check = v * &r.square();
258 
259         let i = &constants::SQRT_M1;
260 
261         let correct_sign_sqrt   = check.ct_eq(        u);
262         let flipped_sign_sqrt   = check.ct_eq(     &(-u));
263         let flipped_sign_sqrt_i = check.ct_eq(&(&(-u)*i));
264 
265         let r_prime = &constants::SQRT_M1 * &r;
266         r.conditional_assign(&r_prime, flipped_sign_sqrt | flipped_sign_sqrt_i);
267 
268         // Choose the nonnegative square root.
269         let r_is_negative = r.is_negative();
270         r.conditional_negate(r_is_negative);
271 
272         let was_nonzero_square = correct_sign_sqrt | flipped_sign_sqrt;
273 
274         (was_nonzero_square, r)
275     }
276 
277     /// Attempt to compute `sqrt(1/self)` in constant time.
278     ///
279     /// Convenience wrapper around `sqrt_ratio_i`.
280     ///
281     /// This function always returns the nonnegative square root.
282     ///
283     /// # Return
284     ///
285     /// - `(Choice(1), +sqrt(1/self))  ` if `self` is a nonzero square;
286     /// - `(Choice(0), zero)           ` if `self` is zero;
287     /// - `(Choice(0), +sqrt(i/self))  ` if `self` is a nonzero nonsquare;
288     ///
289     pub fn invsqrt(&self) -> (Choice, FieldElement) {
290         FieldElement::sqrt_ratio_i(&FieldElement::one(), self)
291     }
292 }
293 
294 #[cfg(test)]
295 mod test {
296     use field::*;
297     use subtle::ConditionallyNegatable;
298 
299     /// Random element a of GF(2^255-19), from Sage
300     /// a = 1070314506888354081329385823235218444233221\
301     ///     2228051251926706380353716438957572
302     static A_BYTES: [u8; 32] =
303         [ 0x04, 0xfe, 0xdf, 0x98, 0xa7, 0xfa, 0x0a, 0x68,
304           0x84, 0x92, 0xbd, 0x59, 0x08, 0x07, 0xa7, 0x03,
305           0x9e, 0xd1, 0xf6, 0xf2, 0xe1, 0xd9, 0xe2, 0xa4,
306           0xa4, 0x51, 0x47, 0x36, 0xf3, 0xc3, 0xa9, 0x17];
307 
308     /// Byte representation of a**2
309     static ASQ_BYTES: [u8; 32] =
310         [ 0x75, 0x97, 0x24, 0x9e, 0xe6, 0x06, 0xfe, 0xab,
311           0x24, 0x04, 0x56, 0x68, 0x07, 0x91, 0x2d, 0x5d,
312           0x0b, 0x0f, 0x3f, 0x1c, 0xb2, 0x6e, 0xf2, 0xe2,
313           0x63, 0x9c, 0x12, 0xba, 0x73, 0x0b, 0xe3, 0x62];
314 
315     /// Byte representation of 1/a
316     static AINV_BYTES: [u8; 32] =
317         [0x96, 0x1b, 0xcd, 0x8d, 0x4d, 0x5e, 0xa2, 0x3a,
318          0xe9, 0x36, 0x37, 0x93, 0xdb, 0x7b, 0x4d, 0x70,
319          0xb8, 0x0d, 0xc0, 0x55, 0xd0, 0x4c, 0x1d, 0x7b,
320          0x90, 0x71, 0xd8, 0xe9, 0xb6, 0x18, 0xe6, 0x30];
321 
322     /// Byte representation of a^((p-5)/8)
323     static AP58_BYTES: [u8; 32] =
324         [0x6a, 0x4f, 0x24, 0x89, 0x1f, 0x57, 0x60, 0x36,
325          0xd0, 0xbe, 0x12, 0x3c, 0x8f, 0xf5, 0xb1, 0x59,
326          0xe0, 0xf0, 0xb8, 0x1b, 0x20, 0xd2, 0xb5, 0x1f,
327          0x15, 0x21, 0xf9, 0xe3, 0xe1, 0x61, 0x21, 0x55];
328 
329     #[test]
330     fn a_mul_a_vs_a_squared_constant() {
331         let a = FieldElement::from_bytes(&A_BYTES);
332         let asq = FieldElement::from_bytes(&ASQ_BYTES);
333         assert_eq!(asq, &a * &a);
334     }
335 
336     #[test]
337     fn a_square_vs_a_squared_constant() {
338         let a = FieldElement::from_bytes(&A_BYTES);
339         let asq = FieldElement::from_bytes(&ASQ_BYTES);
340         assert_eq!(asq, a.square());
341     }
342 
343     #[test]
344     fn a_square2_vs_a_squared_constant() {
345         let a = FieldElement::from_bytes(&A_BYTES);
346         let asq = FieldElement::from_bytes(&ASQ_BYTES);
347         assert_eq!(a.square2(), &asq+&asq);
348     }
349 
350     #[test]
351     fn a_invert_vs_inverse_of_a_constant() {
352         let a    = FieldElement::from_bytes(&A_BYTES);
353         let ainv = FieldElement::from_bytes(&AINV_BYTES);
354         let should_be_inverse = a.invert();
355         assert_eq!(ainv, should_be_inverse);
356         assert_eq!(FieldElement::one(), &a * &should_be_inverse);
357     }
358 
359     #[test]
360     fn batch_invert_a_matches_nonbatched() {
361         let a    = FieldElement::from_bytes(&A_BYTES);
362         let ap58 = FieldElement::from_bytes(&AP58_BYTES);
363         let asq  = FieldElement::from_bytes(&ASQ_BYTES);
364         let ainv = FieldElement::from_bytes(&AINV_BYTES);
365         let a2   = &a + &a;
366         let a_list = vec![a, ap58, asq, ainv, a2];
367         let mut ainv_list = a_list.clone();
368         FieldElement::batch_invert(&mut ainv_list[..]);
369         for i in 0..5 {
370             assert_eq!(a_list[i].invert(), ainv_list[i]);
371         }
372     }
373 
374     #[test]
375     fn sqrt_ratio_behavior() {
376         let zero = FieldElement::zero();
377         let one = FieldElement::one();
378         let i = constants::SQRT_M1;
379         let two = &one + &one; // 2 is nonsquare mod p.
380         let four = &two + &two; // 4 is square mod p.
381 
382         // 0/0 should return (1, 0) since u is 0
383         let (choice, sqrt) = FieldElement::sqrt_ratio_i(&zero, &zero);
384         assert_eq!(choice.unwrap_u8(), 1);
385         assert_eq!(sqrt, zero);
386         assert_eq!(sqrt.is_negative().unwrap_u8(), 0);
387 
388         // 1/0 should return (0, 0) since v is 0, u is nonzero
389         let (choice, sqrt) = FieldElement::sqrt_ratio_i(&one, &zero);
390         assert_eq!(choice.unwrap_u8(), 0);
391         assert_eq!(sqrt, zero);
392         assert_eq!(sqrt.is_negative().unwrap_u8(), 0);
393 
394         // 2/1 is nonsquare, so we expect (0, sqrt(i*2))
395         let (choice, sqrt) = FieldElement::sqrt_ratio_i(&two, &one);
396         assert_eq!(choice.unwrap_u8(), 0);
397         assert_eq!(sqrt.square(), &two * &i);
398         assert_eq!(sqrt.is_negative().unwrap_u8(), 0);
399 
400         // 4/1 is square, so we expect (1, sqrt(4))
401         let (choice, sqrt) = FieldElement::sqrt_ratio_i(&four, &one);
402         assert_eq!(choice.unwrap_u8(), 1);
403         assert_eq!(sqrt.square(), four);
404         assert_eq!(sqrt.is_negative().unwrap_u8(), 0);
405 
406         // 1/4 is square, so we expect (1, 1/sqrt(4))
407         let (choice, sqrt) = FieldElement::sqrt_ratio_i(&one, &four);
408         assert_eq!(choice.unwrap_u8(), 1);
409         assert_eq!(&sqrt.square() * &four, one);
410         assert_eq!(sqrt.is_negative().unwrap_u8(), 0);
411     }
412 
413     #[test]
414     fn a_p58_vs_ap58_constant() {
415         let a    = FieldElement::from_bytes(&A_BYTES);
416         let ap58 = FieldElement::from_bytes(&AP58_BYTES);
417         assert_eq!(ap58, a.pow_p58());
418     }
419 
420     #[test]
421     fn equality() {
422         let a    = FieldElement::from_bytes(&A_BYTES);
423         let ainv = FieldElement::from_bytes(&AINV_BYTES);
424         assert!(a == a);
425         assert!(a != ainv);
426     }
427 
428     /// Notice that the last element has the high bit set, which
429     /// should be ignored
430     static B_BYTES: [u8;32] =
431         [113, 191, 169, 143,  91, 234, 121,  15,
432          241, 131, 217,  36, 230, 101,  92, 234,
433            8, 208, 170, 251,  97, 127,  70, 210,
434           58,  23, 166,  87, 240, 169, 184, 178];
435 
436     #[test]
437     fn from_bytes_highbit_is_ignored() {
438         let mut cleared_bytes = B_BYTES;
439         cleared_bytes[31] &= 127u8;
440         let with_highbit_set    = FieldElement::from_bytes(&B_BYTES);
441         let without_highbit_set = FieldElement::from_bytes(&cleared_bytes);
442         assert_eq!(without_highbit_set, with_highbit_set);
443     }
444 
445     #[test]
446     fn conditional_negate() {
447         let       one = FieldElement::one();
448         let minus_one = FieldElement::minus_one();
449         let mut x = one;
450         x.conditional_negate(Choice::from(1));
451         assert_eq!(x, minus_one);
452         x.conditional_negate(Choice::from(0));
453         assert_eq!(x, minus_one);
454         x.conditional_negate(Choice::from(1));
455         assert_eq!(x, one);
456     }
457 
458     #[test]
459     fn encoding_is_canonical() {
460         // Encode 1 wrongly as 1 + (2^255 - 19) = 2^255 - 18
461         let one_encoded_wrongly_bytes: [u8;32] = [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];
462         // Decode to a field element
463         let one = FieldElement::from_bytes(&one_encoded_wrongly_bytes);
464         // .. then check that the encoding is correct
465         let one_bytes = one.to_bytes();
466         assert_eq!(one_bytes[0], 1);
467         for i in 1..32 {
468             assert_eq!(one_bytes[i], 0);
469         }
470     }
471 
472     #[test]
473     fn batch_invert_empty() {
474         FieldElement::batch_invert(&mut []);
475     }
476 }
477