Merge branch 'feature_15055_v2'

24 files changed, 2443 insertions, 411 deletions

diff --git a/src/common/tortls.c b/src/common/tortls.c
index cf3c8ab548..318dfc8dca 100644
--- a/src/common/tortls.c
+++ b/src/common/tortls.c
@@ -136,6 +136,7 @@ static void tor_tls_context_decref(tor_tls_context_t *ctx);
 static void tor_tls_context_incref(tor_tls_context_t *ctx);
 
 static int check_cert_lifetime_internal(int severity, const X509 *cert,
+                                   time_t now,
                                    int past_tolerance, int future_tolerance);
 
 /** Global TLS contexts. We keep them here because nobody else needs
@@ -522,7 +523,8 @@ MOCK_IMPL(STATIC X509 *,
     goto error;
   if (!X509_set_pubkey(x509, pkey))
     goto error;
-  if (!X509_sign(x509, sign_pkey, EVP_sha1()))
+
+  if (!X509_sign(x509, sign_pkey, EVP_sha256()))
     goto error;
 
   goto done;
@@ -677,6 +679,13 @@ MOCK_IMPL(STATIC tor_x509_cert_t *,
   return cert;
 }
 
+/** Return a copy of <b>cert</b> */
+tor_x509_cert_t *
+tor_x509_cert_dup(const tor_x509_cert_t *cert)
+{
+  return tor_x509_cert_new(X509_dup(cert->cert));
+}
+
 /** Read a DER-encoded X509 cert, of length exactly <b>certificate_len</b>,
  * from a <b>certificate</b>.  Return a newly allocated tor_x509_cert_t on
  * success and NULL on failure. */
