dcrypt_algorithms/ec/k256/
point.rs

1//! secp256k1 elliptic curve point operations
2
3use crate::ec::k256::{
4    constants::{
5        K256_FIELD_ELEMENT_SIZE, K256_POINT_COMPRESSED_SIZE, K256_POINT_UNCOMPRESSED_SIZE,
6    },
7    field::FieldElement,
8    scalar::Scalar,
9};
10use crate::error::{validate, Error, Result};
11use subtle::{Choice, ConditionallySelectable};
12
13/// Format of a serialized elliptic curve point
14#[derive(Debug, Clone, Copy, PartialEq, Eq)]
15pub enum PointFormat {
16    /// The point at infinity (identity element)
17    Identity,
18    /// Uncompressed format: 0x04 || x || y
19    Uncompressed,
20    /// Compressed format: 0x02/0x03 || x
21    Compressed,
22}
23
24/// A point on the secp256k1 elliptic curve in affine coordinates
25#[derive(Clone, Debug)]
26pub struct Point {
27    pub(crate) is_identity: Choice,
28    pub(crate) x: FieldElement,
29    pub(crate) y: FieldElement,
30}
31
32#[derive(Clone, Copy, Debug)]
33pub(crate) struct ProjectivePoint {
34    is_identity: Choice,
35    x: FieldElement,
36    y: FieldElement,
37    z: FieldElement,
38}
39
40impl PartialEq for Point {
41    fn eq(&self, other: &Self) -> bool {
42        let self_is_identity: bool = self.is_identity.into();
43        let other_is_identity: bool = other.is_identity.into();
44        if self_is_identity || other_is_identity {
45            return self_is_identity == other_is_identity;
46        }
47        self.x == other.x && self.y == other.y
48    }
49}
50
51impl Point {
52    /// Create a new point from uncompressed coordinates.
53    ///
54    /// Returns an error if the coordinates don't satisfy the curve equation.
55    pub fn new_uncompressed(
56        x: &[u8; K256_FIELD_ELEMENT_SIZE],
57        y: &[u8; K256_FIELD_ELEMENT_SIZE],
58    ) -> Result<Self> {
59        let x_fe = FieldElement::from_bytes(x)?;
60        let y_fe = FieldElement::from_bytes(y)?;
61        if !Self::is_on_curve(&x_fe, &y_fe) {
62            return Err(Error::param(
63                "K256 Point",
64                "Point coordinates do not satisfy curve equation",
65            ));
66        }
67        Ok(Point {
68            is_identity: Choice::from(0),
69            x: x_fe,
70            y: y_fe,
71        })
72    }
73
74    /// Create the identity point (point at infinity).
75    pub fn identity() -> Self {
76        Point {
77            is_identity: Choice::from(1),
78            x: FieldElement::zero(),
79            y: FieldElement::zero(),
80        }
81    }
82
83    /// Check if this point is the identity element.
84    pub fn is_identity(&self) -> bool {
85        self.is_identity.into()
86    }
87
88    /// Check if this point is valid (on the curve).
89    pub fn is_valid(&self) -> bool {
90        if self.is_identity() {
91            return true;
92        }
93        Self::is_on_curve(&self.x, &self.y)
94    }
95
96    /// Get the x-coordinate of this point as bytes.
97    pub fn x_coordinate_bytes(&self) -> [u8; K256_FIELD_ELEMENT_SIZE] {
98        self.x.to_bytes()
99    }
100
101    /// Get the y-coordinate of this point as bytes.
102    pub fn y_coordinate_bytes(&self) -> [u8; K256_FIELD_ELEMENT_SIZE] {
103        self.y.to_bytes()
104    }
105
106    /// Serialize this point in uncompressed format.
107    pub fn serialize_uncompressed(&self) -> [u8; K256_POINT_UNCOMPRESSED_SIZE] {
108        let mut out = [0u8; K256_POINT_UNCOMPRESSED_SIZE];
109        if self.is_identity() {
110            return out;
111        }
112        out[0] = 0x04;
113        out[1..33].copy_from_slice(&self.x.to_bytes());
114        out[33..].copy_from_slice(&self.y.to_bytes());
115        out
116    }
117
118    /// Deserialize a point from uncompressed format.
119    ///
120    /// Returns an error if the bytes don't represent a valid point.
121    pub fn deserialize_uncompressed(bytes: &[u8]) -> Result<Self> {
122        validate::length(
123            "K256 Uncompressed Point",
124            bytes.len(),
125            K256_POINT_UNCOMPRESSED_SIZE,
126        )?;
127
128        if bytes.iter().all(|&b| b == 0) {
129            return Ok(Self::identity());
130        }
131
132        if bytes[0] != 0x04 {
133            return Err(Error::param(
134                "K256 Point",
135                "Invalid uncompressed point prefix (expected 0x04)",
136            ));
137        }
138
139        let mut x_bytes = [0u8; K256_FIELD_ELEMENT_SIZE];
140        let mut y_bytes = [0u8; K256_FIELD_ELEMENT_SIZE];
141        x_bytes.copy_from_slice(&bytes[1..33]);
142        y_bytes.copy_from_slice(&bytes[33..65]);
143
144        Self::new_uncompressed(&x_bytes, &y_bytes)
145    }
146
147    /// Serialize this point in compressed format.
148    pub fn serialize_compressed(&self) -> [u8; K256_POINT_COMPRESSED_SIZE] {
149        let mut out = [0u8; K256_POINT_COMPRESSED_SIZE];
150        if self.is_identity() {
151            return out;
152        }
153        out[0] = if self.y.is_odd() { 0x03 } else { 0x02 };
154        out[1..].copy_from_slice(&self.x.to_bytes());
155        out
156    }
157
158    /// Deserialize a point from compressed format.
159    ///
160    /// Returns an error if the bytes don't represent a valid point.
161    pub fn deserialize_compressed(bytes: &[u8]) -> Result<Self> {
162        validate::length(
163            "K256 Compressed Point",
164            bytes.len(),
165            K256_POINT_COMPRESSED_SIZE,
166        )?;
167        if bytes.iter().all(|&b| b == 0) {
168            return Ok(Self::identity());
169        }
170        let tag = bytes[0];
171        if tag != 0x02 && tag != 0x03 {
172            return Err(Error::param(
173                "K256 Point",
174                "Invalid compressed point prefix",
175            ));
176        }
177        let mut x_bytes = [0u8; K256_FIELD_ELEMENT_SIZE];
178        x_bytes.copy_from_slice(&bytes[1..]);
179        let x_fe = FieldElement::from_bytes(&x_bytes)
180            .map_err(|_| Error::param("K256 Point", "Invalid x-coordinate"))?;
181        
182        let rhs = {
183            let x3 = x_fe.square().mul(&x_fe);
184            let mut seven = [0u32; 8];
185            seven[0] = 7;
186            let b = FieldElement(seven);
187            x3.add(&b)
188        };
189        let y_fe = rhs
190            .sqrt()
191            .ok_or_else(|| Error::param("K256 Point", "Invalid compressed point: no sqrt"))?;
192        let y_final = if (y_fe.is_odd() && tag == 0x03) || (!y_fe.is_odd() && tag == 0x02) {
193            y_fe
194        } else {
195            y_fe.negate()
196        };
197        Ok(Point {
198            is_identity: Choice::from(0),
199            x: x_fe,
200            y: y_final,
201        })
202    }
203
204    /// Add two points using the group law.
205    pub fn add(&self, other: &Self) -> Self {
206        self.to_projective().add(&other.to_projective()).to_affine()
207    }
208
209    /// Double a point (add it to itself).
210    pub fn double(&self) -> Self {
211        self.to_projective().double().to_affine()
212    }
213
214    /// Scalar multiplication: compute scalar * self.
215    ///
216    /// Uses constant-time double-and-add algorithm.
217    pub fn mul(&self, scalar: &Scalar) -> Result<Self> {
218        if scalar.is_zero() {
219            return Ok(Self::identity());
220        }
221        let scalar_bytes = scalar.as_secret_buffer().as_ref();
222        let base = self.to_projective();
223        let mut result = ProjectivePoint::identity();
224
225        for byte in scalar_bytes.iter() {
226            for bit_pos in (0..8).rev() {
227                result = result.double();
228                let bit = (byte >> bit_pos) & 1;
229                let choice = Choice::from(bit);
230                let result_added = result.add(&base);
231                result = ProjectivePoint::conditional_select(&result, &result_added, choice);
232            }
233        }
234        Ok(result.to_affine())
235    }
236
237    fn is_on_curve(x: &FieldElement, y: &FieldElement) -> bool {
238        let y_squared = y.square();
239        let x_cubed = x.square().mul(x);
240        let mut seven_limbs = [0u32; 8];
241        seven_limbs[0] = 7;
242        let seven = FieldElement(seven_limbs);
243        let rhs = x_cubed.add(&seven);
244        y_squared == rhs
245    }
246
247    fn to_projective(&self) -> ProjectivePoint {
248        if self.is_identity() {
249            return ProjectivePoint::identity();
250        }
251        ProjectivePoint {
252            is_identity: Choice::from(0),
253            x: self.x,
254            y: self.y,
255            z: FieldElement::one(),
256        }
257    }
258}
259
260impl ConditionallySelectable for ProjectivePoint {
261    fn conditional_select(a: &Self, b: &Self, choice: Choice) -> Self {
262        Self {
263            is_identity: Choice::conditional_select(&a.is_identity, &b.is_identity, choice),
264            x: FieldElement::conditional_select(&a.x, &b.x, choice),
265            y: FieldElement::conditional_select(&a.y, &b.y, choice),
266            z: FieldElement::conditional_select(&a.z, &b.z, choice),
267        }
268    }
269}
270
271impl ProjectivePoint {
272    pub fn identity() -> Self {
273        ProjectivePoint {
274            is_identity: Choice::from(1),
275            x: FieldElement::zero(),
276            y: FieldElement::one(),
277            z: FieldElement::zero(),
278        }
279    }
280
281    pub fn add(&self, other: &Self) -> Self {
282        // Constant-time add with no early returns
283        let z1_sq = self.z.square();
284        let z2_sq = other.z.square();
285        let u1 = self.x.mul(&z2_sq);
286        let u2 = other.x.mul(&z1_sq);
287        let s1 = self.y.mul(&z2_sq).mul(&other.z);
288        let s2 = other.y.mul(&z1_sq).mul(&self.z);
289
290        let h = u2.sub(&u1);
291        let r = s2.sub(&s1);
292        
293        // Generic addition
294        let h_sq = h.square();
295        let h_cu = h_sq.mul(&h);
296        let v = u1.mul(&h_sq);
297
298        let r_sq = r.square();
299        let two_v = v.add(&v);
300        let mut x3 = r_sq.sub(&h_cu);
301        x3 = x3.sub(&two_v);
302
303        let v_minus_x3 = v.sub(&x3);
304        let mut y3 = r.mul(&v_minus_x3);
305        let s1_h_cu = s1.mul(&h_cu);
306        y3 = y3.sub(&s1_h_cu);
307
308        let mut z3 = self.z.mul(&other.z);
309        z3 = z3.mul(&h);
310
311        let generic = ProjectivePoint {
312            is_identity: Choice::from(0),
313            x: x3,
314            y: y3,
315            z: z3,
316        };
317
318        // Double (fallback for P==Q)
319        let double = self.double();
320
321        // Select results
322        let h_is_zero = Choice::from((h.is_zero() as u8) & 1);
323        let r_is_zero = Choice::from((r.is_zero() as u8) & 1);
324        let p_eq_q = h_is_zero & r_is_zero;
325        let p_eq_neg_q = h_is_zero & !r_is_zero;
326
327        let mut result = Self::conditional_select(&generic, &double, p_eq_q);
328        result = Self::conditional_select(&result, &Self::identity(), p_eq_neg_q);
329        result = Self::conditional_select(&result, other, self.is_identity);
330        result = Self::conditional_select(&result, self, other.is_identity);
331
332        result
333    }
334
335    pub fn double(&self) -> Self {
336        // Jacobian doubling for a = 0 (y^2 = x^3 + 7)
337        
338        let y_sq = self.y.square();
339        let mut s = self.x.mul(&y_sq);
340        s = s.add(&s); // 2s
341        s = s.add(&s); // 4s -> S = 4*x*y^2
342        
343        let x_sq = self.x.square();
344        let mut m = x_sq.add(&x_sq);
345        m = m.add(&x_sq); // M = 3*x^2 (a=0)
346
347        let mut x3 = m.square();
348        let s_plus_s = s.add(&s);
349        x3 = x3.sub(&s_plus_s); // X3 = M^2 - 2S
350
351        let mut y3 = s.sub(&x3);
352        y3 = m.mul(&y3);
353        
354        let y_sq_sq = y_sq.square();
355        let mut eight_y4 = y_sq_sq.add(&y_sq_sq); // 2
356        eight_y4 = eight_y4.add(&eight_y4); // 4
357        eight_y4 = eight_y4.add(&eight_y4); // 8
358        y3 = y3.sub(&eight_y4); // Y3 = M(S - X3) - 8Y^4
359
360        let mut z3 = self.y.mul(&self.z);
361        z3 = z3.add(&z3); // Z3 = 2*Y*Z
362
363        let result = ProjectivePoint {
364            is_identity: Choice::from(0),
365            x: x3,
366            y: y3,
367            z: z3,
368        };
369
370        // Explicitly handle identity or y=0 cases constant-time
371        let is_y_zero = self.y.is_zero();
372        let return_identity = self.is_identity | Choice::from(is_y_zero as u8);
373        
374        Self::conditional_select(&result, &Self::identity(), return_identity)
375    }
376
377    pub fn to_affine(&self) -> Point {
378        if self.is_identity.into() {
379            return Point::identity();
380        }
381        let z_inv = self.z.invert().expect("Nonzero Z should be invertible");
382        let z_inv_sq = z_inv.square();
383        let z_inv_cu = z_inv_sq.mul(&z_inv);
384        let x_aff = self.x.mul(&z_inv_sq);
385        let y_aff = self.y.mul(&z_inv_cu);
386        Point {
387            is_identity: Choice::from(0),
388            x: x_aff,
389            y: y_aff,
390        }
391    }
392}
dcrypt_algorithms/ec/k256/point.rs

dcrypt_algorithms/ec/k256/
point.rs
