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 dcrypt_internal::{
12    constant_time::{Choice, ConditionallySelectable},
13    Zeroize, ZeroizeOnDrop, Zeroizing,
14};
15
16/// Format of a serialized elliptic curve point
17#[derive(Debug, Clone, Copy, PartialEq, Eq)]
18pub enum PointFormat {
19    /// The point at infinity (identity element)
20    Identity,
21    /// Uncompressed format: 0x04 || x || y
22    Uncompressed,
23    /// Compressed format: 0x02/0x03 || x
24    Compressed,
25}
26
27/// A point on the secp256k1 elliptic curve in affine coordinates
28#[derive(Clone, Debug)]
29pub struct Point {
30    pub(crate) is_identity: Choice,
31    pub(crate) x: FieldElement,
32    pub(crate) y: FieldElement,
33}
34
35impl Default for Point {
36    fn default() -> Self {
37        Self::identity()
38    }
39}
40
41impl Zeroize for Point {
42    fn zeroize(&mut self) {
43        self.is_identity.zeroize();
44        self.x.zeroize();
45        self.y.zeroize();
46    }
47}
48
49impl Drop for Point {
50    fn drop(&mut self) {
51        self.zeroize();
52    }
53}
54
55impl ZeroizeOnDrop for Point {}
56
57#[derive(Clone, Copy, Debug)]
58pub(crate) struct ProjectivePoint {
59    is_identity: Choice,
60    x: FieldElement,
61    y: FieldElement,
62    z: FieldElement,
63}
64
65// `ConditionallySelectable` requires `Copy`, so compiler/register-created
66// copies cannot be erased by safe Rust. Every explicit projective owner in
67// secret arithmetic is nevertheless held in `Zeroizing` storage.
68impl Default for ProjectivePoint {
69    fn default() -> Self {
70        Self::identity()
71    }
72}
73
74impl Zeroize for ProjectivePoint {
75    fn zeroize(&mut self) {
76        self.is_identity.zeroize();
77        self.x.zeroize();
78        self.y.zeroize();
79        self.z.zeroize();
80    }
81}
82
83impl PartialEq for Point {
84    fn eq(&self, other: &Self) -> bool {
85        let self_is_identity: bool = self.is_identity.into();
86        let other_is_identity: bool = other.is_identity.into();
87        if self_is_identity || other_is_identity {
88            return self_is_identity == other_is_identity;
89        }
90        self.x == other.x && self.y == other.y
91    }
92}
93
94impl Point {
95    /// Create a new point from uncompressed coordinates.
96    ///
97    /// Returns an error if the coordinates don't satisfy the curve equation.
98    pub fn new_uncompressed(
99        x: &[u8; K256_FIELD_ELEMENT_SIZE],
100        y: &[u8; K256_FIELD_ELEMENT_SIZE],
101    ) -> Result<Self> {
102        let x_fe = Zeroizing::new(FieldElement::from_bytes(x)?);
103        let y_fe = Zeroizing::new(FieldElement::from_bytes(y)?);
104        if !Self::is_on_curve(&x_fe, &y_fe) {
105            return Err(Error::param(
106                "K256 Point",
107                "Point coordinates do not satisfy curve equation",
108            ));
109        }
110        Ok(Point {
111            is_identity: Choice::from(0),
112            x: x_fe.into_inner(),
113            y: y_fe.into_inner(),
114        })
115    }
116
117    /// Create the identity point (point at infinity).
118    pub fn identity() -> Self {
119        Point {
120            is_identity: Choice::from(1),
121            x: FieldElement::zero(),
122            y: FieldElement::zero(),
123        }
124    }
125
126    /// Check if this point is the identity element.
127    pub fn is_identity(&self) -> bool {
128        self.is_identity.into()
129    }
130
131    /// Check if this point is valid (on the curve).
132    pub fn is_valid(&self) -> bool {
133        if self.is_identity() {
134            return true;
135        }
136        Self::is_on_curve(&self.x, &self.y)
137    }
138
139    /// Get the x-coordinate of this point as bytes.
140    pub fn x_coordinate_bytes(&self) -> [u8; K256_FIELD_ELEMENT_SIZE] {
141        self.x.to_bytes()
142    }
143
144    /// Get the y-coordinate of this point as bytes.
145    pub fn y_coordinate_bytes(&self) -> [u8; K256_FIELD_ELEMENT_SIZE] {
146        self.y.to_bytes()
147    }
148
149    /// Serialize this point in uncompressed format.
150    ///
151    /// For the identity this fixed-width API returns an all-zero internal
152    /// sentinel. SEC 1 encodes identity as the single byte `0x00`, so the
153    /// sentinel is deliberately rejected by the deserializer and must not be
154    /// placed on the wire.
155    pub fn serialize_uncompressed(&self) -> [u8; K256_POINT_UNCOMPRESSED_SIZE] {
156        let mut out = Zeroizing::new([0u8; K256_POINT_UNCOMPRESSED_SIZE]);
157        if self.is_identity() {
158            return [0u8; K256_POINT_UNCOMPRESSED_SIZE];
159        }
160        out[0] = 0x04;
161        let x_bytes = Zeroizing::new(self.x.to_bytes());
162        let y_bytes = Zeroizing::new(self.y.to_bytes());
163        out[1..33].copy_from_slice(&x_bytes[..]);
164        out[33..].copy_from_slice(&y_bytes[..]);
165        // Intentional public serialization boundary. This array exceeds the
166        // MSRV's array-`Default` support, so `into_inner` is unavailable.
167        let mut public_output = [0u8; K256_POINT_UNCOMPRESSED_SIZE];
168        public_output.copy_from_slice(&out[..]);
169        public_output
170    }
171
172    /// Deserialize a point from uncompressed format.
173    ///
174    /// Returns an error if the bytes don't represent a valid point.
175    pub fn deserialize_uncompressed(bytes: &[u8]) -> Result<Self> {
176        validate::length(
177            "K256 Uncompressed Point",
178            bytes.len(),
179            K256_POINT_UNCOMPRESSED_SIZE,
180        )?;
181
182        if bytes[0] != 0x04 {
183            return Err(Error::param(
184                "K256 Point",
185                "Invalid uncompressed point prefix (expected 0x04)",
186            ));
187        }
188
189        let mut x_bytes = Zeroizing::new([0u8; K256_FIELD_ELEMENT_SIZE]);
190        let mut y_bytes = Zeroizing::new([0u8; K256_FIELD_ELEMENT_SIZE]);
191        x_bytes.copy_from_slice(&bytes[1..33]);
192        y_bytes.copy_from_slice(&bytes[33..65]);
193
194        Self::new_uncompressed(&x_bytes, &y_bytes)
195    }
196
197    /// Serialize this point in compressed format.
198    ///
199    /// For the identity this fixed-width API returns an all-zero internal
200    /// sentinel, which is not a canonical SEC 1 encoding and is rejected by
201    /// the deserializer.
202    pub fn serialize_compressed(&self) -> [u8; K256_POINT_COMPRESSED_SIZE] {
203        let mut out = Zeroizing::new([0u8; K256_POINT_COMPRESSED_SIZE]);
204        if self.is_identity() {
205            return [0u8; K256_POINT_COMPRESSED_SIZE];
206        }
207        out[0] = if self.y.is_odd() { 0x03 } else { 0x02 };
208        let x_bytes = Zeroizing::new(self.x.to_bytes());
209        out[1..].copy_from_slice(&x_bytes[..]);
210        // Intentional public serialization boundary; see the uncompressed
211        // serializer for the MSRV array-`Default` limitation.
212        let mut public_output = [0u8; K256_POINT_COMPRESSED_SIZE];
213        public_output.copy_from_slice(&out[..]);
214        public_output
215    }
216
217    /// Deserialize a point from compressed format.
218    ///
219    /// Returns an error if the bytes don't represent a valid point.
220    pub fn deserialize_compressed(bytes: &[u8]) -> Result<Self> {
221        validate::length(
222            "K256 Compressed Point",
223            bytes.len(),
224            K256_POINT_COMPRESSED_SIZE,
225        )?;
226        let tag = bytes[0];
227        if tag != 0x02 && tag != 0x03 {
228            return Err(Error::param(
229                "K256 Point",
230                "Invalid compressed point prefix",
231            ));
232        }
233        let mut x_bytes = Zeroizing::new([0u8; K256_FIELD_ELEMENT_SIZE]);
234        x_bytes.copy_from_slice(&bytes[1..]);
235        let x_fe = Zeroizing::new(
236            FieldElement::from_bytes(&x_bytes)
237                .map_err(|_| Error::param("K256 Point", "Invalid x-coordinate"))?,
238        );
239
240        let x_squared = Zeroizing::new(x_fe.square());
241        let x3 = Zeroizing::new(x_squared.mul(&x_fe));
242        let mut seven = Zeroizing::new([0u32; 8]);
243        seven[0] = 7;
244        let b = Zeroizing::new(FieldElement(seven.into_inner()));
245        let rhs = Zeroizing::new(x3.add(&b));
246        let y_fe = Zeroizing::new(
247            rhs.sqrt()
248                .ok_or_else(|| Error::param("K256 Point", "Invalid compressed point: no sqrt"))?,
249        );
250        let y_final = Zeroizing::new(
251            if (y_fe.is_odd() && tag == 0x03) || (!y_fe.is_odd() && tag == 0x02) {
252                *y_fe
253            } else {
254                y_fe.negate()
255            },
256        );
257        Ok(Point {
258            is_identity: Choice::from(0),
259            x: x_fe.into_inner(),
260            y: y_final.into_inner(),
261        })
262    }
263
264    /// Add two points using the group law.
265    pub fn add(&self, other: &Self) -> Self {
266        let left = self.to_projective();
267        let right = other.to_projective();
268        let sum = Zeroizing::new(left.add(&right));
269        let affine = Zeroizing::new(sum.to_affine());
270        affine.into_inner()
271    }
272
273    /// Double a point (add it to itself).
274    pub fn double(&self) -> Self {
275        let point = self.to_projective();
276        let doubled = Zeroizing::new(point.double());
277        let affine = Zeroizing::new(doubled.to_affine());
278        affine.into_inner()
279    }
280
281    /// Scalar multiplication: compute scalar * self.
282    ///
283    /// Uses constant-time double-and-add algorithm.
284    pub fn mul(&self, scalar: &Scalar) -> Result<Self> {
285        let scalar_bytes = scalar.as_secret_buffer().as_ref();
286        let base = self.to_projective();
287        let mut result = Zeroizing::new(ProjectivePoint::identity());
288
289        for byte in scalar_bytes.iter() {
290            for bit_pos in (0..8).rev() {
291                let doubled = Zeroizing::new(result.double());
292                let bit = (byte >> bit_pos) & 1;
293                let choice = Choice::from(bit);
294                let result_added = Zeroizing::new(doubled.add(&base));
295                let selected = Zeroizing::new(ProjectivePoint::conditional_select(
296                    &doubled,
297                    &result_added,
298                    choice,
299                ));
300                result.zeroize();
301                *result = selected.into_inner();
302            }
303        }
304        let affine = Zeroizing::new(result.to_affine());
305        Ok(affine.into_inner())
306    }
307
308    fn is_on_curve(x: &FieldElement, y: &FieldElement) -> bool {
309        let y_squared = Zeroizing::new(y.square());
310        let x_squared = Zeroizing::new(x.square());
311        let x_cubed = Zeroizing::new(x_squared.mul(x));
312        let mut seven_limbs = Zeroizing::new([0u32; 8]);
313        seven_limbs[0] = 7;
314        let seven = Zeroizing::new(FieldElement(seven_limbs.into_inner()));
315        let rhs = Zeroizing::new(x_cubed.add(&seven));
316        *y_squared == *rhs
317    }
318
319    fn to_projective(&self) -> Zeroizing<ProjectivePoint> {
320        if self.is_identity() {
321            return Zeroizing::new(ProjectivePoint::identity());
322        }
323        Zeroizing::new(ProjectivePoint {
324            is_identity: Choice::from(0),
325            x: self.x,
326            y: self.y,
327            z: FieldElement::one(),
328        })
329    }
330}
331
332impl ConditionallySelectable for ProjectivePoint {
333    fn conditional_select(a: &Self, b: &Self, choice: Choice) -> Self {
334        let selected = Zeroizing::new(Self {
335            is_identity: Choice::conditional_select(&a.is_identity, &b.is_identity, choice),
336            x: FieldElement::conditional_select(&a.x, &b.x, choice),
337            y: FieldElement::conditional_select(&a.y, &b.y, choice),
338            z: FieldElement::conditional_select(&a.z, &b.z, choice),
339        });
340        selected.into_inner()
341    }
342}
343
344impl ProjectivePoint {
345    pub fn identity() -> Self {
346        ProjectivePoint {
347            is_identity: Choice::from(1),
348            x: FieldElement::zero(),
349            y: FieldElement::one(),
350            z: FieldElement::zero(),
351        }
352    }
353
354    pub fn add(&self, other: &Self) -> Self {
355        // Constant-time add with no early returns
356        let z1_sq = Zeroizing::new(self.z.square());
357        let z2_sq = Zeroizing::new(other.z.square());
358        let u1 = Zeroizing::new(self.x.mul(&z2_sq));
359        let u2 = Zeroizing::new(other.x.mul(&z1_sq));
360        let self_y_z2 = Zeroizing::new(self.y.mul(&z2_sq));
361        let s1 = Zeroizing::new(self_y_z2.mul(&other.z));
362        let other_y_z1 = Zeroizing::new(other.y.mul(&z1_sq));
363        let s2 = Zeroizing::new(other_y_z1.mul(&self.z));
364
365        let h = Zeroizing::new(u2.sub(&u1));
366        let r = Zeroizing::new(s2.sub(&s1));
367
368        // Generic addition
369        let h_sq = Zeroizing::new(h.square());
370        let h_cu = Zeroizing::new(h_sq.mul(&h));
371        let v = Zeroizing::new(u1.mul(&h_sq));
372
373        let r_sq = Zeroizing::new(r.square());
374        let r_sq_minus_h_cu = Zeroizing::new(r_sq.sub(&h_cu));
375        let two_v = Zeroizing::new(v.add(&v));
376        let x3 = Zeroizing::new(r_sq_minus_h_cu.sub(&two_v));
377
378        let v_minus_x3 = Zeroizing::new(v.sub(&x3));
379        let r_times_difference = Zeroizing::new(r.mul(&v_minus_x3));
380        let s1_h_cu = Zeroizing::new(s1.mul(&h_cu));
381        let y3 = Zeroizing::new(r_times_difference.sub(&s1_h_cu));
382
383        let z_product = Zeroizing::new(self.z.mul(&other.z));
384        let z3 = Zeroizing::new(z_product.mul(&h));
385
386        let generic = Zeroizing::new(ProjectivePoint {
387            is_identity: Choice::from(0),
388            x: x3.into_inner(),
389            y: y3.into_inner(),
390            z: z3.into_inner(),
391        });
392
393        // Double (fallback for P==Q)
394        let double = Zeroizing::new(self.double());
395
396        // Select results
397        let h_is_zero = Choice::from((h.is_zero() as u8) & 1);
398        let r_is_zero = Choice::from((r.is_zero() as u8) & 1);
399        let p_eq_q = h_is_zero & r_is_zero;
400        let p_eq_neg_q = h_is_zero & !r_is_zero;
401
402        let mut result = Zeroizing::new(Self::conditional_select(&generic, &double, p_eq_q));
403        let identity = Zeroizing::new(Self::identity());
404        let selected = Zeroizing::new(Self::conditional_select(&result, &identity, p_eq_neg_q));
405        result.zeroize();
406        *result = selected.into_inner();
407        let selected = Zeroizing::new(Self::conditional_select(&result, other, self.is_identity));
408        result.zeroize();
409        *result = selected.into_inner();
410        let selected = Zeroizing::new(Self::conditional_select(&result, self, other.is_identity));
411        result.zeroize();
412        *result = selected.into_inner();
413
414        result.into_inner()
415    }
416
417    pub fn double(&self) -> Self {
418        // Jacobian doubling for a = 0 (y^2 = x^3 + 7)
419
420        let y_sq = Zeroizing::new(self.y.square());
421        let s_once = Zeroizing::new(self.x.mul(&y_sq));
422        let s_twice = Zeroizing::new(s_once.add(&s_once)); // 2s
423        let s = Zeroizing::new(s_twice.add(&s_twice)); // 4s -> S = 4*x*y^2
424
425        let x_sq = Zeroizing::new(self.x.square());
426        let m_twice = Zeroizing::new(x_sq.add(&x_sq));
427        let m = Zeroizing::new(m_twice.add(&x_sq)); // M = 3*x^2 (a=0)
428
429        let m_squared = Zeroizing::new(m.square());
430        let s_plus_s = Zeroizing::new(s.add(&s));
431        let x3 = Zeroizing::new(m_squared.sub(&s_plus_s)); // X3 = M^2 - 2S
432
433        let s_minus_x3 = Zeroizing::new(s.sub(&x3));
434        let m_term = Zeroizing::new(m.mul(&s_minus_x3));
435
436        let y_sq_sq = Zeroizing::new(y_sq.square());
437        let two_y4 = Zeroizing::new(y_sq_sq.add(&y_sq_sq));
438        let four_y4 = Zeroizing::new(two_y4.add(&two_y4));
439        let eight_y4 = Zeroizing::new(four_y4.add(&four_y4));
440        let y3 = Zeroizing::new(m_term.sub(&eight_y4)); // Y3 = M(S - X3) - 8Y^4
441
442        let yz = Zeroizing::new(self.y.mul(&self.z));
443        let z3 = Zeroizing::new(yz.add(&yz)); // Z3 = 2*Y*Z
444
445        let result = Zeroizing::new(ProjectivePoint {
446            is_identity: Choice::from(0),
447            x: x3.into_inner(),
448            y: y3.into_inner(),
449            z: z3.into_inner(),
450        });
451
452        // Explicitly handle identity or y=0 cases constant-time
453        let is_y_zero = self.y.is_zero();
454        let return_identity = self.is_identity | Choice::from(is_y_zero as u8);
455
456        let identity = Zeroizing::new(Self::identity());
457        let selected = Zeroizing::new(Self::conditional_select(
458            &result,
459            &identity,
460            return_identity,
461        ));
462        selected.into_inner()
463    }
464
465    pub fn to_affine(&self) -> Point {
466        let safe_z = Zeroizing::new(FieldElement::conditional_select(
467            &self.z,
468            &FieldElement::one(),
469            self.is_identity,
470        ));
471        let z_inv = Zeroizing::new(safe_z.invert().expect("Nonzero Z should be invertible"));
472        let z_inv_sq = Zeroizing::new(z_inv.square());
473        let z_inv_cu = Zeroizing::new(z_inv_sq.mul(&z_inv));
474        let x_aff = Zeroizing::new(self.x.mul(&z_inv_sq));
475        let y_aff = Zeroizing::new(self.y.mul(&z_inv_cu));
476        let x = Zeroizing::new(FieldElement::conditional_select(
477            &x_aff,
478            &FieldElement::zero(),
479            self.is_identity,
480        ));
481        let y = Zeroizing::new(FieldElement::conditional_select(
482            &y_aff,
483            &FieldElement::zero(),
484            self.is_identity,
485        ));
486        let point = Zeroizing::new(Point {
487            is_identity: self.is_identity,
488            x: x.into_inner(),
489            y: y.into_inner(),
490        });
491        point.into_inner()
492    }
493}
494
495#[cfg(test)]
496mod lifecycle_tests {
497    use super::*;
498
499    fn assert_zeroize_on_drop<T: ZeroizeOnDrop>() {}
500
501    #[test]
502    fn affine_drop_and_projective_copy_limit_are_explicit() {
503        assert_zeroize_on_drop::<Point>();
504
505        let mut affine = Point {
506            is_identity: Choice::from(0),
507            x: FieldElement::one(),
508            y: FieldElement::one(),
509        };
510        affine.zeroize();
511        assert!(affine.x.is_zero());
512        assert!(affine.y.is_zero());
513
514        let original = ProjectivePoint {
515            is_identity: Choice::from(0),
516            x: FieldElement::one(),
517            y: FieldElement::one(),
518            z: FieldElement::one(),
519        };
520        let mut owned_copy = original;
521        owned_copy.zeroize();
522        assert!(owned_copy.x.is_zero());
523        assert!(!original.x.is_zero());
524    }
525}
dcrypt_algorithms/ec/k256/point.rs

dcrypt_algorithms/ec/k256/
point.rs
