openpgp: Implement asymmetric key gen/import using Windows CNG API

3 files changed, 247 insertions, 13 deletions

diff --git a/Cargo.lock b/Cargo.lock
index 4176b720..f940a0cc 100644
--- a/Cargo.lock
+++ b/Cargo.lock
@@ -884,6 +884,9 @@ source = "registry+https://github.com/rust-lang/crates.io-index"
 name = "lazy_static"
 version = "1.4.0"
 source = "registry+https://github.com/rust-lang/crates.io-index"
+dependencies = [
+ "spin 0.5.2 (registry+https://github.com/rust-lang/crates.io-index)",
+]
 
 [[package]]
 name = "libc"
@@ -900,6 +903,11 @@ dependencies = [
 ]
 
 [[package]]
+name = "libm"
+version = "0.2.1"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+
+[[package]]
 name = "libsqlite3-sys"
 version = "0.15.0"
 source = "registry+https://github.com/rust-lang/crates.io-index"
@@ -1115,6 +1123,21 @@ dependencies = [
 ]
 
 [[package]]
+name = "num-bigint-dig"
+version = "0.6.0"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+dependencies = [
+ "autocfg 0.1.7 (registry+https://github.com/rust-lang/crates.io-index)",
+ "byteorder 1.3.4 (registry+https://github.com/rust-lang/crates.io-index)",
+ "lazy_static 1.4.0 (registry+https://github.com/rust-lang/crates.io-index)",
+ "libm 0.2.1 (registry+https://github.com/rust-lang/crates.io-index)",
+ "num-integer 0.1.43 (registry+https://github.com/rust-lang/crates.io-index)",
+ "num-iter 0.1.41 (registry+https://github.com/rust-lang/crates.io-index)",
+ "num-traits 0.2.12 (registry+https://github.com/rust-lang/crates.io-index)",
+ "smallvec 1.4.0 (registry+https://github.com/rust-lang/crates.io-index)",
+]
+
+[[package]]
 name = "num-integer"
 version = "0.1.43"
 source = "registry+https://github.com/rust-lang/crates.io-index"
@@ -1124,6 +1147,16 @@ dependencies = [
 ]
 
 [[package]]
+name = "num-iter"
+version = "0.1.41"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+dependencies = [
+ "autocfg 1.0.0 (registry+https://github.com/rust-lang/crates.io-index)",
+ "num-integer 0.1.43 (registry+https://github.com/rust-lang/crates.io-index)",
+ "num-traits 0.2.12 (registry+https://github.com/rust-lang/crates.io-index)",
+]
+
+[[package]]
 name = "num-traits"
 version = "0.2.12"
 source = "registry+https://github.com/rust-lang/crates.io-index"
