openpgp: Fix RSA key generation with OpenSSL and RustCrypto.

  - Previously, there was a chance that we generated keys with p > q.
    Add a test.

4 files changed, 106 insertions, 1 deletions

diff --git a/openpgp/src/crypto/backend/cng/asymmetric.rs b/openpgp/src/crypto/backend/cng/asymmetric.rs
index 6eb81c51..4bd8fa70 100644
--- a/openpgp/src/crypto/backend/cng/asymmetric.rs
+++ b/openpgp/src/crypto/backend/cng/asymmetric.rs
@@ -812,7 +812,7 @@ where
         let q = mpi::MPI::new(blob.prime2());
         // RSA prime generation in CNG returns them in arbitrary order but
         // RFC 4880 expects `p < q`
-        let (p, q) = if p < q { (p, q) } else { (q, p) };
+        let (p, q) = rsa_sort_pq(p, q);
         // CNG `coeff` is `prime1`^-1 mod `prime2` so adjust for possible p,q reorder
         let big_p = BigUint::from_bytes_be(p.value());
         let big_q = BigUint::from_bytes_be(q.value());
@@ -913,6 +913,25 @@ fn round_up_to_multiple_of(n: usize, m: usize) -> usize {
     ((n + m - 1) / m) * m
 }
 
+/// Given the secret prime values `p` and `q`, returns the pair of
+/// primes so that the smaller one comes first.
+///
+/// Section 5.5.3 of RFC4880 demands that `p < q`.  This function can
+/// be used to order `p` and `q` accordingly.
+///
+/// Note: even though this function seems trivial, we introduce it as
+/// explicit abstraction.  The reason is that the function's
+/// expression also "works" (as in it compiles) for byte slices, but
+/// does the wrong thing, see [`crate::crypto::rsa_sort_raw_pq`].
+fn rsa_sort_pq(p: mpi::MPI, q: mpi::MPI)
+               -> (mpi::MPI, mpi::MPI)
+{
+    if p < q {
+        (p, q)
+    } else {
+        (q, p)
+    }
+}
 
 #[cfg(test)]
 mod tests {
diff --git a/openpgp/src/crypto/backend/openssl/asymmetric.rs b/openpgp/src/crypto/backend/openssl/asymmetric.rs
index 7d82732c..65ea8ef6 100644
--- a/openpgp/src/crypto/backend/openssl/asymmetric.rs
+++ b/openpgp/src/crypto/backend/openssl/asymmetric.rs
@@ -505,6 +505,8 @@ where
         let q = key
             .q()
             .ok_or_else(|| crate::Error::InvalidOperation("q".into()))?;
+        // RFC 4880: `p < q`
+        let (p, q) = rsa_sort_pq(p, q);
 
         let mut ctx = BigNumContext::new_secure()?;
         let mut u = BigNum::new_secure()?;
@@ -573,3 +575,23 @@ where
         }
     }
 }
+
+/// Given the secret prime values `p` and `q`, returns the pair of
+/// primes so that the smaller one comes first.
+///
+/// Section 5.5.3 of RFC4880 demands that `p < q`.  This function can
+/// be used to order `p` and `q` accordingly.
+///
+/// Note: even though this function seems trivial, we introduce it as
+/// explicit abstraction.  The reason is that the function's
+/// expression also "works" (as in it compiles) for byte slices, but
+/// does the wrong thing, see [`crate::crypto::rsa_sort_raw_pq`].
+fn rsa_sort_pq<'a>(p: &'a BigNumRef, q: &'a BigNumRef)
+                   -> (&'a BigNumRef, &'a BigNumRef)
+{
+    if p < q {
+        (p, q)
+    } else {
+        (q, p)
+    }
+}
diff --git a/openpgp/src/crypto/backend/rust/asymmetric.rs b/openpgp/src/crypto/backend/rust/asymmetric.rs
index 0d214edd..3c6e4d68 100644
--- a/openpgp/src/crypto/backend/rust/asymmetric.rs
+++ b/openpgp/src/crypto/backend/rust/asymmetric.rs
@@ -613,6 +613,8 @@ impl<R> Key4<SecretParts, R>
             [p, q] => (p, q),
             _ => panic!("RSA key generation resulted in wrong number of primes"),
         };
