miden_crypto/dsa/ecdsa_k256_keccak/
mod.rs

1//! ECDSA (Elliptic Curve Digital Signature Algorithm) signature implementation over secp256k1
2//! curve using Keccak to hash the messages when signing.
3
4use alloc::{string::ToString, vec::Vec};
5use core::fmt;
6
7use k256::{
8    AffinePoint,
9    ecdh::diffie_hellman,
10    ecdsa,
11    ecdsa::{RecoveryId, VerifyingKey, signature::hazmat::PrehashVerifier},
12    elliptic_curve::{Generate, point::AffineCoordinates, scalar::IsHigh},
13    pkcs8::DecodePublicKey,
14};
15use miden_crypto_derive::{SilentDebug, SilentDisplay};
16use rand::CryptoRng;
17use thiserror::Error;
18
19use crate::{
20    Felt, SequentialCommit, Word,
21    ecdh::k256::{EphemeralPublicKey, SharedSecret},
22    utils::{
23        ByteReader, ByteWriter, Deserializable, DeserializationError, Serializable,
24        read_sensitive_array, zeroize::ZeroizeOnDrop,
25    },
26};
27
28mod tests;
29
30// CONSTANTS
31// ================================================================================================
32
33/// Length of secret key in bytes
34const SECRET_KEY_BYTES: usize = 32;
35/// Length of public key in bytes when using compressed format encoding
36pub(crate) const PUBLIC_KEY_BYTES: usize = 33;
37/// Length of signature in bytes using our custom serialization
38const SIGNATURE_BYTES: usize = 65;
39/// Length of signature in bytes using standard serialization i.e., `SEC1`
40const SIGNATURE_STANDARD_BYTES: usize = 64;
41/// Length of scalars for the `secp256k1` curve
42const SCALARS_SIZE_BYTES: usize = 32;
43
44// SECRET KEY
45// ================================================================================================
46
47/// Secret key for ECDSA signature verification over secp256k1 curve.
48#[derive(Clone, SilentDebug, SilentDisplay)]
49struct SecretKey {
50    inner: ecdsa::SigningKey,
51}
52
53impl SecretKey {
54    /// Generates a new secret key using the provided random number generator.
55    fn with_rng<R: CryptoRng>(rng: &mut R) -> Self {
56        let signing_key = ecdsa::SigningKey::generate_from_rng(rng);
57
58        Self { inner: signing_key }
59    }
60
61    /// Gets the corresponding public key for this secret key.
62    fn public_key(&self) -> PublicKey {
63        let verifying_key = self.inner.verifying_key();
64        PublicKey { inner: *verifying_key }
65    }
66
67    /// Signs a message (represented as a Word) with this secret key.
68    fn sign(&self, message: Word) -> Signature {
69        let message_digest = hash_message(message);
70        self.sign_prehash(message_digest)
71    }
72
73    /// Signs a pre-hashed message with this secret key.
74    fn sign_prehash(&self, message_digest: [u8; 32]) -> Signature {
75        let (signature_inner, recovery_id) = self.inner.sign_prehash_recoverable(&message_digest);
76
77        let (r, s) = signature_inner.split_scalars();
78
79        Signature {
80            r: r.to_bytes().into(),
81            s: s.to_bytes().into(),
82            v: recovery_id.into(),
83        }
84    }
85
86    /// Computes a Diffie-Hellman shared secret from this secret key and the ephemeral public key
87    /// generated by the other party.
88    fn get_shared_secret(&self, pk_e: &EphemeralPublicKey) -> SharedSecret {
89        let shared_secret_inner = diffie_hellman(self.inner.as_nonzero_scalar(), pk_e.as_affine());
90
91        SharedSecret::new(shared_secret_inner)
92    }
93}
94
95// SAFETY: The inner `k256::ecdsa::SigningKey` already implements `ZeroizeOnDrop`,
96// which ensures that the secret key material is securely zeroized when dropped.
97impl ZeroizeOnDrop for SecretKey {}
98
99impl PartialEq for SecretKey {
100    fn eq(&self, other: &Self) -> bool {
101        use subtle::ConstantTimeEq;
102        self.to_bytes().ct_eq(&other.to_bytes()).into()
103    }
104}
105
106impl Eq for SecretKey {}
107
108// SIGNING KEY
109// ================================================================================================
110
111/// A secret key for ECDSA signature verification over the secp256k1 curve.
112#[derive(Clone, Eq, PartialEq, SilentDebug, SilentDisplay)] // Safe as SecretKey has const-time eq
113pub struct SigningKey(SecretKey);
114
115impl SigningKey {
116    /// Generates a new random signing key using the OS random number generator.
117    ///
118    /// This is cryptographically secure as long as [`rand::rng`] remains so.
119    #[cfg(feature = "std")]
120    #[allow(clippy::new_without_default)]
121    pub fn new() -> Self {
122        let mut rng = rand::rng();
123        Self::with_rng(&mut rng)
124    }
125
126    /// Generates a new signing key using the provided random number generator.
127    pub fn with_rng<R: CryptoRng>(rng: &mut R) -> Self {
128        Self(SecretKey::with_rng(rng))
129    }
130
131    /// Gets the public key that corresponds to this signing key.
132    pub fn public_key(&self) -> PublicKey {
133        self.0.public_key()
134    }
135
136    /// Signs a message (represented as a word) with this signing key.
137    pub fn sign(&self, message: Word) -> Signature {
138        self.0.sign(message)
139    }
140
141    /// Signs a pre-hashed message with this signing key.
142    pub fn sign_prehash(&self, message_digest: [u8; 32]) -> Signature {
143        self.0.sign_prehash(message_digest)
144    }
145}
146
147impl From<SecretKey> for SigningKey {
148    fn from(secret_key: SecretKey) -> Self {
149        Self(secret_key)
150    }
151}
152
153// SAFETY: The inner `SecretKey` already implements `ZeroizeOnDrop` which ensures that the secret
154// key material is securely zeroized when dropped.
155impl ZeroizeOnDrop for SigningKey {}
156
157impl Serializable for SigningKey {
158    fn write_into<W: ByteWriter>(&self, target: &mut W) {
159        self.0.write_into(target);
160    }
161}
162
163impl Deserializable for SigningKey {
164    fn read_from<R: ByteReader>(source: &mut R) -> Result<Self, DeserializationError> {
165        Ok(Self(SecretKey::read_from(source)?))
166    }
167}
168
169// KEY EXCHANGE KEY
170// ================================================================================================
171
172/// A secret key for ECDH key-exchange over the secp256k1 curve.
173#[derive(Clone, Eq, PartialEq, SilentDebug, SilentDisplay)] // Safe as SecretKey has const-time eq
174pub struct KeyExchangeKey(SecretKey);
175
176impl KeyExchangeKey {
177    /// Generates a new random key exchange key using the OS random number generator.
178    ///
179    /// This is cryptographically secure as long as [`rand::rng`] remains so.
180    #[cfg(feature = "std")]
181    #[allow(clippy::new_without_default)]
182    pub fn new() -> Self {
183        let mut rng = rand::rng();
184        Self::with_rng(&mut rng)
185    }
186
187    /// Generates a new signing key using the provided random number generator.
188    pub fn with_rng<R: CryptoRng>(rng: &mut R) -> Self {
189        Self(SecretKey::with_rng(rng))
190    }
191
192    /// Gets the public key that corresponds to this key exchange key.
193    pub fn public_key(&self) -> PublicKey {
194        self.0.public_key()
195    }
196
197    /// Computes a Diffie-Hellman shared secret from this secret key and the ephemeral public key
198    /// generated by the other party.
199    pub fn get_shared_secret(&self, pk_e: EphemeralPublicKey) -> SharedSecret {
200        self.0.get_shared_secret(&pk_e)
201    }
202}
203
204impl From<SecretKey> for KeyExchangeKey {
205    fn from(value: SecretKey) -> Self {
206        Self(value)
207    }
208}
209
210// SAFETY: The inner `SecretKey` already implements `ZeroizeOnDrop` which ensures that the secret
211// key material is securely zeroized when dropped.
212impl ZeroizeOnDrop for KeyExchangeKey {}
213
214impl Serializable for KeyExchangeKey {
215    fn write_into<W: ByteWriter>(&self, target: &mut W) {
216        self.0.write_into(target);
217    }
218}
219
220impl Deserializable for KeyExchangeKey {
221    fn read_from<R: ByteReader>(source: &mut R) -> Result<Self, DeserializationError> {
222        Ok(Self(SecretKey::read_from(source)?))
223    }
224}
225
226// PUBLIC KEY
227// ================================================================================================
228
229/// Public key for ECDSA signature verification over secp256k1 curve.
230#[derive(Debug, Clone, PartialEq, Eq)]
231pub struct PublicKey {
232    pub(crate) inner: VerifyingKey,
233}
234
235impl PublicKey {
236    /// Returns a commitment to the public key using the Poseidon2 hash function.
237    ///
238    /// Public key serialization remains compressed SEC1. The commitment preimage is not the
239    /// compressed SEC1 encoding; it is `qx || qy`, where each secp256k1 affine coordinate is
240    /// represented as eight little-endian numeric `u32` limbs, one limb per [`Felt`].
241    pub fn to_commitment(&self) -> Word {
242        <Self as SequentialCommit>::to_commitment(self)
243    }
244
245    /// Returns a reference to this public key as an elliptic curve point in affine coordinates.
246    pub fn as_affine(&self) -> &AffinePoint {
247        self.inner.as_affine()
248    }
249
250    /// Verifies a signature against this public key and message.
251    pub fn verify(&self, message: Word, signature: &Signature) -> bool {
252        let message_digest = hash_message(message);
253        self.verify_prehash(message_digest, signature)
254    }
255
256    /// Verifies a signature against this public key and pre-hashed message.
257    pub fn verify_prehash(&self, message_digest: [u8; 32], signature: &Signature) -> bool {
258        let signature_inner = ecdsa::Signature::from_scalars(*signature.r(), *signature.s());
259
260        match signature_inner {
261            Ok(signature) => self.inner.verify_prehash(&message_digest, &signature).is_ok(),
262            Err(_) => false,
263        }
264    }
265
266    /// Recovers from the signature the public key associated to the secret key used to sign the
267    /// message.
268    pub fn recover_from(message: Word, signature: &Signature) -> Result<Self, PublicKeyError> {
269        let message_digest = hash_message(message);
270        Self::recover_from_prehash(message_digest, signature)
271    }
272
273    /// Recovers the public key associated with a signature over a pre-hashed message.
274    ///
275    /// # Security
276    ///
277    /// `message_digest` must be produced by a cryptographically secure hash of the intended
278    /// message. If an attacker can choose it as arbitrary algebraic data, they can construct a
279    /// signature that recovers a target public key without knowing the corresponding secret key.
280    ///
281    /// Recovery returns a key consistent with the supplied digest and signature; it does not by
282    /// itself authenticate an identity. Before authorizing an action, callers must compare the
283    /// recovered key with an expected key from trusted state.
284    pub fn recover_from_prehash(
285        message_digest: [u8; 32],
286        signature: &Signature,
287    ) -> Result<Self, PublicKeyError> {
288        let signature_data = ecdsa::Signature::from_scalars(*signature.r(), *signature.s())
289            .map_err(|_| PublicKeyError::RecoveryFailed)?;
290
291        let verifying_key = VerifyingKey::recover_from_prehash(
292            &message_digest,
293            &signature_data,
294            RecoveryId::from_byte(signature.v()).ok_or(PublicKeyError::RecoveryFailed)?,
295        )
296        .map_err(|_| PublicKeyError::RecoveryFailed)?;
297
298        Ok(Self { inner: verifying_key })
299    }
300
301    /// Creates a public key from SPKI ASN.1 DER format bytes.
302    ///
303    /// # Arguments
304    /// * `bytes` - SPKI ASN.1 DER format bytes
305    pub fn from_der(bytes: &[u8]) -> Result<Self, DeserializationError> {
306        let verifying_key = VerifyingKey::from_public_key_der(bytes)
307            .map_err(|err| DeserializationError::InvalidValue(err.to_string()))?;
308        Ok(PublicKey { inner: verifying_key })
309    }
310}
311
312impl SequentialCommit for PublicKey {
313    type Commitment = Word;
314
315    fn to_elements(&self) -> Vec<Felt> {
316        affine_point_to_elements(self.as_affine()).to_vec()
317    }
318}
319
320#[derive(Debug, Error)]
321pub enum PublicKeyError {
322    #[error("Could not recover the public key from the message and signature")]
323    RecoveryFailed,
324}
325
326// SIGNATURE
327// ================================================================================================
328
329/// ECDSA signature over secp256k1 curve using Keccak to hash the messages when signing.
330///
331/// ## Serialization Formats
332///
333/// This implementation supports two serialization formats:
334///
335/// ### Custom Format (65 bytes):
336/// - Bytes 0-31: r component (32 bytes, big-endian)
337/// - Bytes 32-63: s component (32 bytes, big-endian)
338/// - Byte 64: recovery ID (v) - values 0-3
339///
340/// ### SEC1 Format (64 bytes):
341/// - Bytes 0-31: r component (32 bytes, big-endian)
342/// - Bytes 32-63: s component (32 bytes, big-endian)
343/// - Note: Recovery ID
344///
345/// # Examples
346///
347/// ```
348/// use miden_crypto::{
349///     Felt, Word,
350///     dsa::ecdsa_k256_keccak::{Signature, SigningKey},
351/// };
352/// use miden_serde_utils::{Deserializable, Serializable};
353/// use rand::SeedableRng;
354/// use rand_chacha::ChaCha20Rng;
355///
356/// let mut rng = ChaCha20Rng::from_seed([7; 32]);
357/// let signing_key = SigningKey::with_rng(&mut rng);
358/// let message = Word::new([
359///     Felt::new_unchecked(1),
360///     Felt::new_unchecked(2),
361///     Felt::new_unchecked(3),
362///     Felt::new_unchecked(4),
363/// ]);
364///
365/// let signature = signing_key.sign(message);
366/// let encoded = signature.to_bytes();
367///
368/// assert_eq!(encoded.len(), 65);
369/// assert_eq!(Signature::read_from_bytes(&encoded).unwrap(), signature);
370/// ```
371#[derive(Debug, Clone, PartialEq, Eq)]
372pub struct Signature {
373    r: [u8; SCALARS_SIZE_BYTES],
374    s: [u8; SCALARS_SIZE_BYTES],
375    v: u8,
376}
377
378impl Signature {
379    /// Returns the `r` scalar of this signature.
380    pub fn r(&self) -> &[u8; SCALARS_SIZE_BYTES] {
381        &self.r
382    }
383
384    /// Returns the `s` scalar of this signature.
385    pub fn s(&self) -> &[u8; SCALARS_SIZE_BYTES] {
386        &self.s
387    }
388
389    /// Returns the `v` component of this signature, which is a `u8` representing the recovery id.
390    pub fn v(&self) -> u8 {
391        self.v
392    }
393
394    /// Verifies this signature against a message and public key.
395    pub fn verify(&self, message: Word, pub_key: &PublicKey) -> bool {
396        pub_key.verify(message, self)
397    }
398
399    /// Converts signature to SEC1 format (standard 64-byte r||s format).
400    ///
401    /// This format is the standard one used by most ECDSA libraries but loses the recovery ID.
402    pub fn to_sec1_bytes(&self) -> [u8; SIGNATURE_STANDARD_BYTES] {
403        let mut bytes = [0u8; 2 * SCALARS_SIZE_BYTES];
404        bytes[0..SCALARS_SIZE_BYTES].copy_from_slice(self.r());
405        bytes[SCALARS_SIZE_BYTES..2 * SCALARS_SIZE_BYTES].copy_from_slice(self.s());
406        bytes
407    }
408
409    /// Creates a signature from SEC1 format bytes with a given recovery id.
410    ///
411    /// # Arguments
412    /// * `bytes` - 64-byte array containing r and s components
413    /// * `recovery_id` - recovery ID (0-3)
414    pub fn from_sec1_bytes_and_recovery_id(
415        bytes: [u8; SIGNATURE_STANDARD_BYTES],
416        recovery_id: u8,
417    ) -> Result<Self, DeserializationError> {
418        let mut r = [0u8; SCALARS_SIZE_BYTES];
419        let mut s = [0u8; SCALARS_SIZE_BYTES];
420        r.copy_from_slice(&bytes[0..SCALARS_SIZE_BYTES]);
421        s.copy_from_slice(&bytes[SCALARS_SIZE_BYTES..2 * SCALARS_SIZE_BYTES]);
422
423        if recovery_id > 3 {
424            return Err(DeserializationError::InvalidValue(r#"Invalid recovery ID"#.to_string()));
425        }
426
427        Ok(Signature { r, s, v: recovery_id })
428    }
429
430    /// Creates a signature from ASN.1 DER format bytes with a given recovery id.
431    ///
432    /// # Arguments
433    /// * `bytes` - ASN.1 DER format bytes
434    /// * `recovery_id` - recovery ID (0-3)
435    pub fn from_der(bytes: &[u8], mut recovery_id: u8) -> Result<Self, DeserializationError> {
436        if recovery_id > 3 {
437            return Err(DeserializationError::InvalidValue(r#"Invalid recovery ID"#.to_string()));
438        }
439
440        let sig = ecdsa::Signature::from_der(bytes)
441            .map_err(|err| DeserializationError::InvalidValue(err.to_string()))?;
442
443        // Normalize signature into "low s" form.
444        // See https://github.com/bitcoin/bips/blob/master/bip-0062.mediawiki.
445        let high_s = sig.s().is_high();
446        if bool::from(high_s) {
447            // Replacing s with (n - s) corresponds to negating the ephemeral point R
448            // (i.e. R -> -R), which flips the y-parity of R. A recoverable signature's
449            // `v` encodes that y-parity in its LSB, so we must toggle only that bit to
450            // preserve recoverability.
451            recovery_id ^= 1;
452        }
453        let sig = sig.normalize_s();
454
455        let (r, s) = sig.split_scalars();
456
457        Ok(Signature {
458            r: <[u8; SCALARS_SIZE_BYTES]>::from(r.to_bytes()),
459            s: <[u8; SCALARS_SIZE_BYTES]>::from(s.to_bytes()),
460            v: recovery_id,
461        })
462    }
463}
464
465// SERIALIZATION / DESERIALIZATION
466// ================================================================================================
467
468impl Serializable for SecretKey {
469    fn write_into<W: ByteWriter>(&self, target: &mut W) {
470        let mut buffer = Vec::with_capacity(SECRET_KEY_BYTES);
471        let sk_bytes: [u8; SECRET_KEY_BYTES] = self.inner.to_bytes().into();
472        buffer.extend_from_slice(&sk_bytes);
473
474        target.write_bytes(&buffer);
475    }
476}
477
478impl Deserializable for SecretKey {
479    fn read_from<R: ByteReader>(source: &mut R) -> Result<Self, DeserializationError> {
480        let bytes = read_sensitive_array::<SECRET_KEY_BYTES, _>(source)?;
481
482        let signing_key = ecdsa::SigningKey::from_slice(bytes.as_slice())
483            .map_err(|_| DeserializationError::InvalidValue("Invalid secret key".to_string()))?;
484
485        Ok(Self { inner: signing_key })
486    }
487}
488
489impl Serializable for PublicKey {
490    fn write_into<W: ByteWriter>(&self, target: &mut W) {
491        let encoded = self.inner.to_sec1_point(true);
492        target.write_bytes(encoded.as_bytes());
493    }
494}
495
496impl Deserializable for PublicKey {
497    fn read_from<R: ByteReader>(source: &mut R) -> Result<Self, DeserializationError> {
498        let bytes: [u8; PUBLIC_KEY_BYTES] = source.read_array()?;
499
500        let verifying_key = VerifyingKey::from_sec1_bytes(&bytes)
501            .map_err(|_| DeserializationError::InvalidValue("Invalid public key".to_string()))?;
502
503        Ok(Self { inner: verifying_key })
504    }
505}
506
507impl fmt::Display for PublicKey {
508    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
509        crate::utils::write_hex(f, &self.to_bytes())
510    }
511}
512
513impl Serializable for Signature {
514    fn write_into<W: ByteWriter>(&self, target: &mut W) {
515        let mut bytes = [0u8; SIGNATURE_BYTES];
516        bytes[0..SCALARS_SIZE_BYTES].copy_from_slice(self.r());
517        bytes[SCALARS_SIZE_BYTES..2 * SCALARS_SIZE_BYTES].copy_from_slice(self.s());
518        bytes[2 * SCALARS_SIZE_BYTES] = self.v();
519        target.write_bytes(&bytes);
520    }
521}
522
523impl Deserializable for Signature {
524    fn read_from<R: ByteReader>(source: &mut R) -> Result<Self, DeserializationError> {
525        let r: [u8; SCALARS_SIZE_BYTES] = source.read_array()?;
526        let s: [u8; SCALARS_SIZE_BYTES] = source.read_array()?;
527        let v: u8 = source.read_u8()?;
528
529        if v > 3 {
530            Err(DeserializationError::InvalidValue(r#"Invalid recovery ID"#.to_string()))
531        } else {
532            Ok(Signature { r, s, v })
533        }
534    }
535}
536
537impl fmt::Display for Signature {
538    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
539        crate::utils::write_hex(f, &self.to_bytes())
540    }
541}
542
543// HELPER
544// ================================================================================================
545
546fn affine_point_to_elements(point: &AffinePoint) -> [Felt; 16] {
547    let qx = be_bytes_to_le_u32_limbs(point.x().as_ref());
548    let qy = be_bytes_to_le_u32_limbs(point.y().as_ref());
549
550    core::array::from_fn(|idx| {
551        if idx < 8 {
552            Felt::from_u32(qx[idx])
553        } else {
554            Felt::from_u32(qy[idx - 8])
555        }
556    })
557}
558
559fn be_bytes_to_le_u32_limbs(bytes: &[u8]) -> [u32; 8] {
560    debug_assert_eq!(bytes.len(), SCALARS_SIZE_BYTES);
561    core::array::from_fn(|idx| {
562        let start = SCALARS_SIZE_BYTES - 4 * (idx + 1);
563        u32::from_be_bytes(bytes[start..start + 4].try_into().expect("chunk is exactly 4 bytes"))
564    })
565}
566
567/// Hashes a word message using Keccak.
568fn hash_message(message: Word) -> [u8; 32] {
569    use sha3::{Digest, Keccak256};
570    let mut hasher = Keccak256::new();
571    let message_bytes: [u8; 32] = message.into();
572    hasher.update(message_bytes);
573    hasher.finalize().into()
574}
miden_crypto/dsa/ecdsa_k256_keccak/mod.rs

miden_crypto/dsa/ecdsa_k256_keccak/
mod.rs
