WIP: openpgp: Editing certificates.

  - XXX: needs top-level documentation on how to edit certs

  - XXX: specially the twist with the expiration times:

    - not expired cert -> editing -> doesn't change expiration
    - not expired cert -> editing + explicit new expiration -> change expiration
    - expired cert -> editing -> change expiration (surprise: doesn't expire at all)
    - expired cert -> editing + explicit new expiration -> change expiration

  - Fixes #483 and #218.

4 files changed, 915 insertions, 61 deletions

diff --git a/openpgp/NEWS b/openpgp/NEWS
index 450ce629..8db9ecef 100644
--- a/openpgp/NEWS
+++ b/openpgp/NEWS
@@ -4,6 +4,14 @@
 
 * Changes in 1.8.0
 ** New functionality
+   - cert::CertBuilder can now edit certificates
+   - cert::CertBuilder can now use remote keys
+   - cert::CertBuilder now implements From<Cert>
+   - cert::CertBuilder now implements From<Key<PublicParts, _>>
+   - cert::CertBuilder now implements From<Key<SecretParts, _>>
+   - cert::CertBuilder::add_signer
+   - cert::CertBuilder::insert_subkey
+   - cert::CertBuilder::insert_subkey_with
    - crypto::Signer::acceptable_hashes
    - Fingerprint::V5
 * Changes in 1.7.0
diff --git a/openpgp/src/cert.rs b/openpgp/src/cert.rs
index 0924d334..3c92b09c 100644
--- a/openpgp/src/cert.rs
+++ b/openpgp/src/cert.rs
@@ -28,6 +28,7 @@
 //! # Common Operations
 //!
 //!  - *Generating a certificate*: See the [`CertBuilder`] module.
+//!  - *Modify a certificate*: Also see the [`CertBuilder#modifying-existing-certificates`] module.
 //!  - *Parsing a certificate*: See the [`Parser` implementation] for `Cert`.
 //!  - *Parsing a keyring*: See the [`CertParser`] module.
 //!  - *Serializing a certificate*: See the [`Serialize`
diff --git a/openpgp/src/cert/builder.rs b/openpgp/src/cert/builder.rs
index e9ff41db..9f87c0c4 100644
--- a/openpgp/src/cert/builder.rs
+++ b/openpgp/src/cert/builder.rs
@@ -1,5 +1,6 @@
 use std::time;
-use std::marker::PhantomData;
+use std::collections::BTreeMap;
+use std::convert::TryFrom;
 
 use crate::packet;
 use crate::packet::{
@@ -7,8 +8,14 @@ use crate::packet::{
     Key,
     key::Key4,
 };
-use crate::Result;
-use crate::packet::Signature;
+use crate::{
+    Fingerprint,
+    Result,
+};
+use crate::packet::{
+    Packet,
+    Signature,
+};
 use crate::packet::signature::{
     self,
     SignatureBuilder,
@@ -182,6 +189,49 @@ impl CipherSuite {
             },
         }.map(|key| key.into())
     }
+
+    /// Guesses an appropriate cipher suite for a given key.
+    fn from_key<P, R>(key: &Key<P, R>) -> Option<Self>
+    where
+        P: key::KeyParts,
+        R: key::KeyRole,
+    {
+        use crate::{
+            crypto::mpi::PublicKey::{self, *},
+            types::Curve::{self, *},
+        };
+
+        let bits = key.mpis().bits()?;
+        match key.mpis() {
+            // Map all old-school algorithms to RSA.
+            | RSA { .. }
+            | DSA { .. }
+            | ElGamal { .. } => {
+                if bits < 3072 {
+                    Some(Self::RSA2k)
+                } else if bits <= 4096 {
+                    Some(Self::RSA3k)
+                } else {
+                    Some(Self::RSA4k)
+                }
+            },
+            | EdDSA { curve, .. }
+            | ECDSA { curve, .. }
+            | ECDH { curve, .. } => {
+                match curve {
+                    NistP256 => Some(Self::P256),
+                    NistP384 => Some(Self::P384),
+                    NistP521 => Some(Self::P521),
+                    Ed25519 => Some(Self::Cv25519),
+                    Cv25519 => Some(Self::Cv25519),
+                    BrainpoolP256 => None,
+                    BrainpoolP512 => None,
+                    Curve::Unknown(_) => None,
+                }
+            },
+            PublicKey::Unknown { .. } => None,
+        }
+    }
 }
 
 #[derive(Clone, Debug)]