+        // RFC 4880: `p < q`
+        let (p, q) = rsa_sort_pq(p, q);
         let u = p.mod_inverse(q) // RFC 4880: u ≡ p⁻¹ (mod q)
             .and_then(|x| x.to_biguint())
             .expect("rsa crate did not generate coprime p and q");
@@ -780,3 +782,22 @@ impl<R> Key4<SecretParts, R>
     }
 }
 
+/// Given the secret prime values `p` and `q`, returns the pair of
+/// primes so that the smaller one comes first.
+///
+/// Section 5.5.3 of RFC4880 demands that `p < q`.  This function can
+/// be used to order `p` and `q` accordingly.
+///
+/// Note: even though this function seems trivial, we introduce it as
+/// explicit abstraction.  The reason is that the function's
+/// expression also "works" (as in it compiles) for byte slices, but
+/// does the wrong thing, see [`crate::crypto::rsa_sort_raw_pq`].
+fn rsa_sort_pq<'a>(p: &'a BigUint, q: &'a BigUint)
+                   -> (&'a BigUint, &'a BigUint)
+{
+    if p < q {
+        (p, q)
+    } else {
+        (q, p)
+    }
+}
diff --git a/openpgp/src/crypto/tests/rsa.rs b/openpgp/src/crypto/tests/rsa.rs
index 9bb82aad..948496ad 100644
--- a/openpgp/src/crypto/tests/rsa.rs
+++ b/openpgp/src/crypto/tests/rsa.rs
@@ -6,6 +6,49 @@ use crate::packet::{prelude::*, signature::subpacket::*};
 use crate::types::*;
 
 #[test]
+fn p_less_than_q() -> Result<()> {
+    use std::cmp::Ordering;
+    use crate::crypto::raw_bigint_cmp;
+
+    // Repeat four times to increase the sensitivity.
+    for _ in 0..4 {
+        // Check that p < q holds when generating an RSA key.
+        let key0 = Key4::generate_rsa(1024)?;
+        let t = key0.creation_time();
+        let (d0, p, q, u0) = extract(&key0);
+        assert_eq!(raw_bigint_cmp(&p, &q), Ordering::Less);
+
+        // Check that p < q holds when importing an RSA key.
+        //
+        // Note: p and q are swapped, i.e. p < q doesn't hold in the
+        // arguments of import_secret_rsa:
+        let key1 = Key4::import_secret_rsa(&d0, &q, &p, t)?;
+        let (d1, p, q, u1) = extract(&key1);
+        assert_eq!(raw_bigint_cmp(&p, &q), Ordering::Less);
+        assert_eq!(d0, d1);
+        assert_eq!(u0, u1);
+    }
+
+    fn extract(key: &Key4<key::SecretParts, key::PrimaryRole>)
+               -> (Vec<u8>, Vec<u8>, Vec<u8>, Vec<u8>)
+    {
+        match key.secret() {
+            SecretKeyMaterial::Unencrypted(s) => s.map(|s| match s {
+                mpi::SecretKeyMaterial::RSA { d, p, q, u } =>
+                    (d.value().into(),
+                     p.value().into(),
+                     q.value().into(),
+                     u.value().into()),
+                _ => unreachable!(),
+            }),
+            _ => unreachable!(),
+        }
+    }
+
+    Ok(())
+}
+
+#[test]
 fn fips_186_3_verification() -> Result<()> {
     if ! PublicKeyAlgorithm::RSAEncryptSign.is_supported() {
         eprintln!("Skipping because RSA is not supported.");