@@ -769,8 +778,8 @@ tor_tls_context_decref(tor_tls_context_t *ctx)
 /** Set *<b>link_cert_out</b> and *<b>id_cert_out</b> to the link certificate
  * and ID certificate that we're currently using for our V3 in-protocol
  * handshake's certificate chain.  If <b>server</b> is true, provide the certs
- * that we use in server mode; otherwise, provide the certs that we use in
- * client mode. */
+ * that we use in server mode (auth, ID); otherwise, provide the certs that we
+ * use in client mode. (link, ID) */
 int
 tor_tls_get_my_certs(int server,
                      const tor_x509_cert_t **link_cert_out,
@@ -800,7 +809,7 @@ tor_tls_get_my_client_auth_key(void)
 
 /**
  * Return a newly allocated copy of the public key that a certificate
- * certifies.  Return NULL if the cert's key is not RSA.
+ * certifies. Watch out! This returns NULL if the cert's key is not RSA.
  */
 crypto_pk_t *
 tor_tls_cert_get_key(tor_x509_cert_t *cert)
@@ -855,6 +864,7 @@ int
 tor_tls_cert_is_valid(int severity,
                       const tor_x509_cert_t *cert,
                       const tor_x509_cert_t *signing_cert,
+                      time_t now,
                       int check_rsa_1024)
 {
   check_no_tls_errors();
@@ -874,7 +884,7 @@ tor_tls_cert_is_valid(int severity,
 
   /* okay, the signature checked out right.  Now let's check the check the
    * lifetime. */
-  if (check_cert_lifetime_internal(severity, cert->cert,
+  if (check_cert_lifetime_internal(severity, cert->cert, now,
                                    48*60*60, 30*24*60*60) < 0)
     goto bad;
 
@@ -1019,6 +1029,8 @@ tor_tls_context_init_one(tor_tls_context_t **ppcontext,
 /** The group we should use for ecdhe when none was selected. */
 #define  NID_tor_default_ecdhe_group NID_X9_62_prime256v1
 
+#define RSA_LINK_KEY_BITS 2048
+
 /** Create a new TLS context for use with Tor TLS handshakes.
  * <b>identity</b> should be set to the identity key used to sign the
  * certificate.
@@ -1044,7 +1056,7 @@ tor_tls_context_new(crypto_pk_t *identity, unsigned int key_lifetime,
   /* Generate short-term RSA key for use with TLS. */
   if (!(rsa = crypto_pk_new()))
     goto error;
-  if (crypto_pk_generate_key(rsa)<0)
+  if (crypto_pk_generate_key_with_bits(rsa, RSA_LINK_KEY_BITS)<0)
     goto error;
   if (!is_client) {
     /* Generate short-term RSA key for use in the in-protocol ("v3")
@@ -2023,13 +2035,13 @@ tor_tls_get_peer_cert,(tor_tls_t *tls))
 
 /** Warn that a certificate lifetime extends through a certain range. */
 static void
-log_cert_lifetime(int severity, const X509 *cert, const char *problem)
+log_cert_lifetime(int severity, const X509 *cert, const char *problem,
+                  time_t now)
 {
   BIO *bio = NULL;
   BUF_MEM *buf;
   char *s1=NULL, *s2=NULL;
   char mytime[33];
-  time_t now = time(NULL);
   struct tm tm;
   size_t n;
 
@@ -2177,6 +2189,7 @@ tor_tls_verify(int severity, tor_tls_t *tls, crypto_pk_t **identity_key)
  */
 int
 tor_tls_check_lifetime(int severity, tor_tls_t *tls,
+                       time_t now,
                        int past_tolerance, int future_tolerance)
 {
   X509 *cert;
@@ -2185,7 +2198,7 @@ tor_tls_check_lifetime(int severity, tor_tls_t *tls,
   if (!(cert = SSL_get_peer_certificate(tls->ssl)))
     goto done;
 
-  if (check_cert_lifetime_internal(severity, cert,
+  if (check_cert_lifetime_internal(severity, cert, now,
                                    past_tolerance, future_tolerance) < 0)
     goto done;
 
@@ -2201,24 +2214,24 @@ tor_tls_check_lifetime(int severity, tor_tls_t *tls,
 
 /** Helper: check whether <b>cert</b> is expired give or take
  * <b>past_tolerance</b> seconds, or not-yet-valid give or take
- * <b>future_tolerance</b> seconds.  If it is live, return 0.  If it is not
- * live, log a message and return -1. */
+ * <b>future_tolerance</b> seconds.  (Relative to the current time
+ * <b>now</b>.)  If it is live, return 0.  If it is not live, log a message
+ * and return -1. */
 static int
 check_cert_lifetime_internal(int severity, const X509 *cert,
+                             time_t now,
                              int past_tolerance, int future_tolerance)
 {
-  time_t now, t;
-
-  now = time(NULL);
+  time_t t;
 
   t = now + future_tolerance;
   if (X509_cmp_time(X509_get_notBefore_const(cert), &t) > 0) {
-    log_cert_lifetime(severity, cert, "not yet valid");
+    log_cert_lifetime(severity, cert, "not yet valid", now);
     return -1;
   }
   t = now - past_tolerance;
   if (X509_cmp_time(X509_get_notAfter_const(cert), &t) < 0) {
-    log_cert_lifetime(severity, cert, "already expired");
+    log_cert_lifetime(severity, cert, "already expired", now);
     return -1;
   }
 
@@ -2443,6 +2456,28 @@ tor_tls_get_tlssecrets,(tor_tls_t *tls, uint8_t *secrets_out))
   return 0;
 }
 
+/** Using the RFC5705 key material exporting construction, and the
+ * provided <b>context</b> (<b>context_len</b> bytes long) and
+ * <b>label</b> (a NUL-terminated string), compute a 32-byte secret in
+ * <b>secrets_out</b> that only the parties to this TLS session can
+ * compute.  Return 0 on success and -1 on failure.
+ */
+MOCK_IMPL(int,
+tor_tls_export_key_material,(tor_tls_t *tls, uint8_t *secrets_out,
+                             const uint8_t *context,
+                             size_t context_len,
+                             const char *label))
+{
+  tor_assert(tls);
+  tor_assert(tls->ssl);
+
+  int r = SSL_export_keying_material(tls->ssl,
+                                     secrets_out, DIGEST256_LEN,
+                                     label, strlen(label),
+                                     context, context_len, 1);
+  return (r == 1) ? 0 : -1;
+}
+
 /** Examine the amount of memory used and available for buffers in <b>tls</b>.
  * Set *<b>rbuf_capacity</b> to the amount of storage allocated for the read
  * buffer and *<b>rbuf_bytes</b> to the amount actually used.
diff --git a/src/common/tortls.h b/src/common/tortls.h
index 7c035a2cd5..6510fdbe64 100644
--- a/src/common/tortls.h
+++ b/src/common/tortls.h
@@ -176,6 +176,7 @@ extern uint64_t total_bytes_written_by_tls;
 
 #endif /* endif TORTLS_PRIVATE */
 
+tor_x509_cert_t *tor_x509_cert_dup(const tor_x509_cert_t *cert);
 const char *tor_tls_err_to_string(int err);
 void tor_tls_get_state_description(tor_tls_t *tls, char *buf, size_t sz);
 
@@ -200,7 +201,8 @@ int tor_tls_peer_has_cert(tor_tls_t *tls);
 MOCK_DECL(tor_x509_cert_t *,tor_tls_get_peer_cert,(tor_tls_t *tls));
 int tor_tls_verify(int severity, tor_tls_t *tls, crypto_pk_t **identity);
 int tor_tls_check_lifetime(int severity,
-                           tor_tls_t *tls, int past_tolerance,
+                           tor_tls_t *tls, time_t now,
+                           int past_tolerance,
                            int future_tolerance);
 MOCK_DECL(int, tor_tls_read, (tor_tls_t *tls, char *cp, size_t len));
 int tor_tls_write(tor_tls_t *tls, const char *cp, size_t n);
@@ -226,6 +228,11 @@ int tor_tls_used_v1_handshake(tor_tls_t *tls);
 int tor_tls_get_num_server_handshakes(tor_tls_t *tls);
 int tor_tls_server_got_renegotiate(tor_tls_t *tls);
 MOCK_DECL(int,tor_tls_get_tlssecrets,(tor_tls_t *tls, uint8_t *secrets_out));
+MOCK_DECL(int,tor_tls_export_key_material,(
+                     tor_tls_t *tls, uint8_t *secrets_out,
+                     const uint8_t *context,
+                     size_t context_len,
+                     const char *label));
 
 /* Log and abort if there are unhandled TLS errors in OpenSSL's error stack.
  */
@@ -254,6 +261,7 @@ MOCK_DECL(int,tor_tls_cert_matches_key,(const tor_tls_t *tls,
 int tor_tls_cert_is_valid(int severity,
                           const tor_x509_cert_t *cert,
                           const tor_x509_cert_t *signing_cert,
+                          time_t now,
                           int check_rsa_1024);
 const char *tor_tls_get_ciphersuite_name(tor_tls_t *tls);
 
diff --git a/src/or/channel.c b/src/or/channel.c
index 75aab3cfef..939b7f93e4 100644
--- a/src/or/channel.c
+++ b/src/or/channel.c
@@ -3220,9 +3220,10 @@ channel_free_all(void)
 
 channel_t *
 channel_connect(const tor_addr_t *addr, uint16_t port,
-                const char *id_digest)
+                const char *id_digest,
+                const ed25519_public_key_t *ed_id)
 {
-  return channel_tls_connect(addr, port, id_digest);
+  return channel_tls_connect(addr, port, id_digest, ed_id);
 }
 
 /**
diff --git a/src/or/channel.h b/src/or/channel.h
index 44a3901991..7e7b2ec899 100644
--- a/src/or/channel.h
+++ b/src/or/channel.h
@@ -489,7 +489,8 @@ int channel_send_destroy(circid_t circ_id, channel_t *chan,
  */
 
 channel_t * channel_connect(const tor_addr_t *addr, uint16_t port,
-                            const char *id_digest);
+                            const char *id_digest,
+                            const ed25519_public_key_t *ed_id);
 
 channel_t * channel_get_for_extend(const char *digest,
                                    const tor_addr_t *target_addr,
diff --git a/src/or/channeltls.c b/src/or/channeltls.c
index 09cca95b64..1af75e6648 100644
--- a/src/or/channeltls.c
+++ b/src/or/channeltls.c
@@ -55,6 +55,7 @@
 #include "router.h"
 #include "routerlist.h"
 #include "scheduler.h"
+#include "torcert.h"
 
 /** How many CELL_PADDING cells have we received, ever? */
 uint64_t stats_n_padding_cells_processed = 0;
@@ -170,8 +171,10 @@ channel_tls_common_init(channel_tls_t *tlschan)
 
 channel_t *
 channel_tls_connect(const tor_addr_t *addr, uint16_t port,
-                    const char *id_digest)
+                    const char *id_digest,
+                    const ed25519_public_key_t *ed_id)
 {
+  (void) ed_id; // XXXX not fully used yet
   channel_tls_t *tlschan = tor_malloc_zero(sizeof(*tlschan));
   channel_t *chan = &(tlschan->base_);
 
@@ -198,7 +201,7 @@ channel_tls_connect(const tor_addr_t *addr, uint16_t port,
   channel_mark_outgoing(chan);
 
   /* Set up or_connection stuff */
-  tlschan->conn = connection_or_connect(addr, port, id_digest, tlschan);
+  tlschan->conn = connection_or_connect(addr, port, id_digest, ed_id, tlschan);
   /* connection_or_connect() will fill in tlschan->conn */
   if (!(tlschan->conn)) {
     chan->reason_for_closing = CHANNEL_CLOSE_FOR_ERROR;
@@ -1639,7 +1642,10 @@ channel_tls_process_netinfo_cell(cell_t *cell, channel_tls_t *chan)
       if (!(chan->conn->handshake_state->authenticated)) {
         tor_assert(tor_digest_is_zero(
                   (const char*)(chan->conn->handshake_state->
-                      authenticated_peer_id)));
+                      authenticated_rsa_peer_id)));
+        tor_assert(tor_mem_is_zero(
+                  (const char*)(chan->conn->handshake_state->
+                                authenticated_ed25519_peer_id.pubkey), 32));
         channel_set_circid_type(TLS_CHAN_TO_BASE(chan), NULL,
                chan->conn->link_proto < MIN_LINK_PROTO_FOR_WIDE_CIRC_IDS);
 
@@ -1647,7 +1653,8 @@ channel_tls_process_netinfo_cell(cell_t *cell, channel_tls_t *chan)
                   &(chan->conn->base_.addr),
                   chan->conn->base_.port,
                   (const char*)(chan->conn->handshake_state->
-                   authenticated_peer_id),
+                                authenticated_rsa_peer_id),
+                  NULL, // XXXX Ed key
                   0);
       }
     }
@@ -1744,6 +1751,41 @@ channel_tls_process_netinfo_cell(cell_t *cell, channel_tls_t *chan)
   assert_connection_ok(TO_CONN(chan->conn),time(NULL));
 }
 
+/** Types of certificates that we know how to parse from CERTS cells.  Each
+ * type corresponds to a different encoding format. */
+typedef enum cert_encoding_t {
+  CERT_ENCODING_UNKNOWN, /**< We don't recognize this. */
+  CERT_ENCODING_X509, /**< It's an RSA key, signed with RSA, encoded in x509.
+                   * (Actually, it might not be RSA. We test that later.) */
+  CERT_ENCODING_ED25519, /**< It's something signed with an Ed25519 key,
+                      * encoded asa a tor_cert_t.*/
+  CERT_ENCODING_RSA_CROSSCERT, /**< It's an Ed key signed with an RSA key. */
+} cert_encoding_t;
+
+/**
+ * Given one of the certificate type codes used in a CERTS cell,
+ * return the corresponding cert_encoding_t that we should use to parse
+ * the certificate.
+ */
+static cert_encoding_t
+certs_cell_typenum_to_cert_type(int typenum)
+{
+  switch (typenum) {
+  case CERTTYPE_RSA1024_ID_LINK:
+  case CERTTYPE_RSA1024_ID_ID:
+  case CERTTYPE_RSA1024_ID_AUTH:
+    return CERT_ENCODING_X509;
+  case CERTTYPE_ED_ID_SIGN:
+  case CERTTYPE_ED_SIGN_LINK:
+  case CERTTYPE_ED_SIGN_AUTH:
+    return CERT_ENCODING_ED25519;
+  case CERTTYPE_RSA1024_ID_EDID:
+    return CERT_ENCODING_RSA_CROSSCERT;
+  default:
+    return CERT_ENCODING_UNKNOWN;
+  }
+}
+
 /**
  * Process a CERTS cell from a channel.
  *
@@ -1763,14 +1805,21 @@ channel_tls_process_netinfo_cell(cell_t *cell, channel_tls_t *chan)
 STATIC void
 channel_tls_process_certs_cell(var_cell_t *cell, channel_tls_t *chan)
 {
-#define MAX_CERT_TYPE_WANTED OR_CERT_TYPE_AUTH_1024
-  tor_x509_cert_t *certs[MAX_CERT_TYPE_WANTED + 1];
+#define MAX_CERT_TYPE_WANTED CERTTYPE_RSA1024_ID_EDID
+  /* These arrays will be sparse, since a cert type can be at most one
+   * of ed/x509 */
+  tor_x509_cert_t *x509_certs[MAX_CERT_TYPE_WANTED + 1];
+  tor_cert_t *ed_certs[MAX_CERT_TYPE_WANTED + 1];
+  uint8_t *rsa_ed_cc_cert = NULL;
+  size_t rsa_ed_cc_cert_len = 0;
+
   int n_certs, i;
   certs_cell_t *cc = NULL;
 
   int send_netinfo = 0;
 
-  memset(certs, 0, sizeof(certs));
+  memset(x509_certs, 0, sizeof(x509_certs));
+  memset(ed_certs, 0, sizeof(ed_certs));
   tor_assert(cell);
   tor_assert(chan);
   tor_assert(chan->conn);
@@ -1814,77 +1863,145 @@ channel_tls_process_certs_cell(var_cell_t *cell, channel_tls_t *chan)
 
     if (cert_type > MAX_CERT_TYPE_WANTED)
       continue;
+    const cert_encoding_t ct = certs_cell_typenum_to_cert_type(cert_type);
+    switch (ct) {
+      default:
+      case CERT_ENCODING_UNKNOWN:
+        break;
+      case CERT_ENCODING_X509: {
+        tor_x509_cert_t *x509_cert = tor_x509_cert_decode(cert_body, cert_len);
+        if (!x509_cert) {
+          log_fn(LOG_PROTOCOL_WARN, LD_PROTOCOL,
+                 "Received undecodable certificate in CERTS cell from %s:%d",
+                 safe_str(chan->conn->base_.address),
+               chan->conn->base_.port);
+        } else {
+          if (x509_certs[cert_type]) {
+            tor_x509_cert_free(x509_cert);
+            ERR("Duplicate x509 certificate");
+          } else {
+            x509_certs[cert_type] = x509_cert;
+          }
+        }
+        break;
+      }
+      case CERT_ENCODING_ED25519: {
+        tor_cert_t *ed_cert = tor_cert_parse(cert_body, cert_len);
+        if (!ed_cert) {
+          log_fn(LOG_PROTOCOL_WARN, LD_PROTOCOL,
+                 "Received undecodable Ed certificate in CERTS cell from %s:%d",
+                 safe_str(chan->conn->base_.address),
+               chan->conn->base_.port);
+        } else {
+          if (ed_certs[cert_type]) {
+            tor_cert_free(ed_cert);
+            ERR("Duplicate Ed25519 certificate");
+          } else {
+            ed_certs[cert_type] = ed_cert;
+          }
+        }
+        break;
+      }
 
-    tor_x509_cert_t *cert = tor_x509_cert_decode(cert_body, cert_len);
-    if (!cert) {
-      log_fn(LOG_PROTOCOL_WARN, LD_PROTOCOL,
-             "Received undecodable certificate in CERTS cell from %s:%d",
-             safe_str(chan->conn->base_.address),
-             chan->conn->base_.port);
-    } else {
-      if (certs[cert_type]) {
-        tor_x509_cert_free(cert);
-        ERR("Duplicate x509 certificate");
-      } else {
-        certs[cert_type] = cert;
+     case CERT_ENCODING_RSA_CROSSCERT: {
+        if (rsa_ed_cc_cert) {
+          ERR("Duplicate RSA->Ed25519 crosscert");
+        } else {
+          rsa_ed_cc_cert = tor_memdup(cert_body, cert_len);
+          rsa_ed_cc_cert_len = cert_len;
+        }
+        break;
       }
     }
   }
 
-  tor_x509_cert_t *id_cert = certs[OR_CERT_TYPE_ID_1024];
-  tor_x509_cert_t *auth_cert = certs[OR_CERT_TYPE_AUTH_1024];
-  tor_x509_cert_t *link_cert = certs[OR_CERT_TYPE_TLS_LINK];
+  /* Move the certificates we (might) want into the handshake_state->certs
+   * structure. */
+  tor_x509_cert_t *id_cert = x509_certs[CERTTYPE_RSA1024_ID_ID];
+  tor_x509_cert_t *auth_cert = x509_certs[CERTTYPE_RSA1024_ID_AUTH];
+  tor_x509_cert_t *link_cert = x509_certs[CERTTYPE_RSA1024_ID_LINK];
+  chan->conn->handshake_state->certs->auth_cert = auth_cert;
+  chan->conn->handshake_state->certs->link_cert = link_cert;
+  chan->conn->handshake_state->certs->id_cert = id_cert;
+  x509_certs[CERTTYPE_RSA1024_ID_ID] =
+    x509_certs[CERTTYPE_RSA1024_ID_AUTH] =
+    x509_certs[CERTTYPE_RSA1024_ID_LINK] = NULL;
+
+  tor_cert_t *ed_id_sign = ed_certs[CERTTYPE_ED_ID_SIGN];
+  tor_cert_t *ed_sign_link = ed_certs[CERTTYPE_ED_SIGN_LINK];
+  tor_cert_t *ed_sign_auth = ed_certs[CERTTYPE_ED_SIGN_AUTH];
+  chan->conn->handshake_state->certs->ed_id_sign = ed_id_sign;
+  chan->conn->handshake_state->certs->ed_sign_link = ed_sign_link;
+  chan->conn->handshake_state->certs->ed_sign_auth = ed_sign_auth;
+  ed_certs[CERTTYPE_ED_ID_SIGN] =
+    ed_certs[CERTTYPE_ED_SIGN_LINK] =
+    ed_certs[CERTTYPE_ED_SIGN_AUTH] = NULL;
+
+  chan->conn->handshake_state->certs->ed_rsa_crosscert = rsa_ed_cc_cert;
+  chan->conn->handshake_state->certs->ed_rsa_crosscert_len =
+    rsa_ed_cc_cert_len;
+  rsa_ed_cc_cert = NULL;
+
+  int severity;
+  /* Note that this warns more loudly about time and validity if we were
+   * _trying_ to connect to an authority, not necessarily if we _did_ connect
+   * to one. */
+  if (chan->conn->handshake_state->started_here &&
+      router_digest_is_trusted_dir(TLS_CHAN_TO_BASE(chan)->identity_digest))
+    severity = LOG_WARN;
+  else
+    severity = LOG_PROTOCOL_WARN;
+
+  const ed25519_public_key_t *checked_ed_id = NULL;
+  const common_digests_t *checked_rsa_id = NULL;
+  or_handshake_certs_check_both(severity,
+                                chan->conn->handshake_state->certs,
+                                chan->conn->tls,
+                                time(NULL),
+                                &checked_ed_id,
+                                &checked_rsa_id);
+
+  if (!checked_rsa_id)
+    ERR("Invalid certificate chain!");
 
   if (chan->conn->handshake_state->started_here) {
-    int severity;
-    if (! (id_cert && link_cert))
-      ERR("The certs we wanted were missing");
-    /* Okay. We should be able to check the certificates now. */
-    if (! tor_tls_cert_matches_key(chan->conn->tls, link_cert)) {
-      ERR("The link certificate didn't match the TLS public key");
-    }
-    /* Note that this warns more loudly about time and validity if we were
-    * _trying_ to connect to an authority, not necessarily if we _did_ connect
-    * to one. */
-    if (router_digest_is_trusted_dir(
-          TLS_CHAN_TO_BASE(chan)->identity_digest))
-      severity = LOG_WARN;
-    else
-      severity = LOG_PROTOCOL_WARN;
-
-    if (! tor_tls_cert_is_valid(severity, link_cert, id_cert, 0))
-      ERR("The link certificate was not valid");
-    if (! tor_tls_cert_is_valid(severity, id_cert, id_cert, 1))
-      ERR("The ID certificate was not valid");
+    /* No more information is needed. */
 
     chan->conn->handshake_state->authenticated = 1;
+    chan->conn->handshake_state->authenticated_rsa = 1;
     {
-      const common_digests_t *id_digests =
-        tor_x509_cert_get_id_digests(id_cert);
+      const common_digests_t *id_digests = checked_rsa_id;
       crypto_pk_t *identity_rcvd;
       if (!id_digests)
         ERR("Couldn't compute digests for key in ID cert");
 
       identity_rcvd = tor_tls_cert_get_key(id_cert);
-      if (!identity_rcvd)
-        ERR("Internal error: Couldn't get RSA key from ID cert.");
-      memcpy(chan->conn->handshake_state->authenticated_peer_id,
+      if (!identity_rcvd) {
+        ERR("Couldn't get RSA key from ID cert.");
+      }
+      memcpy(chan->conn->handshake_state->authenticated_rsa_peer_id,
              id_digests->d[DIGEST_SHA1], DIGEST_LEN);
       channel_set_circid_type(TLS_CHAN_TO_BASE(chan), identity_rcvd,
                 chan->conn->link_proto < MIN_LINK_PROTO_FOR_WIDE_CIRC_IDS);
       crypto_pk_free(identity_rcvd);
     }
 
+    if (checked_ed_id) {
+      chan->conn->handshake_state->authenticated_ed25519 = 1;
+      memcpy(&chan->conn->handshake_state->authenticated_ed25519_peer_id,
+             checked_ed_id, sizeof(ed25519_public_key_t));
+    }
+
     if (connection_or_client_learned_peer_id(chan->conn,
-            chan->conn->handshake_state->authenticated_peer_id) < 0)
+                  chan->conn->handshake_state->authenticated_rsa_peer_id,
+                  checked_ed_id) < 0)
       ERR("Problem setting or checking peer id");
 
     log_info(LD_OR,
-             "Got some good certificates from %s:%d: Authenticated it.",
-             safe_str(chan->conn->base_.address), chan->conn->base_.port);
-
-    chan->conn->handshake_state->id_cert = id_cert;
-    certs[OR_CERT_TYPE_ID_1024] = NULL;
+             "Got some good certificates from %s:%d: Authenticated it with "
+             "RSA%s",
+             safe_str(chan->conn->base_.address), chan->conn->base_.port,
+             checked_ed_id ? " and Ed25519" : "");
 
     if (!public_server_mode(get_options())) {
       /* If we initiated the connection and we are not a public server, we
@@ -1893,25 +2010,14 @@ channel_tls_process_certs_cell(var_cell_t *cell, channel_tls_t *chan)
       send_netinfo = 1;
     }
   } else {
-    if (! (id_cert && auth_cert))
-      ERR("The certs we wanted were missing");
-
-    /* Remember these certificates so we can check an AUTHENTICATE cell */
-    if (! tor_tls_cert_is_valid(LOG_PROTOCOL_WARN, auth_cert, id_cert, 1))
-      ERR("The authentication certificate was not valid");
-    if (! tor_tls_cert_is_valid(LOG_PROTOCOL_WARN, id_cert, id_cert, 1))
-      ERR("The ID certificate was not valid");
-
+    /* We can't call it authenticated till we see an AUTHENTICATE cell. */
     log_info(LD_OR,
-             "Got some good certificates from %s:%d: "
+             "Got some good RSA%s certificates from %s:%d. "
              "Waiting for AUTHENTICATE.",
+             checked_ed_id ? " and Ed25519" : "",
              safe_str(chan->conn->base_.address),
              chan->conn->base_.port);
     /* XXXX check more stuff? */
-
-    chan->conn->handshake_state->id_cert = id_cert;
-    chan->conn->handshake_state->auth_cert = auth_cert;
-    certs[OR_CERT_TYPE_ID_1024] = certs[OR_CERT_TYPE_AUTH_1024] = NULL;
   }
 
   chan->conn->handshake_state->received_certs_cell = 1;
@@ -1925,9 +2031,13 @@ channel_tls_process_certs_cell(var_cell_t *cell, channel_tls_t *chan)
   }
 
  err:
-  for (unsigned u = 0; u < ARRAY_LENGTH(certs); ++u) {
-    tor_x509_cert_free(certs[u]);
+  for (unsigned u = 0; u < ARRAY_LENGTH(x509_certs); ++u) {
+    tor_x509_cert_free(x509_certs[u]);
   }
+  for (unsigned u = 0; u < ARRAY_LENGTH(ed_certs); ++u) {
+    tor_cert_free(ed_certs[u]);
+  }
+  tor_free(rsa_ed_cc_cert);
   certs_cell_free(cc);
 #undef ERR
 }
@@ -1984,8 +2094,12 @@ channel_tls_process_auth_challenge_cell(var_cell_t *cell, channel_tls_t *chan)
   /* Now see if there is an authentication type we can use */
   for (i = 0; i < n_types; ++i) {
     uint16_t authtype = auth_challenge_cell_get_methods(ac, i);
-    if (authtype == AUTHTYPE_RSA_SHA256_TLSSECRET)
-      use_type = authtype;
+    if (authchallenge_type_is_supported(authtype)) {
+      if (use_type == -1 ||
+          authchallenge_type_is_better(authtype, use_type)) {
+        use_type = authtype;
+      }
+    }
   }
 
   chan->conn->handshake_state->received_auth_challenge = 1;
@@ -2000,9 +2114,10 @@ channel_tls_process_auth_challenge_cell(var_cell_t *cell, channel_tls_t *chan)
   if (use_type >= 0) {
     log_info(LD_OR,
              "Got an AUTH_CHALLENGE cell from %s:%d: Sending "
-             "authentication",
+             "authentication type %d",
              safe_str(chan->conn->base_.address),
-             chan->conn->base_.port);
+             chan->conn->base_.port,
+             use_type);
 
     if (connection_or_send_authenticate_cell(chan->conn, use_type) < 0) {
       log_warn(LD_OR,
@@ -2043,9 +2158,11 @@ channel_tls_process_auth_challenge_cell(var_cell_t *cell, channel_tls_t *chan)
 STATIC void
 channel_tls_process_authenticate_cell(var_cell_t *cell, channel_tls_t *chan)
 {
-  uint8_t expected[V3_AUTH_FIXED_PART_LEN+256];
+  var_cell_t *expected_cell = NULL;
   const uint8_t *auth;
   int authlen;
+  int authtype;
+  int bodylen;
 
   tor_assert(cell);
   tor_assert(chan);
@@ -2058,6 +2175,7 @@ channel_tls_process_authenticate_cell(var_cell_t *cell, channel_tls_t *chan)
            safe_str(chan->conn->base_.address),                 \
            chan->conn->base_.port, (s));                        \
     connection_or_close_for_error(chan->conn, 0);               \
+    var_cell_free(expected_cell);                               \
     return;                                                     \
   } while (0)
 
@@ -2075,9 +2193,7 @@ channel_tls_process_authenticate_cell(var_cell_t *cell, channel_tls_t *chan)
   }
   if (!(chan->conn->handshake_state->received_certs_cell))
     ERR("We never got a certs cell");
-  if (chan->conn->handshake_state->auth_cert == NULL)
-    ERR("We never got an authentication certificate");
-  if (chan->conn->handshake_state->id_cert == NULL)
+  if (chan->conn->handshake_state->certs->id_cert == NULL)
     ERR("We never got an identity certificate");
   if (cell->payload_len < 4)
     ERR("Cell was way too short");
@@ -2089,8 +2205,9 @@ channel_tls_process_authenticate_cell(var_cell_t *cell, channel_tls_t *chan)
     if (4 + len > cell->payload_len)
       ERR("Authenticator was truncated");
 
-    if (type != AUTHTYPE_RSA_SHA256_TLSSECRET)
+    if (! authchallenge_type_is_supported(type))
       ERR("Authenticator type was not recognized");
+    authtype = type;
 
     auth += 4;
     authlen = len;
@@ -2099,25 +2216,55 @@ channel_tls_process_authenticate_cell(var_cell_t *cell, channel_tls_t *chan)
   if (authlen < V3_AUTH_BODY_LEN + 1)
     ERR("Authenticator was too short");
 
-  ssize_t bodylen =
-    connection_or_compute_authenticate_cell_body(
-                        chan->conn, expected, sizeof(expected), NULL, 1);
-  if (bodylen < 0 || bodylen != V3_AUTH_FIXED_PART_LEN)
+  expected_cell = connection_or_compute_authenticate_cell_body(
+                chan->conn, authtype, NULL, NULL, 1);
+  if (! expected_cell)
     ERR("Couldn't compute expected AUTHENTICATE cell body");
 
-  if (tor_memneq(expected, auth, bodylen))
+  int sig_is_rsa;
+  if (authtype == AUTHTYPE_RSA_SHA256_TLSSECRET ||
+      authtype == AUTHTYPE_RSA_SHA256_RFC5705) {
+    bodylen = V3_AUTH_BODY_LEN;
+    sig_is_rsa = 1;
+  } else {
+    tor_assert(authtype == AUTHTYPE_ED25519_SHA256_RFC5705);
+    /* Our earlier check had better have made sure we had room
+     * for an ed25519 sig (inadvertently) */
+    tor_assert(V3_AUTH_BODY_LEN > ED25519_SIG_LEN);
+    bodylen = authlen - ED25519_SIG_LEN;
+    sig_is_rsa = 0;
+  }
+  if (expected_cell->payload_len != bodylen+4) {
+    ERR("Expected AUTHENTICATE cell body len not as expected.");
+  }
+
+  /* Length of random part. */
+  if (BUG(bodylen < 24)) {
+    // LCOV_EXCL_START
+    ERR("Bodylen is somehow less than 24, which should really be impossible");
+    // LCOV_EXCL_STOP
+  }
+
+  if (tor_memneq(expected_cell->payload+4, auth, bodylen-24))
     ERR("Some field in the AUTHENTICATE cell body was not as expected");
 
-  {
+  if (sig_is_rsa) {
+    if (chan->conn->handshake_state->certs->ed_id_sign != NULL)
+      ERR("RSA-signed AUTHENTICATE response provided with an ED25519 cert");
+
+    if (chan->conn->handshake_state->certs->auth_cert == NULL)
+      ERR("We never got an RSA authentication certificate");
+
     crypto_pk_t *pk = tor_tls_cert_get_key(
-                                   chan->conn->handshake_state->auth_cert);
+                             chan->conn->handshake_state->certs->auth_cert);
     char d[DIGEST256_LEN];
     char *signed_data;
     size_t keysize;
     int signed_len;
 
-    if (!pk)
-      ERR("Internal error: couldn't get RSA key from AUTH cert.");
+    if (! pk) {
+      ERR("Couldn't get RSA key from AUTH cert.");
+    }
     crypto_digest256(d, (char*)auth, V3_AUTH_BODY_LEN, DIGEST_SHA256);
 
     keysize = crypto_pk_keysize(pk);
@@ -2128,7 +2275,7 @@ channel_tls_process_authenticate_cell(var_cell_t *cell, channel_tls_t *chan)
     crypto_pk_free(pk);
     if (signed_len < 0) {
       tor_free(signed_data);
-      ERR("Signature wasn't valid");
+      ERR("RSA signature wasn't valid");
     }
     if (signed_len < DIGEST256_LEN) {
       tor_free(signed_data);
@@ -2141,22 +2288,46 @@ channel_tls_process_authenticate_cell(var_cell_t *cell, channel_tls_t *chan)
       ERR("Signature did not match data to be signed.");
     }
     tor_free(signed_data);
+  } else {
+    if (chan->conn->handshake_state->certs->ed_id_sign == NULL)
+      ERR("We never got an Ed25519 identity certificate.");
+    if (chan->conn->handshake_state->certs->ed_sign_auth == NULL)
+      ERR("We never got an Ed25519 authentication certificate.");
+
+    const ed25519_public_key_t *authkey =
+      &chan->conn->handshake_state->certs->ed_sign_auth->signed_key;
+    ed25519_signature_t sig;
+    tor_assert(authlen > ED25519_SIG_LEN);
+    memcpy(&sig.sig, auth + authlen - ED25519_SIG_LEN, ED25519_SIG_LEN);
+    if (ed25519_checksig(&sig, auth, authlen - ED25519_SIG_LEN, authkey)<0) {
+      ERR("Ed25519 signature wasn't valid.");
+    }
   }
 
   /* Okay, we are authenticated. */
   chan->conn->handshake_state->received_authenticate = 1;
   chan->conn->handshake_state->authenticated = 1;
+  chan->conn->handshake_state->authenticated_rsa = 1;
   chan->conn->handshake_state->digest_received_data = 0;
   {
     crypto_pk_t *identity_rcvd =
-      tor_tls_cert_get_key(chan->conn->handshake_state->id_cert);
+      tor_tls_cert_get_key(chan->conn->handshake_state->certs->id_cert);
     const common_digests_t *id_digests =
-      tor_x509_cert_get_id_digests(chan->conn->handshake_state->id_cert);
+      tor_x509_cert_get_id_digests(chan->conn->handshake_state->certs->id_cert);
+    const ed25519_public_key_t *ed_identity_received = NULL;
+
+    if (! sig_is_rsa) {
+      chan->conn->handshake_state->authenticated_ed25519 = 1;
+      ed_identity_received =
+        &chan->conn->handshake_state->certs->ed_id_sign->signing_key;
+      memcpy(&chan->conn->handshake_state->authenticated_ed25519_peer_id,
+             ed_identity_received, sizeof(ed25519_public_key_t));
+    }
 
     /* This must exist; we checked key type when reading the cert. */
     tor_assert(id_digests);
 
-    memcpy(chan->conn->handshake_state->authenticated_peer_id,
+    memcpy(chan->conn->handshake_state->authenticated_rsa_peer_id,
            id_digests->d[DIGEST_SHA1], DIGEST_LEN);
 
     channel_set_circid_type(TLS_CHAN_TO_BASE(chan), identity_rcvd,
@@ -2167,15 +2338,19 @@ channel_tls_process_authenticate_cell(var_cell_t *cell, channel_tls_t *chan)
                   &(chan->conn->base_.addr),
                   chan->conn->base_.port,
                   (const char*)(chan->conn->handshake_state->
-                    authenticated_peer_id),
+                    authenticated_rsa_peer_id),
+                  ed_identity_received,
                   0);
 
     log_info(LD_OR,
-             "Got an AUTHENTICATE cell from %s:%d: Looks good.",
+             "Got an AUTHENTICATE cell from %s:%d, type %d: Looks good.",
              safe_str(chan->conn->base_.address),
-             chan->conn->base_.port);
+             chan->conn->base_.port,
+             authtype);
   }
 
+  var_cell_free(expected_cell);
+
 #undef ERR
 }
 
diff --git a/src/or/channeltls.h b/src/or/channeltls.h
index 8b5863a461..729e595615 100644
--- a/src/or/channeltls.h
+++ b/src/or/channeltls.h
@@ -29,7 +29,8 @@ struct channel_tls_s {
 #endif /* TOR_CHANNEL_INTERNAL_ */
 
 channel_t * channel_tls_connect(const tor_addr_t *addr, uint16_t port,
-                                const char *id_digest);
+                                const char *id_digest,
+                                const ed25519_public_key_t *ed_id);
 channel_listener_t * channel_tls_get_listener(void);
 channel_listener_t * channel_tls_start_listener(void);
 channel_t * channel_tls_handle_incoming(or_connection_t *orconn);
diff --git a/src/or/circuitbuild.c b/src/or/circuitbuild.c
index 50468b7158..b2fbd273a8 100644
--- a/src/or/circuitbuild.c
+++ b/src/or/circuitbuild.c
@@ -84,7 +84,10 @@ channel_connect_for_circuit(const tor_addr_t *addr, uint16_t port,
 {
   channel_t *chan;
 
-  chan = channel_connect(addr, port, id_digest);
+
+  chan = channel_connect(addr, port, id_digest,
+                         NULL // XXXX Ed25519 id.
+                         );
   if (chan) command_setup_channel(chan);
 
   return chan;
diff --git a/src/or/connection_or.c b/src/or/connection_or.c
index 267c32dda4..c6d5bb5250 100644
--- a/src/or/connection_or.c
+++ b/src/or/connection_or.c
@@ -49,9 +49,11 @@
 #include "relay.h"
 #include "rephist.h"
 #include "router.h"
+#include "routerkeys.h"
 #include "routerlist.h"
 #include "ext_orport.h"
 #include "scheduler.h"
+#include "torcert.h"
 
 static int connection_tls_finish_handshake(or_connection_t *conn);
 static int connection_or_launch_v3_or_handshake(or_connection_t *conn);
@@ -143,15 +145,18 @@ connection_or_clear_identity_map(void)
 /** Change conn->identity_digest to digest, and add conn into
  * orconn_digest_map. */
 static void
-connection_or_set_identity_digest(or_connection_t *conn, const char *digest)
+connection_or_set_identity_digest(or_connection_t *conn,
+                                  const char *rsa_digest,
+                                  const ed25519_public_key_t *ed_id)
 {
+  (void) ed_id; // DOCDOC // XXXX not implemented yet.
   or_connection_t *tmp;
   tor_assert(conn);
-  tor_assert(digest);
+  tor_assert(rsa_digest);
 
   if (!orconn_identity_map)
     orconn_identity_map = digestmap_new();
-  if (tor_memeq(conn->identity_digest, digest, DIGEST_LEN))
+  if (tor_memeq(conn->identity_digest, rsa_digest, DIGEST_LEN))
     return;
 
   /* If the identity was set previously, remove the old mapping. */
@@ -161,23 +166,23 @@ connection_or_set_identity_digest(or_connection_t *conn, const char *digest)
       channel_clear_identity_digest(TLS_CHAN_TO_BASE(conn->chan));
   }
 
-  memcpy(conn->identity_digest, digest, DIGEST_LEN);
+  memcpy(conn->identity_digest, rsa_digest, DIGEST_LEN);
 
   /* If we're setting the ID to zero, don't add a mapping. */
-  if (tor_digest_is_zero(digest))
+  if (tor_digest_is_zero(rsa_digest))
     return;
 
-  tmp = digestmap_set(orconn_identity_map, digest, conn);
+  tmp = digestmap_set(orconn_identity_map, rsa_digest, conn);
   conn->next_with_same_id = tmp;
 
   /* Deal with channels */
   if (conn->chan)
-    channel_set_identity_digest(TLS_CHAN_TO_BASE(conn->chan), digest);
+    channel_set_identity_digest(TLS_CHAN_TO_BASE(conn->chan), rsa_digest);
 
 #if 1
   /* Testing code to check for bugs in representation. */
   for (; tmp; tmp = tmp->next_with_same_id) {
-    tor_assert(tor_memeq(tmp->identity_digest, digest, DIGEST_LEN));
+    tor_assert(tor_memeq(tmp->identity_digest, rsa_digest, DIGEST_LEN));
     tor_assert(tmp != conn);
   }
 #endif
@@ -875,10 +880,12 @@ void
 connection_or_init_conn_from_address(or_connection_t *conn,
                                      const tor_addr_t *addr, uint16_t port,
                                      const char *id_digest,
+                                     const ed25519_public_key_t *ed_id,
                                      int started_here)
 {
+  (void) ed_id; // not fully used yet.
   const node_t *r = node_get_by_id(id_digest);
-  connection_or_set_identity_digest(conn, id_digest);
+  connection_or_set_identity_digest(conn, id_digest, ed_id);
   connection_or_update_token_buckets_helper(conn, 1, get_options());
 
   conn->base_.port = port;
@@ -1171,8 +1178,11 @@ connection_or_notify_error(or_connection_t *conn,
 
 MOCK_IMPL(or_connection_t *,
 connection_or_connect, (const tor_addr_t *_addr, uint16_t port,
-                        const char *id_digest, channel_tls_t *chan))
+                        const char *id_digest,
+                        const ed25519_public_key_t *ed_id,
+                        channel_tls_t *chan))
 {
+  (void) ed_id; // XXXX not fully used yet.
   or_connection_t *conn;
   const or_options_t *options = get_options();
   int socket_error = 0;
@@ -1203,7 +1213,7 @@ connection_or_connect, (const tor_addr_t *_addr, uint16_t port,
    */
   conn->chan = chan;
   chan->conn = conn;
-  connection_or_init_conn_from_address(conn, &addr, port, id_digest, 1);
+  connection_or_init_conn_from_address(conn, &addr, port, id_digest, ed_id, 1);
   connection_or_change_state(conn, OR_CONN_STATE_CONNECTING);
   control_event_or_conn_status(conn, OR_CONN_EVENT_LAUNCHED, 0);
 
@@ -1562,7 +1572,9 @@ connection_or_check_valid_tls_handshake(or_connection_t *conn,
 
   if (started_here)
     return connection_or_client_learned_peer_id(conn,
-                                     (const uint8_t*)digest_rcvd_out);
+                                        (const uint8_t*)digest_rcvd_out,
+                                        NULL // Ed25519 ID
+                                        );
 
   return 0;
 }
@@ -1592,12 +1604,16 @@ connection_or_check_valid_tls_handshake(or_connection_t *conn,
  */
 int
 connection_or_client_learned_peer_id(or_connection_t *conn,
-                                     const uint8_t *peer_id)
+                                     const uint8_t *rsa_peer_id,
+                                     const ed25519_public_key_t *ed_peer_id)
 {
+  (void) ed_peer_id; // not used yet.
+
   const or_options_t *options = get_options();
 
   if (tor_digest_is_zero(conn->identity_digest)) {
-    connection_or_set_identity_digest(conn, (const char*)peer_id);
+    connection_or_set_identity_digest(conn,
+                                      (const char*)rsa_peer_id, ed_peer_id);
     tor_free(conn->nickname);
     conn->nickname = tor_malloc(HEX_DIGEST_LEN+2);
     conn->nickname[0] = '$';
@@ -1609,14 +1625,14 @@ connection_or_client_learned_peer_id(or_connection_t *conn,
     /* if it's a bridge and we didn't know its identity fingerprint, now
      * we do -- remember it for future attempts. */
     learned_router_identity(&conn->base_.addr, conn->base_.port,
-                            (const char*)peer_id);
+                            (const char*)rsa_peer_id /*, ed_peer_id XXXX */);
   }
 
-  if (tor_memneq(peer_id, conn->identity_digest, DIGEST_LEN)) {
+  if (tor_memneq(rsa_peer_id, conn->identity_digest, DIGEST_LEN)) {
     /* I was aiming for a particular digest. I didn't get it! */
     char seen[HEX_DIGEST_LEN+1];
     char expected[HEX_DIGEST_LEN+1];
-    base16_encode(seen, sizeof(seen), (const char*)peer_id, DIGEST_LEN);
+    base16_encode(seen, sizeof(seen), (const char*)rsa_peer_id, DIGEST_LEN);
     base16_encode(expected, sizeof(expected), conn->identity_digest,
                   DIGEST_LEN);
     const int using_hardcoded_fingerprints =
@@ -1669,7 +1685,7 @@ connection_or_client_learned_peer_id(or_connection_t *conn,
   }
   if (authdir_mode_tests_reachability(options)) {
     dirserv_orconn_tls_done(&conn->base_.addr, conn->base_.port,
-                            (const char*)peer_id);
+                            (const char*)rsa_peer_id /*, ed_id XXXX */);
   }
 
   return 0;
@@ -1725,7 +1741,8 @@ connection_tls_finish_handshake(or_connection_t *conn)
   if (tor_tls_used_v1_handshake(conn->tls)) {
     conn->link_proto = 1;
     connection_or_init_conn_from_address(conn, &conn->base_.addr,
-                                         conn->base_.port, digest_rcvd, 0);
+                                         conn->base_.port, digest_rcvd,
+                                         NULL, 0);
     tor_tls_block_renegotiation(conn->tls);
     rep_hist_note_negotiated_link_proto(1, started_here);
     return connection_or_set_state_open(conn);
@@ -1734,7 +1751,8 @@ connection_tls_finish_handshake(or_connection_t *conn)
     if (connection_init_or_handshake_state(conn, started_here) < 0)
       return -1;
     connection_or_init_conn_from_address(conn, &conn->base_.addr,
-                                         conn->base_.port, digest_rcvd, 0);
+                                         conn->base_.port, digest_rcvd,
+                                         NULL, 0);
     return connection_or_send_versions(conn, 0);
   }
 }
@@ -1773,6 +1791,8 @@ connection_init_or_handshake_state(or_connection_t *conn, int started_here)
   s->started_here = started_here ? 1 : 0;
   s->digest_sent_data = 1;
   s->digest_received_data = 1;
+  s->certs = or_handshake_certs_new();
+  s->certs->started_here = s->started_here;
   return 0;
 }
 
@@ -1784,8 +1804,7 @@ or_handshake_state_free(or_handshake_state_t *state)
     return;
   crypto_digest_free(state->digest_sent);
   crypto_digest_free(state->digest_received);
-  tor_x509_cert_free(state->auth_cert);
-  tor_x509_cert_free(state->id_cert);
+  or_handshake_certs_free(state->certs);
   memwipe(state, 0xBE, sizeof(or_handshake_state_t));
   tor_free(state);
 }
@@ -2132,57 +2151,171 @@ connection_or_send_netinfo,(or_connection_t *conn))
   return 0;
 }
 
+/** Helper used to add an encoded certs to a cert cell */
+static void
+add_certs_cell_cert_helper(certs_cell_t *certs_cell,
+                           uint8_t cert_type,
+                           const uint8_t *cert_encoded,
+                           size_t cert_len)
+{
+  tor_assert(cert_len <= UINT16_MAX);
+  certs_cell_cert_t *ccc = certs_cell_cert_new();
+  ccc->cert_type = cert_type;
+  ccc->cert_len = cert_len;
+  certs_cell_cert_setlen_body(ccc, cert_len);
+  memcpy(certs_cell_cert_getarray_body(ccc), cert_encoded, cert_len);
+
+  certs_cell_add_certs(certs_cell, ccc);
+}
+
+/** Add an encoded X509 cert (stored as <b>cert_len</b> bytes at
+ * <b>cert_encoded</b>) to the trunnel certs_cell_t object that we are
+ * building in <b>certs_cell</b>.  Set its type field to <b>cert_type</b>. */
+static void
+add_x509_cert(certs_cell_t *certs_cell,
+              uint8_t cert_type,
+              const tor_x509_cert_t *cert)
+{
+  if (NULL == cert)
+    return;
+
+  const uint8_t *cert_encoded = NULL;
+  size_t cert_len;
+  tor_x509_cert_get_der(cert, &cert_encoded, &cert_len);
+
+  add_certs_cell_cert_helper(certs_cell, cert_type, cert_encoded, cert_len);
+}
+
+/** Add an Ed25519 cert from <b>cert</b> to the trunnel certs_cell_t object
+ * that we are building in <b>certs_cell</b>.  Set its type field to
+ * <b>cert_type</b>. */
+static void
+add_ed25519_cert(certs_cell_t *certs_cell,
+                 uint8_t cert_type,
+                 const tor_cert_t *cert)
+{
+  if (NULL == cert)
+    return;
+
+  add_certs_cell_cert_helper(certs_cell, cert_type,
+                             cert->encoded, cert->encoded_len);
+}
+
 /** Send a CERTS cell on the connection <b>conn</b>.  Return 0 on success, -1
  * on failure. */
 int
 connection_or_send_certs_cell(or_connection_t *conn)
 {
   const tor_x509_cert_t *link_cert = NULL, *id_cert = NULL;
-  const uint8_t *link_encoded = NULL, *id_encoded = NULL;
-  size_t link_len, id_len;
   var_cell_t *cell;
-  size_t cell_len;
-  ssize_t pos;
+
+  certs_cell_t *certs_cell = NULL;
 
   tor_assert(conn->base_.state == OR_CONN_STATE_OR_HANDSHAKING_V3);
 
   if (! conn->handshake_state)
     return -1;
+
   const int conn_in_server_mode = ! conn->handshake_state->started_here;
+
+  /* Get the encoded values of the X509 certificates */
   if (tor_tls_get_my_certs(conn_in_server_mode, &link_cert, &id_cert) < 0)
     return -1;
-  tor_x509_cert_get_der(link_cert, &link_encoded, &link_len);
-  tor_x509_cert_get_der(id_cert, &id_encoded, &id_len);
 
-  cell_len = 1 /* 1 byte: num certs in cell */ +
-             2 * ( 1 + 2 ) /* For each cert: 1 byte for type, 2 for length */ +
-             link_len + id_len;
-  cell = var_cell_new(cell_len);
-  cell->command = CELL_CERTS;
-  cell->payload[0] = 2;
-  pos = 1;
+  tor_assert(link_cert);
+  tor_assert(id_cert);
 
-  if (conn_in_server_mode)
-    cell->payload[pos] = OR_CERT_TYPE_TLS_LINK; /* Link cert  */
-  else
-    cell->payload[pos] = OR_CERT_TYPE_AUTH_1024; /* client authentication */
-  set_uint16(&cell->payload[pos+1], htons(link_len));
-  memcpy(&cell->payload[pos+3], link_encoded, link_len);
-  pos += 3 + link_len;
+  certs_cell = certs_cell_new();
 
-  cell->payload[pos] = OR_CERT_TYPE_ID_1024; /* ID cert */
-  set_uint16(&cell->payload[pos+1], htons(id_len));
-  memcpy(&cell->payload[pos+3], id_encoded, id_len);
-  pos += 3 + id_len;
+  /* Start adding certs.  First the link cert or auth1024 cert. */
+  if (conn_in_server_mode) {
+    add_x509_cert(certs_cell,
+                  OR_CERT_TYPE_TLS_LINK, link_cert);
+  } else {
+    add_x509_cert(certs_cell,
+                  OR_CERT_TYPE_AUTH_1024, link_cert);
+  }
 
-  tor_assert(pos == (int)cell_len); /* Otherwise we just smashed the heap */
+  /* Next the RSA->RSA ID cert */
+  add_x509_cert(certs_cell,
+                OR_CERT_TYPE_ID_1024, id_cert);
+
+  /* Next the Ed25519 certs */
+  add_ed25519_cert(certs_cell,
+                   CERTTYPE_ED_ID_SIGN,
+                   get_master_signing_key_cert());
+  if (conn_in_server_mode) {
+    add_ed25519_cert(certs_cell,
+                     CERTTYPE_ED_SIGN_LINK,
+                     get_current_link_cert_cert());
+  } else {
+    add_ed25519_cert(certs_cell,
+                     CERTTYPE_ED_SIGN_AUTH,
+                     get_current_auth_key_cert());
+  }
+
+  /* And finally the crosscert. */
+  {
+    const uint8_t *crosscert=NULL;
+    size_t crosscert_len;
+    get_master_rsa_crosscert(&crosscert, &crosscert_len);
+    if (crosscert) {
+      add_certs_cell_cert_helper(certs_cell,
+                               CERTTYPE_RSA1024_ID_EDID,
+                               crosscert, crosscert_len);
+    }
+  }
+
+  /* We've added all the certs; make the cell. */
+  certs_cell->n_certs = certs_cell_getlen_certs(certs_cell);
+
+  ssize_t alloc_len = certs_cell_encoded_len(certs_cell);
+  tor_assert(alloc_len >= 0 && alloc_len <= UINT16_MAX);
+  cell = var_cell_new(alloc_len);
+  cell->command = CELL_CERTS;
+  ssize_t enc_len = certs_cell_encode(cell->payload, alloc_len, certs_cell);
+  tor_assert(enc_len > 0 && enc_len <= alloc_len);
+  cell->payload_len = enc_len;
 
   connection_or_write_var_cell_to_buf(cell, conn);
   var_cell_free(cell);
+  certs_cell_free(certs_cell);
 
   return 0;
 }
 
+/** Return true iff <b>challenge_type</b> is an AUTHCHALLENGE type that
+ * we can send and receive. */
+int
+authchallenge_type_is_supported(uint16_t challenge_type)
+{
+  switch (challenge_type) {
+     case AUTHTYPE_RSA_SHA256_TLSSECRET:
+     case AUTHTYPE_ED25519_SHA256_RFC5705:
+       return 1;
+     case AUTHTYPE_RSA_SHA256_RFC5705:
+     default:
+       return 0;
+  }
+}
+
+/** Return true iff <b>challenge_type_a</b> is one that we would rather
+ * use than <b>challenge_type_b</b>. */
+int
+authchallenge_type_is_better(uint16_t challenge_type_a,
+                             uint16_t challenge_type_b)
+{
+  /* Any supported type is better than an unsupported one;
+   * all unsupported types are equally bad. */
+  if (!authchallenge_type_is_supported(challenge_type_a))
+    return 0;
+  if (!authchallenge_type_is_supported(challenge_type_b))
+    return 1;
+  /* It happens that types are superior in numerically ascending order.
+   * If that ever changes, this must change too. */
+  return (challenge_type_a > challenge_type_b);
+}
+
 /** Send an AUTH_CHALLENGE cell on the connection <b>conn</b>. Return 0
  * on success, -1 on failure. */
 int
@@ -2197,17 +2330,26 @@ connection_or_send_auth_challenge_cell(or_connection_t *conn)
 
   auth_challenge_cell_t *ac = auth_challenge_cell_new();
 
+  tor_assert(sizeof(ac->challenge) == 32);
   crypto_rand((char*)ac->challenge, sizeof(ac->challenge));
 
   auth_challenge_cell_add_methods(ac, AUTHTYPE_RSA_SHA256_TLSSECRET);
+  /* Disabled, because everything that supports this method also supports
+   * the much-superior ED25519_SHA256_RFC5705 */
+  /* auth_challenge_cell_add_methods(ac, AUTHTYPE_RSA_SHA256_RFC5705); */
+  auth_challenge_cell_add_methods(ac, AUTHTYPE_ED25519_SHA256_RFC5705);
   auth_challenge_cell_set_n_methods(ac,
                                     auth_challenge_cell_getlen_methods(ac));
 
   cell = var_cell_new(auth_challenge_cell_encoded_len(ac));
   ssize_t len = auth_challenge_cell_encode(cell->payload, cell->payload_len,
                                            ac);
-  if (len != cell->payload_len)
+  if (len != cell->payload_len) {
+    /* LCOV_EXCL_START */
+    log_warn(LD_BUG, "Encoded auth challenge cell length not as expected");
     goto done;
+    /* LCOV_EXCL_STOP */
+  }
   cell->command = CELL_AUTH_CHALLENGE;
 
   connection_or_write_var_cell_to_buf(cell, conn);
@@ -2221,8 +2363,8 @@ connection_or_send_auth_challenge_cell(or_connection_t *conn)
 }
 
 /** Compute the main body of an AUTHENTICATE cell that a client can use
- * to authenticate itself on a v3 handshake for <b>conn</b>.  Write it to the
- * <b>outlen</b>-byte buffer at <b>out</b>.
+ * to authenticate itself on a v3 handshake for <b>conn</b>.  Return it
+ * in a var_cell_t.
  *
  * If <b>server</b> is true, only calculate the first
  * V3_AUTH_FIXED_PART_LEN bytes -- the part of the authenticator that's
@@ -2238,24 +2380,44 @@ connection_or_send_auth_challenge_cell(or_connection_t *conn)
  *
  * Return the length of the cell body on success, and -1 on failure.
  */
-int
+var_cell_t *
 connection_or_compute_authenticate_cell_body(or_connection_t *conn,
-                                             uint8_t *out, size_t outlen,
+                                             const int authtype,
                                              crypto_pk_t *signing_key,
-                                             int server)
+                                      const ed25519_keypair_t *ed_signing_key,
+                                      int server)
 {
   auth1_t *auth = NULL;
   auth_ctx_t *ctx = auth_ctx_new();
-  int result;
+  var_cell_t *result = NULL;
+  int old_tlssecrets_algorithm = 0;
+  const char *authtype_str = NULL;
 
-  /* assert state is reasonable XXXX */
+  int is_ed = 0;
 
-  ctx->is_ed = 0;
+  /* assert state is reasonable XXXX */
+  switch (authtype) {
+  case AUTHTYPE_RSA_SHA256_TLSSECRET:
+    authtype_str = "AUTH0001";
+    old_tlssecrets_algorithm = 1;
+    break;
+  case AUTHTYPE_RSA_SHA256_RFC5705:
+    authtype_str = "AUTH0002";
+    break;
+  case AUTHTYPE_ED25519_SHA256_RFC5705:
+    authtype_str = "AUTH0003";
+    is_ed = 1;
+    break;
+  default:
+    tor_assert(0);
+    break;
+  }
 
   auth = auth1_new();
+  ctx->is_ed = is_ed;
 
   /* Type: 8 bytes. */
-  memcpy(auth1_getarray_type(auth), "AUTH0001", 8);
+  memcpy(auth1_getarray_type(auth), authtype_str, 8);
 
   {
     const tor_x509_cert_t *id_cert=NULL, *link_cert=NULL;
@@ -2265,7 +2427,7 @@ connection_or_compute_authenticate_cell_body(or_connection_t *conn,
       goto err;
     my_digests = tor_x509_cert_get_id_digests(id_cert);
     their_digests =
-      tor_x509_cert_get_id_digests(conn->handshake_state->id_cert);
+      tor_x509_cert_get_id_digests(conn->handshake_state->certs->id_cert);
     tor_assert(my_digests);
     tor_assert(their_digests);
     my_id = (uint8_t*)my_digests->d[DIGEST_SHA256];
@@ -2281,6 +2443,22 @@ connection_or_compute_authenticate_cell_body(or_connection_t *conn,
     memcpy(auth->sid, server_id, 32);
   }
 
+  if (is_ed) {
+    const ed25519_public_key_t *my_ed_id, *their_ed_id;
+    if (!conn->handshake_state->certs->ed_id_sign) {
+      log_warn(LD_OR, "Ed authenticate without Ed ID cert from peer.");
+      goto err;
+    }
+    my_ed_id = get_master_identity_key();
+    their_ed_id = &conn->handshake_state->certs->ed_id_sign->signing_key;
+
+    const uint8_t *cid_ed = (server ? their_ed_id : my_ed_id)->pubkey;
+    const uint8_t *sid_ed = (server ? my_ed_id : their_ed_id)->pubkey;
+
+    memcpy(auth->u1_cid_ed, cid_ed, ED25519_PUBKEY_LEN);
+    memcpy(auth->u1_sid_ed, sid_ed, ED25519_PUBKEY_LEN);
+  }
+
   {
     crypto_digest_t *server_d, *client_d;
     if (server) {
@@ -2309,7 +2487,8 @@ connection_or_compute_authenticate_cell_body(or_connection_t *conn,
       cert = freecert;
     }
     if (!cert) {
-      log_warn(LD_OR, "Unable to find cert when making AUTH1 data.");
+      log_warn(LD_OR, "Unable to find cert when making %s data.",
+               authtype_str);
       goto err;
     }
 
@@ -2321,36 +2500,79 @@ connection_or_compute_authenticate_cell_body(or_connection_t *conn,
   }
 
   /* HMAC of clientrandom and serverrandom using master key : 32 octets */
-  tor_tls_get_tlssecrets(conn->tls, auth->tlssecrets);
+  if (old_tlssecrets_algorithm) {
+    tor_tls_get_tlssecrets(conn->tls, auth->tlssecrets);
+  } else {
+    char label[128];
+    tor_snprintf(label, sizeof(label),
+                 "EXPORTER FOR TOR TLS CLIENT BINDING %s", authtype_str);
+    tor_tls_export_key_material(conn->tls, auth->tlssecrets,
+                                auth->cid, sizeof(auth->cid),
+                                label);
+  }
 
   /* 8 octets were reserved for the current time, but we're trying to get out
    * of the habit of sending time around willynilly.  Fortunately, nothing
    * checks it.  That's followed by 16 bytes of nonce. */
   crypto_rand((char*)auth->rand, 24);
 
+  ssize_t maxlen = auth1_encoded_len(auth, ctx);
+  if (ed_signing_key && is_ed) {
+    maxlen += ED25519_SIG_LEN;
+  } else if (signing_key && !is_ed) {
+    maxlen += crypto_pk_keysize(signing_key);
+  }
+
+  const int AUTH_CELL_HEADER_LEN = 4; /* 2 bytes of type, 2 bytes of length */
+  result = var_cell_new(AUTH_CELL_HEADER_LEN + maxlen);
+  uint8_t *const out = result->payload + AUTH_CELL_HEADER_LEN;
+  const size_t outlen = maxlen;
   ssize_t len;
+
+  result->command = CELL_AUTHENTICATE;
+  set_uint16(result->payload, htons(authtype));
+
   if ((len = auth1_encode(out, outlen, auth, ctx)) < 0) {
-    log_warn(LD_OR, "Unable to encode signed part of AUTH1 data.");
+    /* LCOV_EXCL_START */
+    log_warn(LD_BUG, "Unable to encode signed part of AUTH1 data.");
     goto err;
+    /* LCOV_EXCL_STOP */
   }
 
   if (server) {
     auth1_t *tmp = NULL;
     ssize_t len2 = auth1_parse(&tmp, out, len, ctx);
     if (!tmp) {
-      log_warn(LD_OR, "Unable to parse signed part of AUTH1 data.");
+      /* LCOV_EXCL_START */
+      log_warn(LD_BUG, "Unable to parse signed part of AUTH1 data that we just "
+               "encoded");
       goto err;
+      /* LCOV_EXCL_STOP */
     }
-    result = (int) (tmp->end_of_fixed_part - out);
+    result->payload_len = (tmp->end_of_signed - result->payload);
+
     auth1_free(tmp);
     if (len2 != len) {
-      log_warn(LD_OR, "Mismatched length when re-parsing AUTH1 data.");
+      /* LCOV_EXCL_START */
+      log_warn(LD_BUG, "Mismatched length when re-parsing AUTH1 data.");
       goto err;
+      /* LCOV_EXCL_STOP */
     }
     goto done;
   }
 
-  if (signing_key) {
+  if (ed_signing_key && is_ed) {
+    ed25519_signature_t sig;
+    if (ed25519_sign(&sig, out, len, ed_signing_key) < 0) {
+      /* LCOV_EXCL_START */
+      log_warn(LD_BUG, "Unable to sign ed25519 authentication data");
+      goto err;
+      /* LCOV_EXCL_STOP */
+    }
+    auth1_setlen_sig(auth, ED25519_SIG_LEN);
+    memcpy(auth1_getarray_sig(auth), sig.sig, ED25519_SIG_LEN);
+
+  } else if (signing_key && !is_ed) {
     auth1_setlen_sig(auth, crypto_pk_keysize(signing_key));
 
     char d[32];
@@ -2365,18 +2587,24 @@ connection_or_compute_authenticate_cell_body(or_connection_t *conn,
     }
 
     auth1_setlen_sig(auth, siglen);
+  }
 
-    len = auth1_encode(out, outlen, auth, ctx);
-    if (len < 0) {
-      log_warn(LD_OR, "Unable to encode signed AUTH1 data.");
-      goto err;
-    }
+  len = auth1_encode(out, outlen, auth, ctx);
+  if (len < 0) {
+    /* LCOV_EXCL_START */
+    log_warn(LD_BUG, "Unable to encode signed AUTH1 data.");
+    goto err;
+    /* LCOV_EXCL_STOP */
   }
-  result = (int) len;
+  tor_assert(len + AUTH_CELL_HEADER_LEN <= result->payload_len);
+  result->payload_len = len + AUTH_CELL_HEADER_LEN;
+  set_uint16(result->payload+2, htons(len));
+
   goto done;
 
  err:
-  result = -1;
+  var_cell_free(result);
+  result = NULL;
  done:
   auth1_free(auth);
   auth_ctx_free(ctx);
@@ -2390,44 +2618,29 @@ connection_or_send_authenticate_cell,(or_connection_t *conn, int authtype))
 {
   var_cell_t *cell;
   crypto_pk_t *pk = tor_tls_get_my_client_auth_key();
-  int authlen;
-  size_t cell_maxlen;
   /* XXXX make sure we're actually supposed to send this! */
 
   if (!pk) {
     log_warn(LD_BUG, "Can't compute authenticate cell: no client auth key");
     return -1;
   }
-  if (authtype != AUTHTYPE_RSA_SHA256_TLSSECRET) {
+  if (! authchallenge_type_is_supported(authtype)) {
     log_warn(LD_BUG, "Tried to send authenticate cell with unknown "
              "authentication type %d", authtype);
     return -1;
   }
 
-  cell_maxlen = 4 + /* overhead */
-    V3_AUTH_BODY_LEN + /* Authentication body */
-    crypto_pk_keysize(pk) + /* Max signature length */
-    16 /* add a few extra bytes just in case. */;
-
-  cell = var_cell_new(cell_maxlen);
-  cell->command = CELL_AUTHENTICATE;
-  set_uint16(cell->payload, htons(AUTHTYPE_RSA_SHA256_TLSSECRET));
-  /* skip over length ; we don't know that yet. */
-
-  authlen = connection_or_compute_authenticate_cell_body(conn,
-                                                         cell->payload+4,
-                                                         cell_maxlen-4,
-                                                         pk,
-                                                         0 /* not server */);
-  if (authlen < 0) {
+  cell = connection_or_compute_authenticate_cell_body(conn,
+                                                 authtype,
+                                                 pk,
+                                                 get_current_auth_keypair(),
+                                                 0 /* not server */);
+  if (! cell) {
+    /* LCOV_EXCL_START */
     log_warn(LD_BUG, "Unable to compute authenticate cell!");
-    var_cell_free(cell);
     return -1;
+    /* LCOV_EXCL_STOP */
   }
-  tor_assert(authlen + 4 <= cell->payload_len);
-  set_uint16(cell->payload+2, htons(authlen));
-  cell->payload_len = authlen + 4;
-
   connection_or_write_var_cell_to_buf(cell, conn);
   var_cell_free(cell);
 
diff --git a/src/or/connection_or.h b/src/or/connection_or.h
index 2e8c6066cc..da95718ac9 100644
--- a/src/or/connection_or.h
+++ b/src/or/connection_or.h
@@ -40,7 +40,9 @@ void connection_or_notify_error(or_connection_t *conn,
 MOCK_DECL(or_connection_t *,
           connection_or_connect,
           (const tor_addr_t *addr, uint16_t port,
-           const char *id_digest, channel_tls_t *chan));
+           const char *id_digest,
+           const ed25519_public_key_t *ed_id,
+           channel_tls_t *chan));
 
 void connection_or_close_normally(or_connection_t *orconn, int flush);
 MOCK_DECL(void,connection_or_close_for_error,
@@ -59,10 +61,12 @@ int connection_init_or_handshake_state(or_connection_t *conn,
 void connection_or_init_conn_from_address(or_connection_t *conn,
                                           const tor_addr_t *addr,
                                           uint16_t port,
-                                          const char *id_digest,
+                                          const char *rsa_id_digest,
+                                          const ed25519_public_key_t *ed_id,
                                           int started_here);
 int connection_or_client_learned_peer_id(or_connection_t *conn,
-                                         const uint8_t *peer_id);
+                              const uint8_t *rsa_peer_id,
+                              const ed25519_public_key_t *ed_peer_id);
 time_t connection_or_client_used(or_connection_t *conn);
 MOCK_DECL(int, connection_or_get_num_circuits, (or_connection_t *conn));
 void or_handshake_state_free(or_handshake_state_t *state);
@@ -84,10 +88,14 @@ int connection_or_send_versions(or_connection_t *conn, int v3_plus);
 MOCK_DECL(int,connection_or_send_netinfo,(or_connection_t *conn));
 int connection_or_send_certs_cell(or_connection_t *conn);
 int connection_or_send_auth_challenge_cell(or_connection_t *conn);
-int connection_or_compute_authenticate_cell_body(or_connection_t *conn,
-                                                 uint8_t *out, size_t outlen,
-                                                 crypto_pk_t *signing_key,
-                                                 int server);
+int authchallenge_type_is_supported(uint16_t challenge_type);
+int authchallenge_type_is_better(uint16_t challenge_type_a,
+                                 uint16_t challenge_type_b);
+var_cell_t *connection_or_compute_authenticate_cell_body(or_connection_t *conn,
+                                       const int authtype,
+                                       crypto_pk_t *signing_key,
+                                       const ed25519_keypair_t *ed_signing_key,
+                                       int server);
 MOCK_DECL(int,connection_or_send_authenticate_cell,
           (or_connection_t *conn, int type));
 
diff --git a/src/or/dirserv.c b/src/or/dirserv.c
index 6e25323bf9..c797c9aa0e 100644
--- a/src/or/dirserv.c
+++ b/src/or/dirserv.c
@@ -3253,7 +3253,9 @@ dirserv_single_reachability_test(time_t now, routerinfo_t *router)
             router->nickname, fmt_addr32(router->addr), router->or_port);
   tor_addr_from_ipv4h(&router_addr, router->addr);
   chan = channel_tls_connect(&router_addr, router->or_port,
-                             router->cache_info.identity_digest);
+                             router->cache_info.identity_digest,
+                             NULL // XXXX Ed25519 ID.
+                             );
   if (chan) command_setup_channel(chan);
 
   /* Possible IPv6. */
@@ -3265,7 +3267,9 @@ dirserv_single_reachability_test(time_t now, routerinfo_t *router)
               tor_addr_to_str(addrstr, &router->ipv6_addr, sizeof(addrstr), 1),
               router->ipv6_orport);
     chan = channel_tls_connect(&router->ipv6_addr, router->ipv6_orport,
-                               router->cache_info.identity_digest);
+                               router->cache_info.identity_digest,
+                               NULL // XXXX Ed25519 ID.
+                               );
     if (chan) command_setup_channel(chan);
   }
 }
diff --git a/src/or/or.h b/src/or/or.h
index d0570a9249..1fc4b16e63 100644
--- a/src/or/or.h
+++ b/src/or/or.h
@@ -1348,13 +1348,34 @@ typedef struct listener_connection_t {
 #define OR_CERT_TYPE_RSA_ED_CROSSCERT 7
 /**@}*/
 
-/** The one currently supported type of AUTHENTICATE cell.  It contains
+/** The first supported type of AUTHENTICATE cell.  It contains
  * a bunch of structures signed with an RSA1024 key.  The signed
  * structures include a HMAC using negotiated TLS secrets, and a digest
  * of all cells sent or received before the AUTHENTICATE cell (including
  * the random server-generated AUTH_CHALLENGE cell).
  */
 #define AUTHTYPE_RSA_SHA256_TLSSECRET 1
+/** As AUTHTYPE_RSA_SHA256_TLSSECRET, but instead of using the
+ * negotiated TLS secrets, uses exported keying material from the TLS
+ * session as described in RFC 5705.
+ *
+ * Not used by today's tors, since everything that supports this
+ * also supports ED25519_SHA3_5705, which is better.
+ **/
+#define AUTHTYPE_RSA_SHA256_RFC5705 2
+/** As AUTHTYPE_RSA_SHA256_RFC5705, but uses an Ed25519 identity key to
+ * authenticate.  */
+#define AUTHTYPE_ED25519_SHA256_RFC5705 3
+/*
+ * NOTE: authchallenge_type_is_better() relies on these AUTHTYPE codes
+ * being sorted in order of preference.  If we someday add one with
+ * a higher numerical value that we don't like as much, we should revise
+ * authchallenge_type_is_better().
+ */
+
+
+
+
 
 /** The length of the part of the AUTHENTICATE cell body that the client and
  * server can generate independently (when using RSA_SHA256_TLSSECRET). It
@@ -1365,6 +1386,34 @@ typedef struct listener_connection_t {
  * signs. */
 #define V3_AUTH_BODY_LEN (V3_AUTH_FIXED_PART_LEN + 8 + 16)
 
+/** Structure to hold all the certificates we've received on an OR connection
+ */
+typedef struct or_handshake_certs_t {
+  /** True iff we originated this connection. */
+  int started_here;
+  /** The cert for the 'auth' RSA key that's supposed to sign the AUTHENTICATE
+   * cell. Signed with the RSA identity key. */
+  tor_x509_cert_t *auth_cert;
+  /** The cert for the 'link' RSA key that was used to negotiate the TLS
+   *  connection.  Signed with the RSA identity key. */
+  tor_x509_cert_t *link_cert;
+  /** A self-signed identity certificate: the RSA identity key signed
+   * with itself.  */
+  tor_x509_cert_t *id_cert;
+  /** The Ed25519 signing key, signed with the Ed25519 identity key. */
+  struct tor_cert_st *ed_id_sign;
+  /** A digest of the X509 link certificate for the TLS connection, signed
+   * with the Ed25519 siging key. */
+  struct tor_cert_st *ed_sign_link;
+  /** The Ed25519 authentication key (that's supposed to sign an AUTHENTICATE
+   * cell) , signed with the Ed25519 siging key. */
+  struct tor_cert_st *ed_sign_auth;
+  /** The Ed25519 identity key, crosssigned with the RSA identity key. */
+  uint8_t *ed_rsa_crosscert;
+  /** The length of <b>ed_rsa_crosscert</b> in bytes */
+  size_t ed_rsa_crosscert_len;
+} or_handshake_certs_t;
+
 /** Stores flags and information related to the portion of a v2/v3 Tor OR
  * connection handshake that happens after the TLS handshake is finished.
  */
@@ -1385,6 +1434,8 @@ typedef struct or_handshake_state_t {
 
   /* True iff we've received valid authentication to some identity. */
   unsigned int authenticated : 1;
+  unsigned int authenticated_rsa : 1;
+  unsigned int authenticated_ed25519 : 1;
 
   /* True iff we have sent a netinfo cell */
   unsigned int sent_netinfo : 1;
@@ -1402,9 +1453,12 @@ typedef struct or_handshake_state_t {
   unsigned int digest_received_data : 1;
   /**@}*/
 
-  /** Identity digest that we have received and authenticated for our peer
+  /** Identity RSA digest that we have received and authenticated for our peer
    * on this connection. */
-  uint8_t authenticated_peer_id[DIGEST_LEN];
+  uint8_t authenticated_rsa_peer_id[DIGEST_LEN];
+  /** Identity Ed25519 public key that we have received and authenticated for
+   * our peer on this connection. */
+  ed25519_public_key_t authenticated_ed25519_peer_id;
 
   /** Digests of the cells that we have sent or received as part of a V3
    * handshake.  Used for making and checking AUTHENTICATE cells.
@@ -1417,14 +1471,8 @@ typedef struct or_handshake_state_t {
 
   /** Certificates that a connection initiator sent us in a CERTS cell; we're
    * holding on to them until we get an AUTHENTICATE cell.
-   *
-   * @{
    */
-  /** The cert for the key that's supposed to sign the AUTHENTICATE cell */
-  tor_x509_cert_t *auth_cert;
-  /** A self-signed identity certificate */
-  tor_x509_cert_t *id_cert;
-  /**@}*/
+  or_handshake_certs_t *certs;
 } or_handshake_state_t;
 
 /** Length of Extended ORPort connection identifier. */
diff --git a/src/or/routerkeys.c b/src/or/routerkeys.c
index 7a1a2c9b2d..b6f20e6642 100644
--- a/src/or/routerkeys.c
+++ b/src/or/routerkeys.c
@@ -24,6 +24,7 @@
 #define ENC_KEY_HEADER "Boxed Ed25519 key"
 #define ENC_KEY_TAG "master"
 
+/* DOCDOC */
 static ssize_t
 do_getpass(const char *prompt, char *buf, size_t buflen,
            int twice, const or_options_t *options)
@@ -90,6 +91,7 @@ do_getpass(const char *prompt, char *buf, size_t buflen,
   return length;
 }
 
+/* DOCDOC */
 int
 read_encrypted_secret_key(ed25519_secret_key_t *out,
                           const char *fname)
@@ -162,6 +164,7 @@ read_encrypted_secret_key(ed25519_secret_key_t *out,
   return r;
 }
 
+/* DOCDOC */
 int
 write_encrypted_secret_key(const ed25519_secret_key_t *key,
                            const char *fname)
@@ -205,6 +208,7 @@ write_encrypted_secret_key(const ed25519_secret_key_t *key,
   return r;
 }
 
+/* DOCDOC */
 static int
 write_secret_key(const ed25519_secret_key_t *key, int encrypted,
                  const char *fname,
@@ -932,7 +936,18 @@ load_ed_keys(const or_options_t *options, time_t now)
   return -1;
 }
 
-/* DOCDOC */
+/**
+ * Retrieve our currently-in-use Ed25519 link certificate and id certificate,
+ * and, if they would expire soon (based on the time <b>now</b>, generate new
+ * certificates (without embedding the public part of the signing key inside).
+ *
+ * The signed_key from the expiring certificate will be used to sign the new
+ * key within newly generated X509 certificate.
+ *
+ * Returns -1 upon error.  Otherwise, returns 0 upon success (either when the
+ * current certificate is still valid, or when a new certificate was
+ * successfully generated).
+ */
 int
 generate_ed_link_cert(const or_options_t *options, time_t now)
 {
@@ -972,6 +987,17 @@ generate_ed_link_cert(const or_options_t *options, time_t now)
 #undef SET_KEY
 #undef SET_CERT
 
+/**
+ * Return 1 if any of the following are true:
+ *
+ *   - if one of our Ed25519 signing, auth, or link certificates would expire
+ *     soon w.r.t. the time <b>now</b>,
+ *   - if we do not currently have a link certificate, or
+ *   - if our cached Ed25519 link certificate is not same as the one we're
+ *     currently using.
+ *
+ * Otherwise, returns 0.
+ */
 int
 should_make_new_ed_keys(const or_options_t *options, const time_t now)
 {
@@ -1002,6 +1028,60 @@ should_make_new_ed_keys(const or_options_t *options, const time_t now)
 
 #undef EXPIRES_SOON
 
+#ifdef TOR_UNIT_TESTS
+/* Helper for unit tests: populate the ed25519 keys without saving or loading */
+void
+init_mock_ed_keys(const crypto_pk_t *rsa_identity_key)
+{
+  routerkeys_free_all();
+
+#define MAKEKEY(k)                                      \
+  k = tor_malloc_zero(sizeof(*k));                      \
+  if (ed25519_keypair_generate(k, 0) < 0) {             \
+    log_warn(LD_BUG, "Couldn't make a keypair");        \
+    goto err;                                           \
+  }
+  MAKEKEY(master_identity_key);
+  MAKEKEY(master_signing_key);
+  MAKEKEY(current_auth_key);
+#define MAKECERT(cert, signing, signed_, type, flags)            \
+  cert = tor_cert_create(signing,                                \
+                         type,                                   \
+                         &signed_->pubkey,                       \
+                         time(NULL), 86400,                      \
+                         flags);                                 \
+  if (!cert) {                                                   \
+    log_warn(LD_BUG, "Couldn't make a %s certificate!", #cert);  \
+    goto err;                                                    \
+  }
+
+  MAKECERT(signing_key_cert,
+           master_identity_key, master_signing_key, CERT_TYPE_ID_SIGNING,
+           CERT_FLAG_INCLUDE_SIGNING_KEY);
+  MAKECERT(auth_key_cert,
+           master_signing_key, current_auth_key, CERT_TYPE_SIGNING_AUTH, 0);
+
+  if (generate_ed_link_cert(get_options(), time(NULL)) < 0) {
+    log_warn(LD_BUG, "Couldn't make link certificate");
+    goto err;
+  }
+
+  rsa_ed_crosscert_len = tor_make_rsa_ed25519_crosscert(
+                                     &master_identity_key->pubkey,
+                                     rsa_identity_key,
+                                     time(NULL)+86400,
+                                     &rsa_ed_crosscert);
+
+  return;
+
+ err:
+  routerkeys_free_all();
+  tor_assert_nonfatal_unreached();
+}
+#undef MAKEKEY
+#undef MAKECERT
+#endif
+
 const ed25519_public_key_t *
 get_master_identity_key(void)
 {
@@ -1010,6 +1090,16 @@ get_master_identity_key(void)
   return &master_identity_key->pubkey;
 }
 
+#ifdef TOR_UNIT_TESTS
+/* only exists for the unit tests, since otherwise the identity key
+ * should be used to sign nothing but the signing key. */
+const ed25519_keypair_t *
+get_master_identity_keypair(void)
+{
+  return master_identity_key;
+}
+#endif
+
 const ed25519_keypair_t *
 get_master_signing_keypair(void)
 {
@@ -1144,9 +1234,12 @@ routerkeys_free_all(void)
   tor_cert_free(signing_key_cert);
   tor_cert_free(link_cert_cert);
   tor_cert_free(auth_key_cert);
+  tor_free(rsa_ed_crosscert);
 
   master_identity_key = master_signing_key = NULL;
   current_auth_key = NULL;
   signing_key_cert = link_cert_cert = auth_key_cert = NULL;
+  rsa_ed_crosscert = NULL; // redundant
+  rsa_ed_crosscert_len = 0;
 }
 
diff --git a/src/or/routerkeys.h b/src/or/routerkeys.h
index be9b19aea8..307a1cd234 100644
--- a/src/or/routerkeys.h
+++ b/src/or/routerkeys.h
@@ -73,5 +73,10 @@ int write_encrypted_secret_key(const ed25519_secret_key_t *out,
 
 void routerkeys_free_all(void);
 
+#ifdef TOR_UNIT_TESTS
+const ed25519_keypair_t *get_master_identity_keypair(void);
+void init_mock_ed_keys(const crypto_pk_t *rsa_identity_key);
+#endif
+
 #endif
 
diff --git a/src/or/routerparse.c b/src/or/routerparse.c
index 7f7d38234d..cb2bc72d0c 100644
--- a/src/or/routerparse.c
+++ b/src/or/routerparse.c
@@ -2100,12 +2100,13 @@ router_parse_entry_from_string(const char *s, const char *end,
 
       ed25519_checkable_t check[3];
       int check_ok[3];
-      if (tor_cert_get_checkable_sig(&check[0], cert, NULL) < 0) {
+      time_t expires = TIME_MAX;
+      if (tor_cert_get_checkable_sig(&check[0], cert, NULL, &expires) < 0) {
         log_err(LD_BUG, "Couldn't create 'checkable' for cert.");
         goto err;
       }
       if (tor_cert_get_checkable_sig(&check[1],
-                                     ntor_cc_cert, &ntor_cc_pk) < 0) {
+                               ntor_cc_cert, &ntor_cc_pk, &expires) < 0) {
         log_err(LD_BUG, "Couldn't create 'checkable' for ntor_cc_cert.");
         goto err;
       }
@@ -2135,10 +2136,7 @@ router_parse_entry_from_string(const char *s, const char *end,
       }
 
       /* We check this before adding it to the routerlist. */
-      if (cert->valid_until < ntor_cc_cert->valid_until)
-        router->cert_expiration_time = cert->valid_until;
-      else
-        router->cert_expiration_time = ntor_cc_cert->valid_until;
+      router->cert_expiration_time = expires;
     }
   }
 
@@ -2452,7 +2450,7 @@ extrainfo_parse_entry_from_string(const char *s, const char *end,
 
       ed25519_checkable_t check[2];
       int check_ok[2];
-      if (tor_cert_get_checkable_sig(&check[0], cert, NULL) < 0) {
+      if (tor_cert_get_checkable_sig(&check[0], cert, NULL, NULL) < 0) {
         log_err(LD_BUG, "Couldn't create 'checkable' for cert.");
         goto err;
       }
diff --git a/src/or/torcert.c b/src/or/torcert.c
index 37a201ea60..4259363f35 100644
--- a/src/or/torcert.c
+++ b/src/or/torcert.c
@@ -25,6 +25,8 @@
  * that one is authority_cert_t, and it's mostly handled in routerlist.c.
  */
 
+#include "or.h"
+#include "config.h"
 #include "crypto.h"
 #include "torcert.h"
 #include "ed25519_cert.h"
@@ -154,7 +156,11 @@ tor_cert_parse(const uint8_t *encoded, const size_t len)
   cert->encoded_len = len;
 
   memcpy(cert->signed_key.pubkey, parsed->certified_key, 32);
-  cert->valid_until = parsed->exp_field * 3600;
+  const int64_t valid_until_64 = ((int64_t)parsed->exp_field) * 3600;
+  if (valid_until_64 > TIME_MAX)
+    cert->valid_until = TIME_MAX - 1;
+  else
+    cert->valid_until = (time_t) valid_until_64;
   cert->cert_type = parsed->cert_type;
 
   for (unsigned i = 0; i < ed25519_cert_getlen_ext(parsed); ++i) {
@@ -181,11 +187,17 @@ tor_cert_parse(const uint8_t *encoded, const size_t len)
 }
 
 /** Fill in <b>checkable_out</b> with the information needed to check
- * the signature on <b>cert</b> with <b>pubkey</b>. */
+ * the signature on <b>cert</b> with <b>pubkey</b>.
+ *
+ * On success, if <b>expiration_out</b> is provided, and it is some time
+ * _after_ the expiration time of this certificate, set it to the
+ * expiration time of this certificate.
+ */
 int
 tor_cert_get_checkable_sig(ed25519_checkable_t *checkable_out,
                            const tor_cert_t *cert,
-                           const ed25519_public_key_t *pubkey)
+                           const ed25519_public_key_t *pubkey,
+                           time_t *expiration_out)
 {
   if (! pubkey) {
     if (cert->signing_key_included)
@@ -202,6 +214,10 @@ tor_cert_get_checkable_sig(ed25519_checkable_t *checkable_out,
   memcpy(checkable_out->signature.sig,
          cert->encoded + signed_len, ED25519_SIG_LEN);
 
+  if (expiration_out) {
+    *expiration_out = MIN(*expiration_out, cert->valid_until);
+  }
+
   return 0;
 }
 
@@ -216,14 +232,15 @@ tor_cert_checksig(tor_cert_t *cert,
 {
   ed25519_checkable_t checkable;
   int okay;
+  time_t expires = TIME_MAX;
 
-  if (now && now > cert->valid_until) {
-    cert->cert_expired = 1;
+  if (tor_cert_get_checkable_sig(&checkable, cert, pubkey, &expires) < 0)
     return -1;
-  }
 
-  if (tor_cert_get_checkable_sig(&checkable, cert, pubkey) < 0)
+  if (now && now > expires) {
+    cert->cert_expired = 1;
     return -1;
+  }
 
   if (ed25519_checksig_batch(&okay, &checkable, 1) < 0) {
     cert->sig_bad = 1;
@@ -272,6 +289,8 @@ tor_cert_opt_eq(const tor_cert_t *cert1, const tor_cert_t *cert2)
   return tor_cert_eq(cert1, cert2);
 }
 
+#define RSA_ED_CROSSCERT_PREFIX "Tor TLS RSA/Ed25519 cross-certificate"
+
 /** Create new cross-certification object to certify <b>ed_key</b> as the
  * master ed25519 identity key for the RSA identity key <b>rsa_key</b>.
  * Allocates and stores the encoded certificate in *<b>cert</b>, and returns
@@ -296,11 +315,21 @@ tor_make_rsa_ed25519_crosscert(const ed25519_public_key_t *ed_key,
   ssize_t sz = rsa_ed_crosscert_encode(res, alloc_sz, cc);
   tor_assert(sz > 0 && sz <= alloc_sz);
 
+  crypto_digest_t *d = crypto_digest256_new(DIGEST_SHA256);
+  crypto_digest_add_bytes(d, RSA_ED_CROSSCERT_PREFIX,
+                          strlen(RSA_ED_CROSSCERT_PREFIX));
+
   const int signed_part_len = 32 + 4;
+  crypto_digest_add_bytes(d, (char*)res, signed_part_len);
+
+  uint8_t digest[DIGEST256_LEN];
+  crypto_digest_get_digest(d, (char*)digest, sizeof(digest));
+  crypto_digest_free(d);
+
   int siglen = crypto_pk_private_sign(rsa_key,
                                       (char*)rsa_ed_crosscert_getarray_sig(cc),
                                       rsa_ed_crosscert_getlen_sig(cc),
-                                      (char*)res, signed_part_len);
+                                      (char*)digest, sizeof(digest));
   tor_assert(siglen > 0 && siglen <= (int)crypto_pk_keysize(rsa_key));
   tor_assert(siglen <= UINT8_MAX);
   cc->sig_len = siglen;
@@ -312,3 +341,310 @@ tor_make_rsa_ed25519_crosscert(const ed25519_public_key_t *ed_key,
   return sz;
 }
 
+/**
+ * Check whether the <b>crosscert_len</b> byte certificate in <b>crosscert</b>
+ * is in fact a correct cross-certification of <b>master_key</b> using
+ * the RSA key <b>rsa_id_key</b>.
+ *
+ * Also reject the certificate if it expired before
+ * <b>reject_if_expired_before</b>.
+ *
+ * Return 0 on success, negative on failure.
+ */
+int
+rsa_ed25519_crosscert_check(const uint8_t *crosscert,
+                            const size_t crosscert_len,
+                            const crypto_pk_t *rsa_id_key,
+                            const ed25519_public_key_t *master_key,
+                            const time_t reject_if_expired_before)
+{
+  rsa_ed_crosscert_t *cc = NULL;
+  int rv;
+
+#define ERR(code, s)                                            \
+  do {                                                          \
+    log_fn(LOG_PROTOCOL_WARN, LD_PROTOCOL,                      \
+           "Received a bad RSA->Ed25519 crosscert: %s",         \
+           (s));                                                \
+    rv = (code);                                                \
+    goto err;                                                   \
+  } while (0)
+
+  if (BUG(crypto_pk_keysize(rsa_id_key) > PK_BYTES))
+    return -1;
+
+  if (BUG(!crosscert))
+    return -1;
+
+  ssize_t parsed_len = rsa_ed_crosscert_parse(&cc, crosscert, crosscert_len);
+  if (parsed_len < 0 || crosscert_len != (size_t)parsed_len) {
+    ERR(-2, "Unparseable or overlong crosscert");
+  }
+
+  if (tor_memneq(rsa_ed_crosscert_getarray_ed_key(cc),
+                 master_key->pubkey,
+                 ED25519_PUBKEY_LEN)) {
+    ERR(-3, "Crosscert did not match Ed25519 key");
+  }
+
+  const uint32_t expiration_date = rsa_ed_crosscert_get_expiration(cc);
+  const uint64_t expiration_time = expiration_date * 3600;
+
+  if (reject_if_expired_before < 0 ||
+      expiration_time < (uint64_t)reject_if_expired_before) {
+    ERR(-4, "Crosscert is expired");
+  }
+
+  const uint8_t *eos = rsa_ed_crosscert_get_end_of_signed(cc);
+  const uint8_t *sig = rsa_ed_crosscert_getarray_sig(cc);
+  const uint8_t siglen = rsa_ed_crosscert_get_sig_len(cc);
+  tor_assert(eos >= crosscert);
+  tor_assert((size_t)(eos - crosscert) <= crosscert_len);
+  tor_assert(siglen == rsa_ed_crosscert_getlen_sig(cc));
+
+  /* Compute the digest */
+  uint8_t digest[DIGEST256_LEN];
+  crypto_digest_t *d = crypto_digest256_new(DIGEST_SHA256);
+  crypto_digest_add_bytes(d, RSA_ED_CROSSCERT_PREFIX,
+                          strlen(RSA_ED_CROSSCERT_PREFIX));
+  crypto_digest_add_bytes(d, (char*)crosscert, eos-crosscert);
+  crypto_digest_get_digest(d, (char*)digest, sizeof(digest));
+  crypto_digest_free(d);
+
+  /* Now check the signature */
+  uint8_t signed_[PK_BYTES];
+  int signed_len = crypto_pk_public_checksig(rsa_id_key,
+                                          (char*)signed_, sizeof(signed_),
+                                          (char*)sig, siglen);
+  if (signed_len < DIGEST256_LEN) {
+    ERR(-5, "Bad signature, or length of signed data not as expected");
+  }
+
+  if (tor_memneq(digest, signed_, DIGEST256_LEN)) {
+    ERR(-6, "The signature was good, but it didn't match the data");
+  }
+
+  rv = 0;
+ err:
+  rsa_ed_crosscert_free(cc);
+  return rv;
+}
+
+/** Construct and return a new empty or_handshake_certs object */
+or_handshake_certs_t *
+or_handshake_certs_new(void)
+{
+  return tor_malloc_zero(sizeof(or_handshake_certs_t));
+}
+
+/** Release all storage held in <b>certs</b> */
+void
+or_handshake_certs_free(or_handshake_certs_t *certs)
+{
+  if (!certs)
+    return;
+
+  tor_x509_cert_free(certs->auth_cert);
+  tor_x509_cert_free(certs->link_cert);
+  tor_x509_cert_free(certs->id_cert);
+
+  tor_cert_free(certs->ed_id_sign);
+  tor_cert_free(certs->ed_sign_link);
+  tor_cert_free(certs->ed_sign_auth);
+  tor_free(certs->ed_rsa_crosscert);
+
+  memwipe(certs, 0xBD, sizeof(*certs));
+  tor_free(certs);
+}
+
+#undef ERR
+#define ERR(s)                                                  \
+  do {                                                          \
+    log_fn(severity, LD_PROTOCOL,                               \
+           "Received a bad CERTS cell: %s",                     \
+           (s));                                                \
+    return 0;                                                   \
+  } while (0)
+
+int
+or_handshake_certs_rsa_ok(int severity,
+                          or_handshake_certs_t *certs,
+                          tor_tls_t *tls,
+                          time_t now)
+{
+  tor_x509_cert_t *link_cert = certs->link_cert;
+  tor_x509_cert_t *auth_cert = certs->auth_cert;
+  tor_x509_cert_t *id_cert = certs->id_cert;
+
+  if (certs->started_here) {
+    if (! (id_cert && link_cert))
+      ERR("The certs we wanted (ID, Link) were missing");
+    if (! tor_tls_cert_matches_key(tls, link_cert))
+      ERR("The link certificate didn't match the TLS public key");
+    if (! tor_tls_cert_is_valid(severity, link_cert, id_cert, now, 0))
+      ERR("The link certificate was not valid");
+    if (! tor_tls_cert_is_valid(severity, id_cert, id_cert, now, 1))
+      ERR("The ID certificate was not valid");
+  } else {
+    if (! (id_cert && auth_cert))
+      ERR("The certs we wanted (ID, Auth) were missing");
+    if (! tor_tls_cert_is_valid(LOG_PROTOCOL_WARN, auth_cert, id_cert, now, 1))
+      ERR("The authentication certificate was not valid");
+    if (! tor_tls_cert_is_valid(LOG_PROTOCOL_WARN, id_cert, id_cert, now, 1))
+      ERR("The ID certificate was not valid");
+  }
+
+  return 1;
+}
+
+/** Check all the ed25519 certificates in <b>certs</b> against each other, and
+ * against the peer certificate in <b>tls</b> if appropriate.  On success,
+ * return 0; on failure, return a negative value and warn at level
+ * <b>severity</b> */
+int
+or_handshake_certs_ed25519_ok(int severity,
+                              or_handshake_certs_t *certs,
+                              tor_tls_t *tls,
+                              time_t now)
+{
+  ed25519_checkable_t check[10];
+  unsigned n_checkable = 0;
+  time_t expiration = TIME_MAX;
+
+#define ADDCERT(cert, pk)                                               \
+  do {                                                                  \
+    tor_assert(n_checkable < ARRAY_LENGTH(check));                      \
+    if (tor_cert_get_checkable_sig(&check[n_checkable++], cert, pk,     \
+                                   &expiration) < 0)                    \
+      ERR("Could not get checkable cert.");                             \
+  } while (0)
+
+  if (! certs->ed_id_sign || !certs->ed_id_sign->signing_key_included) {
+    ERR("No Ed25519 signing key");
+  }
+  ADDCERT(certs->ed_id_sign, NULL);
+
+  if (certs->started_here) {
+    if (! certs->ed_sign_link)
+      ERR("No Ed25519 link key");
+    {
+      /* check for a match with the TLS cert. */
+      tor_x509_cert_t *peer_cert = tor_tls_get_peer_cert(tls);
+      if (BUG(!peer_cert)) {
+        /* This is a bug, because if we got to this point, we are a connection
+         * that was initiated here, and we completed a TLS handshake. The
+         * other side *must* have given us a certificate! */
+        ERR("No x509 peer cert"); // LCOV_EXCL_LINE
+      }
+      const common_digests_t *peer_cert_digests =
+        tor_x509_cert_get_cert_digests(peer_cert);
+      int okay = tor_memeq(peer_cert_digests->d[DIGEST_SHA256],
+                           certs->ed_sign_link->signed_key.pubkey,
+                           DIGEST256_LEN);
+      tor_x509_cert_free(peer_cert);
+      if (!okay)
+        ERR("Link certificate does not match TLS certificate");
+    }
+
+    ADDCERT(certs->ed_sign_link, &certs->ed_id_sign->signed_key);
+
+  } else {
+    if (! certs->ed_sign_auth)
+      ERR("No Ed25519 link authentication key");
+    ADDCERT(certs->ed_sign_auth, &certs->ed_id_sign->signed_key);
+  }
+
+  if (expiration < now) {
+    ERR("At least one certificate expired.");
+  }
+
+  /* Okay, we've gotten ready to check all the Ed25519 certificates.
+   * Now, we are going to check the RSA certificate's cross-certification
+   * with the ED certificates.
+   *
+   * FFFF In the future, we might want to make this optional.
+   */
+
+  tor_x509_cert_t *rsa_id_cert = certs->id_cert;
+  if (!rsa_id_cert) {
+    ERR("Missing legacy RSA ID certificate");
+  }
+  if (! tor_tls_cert_is_valid(severity, rsa_id_cert, rsa_id_cert, now, 1)) {
+    ERR("The legacy RSA ID certificate was not valid");
+  }
+  if (! certs->ed_rsa_crosscert) {
+    ERR("Missing RSA->Ed25519 crosscert");
+  }
+  crypto_pk_t *rsa_id_key = tor_tls_cert_get_key(rsa_id_cert);
+  if (!rsa_id_key) {
+    ERR("RSA ID cert had no RSA key");
+  }
+
+  if (rsa_ed25519_crosscert_check(certs->ed_rsa_crosscert,
+                                  certs->ed_rsa_crosscert_len,
+                                  rsa_id_key,
+                                  &certs->ed_id_sign->signing_key,
+                                  now) < 0) {
+    crypto_pk_free(rsa_id_key);
+    ERR("Invalid RSA->Ed25519 crosscert");
+  }
+  crypto_pk_free(rsa_id_key);
+  rsa_id_key = NULL;
+
+  /* FFFF We could save a little time in the client case by queueing
+   * this batch to check it later, along with the signature from the
+   * AUTHENTICATE cell. That will change our data flow a bit, though,
+   * so I say "postpone". */
+
+  if (ed25519_checksig_batch(NULL, check, n_checkable) < 0) {
+    ERR("At least one Ed25519 certificate was badly signed");
+  }
+
+  return 1;
+}
+
+
+/**
+ * Check the Ed certificates and/or the RSA certificates, as appropriate.  If
+ * we obtained an Ed25519 identity, set *ed_id_out. If we obtained an RSA
+ * identity, set *rs_id_out. Otherwise, set them both to NULL.
+ */
+void
+or_handshake_certs_check_both(int severity,
+                              or_handshake_certs_t *certs,
+                              tor_tls_t *tls,
+                              time_t now,
+                              const ed25519_public_key_t **ed_id_out,
+                              const common_digests_t **rsa_id_out)
+{
+  tor_assert(ed_id_out);
+  tor_assert(rsa_id_out);
+
+  *ed_id_out = NULL;
+  *rsa_id_out = NULL;
+
+  if (certs->ed_id_sign) {
+    if (or_handshake_certs_ed25519_ok(severity, certs, tls, now)) {
+      tor_assert(certs->ed_id_sign);
+      tor_assert(certs->id_cert);
+
+      *ed_id_out = &certs->ed_id_sign->signing_key;
+      *rsa_id_out = tor_x509_cert_get_id_digests(certs->id_cert);
+
+      /* If we reached this point, we did not look at any of the
+       * subsidiary RSA certificates, so we'd better just remove them.
+       */
+      tor_x509_cert_free(certs->link_cert);
+      tor_x509_cert_free(certs->auth_cert);
+      certs->link_cert = certs->auth_cert = NULL;
+    }
+    /* We do _not_ fall through here.  If you provided us Ed25519
+     * certificates, we expect to verify them! */
+  } else {
+    /* No ed25519 keys given in the CERTS cell */
+    if (or_handshake_certs_rsa_ok(severity, certs, tls, now)) {
+      *rsa_id_out = tor_x509_cert_get_id_digests(certs->id_cert);
+    }
+  }
+
+}
diff --git a/src/or/torcert.h b/src/or/torcert.h
index 9c819c0abb..f7ca0ff521 100644
--- a/src/or/torcert.h
+++ b/src/or/torcert.h
@@ -57,8 +57,9 @@ tor_cert_t *tor_cert_parse(const uint8_t *cert, size_t certlen);
 void tor_cert_free(tor_cert_t *cert);
 
 int tor_cert_get_checkable_sig(ed25519_checkable_t *checkable_out,
-                                 const tor_cert_t *out,
-                                 const ed25519_public_key_t *pubkey);
+                               const tor_cert_t *out,
+                               const ed25519_public_key_t *pubkey,
+                               time_t *expiration_out);
 
 int tor_cert_checksig(tor_cert_t *cert,
                       const ed25519_public_key_t *pubkey, time_t now);
@@ -71,6 +72,28 @@ ssize_t tor_make_rsa_ed25519_crosscert(const ed25519_public_key_t *ed_key,
                                        const crypto_pk_t *rsa_key,
                                        time_t expires,
                                        uint8_t **cert);
+int rsa_ed25519_crosscert_check(const uint8_t *crosscert,
+                                const size_t crosscert_len,
+                                const crypto_pk_t *rsa_id_key,
+                                const ed25519_public_key_t *master_key,
+                                const time_t reject_if_expired_before);
+
+or_handshake_certs_t *or_handshake_certs_new(void);
+void or_handshake_certs_free(or_handshake_certs_t *certs);
+int or_handshake_certs_rsa_ok(int severity,
+                              or_handshake_certs_t *certs,
+                              tor_tls_t *tls,
+                              time_t now);
+int or_handshake_certs_ed25519_ok(int severity,
+                                  or_handshake_certs_t *certs,
+                                  tor_tls_t *tls,
+                                  time_t now);
+void or_handshake_certs_check_both(int severity,
+                              or_handshake_certs_t *certs,
+                              tor_tls_t *tls,
+                              time_t now,
+                              const ed25519_public_key_t **ed_id_out,
+                              const common_digests_t **rsa_id_out);
 
 #endif
 
diff --git a/src/test/include.am b/src/test/include.am
index 8ecfaf10c6..4af48cfbc1 100644
--- a/src/test/include.am
+++ b/src/test/include.am
@@ -130,6 +130,7 @@ src_test_test_SOURCES = \
 	src/test/test_helpers.c \
 	src/test/test_dns.c \
 	src/test/testing_common.c \
+	src/test/testing_rsakeys.c \
 	src/ext/tinytest.c
 
 src_test_test_slow_SOURCES = \
@@ -137,6 +138,7 @@ src_test_test_slow_SOURCES = \
 	src/test/test_crypto_slow.c \
 	src/test/test_util_slow.c \
 	src/test/testing_common.c \
+	src/test/testing_rsakeys.c \
 	src/ext/tinytest.c
 
 src_test_test_memwipe_SOURCES = \
diff --git a/src/test/test.h b/src/test/test.h
index 770f403cee..b7c769fe0d 100644
--- a/src/test/test.h
+++ b/src/test/test.h
@@ -74,6 +74,8 @@
 
 const char *get_fname(const char *name);
 struct crypto_pk_t *pk_generate(int idx);
+void init_pregenerated_keys(void);
+void free_pregenerated_keys(void);
 
 #define US2_CONCAT_2__(a, b) a ## __ ## b
 #define US_CONCAT_2__(a, b) a ## _ ## b
diff --git a/src/test/test_channeltls.c b/src/test/test_channeltls.c
index 08442e01b6..fd98ee40fb 100644
--- a/src/test/test_channeltls.c
+++ b/src/test/test_channeltls.c
@@ -32,6 +32,7 @@ static or_connection_t * tlschan_connection_or_connect_mock(
     const tor_addr_t *addr,
     uint16_t port,
     const char *digest,
+    const ed25519_public_key_t *ed_id,
     channel_tls_t *tlschan);
 static int tlschan_is_local_addr_mock(const tor_addr_t *addr);
 
@@ -70,7 +71,7 @@ test_channeltls_create(void *arg)
   MOCK(connection_or_connect, tlschan_connection_or_connect_mock);
 
   /* Try connecting */
-  ch = channel_tls_connect(&test_addr, 567, test_digest);
+  ch = channel_tls_connect(&test_addr, 567, test_digest, NULL);
   tt_assert(ch != NULL);
 
  done:
@@ -119,7 +120,7 @@ test_channeltls_num_bytes_queued(void *arg)
   MOCK(connection_or_connect, tlschan_connection_or_connect_mock);
 
   /* Try connecting */
-  ch = channel_tls_connect(&test_addr, 567, test_digest);
+  ch = channel_tls_connect(&test_addr, 567, test_digest, NULL);
   tt_assert(ch != NULL);
 
   /*
@@ -204,7 +205,7 @@ test_channeltls_overhead_estimate(void *arg)
   MOCK(connection_or_connect, tlschan_connection_or_connect_mock);
 
   /* Try connecting */
-  ch = channel_tls_connect(&test_addr, 567, test_digest);
+  ch = channel_tls_connect(&test_addr, 567, test_digest, NULL);
   tt_assert(ch != NULL);
 
   /* First case: silly low ratios should get clamped to 1.0 */
@@ -266,9 +267,11 @@ static or_connection_t *
 tlschan_connection_or_connect_mock(const tor_addr_t *addr,
                                    uint16_t port,
                                    const char *digest,
+                                   const ed25519_public_key_t *ed_id,
                                    channel_tls_t *tlschan)
 {
   or_connection_t *result = NULL;
+  (void) ed_id; // XXXX Not yet used.
 
   tt_assert(addr != NULL);
   tt_assert(port != 0);
diff --git a/src/test/test_link_handshake.c b/src/test/test_link_handshake.c
index 6c0567098f..bf5ff677c1 100644
--- a/src/test/test_link_handshake.c
+++ b/src/test/test_link_handshake.c
@@ -6,13 +6,19 @@
 #define CHANNELTLS_PRIVATE
 #define CONNECTION_PRIVATE
 #define TOR_CHANNEL_INTERNAL_
+#define TORTLS_PRIVATE
+#include <openssl/x509.h>
+#include <openssl/ssl.h>
 #include "or.h"
 #include "config.h"
 #include "connection.h"
 #include "connection_or.h"
 #include "channeltls.h"
 #include "link_handshake.h"
+#include "router.h"
+#include "routerkeys.h"
 #include "scheduler.h"
+#include "torcert.h"
 
 #include "test.h"
 #include "log_test_helpers.h"
@@ -37,6 +43,16 @@ mock_tls_cert_matches_key(const tor_tls_t *tls, const tor_x509_cert_t *cert)
   (void) cert; // XXXX look at this.
   return 1;
 }
+static tor_tls_t *mock_peer_cert_expect_tortls = NULL;
+static tor_x509_cert_t *mock_peer_cert = NULL;
+static tor_x509_cert_t *
+mock_get_peer_cert(tor_tls_t *tls)
+{
+  if (mock_peer_cert_expect_tortls &&
+      mock_peer_cert_expect_tortls != tls)
+    return NULL;
+  return mock_peer_cert;
+}
 
 static int mock_send_netinfo_called = 0;
 static int
@@ -57,33 +73,48 @@ mock_close_for_err(or_connection_t *orconn, int flush)
 }
 
 static int mock_send_authenticate_called = 0;
+static int mock_send_authenticate_called_with_type = 0;
 static int
 mock_send_authenticate(or_connection_t *conn, int type)
 {
   (void) conn;
-  (void) type;
+  mock_send_authenticate_called_with_type = type;
   ++mock_send_authenticate_called;// XXX check_this
   return 0;
 }
+static int
+mock_export_key_material(tor_tls_t *tls, uint8_t *secrets_out,
+                         const uint8_t *context,
+                         size_t context_len,
+                         const char *label)
+{
+  (void) tls;
+  (void)secrets_out;
+  (void)context;
+  (void)context_len;
+  (void)label;
+  memcpy(secrets_out, "int getRandomNumber(){return 4;}", 32);
+  return 0;
+}
 
 /* Test good certs cells */
 static void
 test_link_handshake_certs_ok(void *arg)
 {
-  (void) arg;
-
   or_connection_t *c1 = or_connection_new(CONN_TYPE_OR, AF_INET);
   or_connection_t *c2 = or_connection_new(CONN_TYPE_OR, AF_INET);
   var_cell_t *cell1 = NULL, *cell2 = NULL;
   certs_cell_t *cc1 = NULL, *cc2 = NULL;
   channel_tls_t *chan1 = NULL, *chan2 = NULL;
   crypto_pk_t *key1 = NULL, *key2 = NULL;
+  const int with_ed = !strcmp((const char *)arg, "Ed25519");
 
   scheduler_init();
 
   MOCK(tor_tls_cert_matches_key, mock_tls_cert_matches_key);
   MOCK(connection_or_write_var_cell_to_buf, mock_write_var_cell);
   MOCK(connection_or_send_netinfo, mock_send_netinfo);
+  MOCK(tor_tls_get_peer_cert, mock_get_peer_cert);
 
   key1 = pk_generate(2);
   key2 = pk_generate(3);
@@ -94,10 +125,18 @@ test_link_handshake_certs_ok(void *arg)
   tt_int_op(tor_tls_context_init(TOR_TLS_CTX_IS_PUBLIC_SERVER,
                                  key1, key2, 86400), ==, 0);
 
+  if (with_ed) {
+    /* If we're making a CERTS cell for an ed handshake, let's make sure we
+     * have some Ed25519 certificates and keys. */
+    init_mock_ed_keys(key2);
+  }
+
+  /* c1 has started_here == 1 */
   c1->base_.state = OR_CONN_STATE_OR_HANDSHAKING_V3;
   c1->link_proto = 3;
   tt_int_op(connection_init_or_handshake_state(c1, 1), ==, 0);
 
+  /* c2 has started_here == 0 */
   c2->base_.state = OR_CONN_STATE_OR_HANDSHAKING_V3;
   c2->link_proto = 3;
   tt_int_op(connection_init_or_handshake_state(c2, 0), ==, 0);
@@ -121,8 +160,13 @@ test_link_handshake_certs_ok(void *arg)
   tt_int_op(cell2->payload_len, ==,
             certs_cell_parse(&cc2, cell2->payload, cell2->payload_len));
 
-  tt_int_op(2, ==, cc1->n_certs);
-  tt_int_op(2, ==, cc2->n_certs);
+  if (with_ed) {
+    tt_int_op(5, ==, cc1->n_certs);
+    tt_int_op(5, ==, cc2->n_certs);
+  } else {
+    tt_int_op(2, ==, cc1->n_certs);
+    tt_int_op(2, ==, cc2->n_certs);
+  }
 
   tt_int_op(certs_cell_get_certs(cc1, 0)->cert_type, ==,
             CERTTYPE_RSA1024_ID_AUTH);
@@ -134,6 +178,22 @@ test_link_handshake_certs_ok(void *arg)
   tt_int_op(certs_cell_get_certs(cc2, 1)->cert_type, ==,
             CERTTYPE_RSA1024_ID_ID);
 
+  if (with_ed) {
+    tt_int_op(certs_cell_get_certs(cc1, 2)->cert_type, ==,
+              CERTTYPE_ED_ID_SIGN);
+    tt_int_op(certs_cell_get_certs(cc1, 3)->cert_type, ==,
+              CERTTYPE_ED_SIGN_AUTH);
+    tt_int_op(certs_cell_get_certs(cc1, 4)->cert_type, ==,
+              CERTTYPE_RSA1024_ID_EDID);
+
+    tt_int_op(certs_cell_get_certs(cc2, 2)->cert_type, ==,
+              CERTTYPE_ED_ID_SIGN);
+    tt_int_op(certs_cell_get_certs(cc2, 3)->cert_type, ==,
+              CERTTYPE_ED_SIGN_LINK);
+    tt_int_op(certs_cell_get_certs(cc2, 4)->cert_type, ==,
+              CERTTYPE_RSA1024_ID_EDID);
+  }
+
   chan1 = tor_malloc_zero(sizeof(*chan1));
   channel_tls_common_init(chan1);
   c1->chan = chan1;
@@ -144,13 +204,38 @@ test_link_handshake_certs_ok(void *arg)
   c1->base_.conn_array_index = -1;
   crypto_pk_get_digest(key2, c1->identity_digest);
 
+  if (with_ed) {
+    const tor_x509_cert_t *linkc, *idc;
+    tor_tls_get_my_certs(1, &linkc, &idc);
+    mock_peer_cert_expect_tortls = c1->tls; /* We should see this tls... */
+    mock_peer_cert = tor_x509_cert_dup(linkc); /* and when we do, the peer's
+                                                *  cert is this... */
+  }
   channel_tls_process_certs_cell(cell2, chan1);
+  mock_peer_cert_expect_tortls = NULL;
+  mock_peer_cert = NULL;
+
+  tor_assert(c1->handshake_state->authenticated);
 
   tt_assert(c1->handshake_state->received_certs_cell);
-  tt_assert(c1->handshake_state->auth_cert == NULL);
-  tt_assert(c1->handshake_state->id_cert);
+  tt_assert(c1->handshake_state->certs->auth_cert == NULL);
+  tt_assert(c1->handshake_state->certs->ed_sign_auth == NULL);
+  tt_assert(c1->handshake_state->certs->id_cert);
+  if (with_ed) {
+    tt_assert(c1->handshake_state->certs->ed_sign_link);
+    tt_assert(c1->handshake_state->certs->ed_rsa_crosscert);
+    tt_assert(c1->handshake_state->certs->ed_id_sign);
+    tt_assert(c1->handshake_state->authenticated_rsa);
+    tt_assert(c1->handshake_state->authenticated_ed25519);
+  } else {
+    tt_assert(c1->handshake_state->certs->ed_sign_link == NULL);
+    tt_assert(c1->handshake_state->certs->ed_rsa_crosscert == NULL);
+    tt_assert(c1->handshake_state->certs->ed_id_sign == NULL);
+    tt_assert(c1->handshake_state->authenticated_rsa);
+    tt_assert(! c1->handshake_state->authenticated_ed25519);
+  }
   tt_assert(! tor_mem_is_zero(
-                  (char*)c1->handshake_state->authenticated_peer_id, 20));
+                (char*)c1->handshake_state->authenticated_rsa_peer_id, 20));
 
   chan2 = tor_malloc_zero(sizeof(*chan2));
   channel_tls_common_init(chan2);
@@ -165,15 +250,30 @@ test_link_handshake_certs_ok(void *arg)
   channel_tls_process_certs_cell(cell1, chan2);
 
   tt_assert(c2->handshake_state->received_certs_cell);
-  tt_assert(c2->handshake_state->auth_cert);
-  tt_assert(c2->handshake_state->id_cert);
+  if (with_ed) {
+    tt_assert(c2->handshake_state->certs->ed_sign_auth);
+    tt_assert(c2->handshake_state->certs->ed_rsa_crosscert);
+    tt_assert(c2->handshake_state->certs->ed_id_sign);
+  } else {
+    tt_assert(c2->handshake_state->certs->auth_cert);
+    tt_assert(c2->handshake_state->certs->ed_sign_auth == NULL);
+    tt_assert(c2->handshake_state->certs->ed_rsa_crosscert == NULL);
+    tt_assert(c2->handshake_state->certs->ed_id_sign == NULL);
+  }
+  tt_assert(c2->handshake_state->certs->id_cert);
   tt_assert(tor_mem_is_zero(
-                (char*)c2->handshake_state->authenticated_peer_id, 20));
+              (char*)c2->handshake_state->authenticated_rsa_peer_id, 20));
+  /* no authentication has happened yet, since we haen't gotten an AUTH cell.
+   */
+  tt_assert(! c2->handshake_state->authenticated);
+  tt_assert(! c2->handshake_state->authenticated_rsa);
+  tt_assert(! c2->handshake_state->authenticated_ed25519);
 
  done:
   UNMOCK(tor_tls_cert_matches_key);
   UNMOCK(connection_or_write_var_cell_to_buf);
   UNMOCK(connection_or_send_netinfo);
+  UNMOCK(tor_tls_get_peer_cert);
   memset(c1->identity_digest, 0, sizeof(c1->identity_digest));
   memset(c2->identity_digest, 0, sizeof(c2->identity_digest));
   connection_free_(TO_CONN(c1));
@@ -193,6 +293,8 @@ test_link_handshake_certs_ok(void *arg)
 }
 
 typedef struct certs_data_s {
+  int is_ed;
+  int is_link_cert;
   or_connection_t *c;
   channel_tls_t *chan;
   certs_cell_t *ccell;
@@ -208,6 +310,7 @@ recv_certs_cleanup(const struct testcase_t *test, void *obj)
   UNMOCK(tor_tls_cert_matches_key);
   UNMOCK(connection_or_send_netinfo);
   UNMOCK(connection_or_close_for_error);
+  UNMOCK(tor_tls_get_peer_cert);
 
   if (d) {
     tor_free(d->cell);
@@ -220,6 +323,7 @@ recv_certs_cleanup(const struct testcase_t *test, void *obj)
     crypto_pk_free(d->key2);
     tor_free(d);
   }
+  routerkeys_free_all();
   return 1;
 }
 
@@ -231,6 +335,12 @@ recv_certs_setup(const struct testcase_t *test)
   certs_cell_cert_t *ccc1 = NULL;
   certs_cell_cert_t *ccc2 = NULL;
   ssize_t n;
+  int is_ed = d->is_ed = !strcmpstart(test->setup_data, "Ed25519");
+  int is_rsa = !strcmpstart(test->setup_data, "RSA");
+  int is_link = d->is_link_cert = !strcmpend(test->setup_data, "-Link");
+  int is_auth = !strcmpend(test->setup_data, "-Auth");
+  tor_assert(is_ed != is_rsa);
+  tor_assert(is_link != is_auth);
 
   d->c = or_connection_new(CONN_TYPE_OR, AF_INET);
   d->chan = tor_malloc_zero(sizeof(*d->chan));
@@ -246,19 +356,25 @@ recv_certs_setup(const struct testcase_t *test)
 
   tt_int_op(tor_tls_context_init(TOR_TLS_CTX_IS_PUBLIC_SERVER,
                                  d->key1, d->key2, 86400), ==, 0);
+  if (is_ed) {
+    init_mock_ed_keys(d->key2);
+  } else {
+    routerkeys_free_all();
+  }
+
   d->ccell = certs_cell_new();
   ccc1 = certs_cell_cert_new();
   certs_cell_add_certs(d->ccell, ccc1);
   ccc2 = certs_cell_cert_new();
   certs_cell_add_certs(d->ccell, ccc2);
   d->ccell->n_certs = 2;
-  ccc1->cert_type = 1;
+  ccc1->cert_type = is_link ? 1 : 3;
   ccc2->cert_type = 2;
 
   const tor_x509_cert_t *a,*b;
   const uint8_t *enca, *encb;
   size_t lena, lenb;
-  tor_tls_get_my_certs(1, &a, &b);
+  tor_tls_get_my_certs(is_link ? 1 : 0, &a, &b);
   tor_x509_cert_get_der(a, &enca, &lena);
   tor_x509_cert_get_der(b, &encb, &lenb);
   certs_cell_cert_setlen_body(ccc1, lena);
@@ -269,6 +385,41 @@ recv_certs_setup(const struct testcase_t *test)
   memcpy(certs_cell_cert_getarray_body(ccc1), enca, lena);
   memcpy(certs_cell_cert_getarray_body(ccc2), encb, lenb);
 
+  if (is_ed) {
+    certs_cell_cert_t *ccc3 = NULL; /* Id->Sign */
+    certs_cell_cert_t *ccc4 = NULL; /* Sign->Link or Sign->Auth. */
+    certs_cell_cert_t *ccc5 = NULL; /* RSAId->Ed Id. */
+    const tor_cert_t *id_sign = get_master_signing_key_cert();
+    const tor_cert_t *secondary =
+      is_link ? get_current_link_cert_cert() : get_current_auth_key_cert();
+    const uint8_t *cc = NULL;
+    size_t cc_sz;
+    get_master_rsa_crosscert(&cc, &cc_sz);
+
+    ccc3 = certs_cell_cert_new();
+    ccc4 = certs_cell_cert_new();
+    ccc5 = certs_cell_cert_new();
+    certs_cell_add_certs(d->ccell, ccc3);
+    certs_cell_add_certs(d->ccell, ccc4);
+    certs_cell_add_certs(d->ccell, ccc5);
+    ccc3->cert_len = id_sign->encoded_len;
+    ccc4->cert_len = secondary->encoded_len;
+    ccc5->cert_len = cc_sz;
+    certs_cell_cert_setlen_body(ccc3, ccc3->cert_len);
+    certs_cell_cert_setlen_body(ccc4, ccc4->cert_len);
+    certs_cell_cert_setlen_body(ccc5, ccc5->cert_len);
+    memcpy(certs_cell_cert_getarray_body(ccc3), id_sign->encoded,
+           ccc3->cert_len);
+    memcpy(certs_cell_cert_getarray_body(ccc4), secondary->encoded,
+           ccc4->cert_len);
+    memcpy(certs_cell_cert_getarray_body(ccc5), cc, ccc5->cert_len);
+    ccc3->cert_type = 4;
+    ccc4->cert_type = is_link ? 5 : 6;
+    ccc5->cert_type = 7;
+
+    d->ccell->n_certs = 5;
+  }
+
   d->cell = var_cell_new(4096);
   d->cell->command = CELL_CERTS;
 
@@ -279,6 +430,12 @@ recv_certs_setup(const struct testcase_t *test)
   MOCK(tor_tls_cert_matches_key, mock_tls_cert_matches_key);
   MOCK(connection_or_send_netinfo, mock_send_netinfo);
   MOCK(connection_or_close_for_error, mock_close_for_err);
+  MOCK(tor_tls_get_peer_cert, mock_get_peer_cert);
+
+  if (is_link) {
+    /* Say that this is the peer's certificate */
+    mock_peer_cert = tor_x509_cert_dup(a);
+  }
 
   tt_int_op(0, ==, d->c->handshake_state->received_certs_cell);
   tt_int_op(0, ==, mock_send_authenticate_called);
@@ -302,9 +459,24 @@ test_link_handshake_recv_certs_ok(void *arg)
   channel_tls_process_certs_cell(d->cell, d->chan);
   tt_int_op(0, ==, mock_close_called);
   tt_int_op(d->c->handshake_state->authenticated, ==, 1);
+  tt_int_op(d->c->handshake_state->authenticated_rsa, ==, 1);
   tt_int_op(d->c->handshake_state->received_certs_cell, ==, 1);
-  tt_assert(d->c->handshake_state->id_cert != NULL);
-  tt_assert(d->c->handshake_state->auth_cert == NULL);
+  tt_assert(d->c->handshake_state->certs->id_cert != NULL);
+  tt_assert(d->c->handshake_state->certs->auth_cert == NULL);
+
+  if (d->is_ed) {
+    tt_assert(d->c->handshake_state->certs->ed_id_sign != NULL);
+    tt_assert(d->c->handshake_state->certs->ed_sign_link != NULL);
+    tt_assert(d->c->handshake_state->certs->ed_sign_auth == NULL);
+    tt_assert(d->c->handshake_state->certs->ed_rsa_crosscert != NULL);
+    tt_int_op(d->c->handshake_state->authenticated_ed25519, ==, 1);
+  } else {
+    tt_assert(d->c->handshake_state->certs->ed_id_sign == NULL);
+    tt_assert(d->c->handshake_state->certs->ed_sign_link == NULL);
+    tt_assert(d->c->handshake_state->certs->ed_sign_auth == NULL);
+    tt_assert(d->c->handshake_state->certs->ed_rsa_crosscert == NULL);
+    tt_int_op(d->c->handshake_state->authenticated_ed25519, ==, 0);
+  }
 
  done:
   ;
@@ -315,17 +487,20 @@ test_link_handshake_recv_certs_ok_server(void *arg)
 {
   certs_data_t *d = arg;
   d->c->handshake_state->started_here = 0;
-  certs_cell_get_certs(d->ccell, 0)->cert_type = 3;
-  certs_cell_get_certs(d->ccell, 1)->cert_type = 2;
-  ssize_t n = certs_cell_encode(d->cell->payload, 2048, d->ccell);
-  tt_int_op(n, >, 0);
-  d->cell->payload_len = n;
+  d->c->handshake_state->certs->started_here = 0;
   channel_tls_process_certs_cell(d->cell, d->chan);
   tt_int_op(0, ==, mock_close_called);
   tt_int_op(d->c->handshake_state->authenticated, ==, 0);
   tt_int_op(d->c->handshake_state->received_certs_cell, ==, 1);
-  tt_assert(d->c->handshake_state->id_cert != NULL);
-  tt_assert(d->c->handshake_state->auth_cert != NULL);
+  tt_assert(d->c->handshake_state->certs->id_cert != NULL);
+  tt_assert(d->c->handshake_state->certs->link_cert == NULL);
+  if (d->is_ed) {
+    tt_assert(d->c->handshake_state->certs->ed_sign_auth != NULL);
+    tt_assert(d->c->handshake_state->certs->auth_cert == NULL);
+  } else {
+    tt_assert(d->c->handshake_state->certs->ed_sign_auth == NULL);
+    tt_assert(d->c->handshake_state->certs->auth_cert != NULL);
+  }
 
  done:
   ;
@@ -343,6 +518,8 @@ test_link_handshake_recv_certs_ok_server(void *arg)
     tt_int_op(1, ==, mock_close_called);                                \
     tt_int_op(0, ==, mock_send_authenticate_called);                    \
     tt_int_op(0, ==, mock_send_netinfo_called);                         \
+    tt_int_op(0, ==, d->c->handshake_state->authenticated_rsa);         \
+    tt_int_op(0, ==, d->c->handshake_state->authenticated_ed25519);     \
     if (require_failure_message) {                                      \
       expect_log_msg_containing(require_failure_message);               \
     }                                                                   \
@@ -383,12 +560,41 @@ CERTS_FAIL(truncated_3,
              d->cell->payload_len = 7;
              memcpy(d->cell->payload, "\x01\x01\x00\x05""abc", 7);
            })
+CERTS_FAIL(truncated_4, /* ed25519 */
+           {
+             require_failure_message = "It couldn't be parsed";
+             d->cell->payload_len -= 10;
+           })
+CERTS_FAIL(truncated_5, /* ed25519 */
+           {
+             require_failure_message = "It couldn't be parsed";
+             d->cell->payload_len -= 100;
+           })
+
 #define REENCODE() do {                                                 \
+    const char *msg = certs_cell_check(d->ccell);                       \
+    if (msg) puts(msg);                                                 \
     ssize_t n = certs_cell_encode(d->cell->payload, 4096, d->ccell);    \
     tt_int_op(n, >, 0);                                                 \
     d->cell->payload_len = n;                                           \
   } while (0)
 
+CERTS_FAIL(truncated_6, /* ed25519 */
+   {
+     /* truncate the link certificate */
+     require_failure_message = "undecodable Ed certificate";
+     certs_cell_cert_setlen_body(certs_cell_get_certs(d->ccell, 3), 7);
+     certs_cell_get_certs(d->ccell, 3)->cert_len = 7;
+     REENCODE();
+   })
+CERTS_FAIL(truncated_7, /* ed25519 */
+   {
+     /* truncate the crosscert */
+     require_failure_message = "Unparseable or overlong crosscert";
+     certs_cell_cert_setlen_body(certs_cell_get_certs(d->ccell, 4), 7);
+     certs_cell_get_certs(d->ccell, 4)->cert_len = 7;
+     REENCODE();
+   })
 CERTS_FAIL(not_x509,
   {
     require_failure_message = "Received undecodable certificate";
@@ -417,6 +623,206 @@ CERTS_FAIL(both_auth,
     certs_cell_get_certs(d->ccell, 1)->cert_type = 3;
     REENCODE();
   })
+CERTS_FAIL(duplicate_id, /* ed25519 */
+  {
+    require_failure_message = "Duplicate Ed25519 certificate";
+    certs_cell_get_certs(d->ccell, 2)->cert_type = 4;
+    certs_cell_get_certs(d->ccell, 3)->cert_type = 4;
+    REENCODE();
+  })
+CERTS_FAIL(duplicate_link, /* ed25519 */
+  {
+    require_failure_message = "Duplicate Ed25519 certificate";
+    certs_cell_get_certs(d->ccell, 2)->cert_type = 5;
+    certs_cell_get_certs(d->ccell, 3)->cert_type = 5;
+    REENCODE();
+  })
+CERTS_FAIL(duplicate_crosscert, /* ed25519 */
+  {
+    require_failure_message = "Duplicate RSA->Ed25519 crosscert";
+    certs_cell_get_certs(d->ccell, 2)->cert_type = 7;
+    certs_cell_get_certs(d->ccell, 3)->cert_type = 7;
+    REENCODE();
+  })
+static void
+test_link_handshake_recv_certs_missing_id(void *arg) /* ed25519 */
+{
+  certs_data_t *d = arg;
+  tt_int_op(certs_cell_getlen_certs(d->ccell), OP_EQ, 5);
+  certs_cell_set_certs(d->ccell, 2, certs_cell_get_certs(d->ccell, 4));
+  certs_cell_set0_certs(d->ccell, 4, NULL); /* prevent free */
+  certs_cell_setlen_certs(d->ccell, 4);
+  d->ccell->n_certs = 4;
+  REENCODE();
+
+  /* This handshake succeeds, but since we have no ID cert, we will
+   * just do the RSA handshake. */
+  channel_tls_process_certs_cell(d->cell, d->chan);
+  tt_int_op(0, ==, mock_close_called);
+  tt_int_op(0, ==, d->c->handshake_state->authenticated_ed25519);
+  tt_int_op(1, ==, d->c->handshake_state->authenticated_rsa);
+ done:
+  ;
+}
+CERTS_FAIL(missing_signing_key, /* ed25519 */
+  {
+    require_failure_message = "No Ed25519 signing key";
+    tt_int_op(certs_cell_getlen_certs(d->ccell), OP_EQ, 5);
+    certs_cell_cert_t *cert = certs_cell_get_certs(d->ccell, 2);
+    tt_int_op(cert->cert_type, ==, CERTTYPE_ED_ID_SIGN);
+    /* replace this with a valid master->signing cert, but with no
+     * signing key. */
+    const ed25519_keypair_t *mk = get_master_identity_keypair();
+    const ed25519_keypair_t *sk = get_master_signing_keypair();
+    tor_cert_t *bad_cert = tor_cert_create(mk, CERT_TYPE_ID_SIGNING,
+                                           &sk->pubkey, time(NULL), 86400,
+                                           0 /* don't include signer */);
+    certs_cell_cert_setlen_body(cert, bad_cert->encoded_len);
+    memcpy(certs_cell_cert_getarray_body(cert),
+           bad_cert->encoded, bad_cert->encoded_len);
+    cert->cert_len = bad_cert->encoded_len;
+    tor_cert_free(bad_cert);
+    REENCODE();
+  })
+CERTS_FAIL(missing_link, /* ed25519 */
+  {
+    require_failure_message = "No Ed25519 link key";
+    tt_int_op(certs_cell_getlen_certs(d->ccell), OP_EQ, 5);
+    certs_cell_set_certs(d->ccell, 3, certs_cell_get_certs(d->ccell, 4));
+    certs_cell_set0_certs(d->ccell, 4, NULL); /* prevent free */
+    certs_cell_setlen_certs(d->ccell, 4);
+    d->ccell->n_certs = 4;
+    REENCODE();
+  })
+CERTS_FAIL(missing_auth, /* ed25519 */
+  {
+    d->c->handshake_state->started_here = 0;
+    d->c->handshake_state->certs->started_here = 0;
+    require_failure_message = "No Ed25519 link authentication key";
+    tt_int_op(certs_cell_getlen_certs(d->ccell), OP_EQ, 5);
+    certs_cell_set_certs(d->ccell, 3, certs_cell_get_certs(d->ccell, 4));
+    certs_cell_set0_certs(d->ccell, 4, NULL); /* prevent free */
+    certs_cell_setlen_certs(d->ccell, 4);
+    d->ccell->n_certs = 4;
+    REENCODE();
+  })
+CERTS_FAIL(missing_crosscert, /* ed25519 */
+  {
+    require_failure_message = "Missing RSA->Ed25519 crosscert";
+    tt_int_op(certs_cell_getlen_certs(d->ccell), OP_EQ, 5);
+    certs_cell_setlen_certs(d->ccell, 4);
+    d->ccell->n_certs = 4;
+    REENCODE();
+  })
+CERTS_FAIL(missing_rsa_id, /* ed25519 */
+  {
+    require_failure_message = "Missing legacy RSA ID cert";
+    tt_int_op(certs_cell_getlen_certs(d->ccell), OP_EQ, 5);
+    certs_cell_set_certs(d->ccell, 1, certs_cell_get_certs(d->ccell, 4));
+    certs_cell_set0_certs(d->ccell, 4, NULL); /* prevent free */
+    certs_cell_setlen_certs(d->ccell, 4);
+    d->ccell->n_certs = 4;
+    REENCODE();
+  })
+CERTS_FAIL(link_mismatch, /* ed25519 */
+  {
+    require_failure_message = "Link certificate does not match "
+      "TLS certificate";
+    const tor_x509_cert_t *idc;
+    tor_tls_get_my_certs(1, NULL, &idc);
+    tor_x509_cert_free(mock_peer_cert);
+    /* Pretend that the peer cert was something else. */
+    mock_peer_cert = tor_x509_cert_dup(idc);
+    /* No reencode needed. */
+  })
+CERTS_FAIL(bad_ed_sig, /* ed25519 */
+  {
+    require_failure_message = "At least one Ed25519 certificate was "
+      "badly signed";
+    certs_cell_cert_t *cert = certs_cell_get_certs(d->ccell, 3);
+    uint8_t *body = certs_cell_cert_getarray_body(cert);
+    ssize_t body_len = certs_cell_cert_getlen_body(cert);
+    /* Frob a byte in the signature */
+    body[body_len - 13] ^= 7;
+    REENCODE();
+  })
+CERTS_FAIL(bad_crosscert, /*ed25519*/
+  {
+    require_failure_message = "Invalid RSA->Ed25519 crosscert";
+    certs_cell_cert_t *cert = certs_cell_get_certs(d->ccell, 4);
+    uint8_t *body = certs_cell_cert_getarray_body(cert);
+    ssize_t body_len = certs_cell_cert_getlen_body(cert);
+    /* Frob a byte in the signature */
+    body[body_len - 13] ^= 7;
+    REENCODE();
+  })
+CERTS_FAIL(bad_rsa_id_cert, /*ed25519*/
+  {
+    require_failure_message = "legacy RSA ID certificate was not valid";
+    certs_cell_cert_t *cert = certs_cell_get_certs(d->ccell, 1);
+    uint8_t *body = certs_cell_cert_getarray_body(cert);
+    ssize_t body_len = certs_cell_cert_getlen_body(cert);
+    /* Frob a byte in the signature */
+    body[body_len - 13] ^= 7;
+    REENCODE();
+  })
+CERTS_FAIL(expired_rsa_id, /* both */
+  {
+    require_failure_message = "Certificate already expired";
+    /* we're going to replace the identity cert with an expired one. */
+    certs_cell_cert_t *cert = certs_cell_get_certs(d->ccell, 1);
+    const tor_x509_cert_t *idc;
+    tor_tls_get_my_certs(1, NULL, &idc);
+    X509 *newc = X509_dup(idc->cert);
+    time_t new_end = time(NULL) - 86400 * 10;
+    X509_time_adj(X509_get_notAfter(newc), 0, &new_end);
+    EVP_PKEY *pk = crypto_pk_get_evp_pkey_(d->key2, 1);
+    tt_assert(X509_sign(newc, pk, EVP_sha1()));
+    int len = i2d_X509(newc, NULL);
+    certs_cell_cert_setlen_body(cert, len);
+    uint8_t *body = certs_cell_cert_getarray_body(cert);
+    int len2 = i2d_X509(newc, &body);
+    tt_int_op(len, ==, len2);
+    REENCODE();
+    X509_free(newc);
+    EVP_PKEY_free(pk);
+  })
+CERTS_FAIL(expired_ed_id, /* ed25519 */
+  {
+    /* we're going to replace the Ed Id->sign cert with an expired one. */
+    require_failure_message = "At least one certificate expired";
+    /* We don't need to re-sign, since we check for expiration first. */
+    certs_cell_cert_t *cert = certs_cell_get_certs(d->ccell, 2);
+    uint8_t *body = certs_cell_cert_getarray_body(cert);
+    /* The expiration field is bytes [2..5].  It is in HOURS since the
+     * epoch. */
+    set_uint32(body+2, htonl(24)); /* Back to jan 2, 1970. */
+    REENCODE();
+  })
+CERTS_FAIL(expired_ed_link, /* ed25519 */
+  {
+    /* we're going to replace the Ed Sign->link cert with an expired one. */
+    require_failure_message = "At least one certificate expired";
+    /* We don't need to re-sign, since we check for expiration first. */
+    certs_cell_cert_t *cert = certs_cell_get_certs(d->ccell, 3);
+    uint8_t *body = certs_cell_cert_getarray_body(cert);
+    /* The expiration field is bytes [2..5].  It is in HOURS since the
+     * epoch. */
+    set_uint32(body+2, htonl(24)); /* Back to jan 2, 1970. */
+    REENCODE();
+  })
+CERTS_FAIL(expired_crosscert, /* ed25519 */
+  {
+    /* we're going to replace the Ed Sign->link cert with an expired one. */
+    require_failure_message = "Crosscert is expired";
+    /* We don't need to re-sign, since we check for expiration first. */
+    certs_cell_cert_t *cert = certs_cell_get_certs(d->ccell, 4);
+    uint8_t *body = certs_cell_cert_getarray_body(cert);
+    /* The expiration field is bytes [32..35]. once again, HOURS. */
+    set_uint32(body+32, htonl(24)); /* Back to jan 2, 1970. */
+    REENCODE();
+  })
+
 CERTS_FAIL(wrong_labels_1,
   {
     require_failure_message = "The link certificate was not valid";
@@ -441,26 +847,32 @@ CERTS_FAIL(wrong_labels_2,
   })
 CERTS_FAIL(wrong_labels_3,
            {
-             require_failure_message = "The certs we wanted were missing";
+             require_failure_message =
+               "The certs we wanted (ID, Link) were missing";
              certs_cell_get_certs(d->ccell, 0)->cert_type = 2;
              certs_cell_get_certs(d->ccell, 1)->cert_type = 3;
              REENCODE();
            })
 CERTS_FAIL(server_missing_certs,
            {
-             require_failure_message = "The certs we wanted were missing";
+             require_failure_message =
+               "The certs we wanted (ID, Auth) were missing";
              d->c->handshake_state->started_here = 0;
+             d->c->handshake_state->certs->started_here = 0;
+
            })
 CERTS_FAIL(server_wrong_labels_1,
            {
              require_failure_message =
                "The authentication certificate was not valid";
              d->c->handshake_state->started_here = 0;
+             d->c->handshake_state->certs->started_here = 0;
              certs_cell_get_certs(d->ccell, 0)->cert_type = 2;
              certs_cell_get_certs(d->ccell, 1)->cert_type = 3;
              REENCODE();
            })
 
+
 static void
 test_link_handshake_send_authchallenge(void *arg)
 {
@@ -478,15 +890,15 @@ test_link_handshake_send_authchallenge(void *arg)
   cell1 = mock_got_var_cell;
   tt_int_op(0, ==, connection_or_send_auth_challenge_cell(c1));
   cell2 = mock_got_var_cell;
-  tt_int_op(36, ==, cell1->payload_len);
-  tt_int_op(36, ==, cell2->payload_len);
+  tt_int_op(38, ==, cell1->payload_len);
+  tt_int_op(38, ==, cell2->payload_len);
   tt_int_op(0, ==, cell1->circ_id);
   tt_int_op(0, ==, cell2->circ_id);
   tt_int_op(CELL_AUTH_CHALLENGE, ==, cell1->command);
   tt_int_op(CELL_AUTH_CHALLENGE, ==, cell2->command);
 
-  tt_mem_op("\x00\x01\x00\x01", ==, cell1->payload + 32, 4);
-  tt_mem_op("\x00\x01\x00\x01", ==, cell2->payload + 32, 4);
+  tt_mem_op("\x00\x02\x00\x01\x00\x03", ==, cell1->payload + 32, 6);
+  tt_mem_op("\x00\x02\x00\x01\x00\x03", ==, cell2->payload + 32, 6);
   tt_mem_op(cell1->payload, !=, cell2->payload, 32);
 
  done:
@@ -538,9 +950,9 @@ recv_authchallenge_setup(const struct testcase_t *test)
   d->c->handshake_state->received_certs_cell = 1;
   d->cell = var_cell_new(128);
   d->cell->payload_len = 38;
-  d->cell->payload[33] = 2;
-  d->cell->payload[35] = 7;
-  d->cell->payload[37] = 1;
+  d->cell->payload[33] = 2; /* 2 methods */
+  d->cell->payload[35] = 7; /* This one isn't real */
+  d->cell->payload[37] = 1; /* This is the old RSA one. */
   d->cell->command = CELL_AUTH_CHALLENGE;
 
   get_options_mutable()->ORPort_set = 1;
@@ -548,7 +960,6 @@ recv_authchallenge_setup(const struct testcase_t *test)
   MOCK(connection_or_close_for_error, mock_close_for_err);
   MOCK(connection_or_send_netinfo, mock_send_netinfo);
   MOCK(connection_or_send_authenticate_cell, mock_send_authenticate);
-
   tt_int_op(0, ==, d->c->handshake_state->received_auth_challenge);
   tt_int_op(0, ==, mock_send_authenticate_called);
   tt_int_op(0, ==, mock_send_netinfo_called);
@@ -574,6 +985,26 @@ test_link_handshake_recv_authchallenge_ok(void *arg)
   tt_int_op(1, ==, d->c->handshake_state->received_auth_challenge);
   tt_int_op(1, ==, mock_send_authenticate_called);
   tt_int_op(1, ==, mock_send_netinfo_called);
+  tt_int_op(1, ==, mock_send_authenticate_called_with_type); /* RSA */
+ done:
+  ;
+}
+
+static void
+test_link_handshake_recv_authchallenge_ok_ed25519(void *arg)
+{
+  authchallenge_data_t *d = arg;
+
+  /* Add the ed25519 authentication mechanism here. */
+  d->cell->payload[33] = 3; /* 3 types are supported now. */
+  d->cell->payload[39] = 3;
+  d->cell->payload_len += 2;
+  channel_tls_process_auth_challenge_cell(d->cell, d->chan);
+  tt_int_op(0, ==, mock_close_called);
+  tt_int_op(1, ==, d->c->handshake_state->received_auth_challenge);
+  tt_int_op(1, ==, mock_send_authenticate_called);
+  tt_int_op(1, ==, mock_send_netinfo_called);
+  tt_int_op(3, ==, mock_send_authenticate_called_with_type); /* Ed25519 */
  done:
   ;
 }
@@ -637,7 +1068,8 @@ AUTHCHALLENGE_FAIL(badproto,
 AUTHCHALLENGE_FAIL(as_server,
                    require_failure_message = "We didn't originate this "
                      "connection";
-                   d->c->handshake_state->started_here = 0;)
+                   d->c->handshake_state->started_here = 0;
+                   d->c->handshake_state->certs->started_here = 0;)
 AUTHCHALLENGE_FAIL(duplicate,
                    require_failure_message = "We already received one";
                    d->c->handshake_state->received_auth_challenge = 1)
@@ -655,13 +1087,6 @@ AUTHCHALLENGE_FAIL(nonzero_circid,
                    require_failure_message = "It had a nonzero circuit ID";
                    d->cell->circ_id = 1337)
 
-static tor_x509_cert_t *mock_peer_cert = NULL;
-static tor_x509_cert_t *
-mock_get_peer_cert(tor_tls_t *tls)
-{
-  (void)tls;
-  return mock_peer_cert;
-}
 
 static int
 mock_get_tlssecrets(tor_tls_t *tls, uint8_t *secrets_out)
@@ -682,6 +1107,7 @@ mock_set_circid_type(channel_t *chan,
 }
 
 typedef struct authenticate_data_s {
+  int is_ed;
   or_connection_t *c1, *c2;
   channel_tls_t *chan2;
   var_cell_t *cell;
@@ -697,6 +1123,7 @@ authenticate_data_cleanup(const struct testcase_t *test, void *arg)
   UNMOCK(tor_tls_get_tlssecrets);
   UNMOCK(connection_or_close_for_error);
   UNMOCK(channel_set_circid_type);
+  UNMOCK(tor_tls_export_key_material);
   authenticate_data_t *d = arg;
   if (d) {
     tor_free(d->cell);
@@ -711,7 +1138,6 @@ authenticate_data_cleanup(const struct testcase_t *test, void *arg)
     tor_free(d);
   }
   mock_peer_cert = NULL;
-
   return 1;
 }
 
@@ -719,6 +1145,7 @@ static void *
 authenticate_data_setup(const struct testcase_t *test)
 {
   authenticate_data_t *d = tor_malloc_zero(sizeof(*d));
+  int is_ed = d->is_ed = (test->setup_data == (void*)3);
 
   scheduler_init();
 
@@ -727,6 +1154,7 @@ authenticate_data_setup(const struct testcase_t *test)
   MOCK(tor_tls_get_tlssecrets, mock_get_tlssecrets);
   MOCK(connection_or_close_for_error, mock_close_for_err);
   MOCK(channel_set_circid_type, mock_set_circid_type);
+  MOCK(tor_tls_export_key_material, mock_export_key_material);
   d->c1 = or_connection_new(CONN_TYPE_OR, AF_INET);
   d->c2 = or_connection_new(CONN_TYPE_OR, AF_INET);
   tor_addr_from_ipv4h(&d->c1->base_.addr, 0x01020304);
@@ -737,6 +1165,8 @@ authenticate_data_setup(const struct testcase_t *test)
   tt_int_op(tor_tls_context_init(TOR_TLS_CTX_IS_PUBLIC_SERVER,
                                  d->key1, d->key2, 86400), ==, 0);
 
+  init_mock_ed_keys(d->key2);
+
   d->c1->base_.state = OR_CONN_STATE_OR_HANDSHAKING_V3;
   d->c1->link_proto = 3;
   tt_int_op(connection_init_or_handshake_state(d->c1, 1), ==, 0);
@@ -767,19 +1197,34 @@ authenticate_data_setup(const struct testcase_t *test)
   const uint8_t *der;
   size_t sz;
   tor_x509_cert_get_der(id_cert, &der, &sz);
-  d->c1->handshake_state->id_cert = tor_x509_cert_decode(der, sz);
-  d->c2->handshake_state->id_cert = tor_x509_cert_decode(der, sz);
+  d->c1->handshake_state->certs->id_cert = tor_x509_cert_decode(der, sz);
+  d->c2->handshake_state->certs->id_cert = tor_x509_cert_decode(der, sz);
+
+  if (is_ed) {
+    d->c1->handshake_state->certs->ed_id_sign =
+      tor_cert_dup(get_master_signing_key_cert());
+    d->c2->handshake_state->certs->ed_id_sign =
+      tor_cert_dup(get_master_signing_key_cert());
+    d->c2->handshake_state->certs->ed_sign_auth =
+      tor_cert_dup(get_current_auth_key_cert());
+  } else {
+    tt_assert(! tor_tls_get_my_certs(0, &auth_cert, &id_cert));
+    tor_x509_cert_get_der(auth_cert, &der, &sz);
+    d->c2->handshake_state->certs->auth_cert = tor_x509_cert_decode(der, sz);
+  }
 
   tor_x509_cert_get_der(link_cert, &der, &sz);
   mock_peer_cert = tor_x509_cert_decode(der, sz);
   tt_assert(mock_peer_cert);
-  tt_assert(! tor_tls_get_my_certs(0, &auth_cert, &id_cert));
-  tor_x509_cert_get_der(auth_cert, &der, &sz);
-  d->c2->handshake_state->auth_cert = tor_x509_cert_decode(der, sz);
 
   /* Make an authenticate cell ... */
-  tt_int_op(0, ==, connection_or_send_authenticate_cell(d->c1,
-                                             AUTHTYPE_RSA_SHA256_TLSSECRET));
+  int authtype;
+  if (is_ed)
+    authtype = AUTHTYPE_ED25519_SHA256_RFC5705;
+  else
+    authtype = AUTHTYPE_RSA_SHA256_TLSSECRET;
+  tt_int_op(0, ==, connection_or_send_authenticate_cell(d->c1, authtype));
+
   tt_assert(mock_got_var_cell);
   d->cell = mock_got_var_cell;
   mock_got_var_cell = NULL;
@@ -805,42 +1250,63 @@ test_link_handshake_auth_cell(void *arg)
   /* Is the cell well-formed on the outer layer? */
   tt_int_op(d->cell->command, ==, CELL_AUTHENTICATE);
   tt_int_op(d->cell->payload[0], ==, 0);
-  tt_int_op(d->cell->payload[1], ==, 1);
+  if (d->is_ed)
+    tt_int_op(d->cell->payload[1], ==, 3);
+  else
+    tt_int_op(d->cell->payload[1], ==, 1);
   tt_int_op(ntohs(get_uint16(d->cell->payload + 2)), ==,
             d->cell->payload_len - 4);
 
   /* Check it out for plausibility... */
   auth_ctx_t ctx;
-  ctx.is_ed = 0;
+  ctx.is_ed = d->is_ed;
   tt_int_op(d->cell->payload_len-4, ==, auth1_parse(&auth1,
                                              d->cell->payload+4,
                                              d->cell->payload_len - 4, &ctx));
   tt_assert(auth1);
 
-  tt_mem_op(auth1->type, ==, "AUTH0001", 8);
+  if (d->is_ed) {
+    tt_mem_op(auth1->type, ==, "AUTH0003", 8);
+  } else {
+    tt_mem_op(auth1->type, ==, "AUTH0001", 8);
+  }
   tt_mem_op(auth1->tlssecrets, ==, "int getRandomNumber(){return 4;}", 32);
-  tt_int_op(auth1_getlen_sig(auth1), >, 120);
 
   /* Is the signature okay? */
-  uint8_t sig[128];
-  uint8_t digest[32];
-
-  auth_pubkey = tor_tls_cert_get_key(d->c2->handshake_state->auth_cert);
-  int n = crypto_pk_public_checksig(
+  const uint8_t *start = d->cell->payload+4, *end = auth1->end_of_signed;
+  if (d->is_ed) {
+    ed25519_signature_t sig;
+    tt_int_op(auth1_getlen_sig(auth1), ==, ED25519_SIG_LEN);
+    memcpy(&sig.sig, auth1_getarray_sig(auth1), ED25519_SIG_LEN);
+    tt_assert(!ed25519_checksig(&sig, start, end-start,
+                                &get_current_auth_keypair()->pubkey));
+  } else {
+    uint8_t sig[128];
+    uint8_t digest[32];
+    tt_int_op(auth1_getlen_sig(auth1), >, 120);
+    auth_pubkey = tor_tls_cert_get_key(d->c2->handshake_state->certs->auth_cert);
+    int n = crypto_pk_public_checksig(
               auth_pubkey,
               (char*)sig, sizeof(sig), (char*)auth1_getarray_sig(auth1),
               auth1_getlen_sig(auth1));
-  tt_int_op(n, ==, 32);
-  const uint8_t *start = d->cell->payload+4, *end = auth1->end_of_signed;
-  crypto_digest256((char*)digest,
-                   (const char*)start, end-start, DIGEST_SHA256);
-  tt_mem_op(sig, ==, digest, 32);
+    tt_int_op(n, ==, 32);
+    crypto_digest256((char*)digest,
+                     (const char*)start, end-start, DIGEST_SHA256);
+    tt_mem_op(sig, ==, digest, 32);
+  }
 
   /* Then feed it to c2. */
   tt_int_op(d->c2->handshake_state->authenticated, ==, 0);
   channel_tls_process_authenticate_cell(d->cell, d->chan2);
   tt_int_op(mock_close_called, ==, 0);
   tt_int_op(d->c2->handshake_state->authenticated, ==, 1);
+  if (d->is_ed) {
+    tt_int_op(d->c2->handshake_state->authenticated_ed25519, ==, 1);
+    tt_int_op(d->c2->handshake_state->authenticated_rsa, ==, 1);
+  } else {
+    tt_int_op(d->c2->handshake_state->authenticated_ed25519, ==, 0);
+    tt_int_op(d->c2->handshake_state->authenticated_rsa, ==, 1);
+  }
 
  done:
   auth1_free(auth1);
@@ -874,7 +1340,8 @@ AUTHENTICATE_FAIL(badproto,
                   d->c2->link_proto = 2)
 AUTHENTICATE_FAIL(atclient,
                   require_failure_message = "We originated this connection";
-                  d->c2->handshake_state->started_here = 1)
+                  d->c2->handshake_state->started_here = 1;
+                  d->c2->handshake_state->certs->started_here = 1;)
 AUTHENTICATE_FAIL(duplicate,
                   require_failure_message = "We already got one";
                   d->c2->handshake_state->received_authenticate = 1)
@@ -898,13 +1365,13 @@ AUTHENTICATE_FAIL(nocerts,
 AUTHENTICATE_FAIL(noidcert,
                   require_failure_message = "We never got an identity "
                     "certificate";
-                  tor_x509_cert_free(d->c2->handshake_state->id_cert);
-                  d->c2->handshake_state->id_cert = NULL)
+                  tor_x509_cert_free(d->c2->handshake_state->certs->id_cert);
+                  d->c2->handshake_state->certs->id_cert = NULL)
 AUTHENTICATE_FAIL(noauthcert,
-                  require_failure_message = "We never got an authentication "
-                    "certificate";
-                  tor_x509_cert_free(d->c2->handshake_state->auth_cert);
-                  d->c2->handshake_state->auth_cert = NULL)
+                  require_failure_message = "We never got an RSA "
+                    "authentication certificate";
+                  tor_x509_cert_free(d->c2->handshake_state->certs->auth_cert);
+                  d->c2->handshake_state->certs->auth_cert = NULL)
 AUTHENTICATE_FAIL(tooshort,
                   require_failure_message = "Cell was way too short";
                   d->cell->payload_len = 3)
@@ -928,11 +1395,33 @@ AUTHENTICATE_FAIL(badcontent,
                     "cell body was not as expected";
                   d->cell->payload[10] ^= 0xff)
 AUTHENTICATE_FAIL(badsig_1,
-                  require_failure_message = "Signature wasn't valid";
+                  if (d->is_ed)
+                    require_failure_message = "Ed25519 signature wasn't valid";
+                  else
+                    require_failure_message = "RSA signature wasn't valid";
                   d->cell->payload[d->cell->payload_len - 5] ^= 0xff)
-
-#define TEST(name, flags)                                       \
-  { #name , test_link_handshake_ ## name, (flags), NULL, NULL }
+AUTHENTICATE_FAIL(missing_ed_id,
+                {
+                  tor_cert_free(d->c2->handshake_state->certs->ed_id_sign);
+                  d->c2->handshake_state->certs->ed_id_sign = NULL;
+                  require_failure_message = "Ed authenticate without Ed ID "
+                    "cert from peer";
+                })
+AUTHENTICATE_FAIL(missing_ed_auth,
+                {
+                  tor_cert_free(d->c2->handshake_state->certs->ed_sign_auth);
+                  d->c2->handshake_state->certs->ed_sign_auth = NULL;
+                  require_failure_message = "We never got an Ed25519 "
+                    "authentication certificate";
+                })
+
+#define TEST_RSA(name, flags)                                           \
+  { #name , test_link_handshake_ ## name, (flags),                      \
+      &passthrough_setup, (void*)"RSA" }
+
+#define TEST_ED(name, flags)                                            \
+  { #name "_ed25519" , test_link_handshake_ ## name, (flags),           \
+      &passthrough_setup, (void*)"Ed25519" }
 
 #define TEST_RCV_AUTHCHALLENGE(name)                            \
   { "recv_authchallenge/" #name ,                               \
@@ -942,17 +1431,34 @@ AUTHENTICATE_FAIL(badsig_1,
 #define TEST_RCV_CERTS(name)                                    \
   { "recv_certs/" #name ,                                       \
       test_link_handshake_recv_certs_ ## name, TT_FORK,         \
-      &setup_recv_certs, NULL }
+      &setup_recv_certs, (void*)"RSA-Link" }
+
+#define TEST_RCV_CERTS_RSA(name,type)                           \
+  { "recv_certs/" #name ,                                       \
+      test_link_handshake_recv_certs_ ## name, TT_FORK,         \
+      &setup_recv_certs, (void*)type }
+
+#define TEST_RCV_CERTS_ED(name, type)                           \
+  { "recv_certs/" #name "_ed25519",                             \
+      test_link_handshake_recv_certs_ ## name, TT_FORK,         \
+      &setup_recv_certs, (void*)type }
 
 #define TEST_AUTHENTICATE(name)                                         \
   { "authenticate/" #name , test_link_handshake_auth_ ## name, TT_FORK, \
       &setup_authenticate, NULL }
 
+#define TEST_AUTHENTICATE_ED(name)                                      \
+  { "authenticate/" #name "_ed25519" , test_link_handshake_auth_ ## name, \
+      TT_FORK, &setup_authenticate, (void*)3 }
+
 struct testcase_t link_handshake_tests[] = {
-  TEST(certs_ok, TT_FORK),
-  //TEST(certs_bad, TT_FORK),
+  TEST_RSA(certs_ok, TT_FORK),
+  TEST_ED(certs_ok, TT_FORK),
+
   TEST_RCV_CERTS(ok),
-  TEST_RCV_CERTS(ok_server),
+  TEST_RCV_CERTS_ED(ok, "Ed25519-Link"),
+  TEST_RCV_CERTS_RSA(ok_server, "RSA-Auth"),
+  TEST_RCV_CERTS_ED(ok_server, "Ed25519-Auth"),
   TEST_RCV_CERTS(badstate),
   TEST_RCV_CERTS(badproto),
   TEST_RCV_CERTS(duplicate),
@@ -962,18 +1468,41 @@ struct testcase_t link_handshake_tests[] = {
   TEST_RCV_CERTS(truncated_1),
   TEST_RCV_CERTS(truncated_2),
   TEST_RCV_CERTS(truncated_3),
+  TEST_RCV_CERTS_ED(truncated_4, "Ed25519-Link"),
+  TEST_RCV_CERTS_ED(truncated_5, "Ed25519-Link"),
+  TEST_RCV_CERTS_ED(truncated_6, "Ed25519-Link"),
+  TEST_RCV_CERTS_ED(truncated_7, "Ed25519-Link"),
   TEST_RCV_CERTS(not_x509),
   TEST_RCV_CERTS(both_link),
   TEST_RCV_CERTS(both_id_rsa),
   TEST_RCV_CERTS(both_auth),
+  TEST_RCV_CERTS_ED(duplicate_id, "Ed25519-Link"),
+  TEST_RCV_CERTS_ED(duplicate_link, "Ed25519-Link"),
+  TEST_RCV_CERTS_ED(duplicate_crosscert, "Ed25519-Link"),
+  TEST_RCV_CERTS_ED(missing_crosscert, "Ed25519-Link"),
+  TEST_RCV_CERTS_ED(missing_id, "Ed25519-Link"),
+  TEST_RCV_CERTS_ED(missing_signing_key, "Ed25519-Link"),
+  TEST_RCV_CERTS_ED(missing_link, "Ed25519-Link"),
+  TEST_RCV_CERTS_ED(missing_auth, "Ed25519-Auth"),
+  TEST_RCV_CERTS_ED(missing_rsa_id, "Ed25519-Link"),
+  TEST_RCV_CERTS_ED(link_mismatch, "Ed25519-Link"),
+  TEST_RCV_CERTS_ED(bad_ed_sig, "Ed25519-Link"),
+  TEST_RCV_CERTS_ED(bad_rsa_id_cert, "Ed25519-Link"),
+  TEST_RCV_CERTS_ED(bad_crosscert, "Ed25519-Link"),
+  TEST_RCV_CERTS_RSA(expired_rsa_id, "RSA-Link"),
+  TEST_RCV_CERTS_ED(expired_rsa_id, "Ed25519-Link"),
+  TEST_RCV_CERTS_ED(expired_ed_id, "Ed25519-Link"),
+  TEST_RCV_CERTS_ED(expired_ed_link, "Ed25519-Link"),
+  TEST_RCV_CERTS_ED(expired_crosscert, "Ed25519-Link"),
   TEST_RCV_CERTS(wrong_labels_1),
   TEST_RCV_CERTS(wrong_labels_2),
   TEST_RCV_CERTS(wrong_labels_3),
   TEST_RCV_CERTS(server_missing_certs),
   TEST_RCV_CERTS(server_wrong_labels_1),
 
-  TEST(send_authchallenge, TT_FORK),
+  TEST_RSA(send_authchallenge, TT_FORK),
   TEST_RCV_AUTHCHALLENGE(ok),
+  TEST_RCV_AUTHCHALLENGE(ok_ed25519),
   TEST_RCV_AUTHCHALLENGE(ok_noserver),
   TEST_RCV_AUTHCHALLENGE(ok_unrecognized),
   TEST_RCV_AUTHCHALLENGE(badstate),
@@ -986,6 +1515,7 @@ struct testcase_t link_handshake_tests[] = {
   TEST_RCV_AUTHCHALLENGE(nonzero_circid),
 
   TEST_AUTHENTICATE(cell),
+  TEST_AUTHENTICATE_ED(cell),
   TEST_AUTHENTICATE(badstate),
   TEST_AUTHENTICATE(badproto),
   TEST_AUTHENTICATE(atclient),
@@ -1001,6 +1531,9 @@ struct testcase_t link_handshake_tests[] = {
   TEST_AUTHENTICATE(tooshort_1),
   TEST_AUTHENTICATE(badcontent),
   TEST_AUTHENTICATE(badsig_1),
+  TEST_AUTHENTICATE_ED(badsig_1),
+  TEST_AUTHENTICATE_ED(missing_ed_id),
+  TEST_AUTHENTICATE_ED(missing_ed_auth),
   //TEST_AUTHENTICATE(),
 
   END_OF_TESTCASES
diff --git a/src/test/test_routerkeys.c b/src/test/test_routerkeys.c
index 24b0da1c46..56055a3b02 100644
--- a/src/test/test_routerkeys.c
+++ b/src/test/test_routerkeys.c
@@ -614,6 +614,67 @@ test_routerkeys_cross_certify_tap(void *args)
   crypto_pk_free(onion_key);
 }
 
+
+static void
+test_routerkeys_rsa_ed_crosscert(void *arg)
+{
+  (void)arg;
+  ed25519_public_key_t ed;
+  crypto_pk_t *rsa = pk_generate(2);
+
+  uint8_t *cc = NULL;
+  ssize_t cc_len;
+  time_t expires_in = 1470846177;
+
+  tt_int_op(0, OP_EQ, ed25519_public_from_base64(&ed,
+                        "ThisStringCanContainAnythingSoNoKeyHereNowX"));
+  cc_len = tor_make_rsa_ed25519_crosscert(&ed, rsa, expires_in, &cc);
+
+  tt_int_op(cc_len, OP_GT, 0);
+  tt_int_op(cc_len, OP_GT, 37); /* key, expires, siglen */
+  tt_mem_op(cc, OP_EQ, ed.pubkey, 32);
+  time_t expires_out = 3600 * ntohl(get_uint32(cc+32));
+  tt_int_op(expires_out, OP_GE, expires_in);
+  tt_int_op(expires_out, OP_LE, expires_in + 3600);
+
+  tt_int_op(cc_len, OP_EQ, 37 + get_uint8(cc+36));
+
+  tt_int_op(0, OP_EQ, rsa_ed25519_crosscert_check(cc, cc_len, rsa, &ed,
+                                                  expires_in - 10));
+
+  /* Now try after it has expired */
+  tt_int_op(-4, OP_EQ, rsa_ed25519_crosscert_check(cc, cc_len, rsa, &ed,
+                                                  expires_out + 1));
+
+  /* Truncated object */
+  tt_int_op(-2, OP_EQ, rsa_ed25519_crosscert_check(cc, cc_len - 2, rsa, &ed,
+                                                  expires_in - 10));
+
+  /* Key not as expected */
+  cc[0] ^= 3;
+  tt_int_op(-3, OP_EQ, rsa_ed25519_crosscert_check(cc, cc_len, rsa, &ed,
+                                                  expires_in - 10));
+  cc[0] ^= 3;
+
+  /* Bad signature */
+  cc[40] ^= 3;
+  tt_int_op(-5, OP_EQ, rsa_ed25519_crosscert_check(cc, cc_len, rsa, &ed,
+                                                   expires_in - 10));
+  cc[40] ^= 3;
+
+  /* Signature of wrong data */
+  cc[0] ^= 3;
+  ed.pubkey[0] ^= 3;
+  tt_int_op(-6, OP_EQ, rsa_ed25519_crosscert_check(cc, cc_len, rsa, &ed,
+                                                  expires_in - 10));
+  cc[0] ^= 3;
+  ed.pubkey[0] ^= 3;
+
+ done:
+  crypto_pk_free(rsa);
+  tor_free(cc);
+}
+
 #define TEST(name, flags)                                       \
   { #name , test_routerkeys_ ## name, (flags), NULL, NULL }
 
@@ -626,6 +687,7 @@ struct testcase_t routerkeys_tests[] = {
   TEST(ed_keys_init_all, TT_FORK),
   TEST(cross_certify_ntor, 0),
   TEST(cross_certify_tap, 0),
+  TEST(rsa_ed_crosscert, 0),
   END_OF_TESTCASES
 };
 
diff --git a/src/test/test_tortls.c b/src/test/test_tortls.c
index 8efcac242f..44961c88e7 100644
--- a/src/test/test_tortls.c
+++ b/src/test/test_tortls.c
@@ -1086,13 +1086,13 @@ test_tortls_check_lifetime(void *ignored)
   time_t now = time(NULL);
 
   tls = tor_malloc_zero(sizeof(tor_tls_t));
-  ret = tor_tls_check_lifetime(LOG_WARN, tls, 0, 0);
+  ret = tor_tls_check_lifetime(LOG_WARN, tls, time(NULL), 0, 0);
   tt_int_op(ret, OP_EQ, -1);
 
   tls->ssl = tor_malloc_zero(sizeof(SSL));
   tls->ssl->session = tor_malloc_zero(sizeof(SSL_SESSION));
   tls->ssl->session->peer = validCert;
-  ret = tor_tls_check_lifetime(LOG_WARN, tls, 0, 0);
+  ret = tor_tls_check_lifetime(LOG_WARN, tls, time(NULL), 0, 0);
   tt_int_op(ret, OP_EQ, 0);
 
   ASN1_STRING_free(validCert->cert_info->validity->notBefore);
@@ -1100,10 +1100,10 @@ test_tortls_check_lifetime(void *ignored)
   ASN1_STRING_free(validCert->cert_info->validity->notAfter);
   validCert->cert_info->validity->notAfter = ASN1_TIME_set(NULL, now+60);
 
-  ret = tor_tls_check_lifetime(LOG_WARN, tls, 0, -1000);
+  ret = tor_tls_check_lifetime(LOG_WARN, tls, time(NULL), 0, -1000);
   tt_int_op(ret, OP_EQ, -1);
 
-  ret = tor_tls_check_lifetime(LOG_WARN, tls, -1000, 0);
+  ret = tor_tls_check_lifetime(LOG_WARN, tls, time(NULL), -1000, 0);
   tt_int_op(ret, OP_EQ, -1);
 
  done:
@@ -2653,18 +2653,18 @@ test_tortls_cert_is_valid(void *ignored)
   tor_x509_cert_t *cert = NULL, *scert = NULL;
 
   scert = tor_malloc_zero(sizeof(tor_x509_cert_t));
-  ret = tor_tls_cert_is_valid(LOG_WARN, cert, scert, 0);
+  ret = tor_tls_cert_is_valid(LOG_WARN, cert, scert, time(NULL), 0);
   tt_int_op(ret, OP_EQ, 0);
 
   cert = tor_malloc_zero(sizeof(tor_x509_cert_t));
-  ret = tor_tls_cert_is_valid(LOG_WARN, cert, scert, 0);
+  ret = tor_tls_cert_is_valid(LOG_WARN, cert, scert, time(NULL), 0);
   tt_int_op(ret, OP_EQ, 0);
   tor_free(scert);
   tor_free(cert);
 
   cert = tor_x509_cert_new(read_cert_from(validCertString));
   scert = tor_x509_cert_new(read_cert_from(caCertString));
-  ret = tor_tls_cert_is_valid(LOG_WARN, cert, scert, 0);
+  ret = tor_tls_cert_is_valid(LOG_WARN, cert, scert, time(NULL), 0);
   tt_int_op(ret, OP_EQ, 1);
 
 #ifndef OPENSSL_OPAQUE
@@ -2675,7 +2675,7 @@ test_tortls_cert_is_valid(void *ignored)
   ASN1_TIME_free(cert->cert->cert_info->validity->notAfter);
   cert->cert->cert_info->validity->notAfter =
     ASN1_TIME_set(NULL, time(NULL)-1000000);
-  ret = tor_tls_cert_is_valid(LOG_WARN, cert, scert, 0);
+  ret = tor_tls_cert_is_valid(LOG_WARN, cert, scert, time(NULL), 0);
   tt_int_op(ret, OP_EQ, 0);
 
   tor_x509_cert_free(cert);
@@ -2684,7 +2684,7 @@ test_tortls_cert_is_valid(void *ignored)
   scert = tor_x509_cert_new(read_cert_from(caCertString));
   X509_PUBKEY_free(cert->cert->cert_info->key);
   cert->cert->cert_info->key = NULL;
-  ret = tor_tls_cert_is_valid(LOG_WARN, cert, scert, 1);
+  ret = tor_tls_cert_is_valid(LOG_WARN, cert, scert, time(NULL), 1);
   tt_int_op(ret, OP_EQ, 0);
 #endif
 
@@ -2695,7 +2695,7 @@ test_tortls_cert_is_valid(void *ignored)
   scert = tor_x509_cert_new(read_cert_from(caCertString));
   /* This doesn't actually change the key in the cert. XXXXXX */
   BN_one(EVP_PKEY_get1_RSA(X509_get_pubkey(cert->cert))->n);
-  ret = tor_tls_cert_is_valid(LOG_WARN, cert, scert, 1);
+  ret = tor_tls_cert_is_valid(LOG_WARN, cert, scert, time(NULL), 1);
   tt_int_op(ret, OP_EQ, 0);
 
   tor_x509_cert_free(cert);
@@ -2704,7 +2704,7 @@ test_tortls_cert_is_valid(void *ignored)
   scert = tor_x509_cert_new(read_cert_from(caCertString));
   /* This doesn't actually change the key in the cert. XXXXXX */
   X509_get_pubkey(cert->cert)->type = EVP_PKEY_EC;
-  ret = tor_tls_cert_is_valid(LOG_WARN, cert, scert, 1);
+  ret = tor_tls_cert_is_valid(LOG_WARN, cert, scert, time(NULL), 1);
   tt_int_op(ret, OP_EQ, 0);
 
   tor_x509_cert_free(cert);
@@ -2713,7 +2713,7 @@ test_tortls_cert_is_valid(void *ignored)
   scert = tor_x509_cert_new(read_cert_from(caCertString));
   /* This doesn't actually change the key in the cert. XXXXXX */
   X509_get_pubkey(cert->cert)->type = EVP_PKEY_EC;
-  ret = tor_tls_cert_is_valid(LOG_WARN, cert, scert, 0);
+  ret = tor_tls_cert_is_valid(LOG_WARN, cert, scert, time(NULL), 0);
   tt_int_op(ret, OP_EQ, 1);
 
   tor_x509_cert_free(cert);
@@ -2723,7 +2723,7 @@ test_tortls_cert_is_valid(void *ignored)
   /* This doesn't actually change the key in the cert. XXXXXX */
   X509_get_pubkey(cert->cert)->type = EVP_PKEY_EC;
   X509_get_pubkey(cert->cert)->ameth = NULL;
-  ret = tor_tls_cert_is_valid(LOG_WARN, cert, scert, 0);
+  ret = tor_tls_cert_is_valid(LOG_WARN, cert, scert, time(NULL), 0);
   tt_int_op(ret, OP_EQ, 0);
 #endif
 
diff --git a/src/test/testing_common.c b/src/test/testing_common.c
index fd7c4e7074..deb11d0112 100644
--- a/src/test/testing_common.c
+++ b/src/test/testing_common.c
@@ -155,65 +155,6 @@ remove_directory(void)
   rm_rf(temp_dir);
 }
 
-/** Define this if unit tests spend too much time generating public keys*/
-#define CACHE_GENERATED_KEYS
-
-#define N_PREGEN_KEYS 11
-static crypto_pk_t *pregen_keys[N_PREGEN_KEYS];
-static int next_key_idx;
-
-/** Generate and return a new keypair for use in unit tests.  If we're using
- * the key cache optimization, we might reuse keys. "idx" is ignored.
- * Our only guarantee is that we won't reuse a key till this function has been
- * called several times. The order in which keys are returned is slightly
- * randomized, so that tests that depend on a particular order will not be
- * reliable. */
-crypto_pk_t *
-pk_generate(int idx)
-{
-  (void) idx;
-#ifdef CACHE_GENERATED_KEYS
-  /* Either skip 1 or 2 keys. */
-  next_key_idx += crypto_rand_int_range(1,3);
-  next_key_idx %= N_PREGEN_KEYS;
-  return crypto_pk_dup_key(pregen_keys[next_key_idx]);
-#else
-  crypto_pk_t *result;
-  int res;
-  result = crypto_pk_new();
-  res = crypto_pk_generate_key__real(result);
-  tor_assert(!res);
-  return result;
-#endif
-}
-
-#ifdef CACHE_GENERATED_KEYS
-static int
-crypto_pk_generate_key_with_bits__get_cached(crypto_pk_t *env, int bits)
-{
-  if (bits != 1024)
-    return crypto_pk_generate_key_with_bits__real(env, bits);
-
-  crypto_pk_t *newkey = pk_generate(0);
-  crypto_pk_assign_(env, newkey);
-  crypto_pk_free(newkey);
-  return 0;
-}
-#endif
-
-/** Free all storage used for the cached key optimization. */
-static void
-free_pregenerated_keys(void)
-{
-  unsigned idx;
-  for (idx = 0; idx < N_PREGEN_KEYS; ++idx) {
-    if (pregen_keys[idx]) {
-      crypto_pk_free(pregen_keys[idx]);
-      pregen_keys[idx] = NULL;
-    }
-  }
-}
-
 static void *
 passthrough_test_setup(const struct testcase_t *testcase)
 {
@@ -339,15 +280,7 @@ main(int c, const char **v)
   }
   tor_set_failed_assertion_callback(an_assertion_failed);
 
-#ifdef CACHE_GENERATED_KEYS
-  for (i = 0; i < N_PREGEN_KEYS; ++i) {
-    pregen_keys[i] = crypto_pk_new();
-    int r = crypto_pk_generate_key(pregen_keys[i]);
-    tor_assert(r == 0);
-  }
-  MOCK(crypto_pk_generate_key_with_bits,
-       crypto_pk_generate_key_with_bits__get_cached);
-#endif
+  init_pregenerated_keys();
 
   atexit(remove_directory);
 
diff --git a/src/test/testing_rsakeys.c b/src/test/testing_rsakeys.c
new file mode 100644
index 0000000000..66684fc279
--- /dev/null
+++ b/src/test/testing_rsakeys.c
@@ -0,0 +1,545 @@
+/* Copyright (c) 2001-2004, Roger Dingledine.
+ * Copyright (c) 2004-2006, Roger Dingledine, Nick Mathewson.
+ * Copyright (c) 2007-2016, The Tor Project, Inc. */
+/* See LICENSE for licensing information */
+
+#include "orconfig.h"
+#include "or.h"
+#include "test.h"
+
+/** Define this if unit tests spend too much time generating public keys.
+ * This module is meant to save time by using a bunch of pregenerated RSA
+keys among */
+#define USE_PREGENERATED_RSA_KEYS
+
+#ifdef USE_PREGENERATED_RSA_KEYS
+
+static const char *PREGEN_KEYS_1024[] = {
+"-----BEGIN RSA PRIVATE KEY-----\n"
+"MIICWwIBAAKBgQCZa39BCgq7KWBWFSjGYHhqmTCHvQ7WNEFAb9Mujb6Xn/Zy01fu\n"
+"WIpVvqmAKeLNEziItUm/gB8GwAN+/ZLwL9pufjIp2Ar+yqVXKySioZQxuCgTP2wm\n"
+"Ku0OfmAra1Xbtrkc2OCJllxkyNPrJ/kxfwjWR96UP0+VMbOlkBoEH1FtvwIDAQAB\n"
+"AoGAUXoygeMIYe+OdwkTt48CRHKIwH3aRE5KHSOGPyIOB05vvvmYqD8jcHgqYqNc\n"
+"DNdZXdkRin9LevU8phObFq4DTXp08XggUx4Kk4AdsFKubQtJ8gHm3xlSKbZXX2m/\n"
+"ZF0GRaZtVDQ3TRGh+OBLILt/2jT+BaFKGAyJ7al76F2nprECQQDJyLlteLDFBmrd\n"
+"0kAjNBE50S5YskBCQeQACROfyTKW8lG1J57UBeYjXvbrDFBR4alIS9DEexGai9Gz\n"
+"wxpgKg2nAkEAwqQmPstjHxvqGQRi41uXO026MLxY7dhEqs1aSw3tuT8v17pW3OEa\n"
+"Qxv7JINePZ3+sNN+Ic+3RXBR0QuD7lSSKQJAZjVSF21GvMXfY7SX4D0DbLHUNAE2\n"
+"I1mUz5/JXOpgwazETmpfPS4vwELd93kpRhBz2rbsbFmaNRoVgmSU+5jRiQJAZ1bV\n"
+"g2NilgKxEGU2x3U6Xt8Oqo9lO6omEvUCKnUTsNWuZf/l3FGbKuQxO5qPr3Ex5tny\n"
+"zqrEqBZRKgbOHfxCuQJAbJY5C3Nm5koemr031r00MY2YD1b6+hyKZyPdZ21HpyY8\n"
+"z1kWShL0POjYPX/BnKE1FkpklWcKBb7wkK7dvAKkEQ==\n"
+"-----END RSA PRIVATE KEY-----\n",
+
+"-----BEGIN RSA PRIVATE KEY-----\n"
+"MIICXQIBAAKBgQCyqMM2TfFGV5tVBTVabxLVln8146nDavIdR6q78DCUMh8Zfzkk\n"
+"h9Lbl1NX4RU+AmrCZMPq21/EjIRxRQyRdgPYJVLdp96eGeYnEzmMkqvXiswXvDg/\n"
+"tXqsjyJeYsoHMQWDTpCLfjYo4K1ol1sg8VIs4wQeq5og6QSdmhBoz7MyqQIDAQAB\n"
+"AoGBAIJekey7nZeV8Bxva4ptSRIg+v0I/2VBUiG5nUX9NIW/uV/yrXERx/VDjKaw\n"
+"8b5JJzxpKWnk4RJc83xwRYaT1qMYHiQfybxEI0K9SjhtaThAjtXkQGtZgLJILl3t\n"
+"yh3LPTh1ocwafsKjU6eGYAe/DYn9/QwYHbtyaimcigu4etp9AkEA2DgC+HndoP1i\n"
+"np26Lx+4TG0vAfrVYGSLT9FXwf2iBV3oJvdKqu6wr8ipb1SbshRPcOQd31/mCh6+\n"
+"2BR+d4ddcwJBANOHrlBbGZdHnoEu6kKbPwwkc31IZYqyfSpkqm0Lb2oWZ9SInKfc\n"
+"cz0qpH91p610XUpYmycaJr4K+N8jgrz86HMCQQCoqGBg1Ca2OpCf66bctWB8dTqS\n"
+"z8d7rlIhC8npr1+f0hWRt5pN5Wx7YgoQpq3gZgllpPtMT7DQOhVh1fKkaDnTAkA4\n"
+"XuskPPLX7t0dvhvtviOSH9CrLXTp/mD+wC7uumJpmij3aaSd01DelxOZaAhUYDNQ\n"
+"UcafKAf1E0V5aaQ4qwljAkA9NVN6CtpzzcLrstTKxrx5P1Ylt/0UYQDo1lIaqwrT\n"
+"aOFbXmOungiC9+p/4U7RbX0MEzjFDHCWlaHASviGVgta\n"
+"-----END RSA PRIVATE KEY-----\n",
+
+"-----BEGIN RSA PRIVATE KEY-----\n"
+"MIICWwIBAAKBgQDDt2V63APj3JSqaRgofUzhtB+prm0wII4uHyxfOxnpYIELOW5z\n"
+"3UHmkr+B4D+Nif5jIp0i6W4OS4S+YHewKsDsXvXKRIW78KzOt6Le4JI9rSarNjy5\n"
+"aJKksWQRALLCmxP/BdolaBFqF3fIPD5+Zxu8ESgxhkEQI4p7awUp3E730QIDAQAB\n"
+"AoGAZktfAR4p8lkCYydW9yK2ommQ+xEuBK+fYL/uYz/yxSYpjIJSFsEYhrlA21Mo\n"
+"JIRxr8MRuoOjgFk8YnztUeimuHpslDlZDaCBzjRjBRFCMepZNG9xqSEL0u7C+SH6\n"
+"KU5f2x2P6PneBj6WaHZM+6Lf2xHlOoeuaVSUfq2Pk2VBF9kCQQDtawWWNwP0+xea\n"
+"oCAQpanaLzYPjlqZfHJQ1AAI5eSkdf1qmlypIHwOtjAEa6XuEO/Or8RNkNy4nQdw\n"
+"qhcQ7PXDAkEA0wjT6Z+Lrt67FnwPgoSvl4Nukcqw4OWHbBKhaQPsO9+oc3PAXLdD\n"
+"SclUUqDF6NX1yONTV1KrPdz4zElmEua+2wJABm4inZnp2oW+cuqpU6oY+pbSwQMb\n"
+"AxMyyWukgJkxYx7q+SsrHU2K7p8Sl9wOh28f/5oVGAC3aayfGfcRXtz8HwJAIqeO\n"
+"dQzYGU1GF7kjquEzHIRewd4xEZ1fkaW1j9MvFd3ygZL+gbsud41yJWd1WHjaNbTu\n"
+"2KYgrLX+vT1IX844hQJAbg0V7iHlttQqXL7yN09jIjQLprqVhDZCUHS9s9Dxe7fz\n"
+"Ac0ZZD0D6EVNmSmBB71q7kLUWX/W/10d447TLnnfew==\n"
+"-----END RSA PRIVATE KEY-----\n",
+
+"-----BEGIN RSA PRIVATE KEY-----\n"
+"MIICXgIBAAKBgQDhCAjPEockl4lqkvoIb5O3NJJG8NWD31c63e/cPWY6MX5nOM/q\n"
+"avof2eWJxFOk0HQ2BRVwIgNex6kLxtsdw7XE0A5uZorTp9DbRCGMqUqHNhHH9ci2\n"
+"mMPP9jptq3ieWg310bH4Tad8h3WE2npSCDBvxyV6EmuH2rlQW9ZlHNoiRQIDAQAB\n"
+"AoGBAI4PgWggPTqng7PJF5mNvsYQpSutzE0VCL977nmuNUQVjMPjRLarVD4ZU+QW\n"
+"EevhQQv9R5xjjJcgGqL5pchzjeKDm0/LA+AygnZoDMs2O68Neieqvr7cPqr5ALGs\n"
+"WuZvSn+bRJTenvV9sUh2ii0/u3GQbL1v7GWDkIdD7itDbmRhAkEA8iijuEY+W67w\n"
+"7JusjY2MQ2Cm6xxxR0YcnYPzT6UDm+Z7NNJwKscQ6AjayNmxmXGpbUdukzLzXf8y\n"
+"fccI9t6iHQJBAO3kx9nZay0Ktl51QP5o2gwoqRIbnogGfR06KJOlzIPGR0aPn8cg\n"
+"uKq2SiyjewEaSBM6S/4UlxYUmvc3VKnxCEkCQQDpTjg2YQ7RPGIIRA/iLV7Wx3bq\n"
+"C/QjjCwjoi44LK6mdE9928WPoUzrkSRg4EQYpwZqL6kcDrmkdSuLPMipOGQNAkA3\n"
+"KtzlujPOiDNuiEaAORSHyU4b8ue6p7aP9pK+Wq6oyGxzAo+NABuTCx78ZxT5Vnzs\n"
+"aJKC44d+CV0+g0hQ+KJxAkEAqFYzNWIzTHX8DVDdK9BpUaBg1DFxIeP5Kk+/X3FF\n"
+"5BafG08B6OiLf8qIGGsxLXNRjIE0GVp3Sy23FUKtUymP+A==\n"
+"-----END RSA PRIVATE KEY-----\n",
+
+"-----BEGIN RSA PRIVATE KEY-----\n"
+"MIICXQIBAAKBgQDMDk01VwPxQq/BAwOBmfGUP/x5BQn+uxI0Aat6bdWuz/2CsjbS\n"
+"CWD/YLCaPm+DpHp9RMwk4HONJaw4B2XOw3ELPx7y9DEgdC1wZ9wRkJmqr2IJZoZR\n"
+"C7x43nNv+/IXTiRkkljCcMpoL1Tld+L2VbmWR29PdZwvspWRILkEZu1mNwIDAQAB\n"
+"AoGANvFK3KfXSei4xfF3yjeXEmHAKx2uOUZJenNQpqBYPr+F9ODjXd5knZ59LqrM\n"
+"/9cTnBMgHHXK5yBTpKppQSjikLeQ2BF04Ktff9oGqVcS9x/rKo0CREuxsEfawZOW\n"
+"OzOWENp4YcDKGP1I/Ctr185QzStaWrXVQftxmYQ53T77ShECQQDnhabwtqW7rfe4\n"
+"+MfkWEJ9Y2s6iMs3JWnwPOX9G9R39PiAD4vAghHJyHHttS9Ipxmvp0hThu0x7a4g\n"
+"8BfUpqgjAkEA4aFAmzarWKigREAACVTYH2RHpXbuk05vF9WqfMPiEvQUd5a1q6vc\n"
+"xkGZsE3v/TExLjPRZP4FeUNV5sD7THzA3QJBAJxPoRlNx3GCEAlDdfnWGPX9JI09\n"
+"hC40RWUcSI7ttjJTI1+an1kWuBnLChhaRpU/tFjikTNLmmMmPHUihIRfDI8CQG7g\n"
+"3WzpKr8A7vFbOilbxnF2yDaqAYfmTXW7DHMPl/OUetJh/5kDdhT/e9VGF5+nIvH/\n"
+"iPFGW85Bpt8lCtmFnQkCQQDjpp9iy2qesE7KKX4Kv3++QfCJ2w3g7lwg4iyncoDd\n"
+"JrM53p29HROM21R6eekvqeWIe9tEX754b+E/N60ZjpGm\n"
+"-----END RSA PRIVATE KEY-----\n",
+
+"-----BEGIN RSA PRIVATE KEY-----\n"
+"MIICXgIBAAKBgQDdDn3H+Eu0AW5GKohqDBntw6ubnd3VaJwZGzZyga4J2kLg8peP\n"
+"RAW6GDD6pcHzW+KZbFWHtRk70FSwvmyGcf+DY0r5tfyCHyDGmbJyPR0o6OVCgSFl\n"
+"ccf4eDvbyszzMdlx3uL05ABIpCShoKtEUqvyIQla3Jon+QBwuVkizMzyVwIDAQAB\n"
+"AoGACoKh4Fwh3VEkGRn0mnYw1Wk0Q5Xh8j+jDF6K3C7mQ3mpLGDca+dkDlEQIxq2\n"
+"egeoYnsQJf+qT3m8TRsAtfO9nj7+7IX4BfCtdIi4RNcorbs5YMWtFyaywnM6SQjS\n"
+"+1qf74aL4On9WRO2FtvnTMjFAAkiWNbQp7mWwTmB59i620ECQQDwde6/PwhUzvZh\n"
+"dyslKJdna5RjkDQyDIuh0zD/tFZ0Iko7Luec8q6n52ev/n0OiTLGetUh8goePsPP\n"
+"HVZHidNJAkEA61eMCmmu+GCAg2vJRtL5sDakAXsbP5M9Bf/QVHXtc4EVXHC6T2ld\n"
+"bldOJriNbBThBuPNmlQbssn9FApkyWT4nwJBAIuHIv3+CUuMvBJaH8L0BsaP+g67\n"
+"wk24Ud2Yujnl3rSMoR4uXV8IwqfS8quAs/gXTEs3QyzrUUuzh9NKZqIkK2ECQQCz\n"
+"vivBEDKIlPvSZBJYO25kfXcJgoKvLb9fw5/TwjXXD/HGpnpFiI3JZnjT7gRlVhT/\n"
+"9CDmC/MTvF3EXqPXhXy1AkEAo3a2me23Ljmub21jycSKaCk09dK85QTRRMe9c/hs\n"
+"i+pcGi9ZZW0Mm7cyQo47oXjNurkkv0fEvXIobVTEXAGU7w==\n"
+"-----END RSA PRIVATE KEY-----\n",
+
+"-----BEGIN RSA PRIVATE KEY-----\n"
+"MIICXAIBAAKBgQCv8R1IbfYnE3R3kNeezJ7m02XnyCBDDy0YfrQldQ+urdg1CFye\n"
+"bO0iPniJb8fmV8NW7x6nUZTDznCg+igroKXtK/w0WYmJJiH4A7Oi5xNjAfRIPvJ/\n"
+"J5GI8szS8rH8tp8pW1h8k/kNg2pnBjwQ2U9omhp95RGaHDQSRYzzH/fEFQIDAQAB\n"
+"AoGAcy7+BcH/iZuB/xjzIIJDcUhqibCJ9n0D/+pLU85sYuZrCmUcBZe4M1gEn61v\n"
+"iExilRJc1hthskL/l1POYql8lk+aqeeDuh38fWJj60TCV/sENiuXOsTmoFVA5pNn\n"
+"lwlG8JlpBMsgr1fGqg1C/WLFfMmvXdKVGvpRqI06j7AYUa0CQQDfZ5rI+FhXBlxo\n"
+"PR5CM1LB90DuHUMW+Kqoj0c9d2esXEQM7UqQ/9BiBQbL6Py7Z3VwCxibOqyz7+V7\n"
+"2aGUMAKnAkEAyZy5Mu2tHs6YBBxPYam7huzMUYjddN7ixAZUyGwxQp9kTIF2NbSQ\n"
+"yVDjKrco3s2lO4qj4pSumwVe3GGlsi6G4wJAOOS3pIqqZK84BUvbUtyjLMZ9AKbv\n"
+"GQCG5ZpneB3ahyiQJAKiRL8BIJVLH87b3hYA8GHDCHUu2jwz4xCPd5+qbQJAV0TP\n"
+"pYvb9AnZI25drhiaY7z8dA6aTYxs/A0Bhf/PEteLwtIHKRgP1BR/QG4n8slxTGSm\n"
+"q91P9ypL9XkPECGzoQJBAIMvGEM7ZGevQHBjJ8HhU8IsgT4cYH/XEYb8jRy4F+Ui\n"
+"jKxHPxLuFK4urAZunNUNrqhT0PxbB7hRjtHZrmFkrcc=\n"
+"-----END RSA PRIVATE KEY-----\n",
+
+"-----BEGIN RSA PRIVATE KEY-----\n"
+"MIICXQIBAAKBgQDSpmV8ncLwc8gXzdFsZGPDtMO7C/IN9jKCIK13WIseMg1APlMt\n"
+"PB5lMQ9fa3m9ZRU0L8HzRo+u/Xdos3yIBI38X2Avy0laGKnQxiOKaDT/5ZHeiBBh\n"
+"nMZjP2WY5V1sgqNP9RD8enE6WaSvq1j0BM++mn9KEe//5+dWD8tboBKF4QIDAQAB\n"
+"AoGBALgVoerdE1Z+WAY1XyaSNHz6o3H6ZnW9CTaex/jb7/dbVikmThnhx842qXCB\n"
+"w8m3ZGhOs/edWkNaTde5wsI6+LhVGco/PWxN4v61jokxUU+5KvUvGacXhXIjzKwG\n"
+"DrNCYmle62QCI1z4+TLQW/Lq+jw2Wzk70NWEvoP58gt5SJoBAkEA9wubRKRs49LW\n"
+"5JNQZ9hjc+mAfP9YK/sMe4jkdloMMWXjSMlF3Z4mI9XQSpfbBqwWIBXsjU/15LIS\n"
+"ftmujZsMKQJBANpJEZI7UFoRdSP7AlM0YJuXWnVGyn/K+VIeEso5AlZdKXCTpxqp\n"
+"9blWq0UVC6jLesZ5UNPuBiAnrBaVwDA8YvkCQF+FQVfdK607TJO80g4VAP9EfcXX\n"
+"BUScIUtytsN8NdKzzpnKGRWDnMOmXI87ABkoWLW3RGuvSyhOIhCiInfmR2ECQASc\n"
+"FmroJcJBLCAeZOYs7P1cLOTdIdmhB7LcP7lVit8YCJAADj9Z536KfgNvdleSNH2M\n"
+"glB3blmvfMrdTrm2DMECQQDj6GJ/Tc2rCsq534xknasVjrgtJMQFxmQCTVgBx9pc\n"
+"gTflJAHAmNDvstacVqeObLCF2ZIvya8fSXGbDOJYeGDv\n"
+"-----END RSA PRIVATE KEY-----\n",
+
+"-----BEGIN RSA PRIVATE KEY-----\n"
+"MIICXAIBAAKBgQDGgUJAm7vf/3focNGwzv4TkzYF2XwpAirnb61dyxvfug1zKv2k\n"
+"AUg3qACiurR7JrI+kAbmxEnNaKV7ts7uO763wP9KE8YAuFZsp7NFA295rEZhw38T\n"
+"rUlWHMCeaZ3mqW2q8gA14C/ZJCG4gS91SIHLjNGsbHwr2Jvri2ItwIP8FQIDAQAB\n"
+"AoGAONceb32oiHWQkkBr6uL6ogRPPdGO2fdC7c5uqCLWsnOGEmpHAsVTNoym0fIA\n"
+"aBsmgv+e2klukKDccdZg3prA+z7lHcc2a4bIFguF6ei80hLIis/dds66fFXofCzy\n"
+"DMlkncSbJwIvQHG9gblxp9qSKElZF7XjABZEImarfUlakGkCQQD//msGy5N0ZhMI\n"
+"yGMXkwXRJXfmRrIrOqHx6u1eUp4OuqDW+hBz4KCHnWfuRJkNGQIammSf18jPasP5\n"
+"YHyr/LifAkEAxoJ8R8Vusexo9ZjuU44qXCSvJQ26UBV7mn6TGEAn2DRK1RWKDaHv\n"
+"j2vnRjt3CO9WPDQL7SB/1HNAy+dIMPyqywJBAIB6tESIz8zPniX+TJ18UKMTZwXP\n"
+"3YQMvVKpUdDRLjq+OBMtFizSRD9MJOlUzGvibUfkzTPcHRDcyNbUMj4vbIkCQBx4\n"
+"6sqAjvgGKKfRX52sbnb47AYsieSisC/gp8h6qzxfg7w8cqix6WJw36M7ND+b1Iqe\n"
+"DHfeiXc3cLvOWJRuKTECQCEYkujtSjXWb26xaESFWGtUI/nEvCyqYPQAFBpaGzQ3\n"
+"tiTDeKHzypesWYoTxOiNQWCQMLrFGuUbDpYOuDOVNjw=\n"
+"-----END RSA PRIVATE KEY-----\n",
+
+"-----BEGIN RSA PRIVATE KEY-----\n"
+"MIICXQIBAAKBgQCcwSAfytnspSSDX/sKmCPOMnpuCYeWA4wbz1wLyb63a8/KXhhG\n"
+"6o2W0kt3x1vnGZkeWwZOeBFUqwoc+xHhoNcZFsMOyqbqA3UMZW5cx27MsexRTQHs\n"
+"Go1newu/E+8NNCohY51G7z1Hdo0L6mi/Tldh7puuGsMwKqNG/Vvo/GQDgwIDAQAB\n"
+"AoGBAIUdpBAbjXDe1OET0vYuOMnUKA/l29RS8tpy/zGrg1/0GCM8QNWIPfEEaL4w\n"
+"+CSKonMazYI5iE4kaZQuygKXOdFqKxX8nrGK2hR0DIEUHhhiqyGMUKrf4ELkAJzK\n"
+"tHtcO64OFEU2EGa72wCmyk2MhqhLxWxA7E00x24uvW6pen6xAkEAzHhbzlRgLZ+K\n"
+"QuXmQHEqkGaS2Ccf6c9TA5Bf5S2/5zBl+OqVyJJQH0yrbPYR6Nn1NeSv3R4IDJYg\n"
+"fSZLaVzWHQJBAMRCU6QtTnZoQ97pLvXCSKRYKJF+CnE3zDFTyoJrpK0W1FSnb1EE\n"
+"DWjjdSdMLynf/InX+VOaLk3Gxwjme4NKjh8CQQCg2b4/HplayrsVzY3I/D2jw02Z\n"
+"xY2RfYusrhMCU284DBbsLn8OfiuRs9rXqOyF5ZDFiNXgeROT8zYzvcBtbp7xAkBU\n"
+"ZET9IvJLXjhZISItUXbVHIeNUIqC9sBaMbKx9EGioF97a2gliT2O7cgRtuPM+ODq\n"
+"ETHILlNc5G3vuNRBt4x3AkBV98Y1SZA3TQlUVTsjGraxkFTfU1IlomiOdOwTQ+xZ\n"
+"x+JxhhgZwZ+kgI3PidEufFCTZJ3WO6Wk9gk18Bx7CLjm\n"
+"-----END RSA PRIVATE KEY-----\n",
+
+"-----BEGIN RSA PRIVATE KEY-----\n"
+"MIICXgIBAAKBgQDq/K7wNW3fcTbaRTjNZlM4W0G7tKeO+X0bca4+9uin3ML3ogNJ\n"
+"6qT/B0QAZB6Vyi9kKa3E8plQkjmPuX8Q27zj2QjEuDZ12RGFnikeOosUhOYiDh3Z\n"
+"T9CHnr6stozzgk79Xd6VI7bqRcgRwbY0uc9QVr6vwddyIfSploSpVcgspQIDAQAB\n"
+"AoGBAJfUpo/sZc6uzxtfCKGmkPTj+ef3hSBbUZuu60AhtxfnC06HrwpOg0eJAUYj\n"
+"aqOsHMziJTYQ7kDiCjE0UMaqxDNS5hueumznq2xM2mSN0nYoktU00kpANVkW4VPA\n"
+"33TB16DyqlKq2/21Rs1g8/8+IKkKDbRLTC//1WqNHASQVoGNAkEA/+z4hxTVXZkr\n"
+"9hz29tAHKURlqzxUEKLnS0eL+XGJRNfGJ+65eXL+gFiIbTnpVeidL1+lKWkZyYzl\n"
+"75cNRdUHhwJBAOsOJ9mUOqTbLW5tzh18ewZGOa1JcxhOvf2E1d56N8tDK6lvoqkF\n"
+"oUUb8kIweDxPLCVLCl8qFrbjn619fxDInXMCQAfEZGKNIlCd5nSoumIRPDZnagKB\n"
+"aTe8CfMB7+CZLoZVWiE6IIzsDYdNqI5QFKHT1nlqmLOiCfNRAGV+GxwEdB8CQQDE\n"
+"sHu4HclU2fMSTOAE3H01qt3om2WsGXfyBI3SNQMrG3IVvkymkwd4BQKbUGPMU5Pl\n"
+"QP3U1CtdruuXCUSijrzxAkEAoqYub6+0zM8fakSQZcZ01TG9Fuo2xVFDCQsvqR3m\n"
+"ZhRT/oinIvOxSh4fQs40bmt1RBmc2L1Is6YB2NTVQEBZDQ==\n"
+"-----END RSA PRIVATE KEY-----\n",
+
+"-----BEGIN RSA PRIVATE KEY-----\n"
+"MIICWwIBAAKBgQCrf0rPvHYaGYQrc1ciRwaONs8TUvSVmUU98HMYXoFEkBL4CAGH\n"
+"4oNHFk8kXHEOsBED0eccSYegWhqKHSz7PbjmJaXloExWrtx5ea3Twf8VTgcfDWQP\n"
+"0TzD3G1TYjAFPQ1/LAZCpQFmwpMmTGGxegUhOzkpEWXdLVEVc9Uw4C4L2QIDAQAB\n"
+"AoGAZXAJZA5pHM7y6nBynYe9TOkGWru6h7H8zsImkcd0VoWRcrvpi+JjG+0KKsuy\n"
+"46kop0XEmWq0mhgxknfnX0QG1MKTqGMIUGN4qCaezOabIpCOdA4d/pr/mWoNgOWw\n"
+"9Kc/tNCrKxPKsQMAlWP6ktHN30XRSlHgAjSeUVUiNHztvTECQQDUNin2nyIvj8ZA\n"
+"QAsFW9qW+TiTkeUK6yiZ9Gvgf20gwZRWOe5/xnMxVvtN6v7Av1ew/l4VhBoj/w5g\n"
+"ydIZk+2LAkEAzuJwdt+ccllG19qmEcbo9XFafgi2PvlEjPJmT1rHV2ns/7HIMu27\n"
+"PJY36GgExSfFco6VmicaoOt+RKg+5acgqwJBAKQxAEjcGWQ5VsgRhTVxO3DChX7Q\n"
+"TColhrWPwwPhM/s7K92HVzwvvKL5TNmdr9xMb7n3Ja56FouxZVuH6/J0XT8CQAat\n"
+"Mhnz/3WFQg8HRGLAe5YoMVZt64u+uaKe1ARtlo9QoNBjqWVTXL6IzocWjEjcjrey\n"
+"uEtARdC5qNqIX3dD3H8CP3pVCPvpHOTxkUaktmLYowSA1HSfO9wkE6bMCHhkLwXF\n"
+"yTIJ+N7c5u5YN1B6hhVqpKbdnSv+K0MQ0xbfwOWNMw==\n"
+"-----END RSA PRIVATE KEY-----\n",
+
+"-----BEGIN RSA PRIVATE KEY-----\n"
+"MIICXAIBAAKBgQDGQmrKfO3WovoXkOTSh/shO9qjbX4izhg4pccVU3Tp45v/dgAE\n"
+"uDUuaa/clToyH5AhOtuazO/asC3ZNajg1ia5VPzmQU3gtqiIZIEXFaOovPlOrXru\n"
+"wyQnxaGORndJwfDXicG6bUwI+PDpNq8c4VOTujReeF0r74qMSc7TQLVlUQIDAQAB\n"
+"AoGAakR/aTm9YibJVohbnl00xoOGlcLCsXU2lmaFZ3DsYdGWdD+TkvQJzW7ozJtQ\n"
+"Lj2sy6L4wujGR7nXWW3hr2IaLpoc1UoyJpieAZM5os6bMN+N4MCqdcZMlazMtSWV\n"
+"UDO7O7xQGFpcvvZmnfKCyluFaJ5K/tWxP+2TnS1/m0BDRIECQQD5DYvToA0eKBt+\n"
+"7K4eEI8pzDot9NlcL21D86kNgpmuY4pifALU7GvXr299JpFFiYa2A1JVRfpQaoI3\n"
+"hZzz0ze1AkEAy8opWJP+T2q4reD5Qq5UjjrHUXFID23KeJEjh5YF40/bHqyVpWVR\n"
+"UMntNgAzs+13vRij48Zn6I8GRhStaQ3ArQJASPyFS8GN1paeaDXoWPs1WWR2cF1f\n"
+"DbsAZHeVxVXOv+J//ZimI8wdVpodLCoPTLee+NxEVqUpVEPCYY8QjgwKOQJAATmj\n"
+"6f5pxvxzQ8hYd0gpBfngfOLbdgxI7VSiDAyg2G8AeDy9YZMsW/n6zRpPNUO2NpLR\n"
+"WWs18LX7aaxyJnGIuQJBAPPfy9pd4XEFsRBIIe3N23Gua1XkS/407RJtAGm73Vrt\n"
+"QhtWh3i6D5gfpEApMoaE8aaQQ7H0z+0Uh1t8SWesy10=\n"
+"-----END RSA PRIVATE KEY-----\n",
+
+"-----BEGIN RSA PRIVATE KEY-----\n"
+"MIICWwIBAAKBgQCc/M/X8etUqrxnmH3PyuAYLIPZhwNySch8qz9NB47izYjxzuBG\n"
+"GSls6H7WeKIrB8UJY1gW8TLkdOLcrI/0hTANNHEPaueOE0xdABFj7tAaiiGPIM25\n"
+"N0wc76me0ZAMYJrZTHk8JZK153y9wInYBwVZreXCVSVf11RuVwe+iFQa5QIDAQAB\n"
+"AoGAQC4XJtivdhDLL6snHFF7pkZkrQTGgu3pOhakrXA+mTigGQOTqvTUe8LdP/9X\n"
+"hTIK+tiTheWcAcxLhx5BSB0/VDKjYhS0ROpTc33Iq9KalOQaTJbBYGA4eagpQjwU\n"
+"jGwr9u2sUsM9WI/Jg0VvLSKhfnNwYIUzLpK3BbWb2qAdh+0CQQDQ2s/8DlibFSBK\n"
+"UsFK7lLpV8UgMk9CkaNM2BPzI8Hsjpp6s3pULVRd36m4YTSg15EEHv7bZ1N/+krX\n"
+"mXb9xUULAkEAwGy5wHsUSjTK+kntkNXjlCU/+9R+HFpzg9Bwm/PqXTBwEWeU24hV\n"
+"iRjPvqPtWFZrWi/nfcviuMaqtdliw1I1zwJAZ2mQxhtMYC2LuYFUWAe9YfClmJWQ\n"
+"jUOTef8bka5I3RqW/t5TWc7AEWMnpDXtWx6hnUrDolt9Cschu7MvKeQ9lQJAL18U\n"
+"46PpPNN+XNuyVoOxgRkihVasrUI/SeYYsuv7eHGiRUagyOLpW9T139LvbV3pE8zT\n"
+"So7VA/Q0towL2lX01QJAGcoBNNouSpum9+5NvGQK1XXsZweawE+pFR2BE5XcjG+n\n"
+"FnaLEUBX7nTxhTU2cSQET1PKRNp568a281NEna0nxw==\n"
+"-----END RSA PRIVATE KEY-----\n",
+
+"-----BEGIN RSA PRIVATE KEY-----\n"
+"MIICXAIBAAKBgQDFOqqGG/VtIScxayZYZ+BT+hcs5W1bD5qRxunbG9O36UVT18UE\n"
+"CWw9HUf0Q5sDMGvVmBxwZ4GjbR5FDPfhIXaRCzobnejJXq/0k+O5NAVkcSPtJvhK\n"
+"AaUqBrWA41vnjKOtJudTsZLfufKafzYwVonze7fXGyVsBRjVwHNS4iqq2QIDAQAB\n"
+"AoGAJCoStI6R3RXUKvKb0GATuTJFZ50WBTmCPTK9FMkwdCuY47vPy2Ky7y3cUMTI\n"
+"urf5PewrYs0H72CFyWGMXkKVi8aOYshsATEXMfGSqOcqXn+UDssRzvabZFlpnAUa\n"
+"WDVt/iN092AdakXNna7/DxrLisDpq8HHJfjtlWGPfkXRg4ECQQDpHeKimTvwJcPc\n"
+"iDa6Qb/n9gwLeRckfzhYtfX1luJYLIOHh+J9vjQN75thenBLQB/B6qlKtOn9ejxg\n"
+"5z+3zIOpAkEA2JbxXVTCOA802p9khvHxDtLHdKi3w/BjjJiC7Mgqo69ZI+s3PB9E\n"
+"F2HJA69kZqpGqvybWHDapjWsq7rcMlxrsQJBAME2yvR3y00VEAyGPc4M1vF8ZqlP\n"
+"uRW/+ETWtEDUyU/JvU6lGt2bu2tdkEyv/cjxIiFIzP4litdT7B1pLc+6S9kCQBwE\n"
+"usiWFGHoJbA6emiyl7qRLdg7kzo3uMkRWa6D3nA6WM+6t/SBHu/faH+fit91G5s2\n"
+"/mmcf8yMmP/GNoIVTqECQFl4Pt6yGiz/YVoYSp35ljY5n3JB6T8o2pOmIrRLuPmT\n"
+"6kgyygtJBAmx5nnQoeG8n08tl9QakWznKzkNJ0DIFKI=\n"
+"-----END RSA PRIVATE KEY-----\n",
+
+"-----BEGIN RSA PRIVATE KEY-----\n"
+"MIICXQIBAAKBgQDCaOqJ0lsSAEBcnNB6X7BvVcEcol+evi/nJsPe0uT1SbtW50Ch\n"
+"vYOHwK6aQR2C5x9VSs47cLynTL7tNt5d8oeryF3NpI8VTPLImDJCcvUZhS7p4bxn\n"
+"JO+Wm+D/e3TWfyjreuWtdL+Mfimw2gzwWuBEtmj51GzQ89eYm7fh11SB6QIDAQAB\n"
+"AoGAWaakMbZNxPlUtOCjyysBY/Y5vYira7rswD3CKak7aFn+CE9QIMYSN7IFUqEg\n"
+"iNMoQd7jR8nvVX8wtJeO5+gF48W13C3n8FZSrW7c5N3bmfMIgo0xa/TGfeXHP98o\n"
+"7vhH0I58j3ZZt0Q+3wTm7t7WPE/nJzgrCk30TqmoaEmstTkCQQDtV6YZ6juEK2Lp\n"
+"LGUiqohcS/WJxvFrF5+LNpk86Xdgomf6FphZlkq42KYkvl7qibKDcfDqLKTbHHle\n"
+"vQQeCgZ7AkEA0bFHi7F8o4iHtKleBvt4QCj1neA0q3CRDypCI5EqFSrNpxY4Krhh\n"
+"WYSVX+xT00QYaCpKKWfYQztCw7Anylv96wJACl86Mwe5ch0zRV1bThiFvQLUyCCZ\n"
+"jESMBFlueOr6/I4cXSF/puqaeVl+aTyoiTdbRcNE8/bffXPRGgLIm0d04QJBAJSY\n"
+"lmTN789Lby99Xh6AkaSV4ghw26Ip8QHYJmph8npxjK69Niw/4Oy44cnKBVUPSmR2\n"
+"o3tYFY7/Lb7S1D+4lOUCQQDbMQUGVsZT+ZjuOG1bAjIuXoAOfOd3mgH5VgQHjSgJ\n"
+"ourZtlJ4OUpNrq9IfWqPkM+zSE8+0Dk8/9MS5ngBA/SJ\n"
+"-----END RSA PRIVATE KEY-----\n",
+
+"-----BEGIN RSA PRIVATE KEY-----\n"
+"MIICXQIBAAKBgQDNbHjwg+7tVNr9erMLowXRnIcttp4pUJbr3B7Jo/u+kD/Yo3F3\n"
+"4rIKhHpJl1uEHP1QmvAD+4ApFFI2hNG54xYI8dGflxL5HOs5xxyOPpkrwzQ8Qvnv\n"
+"LPg7Gf6PAW9zF4McG4wK0TkrV28G6NhqcPs5VFY6UyvfZ0fEdWAeoWTIfQIDAQAB\n"
+"AoGBAKOmkMp7MLLd8QAS6eSRYSdWHdLrMyES1MjduaFGBF4SKOr7en/Zl6ENXSaX\n"
+"cA7V0XCPnjpt9/HCAKTyNupx4LCeFWiqdu8VGXhlzX8bdb896OSR2brKbxgRY5tF\n"
+"36uL8akrZdrYgocykQCxmRARMB7/rHwDusiamjL6RUZ3+c45AkEA6UPTVmKZQRMr\n"
+"A7Qgg5nXrXo9117Lpqf3FdZ1wdni9V59Ptf5xrx9oGZNZzctJPXSAH4M4cumSJrV\n"
+"sZ1V8qE7AwJBAOFx+5luLrVKrdlG7MyOhTAdhKYUvKIvL4wvVSY6y+L2nNEx/cTx\n"
+"KYbxGC+H1RJbkCS09rYir3VfDRWQ3W1c1n8CQH+X4hn2hO3blkPIW6CgniD+JKWR\n"
+"7MOUTMtdK7yFemfM76VYbgAPSohabSxwOfllnSE30cQQqTw9tXYaIdE98BECQG+M\n"
+"QWxSS0QillB6unIgVqBPCrJOcmNhK4qWZPBMiVNcqI0Nyj2nAeAl7MyfzfqOWY0A\n"
+"CU5nbR+LD2NLUXRqSisCQQCN3IGv1WOWInmA5xhU6vCFDX5u48Dcji7VLJO/Nv/i\n"
+"b/zHKAgjHk5Js7bi5ZWEGaUgA4Jt6cKmGdERheqTMKxx\n"
+"-----END RSA PRIVATE KEY-----\n"
+};
+
+static const char *PREGEN_KEYS_2048[] = {
+"-----BEGIN RSA PRIVATE KEY-----\n"
+"MIIEpAIBAAKCAQEAoksI1qIuIaFCqT4QbgDvOQCmr9Z9F0E7ku+U5Ep/5dWNANqB\n"
+"bSzAOq0+cxiisfF+H4desoqiWDUwlOwXH74qD3ZsbChhvFUD78cQBWQkF+whLVHb\n"
+"296QmF0LZqosqz9HMS9CdoMUc1brZb78Hb25QIOOjrg25KYHLZHaqcet1wfhHow6\n"
+"Uehc6QTuWgOWFhJnfiXzYgen2o8lnLixxZozhk7Lm7Aix9ur2ckXdQ2Wgny4xw70\n"
+"JW84Hapnd8oFUD98XXrExk4VFuIcA8qo7r7y18II6wx4Cw1suKru6bhW65cM/y51\n"
+"KC4lB7VkvuoJCelRFdM1PfKZLv2tJP63oAqJrQIDAQABAoIBAQCWc38PEqw3avqU\n"
+"UMAEaoNa0bq1Gd8/Nq8WqVnbRSFKHO2pk+cWIb1W6BITuwvgcGKesezdEV4s7apK\n"
+"9I7/U1hEm2Ep50mrwRh0KZM1nD9Fmharn851Bt//D4qpMytT2caS1yADI8NKpZJ1\n"
+"8VZh7+cT4qG+txHUaAIRgbw3VrBWvTIMu6SOSOZm+e3eOr5UU3du1KvjdJHJ2c2k\n"
+"TceHvUdKxV7OYt+BBSN1oBOhs3ajUSRge1v3twRDg3cmbwG0DeXvwHNhGUTcF8IH\n"
+"JO1RF5njbkFvyqdAi3ltjU41zYd4OMuPtrwzFOtxUjKT62Soz109HUXXE2CGKFPZ\n"
+"PVi5/BIhAoGBANN1xqS5BgHszIB0nXbw5ImYpTRmyhO0KsTblBT9+8Q/B7BCK7bM\n"
+"zl+dOPeyvEadSwE7RSMMt6CAlTakWIf3Quw/VZajvXy9C9/LHf52pEKXjxMFMPKE\n"
+"aGLHpQnwMtDi8/H8AEAXxI3hpxB2KVR7sAYHWihSGjRJ6oPGvEmKEkb5AoGBAMR6\n"
+"G2PKz0xk1vFrjfjSY+y13gH/t7xHaXUggjggUSGKaknQh2BDUllXjadeI0fi1eLW\n"
+"r98ZImZZgntAgjaIZ4bAlooTDk4gRHaz9jI+z8lsRwOKnWdiigM7txiXZTMVwMqj\n"
+"o5mMNGMA+A+ACkTViRHmkDI7S/9FqAvnbOqVwgFVAoGBALUcY6WDvwx5B3Jh7tgH\n"
+"XIYpEh3+h8c2gYcX1g3gtvkPTwN8uToY0gz8eOVV1YHZiHsmi4GIi+HRH3usaRMT\n"
+"COOVHzYlSc8Dj57+tdLTRL6wVl9hC9o647ju64DGlI9qQquYPZKniLZIdbFYsu9j\n"
+"/JA9Tc/I+h6czFpPJccKlbrpAoGAAPWXrKUQ3g6f/g3IY66jTkSVEO1uuDyhBzFh\n"
+"cWS3ALLsUe/yuUWa4VTMHEUZZwB0iucBdNVqlZVaTb/C4wFHgCDwmzv8leUScIHw\n"
+"cc5ctV8R+bJzkk2o3tsrybLzi4xPpK2n3tgQaWtXyruVUUC5qpy1l4kylcyBRY2b\n"
+"uomAqQECgYAiCNWtuWIDlRBcvtIB+kHguzcoFT3vTCCNhalTEn0zi/tbi+voQgVJ\n"
+"SDJNptZv+6vRwQ/HfcQtljKIPO6hUZPYaFWRNhgbh7Ay85lRXYXQOottE8ayReBk\n"
+"zZb0fl853Qah4DPsaOugAvhjjKeBmKg6bFWO1z6hj18I3UpDf2YnVQ==\n"
+"-----END RSA PRIVATE KEY-----\n",
+
+"-----BEGIN RSA PRIVATE KEY-----\n"
+"MIIEpQIBAAKCAQEAssO0r37mSJNAkc/ISwXBsu9JjyLeWlsHPAhylQGkSAdp2rjz\n"
+"E6AT0Eh3wrocNO31I4pvHReAuh1QedGY6T1cQwO/WAAhQtRCBQDK12qWRgfbC11y\n"
+"Xu7zNYPd1Z7YIRy+FxhbL5f+lv3rEUv0HUG5c3CWhLtbANKg+jOieIDzA4Yp1s55\n"
+"ynodQBUkTZrwQiT0P8yDSjiasf+clgJRfA1k2XK12KSAMRgyDuPTE4OtBxBvUM3L\n"
+"Zvxs81PsmcOuAG4DLaFTg2a/QkCjt2VC1SYYuh/LVxpL41FFh3eMoK5g5deHkgRe\n"
+"tlywKjAHIDJu/qgNzNgNW7ymwn2CfBvry9h0/wIDAQABAoIBAEMZ4wDdCWPEokAZ\n"
+"Vn2Ss5qO53WrCPuxn42RPjFgZGIFJl7LfbKoK8fK6+lUIrJbf+DPXdX1tIQn7MVN\n"
+"P7CNL8yX44MMyW9kbUOjgIBLqgyvdjFV6lBoMTKtRN+iuE31lATnR5Md4pqaxVnA\n"
+"wOkaepoycM1x5j7w0SwZparF/HIdkYv0y/MysqT9ByupPA4Fqp/iRSrosHXahNtI\n"
+"KZYj1TyERYtuDXq91P4dr/pWq3FmDNI8O3upblkL0YouvG/ZlFLdiNy77XbAyWcX\n"
+"ps3YDddM+vECnXO3+sa3ZxgBYvXJdWrrIzM5A+jCkDRZQGsFAzK5I5/S7C2ljt6i\n"
+"SmzqvMECgYEA16bGy2XTi6KBPb8aev/OBgK9XuGLwUqK1m15mS9Y2qPHmuc22qaZ\n"
+"hw6zginPFrxAEtQWKanhZy4aVqlLkDPLwRnyeuMo1EZAc5B1gZ5ViSAKxBq99hA9\n"
+"eqyakdb+IUQsEnRDxSc2gqUQ0EagksUyw5wGG5Q/CVEALmS/r1SU3KUCgYEA1DYf\n"
+"6JYdzuRtule3vYeWXKf8sOJpdplgWV7tvLrKkQhdE564uwMCYB23HvYfwWqEdDYG\n"
+"fsYg/ur/stk9MDZ3wZKffTEM8V3sX1t1JXnC3ogSAgMGhLZ3ILOLqkoO4BEZJnsS\n"
+"dMdiNijlAtQkqs/BO/UVUAKysCtKP3v/+1775dMCgYEAvLjGFjApfnSbV/cK7IM6\n"
+"wEXbhdIqZOCgOeEaXjVyM/zKbMRVW+oaR3hVHd8KzSG3jQKv1oxFpu9Qu3ByoWLC\n"
+"uF3Ft0debs6ADuJoAyQWROeWpGGmxlUWCGpO5rxYL7KiQxAeUsXrTU+5NBvq4CbV\n"
+"MxwyuCX3OGb7mp4upfiGQcUCgYEAuhVsDYv1P4LXJVvd5viKRV2ZG5KuYC1Ga5fu\n"
+"aFxzXJI07At2eaa94oKsHR494mEBHNZzA5/BN0fiSHZuTWS1xqxH5oOokc6Gg2ez\n"
+"ZdVLp88x20nD4YQPGkHW6tBeEuVrZG7vVC+yU0Ow7bYRISdkjqrusWZsQkbzqI+X\n"
+"fFliEbkCgYEAu8x+47M1ordbI7NmbBGyiyP0r7nMRCZ+KEvGeCNYracWmsnCNnfV\n"
+"zR2UzmwtSainw3Ho8Jv/rWDC8RIDauyBRYEi2VqOnUzT2ca0iymQyLeBCudAQuio\n"
+"drOu4JU8RzZ3Ad6V3DNFnaqmX/7GA9Pa2GI8NJMyb8p1GAGv7Gi8nxc=\n"
+"-----END RSA PRIVATE KEY-----\n",
+
+"-----BEGIN RSA PRIVATE KEY-----\n"
+"MIIEowIBAAKCAQEAt01S8JuEwWy/Hzb90yO2O7oGWq3GfvfDpFOF4OQnwG3kQ/BP\n"
+"4MoPDCYHdqb3iI9aD3vykZA6Q8zpdfGwjm4+bHrgRdiSmZWv8NvRwuQ5Ji9xbiGn\n"
+"hA1XwqH9hvgFTiy6tRvirWSJ7kzH3Q/bEGpCbHUQkwMog4v6yCNKNrjlwjN++eCi\n"
+"gFK/0RMOJMLOs8BD3zY+lKjd/pd8LBRujkMyUF5SryeRueAFjD2sq4OXq8DPABGt\n"
+"zdR6vbTcsi4JwP1Q6y4x0/LIWEprzzewNU63I5E2zj0WnoRGAIM4aF+VuqcHjWUx\n"
+"VWnyLZldSen6lScZ4xj4seitiDbSFvtFkDF6VwIDAQABAoIBAGTP9im2ntDyyjqU\n"
+"uA0DuxomOZBtupniEouyFBOX5/UBe2WSKZxsBNKdp8UuFz3X+aRCeyprtF/NtyjT\n"
+"AFOVdmebPPWtIxOtK9LAUyFo+7VwqmXzxHnwDLBS/2jXx7MzDozFBWpvvRx+xf1i\n"
+"1wy0JEwaJj90oTeYKRkhr5NhJZwkX8zCNYaemBd3kHB3aGWGJasI1Y81UezeRKCn\n"
+"hSbn2CrWalI7pyJ4lsavM11nIq1Eu2ZthJiNCMghbYrHoBHd+iVWiCYchP2rNEWV\n"
+"sdHtaVHtQ9zdZ43bao3OzPu7lAjd6UAbxsuhUe+a2YdDz/+Up+6+BvQf1FCfYIjW\n"
+"KFUdCoECgYEA4t5O+u0V9gkMUhKsevYb0zgc7O/mo8ivN+V++EpAtL0mhiwxeO8p\n"
+"oef0szLyhdULQeLN9pJQDCeAbkGdwIe3L+AKU8o8BFGEWLFysZjMg9In/UTrp5MN\n"
+"mMDy2SRKKu5BqsvdYH302xpZfHq1T2cMNDWE8lrZffduH06Cgq/XEtECgYEAztbj\n"
+"bhFneADnrvk609VnOQvoQEjySeCQKFQFRRI6k/FguqMisL2IRXnMaWammosdeCAg\n"
+"m7eZchnszHIst9cwZUKXUFqmAqeDuWSNdTI7uKZH6nT/A6IDlgdjaHsqhvpK0Ac9\n"
+"ngycdHONitOZh0ZG74pdWjf828Dwzf+CuYjl9KcCgYEAmIvI6ZqvkJ8m5Kzfw1Jn\n"
+"BVCOypbJK8oOX3R2Orea6KzjEYb3wQx3nwFcHX6danYFOskpmqlpH7MT/Y8rZsEa\n"
+"4RsxdoPedTzm08iFiXtn0R9nejp0hlov402iPXXUVSedih3IflBTa1w9XaEY9wog\n"
+"P57ZBSknYzcTmgNtaDiaUnECgYA5sWauhNw/dMEq5QmrnJK2LsQRakdqo+CR3x25\n"
+"LmR4b5Nze51pfvRLrLV/kMpXwQXvQ8bUqFl8og6S2CXxAWzWUcSy/RXhF6h+RbXP\n"
+"Qru1vWvB0fBvqvklF9p6giBSle3YKKzfMNVTBggs+OiR+uA+YHG5gHRfN2nzi5mC\n"
+"9tRtcQKBgBnDSi4lRCjRe9pPnyAYaa4iyBUGhjPysScSLY9orel89+qmTBQ/Py6J\n"
+"0+sefL4ZJaOsuaR2mSSPP/lbSkF9DMFs4tHbBqY+WkVNYLshAkauHwqv26HTVCSd\n"
+"QKzeb7uZw9lNaRIzDvy/3wfCLvXfdDozPFrOUgkyaBN5pJSA/4sv\n"
+"-----END RSA PRIVATE KEY-----\n",
+
+"-----BEGIN RSA PRIVATE KEY-----\n"
+"MIIEogIBAAKCAQEA9qtiDoJWqU/eSlpj381eG6UcDzfMguFh/q4e4s7QVdRYj5J0\n"
+"Msv0PCkti8JHuvQUyncRpOPccBkhNbVjNbjIgw1pHaIZNdVotUDhP0kseRyJ6z3M\n"
+"qbZ5qKn+0mHjVjPNItVDDe6tebYMT1BZpVyRrCOqY2v5z1ecLC+ReygmHgDpzg+L\n"
+"0rWfIxGT10IPZ8pAlcdEn6xt5aEhi7mPCX/xwqfQChPIJz6zVLEC8UaPtvDBohPR\n"
+"6NQTBTeZZAAtzrQ7+oNxfz1v6Fz6RwMei7Q+qOBnMiwpQmbcDBKABM2RnXSpD0LA\n"
+"1GR7/+CiV1HQoShWVvEwrSIlM6jVAJo6iqF6WQIDAQABAoIBAHqwcdxPnfUm4aTP\n"
+"4r9NcZKEhDlZgqJSoiA/0OL1BRC7xrTanmspoLhPrvTF1FG715+Aq8j9AQbMqQUC\n"
+"zG7LEwiEIhV4K9vn4uXMeHy206UFud/E5EhBl695pmJUB/Q3XcAGnQyP+77++o50\n"
+"o7IpIdeiAbzj1uP3aplbq5u7M4JV7fUZWA/368G4HolqFTxcAfBJ05GXlp97BBwY\n"
+"AnY3/pNrKMz0NiPf3nsJHYWK18up0JCLPL3tomc94wuNZ66spIazHIL9aaKY0q3V\n"
+"LkBrelndfYM1m4xRTnSOy6STu0qKTPOpX0C8XBLYs6uiXjRsChqSYwndCCeASaH3\n"
+"LGNIcbUCgYEA/m4qvt8tdT4wEvnE+QUxEELmBtT4UFa3NnQISrzNlhNeI0Zd2xlp\n"
+"SG0/pcw83mG2uX+V5xSaWL5LYfLBkvy83Y0yIWgYbbIkyyCOUZnTpwaDGU/FjWip\n"
+"3TfXf5qpAgiez94sV+MsFpKfG05yxJh5u+3sIyGTVUAxp0HPx4LVgbMCgYEA+DD1\n"
+"fu6ttpuV1UMrsFdjuk6gBvSbyJ9OilY2jT+yE7hSRc/yP3O9ikuR74tNlVrWTnO2\n"
+"0kcYbyLJXE2cGUC2q5e4r8TDGiozNfQ7/OC2M3XaJ+xJk4zMf/8PuDDpWr+18ZXA\n"
+"Pf+ibXWTFvZ6ZeUmpbrrfCrXdvmIZnwVuOI0FcMCgYAZn26emksxq3mb75tumJ9A\n"
+"S/xuY7Q+Iv2Adl7/Z9QscPbiBowdLIn1yUrHn7Hhk2WbeMXX57NDjKZ6zr+/1cQP\n"
+"a9DInHsZUP9zlWu/vAYcpAM/4VC71PaGWMFTEHhExCl6NZ2xnCcsfseXMGdOdSyN\n"
+"SICnaRI1W6mkdnQ+W2a1EQKBgGEKA3KVr6XuPy8bDEHuaTe29irCCQbwAq1j+ABS\n"
+"HzZGoyRYocbdYgZoda7LMJJs6c3SwHCHC66oU0KbtaTKAKImuDdBH2djiJJX4/yD\n"
+"f7mvIpTpdfsS2gJRn7vMo/CvdFv4ySl0gfV6OwCHbmPYrLuv0dLCjWwfNI2dhoC7\n"
+"MNIxAoGAIPSIG4BrShzbeX4c2L18iwIg+NlOcUbtl0Ccr1t6uLGI+ge/6I6T/5XH\n"
+"DPKqYIf0IRYV8suxpfQNKiz/C0NPffA1d1M2hvuAg2v09o2cSwvdcQwdmakKZ5bl\n"
+"sdCuYKdCIwomEUOz/4XgQrJl4XDUqxftJT6/egAjWvcIYvfNCsY=\n"
+"-----END RSA PRIVATE KEY-----\n",
+
+"-----BEGIN RSA PRIVATE KEY-----\n"
+"MIIEowIBAAKCAQEA1yHZMsgRLckL+v6rgpGq9qmxVBNDxeuul1V/QlFyOlcAk5n/\n"
+"uduTalSqGQhc4NEePMxq6nFui4ucpkZOozmcEnhV0N9jld9IB9rLGt4erdg7RKl9\n"
+"+gQ+zTn69j69U36E2I47H4dM69uxeSOyWP2Odxpw+biisa3o8mMz1zCmuj4GMDtG\n"
+"DlnSpthFzgQR6N1pbvxLXrWg5F16GqFiJOD7kXDfy4/l6kB/mDs1T/3r8kav6DqR\n"
+"c/t3aQZxgWGIpI7hc9Qgvp7coZRMey5dNOZEna3tqS8dn2tZlhkpYV5uyFUjmxjG\n"
+"TERSULQ7hvUqW+eshGGsnxFtL7ANnTSc4xECowIDAQABAoIBAFhJJMhpQFuIySjd\n"
+"AGeZ/g4x/3rgWQzNNp4WUR5XLEhy0eLA7ShJywp06kVRoEQGraEHxsyldldAGS5H\n"
+"ZhgoGTufNKB+PHER646FpJpHE1IGjfQUloVW3qr8I1iQ0MOGBWCVpf+/V7rnMsLi\n"
+"+lr421FXgYuJ0QKXuyRVv72M0q9U6i+ml3aVAhgW/19oFg+dW7YccX+9iVyD05Q5\n"
+"KR64tX8xd4wrAqfAgYA3erbbE6GTyHYD5K54kIgfRr/+pIU4qc1L7XOCblnqc/rI\n"
+"BilFysEC634r2MNe66uQvNui4oQTfBcFFlXg0zAmp7d5QE0ApOL6HpCsmbImm2uJ\n"
+"sdFNYyECgYEA716kfEv7HfnF0P3pAP2AOuEsW6t8q0UtWvnHrwRQXQw8Yv90g7kD\n"
+"pUV3/BjD9VQgsQZosbdSn5wbT4j7dypRdrzYk+8m/hBk4Q8M/tWoRGVOn46NudvK\n"
+"/KX0A4ODLuulj8yAZVc7CM5Cdy4GCGJBVO+oVvBUAnHxfZziOyqBw9MCgYEA5hQg\n"
+"HEORzdxvbbfAx1ggvH1Eg1lqRhmpI43PpRkaoqb8jLwXb2CyBeuv3RBft/X2Tr6F\n"
+"mHpe0U1kN/5YEjii/Q/jUX8azIHaUNNSAjrriEeMQZOqFxmhCdiyeXuqg2fbFbhe\n"
+"K3Q6/fsB1xj9OOSwyPMqm/M5U0LsoGjmg8TFE/ECgYAlImKUIdlwOgp1NJ7MF4eo\n"
+"Gryd8AmkLFQv8+YFgb7R4I8RsJ2rva0SG6fUhScJTSbRL7RYNZ9swXP/L7oLL5Z5\n"
+"vCxBLu22pmZv/7y9X/n9ulWrLRtRhQaFkV08mk9knQwPNeOJVTIEWLM49/vZmxyV\n"
+"h6Ru8FOoGXMkUI1MLnj5HwKBgGJLkNhiacVYeuaWDa9c0EeXARFYvxWJ2wAMkvzG\n"
+"9+ErlFQP+7ciyYvMAItidnJii8NilDLrfNzQwpNFf5zxQ3j4M7bapblfdMT5M10u\n"
+"jPfhEWPm0VEjKvDI+p76HYQcd7YU2W6ZLqbZeRTLYUvQMFL5yGduBzyyJ+P0TR9Y\n"
+"jpYRAoGBAM7vYGTprw4w2tTZPFICXVk1bQ0LO06oNRtwkiQTUT6UqPjWMFyvHnmN\n"
+"11SVVBmRZ0RAk6e5eZLFX8WelJ4J4nSOGRcJheCtoEFlO7D1ewAUSbqWJ0pBqp2T\n"
+"gV4oCS8LYe8zReVoYZJjuLwoHvxZzs/hUjc3SI2HRW2W/HQRPC25\n"
+"-----END RSA PRIVATE KEY-----\n"
+};
+
+#define N_PREGEN_KEYS_1024 ARRAY_LENGTH(PREGEN_KEYS_1024)
+static crypto_pk_t *pregen_keys_1024[N_PREGEN_KEYS_1024];
+static int next_key_idx_1024;
+#define N_PREGEN_KEYS_2048 ARRAY_LENGTH(PREGEN_KEYS_2048)
+static crypto_pk_t *pregen_keys_2048[N_PREGEN_KEYS_2048];
+static int next_key_idx_2048;
+#endif
+
+/** Generate and return a new keypair for use in unit tests.  If we're using
+ * the key cache optimization, we might reuse keys. "idx" is ignored.
+ * Our only guarantee is that we won't reuse a key till this function has been
+ * called several times. The order in which keys are returned is slightly
+ * randomized, so that tests that depend on a particular order will not be
+ * reliable. */
+static crypto_pk_t *
+pk_generate_internal(int bits)
+{
+  tor_assert(bits == 2048 || bits == 1024);
+
+#ifdef USE_PREGENERATED_RSA_KEYS
+  int *idxp;
+  int n_pregen;
+  crypto_pk_t **pregen_array;
+  if (bits == 2048) {
+    idxp = &next_key_idx_2048;
+    n_pregen = N_PREGEN_KEYS_2048;
+    pregen_array = pregen_keys_2048;
+  } else {
+    idxp = &next_key_idx_1024;
+    n_pregen = N_PREGEN_KEYS_1024;
+    pregen_array = pregen_keys_1024;
+  }
+  /* Either skip 1 or 2 keys. */
+  *idxp += crypto_rand_int_range(1,3);
+  *idxp %= n_pregen;
+  return crypto_pk_dup_key(pregen_array[*idxp]);
+#else
+  crypto_pk_t *result;
+  int res;
+  result = crypto_pk_new();
+  res = crypto_pk_generate_key_with_bits__real(result, bits);
+  tor_assert(!res);
+  return result;
+#endif
+}
+
+crypto_pk_t *
+pk_generate(int idx)
+{
+  (void) idx;
+  return pk_generate_internal(1024);
+}
+
+#ifdef USE_PREGENERATED_RSA_KEYS
+static int
+crypto_pk_generate_key_with_bits__get_cached(crypto_pk_t *env, int bits)
+{
+  if (bits == 1024 || bits == 2048)  {
+    crypto_pk_t *newkey = pk_generate_internal(bits);
+    crypto_pk_assign_(env, newkey);
+    crypto_pk_free(newkey);
+  } else {
+    return crypto_pk_generate_key_with_bits__real(env, bits);
+  }
+  return 0;
+}
+#endif
+
+/** Free all storage used for the cached key optimization. */
+void
+free_pregenerated_keys(void)
+{
+#ifdef USE_PREGENERATED_RSA_KEYS
+  unsigned idx;
+  for (idx = 0; idx < N_PREGEN_KEYS_1024; ++idx) {
+    if (pregen_keys_1024[idx]) {
+      crypto_pk_free(pregen_keys_1024[idx]);
+      pregen_keys_1024[idx] = NULL;
+    }
+  }
+  for (idx = 0; idx < N_PREGEN_KEYS_2048; ++idx) {
+    if (pregen_keys_2048[idx]) {
+      crypto_pk_free(pregen_keys_2048[idx]);
+      pregen_keys_2048[idx] = NULL;
+    }
+  }
+#endif
+}
+
+void
+init_pregenerated_keys(void)
+{
+#ifdef USE_PREGENERATED_RSA_KEYS
+  const char *s;
+  crypto_pk_t *pk;
+  unsigned i;
+  for (i = 0; i < N_PREGEN_KEYS_1024; ++i) {
+    pk = pregen_keys_1024[i] = crypto_pk_new();
+    s = PREGEN_KEYS_1024[i];
+    int r = crypto_pk_read_private_key_from_string(pk, s, strlen(s));
+    tor_assert(r == 0);
+  }
+  for (i = 0; i < N_PREGEN_KEYS_2048; ++i) {
+    pk = pregen_keys_2048[i] = crypto_pk_new();
+    s = PREGEN_KEYS_2048[i];
+    int r = crypto_pk_read_private_key_from_string(pk, s, strlen(s));
+    tor_assert(r == 0);
+  }
+
+  MOCK(crypto_pk_generate_key_with_bits,
+       crypto_pk_generate_key_with_bits__get_cached);
+#endif
+}