cryptography/public_key/
cocks.rs

1//! Clifford Cocks's original public-key scheme (CESG memo, 1973).
2//!
3//! This predates RSA by five years and is historically important as the first
4//! public-key encryption construction described in the open literature later on.
5//! The module keeps the published Cocks arithmetic map and layers a
6//! byte-oriented interface on
7//! top of it. The arithmetic primitive remains available directly, while the
8//! byte helpers serialize ciphertext integers as single-field DER `INTEGER`
9//! sequences so callers can move ciphertexts around as bytes.
10
11use core::fmt;
12
13use crate::public_key::bigint::BigUint;
14use crate::public_key::io::{
15    decode_biguints, encode_biguints, pem_unwrap, pem_wrap, xml_unwrap, xml_wrap,
16};
17use crate::public_key::primes::{is_probable_prime, mod_inverse, mod_pow, random_probable_prime};
18use crate::Csprng;
19
20const COCKS_PUBLIC_LABEL: &str = "CRYPTOGRAPHY COCKS PUBLIC KEY";
21const COCKS_PRIVATE_LABEL: &str = "CRYPTOGRAPHY COCKS PRIVATE KEY";
22
23/// Public key for the Cocks primitive.
24#[derive(Clone, Debug, Eq, PartialEq)]
25pub struct CocksPublicKey {
26    n: BigUint,
27}
28
29/// Private key for the Cocks primitive.
30#[derive(Clone, Eq, PartialEq)]
31pub struct CocksPrivateKey {
32    pi: BigUint,
33    q: BigUint,
34}
35
36/// Namespace wrapper for the Cocks construction.
37pub struct Cocks;
38
39impl CocksPublicKey {
40    /// Return the modulus `n = p * q`.
41    #[must_use]
42    pub fn modulus(&self) -> &BigUint {
43        &self.n
44    }
45
46    /// Return a conservative public upper bound for byte-oriented plaintexts.
47    ///
48    /// When `p < q`, the private prime `q` is strictly larger than
49    /// `floor(sqrt(n))`, so any message in `[0, floor(sqrt(n)))` will also be
50    /// in the range recovered by the private map `c^pi mod q`.
51    #[must_use]
52    pub fn max_plaintext_exclusive(&self) -> BigUint {
53        self.n.sqrt_floor()
54    }
55
56    /// Encrypt the raw integer message.
57    ///
58    /// Cocks uses the unusual public map `c = m^n mod n`, where the public
59    /// exponent is the modulus `n` itself.
60    #[must_use]
61    pub fn encrypt_raw(&self, message: &BigUint) -> BigUint {
62        mod_pow(message, &self.n, &self.n)
63    }
64
65    /// Encrypt a byte string using the conservative public plaintext bound.
66    ///
67    /// The Cocks private map only recovers integers modulo the private prime
68    /// `q`. This wrapper therefore accepts only messages strictly below
69    /// `floor(sqrt(n))`, which is a public bound guaranteed to stay below `q`
70    /// because the key generator enforces `p < q`.
71    #[must_use]
72    pub fn encrypt(&self, message: &[u8]) -> Option<BigUint> {
73        let message_int = BigUint::from_be_bytes(message);
74        if message_int >= self.max_plaintext_exclusive() {
75            return None;
76        }
77        Some(self.encrypt_raw(&message_int))
78    }
79
80    /// Encrypt a byte string and return the ciphertext as a byte string.
81    ///
82    /// The encoded ciphertext is the crate's standard one-`INTEGER` DER
83    /// payload for non-RSA public-key values. That keeps the byte-oriented
84    /// helper unambiguous for this specific scheme without changing the
85    /// underlying arithmetic map.
86    #[must_use]
87    pub fn encrypt_bytes(&self, message: &[u8]) -> Option<Vec<u8>> {
88        let ciphertext = self.encrypt(message)?;
89        Some(encode_biguints(&[&ciphertext]))
90    }
91
92    /// Encode the public key in the crate-defined binary format.
93    #[must_use]
94    pub fn to_key_blob(&self) -> Vec<u8> {
95        encode_biguints(&[&self.n])
96    }
97
98    /// Decode the public key from the crate-defined binary format.
99    #[must_use]
100    pub fn from_key_blob(blob: &[u8]) -> Option<Self> {
101        let mut fields = decode_biguints(blob)?.into_iter();
102        let n = fields.next()?;
103        if fields.next().is_some() || n <= BigUint::one() {
104            return None;
105        }
106        Some(Self { n })
107    }
108
109    /// Encode the public key in PEM using the crate-defined label.
110    #[must_use]
111    pub fn to_pem(&self) -> String {
112        pem_wrap(COCKS_PUBLIC_LABEL, &self.to_key_blob())
113    }
114
115    /// Encode the public key as the crate's flat XML form.
116    #[must_use]
117    pub fn to_xml(&self) -> String {
118        xml_wrap("CocksPublicKey", &[("n", &self.n)])
119    }
120
121    /// Decode the public key from the crate-defined PEM label.
122    #[must_use]
123    pub fn from_pem(pem: &str) -> Option<Self> {
124        let blob = pem_unwrap(COCKS_PUBLIC_LABEL, pem)?;
125        Self::from_key_blob(&blob)
126    }
127
128    /// Decode the public key from the crate's flat XML form.
129    #[must_use]
130    pub fn from_xml(xml: &str) -> Option<Self> {
131        let mut fields = xml_unwrap("CocksPublicKey", &["n"], xml)?.into_iter();
132        let n = fields.next()?;
133        if fields.next().is_some() || n <= BigUint::one() {
134            return None;
135        }
136        Some(Self { n })
137    }
138}
139
140impl fmt::Debug for CocksPrivateKey {
141    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
142        f.write_str("CocksPrivateKey(<redacted>)")
143    }
144}
145
146impl CocksPrivateKey {
147    /// Return the stored exponent `pi = p^{-1} mod (q - 1)`.
148    #[must_use]
149    pub fn exponent(&self) -> &BigUint {
150        &self.pi
151    }
152
153    /// Return the private prime `q`.
154    #[must_use]
155    pub fn q(&self) -> &BigUint {
156        &self.q
157    }
158
159    /// Decrypt the raw integer ciphertext.
160    ///
161    /// The Python source recovers the message as `c^pi mod q`, so the original
162    /// message must be interpreted in the range `[0, q)`.
163    #[must_use]
164    pub fn decrypt_raw(&self, ciphertext: &BigUint) -> BigUint {
165        mod_pow(ciphertext, &self.pi, &self.q)
166    }
167
168    /// Decrypt a ciphertext back into the big-endian byte string that was
169    /// interpreted as the plaintext integer.
170    #[must_use]
171    pub fn decrypt(&self, ciphertext: &BigUint) -> Vec<u8> {
172        self.decrypt_raw(ciphertext).to_be_bytes()
173    }
174
175    /// Decrypt a byte-encoded ciphertext produced by [`CocksPublicKey::encrypt_bytes`].
176    #[must_use]
177    pub fn decrypt_bytes(&self, ciphertext: &[u8]) -> Option<Vec<u8>> {
178        let mut fields = decode_biguints(ciphertext)?.into_iter();
179        let value = fields.next()?;
180        if fields.next().is_some() {
181            return None;
182        }
183        Some(self.decrypt(&value))
184    }
185
186    /// Encode the private key in the crate-defined binary format.
187    #[must_use]
188    pub fn to_key_blob(&self) -> Vec<u8> {
189        encode_biguints(&[&self.pi, &self.q])
190    }
191
192    /// Decode the private key from the crate-defined binary format.
193    #[must_use]
194    pub fn from_key_blob(blob: &[u8]) -> Option<Self> {
195        let mut fields = decode_biguints(blob)?.into_iter();
196        let pi = fields.next()?;
197        let q = fields.next()?;
198        if fields.next().is_some() || pi.is_zero() || q <= BigUint::one() {
199            return None;
200        }
201        Some(Self { pi, q })
202    }
203
204    /// Encode the private key in PEM using the crate-defined label.
205    #[must_use]
206    pub fn to_pem(&self) -> String {
207        pem_wrap(COCKS_PRIVATE_LABEL, &self.to_key_blob())
208    }
209
210    /// Encode the private key as the crate's flat XML form.
211    #[must_use]
212    pub fn to_xml(&self) -> String {
213        xml_wrap("CocksPrivateKey", &[("pi", &self.pi), ("q", &self.q)])
214    }
215
216    /// Decode the private key from the crate-defined PEM label.
217    #[must_use]
218    pub fn from_pem(pem: &str) -> Option<Self> {
219        let blob = pem_unwrap(COCKS_PRIVATE_LABEL, pem)?;
220        Self::from_key_blob(&blob)
221    }
222
223    /// Decode the private key from the crate's flat XML form.
224    #[must_use]
225    pub fn from_xml(xml: &str) -> Option<Self> {
226        let mut fields = xml_unwrap("CocksPrivateKey", &["pi", "q"], xml)?.into_iter();
227        let pi = fields.next()?;
228        let q = fields.next()?;
229        if fields.next().is_some() || pi.is_zero() || q <= BigUint::one() {
230            return None;
231        }
232        Some(Self { pi, q })
233    }
234}
235
236impl Cocks {
237    /// Derive a raw key pair from explicit primes `p` and `q`.
238    ///
239    /// Returns `None` if `p >= q`, the inputs are equal, either prime is
240    /// composite, or if
241    /// `p` is not invertible modulo `q - 1`.
242    #[must_use]
243    pub fn from_primes(p: &BigUint, q: &BigUint) -> Option<(CocksPublicKey, CocksPrivateKey)> {
244        if p >= q || !is_probable_prime(p) || !is_probable_prime(q) {
245            return None;
246        }
247
248        let q_minus_one = q.sub_ref(&BigUint::one());
249        let pi = mod_inverse(p, &q_minus_one)?;
250        let n = p.mul_ref(q);
251
252        Some((CocksPublicKey { n }, CocksPrivateKey { pi, q: q.clone() }))
253    }
254
255    /// Generate a Cocks key pair with `p < q`.
256    #[must_use]
257    pub fn generate<R: Csprng>(
258        rng: &mut R,
259        bits: usize,
260    ) -> Option<(CocksPublicKey, CocksPrivateKey)> {
261        // With fewer than 8 total bits the split can collapse to the same tiny
262        // prime on both sides, so a distinct-prime key may never be found.
263        if bits < 8 {
264            return None;
265        }
266
267        let p_bits = bits / 2;
268        let q_bits = bits - p_bits;
269        loop {
270            let mut p = random_probable_prime(rng, p_bits)?;
271            let mut q = random_probable_prime(rng, q_bits)?;
272            if q < p {
273                core::mem::swap(&mut p, &mut q);
274            }
275            if let Some(keypair) = Self::from_primes(&p, &q) {
276                return Some(keypair);
277            }
278        }
279    }
280}
281
282#[cfg(test)]
283mod tests {
284    use super::{Cocks, CocksPrivateKey, CocksPublicKey};
285    use crate::public_key::bigint::BigUint;
286    use crate::CtrDrbgAes256;
287
288    #[test]
289    fn derive_small_reference_key() {
290        let p = BigUint::from_u64(11);
291        let q = BigUint::from_u64(17);
292        let (public, private) = Cocks::from_primes(&p, &q).expect("valid small primes");
293        assert_eq!(public.modulus(), &BigUint::from_u64(187));
294        assert_eq!(private.exponent(), &BigUint::from_u64(3));
295        assert_eq!(private.q(), &BigUint::from_u64(17));
296    }
297
298    #[test]
299    fn roundtrip_small_messages() {
300        let prime_p = BigUint::from_u64(19);
301        let prime_q = BigUint::from_u64(23);
302        let (public, private) = Cocks::from_primes(&prime_p, &prime_q).expect("valid Cocks key");
303
304        for msg in [0u64, 1, 2, 7, 11, 22] {
305            let message = BigUint::from_u64(msg);
306            let ciphertext = public.encrypt_raw(&message);
307            let plaintext = private.decrypt_raw(&ciphertext);
308            assert_eq!(plaintext, message);
309        }
310    }
311
312    #[test]
313    fn exact_small_ciphertext_matches_python() {
314        let p = BigUint::from_u64(11);
315        let q = BigUint::from_u64(17);
316        let (public, private) = Cocks::from_primes(&p, &q).expect("valid small primes");
317        let message = BigUint::from_u64(5);
318        let ciphertext = public.encrypt_raw(&message);
319        assert_eq!(ciphertext, BigUint::from_u64(113));
320        assert_eq!(private.decrypt_raw(&ciphertext), message);
321    }
322
323    #[test]
324    fn rejects_non_invertible_choice() {
325        let p = BigUint::from_u64(23);
326        let q = BigUint::from_u64(47);
327        // Here q - 1 = 46 is divisible by p = 23, so p has no inverse modulo
328        // q - 1 and the Cocks private exponent cannot be formed.
329        assert!(Cocks::from_primes(&p, &q).is_none());
330    }
331
332    #[test]
333    fn byte_wrapper_roundtrip() {
334        let prime_p = BigUint::from_u64(19);
335        let prime_q = BigUint::from_u64(23);
336        let (public, private) = Cocks::from_primes(&prime_p, &prime_q).expect("valid Cocks key");
337        let ciphertext = public.encrypt(&[0x0b]).expect("message fits public bound");
338        assert_eq!(private.decrypt(&ciphertext), vec![0x0b]);
339    }
340
341    #[test]
342    fn generate_keypair_roundtrip() {
343        let mut drbg = CtrDrbgAes256::new(&[0x21; 48]);
344        let (public, private) = Cocks::generate(&mut drbg, 32).expect("Cocks key generation");
345        let ciphertext = public.encrypt(&[0x2a]).expect("message fits public bound");
346        assert_eq!(private.decrypt(&ciphertext), vec![0x2a]);
347    }
348
349    #[test]
350    fn generate_rejects_too_few_bits() {
351        let mut drbg = CtrDrbgAes256::new(&[0x91; 48]);
352        assert!(Cocks::generate(&mut drbg, 7).is_none());
353    }
354
355    #[test]
356    fn rejects_unordered_primes() {
357        let p = BigUint::from_u64(17);
358        let q = BigUint::from_u64(11);
359        assert!(Cocks::from_primes(&p, &q).is_none());
360    }
361
362    #[test]
363    fn key_serialization_roundtrip() {
364        let p = BigUint::from_u64(11);
365        let q = BigUint::from_u64(17);
366        let (public, private) = Cocks::from_primes(&p, &q).expect("valid key");
367
368        let public_blob = public.to_key_blob();
369        let private_blob = private.to_key_blob();
370        assert_eq!(
371            CocksPublicKey::from_key_blob(&public_blob),
372            Some(public.clone())
373        );
374        assert_eq!(
375            CocksPrivateKey::from_key_blob(&private_blob),
376            Some(private.clone())
377        );
378
379        let public_pem = public.to_pem();
380        let private_pem = private.to_pem();
381        let public_xml = public.to_xml();
382        let private_xml = private.to_xml();
383        assert_eq!(CocksPublicKey::from_pem(&public_pem), Some(public.clone()));
384        assert_eq!(
385            CocksPrivateKey::from_pem(&private_pem),
386            Some(private.clone())
387        );
388        assert_eq!(CocksPublicKey::from_xml(&public_xml), Some(public));
389        assert_eq!(CocksPrivateKey::from_xml(&private_xml), Some(private));
390    }
391
392    #[test]
393    fn generated_key_serialization_roundtrip() {
394        let mut drbg = CtrDrbgAes256::new(&[0xa1; 48]);
395        let (public, private) = Cocks::generate(&mut drbg, 32).expect("Cocks key generation");
396        let message = [0x07];
397
398        let public = CocksPublicKey::from_xml(&public.to_xml()).expect("public XML");
399        let private =
400            CocksPrivateKey::from_key_blob(&private.to_key_blob()).expect("private binary");
401        let ciphertext = public.encrypt(&message).expect("message fits");
402        assert_eq!(private.decrypt(&ciphertext), message.to_vec());
403    }
404
405    #[test]
406    fn byte_ciphertext_roundtrip() {
407        let p = BigUint::from_u64(13);
408        let q = BigUint::from_u64(23);
409        let (public, private) = Cocks::from_primes(&p, &q).expect("valid Cocks key");
410        let ciphertext = public
411            .encrypt_bytes(&[0x0b])
412            .expect("message fits public bound");
413        assert_eq!(private.decrypt_bytes(&ciphertext), Some(vec![0x0b]));
414    }
415}
cryptography/public_key/cocks.rs

cryptography/public_key/
cocks.rs
