dcrypt_algorithms/ec/p192/field.rs
1//! P-192 field arithmetic implementation
2
3use crate::ec::p192::constants::P192_FIELD_ELEMENT_SIZE;
4use crate::error::{Error, Result};
5use subtle::{Choice, ConditionallySelectable};
6
7/// Number of 32‐bit limbs for a P-192 field element (6 × 32 = 192 bits)
8const NLIMBS: usize = 6;
9
10/// NIST P-192 coefficient b (big-endian, 24 bytes)
11pub const B: [u8; 24] = [
12 0x64, 0x21, 0x05, 0x19, 0xE5, 0x9C, 0x80, 0xE7, 0x0F, 0xA7, 0xE9, 0xAB, 0x72, 0x24, 0x30, 0x49,
13 0xFE, 0xB8, 0xDE, 0xEC, 0xC1, 0x46, 0xB9, 0xB1,
14];
15
16/// P-192 field element representing values in 𝔽ₚ, where
17/// p = 2¹⁹² − 2⁶⁴ − 1.
18/// Internally stored as 6 little‐endian 32‐bit limbs.
19#[derive(Clone, Debug, PartialEq, Eq)]
20pub struct FieldElement(pub(crate) [u32; NLIMBS]);
21
22impl FieldElement {
23 /* ---------------------------------------------------------------- */
24 /* NIST P-192 Field Constants (little‐endian 32‐bit limbs) */
25 /* ---------------------------------------------------------------- */
26
27 /// p = 0xFFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE FFFFFFFF FFFFFFFF
28 /// which equals 2¹⁹² − 2⁶⁴ − 1.
29 /// Stored as six 32-bit words, little‐endian.
30 /// Big‐endian words: [FFFFFFFF, FFFFFFFF, FFFFFFFF, FFFFFFFE, FFFFFFFF, FFFFFFFF]
31 /// Little‐endian limbs become: [FFFFFFFF, FFFFFFFF, FFFFFFFE, FFFFFFFF, FFFFFFFF, FFFFFFFF]
32 pub(crate) const MOD_LIMBS: [u32; NLIMBS] = [
33 0xFFFFFFFF, // least significant
34 0xFFFFFFFF, 0xFFFFFFFE, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, // most significant
35 ];
36
37 /// a = −3 mod p = p − 3 = 2¹⁹² − 2⁶⁴ − 4.
38 /// In limbs that is:
39 /// subtract 3 from the least‐significant limb 0xFFFFFFFF → 0xFFFFFFFC.
40 pub(crate) const A_M3: [u32; NLIMBS] = [
41 0xFFFFFFFC, 0xFFFFFFFF, 0xFFFFFFFE, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF,
42 ];
43
44 /* ================================================================= */
45 /* Tiny helpers */
46 /* ================================================================= */
47
48 /// Build a field element from a small literal (`0 ≤ n < 2³²`)
49 #[inline]
50 pub fn from_u32(n: u32) -> Self {
51 let mut limbs = [0u32; NLIMBS];
52 limbs[0] = n;
53 FieldElement(limbs)
54 }
55
56 /// The additive identity: 0
57 #[inline]
58 pub fn zero() -> Self {
59 FieldElement([0u32; NLIMBS])
60 }
61
62 /// The multiplicative identity: 1
63 #[inline]
64 pub fn one() -> Self {
65 let mut limbs = [0u32; NLIMBS];
66 limbs[0] = 1;
67 FieldElement(limbs)
68 }
69
70 /// Create a field element from big‐endian bytes.
71 /// Validates that the value < p. Returns Err if ≥ p.
72 pub fn from_bytes(bytes: &[u8; P192_FIELD_ELEMENT_SIZE]) -> Result<Self> {
73 // Convert big‐endian → little‐endian limbs
74 let mut limbs = [0u32; NLIMBS];
75 for (i, limb) in limbs.iter_mut().enumerate() {
76 let offset = (NLIMBS - 1 - i) * 4;
77 *limb = u32::from_be_bytes([
78 bytes[offset],
79 bytes[offset + 1],
80 bytes[offset + 2],
81 bytes[offset + 3],
82 ]);
83 }
84 // ── canonicalise ───────────────────────────────────────────────
85 let (sub, borrow) = Self::sbb6(limbs, Self::MOD_LIMBS);
86 if borrow == 1 {
87 // limbs < p → already canonical
88 return Ok(FieldElement(limbs));
89 }
90
91 // limbs ≥ p
92 if limbs == Self::MOD_LIMBS {
93 // exact modulus is forbidden
94 return Err(Error::param("FieldElement P-192", "Value ≥ modulus"));
95 }
96
97 // Reduce once (limbs − p) — always < p now
98 Ok(FieldElement(sub))
99 }
100
101 /// Convert this field element into big‐endian bytes.
102 pub fn to_bytes(&self) -> [u8; P192_FIELD_ELEMENT_SIZE] {
103 let mut out = [0u8; P192_FIELD_ELEMENT_SIZE];
104 for (i, &limb) in self.0.iter().enumerate() {
105 let limb_bytes = limb.to_be_bytes();
106 let offset = (NLIMBS - 1 - i) * 4;
107 out[offset..offset + 4].copy_from_slice(&limb_bytes);
108 }
109 out
110 }
111
112 /// Constant‐time check: is self < p ?
113 #[inline(always)]
114 pub fn is_valid(&self) -> bool {
115 let (_, borrow) = Self::sbb6(self.0, Self::MOD_LIMBS);
116 // If borrow == 1, then self < p
117 borrow == 1
118 }
119
120 /// Check if element is zero
121 pub fn is_zero(&self) -> bool {
122 self.0.iter().all(|&w| w == 0)
123 }
124
125 /// Return true if the element is odd (least‐significant bit = 1).
126 pub fn is_odd(&self) -> bool {
127 (self.0[0] & 1) == 1
128 }
129
130 /// Constant‐time addition: (self + other) mod p
131 pub fn add(&self, other: &Self) -> Self {
132 // 1. Full 192-bit addition
133 let (sum, carry) = Self::adc6(self.0, other.0);
134
135 // 2. Reduce if necessary
136 // If carry = 1 or sum >= p, subtract p
137 let (reduced, borrow) = Self::sbb6(sum, Self::MOD_LIMBS);
138 let need_reduce = (carry | (borrow ^ 1)) & 1;
139
140 Self::conditional_select(&sum, &reduced, Choice::from(need_reduce as u8))
141 }
142
143 /// Constant‐time subtraction: (self - other) mod p
144 pub fn sub(&self, other: &Self) -> Self {
145 let (diff, borrow) = Self::sbb6(self.0, other.0);
146 // If borrow == 1, we add p back
147 let (diff_plus_p, _) = Self::adc6(diff, Self::MOD_LIMBS);
148 Self::conditional_select(&diff, &diff_plus_p, Choice::from(borrow as u8))
149 }
150
151 /// Field multiplication: (self * other) mod p
152 /// Implements schoolbook 6×6 → 12‐limb product, then reduction
153 pub fn mul(&self, other: &Self) -> Self {
154 // Phase 1: 6×6 → 12 128-bit partial accumulators
155 let mut t = [0u128; NLIMBS * 2];
156 for i in 0..NLIMBS {
157 for j in 0..NLIMBS {
158 t[i + j] += (self.0[i] as u128) * (other.0[j] as u128);
159 }
160 }
161
162 // Phase 2: Carry‐propagate into 12 × u32 limbs
163 let mut wide = [0u32; NLIMBS * 2];
164 let mut carry: u128 = 0;
165 for i in 0..(NLIMBS * 2) {
166 let v = t[i] + carry;
167 wide[i] = (v & 0xFFFF_FFFF) as u32;
168 carry = v >> 32;
169 }
170
171 // Phase 3: Reduce 12 limbs → 6 limbs mod p
172 Self::reduce_wide(wide)
173 }
174
175 /// Field squaring: (self²) mod p
176 #[inline(always)]
177 pub fn square(&self) -> Self {
178 self.mul(self)
179 }
180
181 /// Compute multiplicative inverse via Fermat: a^(p-2) mod p
182 pub fn invert(&self) -> Result<Self> {
183 if self.is_zero() {
184 return Err(Error::param("FieldElement P-192", "Inverse of zero"));
185 }
186
187 // P-192 prime: p = FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFFFFFFFFFFFF
188 // p-2 = FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFFFFFFFFFFFD
189 const P_MINUS_2: [u8; 24] = [
190 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF,
191 0xFF, 0xFE, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFD,
192 ];
193
194 // Binary exponentiation
195 let mut result = FieldElement::one();
196 let base = self.clone();
197
198 for &byte in P_MINUS_2.iter() {
199 for bit in (0..8).rev() {
200 result = result.square();
201 if (byte >> bit) & 1 == 1 {
202 result = result.mul(&base);
203 }
204 }
205 }
206
207 Ok(result)
208 }
209
210 /// Negate this field element: returns p - self if non-zero, else zero
211 pub fn negate(&self) -> Self {
212 if self.is_zero() {
213 self.clone()
214 } else {
215 FieldElement::zero().sub(self)
216 }
217 }
218
219 /// Compute square root using the fact that p ≡ 3 (mod 4)
220 /// For such primes, sqrt(x) = x^((p+1)/4)
221 pub fn sqrt(&self) -> Option<Self> {
222 if self.is_zero() {
223 return Some(FieldElement::zero());
224 }
225
226 // Correct exponent (p + 1) / 4 = 2¹⁹⁰ − 2⁶²
227 const EXP: [u8; 24] = [
228 0x3F, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF,
229 0xFF, 0xFF, 0xC0, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
230 ];
231
232 // Compute self^exp using square-and-multiply
233 let mut result = FieldElement::one();
234 let base = self.clone();
235
236 for &byte in EXP.iter() {
237 for i in (0..8).rev() {
238 result = result.square();
239 if (byte >> i) & 1 == 1 {
240 result = result.mul(&base);
241 }
242 }
243 }
244
245 // Verify that result^2 == self
246 if result.square() == *self {
247 Some(result)
248 } else {
249 None
250 }
251 }
252
253 /* ================================================================= */
254 /* Private helper methods (constant‐time arithmetic) */
255 /* ================================================================= */
256
257 /// 6‐limb addition with carry
258 #[inline(always)]
259 fn adc6(a: [u32; 6], b: [u32; 6]) -> ([u32; 6], u32) {
260 let mut r = [0u32; 6];
261 let mut carry = 0u64;
262 for ((&a_limb, &b_limb), r_limb) in a.iter().zip(b.iter()).zip(r.iter_mut()) {
263 let tmp = (a_limb as u64) + (b_limb as u64) + carry;
264 *r_limb = (tmp & 0xFFFF_FFFF) as u32;
265 carry = tmp >> 32;
266 }
267 (r, carry as u32)
268 }
269
270 /// 6‐limb subtraction with borrow (constant-time)
271 #[inline(always)]
272 fn sbb6(a: [u32; 6], b: [u32; 6]) -> ([u32; 6], u32) {
273 let mut r = [0u32; 6];
274 let mut borrow = 0u32;
275
276 for ((&a_limb, &b_limb), r_limb) in a.iter().zip(b.iter()).zip(r.iter_mut()) {
277 // Compute: a[i] – b[i] – borrow
278 //
279 // `sub` is done in u64 to avoid rust's 'add with borrow'
280 // undefined-behaviour rules, then truncated back to 32 bits.
281 let ai = a_limb as u64;
282 let bi = b_limb as u64;
283 let tmp = ai.wrapping_sub(bi + borrow as u64);
284
285 *r_limb = tmp as u32;
286
287 // New borrow = 1 iff ai < bi + old_borrow
288 borrow = (ai < bi + borrow as u64) as u32;
289 }
290
291 (r, borrow)
292 }
293
294 /// Constant‐time select: if flag == 0 return a else return b
295 fn conditional_select(a: &[u32; 6], b: &[u32; 6], flag: Choice) -> Self {
296 let mut out = [0u32; 6];
297 for ((a_limb, b_limb), out_limb) in a.iter().zip(b.iter()).zip(out.iter_mut()) {
298 *out_limb = u32::conditional_select(a_limb, b_limb, flag);
299 }
300 FieldElement(out)
301 }
302
303 /// Reduce a 12-word (384-bit) value modulo
304 /// `p = 2¹⁹² − 2⁶⁴ − 1`.
305 ///
306 /// Algorithm: FIPS-186-5 B.3.3 (low + high + high·2⁶⁴)
307 /// followed by two conditional subtractions of *p*.
308 fn reduce_wide(t: [u32; 12]) -> FieldElement {
309 //------------------------------------------------------------------
310 // step 1 – r = low + high + (high << 64)
311 //------------------------------------------------------------------
312 let mut r = [0u64; 6];
313
314 /* low */
315 for (i, r_limb) in r.iter_mut().enumerate() {
316 *r_limb = t[i] as u64;
317 }
318
319 /* high + high << 64 */
320 for j in 0..6 {
321 let hi = t[j + 6] as u64;
322
323 r[j] += hi; // + high
324 r[(j + 2) % 6] += hi; // + high·2⁶⁴ (wrap at 192)
325
326 // *** extra wrap for j = 4, 5 (hi·2¹⁹² term) ***
327 if j >= 4 {
328 r[j - 2] += hi; // + hi·2⁶⁴ that
329 // arises from 2¹⁹² ≡ 2⁶⁴ + 1
330 }
331 }
332
333 //------------------------------------------------------------------
334 // step 2 – propagate carries once over the six 32-bit limbs
335 //------------------------------------------------------------------
336 let mut carry = 0u64;
337 for limb in &mut r {
338 let tmp = *limb + carry;
339 *limb = tmp & 0xFFFF_FFFF;
340 carry = tmp >> 32;
341 }
342
343 //------------------------------------------------------------------
344 // step 3 – fold the single residual carry
345 // using 2¹⁹² ≡ 2⁶⁴ + 1 (mod p)
346 //------------------------------------------------------------------
347 while carry != 0 {
348 let c = carry; // c is 1 at most
349
350 let tmp0 = r[0] + c;
351 r[0] = tmp0 & 0xFFFF_FFFF;
352 carry = tmp0 >> 32;
353
354 let tmp2 = r[2] + c + carry;
355 r[2] = tmp2 & 0xFFFF_FFFF;
356 carry = tmp2 >> 32;
357 }
358
359 //------------------------------------------------------------------
360 // step 4 – at most two conditional subtractions of p
361 //------------------------------------------------------------------
362 let mut out = [0u32; 6];
363 for (i, out_limb) in out.iter_mut().enumerate() {
364 *out_limb = r[i] as u32;
365 }
366
367 for _ in 0..2 {
368 let (sub, borrow) = Self::sbb6(out, Self::MOD_LIMBS);
369 /* if borrow == 0 → out ≥ p → use the subtracted value */
370 let selected = Self::conditional_select(&out, &sub, Choice::from((borrow ^ 1) as u8));
371 out = selected.0;
372 }
373
374 FieldElement(out)
375 }
376}