ecdsa/
hazmat.rs

1//! Low-level ECDSA primitives.
2//!
3//! # ⚠️ Warning: Hazmat!
4//!
5//! YOU PROBABLY DON'T WANT TO USE THESE!
6//!
7//! These primitives are easy-to-misuse low-level interfaces.
8//!
9//! If you are an end user / non-expert in cryptography, do not use these!
10//! Failure to use them correctly can lead to catastrophic failures including
11//! FULL PRIVATE KEY RECOVERY!
12
13use crate::{Error, Result};
14use core::cmp;
15use elliptic_curve::{generic_array::typenum::Unsigned, FieldBytes, PrimeCurve};
16
17#[cfg(feature = "arithmetic")]
18use {
19    crate::{RecoveryId, SignatureSize},
20    elliptic_curve::{
21        ff::{Field, PrimeField},
22        group::{Curve as _, Group},
23        ops::{Invert, LinearCombination, MulByGenerator, Reduce},
24        point::AffineCoordinates,
25        scalar::IsHigh,
26        subtle::CtOption,
27        CurveArithmetic, ProjectivePoint, Scalar,
28    },
29};
30
31#[cfg(feature = "digest")]
32use {
33    elliptic_curve::FieldBytesSize,
34    signature::{
35        digest::{core_api::BlockSizeUser, Digest, FixedOutput, FixedOutputReset},
36        PrehashSignature,
37    },
38};
39
40#[cfg(feature = "rfc6979")]
41use elliptic_curve::{FieldBytesEncoding, ScalarPrimitive};
42
43#[cfg(any(feature = "arithmetic", feature = "digest"))]
44use crate::{elliptic_curve::generic_array::ArrayLength, Signature};
45
46/// Try to sign the given prehashed message using ECDSA.
47///
48/// This trait is intended to be implemented on a type with access to the
49/// secret scalar via `&self`, such as particular curve's `Scalar` type.
50#[cfg(feature = "arithmetic")]
51pub trait SignPrimitive<C>:
52    AsRef<Self>
53    + Into<FieldBytes<C>>
54    + IsHigh
55    + PrimeField<Repr = FieldBytes<C>>
56    + Reduce<C::Uint, Bytes = FieldBytes<C>>
57    + Sized
58where
59    C: PrimeCurve + CurveArithmetic<Scalar = Self>,
60    SignatureSize<C>: ArrayLength<u8>,
61{
62    /// Try to sign the prehashed message.
63    ///
64    /// Accepts the following arguments:
65    ///
66    /// - `k`: ephemeral scalar value. MUST BE UNIFORMLY RANDOM!!!
67    /// - `z`: message digest to be signed. MUST BE OUTPUT OF A CRYPTOGRAPHICALLY
68    ///        SECURE DIGEST ALGORITHM!!!
69    ///
70    /// # Returns
71    ///
72    /// ECDSA [`Signature`] and, when possible/desired, a [`RecoveryId`]
73    /// which can be used to recover the verifying key for a given signature.
74    fn try_sign_prehashed<K>(
75        &self,
76        k: K,
77        z: &FieldBytes<C>,
78    ) -> Result<(Signature<C>, Option<RecoveryId>)>
79    where
80        K: AsRef<Self> + Invert<Output = CtOption<Self>>,
81    {
82        sign_prehashed(self, k, z).map(|(sig, recid)| (sig, (Some(recid))))
83    }
84
85    /// Try to sign the given message digest deterministically using the method
86    /// described in [RFC6979] for computing ECDSA ephemeral scalar `k`.
87    ///
88    /// Accepts the following parameters:
89    /// - `z`: message digest to be signed.
90    /// - `ad`: optional additional data, e.g. added entropy from an RNG
91    ///
92    /// [RFC6979]: https://datatracker.ietf.org/doc/html/rfc6979
93    #[cfg(feature = "rfc6979")]
94    fn try_sign_prehashed_rfc6979<D>(
95        &self,
96        z: &FieldBytes<C>,
97        ad: &[u8],
98    ) -> Result<(Signature<C>, Option<RecoveryId>)>
99    where
100        Self: From<ScalarPrimitive<C>> + Invert<Output = CtOption<Self>>,
101        D: Digest + BlockSizeUser + FixedOutput<OutputSize = FieldBytesSize<C>> + FixedOutputReset,
102    {
103        let k = Scalar::<C>::from_repr(rfc6979::generate_k::<D, _>(
104            &self.to_repr(),
105            &C::ORDER.encode_field_bytes(),
106            z,
107            ad,
108        ))
109        .unwrap();
110
111        self.try_sign_prehashed::<Self>(k, z)
112    }
113}
114
115/// Verify the given prehashed message using ECDSA.
116///
117/// This trait is intended to be implemented on type which can access
118/// the affine point represeting the public key via `&self`, such as a
119/// particular curve's `AffinePoint` type.
120#[cfg(feature = "arithmetic")]
121pub trait VerifyPrimitive<C>: AffineCoordinates<FieldRepr = FieldBytes<C>> + Copy + Sized
122where
123    C: PrimeCurve + CurveArithmetic<AffinePoint = Self>,
124    SignatureSize<C>: ArrayLength<u8>,
125{
126    /// Verify the prehashed message against the provided ECDSA signature.
127    ///
128    /// Accepts the following arguments:
129    ///
130    /// - `z`: message digest to be verified. MUST BE OUTPUT OF A
131    ///        CRYPTOGRAPHICALLY SECURE DIGEST ALGORITHM!!!
132    /// - `sig`: signature to be verified against the key and message
133    fn verify_prehashed(&self, z: &FieldBytes<C>, sig: &Signature<C>) -> Result<()> {
134        verify_prehashed(&ProjectivePoint::<C>::from(*self), z, sig)
135    }
136
137    /// Verify message digest against the provided signature.
138    #[cfg(feature = "digest")]
139    fn verify_digest<D>(&self, msg_digest: D, sig: &Signature<C>) -> Result<()>
140    where
141        D: FixedOutput<OutputSize = FieldBytesSize<C>>,
142    {
143        self.verify_prehashed(&msg_digest.finalize_fixed(), sig)
144    }
145}
146
147/// Bind a preferred [`Digest`] algorithm to an elliptic curve type.
148///
149/// Generally there is a preferred variety of the SHA-2 family used with ECDSA
150/// for a particular elliptic curve.
151///
152/// This trait can be used to specify it, and with it receive a blanket impl of
153/// [`PrehashSignature`], used by [`signature_derive`][1]) for the [`Signature`]
154/// type for a particular elliptic curve.
155///
156/// [1]: https://github.com/RustCrypto/traits/tree/master/signature/derive
157#[cfg(feature = "digest")]
158pub trait DigestPrimitive: PrimeCurve {
159    /// Preferred digest to use when computing ECDSA signatures for this
160    /// elliptic curve. This is typically a member of the SHA-2 family.
161    type Digest: BlockSizeUser
162        + Digest
163        + FixedOutput<OutputSize = FieldBytesSize<Self>>
164        + FixedOutputReset;
165}
166
167#[cfg(feature = "digest")]
168impl<C> PrehashSignature for Signature<C>
169where
170    C: DigestPrimitive,
171    <FieldBytesSize<C> as core::ops::Add>::Output: ArrayLength<u8>,
172{
173    type Digest = C::Digest;
174}
175
176/// Partial implementation of the `bits2int` function as defined in
177/// [RFC6979 § 2.3.2] as well as [SEC1] § 2.3.8.
178///
179/// This is used to convert a message digest whose size may be smaller or
180/// larger than the size of the curve's scalar field into a serialized
181/// (unreduced) field element.
182///
183/// [RFC6979 § 2.3.2]: https://datatracker.ietf.org/doc/html/rfc6979#section-2.3.2
184/// [SEC1]: https://www.secg.org/sec1-v2.pdf
185pub fn bits2field<C: PrimeCurve>(bits: &[u8]) -> Result<FieldBytes<C>> {
186    // Minimum allowed bits size is half the field size
187    if bits.len() < C::FieldBytesSize::USIZE / 2 {
188        return Err(Error::new());
189    }
190
191    let mut field_bytes = FieldBytes::<C>::default();
192
193    match bits.len().cmp(&C::FieldBytesSize::USIZE) {
194        cmp::Ordering::Equal => field_bytes.copy_from_slice(bits),
195        cmp::Ordering::Less => {
196            // If bits is smaller than the field size, pad with zeroes on the left
197            field_bytes[(C::FieldBytesSize::USIZE - bits.len())..].copy_from_slice(bits);
198        }
199        cmp::Ordering::Greater => {
200            // If bits is larger than the field size, truncate
201            field_bytes.copy_from_slice(&bits[..C::FieldBytesSize::USIZE]);
202        }
203    }
204
205    Ok(field_bytes)
206}
207
208/// Sign a prehashed message digest using the provided secret scalar and
209/// ephemeral scalar, returning an ECDSA signature.
210///
211/// Accepts the following arguments:
212///
213/// - `d`: signing key. MUST BE UNIFORMLY RANDOM!!!
214/// - `k`: ephemeral scalar value. MUST BE UNIFORMLY RANDOM!!!
215/// - `z`: message digest to be signed. MUST BE OUTPUT OF A CRYPTOGRAPHICALLY
216///        SECURE DIGEST ALGORITHM!!!
217///
218/// # Returns
219///
220/// ECDSA [`Signature`] and, when possible/desired, a [`RecoveryId`]
221/// which can be used to recover the verifying key for a given signature.
222#[cfg(feature = "arithmetic")]
223#[allow(non_snake_case)]
224pub fn sign_prehashed<C, K>(
225    d: &Scalar<C>,
226    k: K,
227    z: &FieldBytes<C>,
228) -> Result<(Signature<C>, RecoveryId)>
229where
230    C: PrimeCurve + CurveArithmetic,
231    K: AsRef<Scalar<C>> + Invert<Output = CtOption<Scalar<C>>>,
232    SignatureSize<C>: ArrayLength<u8>,
233{
234    // TODO(tarcieri): use `NonZeroScalar<C>` for `k`.
235    if k.as_ref().is_zero().into() {
236        return Err(Error::new());
237    }
238
239    let z = <Scalar<C> as Reduce<C::Uint>>::reduce_bytes(z);
240
241    // Compute scalar inversion of 𝑘
242    let k_inv = Option::<Scalar<C>>::from(k.invert()).ok_or_else(Error::new)?;
243
244    // Compute 𝑹 = 𝑘×𝑮
245    let R = ProjectivePoint::<C>::mul_by_generator(k.as_ref()).to_affine();
246
247    // Lift x-coordinate of 𝑹 (element of base field) into a serialized big
248    // integer, then reduce it into an element of the scalar field
249    let r = Scalar::<C>::reduce_bytes(&R.x());
250    let x_is_reduced = r.to_repr() != R.x();
251
252    // Compute 𝒔 as a signature over 𝒓 and 𝒛.
253    let s = k_inv * (z + (r * d));
254
255    // NOTE: `Signature::from_scalars` checks that both `r` and `s` are non-zero.
256    let signature = Signature::from_scalars(r, s)?;
257    let recovery_id = RecoveryId::new(R.y_is_odd().into(), x_is_reduced);
258    Ok((signature, recovery_id))
259}
260
261/// Verify the prehashed message against the provided ECDSA signature.
262///
263/// Accepts the following arguments:
264///
265/// - `q`: public key with which to verify the signature.
266/// - `z`: message digest to be verified. MUST BE OUTPUT OF A
267///        CRYPTOGRAPHICALLY SECURE DIGEST ALGORITHM!!!
268/// - `sig`: signature to be verified against the key and message.
269#[cfg(feature = "arithmetic")]
270pub fn verify_prehashed<C>(
271    q: &ProjectivePoint<C>,
272    z: &FieldBytes<C>,
273    sig: &Signature<C>,
274) -> Result<()>
275where
276    C: PrimeCurve + CurveArithmetic,
277    SignatureSize<C>: ArrayLength<u8>,
278{
279    let z = Scalar::<C>::reduce_bytes(z);
280    let (r, s) = sig.split_scalars();
281    let s_inv = *s.invert_vartime();
282    let u1 = z * s_inv;
283    let u2 = *r * s_inv;
284    let x = ProjectivePoint::<C>::lincomb(&ProjectivePoint::<C>::generator(), &u1, q, &u2)
285        .to_affine()
286        .x();
287
288    if *r == Scalar::<C>::reduce_bytes(&x) {
289        Ok(())
290    } else {
291        Err(Error::new())
292    }
293}
294
295#[cfg(test)]
296mod tests {
297    use super::bits2field;
298    use elliptic_curve::dev::MockCurve;
299    use hex_literal::hex;
300
301    #[test]
302    fn bits2field_too_small() {
303        assert!(bits2field::<MockCurve>(b"").is_err());
304    }
305
306    #[test]
307    fn bits2field_size_less() {
308        let prehash = hex!("AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA");
309        let field_bytes = bits2field::<MockCurve>(&prehash).unwrap();
310        assert_eq!(
311            field_bytes.as_slice(),
312            &hex!("00000000000000000000000000000000AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA")
313        );
314    }
315
316    #[test]
317    fn bits2field_size_eq() {
318        let prehash = hex!("AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA");
319        let field_bytes = bits2field::<MockCurve>(&prehash).unwrap();
320        assert_eq!(field_bytes.as_slice(), &prehash);
321    }
322
323    #[test]
324    fn bits2field_size_greater() {
325        let prehash = hex!("AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAABBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBB");
326        let field_bytes = bits2field::<MockCurve>(&prehash).unwrap();
327        assert_eq!(
328            field_bytes.as_slice(),
329            &hex!("AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA")
330        );
331    }
332}
ecdsa/hazmat.rs

ecdsa/
hazmat.rs