@@ -191,6 +241,8 @@ pub struct KeyBlueprint {
     // If not None, uses the specified ciphersuite.  Otherwise, uses
     // CertBuilder::ciphersuite.
     ciphersuite: Option<CipherSuite>,
+    /// An existing subkey, if any.
+    key: Option<Key<key::UnspecifiedParts, key::SubordinateRole>>,
 }
 assert_send_and_sync!(KeyBlueprint);
 
@@ -207,6 +259,15 @@ assert_send_and_sync!(KeyBlueprint);
 /// [`UserAttribute`s]: crate::packet::user_attribute::UserAttribute
 /// [`Key`s]: crate::packet::Key
 ///
+/// # Modifying existing certificates
+///
+/// Besides generating new certificates, the `CertBuilder` can be used
+/// to modify existing certificates: new User IDs and subkeys can be
+/// added, and the expiration time of expired certificates and subkeys
+/// can be extended.
+///
+/// XXX
+///
 /// # Security considerations
 ///
 /// ## Expiration
@@ -259,6 +320,7 @@ assert_send_and_sync!(KeyBlueprint);
 /// # }
 /// ```
 pub struct CertBuilder<'a> {
+    cert: Option<Cert>,
     creation_time: Option<std::time::SystemTime>,
     ciphersuite: CipherSuite,
     primary: KeyBlueprint,
@@ -267,12 +329,41 @@ pub struct CertBuilder<'a> {
     user_attributes: Vec<(Option<SignatureBuilder>, packet::UserAttribute)>,
     password: Option<Password>,
     revocation_keys: Option<Vec<RevocationKey>>,
-    phantom: PhantomData<&'a ()>,
+    signers: BTreeMap<Fingerprint, Box<dyn Signer + Send + Sync + 'a>>,
 }
 assert_send_and_sync!(CertBuilder<'_>);
 
+impl From<Cert> for CertBuilder<'_> {
+    fn from(c: Cert) -> Self {
+        // Guess a suitable cipher suite.
+        let cs =
+            c.keys()
+            .filter_map(|k| CipherSuite::from_key(&k))
+            .next()
+            .unwrap_or_default();
+
+        let mut b = CertBuilder::new()
+            .set_cipher_suite(cs);
+
+        b.cert = Some(c);
+        b
+    }
+}
+
+impl From<Key<key::PublicParts, key::PrimaryRole>> for CertBuilder<'_> {
+    fn from(k: Key<key::PublicParts, key::PrimaryRole>) -> Self {
+        Cert::try_from(Packet::from(k)).unwrap().into()
+    }
+}
+
+impl From<Key<key::SecretParts, key::PrimaryRole>> for CertBuilder<'_> {
+    fn from(k: Key<key::SecretParts, key::PrimaryRole>) -> Self {
+        Cert::try_from(Packet::from(k)).unwrap().into()
+    }
+}
+
 #[allow(clippy::new_without_default)]
-impl CertBuilder<'_> {
+impl<'a> CertBuilder<'a> {
     /// Returns a new `CertBuilder`.
     ///
     /// The returned builder is configured to generate a minimal
@@ -311,19 +402,21 @@ impl CertBuilder<'_> {
     /// ```
     pub fn new() -> Self {
         CertBuilder {
+            cert: None,
             creation_time: None,
             ciphersuite: CipherSuite::default(),
             primary: KeyBlueprint{
                 flags: KeyFlags::empty().set_certification(),
                 validity: None,
                 ciphersuite: None,
+                key: None,
             },
             subkeys: vec![],
             userids: vec![],
             user_attributes: vec![],
             password: None,
             revocation_keys: None,
-            phantom: PhantomData,
+            signers: Default::default(),
         }
     }
 
@@ -374,6 +467,104 @@ impl CertBuilder<'_> {
         builder
     }
 
