acvm_blackbox_solver/ecdsa/
secp256r1.rs

1use acir::BlackBoxFunc;
2
3use p256::{
4    AffinePoint, ProjectivePoint, PublicKey,
5    elliptic_curve::{
6        PrimeField,
7        ops::Reduce,
8        scalar::IsHigh,
9        sec1::{Coordinates, FromSec1Point, Sec1Point, ToSec1Point},
10    },
11};
12use p256::{Scalar, ecdsa::Signature};
13
14use crate::BlackBoxResolutionError;
15
16/// Verifies an ECDSA signature over the Secp256r1 elliptic curve.
17///
18/// This function implements ECDSA signature verification on the Secp256r1 curve
19///
20/// # Parameters:
21///
22/// * `hashed_msg` - The 32-byte hash of the message that was signed
23/// * `public_key_x_bytes` - The x-coordinate of the public key (32 bytes, big-endian)
24/// * `public_key_y_bytes` - The y-coordinate of the public key (32 bytes, big-endian)
25/// * `signature` - The 64-byte signature in (r, s) format, where r and s are 32 bytes each
26///
27/// Returns `true` if the signature is valid, `false` otherwise.
28///
29/// The function does not validate a signature if any of the following are true:
30/// - The signature is not "low S" normalized per BIP 0062 to prevent malleability
31/// - The signature components `r` and `s` is zero
32/// - The public key point is not on the Secp256r1 curve
33///
34/// If `hashed_msg >= p256::NistP256::ORDER`, the message hash is reduced modulo the curve
35/// order per ECDSA specification (SEC 1, section 4.1.4).
36pub(super) fn verify_signature(
37    hashed_msg: &[u8; 32],
38    public_key_x_bytes: &[u8; 32],
39    public_key_y_bytes: &[u8; 32],
40    signature: &[u8; 64],
41) -> Result<bool, BlackBoxResolutionError> {
42    // Convert the inputs into k256 data structures
43    let Ok(signature) = Signature::try_from(signature.as_slice()) else {
44        // Signature `r` and `s` are forbidden from being zero.
45        log::warn!("Signature provided for ECDSA verification is zero");
46        return Ok(false);
47    };
48
49    let point = Sec1Point::<p256::NistP256>::from_affine_coordinates(
50        public_key_x_bytes.into(),
51        public_key_y_bytes.into(),
52        false,
53    );
54
55    let pubkey = PublicKey::from_sec1_point(&point);
56    if pubkey.is_none().into() {
57        // Public key must sit on the Secp256r1 curve.
58        log::warn!("Invalid public key provided for ECDSA verification");
59        return Ok(false);
60    }
61    let pubkey = pubkey.unwrap();
62
63    // Convert the hashed message to a scalar.
64    // Per ECDSA specification (SEC 1, section 4.1.4), if `hashed_msg >= p256::NistP256::ORDER`,
65    // the message hash should be reduced modulo the curve order.
66    let z = <Scalar as Reduce<p256::U256>>::reduce(&p256::U256::from_be_slice(hashed_msg));
67
68    // Finished converting bytes into data structures
69
70    let r = signature.r();
71    let s = signature.s();
72
73    // Ensure signature is "low S" normalized ala BIP 0062
74    if s.is_high().into() {
75        log::warn!(
76            "Signature provided for ECDSA verification is not properly normalized (high S value)"
77        );
78        return Ok(false);
79    }
80
81    let s_inv = s.invert().unwrap();
82    let u1 = z * s_inv;
83    let u2 = *r * s_inv;
84
85    #[allow(non_snake_case)]
86    let R: AffinePoint = ((ProjectivePoint::GENERATOR * u1)
87        + (ProjectivePoint::from(*pubkey.as_affine()) * u2))
88        .to_affine();
89
90    match R.to_sec1_point(false).coordinates() {
91        Coordinates::Uncompressed { x, y: _ } => {
92            // The conversion from R.x to a scalar can fail if R.x >= curve_order (a possible but rare case).
93            // In this case, the signature is invalid per ECDSA specification, so we return false.
94            // The prover will handle this gracefully - it should generate a proof that fails verification.
95            Ok(Scalar::from_repr(*x).into_option().map_or_else(
96                || {
97                    log::warn!("Failed to convert R.x coordinate to scalar for ECDSA verification");
98                    false
99                },
100                |scalar| scalar == *r,
101            ))
102        }
103        Coordinates::Identity => Ok(false),
104        _ => Err(BlackBoxResolutionError::Failed(
105            BlackBoxFunc::EcdsaSecp256r1,
106            "Unexpected coordinate encoding".to_string(),
107        )),
108    }
109}
110
111#[cfg(test)]
112mod secp256r1_tests {
113    use super::verify_signature;
114
115    // 0x54705ba3baafdbdfba8c5f9a70f7a89bee98d906b53e31074da7baecdc0da9ad
116    const HASHED_MESSAGE: [u8; 32] = [
117        84, 112, 91, 163, 186, 175, 219, 223, 186, 140, 95, 154, 112, 247, 168, 155, 238, 152, 217,
118        6, 181, 62, 49, 7, 77, 167, 186, 236, 220, 13, 169, 173,
119    ];
120    // 0x550f471003f3df97c3df506ac797f6721fb1a1fb7b8f6f83d224498a65c88e24
121    const PUB_KEY_X: [u8; 32] = [
122        85, 15, 71, 16, 3, 243, 223, 151, 195, 223, 80, 106, 199, 151, 246, 114, 31, 177, 161, 251,
123        123, 143, 111, 131, 210, 36, 73, 138, 101, 200, 142, 36,
124    ];
125    // 0x136093d7012e509a73715cbd0b00a3cc0ff4b5c01b3ffa196ab1fb327036b8e6
126    const PUB_KEY_Y: [u8; 32] = [
127        19, 96, 147, 215, 1, 46, 80, 154, 115, 113, 92, 189, 11, 0, 163, 204, 15, 244, 181, 192,
128        27, 63, 250, 25, 106, 177, 251, 50, 112, 54, 184, 230,
129    ];
130    // 0x2c70a8d084b62bfc5ce03641caf9f72ad4da8c81bfe6ec9487bb5e1bef62a13218ad9ee29eaf351fdc50f1520c425e9b908a07278b43b0ec7b872778c14e0784
131    const SIGNATURE: [u8; 64] = [
132        44, 112, 168, 208, 132, 182, 43, 252, 92, 224, 54, 65, 202, 249, 247, 42, 212, 218, 140,
133        129, 191, 230, 236, 148, 135, 187, 94, 27, 239, 98, 161, 50, 24, 173, 158, 226, 158, 175,
134        53, 31, 220, 80, 241, 82, 12, 66, 94, 155, 144, 138, 7, 39, 139, 67, 176, 236, 123, 135,
135        39, 120, 193, 78, 7, 132,
136    ];
137
138    #[test]
139    fn verifies_valid_signature_with_low_s_value() {
140        let valid = verify_signature(&HASHED_MESSAGE, &PUB_KEY_X, &PUB_KEY_Y, &SIGNATURE).unwrap();
141
142        assert!(valid);
143    }
144
145    #[test]
146    fn signature_does_not_verify_when_does_not_have_the_full_y_coordinate() {
147        let mut pub_key_y_bytes = [0u8; 32];
148        pub_key_y_bytes[31] = PUB_KEY_Y[31];
149        let result =
150            verify_signature(&HASHED_MESSAGE, &PUB_KEY_X, &pub_key_y_bytes, &SIGNATURE).unwrap();
151        assert!(!result);
152    }
153
154    #[test]
155    fn signature_does_not_verify_on_invalid_signature() {
156        // This signature is invalid as ECDSA specifies that `r` and `s` must be non-zero.
157        let invalid_signature: [u8; 64] = [0x00; 64];
158        let result =
159            verify_signature(&HASHED_MESSAGE, &PUB_KEY_X, &PUB_KEY_Y, &invalid_signature).unwrap();
160        assert!(!result);
161    }
162
163    #[test]
164    fn signature_does_not_verify_on_invalid_public_key() {
165        let invalid_pub_key_x: [u8; 32] = [0xff; 32];
166        let invalid_pub_key_y: [u8; 32] = [0xff; 32];
167        let result =
168            verify_signature(&HASHED_MESSAGE, &invalid_pub_key_x, &invalid_pub_key_y, &SIGNATURE)
169                .unwrap();
170        assert!(!result);
171    }
172
173    #[test]
174    fn signature_does_not_verify_when_hashed_msg_exceeds_curve_order() {
175        // All 0xFF bytes is larger than the secp256r1 curve order
176        // (0xFFFFFFFF00000000FFFFFFFFFFFFFFFFBCE6FAADA7179E84F3B9CAC2FC632551).
177        // The function should reduce it modulo the order, not panic.
178        let oversized_hash: [u8; 32] = [0xff; 32];
179
180        // The result will be false (signature doesn't match the reduced hash), but no panic.
181        let result = verify_signature(&oversized_hash, &PUB_KEY_X, &PUB_KEY_Y, &SIGNATURE).unwrap();
182        assert!(!result);
183    }
184
185    #[test]
186    fn signature_does_not_verify_when_hashed_msg_equals_curve_order() {
187        // The exact secp256r1 curve order.
188        let curve_order: [u8; 32] = [
189            0xFF, 0xFF, 0xFF, 0xFF, 0x00, 0x00, 0x00, 0x00, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF,
190            0xFF, 0xFF, 0xBC, 0xE6, 0xFA, 0xAD, 0xA7, 0x17, 0x9E, 0x84, 0xF3, 0xB9, 0xCA, 0xC2,
191            0xFC, 0x63, 0x25, 0x51,
192        ];
193
194        let result = verify_signature(&curve_order, &PUB_KEY_X, &PUB_KEY_Y, &SIGNATURE).unwrap();
195        assert!(!result);
196    }
197}
acvm_blackbox_solver/ecdsa/secp256r1.rs

acvm_blackbox_solver/ecdsa/
secp256r1.rs
