//! Elliptic Curve Digital Signature Algorithm (ECDSA) for the STARK curve.
//!
//! This module provides implementations for ECDSA signature verification and public key recovery
//! specifically tailored for the STARK curve.
//!
//! Curve information:
//! * Curve equation: y² ≡ x³ + α·x + β (mod p)
//! * α = 1
//! * β = 0x6f21413efbe40de150e596d72f7a8c5609ad26c15c915c1f4cdfcb99cee9e89
//! * p = 0x0800000000000011000000000000000000000000000000000000000000000001 = 2^251 + 17 * 2^192 +
//! 1
//! Generator point:
//! * x = 0x1ef15c18599971b7beced415a40f0c7deacfd9b0d1819e03d723d8bc943cfca
//! * y = 0x5668060aa49730b7be4801df46ec62de53ecd11abe43a32873000c36e8dc1f
use crate::ec::{self, EcPointTrait, EcStateTrait};
use crate::math;
#[allow(unused_imports)]
use crate::option::OptionTrait;
#[allow(unused_imports)]
use crate::traits::{Into, TryInto};
#[allow(unused_imports)]
use crate::zeroable::IsZeroResult;
/// Verifies an ECDSA signature against a message hash and public key.
///
/// Note: the verification algorithm implemented by this function slightly deviates from the
/// standard ECDSA.
/// While this does not allow creating valid signatures if one does not possess the private key,
/// it means that the signature algorithm used should be modified accordingly.
/// This function validates that `s` and `r` are not 0 or equal to the curve order,
/// but does not check that `r, s < stark_curve::ORDER`, which should be checked by the caller.
/// Additionally, it does not prevent malleability attacks of using `s` as `stark_curve::ORDER - s`,
/// `stark_curve::ORDER + s` or `2 * stark_curve::ORDER - s` (when in felt252 range).
/// Those can be avoided by checking that `s <= stark_curve::ORDER / 2`.
///
/// # Arguments
/// * `message_hash` - The hash of the signed message
/// * `public_key` - The x-coordinate of the signer's public key point on the STARK curve
/// * `signature_r` - The r component of the ECDSA signature (x-coordinate of point R)
/// * `signature_s` - The s component of the ECDSA signature
///
/// # Returns
/// Returns `true` if the signature is valid, `false` otherwise.
///
/// # Examples
///
/// ```
/// use core::ecdsa::check_ecdsa_signature;
///
/// let message_hash = 0x2d6479c0758efbb5aa07d35ed5454d728637fceab7ba544d3ea95403a5630a8;
/// let pubkey = 0x1ef15c18599971b7beced415a40f0c7deacfd9b0d1819e03d723d8bc943cfca;
/// let r = 0x6ff7b413a8457ef90f326b5280600a4473fef49b5b1dcdfcd7f42ca7aa59c69;
/// let s = 0x23a9747ed71abc5cb956c0df44ee8638b65b3e9407deade65de62247b8fd77;
/// assert!(check_ecdsa_signature(message_hash, pubkey, r, s));
/// ```
// TODO(lior): Make this function nopanic once possible.
pub fn check_ecdsa_signature(
message_hash: felt252, public_key: felt252, signature_r: felt252, signature_s: felt252,
) -> bool {
if is_equivalent_to_zero(signature_s) || signature_r == ec::stark_curve::ORDER {
return false;
}
// Check that the public key is the x coordinate of a point on the curve and get such a point.
let Some(public_key_point) = EcPointTrait::new_nz_from_x(public_key) else {
return false;
};
// Check that `r` is the x coordinate of a point on the curve and get such a point.
// Note that this ensures that `r != 0`.
let Some(signature_r_point) = EcPointTrait::new_nz_from_x(signature_r) else {
return false;
};
// Retrieve the generator point.
let Some(gen_point) = generator_point() else {
return false;
};
// Initialize an EC state.
let init_ec = EcStateTrait::init();
// To verify ECDSA, obtain:
// zG = z * G, where z is the message and G is a generator of the EC.
// rQ = r * Q, where Q.x = public_key.
// sR = s * R, where R.x = r.
// and check that:
// zG +/- rQ = +/- sR, or more efficiently that:
// (zG +/- rQ).x = sR.x.
// Calculate `sR.x`.
let mut sR_state = init_ec.clone();
sR_state.add_mul(signature_s, signature_r_point);
let Some(sR_nz) = sR_state.finalize_nz() else {
return false;
};
let sR_x = sR_nz.x();
// Calculate a state with `z * G`.
let mut zG_state = init_ec.clone();
zG_state.add_mul(message_hash, gen_point);
// Calculate the point `r * Q`.
let mut rQ_state = init_ec;
rQ_state.add_mul(signature_r, public_key_point);
let Some(rQ) = rQ_state.finalize_nz() else {
// The zero case is not actually possible, as `signature_r` isn't 0.
return false;
};
// Check the `(zG + rQ).x = sR.x` case.
let mut zG_plus_eQ_state = zG_state.clone();
zG_plus_eQ_state.add(rQ);
if let Some(pt) = zG_plus_eQ_state.finalize_nz() && pt.x() == sR_x {
return true;
}
// Check the `(zG - rQ).x = sR.x` case.
let mut zG_minus_eQ_state = zG_state;
zG_minus_eQ_state.sub(rQ);
if let Some(pt) = zG_minus_eQ_state.finalize_nz() && pt.x() == sR_x {
return true;
}
false
}
/// Recovers the public key from an ECDSA signature and message hash.
///
/// Given a valid ECDSA signature, the original message hash, and the y-coordinate parity of point
/// R, this function recovers the signer's public key. This is useful in scenarios where you need to
/// verify a message has been signed by a specific public key.
///
/// # Arguments
/// * `message_hash` - The hash of the signed message
/// * `signature_r` - The r component of the ECDSA signature (x-coordinate of point R)
/// * `signature_s` - The s component of the ECDSA signature
/// * `y_parity` - The parity of the y-coordinate of point R (`true` for odd, `false` for even)
///
/// # Returns
/// Returns `Some(public_key)` containing the x-coordinate of the recovered public key point if
/// the signature is valid, `None` otherwise.
///
/// # Examples
///
/// ```
/// use core::ecdsa::recover_public_key;
///
/// let message_hash = 0x503f4bea29baee10b22a7f10bdc82dda071c977c1f25b8f3973d34e6b03b2c;
/// let signature_r = 0xbe96d72eb4f94078192c2e84d5230cde2a70f4b45c8797e2c907acff5060bb;
/// let signature_s = 0x677ae6bba6daf00d2631fab14c8acf24be6579f9d9e98f67aa7f2770e57a1f5;
/// assert!(
/// recover_public_key(:message_hash, :signature_r, :signature_s, y_parity: false)
/// .unwrap() == 0x7b7454acbe7845da996377f85eb0892044d75ae95d04d3325a391951f35d2ec,
/// )
/// ```
pub fn recover_public_key(
message_hash: felt252, signature_r: felt252, signature_s: felt252, y_parity: bool,
) -> Option<felt252> {
if is_equivalent_to_zero(signature_s) {
return None;
}
let r_point = EcPointTrait::new_nz_from_x(signature_r)?;
let gen_point = generator_point()?;
// a Valid signature should satisfy:
// zG + rQ = sR.
// Where:
// zG = z * G, z is the message and G is a generator of the EC.
// rQ = r * Q, Q.x = public_key.
// sR = s * R, where R.x = r and R.y is determined by y_parity.
//
// Hence:
// rQ = sR - zG.
// Q = (s/r)R - (z/r)G
// and we can recover the public key using:
// Q.x = ((s/r)R - (z/r)G).x.
let r_nz: u256 = signature_r.into();
let r_nz = r_nz.try_into()?;
use ec::stark_curve::ORDER as ORD;
const ORD_U256: u256 = ORD.into();
const ORD_NZ: NonZero<u256> = ORD_U256.try_into().unwrap();
let r_inv = math::u256_inv_mod(r_nz, ORD_NZ)?.into();
let s_div_r: felt252 = math::u256_mul_mod_n(signature_s.into(), r_inv, ORD_NZ).try_into()?;
let z_div_r: felt252 = math::u256_mul_mod_n(message_hash.into(), r_inv, ORD_NZ).try_into()?;
let mut state = EcStateTrait::init();
let ord = ORD;
state.add_mul(ord - z_div_r, gen_point);
// Checking if the actual parity of the point's y is different from the requested, and if so,
// flipping the multiplier instead of negating the point to match the requested parity.
let y: u256 = r_point.y().into();
let r_multiplier = if (y.low & 1 != 0) ^ y_parity {
ord - s_div_r
} else {
s_div_r
};
state.add_mul(r_multiplier, r_point);
Some(state.finalize_nz()?.x())
}
/// Checks if `value == 0` (mod stark_curve::ORDER).
fn is_equivalent_to_zero(value: felt252) -> bool {
// Note that `2 * ec::stark_curve::ORDER` is larger than the felt252 PRIME.
value == 0 || value == ec::stark_curve::ORDER
}
// TODO(orizi): Remove this function on next Sierra release.
/// Returns the generator point of the elliptic curve.
///
/// Note: Cannot actually fail, as the generator point is always valid.
#[cfg(not(sierra: "future"))]
fn generator_point() -> Option<ec::NonZeroEcPoint> {
EcPointTrait::new_nz(ec::stark_curve::GEN_X, ec::stark_curve::GEN_Y)
}
// TODO(orizi): Remove this function and use `generator::value()` directly on next Sierra release.
/// Returns the generator point of the elliptic curve.
///
/// Note: Cannot actually fail, as the generator point is always valid.
#[cfg(sierra: "future")]
fn generator_point() -> Option<ec::NonZeroEcPoint> {
Some(generator::value())
}
#[cfg(sierra: "future")]
mod generator {
use crate::ec;
mod v {
/// Const type variant for the EcPoint type.
pub extern type Const<T, const X: felt252, const Y: felt252>;
}
mod nz {
/// Non-zero const type variant for the EcPoint type.
pub extern type Const<T, C>;
}
/// Extern declaration for fetching the actual value.
extern fn const_as_immediate<T>() -> NonZero<ec::EcPoint> nopanic;
/// Returns the generator point of the elliptic curve.
pub fn value() -> ec::NonZeroEcPoint {
const_as_immediate::<
nz::Const<
ec::NonZeroEcPoint,
v::Const<ec::EcPoint, ec::stark_curve::GEN_X, ec::stark_curve::GEN_Y>,
>,
>()
}
}