dcrypt_algorithms/ec/b283k/
field.rs

1//! sect283k1 binary field arithmetic GF(2^283)
2//! Irreducible polynomial: x^283 + x^12 + x^7 + x^5 + 1
3
4use crate::ec::b283k::constants::B283K_FIELD_ELEMENT_SIZE;
5use crate::error::{Error, Result};
6use subtle::{Choice, ConditionallySelectable};
7
8/// A field element in GF(2^283) represented by 5 u64 limbs (320 bits).
9#[derive(Clone, Copy, Debug, PartialEq, Eq)]
10pub struct FieldElement(pub(crate) [u64; 5]);
11
12impl ConditionallySelectable for FieldElement {
13    fn conditional_select(a: &Self, b: &Self, choice: Choice) -> Self {
14        let mut out = [0u64; 5];
15        for i in 0..5 {
16            out[i] = u64::conditional_select(&a.0[i], &b.0[i], choice);
17        }
18        FieldElement(out)
19    }
20}
21
22impl FieldElement {
23    // The irreducible polynomial for sect283k1: f(x) = x^283 + x^12 + x^7 + x^5 + 1
24    const REDUCER: [u64; 5] = [1 << 12 | 1 << 7 | 1 << 5 | 1, 0, 0, 0, 0];
25
26    /// The additive identity element (zero).
27    pub fn zero() -> Self {
28        FieldElement([0; 5])
29    }
30
31    /// The multiplicative identity element (one).
32    pub fn one() -> Self {
33        FieldElement([1, 0, 0, 0, 0])
34    }
35
36    /// Create a field element from its canonical byte representation.
37    ///
38    /// The bytes are interpreted as a big-endian representation of the field element.
39    pub fn from_bytes(bytes: &[u8; B283K_FIELD_ELEMENT_SIZE]) -> Result<Self> {
40        let mut limbs = [0u64; 5];
41        // Read 36 bytes big-endian into 5 u64 limbs
42        // bytes[0..4] contains the top 27 bits (283-256)
43        limbs[4] = u64::from_be_bytes([0, 0, 0, 0, bytes[0], bytes[1], bytes[2], bytes[3]]);
44        limbs[3] = u64::from_be_bytes(bytes[4..12].try_into().unwrap());
45        limbs[2] = u64::from_be_bytes(bytes[12..20].try_into().unwrap());
46        limbs[1] = u64::from_be_bytes(bytes[20..28].try_into().unwrap());
47        limbs[0] = u64::from_be_bytes(bytes[28..36].try_into().unwrap());
48
49        // Verify that the highest bits are zero (only 283 bits should be used)
50        if limbs[4] & !((1u64 << 27) - 1) != 0 {
51            return Err(Error::param(
52                "FieldElement B283k",
53                "Value exceeds field size",
54            ));
55        }
56
57        Ok(FieldElement(limbs))
58    }
59
60    /// Convert this field element to its canonical byte representation.
61    ///
62    /// The bytes are a big-endian representation of the field element.
63    pub fn to_bytes(&self) -> [u8; B283K_FIELD_ELEMENT_SIZE] {
64        let mut bytes = [0u8; B283K_FIELD_ELEMENT_SIZE];
65        // Write 5 u64 limbs to 36 bytes big-endian
66        // Only use the lower 4 bytes of limb[4] since we only need 283 bits
67        let top_limb_bytes = self.0[4].to_be_bytes();
68        bytes[0..4].copy_from_slice(&top_limb_bytes[4..]);
69        bytes[4..12].copy_from_slice(&self.0[3].to_be_bytes());
70        bytes[12..20].copy_from_slice(&self.0[2].to_be_bytes());
71        bytes[20..28].copy_from_slice(&self.0[1].to_be_bytes());
72        bytes[28..36].copy_from_slice(&self.0[0].to_be_bytes());
73        bytes
74    }
75
76    /// Check if this field element is zero.
77    pub fn is_zero(&self) -> bool {
78        self.0.iter().all(|&l| l == 0)
79    }
80
81    /// Add two field elements in GF(2^283).
82    ///
83    /// In binary fields, addition is performed using XOR.
84    pub fn add(&self, other: &Self) -> Self {
85        let mut res = [0u64; 5];
86        for (i, (a, b)) in self.0.iter().zip(other.0.iter()).enumerate() {
87            res[i] = a ^ b;
88        }
89        FieldElement(res)
90    }
91
92    /// Multiply two field elements in GF(2^283).
93    ///
94    /// Uses the irreducible polynomial for reduction.
95    pub fn mul(&self, other: &Self) -> Self {
96        let mut res = FieldElement::zero();
97        let mut a = *self;
98        let mut b = *other;
99
100        for _ in 0..283 {
101            if (b.0[0] & 1) == 1 {
102                res = res.add(&a);
103            }
104            b = b.shr1();
105            a = a.shl1();
106
107            // After shifting left, check if bit 283 is set
108            // Bit 283 is at position 27 in limb[4] (since 283 = 256 + 27)
109            if (a.0[4] >> 27) & 1 == 1 {
110                // Reduce by XORing with the reduction polynomial
111                a = a.add(&FieldElement(Self::REDUCER));
112                // Clear the overflow bit
113                a.0[4] &= (1u64 << 27) - 1;
114            }
115        }
116        res
117    }
118
119    /// Square a field element in GF(2^283).
120    pub fn square(&self) -> Self {
121        self.mul(self) // Non-optimized square
122    }
123
124    /// Compute the multiplicative inverse of a field element.
125    ///
126    /// Uses Fermat's Little Theorem: a^(2^m - 2) = a^(-1) in GF(2^m).
127    /// Returns an error if the element is zero.
128    pub fn invert(&self) -> Result<Self> {
129        if self.is_zero() {
130            return Err(Error::param("FieldElement B283k", "Inversion of zero"));
131        }
132        // Fermat's Little Theorem: a^(2^m - 2)
133        let mut res = *self;
134        for _ in 1..282 {
135            res = res.square();
136            res = res.mul(self);
137        }
138        res = res.square();
139        Ok(res)
140    }
141
142    /// Compute the square root of a field element.
143    ///
144    /// In binary fields of characteristic 2, sqrt(x) = x^(2^(m-1)).
145    pub fn sqrt(&self) -> Self {
146        // sqrt(x) = x^(2^(m-1))
147        let mut res = *self;
148        for _ in 0..282 {
149            res = res.square();
150        }
151        res
152    }
153
154    // Shift left by 1
155    fn shl1(&self) -> Self {
156        let mut r = [0u64; 5];
157        r[0] = self.0[0] << 1;
158
159        // Use zip to iterate over current and previous elements
160        for (i, (&curr, &prev)) in self.0[1..].iter().zip(self.0[..4].iter()).enumerate() {
161            r[i + 1] = (curr << 1) | (prev >> 63);
162        }
163
164        // Ensure we don't have bits beyond position 282
165        r[4] &= (1u64 << 28) - 1; // Allow up to bit 283 for overflow detection
166        FieldElement(r)
167    }
168
169    // Shift right by 1
170    fn shr1(&self) -> Self {
171        let mut r = [0u64; 5];
172
173        // Use zip to iterate over current and next elements
174        for (i, (&curr, &next)) in self.0[..4].iter().zip(self.0[1..].iter()).enumerate() {
175            r[i] = (curr >> 1) | (next << 63);
176        }
177
178        r[4] = self.0[4] >> 1;
179        FieldElement(r)
180    }
181
182    /// Get the trace of the element.
183    ///
184    /// The trace is Tr(z) = z + z^2 + z^4 + ... + z^(2^(m-1)).
185    /// For compressed points, it's used to disambiguate the y-coordinate.
186    pub fn trace(&self) -> u64 {
187        let mut res = *self;
188        let mut temp = *self;
189        for _ in 0..282 {
190            temp = temp.square();
191            res = res.add(&temp);
192        }
193        res.0[0] & 1
194    }
195}
dcrypt_algorithms/ec/b283k/field.rs

dcrypt_algorithms/ec/b283k/
field.rs
