openvm_ecc_guest/
ecdsa.rs

Help
1use alloc::vec::Vec;
2use core::ops::{Add, AddAssign, Mul};
3
4use ecdsa::{self, hazmat::bits2field, Error, RecoveryId, Result};
5use elliptic_curve::{sec1::Tag, PrimeCurve};
6use openvm_algebra_guest::{DivUnsafe, IntMod, Reduce};
7
8use crate::{
9    weierstrass::{FromCompressed, IntrinsicCurve, WeierstrassPoint},
10    CyclicGroup, Group,
11};
12
13pub type Coordinate<C> = <<C as IntrinsicCurve>::Point as WeierstrassPoint>::Coordinate;
14pub type Scalar<C> = <C as IntrinsicCurve>::Scalar;
15
16#[repr(C)]
17#[derive(Clone)]
18pub struct VerifyingKey<C: IntrinsicCurve> {
19    pub(crate) inner: PublicKey<C>,
20}
21
22#[repr(C)]
23#[derive(Clone)]
24pub struct PublicKey<C: IntrinsicCurve> {
25    /// Affine point
26    point: <C as IntrinsicCurve>::Point,
27}
28
29impl<C: IntrinsicCurve> PublicKey<C>
30where
31    C::Point: WeierstrassPoint + Group + FromCompressed<Coordinate<C>>,
32    Coordinate<C>: IntMod,
33    for<'a> &'a Coordinate<C>: Mul<&'a Coordinate<C>, Output = Coordinate<C>>,
34{
35    pub fn new(point: <C as IntrinsicCurve>::Point) -> Self {
36        Self { point }
37    }
38
39    pub fn from_sec1_bytes(bytes: &[u8]) -> Result<Self> {
40        if bytes.is_empty() {
41            return Err(Error::new());
42        }
43
44        // Validate tag
45        let tag = Tag::from_u8(bytes[0]).unwrap();
46
47        // Validate length
48        let expected_len = tag.message_len(Coordinate::<C>::NUM_LIMBS);
49        if bytes.len() != expected_len {
50            return Err(Error::new());
51        }
52
53        match tag {
54            Tag::Identity => {
55                let point = <<C as IntrinsicCurve>::Point as WeierstrassPoint>::IDENTITY;
56                Ok(Self { point })
57            }
58
59            Tag::CompressedEvenY | Tag::CompressedOddY => {
60                let x = Coordinate::<C>::from_be_bytes(&bytes[1..]);
61                let rec_id = bytes[0] & 1;
62                let point = FromCompressed::decompress(x, &rec_id).ok_or_else(Error::new)?;
63                Ok(Self { point })
64            }
65
66            Tag::Uncompressed => {
67                let (x_bytes, y_bytes) = bytes[1..].split_at(Coordinate::<C>::NUM_LIMBS);
68                let x = Coordinate::<C>::from_be_bytes(x_bytes);
69                let y = Coordinate::<C>::from_be_bytes(y_bytes);
70                let point = <C as IntrinsicCurve>::Point::from_xy(x, y).ok_or_else(Error::new)?;
71                Ok(Self { point })
72            }
73
74            _ => Err(Error::new()),
75        }
76    }
77
78    pub fn to_sec1_bytes(&self, compress: bool) -> Vec<u8> {
79        if self.point.is_identity() {
80            return vec![0x00];
81        }
82
83        let (x, y) = self.point.clone().into_coords();
84
85        if compress {
86            let mut bytes = Vec::<u8>::with_capacity(1 + Coordinate::<C>::NUM_LIMBS);
87            let tag = if y.as_le_bytes()[0] & 1 == 1 {
88                Tag::CompressedOddY
89            } else {
90                Tag::CompressedEvenY
91            };
92            bytes.push(tag.into());
93            bytes.extend_from_slice(x.to_be_bytes().as_ref());
94            bytes
95        } else {
96            let mut bytes = Vec::<u8>::with_capacity(1 + Coordinate::<C>::NUM_LIMBS * 2);
97            bytes.push(Tag::Uncompressed.into());
98            bytes.extend_from_slice(x.to_be_bytes().as_ref());
99            bytes.extend_from_slice(y.to_be_bytes().as_ref());
100            bytes
101        }
102    }
103
104    pub fn as_affine(&self) -> &<C as IntrinsicCurve>::Point {
105        &self.point
106    }
107}
108
109impl<C: IntrinsicCurve> VerifyingKey<C>
110where
111    C::Point: WeierstrassPoint + Group + FromCompressed<Coordinate<C>>,
112    Coordinate<C>: IntMod,
113    for<'a> &'a Coordinate<C>: Mul<&'a Coordinate<C>, Output = Coordinate<C>>,
114{
115    pub fn new(public_key: PublicKey<C>) -> Self {
116        Self { inner: public_key }
117    }
118
119    pub fn from_sec1_bytes(bytes: &[u8]) -> Result<Self> {
120        let public_key = PublicKey::<C>::from_sec1_bytes(bytes)?;
121        Ok(Self::new(public_key))
122    }
123
124    pub fn from_affine(point: <C as IntrinsicCurve>::Point) -> Result<Self> {
125        let public_key = PublicKey::<C>::new(point);
126        Ok(Self::new(public_key))
127    }
128
129    pub fn to_sec1_bytes(&self, compress: bool) -> Vec<u8> {
130        self.inner.to_sec1_bytes(compress)
131    }
132
133    pub fn as_affine(&self) -> &<C as IntrinsicCurve>::Point {
134        self.inner.as_affine()
135    }
136}
137
138impl<C> VerifyingKey<C>
139where
140    C: PrimeCurve + IntrinsicCurve,
141    C::Point: WeierstrassPoint + CyclicGroup + FromCompressed<Coordinate<C>>,
142    Coordinate<C>: IntMod,
143    C::Scalar: IntMod + Reduce,
144{
145    /// Ref: <https://github.com/RustCrypto/signatures/blob/85c984bcc9927c2ce70c7e15cbfe9c6936dd3521/ecdsa/src/recovery.rs#L297>
146    ///
147    /// Recovery does not require additional signature verification: <https://github.com/RustCrypto/signatures/pull/831>
148    ///
149    /// ## Panics
150    /// If the signature is invalid or public key cannot be recovered from the given input.
151    #[allow(non_snake_case)]
152    pub fn recover_from_prehash_noverify(
153        prehash: &[u8],
154        sig: &[u8],
155        recovery_id: RecoveryId,
156    ) -> Result<Self>
157    where
158        for<'a> &'a C::Point: Add<&'a C::Point, Output = C::Point>,
159        for<'a> &'a Coordinate<C>: Mul<&'a Coordinate<C>, Output = Coordinate<C>>,
160    {
161        // This should get compiled out:
162        assert!(Scalar::<C>::NUM_LIMBS <= Coordinate::<C>::NUM_LIMBS);
163        // IntMod limbs are currently always bytes
164        assert_eq!(sig.len(), <C as IntrinsicCurve>::Scalar::NUM_LIMBS * 2);
165        // Signature is default encoded in big endian bytes
166        let (r_be, s_be) = sig.split_at(<C as IntrinsicCurve>::Scalar::NUM_LIMBS);
167        // Note: Scalar internally stores using little endian
168        let r = Scalar::<C>::from_be_bytes(r_be);
169        let s = Scalar::<C>::from_be_bytes(s_be);
170        if !r.is_reduced() || !s.is_reduced() {
171            return Err(Error::new());
172        }
173        if r == Scalar::<C>::ZERO || s == Scalar::<C>::ZERO {
174            return Err(Error::new());
175        }
176
177        // Perf: don't use bits2field from ::ecdsa
178        let z = Scalar::<C>::from_be_bytes(bits2field::<C>(prehash).unwrap().as_ref());
179
180        // `r` is in the Scalar field, we now possibly add C::ORDER to it to get `x`
181        // in the Coordinate field.
182        let mut x = Coordinate::<C>::from_le_bytes(r.as_le_bytes());
183        if recovery_id.is_x_reduced() {
184            // Copy from slice in case Coordinate has more bytes than Scalar
185            let order = Coordinate::<C>::from_le_bytes(Scalar::<C>::MODULUS.as_ref());
186            x.add_assign(order);
187        }
188        let rec_id = recovery_id.to_byte();
189        // The point R decompressed from x-coordinate `r`
190        let R: C::Point = FromCompressed::decompress(x, &rec_id).ok_or_else(Error::new)?;
191
192        let neg_u1 = z.div_unsafe(&r);
193        let u2 = s.div_unsafe(&r);
194        let NEG_G = C::Point::NEG_GENERATOR;
195        let point = <C as IntrinsicCurve>::msm(&[neg_u1, u2], &[NEG_G, R]);
196        let public_key = PublicKey { point };
197
198        Ok(VerifyingKey { inner: public_key })
199    }
200
201    // Ref: https://docs.rs/ecdsa/latest/src/ecdsa/hazmat.rs.html#270
202    #[allow(non_snake_case)]
203    pub fn verify_prehashed(self, prehash: &[u8], sig: &[u8]) -> Result<()>
204    where
205        for<'a> &'a C::Point: Add<&'a C::Point, Output = C::Point>,
206        for<'a> &'a Scalar<C>: DivUnsafe<&'a Scalar<C>, Output = Scalar<C>>,
207    {
208        // This should get compiled out:
209        assert!(Scalar::<C>::NUM_LIMBS <= Coordinate::<C>::NUM_LIMBS);
210        // IntMod limbs are currently always bytes
211        assert_eq!(sig.len(), Scalar::<C>::NUM_LIMBS * 2);
212        // Signature is default encoded in big endian bytes
213        let (r_be, s_be) = sig.split_at(<C as IntrinsicCurve>::Scalar::NUM_LIMBS);
214        // Note: Scalar internally stores using little endian
215        let r = Scalar::<C>::from_be_bytes(r_be);
216        let s = Scalar::<C>::from_be_bytes(s_be);
217        if !r.is_reduced() || !s.is_reduced() {
218            return Err(Error::new());
219        }
220        if r == Scalar::<C>::ZERO || s == Scalar::<C>::ZERO {
221            return Err(Error::new());
222        }
223
224        // Perf: don't use bits2field from ::ecdsa
225        let z = <C as IntrinsicCurve>::Scalar::from_be_bytes(
226            bits2field::<C>(prehash).unwrap().as_ref(),
227        );
228
229        let u1 = z.div_unsafe(&s);
230        let u2 = (&r).div_unsafe(&s);
231
232        let G = C::Point::GENERATOR;
233        // public key
234        let Q = self.inner.point;
235        let R = <C as IntrinsicCurve>::msm(&[u1, u2], &[G, Q]);
236        if R.is_identity() {
237            return Err(Error::new());
238        }
239        let (x_1, _) = R.into_coords();
240        // Scalar and Coordinate may be different byte lengths, so we use an inefficient reduction
241        let x_mod_n = Scalar::<C>::reduce_le_bytes(x_1.as_le_bytes());
242        if x_mod_n == r {
243            Ok(())
244        } else {
245            Err(Error::new())
246        }
247    }
248}
openvm_ecc_guest/ecdsa.rs

openvm_ecc_guest/
ecdsa.rs
