p256/arithmetic/field/
field64.rs

1//! 64-bit secp256r1 base field implementation
2
3use super::{MODULUS, R_2};
4use crate::arithmetic::util::{adc, mac, sbb};
5
6/// Raw field element.
7pub type Fe = [u64; 4];
8
9/// Translate a field element out of the Montgomery domain.
10#[inline]
11pub const fn fe_from_montgomery(w: &Fe) -> Fe {
12    montgomery_reduce(&[w[0], w[1], w[2], w[3], 0, 0, 0, 0])
13}
14
15/// Translate a field element into the Montgomery domain.
16#[inline]
17pub const fn fe_to_montgomery(w: &Fe) -> Fe {
18    fe_mul(w, R_2.as_words())
19}
20
21/// Returns `a + b mod p`.
22pub const fn fe_add(a: &Fe, b: &Fe) -> Fe {
23    // Bit 256 of p is set, so addition can result in five words.
24    let (w0, carry) = adc(a[0], b[0], 0);
25    let (w1, carry) = adc(a[1], b[1], carry);
26    let (w2, carry) = adc(a[2], b[2], carry);
27    let (w3, w4) = adc(a[3], b[3], carry);
28
29    // Attempt to subtract the modulus, to ensure the result is in the field.
30    let modulus = MODULUS.as_words();
31    sub_inner(
32        &[w0, w1, w2, w3, w4],
33        &[modulus[0], modulus[1], modulus[2], modulus[3], 0],
34    )
35}
36
37/// Returns `a - b mod p`.
38pub const fn fe_sub(a: &Fe, b: &Fe) -> Fe {
39    sub_inner(&[a[0], a[1], a[2], a[3], 0], &[b[0], b[1], b[2], b[3], 0])
40}
41
42/// Returns `a * b mod p`.
43pub const fn fe_mul(a: &Fe, b: &Fe) -> Fe {
44    let (w0, carry) = mac(0, a[0], b[0], 0);
45    let (w1, carry) = mac(0, a[0], b[1], carry);
46    let (w2, carry) = mac(0, a[0], b[2], carry);
47    let (w3, w4) = mac(0, a[0], b[3], carry);
48
49    let (w1, carry) = mac(w1, a[1], b[0], 0);
50    let (w2, carry) = mac(w2, a[1], b[1], carry);
51    let (w3, carry) = mac(w3, a[1], b[2], carry);
52    let (w4, w5) = mac(w4, a[1], b[3], carry);
53
54    let (w2, carry) = mac(w2, a[2], b[0], 0);
55    let (w3, carry) = mac(w3, a[2], b[1], carry);
56    let (w4, carry) = mac(w4, a[2], b[2], carry);
57    let (w5, w6) = mac(w5, a[2], b[3], carry);
58
59    let (w3, carry) = mac(w3, a[3], b[0], 0);
60    let (w4, carry) = mac(w4, a[3], b[1], carry);
61    let (w5, carry) = mac(w5, a[3], b[2], carry);
62    let (w6, w7) = mac(w6, a[3], b[3], carry);
63
64    montgomery_reduce(&[w0, w1, w2, w3, w4, w5, w6, w7])
65}
66
67/// Returns `-w mod p`.
68pub const fn fe_neg(w: &Fe) -> Fe {
69    fe_sub(&[0, 0, 0, 0], w)
70}
71
72/// Returns `w * w mod p`.
73pub const fn fe_square(w: &Fe) -> Fe {
74    fe_mul(w, w)
75}
76
77/// Montgomery Reduction
78///
79/// The general algorithm is:
80/// ```text
81/// A <- input (2n b-limbs)
82/// for i in 0..n {
83///     k <- A[i] p' mod b
84///     A <- A + k p b^i
85/// }
86/// A <- A / b^n
87/// if A >= p {
88///     A <- A - p
89/// }
90/// ```
91///
92/// For secp256r1, we have the following simplifications:
93///
94/// - `p'` is 1, so our multiplicand is simply the first limb of the intermediate A.
95///
96/// - The first limb of p is 2^64 - 1; multiplications by this limb can be simplified
97///   to a shift and subtraction:
98///   ```text
99///       a_i * (2^64 - 1) = a_i * 2^64 - a_i = (a_i << 64) - a_i
100///   ```
101///   However, because `p' = 1`, the first limb of p is multiplied by limb i of the
102///   intermediate A and then immediately added to that same limb, so we simply
103///   initialize the carry to limb i of the intermediate.
104///
105/// - The third limb of p is zero, so we can ignore any multiplications by it and just
106///   add the carry.
107///
108/// References:
109/// - Handbook of Applied Cryptography, Chapter 14
110///   Algorithm 14.32
111///   http://cacr.uwaterloo.ca/hac/about/chap14.pdf
112///
113/// - Efficient and Secure Elliptic Curve Cryptography Implementation of Curve P-256
114///   Algorithm 7) Montgomery Word-by-Word Reduction
115///   https://csrc.nist.gov/csrc/media/events/workshop-on-elliptic-curve-cryptography-standards/documents/papers/session6-adalier-mehmet.pdf
116#[inline]
117#[allow(clippy::too_many_arguments)]
118const fn montgomery_reduce(r: &[u64; 8]) -> Fe {
119    let r0 = r[0];
120    let r1 = r[1];
121    let r2 = r[2];
122    let r3 = r[3];
123    let r4 = r[4];
124    let r5 = r[5];
125    let r6 = r[6];
126    let r7 = r[7];
127    let modulus = MODULUS.as_words();
128
129    let (r1, carry) = mac(r1, r0, modulus[1], r0);
130    let (r2, carry) = adc(r2, 0, carry);
131    let (r3, carry) = mac(r3, r0, modulus[3], carry);
132    let (r4, carry2) = adc(r4, 0, carry);
133
134    let (r2, carry) = mac(r2, r1, modulus[1], r1);
135    let (r3, carry) = adc(r3, 0, carry);
136    let (r4, carry) = mac(r4, r1, modulus[3], carry);
137    let (r5, carry2) = adc(r5, carry2, carry);
138
139    let (r3, carry) = mac(r3, r2, modulus[1], r2);
140    let (r4, carry) = adc(r4, 0, carry);
141    let (r5, carry) = mac(r5, r2, modulus[3], carry);
142    let (r6, carry2) = adc(r6, carry2, carry);
143
144    let (r4, carry) = mac(r4, r3, modulus[1], r3);
145    let (r5, carry) = adc(r5, 0, carry);
146    let (r6, carry) = mac(r6, r3, modulus[3], carry);
147    let (r7, r8) = adc(r7, carry2, carry);
148
149    // Result may be within MODULUS of the correct value
150    sub_inner(
151        &[r4, r5, r6, r7, r8],
152        &[modulus[0], modulus[1], modulus[2], modulus[3], 0],
153    )
154}
155
156#[inline]
157#[allow(clippy::too_many_arguments)]
158const fn sub_inner(l: &[u64; 5], r: &[u64; 5]) -> Fe {
159    let (w0, borrow) = sbb(l[0], r[0], 0);
160    let (w1, borrow) = sbb(l[1], r[1], borrow);
161    let (w2, borrow) = sbb(l[2], r[2], borrow);
162    let (w3, borrow) = sbb(l[3], r[3], borrow);
163    let (_, borrow) = sbb(l[4], r[4], borrow);
164
165    // If underflow occurred on the final limb, borrow = 0xfff...fff, otherwise
166    // borrow = 0x000...000. Thus, we use it as a mask to conditionally add the
167    // modulus.
168    let modulus = MODULUS.as_words();
169    let (w0, carry) = adc(w0, modulus[0] & borrow, 0);
170    let (w1, carry) = adc(w1, modulus[1] & borrow, carry);
171    let (w2, carry) = adc(w2, modulus[2] & borrow, carry);
172    let (w3, _) = adc(w3, modulus[3] & borrow, carry);
173
174    [w0, w1, w2, w3]
175}
p256/arithmetic/field/field64.rs

p256/arithmetic/field/
field64.rs
