pathfinder_crypto/signature/
ecdsa.rs

1use std::fmt::{Display, Formatter};
2
3use crate::algebra::curve::{AffinePoint, ProjectivePoint, CURVE_G};
4use crate::algebra::field::{CurveOrderMontFelt, Felt, MontFelt};
5
6/// Upper bound is
7/// 0x0800000000000000000000000000000000000000000000000000000000000000
8/// in Montgomery representation. We could also use
9/// Felt::has_more_than_251_bits, but makes comparison easy for MontFelts and is
10/// consistent with StarkWare's implementation.
11pub const UPPER_BOUND: MontFelt = MontFelt::from_raw([
12    18446743986131435553,
13    160989183,
14    18446744073709255680,
15    576459263475450960,
16]);
17
18/// Signature error
19#[derive(Debug, Eq, PartialEq)]
20pub enum SignatureError {
21    /// Error if the signature is invalid during verification.
22    Signature,
23
24    /// Error for invalid randomness.
25    Randomness,
26
27    /// Error for invalid message.
28    Message,
29
30    /// Error for invalid secret key.
31    SecretKey,
32
33    /// Error for invalid public key.
34    PublicKey,
35}
36
37impl Display for SignatureError {
38    fn fmt(&self, f: &mut Formatter<'_>) -> std::fmt::Result {
39        match self {
40            SignatureError::Signature => write!(f, "invalid signature"),
41            SignatureError::Message => write!(f, "invalid message"),
42            SignatureError::Randomness => write!(f, "invalid randomness"),
43            SignatureError::SecretKey => write!(f, "invalid secret key"),
44            SignatureError::PublicKey => write!(f, "invalid public key"),
45        }
46    }
47}
48
49impl std::error::Error for SignatureError {}
50
51/// Retrieve the partial public-key from a private key
52pub fn get_pk(sk: Felt) -> Option<Felt> {
53    CurveOrderMontFelt::try_from(sk)
54        .map(ProjectivePoint::gen_multiply_elm)
55        .as_ref()
56        .map(AffinePoint::from)
57        .map(|ap| ap.x)
58        .map(Felt::from)
59        .ok()
60}
61
62/// Generate a signature `(r,s)` on message z with secret key sk with `k` from
63/// thread_rng, not constant time!
64///
65/// This algorithm tries different random `k` from thread_rng until it finds a
66/// valid signature. The algorithm is **NOT** constant time and care should be
67/// taken when used in timing-sensitive contexts.
68pub fn ecdsa_sign(sk: Felt, z: Felt) -> Result<(Felt, Felt), SignatureError> {
69    let rng = &mut rand::thread_rng();
70    loop {
71        let k = Felt::random(rng);
72        match ecdsa_sign_k(sk, z, k) {
73            Ok(sig) => return Ok(sig),
74            Err(SignatureError::Randomness) => continue,
75            Err(e) => return Err(e),
76        }
77    }
78}
79
80/// Generate a signature `(r,s)` on message z with secret key sk and explicit
81/// randomness k, not constant time!
82///
83/// Never sign the same message with the same randomness twice, or your key my
84/// be extracted. The algorithm is **NOT** constant time and care should be
85/// taken when used in timing-sensitive contexts.
86pub fn ecdsa_sign_k(sk: Felt, z: Felt, k: Felt) -> Result<(Felt, Felt), SignatureError> {
87    let sk = CurveOrderMontFelt::try_from(sk).map_err(|_| SignatureError::SecretKey)?;
88    let z = CurveOrderMontFelt::try_from(z).map_err(|_| SignatureError::Message)?;
89    let k = CurveOrderMontFelt::try_from(k).map_err(|_| SignatureError::Randomness)?;
90    if k == CurveOrderMontFelt::ZERO {
91        return Err(SignatureError::Randomness);
92    }
93
94    // Compute `r` - we require it fits in 251 bits (less than curve order).
95    let x = AffinePoint::gen_multiply_elm(k).x;
96    if x >= UPPER_BOUND {
97        return Err(SignatureError::Randomness);
98    }
99    let r = CurveOrderMontFelt::try_from(x).unwrap();
100
101    // Compute `s` - safe as non-zero `k` are invertible in prime fields.
102    let kinv = k.inverse().unwrap();
103    let s = kinv * (z + r * sk);
104
105    let r = Felt::from(r);
106    let s = Felt::from(s);
107    Ok((r, s))
108}
109
110/// Retrieve the point for a public key while validating it's non-zero and on
111/// the curve.
112fn get_pk_point(pk: MontFelt) -> Option<AffinePoint> {
113    match AffinePoint::from_x(pk) {
114        Some(p) if !p.infinity => Some(p),
115        _ => None,
116    }
117}
118
119/// Verify an ECDSA signature with a partial public key.
120pub fn ecdsa_verify_partial(pk: Felt, z: Felt, r: Felt, s: Felt) -> Result<(), SignatureError> {
121    let montpk = MontFelt::from(pk);
122    let pk_point = get_pk_point(montpk).ok_or(SignatureError::PublicKey)?;
123    let pk_proj = ProjectivePoint::from(&pk_point);
124    ecdsa_verify_inner(pk_proj, z, r, s)
125}
126
127/// Verify an ECDSA signature `(r,s)` on message `z` given a full public key
128/// `pk=(x,y)`.
129pub fn ecdsa_verify(pk: AffinePoint, z: Felt, r: Felt, s: Felt) -> Result<(), SignatureError> {
130    let pk_point = get_pk_point(pk.x).ok_or(SignatureError::PublicKey)?;
131    if pk_point.y != pk.y {
132        return Err(SignatureError::PublicKey);
133    }
134    let pk_proj = ProjectivePoint::from(&pk_point);
135    ecdsa_verify_inner(pk_proj, z, r, s)
136}
137
138/// Verify an ECDSA signature `(r,s)` on message `z` given a validated public
139/// key `pk`.
140///
141/// The caller should check that the public key is on the curve and not
142/// infinity.
143pub fn ecdsa_verify_inner(
144    pk: ProjectivePoint,
145    z: Felt,
146    r: Felt,
147    s: Felt,
148) -> Result<(), SignatureError> {
149    // Convert to field elements
150    let f_z = MontFelt::from(z);
151    let f_r = MontFelt::from(r);
152    let f_s = MontFelt::from(s);
153
154    let cf_z = CurveOrderMontFelt::try_from(f_z).unwrap();
155    let cf_r = CurveOrderMontFelt::try_from(f_r).unwrap();
156    let cf_s = CurveOrderMontFelt::try_from(f_s).unwrap();
157
158    // Check hard bound on message and signature.
159    if f_z >= UPPER_BOUND {
160        return Err(SignatureError::Message);
161    }
162    if f_r == MontFelt::ZERO || f_r >= UPPER_BOUND {
163        return Err(SignatureError::Signature);
164    }
165    if f_s == MontFelt::ZERO || f_s >= UPPER_BOUND {
166        return Err(SignatureError::Signature);
167    }
168
169    // Compute u1 = z/s and u2 = r/s
170    let cf_s = cf_s.inverse().unwrap();
171    let u1 = cf_z * cf_s;
172    let u2 = cf_r * cf_s;
173
174    // Compute r1 = u1*G + u2*pk and r2 = u1*G - u2*pk
175    let u1g = CURVE_G.multiply_elm(&u1);
176    let u2pk = pk.multiply_elm(&u2);
177    let r1 = {
178        let mut tmp = u1g.clone();
179        tmp.add(&u2pk);
180        AffinePoint::from(&tmp)
181    };
182    let r2 = {
183        let mut minus_u2pk = u2pk.clone();
184        minus_u2pk.negate();
185
186        let mut tmp = u1g;
187        tmp.add(&minus_u2pk);
188        AffinePoint::from(&tmp)
189    };
190
191    // Return whether signature was valid
192    if r1.x == f_r || r2.x == f_r {
193        Ok(())
194    } else {
195        Err(SignatureError::Signature)
196    }
197}
198
199/// Test vectors from https://github.com/starkware-libs/crypto-cpp/blob/master/src/starkware/crypto/ecdsa_test.cc
200#[cfg(test)]
201mod tests {
202    use super::*;
203
204    fn felt_hex(x: &str) -> Felt {
205        Felt::from_hex_str(x).unwrap()
206    }
207    fn felm_hex(x: &str) -> MontFelt {
208        MontFelt::from(Felt::from_hex_str(x).unwrap())
209    }
210
211    #[test]
212    fn upper_bound() {
213        assert!(UPPER_BOUND <= crate::algebra::curve::CURVE_ORDER);
214    }
215
216    #[test]
217    fn test_get_pk() {
218        let sk = felt_hex("0x03c1e9550e66958296d11b60f8e8e7a7ad990d07fa65d5f7652c4a6c87d4e3cc");
219
220        let pk_x = felm_hex("0x77a3b314db07c45076d11f62b6f9e748a39790441823307743cf00d6597ea43");
221        let pk_y = felm_hex("0x54d7beec5ec728223671c627557efc5c9a6508425dc6c900b7741bf60afec06");
222
223        let pk = get_pk(sk).expect("valid sk");
224        let pk_affine = AffinePoint::from_x(pk.into()).unwrap();
225
226        assert_eq!(pk_affine.x, pk_x);
227        assert_eq!(pk_affine.y, pk_y);
228    }
229
230    #[test]
231    fn from_x() {
232        let pk_x = felm_hex("0x77a3b314db07c45076d11f62b6f9e748a39790441823307743cf00d6597ea43");
233        let pk_y = felm_hex("0x54d7beec5ec728223671c627557efc5c9a6508425dc6c900b7741bf60afec06");
234        let pk_affine = AffinePoint::from_x(pk_x).unwrap();
235        assert_eq!(pk_affine.y, pk_y);
236    }
237
238    #[test]
239    fn get_partial_pk() {
240        let pk_x = felt_hex("0x77a3b314db07c45076d11f62b6f9e748a39790441823307743cf00d6597ea43");
241
242        let sk = felt_hex("0x03c1e9550e66958296d11b60f8e8e7a7ad990d07fa65d5f7652c4a6c87d4e3cc");
243        let pk = get_pk(sk).unwrap();
244
245        assert_eq!(pk, pk_x);
246    }
247
248    #[test]
249    fn verify_partial() {
250        let sk = felt_hex("0x03c1e9550e66958296d11b60f8e8e7a7ad990d07fa65d5f7652c4a6c87d4e3cc");
251        let msg = felt_hex("0x397e76d1667c4454bfb83514e120583af836f8e32a516765497823eabe16a3f");
252        let sig = ecdsa_sign(sk, msg).expect("can sign");
253        let pk = get_pk(sk).expect("can get pk");
254        assert!(ecdsa_verify_partial(pk, msg, sig.0, sig.1).is_ok());
255    }
256
257    #[test]
258    fn verify_inner() {
259        // Test vector from https://github.com/starkware-libs/crypto-cpp/blob/master/src/starkware/crypto/ecdsa_test.cc
260        let pk_x = felm_hex("0x77a3b314db07c45076d11f62b6f9e748a39790441823307743cf00d6597ea43");
261        let pk = ProjectivePoint::from_x(pk_x).unwrap();
262
263        let msg = felt_hex("0x397e76d1667c4454bfb83514e120583af836f8e32a516765497823eabe16a3f");
264        let r = felt_hex("0x173fd03d8b008ee7432977ac27d1e9d1a1f6c98b1a2f05fa84a21c84c44e882");
265        let w = felt_hex("0x1f2c44a7798f55192f153b4c48ea5c1241fbb69e6132cc8a0da9c5b62a4286e");
266
267        // Compute s=1/w
268        let w = CurveOrderMontFelt::try_from(MontFelt::from(w)).unwrap();
269        let s = Felt::from(w.inverse().unwrap());
270
271        assert!(ecdsa_verify_inner(pk, msg, r, s).is_ok());
272    }
273
274    #[test]
275    fn verify_bad() {
276        // Changed last byte of pk from 3 to 4
277        let pk = felt_hex("0x77a3b314db07c45076d11f62b6f9e748a39790441823307743cf00d6597ea44");
278        let msg = felt_hex("0x397e76d1667c4454bfb83514e120583af836f8e32a516765497823eabe16a3f");
279        let r = felt_hex("0x173fd03d8b008ee7432977ac27d1e9d1a1f6c98b1a2f05fa84a21c84c44e882");
280        let s = felt_hex("0x1f2c44a7798f55192f153b4c48ea5c1241fbb69e6132cc8a0da9c5b62a4286e");
281        assert!(ecdsa_verify_partial(pk, msg, r, s).is_err());
282
283        // Changed last byte of msg from f to 0
284        let pk = felt_hex("0x77a3b314db07c45076d11f62b6f9e748a39790441823307743cf00d6597ea43");
285        let msg = felt_hex("0x397e76d1667c4454bfb83514e120583af836f8e32a516765497823eabe16a30");
286        let r = felt_hex("0x173fd03d8b008ee7432977ac27d1e9d1a1f6c98b1a2f05fa84a21c84c44e882");
287        let s = felt_hex("0x1f2c44a7798f55192f153b4c48ea5c1241fbb69e6132cc8a0da9c5b62a4286e");
288        assert!(ecdsa_verify_partial(pk, msg, r, s).is_err());
289
290        // Changed last byte of r from 2 to 3
291        let pk = felt_hex("0x77a3b314db07c45076d11f62b6f9e748a39790441823307743cf00d6597ea43");
292        let msg = felt_hex("0x397e76d1667c4454bfb83514e120583af836f8e32a516765497823eabe16a3f");
293        let r = felt_hex("0x173fd03d8b008ee7432977ac27d1e9d1a1f6c98b1a2f05fa84a21c84c44e883");
294        let s = felt_hex("0x1f2c44a7798f55192f153b4c48ea5c1241fbb69e6132cc8a0da9c5b62a4286e");
295        assert!(ecdsa_verify_partial(pk, msg, r, s).is_err());
296
297        // Changed last byte of s from e to f
298        let pk = felt_hex("0x77a3b314db07c45076d11f62b6f9e748a39790441823307743cf00d6597ea43");
299        let msg = felt_hex("0x397e76d1667c4454bfb83514e120583af836f8e32a516765497823eabe16a3f");
300        let r = felt_hex("0x173fd03d8b008ee7432977ac27d1e9d1a1f6c98b1a2f05fa84a21c84c44e882");
301        let s = felt_hex("0x1f2c44a7798f55192f153b4c48ea5c1241fbb69e6132cc8a0da9c5b62a4286f");
302        assert!(ecdsa_verify_partial(pk, msg, r, s).is_err());
303    }
304
305    #[test]
306    fn sequencer() {
307        // Test vector from https://alpha-mainnet.starknet.io/feeder_gateway/get_signature?blockNumber=350000
308        // and pk from https://alpha-mainnet.starknet.io/feeder_gateway/get_public_key?
309        use crate::hash::poseidon::poseidon_hash_many;
310        let state_diff_commitment =
311            felm_hex("0x432e8e2ad833548e1c1077fc298991b055ba1e6f7a17dd332db98f4f428c56c");
312        let block_hash =
313            felm_hex("0x6f7342a680d7f99bdfdd859f587c75299e7ffabe62c071ded3a6d8a34cb132c");
314
315        let msg = Felt::from(poseidon_hash_many(&[block_hash, state_diff_commitment]));
316        let r = felt_hex("0x95e98f5b91d39ae2b1bf77447a4fc01725352ae8b0b2c0a3fe09d43d1d9e57");
317        let s = felt_hex("0x541b2db8dae6d5ae24b34e427d251edc2e94dcffddd85f207e1b51f2f4bb1ef");
318        let pk = felt_hex("0x48253ff2c3bed7af18bde0b611b083b39445959102d4947c51c4db6aa4f4e58");
319        assert!(ecdsa_verify_partial(pk, msg, r, s).is_ok());
320    }
321
322    #[test]
323    fn openzeppelin_signature() {
324        // From https://testnet.starkscan.co/tx/0x0630a81628900577eea4b4a677767e57a56dabd730c2f64772ecbbde22ff485a
325        let pk = felt_hex("0x792c60ec4fdfea7ce6409db046b8dde11f595911cb74906be02a87ae6a4f70d");
326        let msg = felt_hex("0x0630a81628900577eea4b4a677767e57a56dabd730c2f64772ecbbde22ff485a");
327        let r = felt_hex("0x176846ea9b114f4f27f0d4d3cefacb5f830513fbd2d2f69a1a4d7552ae040be");
328        let s = felt_hex("0x601a87d6bc3e3a6513bafa1d449ffb3a0dd6cbe72f927a8e7271af0e8dd1302");
329        assert!(ecdsa_verify_partial(pk, msg, r, s).is_ok());
330    }
331}
pathfinder_crypto/signature/ecdsa.rs

pathfinder_crypto/signature/
ecdsa.rs
