p256/arithmetic/field/
field64.rs

1//! 64-bit secp256r1 field element algorithms.
2
3use elliptic_curve::bigint::{Limb, U256, modular::ConstMontyParams};
4
5const MODULUS: &[Limb; 4] = super::FieldParams::PARAMS.modulus().as_ref().as_limbs();
6
7pub(super) const fn add(a: &U256, b: &U256) -> U256 {
8    let a = a.as_limbs();
9    let b = b.as_limbs();
10
11    // Bit 256 of p is set, so addition can result in five words.
12    let (w0, carry) = a[0].carrying_add(b[0], Limb::ZERO);
13    let (w1, carry) = a[1].carrying_add(b[1], carry);
14    let (w2, carry) = a[2].carrying_add(b[2], carry);
15    let (w3, w4) = a[3].carrying_add(b[3], carry);
16
17    // Attempt to subtract the modulus, to ensure the result is in the field
18    let (result, _) = sub_inner(
19        [w0, w1, w2, w3, w4],
20        [MODULUS[0], MODULUS[1], MODULUS[2], MODULUS[3], Limb::ZERO],
21    );
22    U256::new([result[0], result[1], result[2], result[3]])
23}
24
25pub(super) const fn sub(a: &U256, b: &U256) -> U256 {
26    let a = a.as_limbs();
27    let b = b.as_limbs();
28
29    let (result, _) = sub_inner(
30        [a[0], a[1], a[2], a[3], Limb::ZERO],
31        [b[0], b[1], b[2], b[3], Limb::ZERO],
32    );
33    U256::new([result[0], result[1], result[2], result[3]])
34}
35
36#[inline]
37pub(super) const fn to_canonical(a: &U256) -> U256 {
38    montgomery_reduce(a, &U256::ZERO)
39}
40
41/// Montgomery Reduction
42///
43/// The general algorithm is:
44/// ```text
45/// A <- input (2n b-limbs)
46/// for i in 0..n {
47///     k <- A[i] p' mod b
48///     A <- A + k p b^i
49/// }
50/// A <- A / b^n
51/// if A >= p {
52///     A <- A - p
53/// }
54/// ```
55///
56/// For secp256r1, with a 64-bit arithmetic, we have the following
57/// simplifications:
58///
59/// - `p'` is 1, so our multiplicand is simply the first limb of the intermediate A.
60///
61/// - The first limb of p is 2^64 - 1; multiplications by this limb can be simplified
62///   to a shift and subtraction:
63///   ```text
64///       a_i * (2^64 - 1) = a_i * 2^64 - a_i = (a_i << 64) - a_i
65///   ```
66///   However, because `p' = 1`, the first limb of p is multiplied by limb i of the
67///   intermediate A and then immediately added to that same limb, so we simply
68///   initialize the carry to limb i of the intermediate.
69///
70/// - The third limb of p is zero, so we can ignore any multiplications by it and just
71///   add the carry.
72///
73/// References:
74/// - Handbook of Applied Cryptography, Chapter 14
75///   Algorithm 14.32
76///   <http://cacr.uwaterloo.ca/hac/about/chap14.pdf>
77///
78/// - Efficient and Secure Elliptic Curve Cryptography Implementation of Curve P-256
79///   Algorithm 7) Montgomery Word-by-Word Reduction
80///   <https://csrc.nist.gov/csrc/media/events/workshop-on-elliptic-curve-cryptography-standards/documents/papers/session6-adalier-mehmet.pdf>
81#[inline]
82#[allow(clippy::too_many_arguments)]
83pub(super) const fn montgomery_reduce(lo: &U256, hi: &U256) -> U256 {
84    let lo = lo.as_limbs();
85    let hi = hi.as_limbs();
86
87    let a0 = lo[0];
88    let a1 = lo[1];
89    let a2 = lo[2];
90    let a3 = lo[3];
91    let a4 = hi[0];
92    let a5 = hi[1];
93    let a6 = hi[2];
94    let a7 = hi[3];
95
96    let (a1, carry) = a0.carrying_mul_add(MODULUS[1], a1, a0);
97    let (a2, carry) = a2.carrying_add(Limb::ZERO, carry);
98    let (a3, carry) = a0.carrying_mul_add(MODULUS[3], a3, carry);
99    let (a4, carry2) = a4.carrying_add(Limb::ZERO, carry);
100
101    let (a2, carry) = a1.carrying_mul_add(MODULUS[1], a2, a1);
102    let (a3, carry) = a3.carrying_add(Limb::ZERO, carry);
103    let (a4, carry) = a1.carrying_mul_add(MODULUS[3], a4, carry);
104    let (a5, carry2) = a5.carrying_add(carry2, carry);
105
106    let (a3, carry) = a2.carrying_mul_add(MODULUS[1], a3, a2);
107    let (a4, carry) = a4.carrying_add(Limb::ZERO, carry);
108    let (a5, carry) = a2.carrying_mul_add(MODULUS[3], a5, carry);
109    let (a6, carry2) = a6.carrying_add(carry2, carry);
110
111    let (a4, carry) = a3.carrying_mul_add(MODULUS[1], a4, a3);
112    let (a5, carry) = a5.carrying_add(Limb::ZERO, carry);
113    let (a6, carry) = a3.carrying_mul_add(MODULUS[3], a6, carry);
114    let (a7, a8) = a7.carrying_add(carry2, carry);
115
116    // Result may be within MODULUS of the correct value
117    let (result, _) = sub_inner(
118        [a4, a5, a6, a7, a8],
119        [MODULUS[0], MODULUS[1], MODULUS[2], MODULUS[3], Limb::ZERO],
120    );
121
122    U256::new([result[0], result[1], result[2], result[3]])
123}
124
125#[inline]
126#[allow(clippy::too_many_arguments)]
127const fn sub_inner(l: [Limb; 5], r: [Limb; 5]) -> ([Limb; 4], Limb) {
128    let (w0, borrow) = l[0].borrowing_sub(r[0], Limb::ZERO);
129    let (w1, borrow) = l[1].borrowing_sub(r[1], borrow);
130    let (w2, borrow) = l[2].borrowing_sub(r[2], borrow);
131    let (w3, borrow) = l[3].borrowing_sub(r[3], borrow);
132    let (_, borrow) = l[4].borrowing_sub(r[4], borrow);
133
134    // If underflow occurred on the final limb, borrow = 0xfff...fff, otherwise
135    // borrow = 0x000...000. Thus, we use it as a mask to conditionally add the
136    // modulus.
137
138    let (w0, carry) = w0.carrying_add(MODULUS[0].bitand(borrow), Limb::ZERO);
139    let (w1, carry) = w1.carrying_add(MODULUS[1].bitand(borrow), carry);
140    let (w2, carry) = w2.carrying_add(MODULUS[2].bitand(borrow), carry);
141    let (w3, _) = w3.carrying_add(MODULUS[3].bitand(borrow), carry);
142
143    ([w0, w1, w2, w3], borrow)
144}
p256/arithmetic/field/field64.rs

p256/arithmetic/field/
field64.rs
