sp1_lib/ecdsa/
affine.rs

1//! Implementation of an affine point, with acceleration for operations in the context of SP1.
2//!
3//! The [`crate::ecdsa::ProjectivePoint`] type is mainly used in the `ecdsa-core` algorithms,
4//! however, in some cases, the affine point is required.
5//!
6//! Note: When performing curve operations, accelerated crates for SP1 use affine arithmetic instead of projective arithmetic for performance.
7
8use super::{
9    ECDSACurve, ECDSAPoint, Field, FieldElement, SP1AffinePointTrait, FIELD_BYTES_SIZE_USIZE,
10};
11
12use elliptic_curve::{
13    ff::Field as _,
14    group::GroupEncoding,
15    point::{AffineCoordinates, DecompactPoint, DecompressPoint},
16    sec1::{self, CompressedPoint, EncodedPoint, FromEncodedPoint, ToEncodedPoint},
17    subtle::{Choice, ConditionallySelectable, ConstantTimeEq, CtOption},
18    zeroize::DefaultIsZeroes,
19    FieldBytes, PrimeField,
20};
21use std::ops::Neg;
22
23#[derive(Clone, Copy, Debug)]
24pub struct AffinePoint<C: ECDSACurve> {
25    pub inner: C::SP1AffinePoint,
26}
27
28impl<C: ECDSACurve> AffinePoint<C> {
29    /// Create an affine point from the given field elements, without checking if the point is on the curve.
30    pub fn from_field_elements_unchecked(x: FieldElement<C>, y: FieldElement<C>) -> Self {
31        let mut x_slice = x.to_bytes();
32        let x_slice = x_slice.as_mut_slice();
33        x_slice.reverse();
34
35        let mut y_slice = y.to_bytes();
36        let y_slice = y_slice.as_mut_slice();
37        y_slice.reverse();
38
39        AffinePoint { inner: <C::SP1AffinePoint as ECDSAPoint>::from(x_slice, y_slice) }
40    }
41
42    /// Get the x and y field elements of the point.
43    ///
44    /// The returned elements are always normalized.
45    pub fn field_elements(&self) -> (FieldElement<C>, FieldElement<C>) {
46        if self.is_identity().into() {
47            return (FieldElement::<C>::ZERO, FieldElement::<C>::ZERO);
48        }
49
50        let bytes = self.inner.to_le_bytes();
51
52        let mut x_bytes: [u8; FIELD_BYTES_SIZE_USIZE] =
53            bytes[..FIELD_BYTES_SIZE_USIZE].try_into().unwrap();
54
55        x_bytes.reverse();
56
57        let mut y_bytes: [u8; FIELD_BYTES_SIZE_USIZE] =
58            bytes[FIELD_BYTES_SIZE_USIZE..].try_into().unwrap();
59
60        y_bytes.reverse();
61
62        let x = FieldElement::<C>::from_bytes(&x_bytes.into()).unwrap();
63        let y = FieldElement::<C>::from_bytes(&y_bytes.into()).unwrap();
64        (x, y)
65    }
66
67    /// Get the generator point.
68    pub fn generator() -> Self {
69        AffinePoint { inner: C::SP1AffinePoint::GENERATOR_T }
70    }
71
72    /// Get the identity point.
73    pub fn identity() -> Self {
74        AffinePoint { inner: C::SP1AffinePoint::identity() }
75    }
76
77    /// Check if the point is the identity point.
78    pub fn is_identity(&self) -> Choice {
79        Choice::from(self.inner.is_identity() as u8)
80    }
81}
82
83impl<C: ECDSACurve> FromEncodedPoint<C> for AffinePoint<C> {
84    fn from_encoded_point(point: &EncodedPoint<C>) -> CtOption<Self> {
85        match point.coordinates() {
86            sec1::Coordinates::Identity => CtOption::new(Self::identity(), 1.into()),
87            sec1::Coordinates::Compact { x } => Self::decompact(x),
88            sec1::Coordinates::Compressed { x, y_is_odd } => {
89                AffinePoint::<C>::decompress(x, Choice::from(y_is_odd as u8))
90            }
91            sec1::Coordinates::Uncompressed { x, y } => {
92                let x = FieldElement::<C>::from_bytes(x);
93                let y = FieldElement::<C>::from_bytes(y);
94
95                x.and_then(|x| {
96                    y.and_then(|y| {
97                        // Ensure the point is on the curve.
98                        let lhs = (y * y).normalize();
99                        let rhs = (x * x * x) + (C::EQUATION_A * x) + C::EQUATION_B;
100
101                        let point = Self::from_field_elements_unchecked(x, y);
102
103                        CtOption::new(point, lhs.ct_eq(&rhs.normalize()))
104                    })
105                })
106            }
107        }
108    }
109}
110
111impl<C: ECDSACurve> ToEncodedPoint<C> for AffinePoint<C> {
112    fn to_encoded_point(&self, compress: bool) -> EncodedPoint<C> {
113        // If the point is the identity point, just return the identity point.
114        if self.is_identity().into() {
115            return EncodedPoint::<C>::identity();
116        }
117
118        let (x, y) = self.field_elements();
119
120        // The field elements are already normalized by virtue of being created via `FromBytes`.
121        EncodedPoint::<C>::from_affine_coordinates(&x.to_bytes(), &y.to_bytes(), compress)
122    }
123}
124
125impl<C: ECDSACurve> DecompressPoint<C> for AffinePoint<C> {
126    fn decompress(x_bytes: &FieldBytes<C>, y_is_odd: Choice) -> CtOption<Self> {
127        FieldElement::<C>::from_bytes(x_bytes).and_then(|x| {
128            let alpha = (x * x * x) + (C::EQUATION_A * x) + C::EQUATION_B;
129            let beta = alpha.sqrt();
130
131            beta.map(|beta| {
132                // Ensure the element is normalized for consistency.
133                let beta = beta.normalize();
134
135                let y = FieldElement::<C>::conditional_select(
136                    &beta.neg(),
137                    &beta,
138                    beta.is_odd().ct_eq(&y_is_odd),
139                );
140
141                // X is normalized by virtue of being created via `FromBytes`.
142                AffinePoint::from_field_elements_unchecked(x, y.normalize())
143            })
144        })
145    }
146}
147
148impl<C: ECDSACurve> DecompactPoint<C> for AffinePoint<C> {
149    fn decompact(x_bytes: &FieldBytes<C>) -> CtOption<Self> {
150        Self::decompress(x_bytes, Choice::from(0))
151    }
152}
153
154impl<C: ECDSACurve> AffineCoordinates for AffinePoint<C> {
155    type FieldRepr = FieldBytes<C>;
156
157    fn x(&self) -> FieldBytes<C> {
158        let (x, _) = self.field_elements();
159
160        x.to_bytes()
161    }
162
163    fn y_is_odd(&self) -> Choice {
164        let (_, y) = self.field_elements();
165
166        // As field elements are created via [`Field::from_bytes`], they are already normalized.
167        y.is_odd()
168    }
169}
170
171impl<C: ECDSACurve> ConditionallySelectable for AffinePoint<C> {
172    fn conditional_select(a: &Self, b: &Self, choice: Choice) -> Self {
173        // Conditional select is a constant time if-else operation.
174        //
175        // In the SP1 vm, there are no attempts made to prevent side channel attacks.
176        if choice.into() {
177            *b
178        } else {
179            *a
180        }
181    }
182}
183
184impl<C: ECDSACurve> ConstantTimeEq for AffinePoint<C> {
185    fn ct_eq(&self, other: &Self) -> Choice {
186        let (x1, y1) = self.field_elements();
187        let (x1, y1) = (x1, y1);
188
189        let (x2, y2) = other.field_elements();
190        let (x2, y2) = (x2, y2);
191
192        // These are already normalized by virtue of being created via `FromBytes`.
193        x1.ct_eq(&x2) & y1.ct_eq(&y2)
194    }
195}
196
197impl<C: ECDSACurve> PartialEq for AffinePoint<C> {
198    fn eq(&self, other: &Self) -> bool {
199        self.ct_eq(other).into()
200    }
201}
202
203impl<C: ECDSACurve> Eq for AffinePoint<C> {}
204
205impl<C: ECDSACurve> Default for AffinePoint<C> {
206    fn default() -> Self {
207        AffinePoint::identity()
208    }
209}
210
211impl<C: ECDSACurve> DefaultIsZeroes for AffinePoint<C> {}
212
213impl<C: ECDSACurve> GroupEncoding for AffinePoint<C> {
214    type Repr = CompressedPoint<C>;
215
216    fn from_bytes(bytes: &Self::Repr) -> CtOption<Self> {
217        EncodedPoint::<C>::from_bytes(bytes)
218            .map(|point| CtOption::new(point, Choice::from(1)))
219            .unwrap_or_else(|_| {
220                // SEC1 identity encoding is technically 1-byte 0x00, but the
221                // `GroupEncoding` API requires a fixed-width `Repr`.
222                let is_identity = bytes.ct_eq(&Self::Repr::default());
223                CtOption::new(EncodedPoint::<C>::identity(), is_identity)
224            })
225            .and_then(|point| Self::from_encoded_point(&point))
226    }
227
228    fn from_bytes_unchecked(bytes: &Self::Repr) -> CtOption<Self> {
229        // There is no unchecked conversion for compressed points.
230        Self::from_bytes(bytes)
231    }
232
233    fn to_bytes(&self) -> Self::Repr {
234        let encoded = self.to_encoded_point(true);
235        let mut result = CompressedPoint::<C>::default();
236        result[..encoded.len()].copy_from_slice(encoded.as_bytes());
237        result
238    }
239}
sp1_lib/ecdsa/affine.rs

sp1_lib/ecdsa/
affine.rs
