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

sp1_lib/ecdsa/
affine.rs
