ecdsa/
hazmat.rs

1//! Low-level ECDSA primitives.
2//!
3//! <div class="warning">
4//! <b>Security️ Warning: Hazardous Materials!</b>
5//!
6//! YOU PROBABLY DON'T WANT TO USE THESE!
7//!
8//! These primitives are easy-to-misuse low-level interfaces.
9//!
10//! If you are an end user / non-expert in cryptography, do not use these!
11//! Failure to use them correctly can lead to catastrophic failures including
12//! FULL PRIVATE KEY RECOVERY!
13//! </div>
14
15use crate::{EcdsaCurve, Error, Result};
16use core::cmp;
17use elliptic_curve::{FieldBytes, array::typenum::Unsigned};
18
19#[cfg(feature = "algorithm")]
20use {
21    crate::{RecoveryId, Signature, SignatureSize},
22    elliptic_curve::{
23        CurveArithmetic, NonZeroScalar, ProjectivePoint, Scalar,
24        array::ArraySize,
25        ff::PrimeField,
26        field,
27        group::{Curve as _, Group},
28        ops::{Invert, MulByGeneratorVartime, Reduce},
29        point::AffineCoordinates,
30        scalar::IsHigh,
31    },
32};
33
34#[cfg(feature = "digest")]
35use digest::{Digest, FixedOutput, FixedOutputReset, common::BlockSizeUser};
36
37/// Bind a preferred [`Digest`] algorithm to an elliptic curve type.
38///
39/// Generally there is a preferred variety of the SHA-2 family used with ECDSA
40/// for a particular elliptic curve.
41#[cfg(feature = "digest")]
42pub trait DigestAlgorithm: EcdsaCurve {
43    /// Preferred digest to use when computing ECDSA signatures for this
44    /// elliptic curve. This is typically a member of the SHA-2 family.
45    type Digest: BlockSizeUser + Digest + FixedOutput + FixedOutputReset;
46}
47
48/// Partial implementation of the `bits2int` function as defined in
49/// [RFC6979 § 2.3.2] as well as [SEC1] § 2.3.8.
50///
51/// This is used to convert a message digest whose size may be smaller or
52/// larger than the size of the curve's scalar field into a serialized
53/// (unreduced) field element.
54///
55/// [RFC6979 § 2.3.2]: https://datatracker.ietf.org/doc/html/rfc6979#section-2.3.2
56/// [SEC1]: https://www.secg.org/sec1-v2.pdf
57pub fn bits2field<C: EcdsaCurve>(bits: &[u8]) -> Result<FieldBytes<C>> {
58    // Absolute 128-bit / 16-byte minimum to catch egregious digest misuse
59    // without rejecting legitimate combinations like SHA-256 with P-521
60    // (see e.g. XML Signature, which permits such pairings).
61    if bits.len() < 16 {
62        return Err(Error::new());
63    }
64
65    let mut field_bytes = FieldBytes::<C>::default();
66
67    match bits.len().cmp(&C::FieldBytesSize::USIZE) {
68        cmp::Ordering::Equal => field_bytes.copy_from_slice(bits),
69        cmp::Ordering::Less => {
70            // If bits is smaller than the field size, pad with zeroes on the left
71            field_bytes[(C::FieldBytesSize::USIZE - bits.len())..].copy_from_slice(bits);
72        }
73        cmp::Ordering::Greater => {
74            // If bits is larger than the field size, truncate
75            field_bytes.copy_from_slice(&bits[..C::FieldBytesSize::USIZE]);
76        }
77    }
78
79    Ok(field_bytes)
80}
81
82/// Sign a prehashed message digest using the provided secret scalar and
83/// ephemeral scalar, returning an ECDSA signature.
84///
85/// Accepts the following arguments:
86///
87/// - `d`: signing key. MUST BE UNIFORMLY RANDOM!!!
88/// - `k`: ephemeral scalar value. MUST BE UNIFORMLY RANDOM!!!
89/// - `z`: message digest to be signed. MUST BE OUTPUT OF A CRYPTOGRAPHICALLY
90///   SECURE DIGEST ALGORITHM!!!
91///
92/// # Low-S Normalization
93///
94/// This function will apply low-S normalization if `<C as EcdsaCurve>::NORMALIZE_S` is true.
95///
96/// # Returns
97///
98/// ECDSA [`Signature`] and a [`RecoveryId`] which can be used to recover the verifying key for a
99/// given signature.
100///
101/// # Errors
102///
103/// This will return an error if a zero-scalar was generated. It can be tried again with a
104/// different `k`.
105#[cfg(feature = "algorithm")]
106#[allow(non_snake_case)]
107pub fn sign_prehashed<C>(
108    d: &NonZeroScalar<C>,
109    k: &NonZeroScalar<C>,
110    z: &FieldBytes<C>,
111) -> Result<(Signature<C>, RecoveryId)>
112where
113    C: EcdsaCurve + CurveArithmetic,
114    SignatureSize<C>: ArraySize,
115{
116    let z = Scalar::<C>::reduce(z);
117
118    // Compute scalar inversion of 𝑘.
119    let k_inv = k.invert();
120
121    // Compute 𝑹 = 𝑘×𝑮.
122    let R = ProjectivePoint::<C>::mul_by_generator(k).to_affine();
123
124    // Lift x-coordinate of 𝑹 (element of base field) into a serialized big
125    // integer, then reduce it into an element of the scalar field.
126    let r = Scalar::<C>::reduce(&R.x());
127
128    // Compute 𝒔 as a signature over 𝒓 and 𝒛.
129    let s = *k_inv * (z + (r * d.as_ref()));
130
131    // NOTE: `Signature::from_scalars` checks that both `r` and `s` are non-zero.
132    let mut signature = Signature::from_scalars(r, s)?;
133
134    // Compute recovery ID.
135    let x_is_reduced = r.to_repr() != R.x();
136    let y_is_odd = R.y_is_odd();
137    let mut recovery_id = RecoveryId::new(y_is_odd.into(), x_is_reduced);
138
139    // Apply low-S normalization if the curve is configured for it
140    if C::NORMALIZE_S {
141        recovery_id.0 ^= s.is_high().unwrap_u8();
142        signature = signature.normalize_s();
143    }
144
145    Ok((signature, recovery_id))
146}
147
148/// Try to sign the given message digest deterministically using the method
149/// described in [RFC6979] for computing ECDSA ephemeral scalar `k`.
150///
151/// Accepts the following parameters:
152/// - `d`: signing key. MUST BE UNIFORMLY RANDOM!!!
153/// - `z`: message digest to be signed, i.e. `H(m)`. Does not have to be reduced in advance.
154/// - `ad`: optional additional data, e.g. added entropy from an RNG
155///
156/// # Errors
157///
158/// This will return an error if a zero-scalar was generated. It can be tried again with different
159/// entropy `ad`.
160///
161/// [RFC6979]: https://datatracker.ietf.org/doc/html/rfc6979
162#[cfg(feature = "algorithm")]
163pub fn sign_prehashed_rfc6979<C, D>(
164    d: &NonZeroScalar<C>,
165    z: &FieldBytes<C>,
166    ad: &[u8],
167) -> Result<(Signature<C>, RecoveryId)>
168where
169    C: EcdsaCurve + CurveArithmetic,
170    D: Digest + BlockSizeUser + FixedOutput + FixedOutputReset,
171    SignatureSize<C>: ArraySize,
172{
173    // From RFC6979 § 2.4:
174    //
175    // H(m) is transformed into an integer modulo q using the bits2int
176    // transform and an extra modular reduction:
177    //
178    // h = bits2int(H(m)) mod q
179    let z2 = Scalar::<C>::reduce(z);
180
181    let k = NonZeroScalar::<C>::from_repr(rfc6979::generate_k::<D, _>(
182        &d.to_repr(),
183        &field::uint_to_bytes::<C>(&C::ORDER),
184        &z2.to_repr(),
185        ad,
186    ))
187    .unwrap();
188
189    sign_prehashed(d, &k, z)
190}
191
192/// Verify the prehashed message against the provided ECDSA signature.
193///
194/// Accepts the following arguments:
195///
196/// - `q`: public key with which to verify the signature.
197/// - `z`: message digest to be verified. MUST BE OUTPUT OF A CRYPTOGRAPHICALLY SECURE DIGEST
198///   ALGORITHM!!!
199/// - `sig`: signature to be verified against the key and message.
200#[cfg(feature = "algorithm")]
201pub fn verify_prehashed<C>(
202    q: &ProjectivePoint<C>,
203    z: &FieldBytes<C>,
204    sig: &Signature<C>,
205) -> Result<()>
206where
207    C: EcdsaCurve + CurveArithmetic,
208    SignatureSize<C>: ArraySize,
209{
210    if C::NORMALIZE_S && sig.s().is_high().into() {
211        return Err(Error::new());
212    }
213
214    let z = Scalar::<C>::reduce(z);
215    let (r, s) = sig.split_scalars();
216    let s_inv = *s.invert_vartime();
217    let u1 = z * s_inv;
218    let u2 = *r * s_inv;
219    let x = ProjectivePoint::<C>::mul_by_generator_and_mul_add_vartime(&u1, &u2, q)
220        .to_affine()
221        .x();
222
223    if *r == Scalar::<C>::reduce(&x) {
224        Ok(())
225    } else {
226        Err(Error::new())
227    }
228}
229
230#[cfg(all(test, feature = "dev"))]
231mod tests {
232    use super::bits2field;
233    use elliptic_curve::dev::MockCurve;
234    use hex_literal::hex;
235
236    #[test]
237    fn bits2field_too_small() {
238        assert!(bits2field::<MockCurve>(b"").is_err());
239        // 15 bytes is one short of the 128-bit absolute floor.
240        let prehash = hex!("AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA");
241        assert!(bits2field::<MockCurve>(&prehash).is_err());
242    }
243
244    #[test]
245    fn bits2field_size_less() {
246        let prehash = hex!("AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA");
247        let field_bytes = bits2field::<MockCurve>(&prehash).expect("field bytes");
248        assert_eq!(
249            field_bytes.as_slice(),
250            &hex!("00000000000000000000000000000000AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA")
251        );
252    }
253
254    #[test]
255    fn bits2field_size_eq() {
256        let prehash = hex!("AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA");
257        let field_bytes = bits2field::<MockCurve>(&prehash).expect("field bytes");
258        assert_eq!(field_bytes.as_slice(), &prehash);
259    }
260
261    #[test]
262    fn bits2field_size_greater() {
263        let prehash = hex!(
264            "AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAABBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBB"
265        );
266        let field_bytes = bits2field::<MockCurve>(&prehash).expect("field bytes");
267        assert_eq!(
268            field_bytes.as_slice(),
269            &hex!("AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA")
270        );
271    }
272}
ecdsa/hazmat.rs

ecdsa/
hazmat.rs
