p256/arithmetic/
field.rs

Help
1//! Field arithmetic modulo p = 2^{224}(2^{32} − 1) + 2^{192} + 2^{96} − 1
2
3#![allow(clippy::assign_op_pattern, clippy::op_ref)]
4
5#[cfg_attr(target_pointer_width = "32", path = "field/field32.rs")]
6#[cfg_attr(target_pointer_width = "64", path = "field/field64.rs")]
7mod field_impl;
8
9use self::field_impl::*;
10use crate::{FieldBytes, NistP256};
11use core::{
12    fmt::{self, Debug},
13    iter::{Product, Sum},
14    ops::{AddAssign, Mul, MulAssign, Neg, SubAssign},
15};
16use elliptic_curve::{
17    bigint::U256,
18    ff::PrimeField,
19    subtle::{Choice, ConstantTimeEq, CtOption},
20};
21
22/// Field modulus serialized as hex.
23/// p = 2^{224}(2^{32} − 1) + 2^{192} + 2^{96} − 1
24const MODULUS_HEX: &str = "ffffffff00000001000000000000000000000000ffffffffffffffffffffffff";
25
26/// Constant representing the modulus.
27pub const MODULUS: U256 = U256::from_be_hex(MODULUS_HEX);
28
29/// R^2 = 2^512 mod p
30const R_2: U256 =
31    U256::from_be_hex("00000004fffffffdfffffffffffffffefffffffbffffffff0000000000000003");
32
33/// An element in the finite field modulo p = 2^{224}(2^{32} − 1) + 2^{192} + 2^{96} − 1.
34///
35/// The internal representation is in little-endian order. Elements are always in
36/// Montgomery form; i.e., FieldElement(a) = aR mod p, with R = 2^256.
37#[derive(Clone, Copy)]
38pub struct FieldElement(pub(crate) U256);
39
40primeorder::impl_mont_field_element!(
41    NistP256,
42    FieldElement,
43    FieldBytes,
44    U256,
45    MODULUS,
46    Fe,
47    fe_from_montgomery,
48    fe_to_montgomery,
49    fe_add,
50    fe_sub,
51    fe_mul,
52    fe_neg,
53    fe_square
54);
55
56impl FieldElement {
57    /// Returns the multiplicative inverse of self, if self is non-zero.
58    pub fn invert(&self) -> CtOption<Self> {
59        CtOption::new(self.invert_unchecked(), !self.is_zero())
60    }
61
62    /// Returns the multiplicative inverse of self.
63    ///
64    /// Does not check that self is non-zero.
65    const fn invert_unchecked(&self) -> Self {
66        // We need to find b such that b * a ≡ 1 mod p. As we are in a prime
67        // field, we can apply Fermat's Little Theorem:
68        //
69        //    a^p         ≡ a mod p
70        //    a^(p-1)     ≡ 1 mod p
71        //    a^(p-2) * a ≡ 1 mod p
72        //
73        // Thus inversion can be implemented with a single exponentiation.
74
75        let t111 = self.multiply(&self.multiply(&self.square()).square());
76        let t111111 = t111.multiply(&t111.sqn(3));
77        let x15 = t111111.sqn(6).multiply(&t111111).sqn(3).multiply(&t111);
78        let x16 = x15.square().multiply(self);
79        let i53 = x16.sqn(16).multiply(&x16).sqn(15);
80        let x47 = x15.multiply(&i53);
81        x47.multiply(&i53.sqn(17).multiply(self).sqn(143).multiply(&x47).sqn(47))
82            .sqn(2)
83            .multiply(self)
84    }
85
86    /// Returns the square root of self mod p, or `None` if no square root exists.
87    pub fn sqrt(&self) -> CtOption<Self> {
88        // We need to find alpha such that alpha^2 = beta mod p. For secp256r1,
89        // p ≡ 3 mod 4. By Euler's Criterion, beta^(p-1)/2 ≡ 1 mod p. So:
90        //
91        //     alpha^2 = beta beta^((p - 1) / 2) mod p ≡ beta^((p + 1) / 2) mod p
92        //     alpha = ± beta^((p + 1) / 4) mod p
93        //
94        // Thus sqrt can be implemented with a single exponentiation.
95
96        let t11 = self.mul(&self.square());
97        let t1111 = t11.mul(&t11.sqn(2));
98        let t11111111 = t1111.mul(&t1111.sqn(4));
99        let x16 = t11111111.sqn(8).mul(&t11111111);
100        let sqrt = x16
101            .sqn(16)
102            .mul(&x16)
103            .sqn(32)
104            .mul(self)
105            .sqn(96)
106            .mul(self)
107            .sqn(94);
108
109        CtOption::new(
110            sqrt,
111            (&sqrt * &sqrt).ct_eq(self), // Only return Some if it's the square root.
112        )
113    }
114
115    /// Returns self^(2^n) mod p
116    const fn sqn(&self, n: usize) -> Self {
117        let mut x = *self;
118        let mut i = 0;
119        while i < n {
120            x = x.square();
121            i += 1;
122        }
123        x
124    }
125}
126
127impl PrimeField for FieldElement {
128    type Repr = FieldBytes;
129
130    const MODULUS: &'static str = MODULUS_HEX;
131    const NUM_BITS: u32 = 256;
132    const CAPACITY: u32 = 255;
133    const TWO_INV: Self = Self::from_u64(2).invert_unchecked();
134    const MULTIPLICATIVE_GENERATOR: Self = Self::from_u64(6);
135    const S: u32 = 1;
136    const ROOT_OF_UNITY: Self =
137        Self::from_hex("ffffffff00000001000000000000000000000000fffffffffffffffffffffffe");
138    const ROOT_OF_UNITY_INV: Self = Self::ROOT_OF_UNITY.invert_unchecked();
139    const DELTA: Self = Self::from_u64(36);
140
141    #[inline]
142    fn from_repr(bytes: FieldBytes) -> CtOption<Self> {
143        Self::from_bytes(&bytes)
144    }
145
146    #[inline]
147    fn to_repr(&self) -> FieldBytes {
148        self.to_bytes()
149    }
150
151    #[inline]
152    fn is_odd(&self) -> Choice {
153        self.is_odd()
154    }
155}
156
157impl Debug for FieldElement {
158    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
159        write!(f, "FieldElement(0x{:X})", &self.0)
160    }
161}
162
163#[cfg(test)]
164mod tests {
165    use super::FieldElement;
166    use crate::{test_vectors::field::DBL_TEST_VECTORS, FieldBytes};
167    use elliptic_curve::{bigint::U256, ff::PrimeField};
168    use primeorder::{
169        impl_field_identity_tests, impl_field_invert_tests, impl_field_sqrt_tests,
170        impl_primefield_tests,
171    };
172    use proptest::{num, prelude::*};
173
174    /// t = (modulus - 1) >> S
175    const T: [u64; 4] = [
176        0xffffffffffffffff,
177        0x000000007fffffff,
178        0x8000000000000000,
179        0x7fffffff80000000,
180    ];
181
182    impl_field_identity_tests!(FieldElement);
183    impl_field_invert_tests!(FieldElement);
184    impl_field_sqrt_tests!(FieldElement);
185    impl_primefield_tests!(FieldElement, T);
186
187    #[test]
188    fn from_bytes() {
189        assert_eq!(
190            FieldElement::from_bytes(&FieldBytes::default()).unwrap(),
191            FieldElement::ZERO
192        );
193        assert_eq!(
194            FieldElement::from_bytes(
195                &[
196                    0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
197                    0, 0, 0, 0, 0, 1
198                ]
199                .into()
200            )
201            .unwrap(),
202            FieldElement::ONE
203        );
204        assert!(bool::from(
205            FieldElement::from_bytes(&[0xff; 32].into()).is_none()
206        ));
207    }
208
209    #[test]
210    fn to_bytes() {
211        assert_eq!(FieldElement::ZERO.to_bytes(), FieldBytes::default());
212        assert_eq!(
213            FieldElement::ONE.to_bytes(),
214            [
215                0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
216                0, 0, 0, 1
217            ]
218            .into()
219        );
220    }
221
222    #[test]
223    fn repeated_add() {
224        let mut r = FieldElement::ONE;
225        for i in 0..DBL_TEST_VECTORS.len() {
226            assert_eq!(r.to_bytes(), DBL_TEST_VECTORS[i].into());
227            r = r + &r;
228        }
229    }
230
231    #[test]
232    fn repeated_double() {
233        let mut r = FieldElement::ONE;
234        for i in 0..DBL_TEST_VECTORS.len() {
235            assert_eq!(r.to_bytes(), DBL_TEST_VECTORS[i].into());
236            r = r.double();
237        }
238    }
239
240    #[test]
241    fn repeated_mul() {
242        let mut r = FieldElement::ONE;
243        let two = r + &r;
244        for i in 0..DBL_TEST_VECTORS.len() {
245            assert_eq!(r.to_bytes(), DBL_TEST_VECTORS[i].into());
246            r = r * &two;
247        }
248    }
249
250    #[test]
251    fn negation() {
252        let two = FieldElement::ONE.double();
253        let neg_two = -two;
254        assert_eq!(two + &neg_two, FieldElement::ZERO);
255        assert_eq!(-neg_two, two);
256    }
257
258    #[test]
259    fn pow_vartime() {
260        let one = FieldElement::ONE;
261        let two = one + &one;
262        let four = two.square();
263        assert_eq!(two.pow_vartime(&[2, 0, 0, 0]), four);
264    }
265
266    proptest! {
267        /// This checks behaviour well within the field ranges, because it doesn't set the
268        /// highest limb.
269        #[cfg(target_pointer_width = "32")]
270        #[test]
271        fn add_then_sub(
272            a0 in num::u32::ANY,
273            a1 in num::u32::ANY,
274            a2 in num::u32::ANY,
275            a3 in num::u32::ANY,
276            a4 in num::u32::ANY,
277            a5 in num::u32::ANY,
278            a6 in num::u32::ANY,
279            b0 in num::u32::ANY,
280            b1 in num::u32::ANY,
281            b2 in num::u32::ANY,
282            b3 in num::u32::ANY,
283            b4 in num::u32::ANY,
284            b5 in num::u32::ANY,
285            b6 in num::u32::ANY,
286        ) {
287            let a = FieldElement(U256::from_words([a0, a1, a2, a3, a4, a5, a6, 0]));
288            let b = FieldElement(U256::from_words([b0, b1, b2, b3, b4, b5, b6, 0]));
289            assert_eq!(a.add(&b).sub(&a), b);
290        }
291
292        /// This checks behaviour well within the field ranges, because it doesn't set the
293        /// highest limb.
294        #[cfg(target_pointer_width = "64")]
295        #[test]
296        fn add_then_sub(
297            a0 in num::u64::ANY,
298            a1 in num::u64::ANY,
299            a2 in num::u64::ANY,
300            b0 in num::u64::ANY,
301            b1 in num::u64::ANY,
302            b2 in num::u64::ANY,
303        ) {
304            let a = FieldElement(U256::from_words([a0, a1, a2, 0]));
305            let b = FieldElement(U256::from_words([b0, b1, b2, 0]));
306            assert_eq!(a.add(&b).sub(&a), b);
307        }
308    }
309}
p256/arithmetic/field.rs

p256/arithmetic/
field.rs