+    /// Adds the given signer so that it can be used to generate
+    /// signatures.
+    ///
+    /// The `CertBuilder` needs to create signatures to bind the
+    /// certificate's components together.  If all the keys are
+    /// generated by the `CertBuilder`, the signers are extracted from
+    /// the freshly generated key material.  On the other hand, if the
+    /// secret key material is not available, for example because it
+    /// resides on a smart card, the signers have to be provided
+    /// explicitly.
+    ///
+    /// # Examples
+    ///
+    /// This example demonstrates how to create a certificate with
+    /// remote secret key material.
+    ///
+    /// ```
+    /// # fn main() -> sequoia_openpgp::Result<()> {
+    /// use std::time::{SystemTime, Duration};
+    /// use std::convert::TryFrom;
+    ///
+    /// use sequoia_openpgp as openpgp;
+    /// use openpgp::cert::prelude::*;
+    /// # use openpgp::Result;
+    /// # use openpgp::crypto::Signer;
+    /// # use openpgp::packet::prelude::*;
+    /// use openpgp::types::KeyFlags;
+    ///
+    /// # fn make_signing_key() -> Result<(Key<key::PublicParts, key::UnspecifiedRole>,
+    /// #                                  impl Signer)>
+    /// # {
+    /// #     use openpgp::types::Curve;
+    /// #     let k = Key4::generate_ecc(true, Curve::Ed25519)?;
+    /// #     let signer = k.clone().into_keypair()?;
+    /// #     let (k, _) = k.take_secret();
+    /// #     Ok((k.into(), signer))
+    /// # }
+    /// # fn make_encryption_key() -> Result<Key<key::PublicParts, key::UnspecifiedRole>>
+    /// # {
+    /// #     use openpgp::types::Curve;
+    /// #     let k = Key4::generate_ecc(false, Curve::Cv25519)?;
+    /// #     let (k, _) = k.take_secret();
+    /// #     Ok(k.into())
+    /// # }
+    /// #
+    /// // First, create a primary key.
+    /// let (primary, primary_signer) = make_signing_key()?;
+    /// # let primary_fp = primary.fingerprint();
+    /// // Mark it as primary.
+    /// let primary = primary.role_into_primary();
+    ///
+    /// // Start building a certificate from it.
+    /// let mut builder = CertBuilder::from(primary)
+    ///     .add_signer(primary_signer)
+    ///     .add_userid("Juliett");
+    ///
+    /// // Now we create an encryption subkey.
+    /// let subkey = make_encryption_key()?;
+    /// # let encryption_fp = subkey.fingerprint();
+    /// // Mark it as subkey.
+    /// let subkey = subkey.role_into_subordinate();
+    /// builder = builder.insert_subkey(
+    ///     subkey, KeyFlags::empty().set_transport_encryption(), None)?;
+    ///
+    /// // Now we create a signing subkey.
+    /// let (subkey, subkey_signer) = make_signing_key()?;
+    /// # let signing_fp = subkey.fingerprint();
+    /// // Mark it as subkey.
+    /// let subkey = subkey.role_into_subordinate();
+    /// builder = builder.insert_subkey(
+    ///     subkey, KeyFlags::empty().set_signing(), None)?
+    /// // For signing-capable subkeys, it is necessary to pass in the
+    /// // corresponding signer so that the builder can create a
+    /// // primary key binding signature using it.
+    ///     .add_signer(subkey_signer);
+    ///
+    /// let (cert, _) = builder.generate()?;
+    /// #
+    /// # let p = &openpgp::policy::StandardPolicy::new();
+    /// # assert_eq!(cert.fingerprint(), primary_fp);
+    /// # assert_eq!(cert.userids().count(), 1);
+    /// # assert_eq!(cert.keys().count(), 3);
+    /// # assert_eq!(cert.with_policy(p, None)?.keys().for_transport_encryption()
+    /// #            .count(), 1);
+    /// # assert_eq!(cert.with_policy(p, None)?.keys().for_transport_encryption()
+    /// #            .next().unwrap().fingerprint(), encryption_fp);
+    /// # assert_eq!(cert.with_policy(p, None)?.keys().for_signing().count(), 1);
+    /// # assert_eq!(cert.with_policy(p, None)?.keys().for_signing()
+    /// #            .next().unwrap().fingerprint(), signing_fp);
+    /// # Ok(()) }
+    /// ```
+    pub fn add_signer<S>(mut self, signer: S) -> Self
+        where S: Signer + Send + Sync + 'a
+    {
+        self.signers.insert(signer.public().fingerprint(), Box::new(signer));
+        self
+    }
+
     /// Sets the creation time.
     ///
     /// If `creation_time` is not `None`, this causes the
