cryptography/public_key/
dsa.rs

1//! Digital Signature Algorithm (`DSA`, FIPS 186-5).
2//!
3//! `DSA` is the signature analogue of the prime-order subgroup construction
4//! already used for `ElGamal`: choose a prime modulus `p`, a prime subgroup
5//! order `q` dividing `p - 1`, and a generator `g` of the order-`q` subgroup.
6//! Signing and verification then operate entirely modulo `q`, while the group
7//! actions still happen modulo `p`.
8
9use core::fmt;
10
11use crate::hash::Digest;
12use crate::public_key::bigint::{BigUint, MontgomeryCtx};
13use crate::public_key::io::{
14    decode_biguints, encode_biguints, pem_unwrap, pem_wrap, xml_unwrap, xml_wrap,
15};
16use crate::public_key::primes::{
17    generate_prime_order_group, is_probable_prime, mod_inverse, mod_pow, random_nonzero_below,
18};
19use crate::Csprng;
20use crate::Hmac;
21
22const DSA_PUBLIC_LABEL: &str = "CRYPTOGRAPHY DSA PUBLIC KEY";
23const DSA_PRIVATE_LABEL: &str = "CRYPTOGRAPHY DSA PRIVATE KEY";
24
25/// Public key for `DSA`.
26#[derive(Clone, Debug, Eq, PartialEq)]
27pub struct DsaPublicKey {
28    /// Prime modulus `p`.
29    p: BigUint,
30    /// Prime subgroup order `q`.
31    q: BigUint,
32    /// Generator `g` of the order-`q` subgroup.
33    g: BigUint,
34    /// Public component `y = g^x mod p`.
35    y: BigUint,
36    /// Cached Montgomery encoding of `g` modulo `p`.
37    g_mont: Option<BigUint>,
38    /// Cached Montgomery encoding of `y` modulo `p`.
39    y_mont: Option<BigUint>,
40    /// Cached Montgomery context for arithmetic modulo `p`.
41    p_ctx: Option<MontgomeryCtx>,
42    /// Cached Montgomery context for arithmetic modulo `q`.
43    q_ctx: Option<MontgomeryCtx>,
44}
45
46/// Private key for `DSA`.
47#[derive(Clone, Eq, PartialEq)]
48pub struct DsaPrivateKey {
49    /// Prime modulus `p`.
50    p: BigUint,
51    /// Prime subgroup order `q`.
52    q: BigUint,
53    /// Generator `g` of the order-`q` subgroup.
54    g: BigUint,
55    /// Secret exponent `x`.
56    x: BigUint,
57    /// Cached public component `y = g^x mod p`.
58    y: BigUint,
59    /// Cached Montgomery encoding of `g` modulo `p`.
60    g_mont: Option<BigUint>,
61    /// Cached Montgomery encoding of `y` modulo `p`.
62    y_mont: Option<BigUint>,
63    /// Cached Montgomery context for arithmetic modulo `p`.
64    p_ctx: Option<MontgomeryCtx>,
65    /// Cached Montgomery context for arithmetic modulo `q`.
66    q_ctx: Option<MontgomeryCtx>,
67}
68
69/// Raw `DSA` signature pair `(r, s)`.
70#[derive(Clone, Debug, Eq, PartialEq)]
71pub struct DsaSignature {
72    r: BigUint,
73    s: BigUint,
74}
75
76/// Namespace wrapper for the `DSA` construction.
77pub struct Dsa;
78
79impl DsaPublicKey {
80    /// Return the prime modulus.
81    #[must_use]
82    pub fn modulus(&self) -> &BigUint {
83        &self.p
84    }
85
86    /// Return the prime subgroup order.
87    #[must_use]
88    pub fn subgroup_order(&self) -> &BigUint {
89        &self.q
90    }
91
92    /// Return the subgroup generator.
93    #[must_use]
94    pub fn generator(&self) -> &BigUint {
95        &self.g
96    }
97
98    /// Return the public component `y = g^x mod p`.
99    #[must_use]
100    pub fn public_component(&self) -> &BigUint {
101        &self.y
102    }
103
104    /// Hash one message with `H`, then verify the resulting digest.
105    #[must_use]
106    pub fn verify_message<H: Digest>(&self, message: &[u8], signature: &DsaSignature) -> bool {
107        let digest = H::digest(message);
108        self.verify(&digest, signature)
109    }
110
111    /// Hash one message with `H`, then verify a serialized signature.
112    #[must_use]
113    pub fn verify_message_bytes<H: Digest>(&self, message: &[u8], signature: &[u8]) -> bool {
114        let digest = H::digest(message);
115        self.verify_bytes(&digest, signature)
116    }
117
118    /// Verify a signature over an explicit integer representative.
119    #[must_use]
120    pub fn verify_digest_scalar(&self, hash: &BigUint, signature: &DsaSignature) -> bool {
121        if signature.r.is_zero()
122            || signature.s.is_zero()
123            || signature.r >= self.q
124            || signature.s >= self.q
125        {
126            return false;
127        }
128
129        let Some(w) = mod_inverse(&signature.s, &self.q) else {
130            return false;
131        };
132        // FIPS 186-5 verification variables: `w = s^-1 mod q`,
133        // `z = leftmost-N-bits(H(M)) mod q`, then `u1 = z * w mod q` and
134        // `u2 = r * w mod q`.
135        let z = hash.modulo(&self.q);
136        let u1 = if let Some(ctx) = &self.q_ctx {
137            ctx.mul(&z, &w)
138        } else {
139            BigUint::mod_mul(&z, &w, &self.q)
140        };
141        let u2 = if let Some(ctx) = &self.q_ctx {
142            ctx.mul(&signature.r, &w)
143        } else {
144            BigUint::mod_mul(&signature.r, &w, &self.q)
145        };
146
147        let g_term = if let (Some(ctx), Some(g_mont)) = (&self.p_ctx, &self.g_mont) {
148            ctx.pow_encoded(g_mont, &u1)
149        } else {
150            mod_pow(&self.g, &u1, &self.p)
151        };
152        let y_term = if let (Some(ctx), Some(y_mont)) = (&self.p_ctx, &self.y_mont) {
153            ctx.pow_encoded(y_mont, &u2)
154        } else {
155            mod_pow(&self.y, &u2, &self.p)
156        };
157        let combined = if let Some(ctx) = &self.p_ctx {
158            ctx.mul(&g_term, &y_term)
159        } else {
160            BigUint::mod_mul(&g_term, &y_term, &self.p)
161        };
162
163        combined.modulo(&self.q) == signature.r
164    }
165
166    /// Verify a signature over the provided digest bytes.
167    ///
168    /// The digest is reduced to the leftmost `N = bits(q)` bits, matching the
169    /// DSA representative construction from the Digital Signature Standard.
170    #[must_use]
171    pub fn verify(&self, digest: &[u8], signature: &DsaSignature) -> bool {
172        self.verify_digest_scalar(&digest_to_scalar(digest, &self.q), signature)
173    }
174
175    /// Verify a byte-encoded signature produced by [`DsaPrivateKey::sign_bytes`].
176    #[must_use]
177    pub fn verify_bytes(&self, digest: &[u8], signature: &[u8]) -> bool {
178        let Some(signature) = DsaSignature::from_key_blob(signature) else {
179            return false;
180        };
181        self.verify(digest, &signature)
182    }
183
184    /// Encode the public key in the crate-defined binary format.
185    #[must_use]
186    pub fn to_key_blob(&self) -> Vec<u8> {
187        encode_biguints(&[&self.p, &self.q, &self.g, &self.y])
188    }
189
190    /// Decode the public key from the crate-defined binary format.
191    #[must_use]
192    pub fn from_key_blob(blob: &[u8]) -> Option<Self> {
193        let mut fields = decode_biguints(blob)?.into_iter();
194        let p = fields.next()?;
195        let q = fields.next()?;
196        let g = fields.next()?;
197        let y = fields.next()?;
198        if fields.next().is_some() || !validate_domain(&p, &q, &g) || y <= BigUint::one() || y >= p
199        {
200            return None;
201        }
202        let p_ctx = MontgomeryCtx::new(&p);
203        let q_ctx = MontgomeryCtx::new(&q);
204        let g_mont = p_ctx.as_ref().map(|ctx| ctx.encode(&g));
205        let y_mont = p_ctx.as_ref().map(|ctx| ctx.encode(&y));
206        Some(Self {
207            p,
208            q,
209            g,
210            y,
211            g_mont,
212            y_mont,
213            p_ctx,
214            q_ctx,
215        })
216    }
217
218    /// Encode the public key in PEM using the crate-defined label.
219    #[must_use]
220    pub fn to_pem(&self) -> String {
221        pem_wrap(DSA_PUBLIC_LABEL, &self.to_key_blob())
222    }
223
224    /// Encode the public key as the crate's flat XML form.
225    #[must_use]
226    pub fn to_xml(&self) -> String {
227        xml_wrap(
228            "DsaPublicKey",
229            &[
230                ("p", &self.p),
231                ("q", &self.q),
232                ("g", &self.g),
233                ("y", &self.y),
234            ],
235        )
236    }
237
238    /// Decode the public key from the crate-defined PEM label.
239    #[must_use]
240    pub fn from_pem(pem: &str) -> Option<Self> {
241        let blob = pem_unwrap(DSA_PUBLIC_LABEL, pem)?;
242        Self::from_key_blob(&blob)
243    }
244
245    /// Decode the public key from the crate's flat XML form.
246    #[must_use]
247    pub fn from_xml(xml: &str) -> Option<Self> {
248        let mut fields = xml_unwrap("DsaPublicKey", &["p", "q", "g", "y"], xml)?.into_iter();
249        let p = fields.next()?;
250        let q = fields.next()?;
251        let g = fields.next()?;
252        let y = fields.next()?;
253        if fields.next().is_some() || !validate_domain(&p, &q, &g) || y <= BigUint::one() || y >= p
254        {
255            return None;
256        }
257        let p_ctx = MontgomeryCtx::new(&p);
258        let q_ctx = MontgomeryCtx::new(&q);
259        let g_mont = p_ctx.as_ref().map(|ctx| ctx.encode(&g));
260        let y_mont = p_ctx.as_ref().map(|ctx| ctx.encode(&y));
261        Some(Self {
262            p,
263            q,
264            g,
265            y,
266            g_mont,
267            y_mont,
268            p_ctx,
269            q_ctx,
270        })
271    }
272}
273
274impl DsaPrivateKey {
275    /// Return the prime modulus.
276    #[must_use]
277    pub fn modulus(&self) -> &BigUint {
278        &self.p
279    }
280
281    /// Return the prime subgroup order.
282    #[must_use]
283    pub fn subgroup_order(&self) -> &BigUint {
284        &self.q
285    }
286
287    /// Return the subgroup generator.
288    #[must_use]
289    pub fn generator(&self) -> &BigUint {
290        &self.g
291    }
292
293    /// Return the private exponent `x`.
294    #[must_use]
295    pub fn exponent(&self) -> &BigUint {
296        &self.x
297    }
298
299    /// Derive the matching public key from this private key.
300    #[must_use]
301    pub fn to_public_key(&self) -> DsaPublicKey {
302        DsaPublicKey {
303            p: self.p.clone(),
304            q: self.q.clone(),
305            g: self.g.clone(),
306            y: self.y.clone(),
307            g_mont: self.g_mont.clone(),
308            y_mont: self.y_mont.clone(),
309            p_ctx: self.p_ctx.clone(),
310            q_ctx: self.q_ctx.clone(),
311        }
312    }
313
314    /// Sign with an explicit nonce `k`.
315    ///
316    /// `DSA` uses a fresh `k` in `[1, q)` for every signature. This lower-level
317    /// entry point keeps the arithmetic explicit for deterministic tests.
318    ///
319    /// Reusing the same `k` for two different messages with the same key
320    /// immediately reveals the private exponent. Outside of fixed vectors,
321    /// prefer [`Self::sign_digest`] or [`Self::sign_message`].
322    #[must_use]
323    pub fn sign_digest_with_nonce(&self, digest: &[u8], nonce: &BigUint) -> Option<DsaSignature> {
324        if nonce.is_zero() || nonce >= &self.q {
325            return None;
326        }
327
328        let z = digest_to_scalar(digest, &self.q);
329        let r = if let (Some(ctx), Some(g_mont)) = (&self.p_ctx, &self.g_mont) {
330            ctx.pow_encoded(g_mont, nonce)
331        } else {
332            mod_pow(&self.g, nonce, &self.p)
333        }
334        .modulo(&self.q);
335        if r.is_zero() {
336            return None;
337        }
338
339        let nonce_inv = mod_inverse(nonce, &self.q)?;
340        let xr = if let Some(ctx) = &self.q_ctx {
341            ctx.mul(&self.x, &r)
342        } else {
343            BigUint::mod_mul(&self.x, &r, &self.q)
344        };
345        let sum = z.add_ref(&xr).modulo(&self.q);
346        let s = if let Some(ctx) = &self.q_ctx {
347            ctx.mul(&nonce_inv, &sum)
348        } else {
349            BigUint::mod_mul(&nonce_inv, &sum, &self.q)
350        };
351        if s.is_zero() {
352            return None;
353        }
354
355        Some(DsaSignature { r, s })
356    }
357
358    /// Sign a pre-hashed digest using RFC 6979 deterministic nonce derivation.
359    #[must_use]
360    pub fn sign_digest<H: Digest>(&self, digest: &[u8]) -> Option<DsaSignature> {
361        let nonce = rfc6979_nonce::<H>(&self.q, &self.x, digest)?;
362        self.sign_digest_with_nonce(digest, &nonce)
363    }
364
365    /// Sign a digest using a fresh random nonce.
366    #[must_use]
367    pub fn sign_digest_with_rng<R: Csprng>(
368        &self,
369        digest: &[u8],
370        rng: &mut R,
371    ) -> Option<DsaSignature> {
372        loop {
373            // Retry only in the negligible edge cases where `r = 0` or
374            // `s = 0`; the fresh nonce changes the arithmetic path.
375            let nonce = random_nonzero_below(rng, &self.q)?;
376            if let Some(signature) = self.sign_digest_with_nonce(digest, &nonce) {
377                return Some(signature);
378            }
379        }
380    }
381
382    /// Hash one message with `H`, then sign deterministically.
383    #[must_use]
384    pub fn sign_message<H: Digest>(&self, message: &[u8]) -> Option<DsaSignature> {
385        let digest = H::digest(message);
386        self.sign_digest::<H>(&digest)
387    }
388
389    /// Hash one message with `H`, then sign with randomized nonces.
390    #[must_use]
391    pub fn sign_message_with_rng<H: Digest, R: Csprng>(
392        &self,
393        message: &[u8],
394        rng: &mut R,
395    ) -> Option<DsaSignature> {
396        let digest = H::digest(message);
397        self.sign_digest_with_rng(&digest, rng)
398    }
399
400    /// Sign a digest deterministically and return serialized signature bytes.
401    #[must_use]
402    pub fn sign_digest_bytes<H: Digest>(&self, digest: &[u8]) -> Option<Vec<u8>> {
403        let signature = self.sign_digest::<H>(digest)?;
404        Some(signature.to_key_blob())
405    }
406
407    /// Sign a digest with randomized nonces and return serialized signature bytes.
408    #[must_use]
409    pub fn sign_digest_bytes_with_rng<H: Digest, R: Csprng>(
410        &self,
411        digest: &[u8],
412        rng: &mut R,
413    ) -> Option<Vec<u8>> {
414        let signature = self.sign_digest_with_rng(digest, rng)?;
415        Some(signature.to_key_blob())
416    }
417
418    /// Hash one message with `H`, then sign and serialize deterministically.
419    #[must_use]
420    pub fn sign_message_bytes<H: Digest>(&self, message: &[u8]) -> Option<Vec<u8>> {
421        let signature = self.sign_message::<H>(message)?;
422        Some(signature.to_key_blob())
423    }
424
425    /// Hash one message with `H`, then sign and serialize with randomized nonces.
426    #[must_use]
427    pub fn sign_message_bytes_with_rng<H: Digest, R: Csprng>(
428        &self,
429        message: &[u8],
430        rng: &mut R,
431    ) -> Option<Vec<u8>> {
432        let signature = self.sign_message_with_rng::<H, R>(message, rng)?;
433        Some(signature.to_key_blob())
434    }
435
436    /// Encode the private key in the crate-defined binary format.
437    #[must_use]
438    pub fn to_key_blob(&self) -> Vec<u8> {
439        encode_biguints(&[&self.p, &self.q, &self.g, &self.x])
440    }
441
442    /// Decode the private key from the crate-defined binary format.
443    #[must_use]
444    pub fn from_key_blob(blob: &[u8]) -> Option<Self> {
445        let mut fields = decode_biguints(blob)?.into_iter();
446        let p = fields.next()?;
447        let q = fields.next()?;
448        let g = fields.next()?;
449        let x = fields.next()?;
450        if fields.next().is_some() || !validate_domain(&p, &q, &g) || x.is_zero() || x >= q {
451            return None;
452        }
453        let y = mod_pow(&g, &x, &p);
454        let p_ctx = MontgomeryCtx::new(&p);
455        let q_ctx = MontgomeryCtx::new(&q);
456        let g_mont = p_ctx.as_ref().map(|ctx| ctx.encode(&g));
457        let y_mont = p_ctx.as_ref().map(|ctx| ctx.encode(&y));
458        Some(Self {
459            p,
460            q,
461            g,
462            x,
463            y,
464            g_mont,
465            y_mont,
466            p_ctx,
467            q_ctx,
468        })
469    }
470
471    /// Encode the private key in PEM using the crate-defined label.
472    #[must_use]
473    pub fn to_pem(&self) -> String {
474        pem_wrap(DSA_PRIVATE_LABEL, &self.to_key_blob())
475    }
476
477    /// Encode the private key as the crate's flat XML form.
478    #[must_use]
479    pub fn to_xml(&self) -> String {
480        xml_wrap(
481            "DsaPrivateKey",
482            &[
483                ("p", &self.p),
484                ("q", &self.q),
485                ("g", &self.g),
486                ("x", &self.x),
487            ],
488        )
489    }
490
491    /// Decode the private key from the crate-defined PEM label.
492    #[must_use]
493    pub fn from_pem(pem: &str) -> Option<Self> {
494        let blob = pem_unwrap(DSA_PRIVATE_LABEL, pem)?;
495        Self::from_key_blob(&blob)
496    }
497
498    /// Decode the private key from the crate's flat XML form.
499    #[must_use]
500    pub fn from_xml(xml: &str) -> Option<Self> {
501        let mut fields = xml_unwrap("DsaPrivateKey", &["p", "q", "g", "x"], xml)?.into_iter();
502        let p = fields.next()?;
503        let q = fields.next()?;
504        let g = fields.next()?;
505        let x = fields.next()?;
506        if fields.next().is_some() || !validate_domain(&p, &q, &g) || x.is_zero() || x >= q {
507            return None;
508        }
509        let y = mod_pow(&g, &x, &p);
510        let p_ctx = MontgomeryCtx::new(&p);
511        let q_ctx = MontgomeryCtx::new(&q);
512        let g_mont = p_ctx.as_ref().map(|ctx| ctx.encode(&g));
513        let y_mont = p_ctx.as_ref().map(|ctx| ctx.encode(&y));
514        Some(Self {
515            p,
516            q,
517            g,
518            x,
519            y,
520            g_mont,
521            y_mont,
522            p_ctx,
523            q_ctx,
524        })
525    }
526}
527
528impl fmt::Debug for DsaPrivateKey {
529    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
530        f.write_str("DsaPrivateKey(<redacted>)")
531    }
532}
533
534impl DsaSignature {
535    /// Return the first signature component.
536    #[must_use]
537    pub fn r(&self) -> &BigUint {
538        &self.r
539    }
540
541    /// Return the second signature component.
542    #[must_use]
543    pub fn s(&self) -> &BigUint {
544        &self.s
545    }
546
547    /// Encode the signature as a DER `SEQUENCE` of `(r, s)`.
548    #[must_use]
549    pub fn to_key_blob(&self) -> Vec<u8> {
550        encode_biguints(&[&self.r, &self.s])
551    }
552
553    /// Decode a crate-defined binary `DSA` signature.
554    ///
555    /// Zero values are rejected immediately. The range checks against the
556    /// subgroup order `q` happen during verification because the signature
557    /// encoding does not carry `q`.
558    #[must_use]
559    pub fn from_key_blob(blob: &[u8]) -> Option<Self> {
560        let mut fields = decode_biguints(blob)?.into_iter();
561        let r = fields.next()?;
562        let s = fields.next()?;
563        if fields.next().is_some() || r.is_zero() || s.is_zero() {
564            return None;
565        }
566        Some(Self { r, s })
567    }
568}
569
570impl Dsa {
571    /// Derive a `DSA` key pair from explicit subgroup parameters and secret exponent.
572    #[must_use]
573    pub fn from_secret_exponent(
574        prime: &BigUint,
575        subgroup_order: &BigUint,
576        generator: &BigUint,
577        secret: &BigUint,
578    ) -> Option<(DsaPublicKey, DsaPrivateKey)> {
579        if !validate_domain(prime, subgroup_order, generator)
580            || secret.is_zero()
581            || secret >= subgroup_order
582        {
583            return None;
584        }
585
586        let public_component = mod_pow(generator, secret, prime);
587        let p_ctx = MontgomeryCtx::new(prime);
588        let q_ctx = MontgomeryCtx::new(subgroup_order);
589        let g_mont = p_ctx.as_ref().map(|ctx| ctx.encode(generator));
590        let y_mont = p_ctx.as_ref().map(|ctx| ctx.encode(&public_component));
591        Some((
592            DsaPublicKey {
593                p: prime.clone(),
594                q: subgroup_order.clone(),
595                g: generator.clone(),
596                y: public_component.clone(),
597                g_mont: g_mont.clone(),
598                y_mont: y_mont.clone(),
599                p_ctx: p_ctx.clone(),
600                q_ctx: q_ctx.clone(),
601            },
602            DsaPrivateKey {
603                p: prime.clone(),
604                q: subgroup_order.clone(),
605                g: generator.clone(),
606                x: secret.clone(),
607                y: public_component.clone(),
608                g_mont,
609                y_mont,
610                p_ctx,
611                q_ctx,
612            },
613        ))
614    }
615
616    /// Generate a `DSA` key pair over a prime-order subgroup.
617    #[must_use]
618    pub fn generate<R: Csprng>(rng: &mut R, bits: usize) -> Option<(DsaPublicKey, DsaPrivateKey)> {
619        let (prime, subgroup_order, _cofactor, generator) = generate_prime_order_group(rng, bits)?;
620        let secret = random_nonzero_below(rng, &subgroup_order)?;
621        let public_component = mod_pow(&generator, &secret, &prime);
622        let p_ctx = MontgomeryCtx::new(&prime);
623        let q_ctx = MontgomeryCtx::new(&subgroup_order);
624        let g_mont = p_ctx.as_ref().map(|ctx| ctx.encode(&generator));
625        let y_mont = p_ctx.as_ref().map(|ctx| ctx.encode(&public_component));
626        Some((
627            DsaPublicKey {
628                p: prime.clone(),
629                q: subgroup_order.clone(),
630                g: generator.clone(),
631                y: public_component.clone(),
632                g_mont: g_mont.clone(),
633                y_mont: y_mont.clone(),
634                p_ctx: p_ctx.clone(),
635                q_ctx: q_ctx.clone(),
636            },
637            DsaPrivateKey {
638                p: prime,
639                q: subgroup_order,
640                g: generator,
641                x: secret,
642                y: public_component.clone(),
643                g_mont,
644                y_mont,
645                p_ctx,
646                q_ctx,
647            },
648        ))
649    }
650}
651
652/// Validate the subgroup parameters used by `DSA`.
653///
654/// This checks that `p` and `q` are prime, that `q` divides `p - 1`, and that
655/// `g` lies in the order-`q` subgroup of `Z_p^*`.
656fn validate_domain(prime: &BigUint, subgroup_order: &BigUint, generator: &BigUint) -> bool {
657    if !is_probable_prime(prime) || !is_probable_prime(subgroup_order) {
658        return false;
659    }
660    if subgroup_order >= prime {
661        return false;
662    }
663    let p_minus_one = prime.sub_ref(&BigUint::one());
664    if !p_minus_one.modulo(subgroup_order).is_zero() {
665        return false;
666    }
667    if generator <= &BigUint::one() || generator >= prime {
668        return false;
669    }
670    let one = BigUint::one();
671    mod_pow(generator, subgroup_order, prime) == one
672}
673
674/// FIPS 186-5 digest representative reduction.
675///
676/// The standard keeps the leftmost `N = bits(q)` bits of the hash. The shift
677/// amount is derived from the original digest width, not the width after
678/// leading-zero trimming.
679fn digest_to_scalar(digest: &[u8], modulus: &BigUint) -> BigUint {
680    let mut value = BigUint::from_be_bytes(digest);
681    let hash_bits = digest.len() * 8;
682    let target_bits = modulus.bits();
683    if hash_bits > target_bits {
684        for _ in 0..(hash_bits - target_bits) {
685            value.shr1();
686        }
687    }
688    value
689}
690
691fn int_to_octets(value: &BigUint, len: usize) -> Vec<u8> {
692    let bytes = value.to_be_bytes();
693    if bytes.len() >= len {
694        return bytes[bytes.len() - len..].to_vec();
695    }
696    let mut out = vec![0u8; len];
697    out[len - bytes.len()..].copy_from_slice(&bytes);
698    out
699}
700
701fn bits_to_int(input: &[u8], target_bits: usize) -> BigUint {
702    let mut value = BigUint::from_be_bytes(input);
703    let input_bits = input.len() * 8;
704    if input_bits > target_bits {
705        for _ in 0..(input_bits - target_bits) {
706            value.shr1();
707        }
708    }
709    value
710}
711
712fn bits_to_octets(input: &[u8], q: &BigUint, q_bits: usize, ro_len: usize) -> Vec<u8> {
713    let z1 = bits_to_int(input, q_bits);
714    let z2 = z1.modulo(q);
715    int_to_octets(&z2, ro_len)
716}
717
718fn rfc6979_nonce<H: Digest>(q: &BigUint, x: &BigUint, digest: &[u8]) -> Option<BigUint> {
719    if q <= &BigUint::one() {
720        return None;
721    }
722
723    let q_bits = q.bits();
724    let ro_len = q_bits.div_ceil(8);
725    let bx = int_to_octets(x, ro_len);
726    let bh = bits_to_octets(digest, q, q_bits, ro_len);
727
728    let mut v = vec![0x01; H::OUTPUT_LEN];
729    let mut k = vec![0x00; H::OUTPUT_LEN];
730
731    let mut data = Vec::with_capacity(v.len() + 1 + bx.len() + bh.len());
732    data.extend_from_slice(&v);
733    data.push(0x00);
734    data.extend_from_slice(&bx);
735    data.extend_from_slice(&bh);
736    k = Hmac::<H>::compute(&k, &data);
737    v = Hmac::<H>::compute(&k, &v);
738
739    data.clear();
740    data.extend_from_slice(&v);
741    data.push(0x01);
742    data.extend_from_slice(&bx);
743    data.extend_from_slice(&bh);
744    k = Hmac::<H>::compute(&k, &data);
745    v = Hmac::<H>::compute(&k, &v);
746
747    loop {
748        let mut t = Vec::with_capacity(ro_len);
749        while t.len() < ro_len {
750            v = Hmac::<H>::compute(&k, &v);
751            let take = (ro_len - t.len()).min(v.len());
752            t.extend_from_slice(&v[..take]);
753        }
754
755        let candidate = bits_to_int(&t, q_bits);
756        if !candidate.is_zero() && &candidate < q {
757            return Some(candidate);
758        }
759
760        data.clear();
761        data.extend_from_slice(&v);
762        data.push(0x00);
763        k = Hmac::<H>::compute(&k, &data);
764        v = Hmac::<H>::compute(&k, &v);
765    }
766}
767
768#[cfg(test)]
769mod tests {
770    use super::{Dsa, DsaPrivateKey, DsaPublicKey, DsaSignature};
771    use crate::public_key::bigint::BigUint;
772    use crate::{CtrDrbgAes256, Sha256, Sha384};
773
774    fn derive_small_reference_key() -> (DsaPublicKey, DsaPrivateKey) {
775        let p = BigUint::from_u64(23);
776        let q = BigUint::from_u64(11);
777        let g = BigUint::from_u64(4);
778        let x = BigUint::from_u64(3);
779        Dsa::from_secret_exponent(&p, &q, &g, &x).expect("valid DSA key")
780    }
781
782    fn decode_hex(hex: &str) -> Vec<u8> {
783        let cleaned: String = hex.chars().filter(|c| !c.is_whitespace()).collect();
784        assert_eq!(
785            cleaned.len() % 2,
786            0,
787            "hex input must have an even number of nybbles"
788        );
789        (0..cleaned.len())
790            .step_by(2)
791            .map(|i| u8::from_str_radix(&cleaned[i..i + 2], 16).expect("valid hex byte"))
792            .collect()
793    }
794
795    fn from_hex(hex: &str) -> BigUint {
796        BigUint::from_be_bytes(&decode_hex(hex))
797    }
798
799    #[test]
800    fn derive_small_reference_key_components() {
801        let (public, private) = derive_small_reference_key();
802        assert_eq!(public.modulus(), &BigUint::from_u64(23));
803        assert_eq!(public.subgroup_order(), &BigUint::from_u64(11));
804        assert_eq!(public.generator(), &BigUint::from_u64(4));
805        assert_eq!(public.public_component(), &BigUint::from_u64(18));
806        assert_eq!(private.exponent(), &BigUint::from_u64(3));
807    }
808
809    #[test]
810    fn exact_small_signature_matches_reference() {
811        let (public, private) = derive_small_reference_key();
812        let nonce = BigUint::from_u64(5);
813        let signature = private
814            .sign_digest_with_nonce(&[0x09], &nonce)
815            .expect("valid DSA nonce");
816        assert_eq!(signature.r(), &BigUint::from_u64(1));
817        // `q = 11` is 4 bits wide, so the 8-bit digest is reduced to its
818        // leftmost 4 bits before signing. `0x09` becomes `0x0`, which makes
819        // this tiny reference vector sensitive to the FIPS truncation rule.
820        assert_eq!(signature.s(), &BigUint::from_u64(5));
821        assert!(public.verify(&[0x09], &signature));
822    }
823
824    #[test]
825    fn rejects_invalid_parameters() {
826        let p = BigUint::from_u64(23);
827        let q = BigUint::from_u64(5);
828        let g = BigUint::from_u64(4);
829        let x = BigUint::from_u64(3);
830        assert!(Dsa::from_secret_exponent(&p, &q, &g, &x).is_none());
831
832        let q = BigUint::from_u64(11);
833        let bad_g = BigUint::from_u64(5);
834        assert!(Dsa::from_secret_exponent(&p, &q, &bad_g, &x).is_none());
835        assert!(Dsa::from_secret_exponent(&p, &q, &g, &BigUint::zero()).is_none());
836    }
837
838    #[test]
839    fn sign_and_verify_roundtrip() {
840        let seed = [0x31u8; 48];
841        let mut drbg = CtrDrbgAes256::new(&seed);
842        let (public, private) = Dsa::generate(&mut drbg, 64).expect("generated DSA key");
843        let digest = b"dsa-signature-digest";
844        let signature = private.sign_digest::<Sha256>(digest).expect("signature");
845        assert!(public.verify(digest, &signature));
846        assert!(!public.verify(b"wrong-digest", &signature));
847    }
848
849    #[test]
850    fn sign_bytes_roundtrip() {
851        let seed = [0x44u8; 48];
852        let mut drbg = CtrDrbgAes256::new(&seed);
853        let (public, private) = Dsa::generate(&mut drbg, 64).expect("generated DSA key");
854        let digest = b"dsa-bytes";
855        let signature = private
856            .sign_digest_bytes::<Sha256>(digest)
857            .expect("signature bytes");
858        assert!(public.verify_bytes(digest, &signature));
859    }
860
861    #[test]
862    fn sign_message_roundtrip() {
863        let seed = [0x45u8; 48];
864        let mut drbg = CtrDrbgAes256::new(&seed);
865        let (public, private) = Dsa::generate(&mut drbg, 64).expect("generated DSA key");
866        let message = b"dsa full message";
867        let signature = private
868            .sign_message::<Sha256>(message)
869            .expect("message signature");
870        assert!(public.verify_message::<Sha256>(message, &signature));
871    }
872
873    #[test]
874    fn tampered_signature_is_rejected() {
875        let seed = [0x46u8; 48];
876        let mut drbg = CtrDrbgAes256::new(&seed);
877        let (public, private) = Dsa::generate(&mut drbg, 64).expect("generated DSA key");
878        let digest = b"dsa-tamper";
879        let mut signature = private.sign_digest::<Sha256>(digest).expect("signature");
880        signature.s = signature
881            .s
882            .add_ref(&BigUint::one())
883            .modulo(public.subgroup_order());
884        if signature.s.is_zero() {
885            signature.s = BigUint::one();
886        }
887        assert!(!public.verify(digest, &signature));
888    }
889
890    #[test]
891    fn cross_key_signature_is_rejected() {
892        let mut drbg_a = CtrDrbgAes256::new(&[0x47; 48]);
893        let mut drbg_b = CtrDrbgAes256::new(&[0x48; 48]);
894        let (public_a, private_a) = Dsa::generate(&mut drbg_a, 64).expect("first key");
895        let (public_b, _) = Dsa::generate(&mut drbg_b, 64).expect("second key");
896        let digest = b"dsa-cross";
897        let signature = private_a.sign_digest::<Sha256>(digest).expect("signature");
898        assert!(public_a.verify(digest, &signature));
899        assert!(!public_b.verify(digest, &signature));
900    }
901
902    #[test]
903    fn sign_digest_with_nonce_rejects_out_of_range_nonce() {
904        let (_public, private) = derive_small_reference_key();
905        assert!(private
906            .sign_digest_with_nonce(&[0x09], &BigUint::zero())
907            .is_none());
908        assert!(private
909            .sign_digest_with_nonce(&[0x09], private.subgroup_order())
910            .is_none());
911    }
912
913    #[test]
914    fn sign_digest_with_nonce_is_deterministic_for_fixed_nonce() {
915        let (_public, private) = derive_small_reference_key();
916        let digest = [0x09];
917        let nonce = BigUint::from_u64(7);
918        let lhs = private
919            .sign_digest_with_nonce(&digest, &nonce)
920            .expect("first explicit nonce signature");
921        let rhs = private
922            .sign_digest_with_nonce(&digest, &nonce)
923            .expect("second explicit nonce signature");
924        assert_eq!(lhs, rhs);
925    }
926
927    #[test]
928    fn generate_rejects_too_few_bits() {
929        let mut drbg = CtrDrbgAes256::new(&[0x49; 48]);
930        for bits in 0..19 {
931            assert!(Dsa::generate(&mut drbg, bits).is_none());
932        }
933    }
934
935    #[test]
936    fn serialization_roundtrip_preserves_verification() {
937        let seed = [0x4Au8; 48];
938        let mut drbg = CtrDrbgAes256::new(&seed);
939        let (public, private) = Dsa::generate(&mut drbg, 64).expect("generated DSA key");
940        let digest = b"dsa-serialize";
941        let signature = private.sign_digest::<Sha256>(digest).expect("signature");
942        let public_xml = public.to_xml();
943        let public_again = DsaPublicKey::from_xml(&public_xml).expect("public xml");
944        assert!(public_again.verify(digest, &signature));
945    }
946
947    #[test]
948    fn digest_to_scalar_truncates_by_digest_width() {
949        let q = BigUint::from_u64(257); // 9-bit subgroup order
950        let digest = [0x00u8, 0xff];
951        let value = super::digest_to_scalar(&digest, &q);
952        assert_eq!(value, BigUint::one());
953    }
954
955    #[test]
956    fn serialization_roundtrip() {
957        let seed = [0x55u8; 48];
958        let mut drbg = CtrDrbgAes256::new(&seed);
959        let (public, private) = Dsa::generate(&mut drbg, 64).expect("generated DSA key");
960
961        let public_blob = public.to_key_blob();
962        let public_pem = public.to_pem();
963        let public_xml = public.to_xml();
964        let private_blob = private.to_key_blob();
965        let private_pem = private.to_pem();
966        let private_xml = private.to_xml();
967
968        let public_from_blob = DsaPublicKey::from_key_blob(&public_blob).expect("public binary");
969        let public_from_pem = DsaPublicKey::from_pem(&public_pem).expect("public pem");
970        let public_from_xml = DsaPublicKey::from_xml(&public_xml).expect("public xml");
971        let private_from_blob =
972            DsaPrivateKey::from_key_blob(&private_blob).expect("private binary");
973        let private_from_pem = DsaPrivateKey::from_pem(&private_pem).expect("private pem");
974        let private_from_xml = DsaPrivateKey::from_xml(&private_xml).expect("private xml");
975
976        assert_eq!(public_from_blob, public);
977        assert_eq!(public_from_pem, public);
978        assert_eq!(public_from_xml, public);
979        assert_eq!(private_from_blob, private);
980        assert_eq!(private_from_pem, private);
981        assert_eq!(private_from_xml, private);
982    }
983
984    #[test]
985    fn signature_binary_roundtrip() {
986        let signature = DsaSignature {
987            r: BigUint::from_u64(1),
988            s: BigUint::from_u64(9),
989        };
990        let blob = signature.to_key_blob();
991        let parsed = DsaSignature::from_key_blob(&blob).expect("signature");
992        assert_eq!(parsed, signature);
993    }
994
995    #[test]
996    fn verify_message_matches_explicit_digest() {
997        let seed = [0x4Bu8; 48];
998        let mut drbg = CtrDrbgAes256::new(&seed);
999        let (public, private) = Dsa::generate(&mut drbg, 64).expect("generated DSA key");
1000        let message = b"dsa-digest";
1001        let digest = Sha384::digest(message);
1002        let signature = private.sign_digest::<Sha384>(&digest).expect("signature");
1003        assert!(public.verify_message::<Sha384>(message, &signature));
1004    }
1005
1006    #[test]
1007    fn rfc6979_dsa_1024_sha256_sample_vector() {
1008        // RFC 6979, Appendix A.2.1 (DSA, 1024 bits), SHA-256, message "sample".
1009        let p = from_hex(
1010            "86F5CA03DCFEB225063FF830A0C769B9DD9D6153AD91D7CE27F787C43278B447\
1011             E6533B86B18BED6E8A48B784A14C252C5BE0DBF60B86D6385BD2F12FB763ED88\
1012             73ABFD3F5BA2E0A8C0A59082EAC056935E529DAF7C610467899C77ADEDFC846C\
1013             881870B7B19B2B58F9BE0521A17002E3BDD6B86685EE90B3D9A1B02B782B1779",
1014        );
1015        let q = from_hex("996F967F6C8E388D9E28D01E205FBA957A5698B1");
1016        let g = from_hex(
1017            "07B0F92546150B62514BB771E2A0C0CE387F03BDA6C56B505209FF25FD3C133D\
1018             89BBCD97E904E09114D9A7DEFDEADFC9078EA544D2E401AEECC40BB9FBBF78FD\
1019             87995A10A1C27CB7789B594BA7EFB5C4326A9FE59A070E136DB77175464ADCA4\
1020             17BE5DCE2F40D10A46A3A3943F26AB7FD9C0398FF8C76EE0A56826A8A88F1DBD",
1021        );
1022        let x = from_hex("411602CB19A6CCC34494D79D98EF1E7ED5AF25F7");
1023
1024        let (public, private) =
1025            Dsa::from_secret_exponent(&p, &q, &g, &x).expect("RFC key must be valid");
1026        let message = b"sample";
1027        let digest = Sha256::digest(message);
1028
1029        let expected_k = from_hex("519BA0546D0C39202A7D34D7DFA5E760B318BCFB");
1030        let derived_k =
1031            super::rfc6979_nonce::<Sha256>(&q, &x, &digest).expect("RFC nonce must derive");
1032        assert_eq!(derived_k, expected_k, "RFC 6979 nonce mismatch");
1033
1034        let signature = private.sign_message::<Sha256>(message).expect("sign");
1035        let expected_r = from_hex("81F2F5850BE5BC123C43F71A3033E9384611C545");
1036        let expected_s = from_hex("4CDD914B65EB6C66A8AAAD27299BEE6B035F5E89");
1037        assert_eq!(signature.r(), &expected_r);
1038        assert_eq!(signature.s(), &expected_s);
1039        assert!(public.verify_message::<Sha256>(message, &signature));
1040    }
1041}
cryptography/public_key/dsa.rs

cryptography/public_key/
dsa.rs