@@ -1776,6 +1809,7 @@ dependencies = [
  "libc 0.2.74 (registry+https://github.com/rust-lang/crates.io-index)",
  "memsec 0.5.7 (registry+https://github.com/rust-lang/crates.io-index)",
  "nettle 7.0.0 (registry+https://github.com/rust-lang/crates.io-index)",
+ "num-bigint-dig 0.6.0 (registry+https://github.com/rust-lang/crates.io-index)",
  "quickcheck 0.9.2 (registry+https://github.com/rust-lang/crates.io-index)",
  "rand 0.7.3 (registry+https://github.com/rust-lang/crates.io-index)",
  "regex 1.3.9 (registry+https://github.com/rust-lang/crates.io-index)",
@@ -1926,6 +1960,11 @@ dependencies = [
 ]
 
 [[package]]
+name = "smallvec"
+version = "1.4.0"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+
+[[package]]
 name = "socket2"
 version = "0.3.11"
 source = "registry+https://github.com/rust-lang/crates.io-index"
@@ -1937,6 +1976,11 @@ dependencies = [
 ]
 
 [[package]]
+name = "spin"
+version = "0.5.2"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+
+[[package]]
 name = "string"
 version = "0.2.1"
 source = "registry+https://github.com/rust-lang/crates.io-index"
@@ -2570,6 +2614,7 @@ source = "registry+https://github.com/rust-lang/crates.io-index"
 "checksum lazy_static 1.4.0 (registry+https://github.com/rust-lang/crates.io-index)" = "e2abad23fbc42b3700f2f279844dc832adb2b2eb069b2df918f455c4e18cc646"
 "checksum libc 0.2.74 (registry+https://github.com/rust-lang/crates.io-index)" = "a2f02823cf78b754822df5f7f268fb59822e7296276d3e069d8e8cb26a14bd10"
 "checksum libloading 0.5.2 (registry+https://github.com/rust-lang/crates.io-index)" = "f2b111a074963af1d37a139918ac6d49ad1d0d5e47f72fd55388619691a7d753"
+"checksum libm 0.2.1 (registry+https://github.com/rust-lang/crates.io-index)" = "c7d73b3f436185384286bd8098d17ec07c9a7d2388a6599f824d8502b529702a"
 "checksum libsqlite3-sys 0.15.0 (registry+https://github.com/rust-lang/crates.io-index)" = "72b1e07fcc60484f42e246f0cf1f133940c98117c81b2cefcdf71be288069680"
 "checksum linked-hash-map 0.5.3 (registry+https://github.com/rust-lang/crates.io-index)" = "8dd5a6d5999d9907cda8ed67bbd137d3af8085216c2ac62de5be860bd41f304a"
 "checksum lock_api 0.3.4 (registry+https://github.com/rust-lang/crates.io-index)" = "c4da24a77a3d8a6d4862d95f72e6fdb9c09a643ecdb402d754004a557f2bec75"
@@ -2594,7 +2639,9 @@ source = "registry+https://github.com/rust-lang/crates.io-index"
 "checksum nettle-sys 2.0.4 (registry+https://github.com/rust-lang/crates.io-index)" = "b8629333ff5f3b74d251dae253e383cda9242410fac4244a4fe855469be101fb"
 "checksum new_debug_unreachable 1.0.4 (registry+https://github.com/rust-lang/crates.io-index)" = "e4a24736216ec316047a1fc4252e27dabb04218aa4a3f37c6e7ddbf1f9782b54"
 "checksum nom 4.2.3 (registry+https://github.com/rust-lang/crates.io-index)" = "2ad2a91a8e869eeb30b9cb3119ae87773a8f4ae617f41b1eb9c154b2905f7bd6"
+"checksum num-bigint-dig 0.6.0 (registry+https://github.com/rust-lang/crates.io-index)" = "b3d03c330f9f7a2c19e3c0b42698e48141d0809c78cd9b6219f85bd7d7e892aa"
 "checksum num-integer 0.1.43 (registry+https://github.com/rust-lang/crates.io-index)" = "8d59457e662d541ba17869cf51cf177c0b5f0cbf476c66bdc90bf1edac4f875b"
+"checksum num-iter 0.1.41 (registry+https://github.com/rust-lang/crates.io-index)" = "7a6e6b7c748f995c4c29c5f5ae0248536e04a5739927c74ec0fa564805094b9f"
 "checksum num-traits 0.2.12 (registry+https://github.com/rust-lang/crates.io-index)" = "ac267bcc07f48ee5f8935ab0d24f316fb722d7a1292e2913f0cc196b29ffd611"
 "checksum num_cpus 1.13.0 (registry+https://github.com/rust-lang/crates.io-index)" = "05499f3756671c15885fee9034446956fff3f243d6077b91e5767df161f766b3"
 "checksum opaque-debug 0.2.3 (registry+https://github.com/rust-lang/crates.io-index)" = "2839e79665f131bdb5782e51f2c6c9599c133c6098982a54c794358bf432529c"
@@ -2662,7 +2709,9 @@ source = "registry+https://github.com/rust-lang/crates.io-index"
 "checksum siphasher 0.2.3 (registry+https://github.com/rust-lang/crates.io-index)" = "0b8de496cf83d4ed58b6be86c3a275b8602f6ffe98d3024a869e124147a9a3ac"
 "checksum slab 0.4.2 (registry+https://github.com/rust-lang/crates.io-index)" = "c111b5bd5695e56cffe5129854aa230b39c93a305372fdbb2668ca2394eea9f8"
 "checksum smallvec 0.6.13 (registry+https://github.com/rust-lang/crates.io-index)" = "f7b0758c52e15a8b5e3691eae6cc559f08eee9406e548a4477ba4e67770a82b6"
+"checksum smallvec 1.4.0 (registry+https://github.com/rust-lang/crates.io-index)" = "c7cb5678e1615754284ec264d9bb5b4c27d2018577fd90ac0ceb578591ed5ee4"
 "checksum socket2 0.3.11 (registry+https://github.com/rust-lang/crates.io-index)" = "e8b74de517221a2cb01a53349cf54182acdc31a074727d3079068448c0676d85"
+"checksum spin 0.5.2 (registry+https://github.com/rust-lang/crates.io-index)" = "6e63cff320ae2c57904679ba7cb63280a3dc4613885beafb148ee7bf9aa9042d"
 "checksum string 0.2.1 (registry+https://github.com/rust-lang/crates.io-index)" = "d24114bfcceb867ca7f71a0d3fe45d45619ec47a6fbfa98cb14e14250bfa5d6d"
 "checksum string_cache 0.7.5 (registry+https://github.com/rust-lang/crates.io-index)" = "89c058a82f9fd69b1becf8c274f412281038877c553182f1d02eb027045a2d67"
 "checksum string_cache_codegen 0.4.4 (registry+https://github.com/rust-lang/crates.io-index)" = "f0f45ed1b65bf9a4bf2f7b7dc59212d1926e9eaf00fa998988e420fd124467c6"
diff --git a/openpgp/Cargo.toml b/openpgp/Cargo.toml
index e4faece2..26949d8c 100644
--- a/openpgp/Cargo.toml
+++ b/openpgp/Cargo.toml
@@ -51,6 +51,7 @@ unicode-normalization = "= 0.1.9"
 
 [target.'cfg(windows)'.dependencies]
 win-crypto-ng = { version = "0.2", features = ["rand"], optional = true }
+num-bigint-dig = { version = "0.6", default-features = false, optional = true }
 
 [build-dependencies]
 lalrpop = "0.17"
@@ -68,7 +69,7 @@ rpassword = "=4.0.3"
 default = ["compression", "crypto-nettle"]
 # TODO(#333): Allow for/implement more backends
 crypto-nettle = ["nettle"]
-crypto-cng = ["win-crypto-ng"]
+crypto-cng = ["win-crypto-ng", "num-bigint-dig"]
 
 # The compression algorithms.
 compression = ["compression-deflate", "compression-bzip2"]
diff --git a/openpgp/src/crypto/backend/cng/asymmetric.rs b/openpgp/src/crypto/backend/cng/asymmetric.rs
index f09d89be..5e5ffdc4 100644
--- a/openpgp/src/crypto/backend/cng/asymmetric.rs
+++ b/openpgp/src/crypto/backend/cng/asymmetric.rs
@@ -3,16 +3,22 @@
 
 use std::time::SystemTime;
 
-use crate::Result;
+use crate::{Error, Result};
 
 use crate::crypto::asymmetric::{Decryptor, KeyPair, Signer};
+use crate::crypto::mem::Protected;
 use crate::crypto::mpi;
 use crate::crypto::SessionKey;
 use crate::packet::key::{Key4, SecretParts};
 use crate::packet::{self, key, Key};
-use crate::types::SymmetricAlgorithm;
+use crate::types::{PublicKeyAlgorithm, SymmetricAlgorithm};
 use crate::types::{Curve, HashAlgorithm};
 
+use num_bigint_dig::{traits::ModInverse, BigInt, BigUint};
+use win_crypto_ng as cng;
+
+const CURVE25519_SIZE: usize = 32;
+
 impl Signer for KeyPair {
     fn public(&self) -> &Key<key::PublicParts, key::UnspecifiedRole> {
         KeyPair::public(self)
@@ -58,7 +64,7 @@ where
     ///
     /// The ECDH key will use hash algorithm `hash` and symmetric
     /// algorithm `sym`.  If one or both are `None` secure defaults
-    /// will be used.  The key will have it's creation date set to
+    /// will be used.  The key will have its creation date set to
     /// `ctime` or the current time if `None` is given.
     pub fn import_secret_cv25519<H, S, T>(
         private_key: &[u8],
@@ -71,20 +77,49 @@ where
         S: Into<Option<SymmetricAlgorithm>>,
         T: Into<Option<SystemTime>>,
     {
-        unimplemented!()
+        use cng::asymmetric::{AsymmetricAlgorithm, AsymmetricAlgorithmId, Ecdh, Private};
+        use cng::asymmetric::{AsymmetricKey, Export};
+        use cng::asymmetric::ecc::{Curve25519, NamedCurve};
+
+        let provider = AsymmetricAlgorithm::open(AsymmetricAlgorithmId::Ecdh(NamedCurve::Curve25519))?;
+        let key = AsymmetricKey::<Ecdh<Curve25519>, Private>::import_from_parts(
+            &provider,
+            private_key
+        )?;
+        let blob = key.export()?;
+
+        let mut public = [0u8; 1 + CURVE25519_SIZE];
+        public[0] = 0x40;
+        &mut public[1..].copy_from_slice(blob.x());
+
+        // Reverse the scalar.  See
+        // https://lists.gnupg.org/pipermail/gnupg-devel/2018-February/033437.html.
+        let mut private = blob.d().to_vec();
+        private.reverse();
+
+        Self::with_secret(
+            ctime.into().unwrap_or_else(SystemTime::now),
+            PublicKeyAlgorithm::ECDH,
+            mpi::PublicKey::ECDH {
+                curve: Curve::Cv25519,
+                hash: hash.into().unwrap_or(HashAlgorithm::SHA512),
+                sym: sym.into().unwrap_or(SymmetricAlgorithm::AES256),
+                q: mpi::MPI::new(&public),
+            },
+            mpi::SecretKeyMaterial::ECDH { scalar: private.into() }.into()
+        )
     }
 
     /// Creates a new OpenPGP secret key packet for an existing Ed25519 key.
     ///
-    /// The ECDH key will use hash algorithm `hash` and symmetric
-    /// algorithm `sym`.  If one or both are `None` secure defaults
-    /// will be used.  The key will have it's creation date set to
-    /// `ctime` or the current time if `None` is given.
+    /// The key will have it's creation date set to `ctime` or the current time
+    /// if `None` is given.
     pub fn import_secret_ed25519<T>(private_key: &[u8], ctime: T) -> Result<Self>
     where
         T: Into<Option<SystemTime>>,
     {
-        unimplemented!()
+        // CNG doesn't support Ed25519 at all
+        Err(Error::UnsupportedEllipticCurve(Curve::Ed25519).into())
     }
 
     /// Creates a new OpenPGP public key packet for an existing RSA key.
@@ -96,12 +131,79 @@ where
     where
         T: Into<Option<SystemTime>>,
     {
-        unimplemented!()
+        // RFC 4880: `p < q`
+        let (p, q) = if p < q { (p, q) } else { (q, p) };
+
+        // CNG can't compute the public key from the private one, so do it ourselves
+        let big_p = BigUint::from_bytes_be(p);
+        let big_q = BigUint::from_bytes_be(q);
+        let n = big_p.clone() * big_q.clone();
+
+        let big_d = BigUint::from_bytes_be(d);
+        let big_phi = (big_p.clone() - 1u32) * (big_q.clone() - 1u32);
+        let e = big_d.mod_inverse(big_phi) // e ≡ d⁻¹ (mod 𝜙)
+            .and_then(|x: BigInt| x.to_biguint())
+            .ok_or_else(|| Error::MalformedMPI("RSA: `d` and `(p-1)(q-1)` aren't coprime".into()))?;
+
+        let u: BigUint = big_p.mod_inverse(big_q) // RFC 4880: u ≡ p⁻¹ (mod q)
+            .and_then(|x: BigInt| x.to_biguint())
+            .ok_or_else(|| Error::MalformedMPI("RSA: `p` and `q` aren't coprime".into()))?;
+
+        Self::with_secret(
+            ctime.into().unwrap_or_else(SystemTime::now),
+            PublicKeyAlgorithm::RSAEncryptSign,
+            mpi::PublicKey::RSA {
+                e: mpi::MPI::new(&e.to_bytes_be()),
+                n: mpi::MPI::new(&n.to_bytes_be()),
+            },
+            mpi::SecretKeyMaterial::RSA {
+                d: mpi::MPI::new(d).into(),
+                p: mpi::MPI::new(p).into(),
+                q: mpi::MPI::new(q).into(),
+                u: mpi::MPI::new(&u.to_bytes_be()).into(),
+            }.into()
+        )
     }
 
     /// Generates a new RSA key with a public modulos of size `bits`.
     pub fn generate_rsa(bits: usize) -> Result<Self> {
-        unimplemented!()
+        use win_crypto_ng::asymmetric::{AsymmetricKey, Rsa};
+
+        let blob = AsymmetricKey::builder(Rsa)
+            .key_bits(bits as u32)
+            .build()?
+            .export_full()?;
+
+        let public = mpi::PublicKey::RSA {
+            e: mpi::MPI::new(blob.pub_exp()).into(),
+            n: mpi::MPI::new(blob.modulus()).into(),
+        };
+
+        let p = mpi::MPI::new(blob.prime1());
+        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) };
+        // 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());
+        let u = big_p.mod_inverse(big_q) // RFC 4880: u ≡ p⁻¹ (mod q)
+            .and_then(|x: BigInt| x.to_biguint())
+            .expect("CNG to generate a valid RSA key (where p, q are coprime)");
+
+        let private = mpi::SecretKeyMaterial::RSA {
+            p: p.into(),
+            q: q.into(),
+            d: mpi::MPI::new(blob.priv_exp()).into(),
+            u: mpi::MPI::new(&u.to_bytes_be()).into(),
+        };
+
+        Self::with_secret(
+            SystemTime::now(),
+            PublicKeyAlgorithm::RSAEncryptSign,
+            public,
+            private.into()
+        )
     }
 
     /// Generates a new ECC key over `curve`.
@@ -112,6 +214,88 @@ where
     /// `for_signing == false` and `curve == Ed25519`.
     /// signing/encryption
     pub fn generate_ecc(for_signing: bool, curve: Curve) -> Result<Self> {
-        unimplemented!()
+        // CNG doesn't support Ed25519 at all
+        if (for_signing && curve == Curve::Cv25519) || curve == Curve::Ed25519 {
+            return Err(Error::UnsupportedEllipticCurve(curve).into());
+        }
+
+        use crate::PublicKeyAlgorithm::*;
+
+        use cng::asymmetric::{ecc, Export};
+        use cng::asymmetric::{AsymmetricKey, AsymmetricAlgorithmId, Ecdh};
+
+        let (algo, public, private) = match curve {
+            Curve::NistP256 | Curve::NistP384 | Curve::NistP521 => {
+                let (cng_curve, hash) = match curve {
+                    Curve::NistP256 => (ecc::NamedCurve::NistP256, HashAlgorithm::SHA256),
+                    Curve::NistP384 => (ecc::NamedCurve::NistP384, HashAlgorithm::SHA384),
+                    Curve::NistP521 => (ecc::NamedCurve::NistP521, HashAlgorithm::SHA512),
+                    _ => unreachable!()
+                };
+
+                let ecc_algo = if for_signing {
+                    AsymmetricAlgorithmId::Ecdsa(cng_curve)
+                } else {
+                    AsymmetricAlgorithmId::Ecdh(cng_curve)
+                };
+
+                let blob = AsymmetricKey::builder(ecc_algo).build()?.export()?;
+                let blob = match blob.try_into::<cng::key::EccKeyPrivateBlob>() {
+                    Ok(blob) => blob,
+                    // Dynamic algorithm specified is either ECDSA or ECDH so
+                    // exported blob should be of appropriate type
+                    Err(..) => unreachable!()
+                };
+                let field_sz = cng_curve.key_bits() as usize;
+
+                let q = mpi::MPI::new_point(blob.x(), blob.y(), field_sz);
+                let scalar = mpi::MPI::new(blob.d());
+
+                if for_signing {
+                    (
+                        ECDSA,
+                        mpi::PublicKey::ECDSA { curve, q },
+                        mpi::SecretKeyMaterial::ECDSA { scalar: scalar.into() },
+                    )
+                } else {
+                    let sym = SymmetricAlgorithm::AES256;
+                    (
+                        ECDH,
+                        mpi::PublicKey::ECDH { curve, q, hash, sym },
+                        mpi::SecretKeyMaterial::ECDH { scalar: scalar.into() },
+                    )
+                }
+            },
+            Curve::Cv25519 => {
+                debug_assert!(!for_signing);
+                let blob = AsymmetricKey::builder(Ecdh(ecc::Curve25519)).build()?.export()?;
+
+                let mut public = [0u8; 1 + CURVE25519_SIZE];
+                public[0] = 0x40;
+                &mut public[1..].copy_from_slice(blob.x());
+
+                // Reverse the scalar.  See
+                // https://lists.gnupg.org/pipermail/gnupg-devel/2018-February/033437.html.
+                let mut private: Protected = blob.d().into();
+                private.reverse();
+
+                (
+                    ECDH,
+                    mpi::PublicKey::ECDH {
+                        curve,
+                        q: mpi::MPI::new(&public),
+                        hash: HashAlgorithm::SHA256,
+                        sym: SymmetricAlgorithm::AES256,
+                    },
+                    mpi::SecretKeyMaterial::ECDH { scalar: private.into() }
+                )
+            },
+            // TODO: Support Brainpool curves
+            curve => {
+                return Err(Error::UnsupportedEllipticCurve(curve).into());
+            }
+        };
+
+        Self::with_secret(SystemTime::now(), algo, public, private.into())
     }
 }