@@ -1071,6 +1262,7 @@ impl CertBuilder<'_> {
             flags,
             validity: validity.into(),
             ciphersuite: cs.into(),
+            key: None,
         }));
         self
     }
@@ -1149,6 +1341,285 @@ impl CertBuilder<'_> {
                     flags,
                     validity: validity.into(),
                     ciphersuite: cs.into(),
+                    key: None,
+                }));
+                Ok(self)
+            },
+            t =>
+                Err(Error::InvalidArgument(format!(
+                    "Signature type is not a subkey binding: {}", t)).into()),
+        }
+    }
+
+    /// Adds or refreshes an existing subkey.
+    ///
+    /// If the certificate builder has been derived from an existing
+    /// cert with `key`, the latest binding signature is used as a
+    /// template for creating the new binding signature.  To supply
+    /// your own template, use [`CertBuilder::insert_subkey_with`].
+    ///
+    /// If `flags` is `None`, the certificate builder must have been
+    /// derived from an existing cert with `key`.  Then, the `flags`
+    /// are taken from the existing binding, i.e. the key will have
+    /// the same flags.
+    ///
+    /// If `validity` is `None`, the subkey will be valid for the same
+    /// period as the primary key.
+    ///
+    /// Likewise, if `cs` is `None`, the same cipher suite is used as
+    /// for the primary key.
+    ///
+    /// # Examples
+    ///
+    /// Demonstrates how to extend the validity of an certificate with
+    /// all of its subkeys:
+    ///
+    /// ```
+    /// # fn main() -> sequoia_openpgp::Result<()> {
+    /// use sequoia_openpgp as openpgp;
+    /// use openpgp::cert::prelude::*;
+    /// use openpgp::policy::StandardPolicy;
+    /// use openpgp::types::KeyFlags;
+    ///
+    /// let p = &StandardPolicy::new();
+    /// let h = std::time::Duration::new(60 * 60, 0);
+    /// let now = std::time::SystemTime::now();
+    /// let past = now - 2 * h;
+    /// let future = now + 2 * h;
+    ///
+    /// // Generate an cert in the past that is still valid now, but
+    /// // will expire in an hour.
+    /// let (c, _) = CertBuilder::new()
+    ///     .set_creation_time(past)
+    ///     .set_validity_period(3 * h)
+    ///     .add_userid("Juliett")
+    ///     .add_signing_subkey()
+    ///     .generate()?;
+    /// assert_eq!(c.with_policy(p, now)?.userids().count(), 1);
+    /// assert_eq!(c.with_policy(p, now)?.keys().for_signing().count(), 1);
+    /// assert!(c.keys().subkeys().next().unwrap().with_policy(p, now)?.alive().is_ok());
+    /// assert!(c.keys().subkeys().next().unwrap().with_policy(p, future)?.alive().is_err());
+    ///
+    /// // Freshen the cert using the `CertBuilder`.
+    /// let mut b = CertBuilder::from(c.clone())
+    ///     .set_creation_time(now)
+    ///     .set_validity_period(3 * h)
+    ///     .add_userid("Julia");
+    /// // We need to re-insert all the subkeys whose expiration times
+    /// // we want to extend.
+    /// for sk in c.keys().subkeys() {
+    ///     b = b.insert_subkey(sk.key().clone(), None, None)?;
+    ///
+    ///     // For signing-capable subkeys, we also need to supply the
+    ///     // signer.
+    ///     if let Ok(signer) = sk.key().clone().parts_into_secret()
+    ///         .and_then(|k| k.into_keypair())
+    ///     {
+    ///         b = b.add_signer(signer);
+    ///     }
+    /// }
+    /// let (c, _) = b.generate()?;
+    /// assert_eq!(c.with_policy(p, now)?.userids().count(), 2);
+    /// assert_eq!(c.with_policy(p, now)?.keys().for_signing().count(), 1);
+    /// assert!(c.keys().subkeys().next().unwrap().with_policy(p, now)?.alive().is_ok());
+    /// assert!(c.keys().subkeys().next().unwrap().with_policy(p, future)?.alive().is_ok());
+    /// # Ok(()) }
+    /// ```
+    pub fn insert_subkey<P, F, T>(mut self,
+                                  key: Key<P, key::SubordinateRole>,
+                                  flags: F, validity: T)
+                                  -> Result<Self>
+    where
+        P: key::KeyParts,
+        F: Into<Option<KeyFlags>>,
+        T: Into<Option<time::Duration>>,
+    {
+        // We don't quite know what the "current" time is, so we go
+        // with the latest binding signature instead.
+        let template = self.cert.as_ref()
+            .and_then(
+                |c| c.keys().subkeys().key_handle(key.fingerprint()).next())
+            .and_then(
+                |ka| ka.self_signatures().next());
+
+        // Maybe get flags from the existing signature.
+        let mut flags = flags.into();
+        if flags.is_none() {
+            if let Some(sig) = &template {
+                if let Some(f) = sig.key_flags() {
+                    flags = Some(f);
+                } else {
+                    return Err(Error::InvalidOperation(
+                        "Existing key binding signature has no key flags"
+                            .into()).into());
+                }
+            } else {
+                return Err(Error::InvalidArgument(
+                    "Key flags are mandatory if the key was not bound before"
+                        .into()).into());
+            }
+        }
+        let flags = flags.expect("set above");
+
+        self.subkeys.push((
+            template.map(|sig| sig.clone().into()),
+            KeyBlueprint {
+                flags,
+                validity: validity.into(),
+                ciphersuite: None,
+                key: Some(key.parts_into_unspecified()),
+            }));
+        Ok(self)
+    }
+
+    /// Adds or refreshes an existing subkey with a binding signature
+    /// based on `builder`.
+    ///
+    /// Adds `key` to the certificate, creating the binding signature
+    /// using `builder`.  The `builder`s signature type must be
+    /// [`SubkeyBinding`].
+    ///
+    /// If the certificate builder has been derived from an existing
+    /// cert with `key`, you can reuse the latest binding signature as
+    /// a template for creating the new binding signature by using
+    /// [`CertBuilder::insert_subkey`].
+    ///
+    /// If `flags` is `None`, the certificate builder must have been
+    /// derived from an existing cert with `key`.  Then, the `flags`
+    /// are taken from the existing binding, i.e. the key will have
+    /// the same flags.
+    ///
+    /// The key generation step uses `builder` as a template, but adds
+    /// all subpackets that the signature needs to be a valid binding
+    /// signature.  If you need more control, or want to adopt
+    /// existing keys, consider using
+    /// [`Key::bind`](crate::packet::Key::bind).
+    ///
+    /// The following modifications are performed on `builder`:
+    ///
+    ///   - An appropriate hash algorithm is selected.
+    ///
+    ///   - The creation time is set.
+    ///
+    ///   - Key metadata is added (key flags, key validity period).
+    ///
+    ///   [`SubkeyBinding`]: crate::types::SignatureType::SubkeyBinding
+    ///
+    /// If `validity` is `None`, the subkey will be valid for the same
+    /// period as the primary key.
+    ///
+    /// # Examples
+    ///
+    /// Demonstrates how to extend the validity of an certificate with
+    /// all of its subkeys.  But, we do not simply want to use the
+    /// current binding signature as template, we need to update the
+    /// `code-signing@policy.example.org` notation data to the current
+    /// policy version.
+    ///
+    /// ```
+    /// # fn main() -> sequoia_openpgp::Result<()> {
+    /// use sequoia_openpgp as openpgp;
+    /// use openpgp::cert::prelude::*;
+    /// use openpgp::packet::{prelude::*, signature::subpacket::*};
+    /// use openpgp::policy::StandardPolicy;
+    /// use openpgp::types::{KeyFlags, SignatureType};
+    ///
+    /// let p = &mut StandardPolicy::new();
+    /// p.good_critical_notations(&["code-signing@policy.example.org"]);
+    /// let h = std::time::Duration::new(60 * 60, 0);
+    /// let now = std::time::SystemTime::now();
+    /// let past = now - 2 * h;
+    /// let future = now + 2 * h;
+    ///
+    /// // Generate an cert in the past that is still valid now, but
+    /// // will expire in an hour.
+    /// let (c, _) = CertBuilder::new()
+    ///     .set_creation_time(past)
+    ///     .set_validity_period(3 * h)
+    ///     .add_userid("Juliett")
+    ///     .add_signing_subkey()
+    ///     .generate()?;
+    /// assert_eq!(c.with_policy(p, now)?.userids().count(), 1);
+    /// assert_eq!(c.with_policy(p, now)?.keys().for_signing().count(), 1);
+    /// assert!(c.keys().subkeys().next().unwrap().with_policy(p, now)?.alive().is_ok());
+    /// assert!(c.keys().subkeys().next().unwrap().with_policy(p, future)?.alive().is_err());
+    ///
+    /// // Freshen the cert using the `CertBuilder`.
+    /// let mut b = CertBuilder::from(c.clone())
+    ///     .set_creation_time(now)
+    ///     .set_validity_period(3 * h)
+    ///     .add_userid("Julia");
+    /// // We need to re-insert all the subkeys whose expiration times
+    /// // we want to extend.
+    /// for sk in c.keys().subkeys() {
+    ///     b = b.insert_subkey_with(sk.key().clone(), None, None,
+    ///         SignatureBuilder::new(SignatureType::SubkeyBinding)
+    ///             // Add a critical notation!
+    ///             .set_notation("code-signing@policy.example.org",
+    ///                           b"Signing Policy Version 2022",
+    ///                           NotationDataFlags::empty(), true)?)?;
+    ///
+    ///     // For signing-capable subkeys, we also need to supply the
+    ///     // signer.
+    ///     if let Ok(signer) = sk.key().clone().parts_into_secret()
+    ///         .and_then(|k| k.into_keypair())
+    ///     {
+    ///         b = b.add_signer(signer);
+    ///     }
+    /// }
+    /// let (c, _) = b.generate()?;
+    /// assert_eq!(c.with_policy(p, now)?.userids().count(), 2);
+    /// assert_eq!(c.with_policy(p, now)?.keys().for_signing().count(), 1);
+    /// assert!(c.keys().subkeys().next().unwrap().with_policy(p, now)?.alive().is_ok());
+    /// assert!(c.keys().subkeys().next().unwrap().with_policy(p, future)?.alive().is_ok());
+    /// # Ok(()) }
+    /// ```
+    pub fn insert_subkey_with<P, F, T, B>(mut self,
+                                          key: Key<P, key::SubordinateRole>,
+                                          flags: F,
+                                          validity: T,
+                                          builder: B) -> Result<Self>
+    where
+        P: key::KeyParts,
+        F: Into<Option<KeyFlags>>,
+        T: Into<Option<time::Duration>>,
+        B: Into<SignatureBuilder>,
+    {
+        // We don't quite know what the "current" time is, so we go
+        // with the latest binding signature instead.
+        let template = self.cert.as_ref()
+            .and_then(
+                |c| c.keys().subkeys().key_handle(key.fingerprint()).next())
+            .and_then(
+                |ka| ka.self_signatures().next());
+
+        // Maybe get flags from the existing signature.
+        let mut flags = flags.into();
+        if flags.is_none() {
+            if let Some(sig) = &template {
+                if let Some(f) = sig.key_flags() {
+                    flags = Some(f);
+                } else {
+                    return Err(Error::InvalidOperation(
+                        "Existing key binding signature has no key flags"
+                            .into()).into());
+                }
+            } else {
+                return Err(Error::InvalidArgument(
+                    "Key flags are mandatory if the key was not bound before"
+                        .into()).into());
+            }
+        }
+        let flags = flags.expect("set above");
+
+        let builder = builder.into();
+        match builder.typ() {
+            SignatureType::SubkeyBinding => {
+                self.subkeys.push((Some(builder), KeyBlueprint {
+                    flags,
+                    validity: validity.into(),
+                    ciphersuite: None,
+                    key: Some(key.parts_into_unspecified()),
                 }));
                 Ok(self)
             },
@@ -1330,31 +1801,84 @@ impl CertBuilder<'_> {
     ///         .generate()?;
     /// # Ok(()) }
     /// ```
-    pub fn generate(self) -> Result<(Cert, Signature)> {
-        use crate::Packet;
+    pub fn generate(mut self) -> Result<(Cert, Signature)> {
         use crate::types::ReasonForRevocation;
-        use std::convert::TryFrom;
+        let null = crate::policy::NullPolicy::new();
 
-        let creation_time =
-            self.creation_time.unwrap_or_else(|| {
+        let mut creation_time =
+            self.creation_time
+            .unwrap_or_else(|| {
                 use crate::packet::signature::SIG_BACKDATE_BY;
                 crate::now() -
                     time::Duration::new(SIG_BACKDATE_BY, 0)
             });
 
-        // Generate & self-sign primary key.
-        let (primary, sig, mut signer) = self.primary_key(creation_time)?;
+        // Make sure we don't create signatures pre-dating the
+        // existing primary key, if any.
+        if let Some(cert) = self.cert.as_ref() {
+            if creation_time < cert.primary_key().creation_time() {
+                creation_time = cert.primary_key().creation_time();
+            }
+        }
 
-        let mut cert = Cert::try_from(vec![
-            Packet::SecretKey({
-                let mut primary = primary.clone();
-                if let Some(ref password) = self.password {
-                    primary.secret_mut().encrypt_in_place(password)?;
+        // If we started from a certificate, and the user didn't
+        // explicitly set a validity period, compute it from the
+        // existing material.
+        if self.primary.validity.is_none() {
+            if let Some(cert) = self.cert.as_ref() {
+                // Compute an expiration time for based on the current
+                // primary key expiration information.
+                let expiration_time =
+                    cert.with_policy(&null, creation_time)
+                    .ok().and_then(
+                        |vcert| vcert.primary_key().key_expiration_time());
+
+                // If that expiration time is not passed, use it as validity
+                // period for new subkeys.
+                if let Some(v) = expiration_time
+                    .and_then(|e| e.duration_since(creation_time).ok())
+                {
+                    self.primary.validity = Some(v);
                 }
-                primary
-            }),
-            sig.into(),
-        ])?;
+            }
+        }
+
+        // From now on, we'll use an absolute expiration time, because
+        // existing keys need different validity periods from newly
+        // generated keys.
+        let expiration_time =
+            self.primary.validity.map(|duration| creation_time + duration);
+
+        // Generate & self-sign primary key.
+        let (mut cert, mut signer) =
+            self.primary_key(creation_time, expiration_time)?;
+
+        // Add any existing User IDs or Attributes to the builder,
+        // with existing binding signatures as templates.  This makes
+        // sure that we re-create all binding signatures which may
+        // carry important metadata for the primary key.
+        for ub in cert.userids() {
+            // Slightly quadratic, but there shouldn't be many.
+            if self.userids.iter().any(|(_, u)| u == ub.userid()) {
+                continue;
+            }
+
+            if let Some(sig) = ub.self_signatures().next() {
+                self.userids.push(
+                    (Some(sig.clone().into()), ub.userid().clone()));
+            }
+        }
+        for ub in cert.user_attributes() {
+            // Slightly quadratic, but there shouldn't be many.
+            if self.user_attributes.iter().any(|(_, u)| u == ub.user_attribute()) {
+                continue;
+            }
+
+            if let Some(sig) = ub.self_signatures().next() {
+                self.user_attributes.push(
+                    (Some(sig.clone().into()), ub.user_attribute().clone()));
+            }
+        }
 
         // We want to mark exactly one User ID or Attribute as primary.
         // First, figure out whether one of the binding signature
@@ -1369,12 +1893,14 @@ impl CertBuilder<'_> {
         };
         let mut emitted_primary_user_thing = false;
 
-        // Sign UserIDs.
-        for (template, uid) in self.userids.into_iter() {
+        // (Re-)Sign UserIDs.
+        for (template, uid) in std::mem::take(&mut self.userids) {
             let sig = template.unwrap_or_else(
                 || SignatureBuilder::new(SignatureType::PositiveCertification));
             let sig = Self::signature_common(sig, creation_time)?;
-            let mut sig = Self::add_primary_key_metadata(sig, &self.primary)?;
+            let mut sig = Self::add_primary_key_metadata(sig, &self.primary,
+                                                         &cert.primary_key(),
+                                                         expiration_time)?;
 
             // Make sure we mark exactly one User ID or Attribute as
             // primary.
@@ -1394,17 +1920,19 @@ impl CertBuilder<'_> {
                 emitted_primary_user_thing = true;
             }
 
-            let signature = uid.bind(&mut signer, &cert, sig)?;
+            let signature = uid.bind(signer.as_mut(), &cert, sig)?;
             cert = cert.insert_packets(
                 vec![Packet::from(uid), signature.into()])?;
         }
 
-        // Sign UserAttributes.
-        for (template, ua) in self.user_attributes.into_iter() {
+        // (Re-)Sign UserAttributes.
+        for (template, ua) in std::mem::take(&mut self.user_attributes) {
             let sig = template.