cryptography/public_key/
dh.rs

1//! Classical Diffie-Hellman (DH) key exchange over a prime-order subgroup.
2//!
3//! This is the finite-field Diffie-Hellman protocol from NIST SP 800-56A.
4//! The mathematical structure is the same as DSA and ElGamal: a prime modulus
5//! `p`, a prime subgroup order `q` dividing `p − 1`, and a generator `g` of
6//! the order-`q` subgroup of `Z_p*`.
7//!
8//! ## Algorithm
9//!
10//! Two parties share domain parameters `(p, q, g)`.  Each holds a key pair:
11//! ```text
12//! Private key: x ∈ [1, q)
13//! Public key:  y = g^x mod p
14//! ```
15//!
16//! The shared secret is:
17//! ```text
18//! Alice: s = y_B^{x_A} mod p
19//! Bob:   s = y_A^{x_B} mod p
20//! (both equal g^{x_A · x_B} mod p)
21//! ```
22//!
23//! The returned shared secret is the raw big-endian encoding of `s`.  Both
24//! parties must apply the same KDF to this value before using it as a key.
25//!
26//! ## Parameter generation
27//!
28//! [`Dh::generate_params`] produces domain parameters using the same
29//! `generate_prime_order_group` routine used by DSA.  Parameters can be
30//! shared among many key pairs (unlike RSA moduli, which are per-key).
31//!
32//! ## Key validation
33//!
34//! [`DhPrivateKey::agree`] verifies that the peer's public key `y` lies in the
35//! correct subgroup (`1 < y < p` and `y^q ≡ 1 mod p`) before computing the
36//! shared secret.  Skipping this check enables small-subgroup attacks.
37
38use core::fmt;
39
40use crate::public_key::bigint::BigUint;
41use crate::public_key::io::{
42    decode_biguints, encode_biguints, pem_unwrap, pem_wrap, xml_unwrap, xml_wrap,
43};
44use crate::public_key::primes::{
45    generate_prime_order_group, is_probable_prime, mod_pow, random_nonzero_below,
46};
47use crate::Csprng;
48
49const DH_PARAMS_LABEL: &str = "CRYPTOGRAPHY DH PARAMETERS";
50const DH_PUBLIC_LABEL: &str = "CRYPTOGRAPHY DH PUBLIC KEY";
51const DH_PRIVATE_LABEL: &str = "CRYPTOGRAPHY DH PRIVATE KEY";
52
53// ─── Types ───────────────────────────────────────────────────────────────────
54
55/// Shared Diffie-Hellman domain parameters `(p, q, g)`.
56///
57/// A single set of parameters can be used by many key pairs.
58#[derive(Clone, Debug, Eq, PartialEq)]
59pub struct DhParams {
60    /// Prime modulus.
61    pub p: BigUint,
62    /// Prime subgroup order (`q | p − 1`).
63    pub q: BigUint,
64    /// Generator of the order-`q` subgroup.
65    pub g: BigUint,
66}
67
68/// Public key for DH.
69#[derive(Clone, Debug, Eq, PartialEq)]
70pub struct DhPublicKey {
71    p: BigUint,
72    q: BigUint,
73    g: BigUint,
74    /// Public component `y = g^x mod p`.
75    y: BigUint,
76}
77
78/// Private key for DH.
79#[derive(Clone, Eq, PartialEq)]
80pub struct DhPrivateKey {
81    p: BigUint,
82    q: BigUint,
83    g: BigUint,
84    /// Private exponent `x ∈ [1, q)`.
85    x: BigUint,
86    /// Cached public component `y = g^x mod p`.
87    y: BigUint,
88}
89
90pub struct Dh;
91
92// ─── DhParams ─────────────────────────────────────────────────────────────────
93
94impl DhParams {
95    /// Encode in binary format: `[p, q, g]`.
96    #[must_use]
97    pub fn to_key_blob(&self) -> Vec<u8> {
98        encode_biguints(&[&self.p, &self.q, &self.g])
99    }
100
101    /// Decode from binary format.
102    #[must_use]
103    pub fn from_key_blob(blob: &[u8]) -> Option<Self> {
104        let mut fields = decode_biguints(blob)?.into_iter();
105        let p = fields.next()?;
106        let q = fields.next()?;
107        let g = fields.next()?;
108        if fields.next().is_some() || !validate_domain(&p, &q, &g) {
109            return None;
110        }
111        Some(Self { p, q, g })
112    }
113
114    #[must_use]
115    pub fn to_pem(&self) -> String {
116        pem_wrap(DH_PARAMS_LABEL, &self.to_key_blob())
117    }
118
119    /// Returns `None` if the PEM label does not match, the payload is malformed,
120    /// or the decoded parameters fail primality / subgroup checks.
121    #[must_use]
122    pub fn from_pem(pem: &str) -> Option<Self> {
123        Self::from_key_blob(&pem_unwrap(DH_PARAMS_LABEL, pem)?)
124    }
125
126    #[must_use]
127    pub fn to_xml(&self) -> String {
128        xml_wrap(
129            "DhParams",
130            &[("p", &self.p), ("q", &self.q), ("g", &self.g)],
131        )
132    }
133
134    /// Returns `None` if the XML is malformed or the decoded parameters fail
135    /// primality / subgroup checks.
136    #[must_use]
137    pub fn from_xml(xml: &str) -> Option<Self> {
138        let mut fields = xml_unwrap("DhParams", &["p", "q", "g"], xml)?.into_iter();
139        let p = fields.next()?;
140        let q = fields.next()?;
141        let g = fields.next()?;
142        if fields.next().is_some() || !validate_domain(&p, &q, &g) {
143            return None;
144        }
145        Some(Self { p, q, g })
146    }
147}
148
149// ─── DhPublicKey ──────────────────────────────────────────────────────────────
150
151impl DhPublicKey {
152    #[must_use]
153    pub fn modulus(&self) -> &BigUint {
154        &self.p
155    }
156
157    #[must_use]
158    pub fn subgroup_order(&self) -> &BigUint {
159        &self.q
160    }
161
162    #[must_use]
163    pub fn generator(&self) -> &BigUint {
164        &self.g
165    }
166
167    /// The public component `y = g^x mod p`.
168    #[must_use]
169    pub fn public_component(&self) -> &BigUint {
170        &self.y
171    }
172
173    #[must_use]
174    pub fn params(&self) -> DhParams {
175        DhParams {
176            p: self.p.clone(),
177            q: self.q.clone(),
178            g: self.g.clone(),
179        }
180    }
181
182    // ── Serialization ────────────────────────────────────────────────────────
183
184    /// Encode in binary format: `[p, q, g, y]`.
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 from 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        Some(Self { p, q, g, y })
203    }
204
205    #[must_use]
206    pub fn to_pem(&self) -> String {
207        pem_wrap(DH_PUBLIC_LABEL, &self.to_key_blob())
208    }
209
210    /// Returns `None` if the PEM label does not match or the payload is malformed.
211    #[must_use]
212    pub fn from_pem(pem: &str) -> Option<Self> {
213        Self::from_key_blob(&pem_unwrap(DH_PUBLIC_LABEL, pem)?)
214    }
215
216    #[must_use]
217    pub fn to_xml(&self) -> String {
218        xml_wrap(
219            "DhPublicKey",
220            &[
221                ("p", &self.p),
222                ("q", &self.q),
223                ("g", &self.g),
224                ("y", &self.y),
225            ],
226        )
227    }
228
229    /// Returns `None` if the XML is malformed or `y` is out of range.
230    #[must_use]
231    pub fn from_xml(xml: &str) -> Option<Self> {
232        let mut fields = xml_unwrap("DhPublicKey", &["p", "q", "g", "y"], xml)?.into_iter();
233        let p = fields.next()?;
234        let q = fields.next()?;
235        let g = fields.next()?;
236        let y = fields.next()?;
237        if fields.next().is_some() || !validate_domain(&p, &q, &g) || y <= BigUint::one() || y >= p
238        {
239            return None;
240        }
241        Some(Self { p, q, g, y })
242    }
243}
244
245// ─── DhPrivateKey ─────────────────────────────────────────────────────────────
246
247impl DhPrivateKey {
248    #[must_use]
249    pub fn modulus(&self) -> &BigUint {
250        &self.p
251    }
252
253    #[must_use]
254    pub fn subgroup_order(&self) -> &BigUint {
255        &self.q
256    }
257
258    #[must_use]
259    pub fn generator(&self) -> &BigUint {
260        &self.g
261    }
262
263    /// The private exponent `x ∈ [1, q)`.
264    #[must_use]
265    pub fn exponent(&self) -> &BigUint {
266        &self.x
267    }
268
269    /// Derive the matching public key.
270    #[must_use]
271    pub fn to_public_key(&self) -> DhPublicKey {
272        DhPublicKey {
273            p: self.p.clone(),
274            q: self.q.clone(),
275            g: self.g.clone(),
276            y: self.y.clone(),
277        }
278    }
279
280    #[must_use]
281    pub fn params(&self) -> DhParams {
282        DhParams {
283            p: self.p.clone(),
284            q: self.q.clone(),
285            g: self.g.clone(),
286        }
287    }
288
289    /// Compute the shared secret with a peer's public key.
290    ///
291    /// Returns `s = y_peer^x mod p`, or `None` if
292    /// the peer key uses different domain parameters or fails subgroup validation.
293    ///
294    /// **Subgroup validation**: checks that `1 < y_peer < p` and that
295    /// `y_peer^q ≡ 1 mod p`, rejecting low-order and small-subgroup inputs.
296    #[must_use]
297    pub fn agree_element(&self, peer: &DhPublicKey) -> Option<BigUint> {
298        // Domain parameters must match.
299        if peer.p != self.p || peer.q != self.q || peer.g != self.g {
300            return None;
301        }
302        // Subgroup validation: reject trivial and low-order values.
303        if peer.y <= BigUint::one() || peer.y >= self.p {
304            return None;
305        }
306        let check = mod_pow(&peer.y, &self.q, &self.p);
307        if check != BigUint::one() {
308            return None;
309        }
310
311        Some(mod_pow(&peer.y, &self.x, &self.p))
312    }
313
314    // ── Serialization ────────────────────────────────────────────────────────
315
316    /// Encode in binary format: `[p, q, g, x]`.
317    #[must_use]
318    pub fn to_key_blob(&self) -> Vec<u8> {
319        encode_biguints(&[&self.p, &self.q, &self.g, &self.x])
320    }
321
322    /// Decode from binary format.
323    #[must_use]
324    pub fn from_key_blob(blob: &[u8]) -> Option<Self> {
325        let mut fields = decode_biguints(blob)?.into_iter();
326        let p = fields.next()?;
327        let q = fields.next()?;
328        let g = fields.next()?;
329        let x = fields.next()?;
330        if fields.next().is_some() || !validate_domain(&p, &q, &g) || x.is_zero() || x >= q {
331            return None;
332        }
333        let y = mod_pow(&g, &x, &p);
334        Some(Self { p, q, g, x, y })
335    }
336
337    #[must_use]
338    pub fn to_pem(&self) -> String {
339        pem_wrap(DH_PRIVATE_LABEL, &self.to_key_blob())
340    }
341
342    /// Returns `None` if the PEM label does not match or the payload is malformed.
343    #[must_use]
344    pub fn from_pem(pem: &str) -> Option<Self> {
345        Self::from_key_blob(&pem_unwrap(DH_PRIVATE_LABEL, pem)?)
346    }
347
348    #[must_use]
349    pub fn to_xml(&self) -> String {
350        xml_wrap(
351            "DhPrivateKey",
352            &[
353                ("p", &self.p),
354                ("q", &self.q),
355                ("g", &self.g),
356                ("x", &self.x),
357            ],
358        )
359    }
360
361    /// Returns `None` if the XML is malformed or `x` is zero or ≥ `q`.
362    #[must_use]
363    pub fn from_xml(xml: &str) -> Option<Self> {
364        let mut fields = xml_unwrap("DhPrivateKey", &["p", "q", "g", "x"], xml)?.into_iter();
365        let p = fields.next()?;
366        let q = fields.next()?;
367        let g = fields.next()?;
368        let x = fields.next()?;
369        if fields.next().is_some() || !validate_domain(&p, &q, &g) || x.is_zero() || x >= q {
370            return None;
371        }
372        let y = mod_pow(&g, &x, &p);
373        Some(Self { p, q, g, x, y })
374    }
375}
376
377impl fmt::Debug for DhPrivateKey {
378    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
379        f.write_str("DhPrivateKey(<redacted>)")
380    }
381}
382
383// ─── Dh namespace ─────────────────────────────────────────────────────────────
384
385impl Dh {
386    /// Generate domain parameters `(p, q, g)` for a given key size.
387    ///
388    /// Uses the same prime-order subgroup generation as DSA (FIPS 186-5).
389    /// The parameters can be reused across many key pairs.
390    #[must_use]
391    pub fn generate_params<R: Csprng>(rng: &mut R, bits: usize) -> Option<DhParams> {
392        let (p, q, _cofactor, g) = generate_prime_order_group(rng, bits)?;
393        Some(DhParams { p, q, g })
394    }
395
396    /// Generate a DH key pair from existing domain parameters.
397    #[must_use]
398    pub fn generate<R: Csprng>(params: &DhParams, rng: &mut R) -> (DhPublicKey, DhPrivateKey) {
399        let x = random_nonzero_below(rng, &params.q)
400            .expect("subgroup order is always > 1 for valid parameters");
401        let y = mod_pow(&params.g, &x, &params.p);
402        (
403            DhPublicKey {
404                p: params.p.clone(),
405                q: params.q.clone(),
406                g: params.g.clone(),
407                y: y.clone(),
408            },
409            DhPrivateKey {
410                p: params.p.clone(),
411                q: params.q.clone(),
412                g: params.g.clone(),
413                x,
414                y,
415            },
416        )
417    }
418}
419
420// ─── Domain parameter validation ─────────────────────────────────────────────
421
422/// Validate DH domain parameters: both `p` and `q` must be probable primes,
423/// `q | p − 1`, and `g` must be a generator of the order-`q` subgroup.
424fn validate_domain(p: &BigUint, q: &BigUint, g: &BigUint) -> bool {
425    if !is_probable_prime(p) || !is_probable_prime(q) {
426        return false;
427    }
428    if q >= p {
429        return false;
430    }
431    let p_minus_one = p.sub_ref(&BigUint::one());
432    if !p_minus_one.modulo(q).is_zero() {
433        return false;
434    }
435    if g <= &BigUint::one() || g >= p {
436        return false;
437    }
438    mod_pow(g, q, p) == BigUint::one()
439}
440
441// ─── Tests ────────────────────────────────────────────────────────────────────
442
443#[cfg(test)]
444mod tests {
445    use super::{Dh, DhParams, DhPrivateKey, DhPublicKey};
446    use crate::public_key::bigint::BigUint;
447    use crate::CtrDrbgAes256;
448
449    fn rng() -> CtrDrbgAes256 {
450        CtrDrbgAes256::new(&[0x33; 48])
451    }
452
453    /// Small reference domain: p=23, q=11, g=4 (the same toy group used in the DSA tests).
454    fn toy_params() -> super::DhParams {
455        DhParams {
456            p: BigUint::from_u64(23),
457            q: BigUint::from_u64(11),
458            g: BigUint::from_u64(4),
459        }
460    }
461
462    // ── Basic key generation and agreement ────────────────────────────────────
463
464    #[test]
465    fn agreement_toy_params() {
466        let params = toy_params();
467        let mut rng = rng();
468        let (pub_a, priv_a) = Dh::generate(&params, &mut rng);
469        let (pub_b, priv_b) = Dh::generate(&params, &mut rng);
470        let s_a = priv_a.agree_element(&pub_b).expect("agree A→B");
471        let s_b = priv_b.agree_element(&pub_a).expect("agree B→A");
472        assert_eq!(s_a, s_b);
473    }
474
475    #[test]
476    fn agreement_generated_params() {
477        let mut rng = rng();
478        let params = Dh::generate_params(&mut rng, 512).expect("params");
479        let (pub_a, priv_a) = Dh::generate(&params, &mut rng);
480        let (pub_b, priv_b) = Dh::generate(&params, &mut rng);
481        let s_a = priv_a.agree_element(&pub_b).expect("agree A");
482        let s_b = priv_b.agree_element(&pub_a).expect("agree B");
483        assert_eq!(s_a, s_b);
484    }
485
486    #[test]
487    fn to_public_key_matches() {
488        let params = toy_params();
489        let mut rng = rng();
490        let (public, private) = Dh::generate(&params, &mut rng);
491        let derived = private.to_public_key();
492        assert_eq!(derived.y, public.y);
493    }
494
495    // ── Domain parameter mismatch ─────────────────────────────────────────────
496
497    #[test]
498    fn mismatched_params_rejected() {
499        let p1 = toy_params();
500        // Different prime — generate_params would be slow; reuse toy with different q.
501        let p2 = DhParams {
502            p: BigUint::from_u64(23),
503            q: BigUint::from_u64(11),
504            g: BigUint::from_u64(2), // different generator
505        };
506        let mut rng = rng();
507        let (pub_a, _) = Dh::generate(&p1, &mut rng);
508        let (_, priv_b) = Dh::generate(&p2, &mut rng);
509        assert!(priv_b.agree_element(&pub_a).is_none());
510    }
511
512    // ── Serialization ─────────────────────────────────────────────────────────
513
514    #[test]
515    fn params_binary_roundtrip() {
516        let params = toy_params();
517        let blob = params.to_key_blob();
518        let recovered = DhParams::from_key_blob(&blob).expect("from_binary");
519        assert_eq!(recovered, params);
520    }
521
522    #[test]
523    fn params_pem_roundtrip() {
524        let params = toy_params();
525        let pem = params.to_pem();
526        assert!(pem.contains("DH PARAMETERS"));
527        let recovered = DhParams::from_pem(&pem).expect("from_pem");
528        assert_eq!(recovered, params);
529    }
530
531    #[test]
532    fn params_xml_roundtrip() {
533        let params = toy_params();
534        let xml = params.to_xml();
535        assert!(xml.contains("DhParams"));
536        let recovered = DhParams::from_xml(&xml).expect("from_xml");
537        assert_eq!(recovered, params);
538    }
539
540    #[test]
541    fn public_key_binary_roundtrip() {
542        let params = toy_params();
543        let mut rng = rng();
544        let (public, _) = Dh::generate(&params, &mut rng);
545        let blob = public.to_key_blob();
546        let recovered = DhPublicKey::from_key_blob(&blob).expect("from_binary");
547        assert_eq!(recovered.y, public.y);
548    }
549
550    #[test]
551    fn private_key_binary_roundtrip() {
552        let params = toy_params();
553        let mut rng = rng();
554        let (_, private) = Dh::generate(&params, &mut rng);
555        let blob = private.to_key_blob();
556        let recovered = DhPrivateKey::from_key_blob(&blob).expect("from_binary");
557        assert_eq!(recovered.x, private.x);
558    }
559
560    #[test]
561    fn public_key_pem_roundtrip() {
562        let params = toy_params();
563        let mut rng = rng();
564        let (public, _) = Dh::generate(&params, &mut rng);
565        let pem = public.to_pem();
566        assert!(pem.contains("DH PUBLIC KEY"));
567        let recovered = DhPublicKey::from_pem(&pem).expect("from_pem");
568        assert_eq!(recovered.y, public.y);
569    }
570
571    #[test]
572    fn private_key_pem_roundtrip() {
573        let params = toy_params();
574        let mut rng = rng();
575        let (_, private) = Dh::generate(&params, &mut rng);
576        let pem = private.to_pem();
577        assert!(pem.contains("DH PRIVATE KEY"));
578        let recovered = DhPrivateKey::from_pem(&pem).expect("from_pem");
579        assert_eq!(recovered.x, private.x);
580    }
581
582    #[test]
583    fn public_key_xml_roundtrip() {
584        let params = toy_params();
585        let mut rng = rng();
586        let (public, _) = Dh::generate(&params, &mut rng);
587        let xml = public.to_xml();
588        assert!(xml.contains("DhPublicKey"));
589        let recovered = DhPublicKey::from_xml(&xml).expect("from_xml");
590        assert_eq!(recovered.y, public.y);
591    }
592
593    #[test]
594    fn private_key_xml_roundtrip() {
595        let params = toy_params();
596        let mut rng = rng();
597        let (_, private) = Dh::generate(&params, &mut rng);
598        let xml = private.to_xml();
599        let recovered = DhPrivateKey::from_xml(&xml).expect("from_xml");
600        assert_eq!(recovered.x, private.x);
601    }
602
603    #[test]
604    fn debug_private_key_redacted() {
605        let params = toy_params();
606        let mut rng = rng();
607        let (_, private) = Dh::generate(&params, &mut rng);
608        assert_eq!(format!("{private:?}"), "DhPrivateKey(<redacted>)");
609    }
610}
cryptography/public_key/dh.rs

cryptography/public_key/
dh.rs
