From 8b2fe3add686db5cbd977e75d3bef02fa4c98c8f Mon Sep 17 00:00:00 2001
From: Thomas Pornin <pornin@bolet.org>
Date: Sun, 19 Mar 2017 14:55:11 -0400
Subject: [PATCH] New "i62" code for big integers with 64x64->128 opcodes; also
 improved "i31" modular exponentiation.

---
 inc/bearssl_rsa.h                    | 117 +++++++
 mk/Rules.mk                          |  20 +-
 mk/mkrules.sh                        |   6 +
 src/inner.h                          |  22 ++
 src/int/i31_modpow2.c                | 160 +++++++++
 src/int/i62_modpow2.c                | 479 +++++++++++++++++++++++++++
 src/rsa/rsa_default_pkcs1_sign.c     |   4 +-
 src/rsa/rsa_default_pkcs1_vrfy.c     |   4 +-
 src/rsa/rsa_default_priv.c           |   4 +-
 src/rsa/rsa_default_pub.c            |   4 +-
 src/rsa/rsa_i31_priv.c               |  96 +++---
 src/rsa/rsa_i31_pub.c                |  39 ++-
 src/rsa/rsa_i62_pkcs1_sign.c         |  57 ++++
 src/rsa/rsa_i62_pkcs1_vrfy.c         |  63 ++++
 src/rsa/rsa_i62_priv.c               | 186 +++++++++++
 src/rsa/rsa_i62_pub.c                | 125 +++++++
 src/ssl/ssl_client_default_rsapub.c  |   6 +-
 src/ssl/ssl_engine_default_rsavrfy.c |   6 +-
 src/ssl/ssl_server_full_rsa.c        |   8 +-
 test/test_crypto.c                   | 133 ++++++++
 test/test_speed.c                    |  16 +
 tools/names.c                        |  22 +-
 22 files changed, 1504 insertions(+), 73 deletions(-)
 create mode 100644 src/int/i31_modpow2.c
 create mode 100644 src/int/i62_modpow2.c
 create mode 100644 src/rsa/rsa_i62_pkcs1_sign.c
 create mode 100644 src/rsa/rsa_i62_pkcs1_vrfy.c
 create mode 100644 src/rsa/rsa_i62_priv.c
 create mode 100644 src/rsa/rsa_i62_pub.c

diff --git a/inc/bearssl_rsa.h b/inc/bearssl_rsa.h
index 9e5b418..8c79157 100644
--- a/inc/bearssl_rsa.h
+++ b/inc/bearssl_rsa.h
@@ -133,6 +133,11 @@
  *     carry propagation easier) for a similar code footprint, but uses
  *     very slightly larger stack buffers (about 4% bigger).
  *
+ *   - The **i62** implementation is similar to the i31 implementation,
+ *     except that it internally leverages the 64x64->128 multiplication
+ *     opcode. This implementation is available only on architectures
+ *     where such an opcode exists. It is much faster than i31.
+ *
  *   - The **i15** implementation uses 16-bit integers, each containing
  *     15 bits worth of integer data. Multiplication results fit on
  *     32 bits, so this won't use the "widening" multiplication routine
@@ -451,6 +456,118 @@ uint32_t br_rsa_i31_pkcs1_sign(const unsigned char *hash_oid,
 	const unsigned char *hash, size_t hash_len,
 	const br_rsa_private_key *sk, unsigned char *x);
 
+/*
+ * RSA "i62" engine. Similar to i31, but internal multiplication use
+ * 64x64->128 multiplications. This is available only on architecture
+ * that offer such an opcode.
+ */
+
+/**
+ * \brief RSA public key engine "i62".
+ *
+ * This function is defined only on architecture that offer a 64x64->128
+ * opcode. Use `br_rsa_i62_public_get()` to dynamically obtain a pointer
+ * to that functiom.
+ *
+ * \see br_rsa_public
+ *
+ * \param x      operand to exponentiate.
+ * \param xlen   length of the operand (in bytes).
+ * \param pk     RSA public key.
+ * \return  1 on success, 0 on error.
+ */
+uint32_t br_rsa_i62_public(unsigned char *x, size_t xlen,
+	const br_rsa_public_key *pk);
+
+/**
+ * \brief RSA signature verification engine "i62".
+ *
+ * This function is defined only on architecture that offer a 64x64->128
+ * opcode. Use `br_rsa_i62_pkcs1_vrfy_get()` to dynamically obtain a pointer
+ * to that functiom.
+ *
+ * \see br_rsa_pkcs1_vrfy
+ *
+ * \param x          signature buffer.
+ * \param xlen       signature length (in bytes).
+ * \param hash_oid   encoded hash algorithm OID (or `NULL`).
+ * \param hash_len   expected hash value length (in bytes).
+ * \param pk         RSA public key.
+ * \param hash_out   output buffer for the hash value.
+ * \return  1 on success, 0 on error.
+ */
+uint32_t br_rsa_i62_pkcs1_vrfy(const unsigned char *x, size_t xlen,
+	const unsigned char *hash_oid, size_t hash_len,
+	const br_rsa_public_key *pk, unsigned char *hash_out);
+
+/**
+ * \brief RSA private key engine "i62".
+ *
+ * This function is defined only on architecture that offer a 64x64->128
+ * opcode. Use `br_rsa_i62_private_get()` to dynamically obtain a pointer
+ * to that functiom.
+ *
+ * \see br_rsa_private
+ *
+ * \param x    operand to exponentiate.
+ * \param sk   RSA private key.
+ * \return  1 on success, 0 on error.
+ */
+uint32_t br_rsa_i62_private(unsigned char *x,
+	const br_rsa_private_key *sk);
+
+/**
+ * \brief RSA signature generation engine "i62".
+ *
+ * This function is defined only on architecture that offer a 64x64->128
+ * opcode. Use `br_rsa_i62_pkcs1_sign_get()` to dynamically obtain a pointer
+ * to that functiom.
+ *
+ * \see br_rsa_pkcs1_sign
+ *
+ * \param hash_oid   encoded hash algorithm OID (or `NULL`).
+ * \param hash       hash value.
+ * \param hash_len   hash value length (in bytes).
+ * \param sk         RSA private key.
+ * \param x          output buffer for the hash value.
+ * \return  1 on success, 0 on error.
+ */
+uint32_t br_rsa_i62_pkcs1_sign(const unsigned char *hash_oid,
+	const unsigned char *hash, size_t hash_len,
+	const br_rsa_private_key *sk, unsigned char *x);
+
+/**
+ * \brief Get the RSA "i62" implementation (public key operations),
+ * if available.
+ *
+ * \return  the implementation, or 0.
+ */
+br_rsa_public br_rsa_i62_public_get(void);
+
+/**
+ * \brief Get the RSA "i62" implementation (PKCS#1 signature verification),
+ * if available.
+ *
+ * \return  the implementation, or 0.
+ */
+br_rsa_pkcs1_vrfy br_rsa_i62_pkcs1_vrfy_get(void);
+
+/**
+ * \brief Get the RSA "i62" implementation (private key operations),
+ * if available.
+ *
+ * \return  the implementation, or 0.
+ */
+br_rsa_private br_rsa_i62_private_get(void);
+
+/**
+ * \brief Get the RSA "i62" implementation (PKCS#1 signature generation),
+ * if available.
+ *
+ * \return  the implementation, or 0.
+ */
+br_rsa_pkcs1_sign br_rsa_i62_pkcs1_sign_get(void);
+
 /*
  * RSA "i15" engine. Integers are represented as 15-bit integers, so
  * the code uses only 32-bit multiplication (no 64-bit result), which
diff --git a/mk/Rules.mk b/mk/Rules.mk
index e8ac590..891f7cf 100644
--- a/mk/Rules.mk
+++ b/mk/Rules.mk
@@ -1,6 +1,6 @@
 # Automatically generated rules. Use 'mkrules.sh' to modify/regenerate.
 
-OBJ = $(OBJDIR)$Pccopy$O $(OBJDIR)$Pdec16be$O $(OBJDIR)$Pdec16le$O $(OBJDIR)$Pdec32be$O $(OBJDIR)$Pdec32le$O $(OBJDIR)$Pdec64be$O $(OBJDIR)$Pdec64le$O $(OBJDIR)$Penc16be$O $(OBJDIR)$Penc16le$O $(OBJDIR)$Penc32be$O $(OBJDIR)$Penc32le$O $(OBJDIR)$Penc64be$O $(OBJDIR)$Penc64le$O $(OBJDIR)$Ppemdec$O $(OBJDIR)$Pec_all_m15$O $(OBJDIR)$Pec_all_m31$O $(OBJDIR)$Pec_c25519_i15$O $(OBJDIR)$Pec_c25519_i31$O $(OBJDIR)$Pec_c25519_m15$O $(OBJDIR)$Pec_c25519_m31$O $(OBJDIR)$Pec_curve25519$O $(OBJDIR)$Pec_default$O $(OBJDIR)$Pec_p256_m15$O $(OBJDIR)$Pec_p256_m31$O $(OBJDIR)$Pec_prime_i15$O $(OBJDIR)$Pec_prime_i31$O $(OBJDIR)$Pec_secp256r1$O $(OBJDIR)$Pec_secp384r1$O $(OBJDIR)$Pec_secp521r1$O $(OBJDIR)$Pecdsa_atr$O $(OBJDIR)$Pecdsa_default_sign_asn1$O $(OBJDIR)$Pecdsa_default_sign_raw$O $(OBJDIR)$Pecdsa_default_vrfy_asn1$O $(OBJDIR)$Pecdsa_default_vrfy_raw$O $(OBJDIR)$Pecdsa_i15_bits$O $(OBJDIR)$Pecdsa_i15_sign_asn1$O $(OBJDIR)$Pecdsa_i15_sign_raw$O $(OBJDIR)$Pecdsa_i15_vrfy_asn1$O $(OBJDIR)$Pecdsa_i15_vrfy_raw$O $(OBJDIR)$Pecdsa_i31_bits$O $(OBJDIR)$Pecdsa_i31_sign_asn1$O $(OBJDIR)$Pecdsa_i31_sign_raw$O $(OBJDIR)$Pecdsa_i31_vrfy_asn1$O $(OBJDIR)$Pecdsa_i31_vrfy_raw$O $(OBJDIR)$Pecdsa_rta$O $(OBJDIR)$Pdig_oid$O $(OBJDIR)$Pdig_size$O $(OBJDIR)$Pghash_ctmul$O $(OBJDIR)$Pghash_ctmul32$O $(OBJDIR)$Pghash_ctmul64$O $(OBJDIR)$Pghash_pclmul$O $(OBJDIR)$Pghash_pwr8$O $(OBJDIR)$Pmd5$O $(OBJDIR)$Pmd5sha1$O $(OBJDIR)$Pmultihash$O $(OBJDIR)$Psha1$O $(OBJDIR)$Psha2big$O $(OBJDIR)$Psha2small$O $(OBJDIR)$Pi15_add$O $(OBJDIR)$Pi15_bitlen$O $(OBJDIR)$Pi15_decmod$O $(OBJDIR)$Pi15_decode$O $(OBJDIR)$Pi15_decred$O $(OBJDIR)$Pi15_encode$O $(OBJDIR)$Pi15_fmont$O $(OBJDIR)$Pi15_iszero$O $(OBJDIR)$Pi15_modpow$O $(OBJDIR)$Pi15_modpow2$O $(OBJDIR)$Pi15_montmul$O $(OBJDIR)$Pi15_mulacc$O $(OBJDIR)$Pi15_muladd$O $(OBJDIR)$Pi15_ninv15$O $(OBJDIR)$Pi15_reduce$O $(OBJDIR)$Pi15_rshift$O $(OBJDIR)$Pi15_sub$O $(OBJDIR)$Pi15_tmont$O $(OBJDIR)$Pi31_add$O $(OBJDIR)$Pi31_bitlen$O $(OBJDIR)$Pi31_decmod$O $(OBJDIR)$Pi31_decode$O $(OBJDIR)$Pi31_decred$O $(OBJDIR)$Pi31_encode$O $(OBJDIR)$Pi31_fmont$O $(OBJDIR)$Pi31_iszero$O $(OBJDIR)$Pi31_modpow$O $(OBJDIR)$Pi31_montmul$O $(OBJDIR)$Pi31_mulacc$O $(OBJDIR)$Pi31_muladd$O $(OBJDIR)$Pi31_ninv31$O $(OBJDIR)$Pi31_reduce$O $(OBJDIR)$Pi31_rshift$O $(OBJDIR)$Pi31_sub$O $(OBJDIR)$Pi31_tmont$O $(OBJDIR)$Pi32_add$O $(OBJDIR)$Pi32_bitlen$O $(OBJDIR)$Pi32_decmod$O $(OBJDIR)$Pi32_decode$O $(OBJDIR)$Pi32_decred$O $(OBJDIR)$Pi32_div32$O $(OBJDIR)$Pi32_encode$O $(OBJDIR)$Pi32_fmont$O $(OBJDIR)$Pi32_iszero$O $(OBJDIR)$Pi32_modpow$O $(OBJDIR)$Pi32_montmul$O $(OBJDIR)$Pi32_mulacc$O $(OBJDIR)$Pi32_muladd$O $(OBJDIR)$Pi32_ninv32$O $(OBJDIR)$Pi32_reduce$O $(OBJDIR)$Pi32_sub$O $(OBJDIR)$Pi32_tmont$O $(OBJDIR)$Phmac$O $(OBJDIR)$Phmac_ct$O $(OBJDIR)$Phmac_drbg$O $(OBJDIR)$Prsa_default_pkcs1_sign$O $(OBJDIR)$Prsa_default_pkcs1_vrfy$O $(OBJDIR)$Prsa_default_priv$O $(OBJDIR)$Prsa_default_pub$O $(OBJDIR)$Prsa_i15_pkcs1_sign$O $(OBJDIR)$Prsa_i15_pkcs1_vrfy$O $(OBJDIR)$Prsa_i15_priv$O $(OBJDIR)$Prsa_i15_pub$O $(OBJDIR)$Prsa_i31_pkcs1_sign$O $(OBJDIR)$Prsa_i31_pkcs1_vrfy$O $(OBJDIR)$Prsa_i31_priv$O $(OBJDIR)$Prsa_i31_pub$O $(OBJDIR)$Prsa_i32_pkcs1_sign$O $(OBJDIR)$Prsa_i32_pkcs1_vrfy$O $(OBJDIR)$Prsa_i32_priv$O $(OBJDIR)$Prsa_i32_pub$O $(OBJDIR)$Prsa_pkcs1_sig_pad$O $(OBJDIR)$Prsa_pkcs1_sig_unpad$O $(OBJDIR)$Prsa_ssl_decrypt$O $(OBJDIR)$Pprf$O $(OBJDIR)$Pprf_md5sha1$O $(OBJDIR)$Pprf_sha256$O $(OBJDIR)$Pprf_sha384$O $(OBJDIR)$Pssl_ccert_single_ec$O $(OBJDIR)$Pssl_ccert_single_rsa$O $(OBJDIR)$Pssl_client$O $(OBJDIR)$Pssl_client_default_rsapub$O $(OBJDIR)$Pssl_client_full$O $(OBJDIR)$Pssl_engine$O $(OBJDIR)$Pssl_engine_default_aescbc$O $(OBJDIR)$Pssl_engine_default_aesgcm$O $(OBJDIR)$Pssl_engine_default_chapol$O $(OBJDIR)$Pssl_engine_default_descbc$O $(OBJDIR)$Pssl_engine_default_ec$O $(OBJDIR)$Pssl_engine_default_ecdsa$O $(OBJDIR)$Pssl_engine_default_rsavrfy$O $(OBJDIR)$Pssl_hashes$O $(OBJDIR)$Pssl_hs_client$O $(OBJDIR)$Pssl_hs_server$O $(OBJDIR)$Pssl_io$O $(OBJDIR)$Pssl_lru$O $(OBJDIR)$Pssl_rec_cbc$O $(OBJDIR)$Pssl_rec_chapol$O $(OBJDIR)$Pssl_rec_gcm$O $(OBJDIR)$Pssl_scert_single_ec$O $(OBJDIR)$Pssl_scert_single_rsa$O $(OBJDIR)$Pssl_server$O $(OBJDIR)$Pssl_server_full_ec$O $(OBJDIR)$Pssl_server_full_rsa$O $(OBJDIR)$Pssl_server_mine2c$O $(OBJDIR)$Pssl_server_mine2g$O $(OBJDIR)$Pssl_server_minf2c$O $(OBJDIR)$Pssl_server_minf2g$O $(OBJDIR)$Pssl_server_minr2g$O $(OBJDIR)$Pssl_server_minu2g$O $(OBJDIR)$Pssl_server_minv2g$O $(OBJDIR)$Paes_big_cbcdec$O $(OBJDIR)$Paes_big_cbcenc$O $(OBJDIR)$Paes_big_ctr$O $(OBJDIR)$Paes_big_dec$O $(OBJDIR)$Paes_big_enc$O $(OBJDIR)$Paes_common$O $(OBJDIR)$Paes_ct$O $(OBJDIR)$Paes_ct64$O $(OBJDIR)$Paes_ct64_cbcdec$O $(OBJDIR)$Paes_ct64_cbcenc$O $(OBJDIR)$Paes_ct64_ctr$O $(OBJDIR)$Paes_ct64_dec$O $(OBJDIR)$Paes_ct64_enc$O $(OBJDIR)$Paes_ct_cbcdec$O $(OBJDIR)$Paes_ct_cbcenc$O $(OBJDIR)$Paes_ct_ctr$O $(OBJDIR)$Paes_ct_dec$O $(OBJDIR)$Paes_ct_enc$O $(OBJDIR)$Paes_pwr8$O $(OBJDIR)$Paes_pwr8_cbcdec$O $(OBJDIR)$Paes_pwr8_cbcenc$O $(OBJDIR)$Paes_pwr8_ctr$O $(OBJDIR)$Paes_small_cbcdec$O $(OBJDIR)$Paes_small_cbcenc$O $(OBJDIR)$Paes_small_ctr$O $(OBJDIR)$Paes_small_dec$O $(OBJDIR)$Paes_small_enc$O $(OBJDIR)$Paes_x86ni$O $(OBJDIR)$Paes_x86ni_cbcdec$O $(OBJDIR)$Paes_x86ni_cbcenc$O $(OBJDIR)$Paes_x86ni_ctr$O $(OBJDIR)$Pchacha20_ct$O $(OBJDIR)$Pdes_ct$O $(OBJDIR)$Pdes_ct_cbcdec$O $(OBJDIR)$Pdes_ct_cbcenc$O $(OBJDIR)$Pdes_support$O $(OBJDIR)$Pdes_tab$O $(OBJDIR)$Pdes_tab_cbcdec$O $(OBJDIR)$Pdes_tab_cbcenc$O $(OBJDIR)$Ppoly1305_ctmul$O $(OBJDIR)$Ppoly1305_ctmul32$O $(OBJDIR)$Ppoly1305_ctmulq$O $(OBJDIR)$Ppoly1305_i15$O $(OBJDIR)$Pskey_decoder$O $(OBJDIR)$Px509_decoder$O $(OBJDIR)$Px509_knownkey$O $(OBJDIR)$Px509_minimal$O $(OBJDIR)$Px509_minimal_full$O
+OBJ = $(OBJDIR)$Pccopy$O $(OBJDIR)$Pdec16be$O $(OBJDIR)$Pdec16le$O $(OBJDIR)$Pdec32be$O $(OBJDIR)$Pdec32le$O $(OBJDIR)$Pdec64be$O $(OBJDIR)$Pdec64le$O $(OBJDIR)$Penc16be$O $(OBJDIR)$Penc16le$O $(OBJDIR)$Penc32be$O $(OBJDIR)$Penc32le$O $(OBJDIR)$Penc64be$O $(OBJDIR)$Penc64le$O $(OBJDIR)$Ppemdec$O $(OBJDIR)$Pec_all_m15$O $(OBJDIR)$Pec_all_m31$O $(OBJDIR)$Pec_c25519_i15$O $(OBJDIR)$Pec_c25519_i31$O $(OBJDIR)$Pec_c25519_m15$O $(OBJDIR)$Pec_c25519_m31$O $(OBJDIR)$Pec_curve25519$O $(OBJDIR)$Pec_default$O $(OBJDIR)$Pec_p256_m15$O $(OBJDIR)$Pec_p256_m31$O $(OBJDIR)$Pec_prime_i15$O $(OBJDIR)$Pec_prime_i31$O $(OBJDIR)$Pec_secp256r1$O $(OBJDIR)$Pec_secp384r1$O $(OBJDIR)$Pec_secp521r1$O $(OBJDIR)$Pecdsa_atr$O $(OBJDIR)$Pecdsa_default_sign_asn1$O $(OBJDIR)$Pecdsa_default_sign_raw$O $(OBJDIR)$Pecdsa_default_vrfy_asn1$O $(OBJDIR)$Pecdsa_default_vrfy_raw$O $(OBJDIR)$Pecdsa_i15_bits$O $(OBJDIR)$Pecdsa_i15_sign_asn1$O $(OBJDIR)$Pecdsa_i15_sign_raw$O $(OBJDIR)$Pecdsa_i15_vrfy_asn1$O $(OBJDIR)$Pecdsa_i15_vrfy_raw$O $(OBJDIR)$Pecdsa_i31_bits$O $(OBJDIR)$Pecdsa_i31_sign_asn1$O $(OBJDIR)$Pecdsa_i31_sign_raw$O $(OBJDIR)$Pecdsa_i31_vrfy_asn1$O $(OBJDIR)$Pecdsa_i31_vrfy_raw$O $(OBJDIR)$Pecdsa_rta$O $(OBJDIR)$Pdig_oid$O $(OBJDIR)$Pdig_size$O $(OBJDIR)$Pghash_ctmul$O $(OBJDIR)$Pghash_ctmul32$O $(OBJDIR)$Pghash_ctmul64$O $(OBJDIR)$Pghash_pclmul$O $(OBJDIR)$Pghash_pwr8$O $(OBJDIR)$Pmd5$O $(OBJDIR)$Pmd5sha1$O $(OBJDIR)$Pmultihash$O $(OBJDIR)$Psha1$O $(OBJDIR)$Psha2big$O $(OBJDIR)$Psha2small$O $(OBJDIR)$Pi15_add$O $(OBJDIR)$Pi15_bitlen$O $(OBJDIR)$Pi15_decmod$O $(OBJDIR)$Pi15_decode$O $(OBJDIR)$Pi15_decred$O $(OBJDIR)$Pi15_encode$O $(OBJDIR)$Pi15_fmont$O $(OBJDIR)$Pi15_iszero$O $(OBJDIR)$Pi15_modpow$O $(OBJDIR)$Pi15_modpow2$O $(OBJDIR)$Pi15_montmul$O $(OBJDIR)$Pi15_mulacc$O $(OBJDIR)$Pi15_muladd$O $(OBJDIR)$Pi15_ninv15$O $(OBJDIR)$Pi15_reduce$O $(OBJDIR)$Pi15_rshift$O $(OBJDIR)$Pi15_sub$O $(OBJDIR)$Pi15_tmont$O $(OBJDIR)$Pi31_add$O $(OBJDIR)$Pi31_bitlen$O $(OBJDIR)$Pi31_decmod$O $(OBJDIR)$Pi31_decode$O $(OBJDIR)$Pi31_decred$O $(OBJDIR)$Pi31_encode$O $(OBJDIR)$Pi31_fmont$O $(OBJDIR)$Pi31_iszero$O $(OBJDIR)$Pi31_modpow$O $(OBJDIR)$Pi31_modpow2$O $(OBJDIR)$Pi31_montmul$O $(OBJDIR)$Pi31_mulacc$O $(OBJDIR)$Pi31_muladd$O $(OBJDIR)$Pi31_ninv31$O $(OBJDIR)$Pi31_reduce$O $(OBJDIR)$Pi31_rshift$O $(OBJDIR)$Pi31_sub$O $(OBJDIR)$Pi31_tmont$O $(OBJDIR)$Pi32_add$O $(OBJDIR)$Pi32_bitlen$O $(OBJDIR)$Pi32_decmod$O $(OBJDIR)$Pi32_decode$O $(OBJDIR)$Pi32_decred$O $(OBJDIR)$Pi32_div32$O $(OBJDIR)$Pi32_encode$O $(OBJDIR)$Pi32_fmont$O $(OBJDIR)$Pi32_iszero$O $(OBJDIR)$Pi32_modpow$O $(OBJDIR)$Pi32_montmul$O $(OBJDIR)$Pi32_mulacc$O $(OBJDIR)$Pi32_muladd$O $(OBJDIR)$Pi32_ninv32$O $(OBJDIR)$Pi32_reduce$O $(OBJDIR)$Pi32_sub$O $(OBJDIR)$Pi32_tmont$O $(OBJDIR)$Pi62_modpow2$O $(OBJDIR)$Phmac$O $(OBJDIR)$Phmac_ct$O $(OBJDIR)$Phmac_drbg$O $(OBJDIR)$Prsa_default_pkcs1_sign$O $(OBJDIR)$Prsa_default_pkcs1_vrfy$O $(OBJDIR)$Prsa_default_priv$O $(OBJDIR)$Prsa_default_pub$O $(OBJDIR)$Prsa_i15_pkcs1_sign$O $(OBJDIR)$Prsa_i15_pkcs1_vrfy$O $(OBJDIR)$Prsa_i15_priv$O $(OBJDIR)$Prsa_i15_pub$O $(OBJDIR)$Prsa_i31_pkcs1_sign$O $(OBJDIR)$Prsa_i31_pkcs1_vrfy$O $(OBJDIR)$Prsa_i31_priv$O $(OBJDIR)$Prsa_i31_pub$O $(OBJDIR)$Prsa_i32_pkcs1_sign$O $(OBJDIR)$Prsa_i32_pkcs1_vrfy$O $(OBJDIR)$Prsa_i32_priv$O $(OBJDIR)$Prsa_i32_pub$O $(OBJDIR)$Prsa_i62_pkcs1_sign$O $(OBJDIR)$Prsa_i62_pkcs1_vrfy$O $(OBJDIR)$Prsa_i62_priv$O $(OBJDIR)$Prsa_i62_pub$O $(OBJDIR)$Prsa_pkcs1_sig_pad$O $(OBJDIR)$Prsa_pkcs1_sig_unpad$O $(OBJDIR)$Prsa_ssl_decrypt$O $(OBJDIR)$Pprf$O $(OBJDIR)$Pprf_md5sha1$O $(OBJDIR)$Pprf_sha256$O $(OBJDIR)$Pprf_sha384$O $(OBJDIR)$Pssl_ccert_single_ec$O $(OBJDIR)$Pssl_ccert_single_rsa$O $(OBJDIR)$Pssl_client$O $(OBJDIR)$Pssl_client_default_rsapub$O $(OBJDIR)$Pssl_client_full$O $(OBJDIR)$Pssl_engine$O $(OBJDIR)$Pssl_engine_default_aescbc$O $(OBJDIR)$Pssl_engine_default_aesgcm$O $(OBJDIR)$Pssl_engine_default_chapol$O $(OBJDIR)$Pssl_engine_default_descbc$O $(OBJDIR)$Pssl_engine_default_ec$O $(OBJDIR)$Pssl_engine_default_ecdsa$O $(OBJDIR)$Pssl_engine_default_rsavrfy$O $(OBJDIR)$Pssl_hashes$O $(OBJDIR)$Pssl_hs_client$O $(OBJDIR)$Pssl_hs_server$O $(OBJDIR)$Pssl_io$O $(OBJDIR)$Pssl_lru$O $(OBJDIR)$Pssl_rec_cbc$O $(OBJDIR)$Pssl_rec_chapol$O $(OBJDIR)$Pssl_rec_gcm$O $(OBJDIR)$Pssl_scert_single_ec$O $(OBJDIR)$Pssl_scert_single_rsa$O $(OBJDIR)$Pssl_server$O $(OBJDIR)$Pssl_server_full_ec$O $(OBJDIR)$Pssl_server_full_rsa$O $(OBJDIR)$Pssl_server_mine2c$O $(OBJDIR)$Pssl_server_mine2g$O $(OBJDIR)$Pssl_server_minf2c$O $(OBJDIR)$Pssl_server_minf2g$O $(OBJDIR)$Pssl_server_minr2g$O $(OBJDIR)$Pssl_server_minu2g$O $(OBJDIR)$Pssl_server_minv2g$O $(OBJDIR)$Paes_big_cbcdec$O $(OBJDIR)$Paes_big_cbcenc$O $(OBJDIR)$Paes_big_ctr$O $(OBJDIR)$Paes_big_dec$O $(OBJDIR)$Paes_big_enc$O $(OBJDIR)$Paes_common$O $(OBJDIR)$Paes_ct$O $(OBJDIR)$Paes_ct64$O $(OBJDIR)$Paes_ct64_cbcdec$O $(OBJDIR)$Paes_ct64_cbcenc$O $(OBJDIR)$Paes_ct64_ctr$O $(OBJDIR)$Paes_ct64_dec$O $(OBJDIR)$Paes_ct64_enc$O $(OBJDIR)$Paes_ct_cbcdec$O $(OBJDIR)$Paes_ct_cbcenc$O $(OBJDIR)$Paes_ct_ctr$O $(OBJDIR)$Paes_ct_dec$O $(OBJDIR)$Paes_ct_enc$O $(OBJDIR)$Paes_pwr8$O $(OBJDIR)$Paes_pwr8_cbcdec$O $(OBJDIR)$Paes_pwr8_cbcenc$O $(OBJDIR)$Paes_pwr8_ctr$O $(OBJDIR)$Paes_small_cbcdec$O $(OBJDIR)$Paes_small_cbcenc$O $(OBJDIR)$Paes_small_ctr$O $(OBJDIR)$Paes_small_dec$O $(OBJDIR)$Paes_small_enc$O $(OBJDIR)$Paes_x86ni$O $(OBJDIR)$Paes_x86ni_cbcdec$O $(OBJDIR)$Paes_x86ni_cbcenc$O $(OBJDIR)$Paes_x86ni_ctr$O $(OBJDIR)$Pchacha20_ct$O $(OBJDIR)$Pdes_ct$O $(OBJDIR)$Pdes_ct_cbcdec$O $(OBJDIR)$Pdes_ct_cbcenc$O $(OBJDIR)$Pdes_support$O $(OBJDIR)$Pdes_tab$O $(OBJDIR)$Pdes_tab_cbcdec$O $(OBJDIR)$Pdes_tab_cbcenc$O $(OBJDIR)$Ppoly1305_ctmul$O $(OBJDIR)$Ppoly1305_ctmul32$O $(OBJDIR)$Ppoly1305_ctmulq$O $(OBJDIR)$Ppoly1305_i15$O $(OBJDIR)$Pskey_decoder$O $(OBJDIR)$Px509_decoder$O $(OBJDIR)$Px509_knownkey$O $(OBJDIR)$Px509_minimal$O $(OBJDIR)$Px509_minimal_full$O
 OBJBRSSL = $(OBJDIR)$Pbrssl$O $(OBJDIR)$Pcerts$O $(OBJDIR)$Pchain$O $(OBJDIR)$Pclient$O $(OBJDIR)$Perrors$O $(OBJDIR)$Pfiles$O $(OBJDIR)$Pkeys$O $(OBJDIR)$Pnames$O $(OBJDIR)$Pserver$O $(OBJDIR)$Pskey$O $(OBJDIR)$Psslio$O $(OBJDIR)$Pta$O $(OBJDIR)$Pvector$O $(OBJDIR)$Pverify$O $(OBJDIR)$Pxmem$O
 OBJTESTCRYPTO = $(OBJDIR)$Ptest_crypto$O
 OBJTESTSPEED = $(OBJDIR)$Ptest_speed$O
@@ -314,6 +314,9 @@ $(OBJDIR)$Pi31_iszero$O: src$Pint$Pi31_iszero.c $(HEADERSPRIV)
 $(OBJDIR)$Pi31_modpow$O: src$Pint$Pi31_modpow.c $(HEADERSPRIV)
 	$(CC) $(CFLAGS) $(INCFLAGS) $(CCOUT)$(OBJDIR)$Pi31_modpow$O src$Pint$Pi31_modpow.c
 
+$(OBJDIR)$Pi31_modpow2$O: src$Pint$Pi31_modpow2.c $(HEADERSPRIV)
+	$(CC) $(CFLAGS) $(INCFLAGS) $(CCOUT)$(OBJDIR)$Pi31_modpow2$O src$Pint$Pi31_modpow2.c
+
 $(OBJDIR)$Pi31_montmul$O: src$Pint$Pi31_montmul.c $(HEADERSPRIV)
 	$(CC) $(CFLAGS) $(INCFLAGS) $(CCOUT)$(OBJDIR)$Pi31_montmul$O src$Pint$Pi31_montmul.c
 
@@ -389,6 +392,9 @@ $(OBJDIR)$Pi32_sub$O: src$Pint$Pi32_sub.c $(HEADERSPRIV)
 $(OBJDIR)$Pi32_tmont$O: src$Pint$Pi32_tmont.c $(HEADERSPRIV)
 	$(CC) $(CFLAGS) $(INCFLAGS) $(CCOUT)$(OBJDIR)$Pi32_tmont$O src$Pint$Pi32_tmont.c
 
+$(OBJDIR)$Pi62_modpow2$O: src$Pint$Pi62_modpow2.c $(HEADERSPRIV)
+	$(CC) $(CFLAGS) $(INCFLAGS) $(CCOUT)$(OBJDIR)$Pi62_modpow2$O src$Pint$Pi62_modpow2.c
+
 $(OBJDIR)$Phmac$O: src$Pmac$Phmac.c $(HEADERSPRIV)
 	$(CC) $(CFLAGS) $(INCFLAGS) $(CCOUT)$(OBJDIR)$Phmac$O src$Pmac$Phmac.c
 
@@ -446,6 +452,18 @@ $(OBJDIR)$Prsa_i32_priv$O: src$Prsa$Prsa_i32_priv.c $(HEADERSPRIV)
 $(OBJDIR)$Prsa_i32_pub$O: src$Prsa$Prsa_i32_pub.c $(HEADERSPRIV)
 	$(CC) $(CFLAGS) $(INCFLAGS) $(CCOUT)$(OBJDIR)$Prsa_i32_pub$O src$Prsa$Prsa_i32_pub.c
 
+$(OBJDIR)$Prsa_i62_pkcs1_sign$O: src$Prsa$Prsa_i62_pkcs1_sign.c $(HEADERSPRIV)
+	$(CC) $(CFLAGS) $(INCFLAGS) $(CCOUT)$(OBJDIR)$Prsa_i62_pkcs1_sign$O src$Prsa$Prsa_i62_pkcs1_sign.c
+
+$(OBJDIR)$Prsa_i62_pkcs1_vrfy$O: src$Prsa$Prsa_i62_pkcs1_vrfy.c $(HEADERSPRIV)
+	$(CC) $(CFLAGS) $(INCFLAGS) $(CCOUT)$(OBJDIR)$Prsa_i62_pkcs1_vrfy$O src$Prsa$Prsa_i62_pkcs1_vrfy.c
+
+$(OBJDIR)$Prsa_i62_priv$O: src$Prsa$Prsa_i62_priv.c $(HEADERSPRIV)
+	$(CC) $(CFLAGS) $(INCFLAGS) $(CCOUT)$(OBJDIR)$Prsa_i62_priv$O src$Prsa$Prsa_i62_priv.c
+
+$(OBJDIR)$Prsa_i62_pub$O: src$Prsa$Prsa_i62_pub.c $(HEADERSPRIV)
+	$(CC) $(CFLAGS) $(INCFLAGS) $(CCOUT)$(OBJDIR)$Prsa_i62_pub$O src$Prsa$Prsa_i62_pub.c
+
 $(OBJDIR)$Prsa_pkcs1_sig_pad$O: src$Prsa$Prsa_pkcs1_sig_pad.c $(HEADERSPRIV)
 	$(CC) $(CFLAGS) $(INCFLAGS) $(CCOUT)$(OBJDIR)$Prsa_pkcs1_sig_pad$O src$Prsa$Prsa_pkcs1_sig_pad.c
 
diff --git a/mk/mkrules.sh b/mk/mkrules.sh
index 7097d4d..b03566b 100755
--- a/mk/mkrules.sh
+++ b/mk/mkrules.sh
@@ -134,6 +134,7 @@ coresrc=" \
 	src/int/i31_fmont.c \
 	src/int/i31_iszero.c \
 	src/int/i31_modpow.c \
+	src/int/i31_modpow2.c \
 	src/int/i31_montmul.c \
 	src/int/i31_mulacc.c \
 	src/int/i31_muladd.c \
@@ -159,6 +160,7 @@ coresrc=" \
 	src/int/i32_reduce.c \
 	src/int/i32_sub.c \
 	src/int/i32_tmont.c \
+	src/int/i62_modpow2.c \
 	src/mac/hmac.c \
 	src/mac/hmac_ct.c \
 	src/rand/hmac_drbg.c \
@@ -178,6 +180,10 @@ coresrc=" \
 	src/rsa/rsa_i32_pkcs1_vrfy.c \
 	src/rsa/rsa_i32_priv.c \
 	src/rsa/rsa_i32_pub.c \
+	src/rsa/rsa_i62_pkcs1_sign.c \
+	src/rsa/rsa_i62_pkcs1_vrfy.c \
+	src/rsa/rsa_i62_priv.c \
+	src/rsa/rsa_i62_pub.c \
 	src/rsa/rsa_pkcs1_sig_pad.c \
 	src/rsa/rsa_pkcs1_sig_unpad.c \
 	src/rsa/rsa_ssl_decrypt.c \
diff --git a/src/inner.h b/src/inner.h
index 6095806..33901ab 100644
--- a/src/inner.h
+++ b/src/inner.h
@@ -1271,6 +1271,25 @@ void br_i31_from_monty(uint32_t *x, const uint32_t *m, uint32_t m0i);
 void br_i31_modpow(uint32_t *x, const unsigned char *e, size_t elen,
 	const uint32_t *m, uint32_t m0i, uint32_t *t1, uint32_t *t2);
 
+/*
+ * Compute a modular exponentiation. x[] MUST be an integer modulo m[]
+ * (same announced bit length, lower value). m[] MUST be odd. The
+ * exponent is in big-endian unsigned notation, over 'elen' bytes. The
+ * "m0i" parameter is equal to -(1/m0) mod 2^31, where m0 is the least
+ * significant value word of m[] (this works only if m[] is an odd
+ * integer). The tmp[] array is used for temporaries, and has size
+ * 'twlen' words; it must be large enough to accommodate at least two
+ * temporary values with the same size as m[] (including the leading
+ * "bit length" word). If there is room for more temporaries, then this
+ * function may use the extra room for window-based optimisation,
+ * resulting in faster computations.
+ *
+ * Returned value is 1 on success, 0 on error. An error is reported if
+ * the provided tmp[] array is too short.
+ */
+uint32_t br_i31_modpow_opt(uint32_t *x, const unsigned char *e, size_t elen,
+	const uint32_t *m, uint32_t m0i, uint32_t *tmp, size_t twlen);
+
 /*
  * Compute d+a*b, result in d. The initial announced bit length of d[]
  * MUST match that of a[]. The d[] array MUST be large enough to
@@ -1338,6 +1357,9 @@ void br_i15_reduce(uint16_t *x, const uint16_t *a, const uint16_t *m);
 
 void br_i15_mulacc(uint16_t *d, const uint16_t *a, const uint16_t *b);
 
+uint32_t br_i62_modpow_opt(uint32_t *x31, const unsigned char *e, size_t elen,
+	const uint32_t *m31, uint32_t m0i31, uint64_t *tmp, size_t twlen);
+
 /* ==================================================================== */
 
 static inline size_t
diff --git a/src/int/i31_modpow2.c b/src/int/i31_modpow2.c
new file mode 100644
index 0000000..23ae0cd
--- /dev/null
+++ b/src/int/i31_modpow2.c
@@ -0,0 +1,160 @@
+/*
+ * Copyright (c) 2017 Thomas Pornin <pornin@bolet.org>
+ *
+ * Permission is hereby granted, free of charge, to any person obtaining 
+ * a copy of this software and associated documentation files (the
+ * "Software"), to deal in the Software without restriction, including
+ * without limitation the rights to use, copy, modify, merge, publish,
+ * distribute, sublicense, and/or sell copies of the Software, and to
+ * permit persons to whom the Software is furnished to do so, subject to
+ * the following conditions:
+ *
+ * The above copyright notice and this permission notice shall be 
+ * included in all copies or substantial portions of the Software.
+ *
+ * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, 
+ * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
+ * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND 
+ * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS
+ * BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN
+ * ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
+ * CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
+ * SOFTWARE.
+ */
+
+#include "inner.h"
+
+/* see inner.h */
+uint32_t
+br_i31_modpow_opt(uint32_t *x,
+	const unsigned char *e, size_t elen,
+	const uint32_t *m, uint32_t m0i, uint32_t *tmp, size_t twlen)
+{
+	size_t mlen, mwlen;
+	uint32_t *t1, *t2, *base;
+	size_t u, v;
+	uint32_t acc;
+	int acc_len, win_len;
+
+	/*
+	 * Get modulus size.
+	 */
+	mwlen = (m[0] + 63) >> 5;
+	mlen = mwlen * sizeof m[0];
+	mwlen += (mwlen & 1);
+	t1 = tmp;
+	t2 = tmp + mwlen;
+
+	/*
+	 * Compute possible window size, with a maximum of 5 bits.
+	 * When the window has size 1 bit, we use a specific code
+	 * that requires only two temporaries. Otherwise, for a
+	 * window of k bits, we need 2^k+1 temporaries.
+	 */
+	if (twlen < (mwlen << 1)) {
+		return 0;
+	}
+	for (win_len = 5; win_len > 1; win_len --) {
+		if ((((uint32_t)1 << win_len) + 1) * mwlen <= twlen) {
+			break;
+		}
+	}
+
+	/*
+	 * Everything is done in Montgomery representation.
+	 */
+	br_i31_to_monty(x, m);
+
+	/*
+	 * Compute window contents. If the window has size one bit only,
+	 * then t2 is set to x; otherwise, t2[0] is left untouched, and
+	 * t2[k] is set to x^k (for k >= 1).
+	 */
+	if (win_len == 1) {
+		memcpy(t2, x, mlen);
+	} else {
+		memcpy(t2 + mwlen, x, mlen);
+		base = t2 + mwlen;
+		for (u = 2; u < ((unsigned)1 << win_len); u ++) {
+			br_i31_montymul(base + mwlen, base, x, m, m0i);
+			base += mwlen;
+		}
+	}
+
+	/*
+	 * We need to set x to 1, in Montgomery representation. This can
+	 * be done efficiently by setting the high word to 1, then doing
+	 * one word-sized shift.
+	 */
+	br_i31_zero(x, m[0]);
+	x[(m[0] + 31) >> 5] = 1;
+	br_i31_muladd_small(x, 0, m);
+
+	/*
+	 * We process bits from most to least significant. At each
+	 * loop iteration, we have acc_len bits in acc.
+	 */
+	acc = 0;
+	acc_len = 0;
+	while (acc_len > 0 || elen > 0) {
+		int i, k;
+		uint32_t bits;
+
+		/*
+		 * Get the next bits.
+		 */
+		k = win_len;
+		if (acc_len < win_len) {
+			if (elen > 0) {
+				acc = (acc << 8) | *e ++;
+				elen --;
+				acc_len += 8;
+			} else {
+				k = acc_len;
+			}
+		}
+		bits = (acc >> (acc_len - k)) & (((uint32_t)1 << k) - 1);
+		acc_len -= k;
+
+		/*
+		 * We could get exactly k bits. Compute k squarings.
+		 */
+		for (i = 0; i < k; i ++) {
+			br_i31_montymul(t1, x, x, m, m0i);
+			memcpy(x, t1, mlen);
+		}
+
+		/*
+		 * Window lookup: we want to set t2 to the window
+		 * lookup value, assuming the bits are non-zero. If
+		 * the window length is 1 bit only, then t2 is
+		 * already set; otherwise, we do a constant-time lookup.
+		 */
+		if (win_len > 1) {
+			br_i31_zero(t2, m[0]);
+			base = t2 + mwlen;
+			for (u = 1; u < ((uint32_t)1 << k); u ++) {
+				uint32_t m;
+
+				m = -EQ(u, bits);
+				for (v = 1; v < mwlen; v ++) {
+					t2[v] |= m & base[v];
+				}
+				base += mwlen;
+			}
+		}
+
+		/*
+		 * Multiply with the looked-up value. We keep the
+		 * product only if the exponent bits are not all-zero.
+		 */
+		br_i31_montymul(t1, x, t2, m, m0i);
+		CCOPY(NEQ(bits, 0), x, t1, mlen);
+	}
+
+	/*
+	 * Convert back from Montgomery representation, and exit.
+	 */
+	br_i31_from_monty(x, m, m0i);
+	return 1;
+}
diff --git a/src/int/i62_modpow2.c b/src/int/i62_modpow2.c
new file mode 100644
index 0000000..0414e5f
--- /dev/null
+++ b/src/int/i62_modpow2.c
@@ -0,0 +1,479 @@
+/*
+ * Copyright (c) 2017 Thomas Pornin <pornin@bolet.org>
+ *
+ * Permission is hereby granted, free of charge, to any person obtaining 
+ * a copy of this software and associated documentation files (the
+ * "Software"), to deal in the Software without restriction, including
+ * without limitation the rights to use, copy, modify, merge, publish,
+ * distribute, sublicense, and/or sell copies of the Software, and to
+ * permit persons to whom the Software is furnished to do so, subject to
+ * the following conditions:
+ *
+ * The above copyright notice and this permission notice shall be 
+ * included in all copies or substantial portions of the Software.
+ *
+ * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, 
+ * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
+ * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND 
+ * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS
+ * BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN
+ * ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
+ * CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
+ * SOFTWARE.
+ */
+
+#include "inner.h"
+
+#if BR_INT128 || BR_UMUL128
+
+#if BR_INT128
+
+/*
+ * Compute x*y+v1+v2. Operands are 64-bit, and result is 128-bit, with
+ * high word in "hi" and low word in "lo".
+ */
+#define FMA1(hi, lo, x, y, v1, v2)   do { \
+		unsigned __int128 fmaz; \
+		fmaz = (unsigned __int128)(x) * (unsigned __int128)(y) \
+			+ (unsigned __int128)(v1) + (unsigned __int128)(v2); \
+		(hi) = (uint64_t)(fmaz >> 64); \
+		(lo) = (uint64_t)fmaz; \
+	} while (0)
+
+/*
+ * Compute x1*y1+x2*y2+v1+v2. Operands are 64-bit, and result is 128-bit,
+ * with high word in "hi" and low word in "lo".
+ *
+ * Callers should ensure that the two inner products, and the v1 and v2
+ * operands, are multiple of 4 (this is not used by this specific definition
+ * but may help other implementations).
+ */
+#define FMA2(hi, lo, x1, y1, x2, y2, v1, v2)   do { \
+		unsigned __int128 fmaz; \
+		fmaz = (unsigned __int128)(x1) * (unsigned __int128)(y1) \
+			+ (unsigned __int128)(x2) * (unsigned __int128)(y2) \
+			+ (unsigned __int128)(v1) + (unsigned __int128)(v2); \
+		(hi) = (uint64_t)(fmaz >> 64); \
+		(lo) = (uint64_t)fmaz; \
+	} while (0)
+
+#elif BR_UMUL128
+
+#include <intrin.h>
+
+#define FMA1(hi, lo, x, y, v1, v2)   do { \
+		uint64_t fmahi, fmalo; \
+		unsigned char fmacc; \
+		fmalo = _umul128((x), (y), &fmahi); \
+		fmacc = _addcarry_u64(0, fmalo, (v1), &fmalo); \
+		_addcarry_u64(fmacc, fmahi, 0, &fmahi); \
+		fmacc = _addcarry_u64(0, fmalo, (v2), &(lo)); \
+		_addcarry_u64(fmacc, fmahi, 0, &(hi)); \
+	} while (0)
+
+/*
+ * Normally we should use _addcarry_u64() for FMA2 too, but it makes
+ * Visual Studio crash. Instead we use this version, which leverages
+ * the fact that the vx operands, and the products, are multiple of 4.
+ * This is unfortunately slower.
+ */
+#define FMA2(hi, lo, x1, y1, x2, y2, v1, v2)   do { \
+		uint64_t fma1hi, fma1lo; \
+		uint64_t fma2hi, fma2lo; \
+		uint64_t fmatt; \
+		fma1lo = _umul128((x1), (y1), &fma1hi); \
+		fma2lo = _umul128((x2), (y2), &fma2hi); \
+		fmatt = (fma1lo >> 2) + (fma2lo >> 2) \
+			+ ((v1) >> 2) + ((v2) >> 2); \
+		(lo) = fmatt << 2; \
+		(hi) = fma1hi + fma2hi + (fmatt >> 62); \
+	} while (0)
+
+/*
+ * The FMA2 macro definition we would prefer to use, but it triggers
+ * an internal compiler error in Visual Studio 2015.
+ *
+#define FMA2(hi, lo, x1, y1, x2, y2, v1, v2)   do { \
+		uint64_t fma1hi, fma1lo; \
+		uint64_t fma2hi, fma2lo; \
+		unsigned char fmacc; \
+		fma1lo = _umul128((x1), (y1), &fma1hi); \
+		fma2lo = _umul128((x2), (y2), &fma2hi); \
+		fmacc = _addcarry_u64(0, fma1lo, (v1), &fma1lo); \
+		_addcarry_u64(fmacc, fma1hi, 0, &fma1hi); \
+		fmacc = _addcarry_u64(0, fma2lo, (v2), &fma2lo); \
+		_addcarry_u64(fmacc, fma2hi, 0, &fma2hi); \
+		fmacc = _addcarry_u64(0, fma1lo, fma2lo, &(lo)); \
+		_addcarry_u64(fmacc, fma1hi, fma2hi, &(hi)); \
+	} while (0)
+ */
+
+#endif
+
+#define MASK62           ((uint64_t)0x3FFFFFFFFFFFFFFF)
+#define MUL62_lo(x, y)   (((uint64_t)(x) * (uint64_t)(y)) & MASK62)
+
+/*
+ * Subtract b from a, and return the final carry. If 'ctl32' is 0, then
+ * a[] is kept unmodified, but the final carry is still computed and
+ * returned.
+ */
+static uint32_t
+i62_sub(uint64_t *a, const uint64_t *b, size_t num, uint32_t ctl32)
+{
+	uint64_t cc, mask;
+	size_t u;
+
+	cc = 0;
+	ctl32 = -ctl32;
+	mask = (uint64_t)ctl32 | ((uint64_t)ctl32 << 32);
+	for (u = 0; u < num; u ++) {
+		uint64_t aw, bw, dw;
+
+		aw = a[u];
+		bw = b[u];
+		dw = aw - bw - cc;
+		cc = dw >> 63;
+		dw &= MASK62;
+		a[u] = aw ^ (mask & (dw ^ aw));
+	}
+	return (uint32_t)cc;
+}
+
+/*
+ * Montgomery multiplication, over arrays of 62-bit values. The
+ * destination array (d) must be distinct from the other operands
+ * (x, y and m). All arrays are in little-endian format (least
+ * significant word comes first) over 'num' words.
+ */
+static void
+montymul(uint64_t *d, const uint64_t *x, const uint64_t *y,
+	const uint64_t *m, size_t num, uint64_t m0i)
+{
+	uint64_t dh;
+	size_t u, num4;
+
+	num4 = 1 + ((num - 1) & ~(size_t)3);
+	memset(d, 0, num * sizeof *d);
+	dh = 0;
+	for (u = 0; u < num; u ++) {
+		size_t v;
+		uint64_t f, xu;
+		uint64_t r, zh;
+		uint64_t hi, lo;
+
+		xu = x[u] << 2;
+		f = MUL62_lo(d[0] + MUL62_lo(x[u], y[0]), m0i) << 2;
+
+		FMA2(hi, lo, xu, y[0], f, m[0], d[0] << 2, 0);
+		r = hi;
+
+		for (v = 1; v < num4; v += 4) {
+			FMA2(hi, lo, xu, y[v + 0],
+				f, m[v + 0], d[v + 0] << 2, r << 2);
+			r = hi + (r >> 62);
+			d[v - 1] = lo >> 2;
+			FMA2(hi, lo, xu, y[v + 1],
+				f, m[v + 1], d[v + 1] << 2, r << 2);
+			r = hi + (r >> 62);
+			d[v + 0] = lo >> 2;
+			FMA2(hi, lo, xu, y[v + 2],
+				f, m[v + 2], d[v + 2] << 2, r << 2);
+			r = hi + (r >> 62);
+			d[v + 1] = lo >> 2;
+			FMA2(hi, lo, xu, y[v + 3],
+				f, m[v + 3], d[v + 3] << 2, r << 2);
+			r = hi + (r >> 62);
+			d[v + 2] = lo >> 2;
+		}
+		for (; v < num; v ++) {
+			FMA2(hi, lo, xu, y[v], f, m[v], d[v] << 2, r << 2);
+			r = hi + (r >> 62);
+			d[v - 1] = lo >> 2;
+		}
+
+		zh = dh + r;
+		d[num - 1] = zh & MASK62;
+		dh = zh >> 62;
+	}
+	i62_sub(d, m, num, (uint32_t)dh | NOT(i62_sub(d, m, num, 0)));
+}
+
+/*
+ * Conversion back from Montgomery representation.
+ */
+static void
+frommonty(uint64_t *x, const uint64_t *m, size_t num, uint64_t m0i)
+{
+	size_t u, v;
+
+	for (u = 0; u < num; u ++) {
+		uint64_t f, cc;
+
+		f = MUL62_lo(x[0], m0i) << 2;
+		cc = 0;
+		for (v = 0; v < num; v ++) {
+			uint64_t hi, lo;
+
+			FMA1(hi, lo, f, m[v], x[v] << 2, cc);
+			cc = hi << 2;
+			if (v != 0) {
+				x[v - 1] = lo >> 2;
+			}
+		}
+		x[num - 1] = cc >> 2;
+	}
+	i62_sub(x, m, num, NOT(i62_sub(x, m, num, 0)));
+}
+
+/* see inner.h */
+uint32_t
+br_i62_modpow_opt(uint32_t *x31, const unsigned char *e, size_t elen,
+	const uint32_t *m31, uint32_t m0i31, uint64_t *tmp, size_t twlen)
+{
+	size_t u, mw31num, mw62num;
+	uint64_t *x, *m, *t1, *t2;
+	uint64_t m0i;
+	uint32_t acc;
+	int win_len, acc_len;
+
+	/*
+	 * Get modulus size, in words.
+	 */
+	mw31num = (m31[0] + 31) >> 5;
+	mw62num = (mw31num + 1) >> 1;
+
+	/*
+	 * In order to apply this function, we must have enough room tp
+	 * copy the operand and modulus into the temporary array, along
+	 * with at least two temporaries. If there is not enough room,
+	 * switch to br_i31_modpow(). We also use br_i31_modpow() if the
+	 * modulus length is not at least four words (94 bits or more).
+	 */
+	if (mw31num < 4 || (mw62num << 2) > twlen) {
+		/*
+		 * We assume here that we can split an aligned uint64_t
+		 * into two properly aligned uint32_t. Since both types
+		 * are supposed to have an exact width with no padding,
+		 * then this property must hold.
+		 */
+		size_t txlen;
+
+		txlen = mw31num + 1;
+		if (twlen < txlen) {
+			return 0;
+		}
+		br_i31_modpow(x31, e, elen, m31, m0i31,
+			(uint32_t *)tmp, (uint32_t *)tmp + txlen);
+		return 1;
+	}
+
+	/*
+	 * Convert x to Montgomery representation: this means that
+	 * we replace x with x*2^z mod m, where z is the smallest multiple
+	 * of the word size such that 2^z >= m. We want to reuse the 31-bit
+	 * functions here (for constant-time operation), but we need z
+	 * for a 62-bit word size.
+	 */
+	for (u = 0; u < mw62num; u ++) {
+		br_i31_muladd_small(x31, 0, m31);
+		br_i31_muladd_small(x31, 0, m31);
+	}
+
+	/*
+	 * Assemble operands into arrays of 62-bit words. Note that
+	 * all the arrays of 62-bit words that we will handle here
+	 * are without any leading size word.
+	 *
+	 * We also adjust tmp and twlen to account for the words used
+	 * for these extra arrays.
+	 */
+	m = tmp;
+	x = tmp + mw62num;
+	tmp += (mw62num << 1);
+	twlen -= (mw62num << 1);
+	for (u = 0; u < mw31num; u += 2) {
+		size_t v;
+
+		v = u >> 1;
+		if ((u + 1) == mw31num) {
+			m[v] = (uint64_t)m31[u + 1];
+			x[v] = (uint64_t)x31[u + 1];
+		} else {
+			m[v] = (uint64_t)m31[u + 1]
+				+ ((uint64_t)m31[u + 2] << 31);
+			x[v] = (uint64_t)x31[u + 1]
+				+ ((uint64_t)x31[u + 2] << 31);
+		}
+	}
+
+	/*
+	 * Compute window size. We support windows up to 5 bits; for a
+	 * window of size k bits, we need 2^k+1 temporaries (for k = 1,
+	 * we use special code that uses only 2 temporaries).
+	 */
+	for (win_len = 5; win_len > 1; win_len --) {
+		if ((((uint32_t)1 << win_len) + 1) * mw62num <= twlen) {
+			break;
+		}
+	}
+
+	t1 = tmp;
+	t2 = tmp + mw62num;
+
+	/*
+	 * Compute m0i, which is equal to -(1/m0) mod 2^62. We were
+	 * provided with m0i31, which already fulfills this property
+	 * modulo 2^31; the single expression below is then sufficient.
+	 */
+	m0i = (uint64_t)m0i31;
+	m0i = MUL62_lo(m0i, (uint64_t)2 + MUL62_lo(m0i, m[0]));
+
+	/*
+	 * Compute window contents. If the window has size one bit only,
+	 * then t2 is set to x; otherwise, t2[0] is left untouched, and
+	 * t2[k] is set to x^k (for k >= 1).
+	 */
+	if (win_len == 1) {
+		memcpy(t2, x, mw62num * sizeof *x);
+	} else {
+		uint64_t *base;
+
+		memcpy(t2 + mw62num, x, mw62num * sizeof *x);
+		base = t2 + mw62num;
+		for (u = 2; u < ((unsigned)1 << win_len); u ++) {
+			montymul(base + mw62num, base, x, m, mw62num, m0i);
+			base += mw62num;
+		}
+	}
+
+	/*
+	 * Set x to 1, in Montgomery representation. We again use the
+	 * 31-bit code.
+	 */
+	br_i31_zero(x31, m31[0]);
+	x31[(m31[0] + 31) >> 5] = 1;
+	br_i31_muladd_small(x31, 0, m31);
+	if (mw31num & 1) {
+		br_i31_muladd_small(x31, 0, m31);
+	}
+	for (u = 0; u < mw31num; u += 2) {
+		size_t v;
+
+		v = u >> 1;
+		if ((u + 1) == mw31num) {
+			x[v] = (uint64_t)x31[u + 1];
+		} else {
+			x[v] = (uint64_t)x31[u + 1]
+				+ ((uint64_t)x31[u + 2] << 31);
+		}
+	}
+
+	/*
+	 * We process bits from most to least significant. At each
+	 * loop iteration, we have acc_len bits in acc.
+	 */
+	acc = 0;
+	acc_len = 0;
+	while (acc_len > 0 || elen > 0) {
+		int i, k;
+		uint32_t bits;
+		uint64_t mask1, mask2;
+
+		/*
+		 * Get the next bits.
+		 */
+		k = win_len;
+		if (acc_len < win_len) {
+			if (elen > 0) {
+				acc = (acc << 8) | *e ++;
+				elen --;
+				acc_len += 8;
+			} else {
+				k = acc_len;
+			}
+		}
+		bits = (acc >> (acc_len - k)) & (((uint32_t)1 << k) - 1);
+		acc_len -= k;
+
+		/*
+		 * We could get exactly k bits. Compute k squarings.
+		 */
+		for (i = 0; i < k; i ++) {
+			montymul(t1, x, x, m, mw62num, m0i);
+			memcpy(x, t1, mw62num * sizeof *x);
+		}
+
+		/*
+		 * Window lookup: we want to set t2 to the window
+		 * lookup value, assuming the bits are non-zero. If
+		 * the window length is 1 bit only, then t2 is
+		 * already set; otherwise, we do a constant-time lookup.
+		 */
+		if (win_len > 1) {
+			uint64_t *base;
+
+			memset(t2, 0, mw62num * sizeof *t2);
+			base = t2 + mw62num;
+			for (u = 1; u < ((uint32_t)1 << k); u ++) {
+				uint64_t mask;
+				size_t v;
+
+				mask = -(uint64_t)EQ(u, bits);
+				for (v = 0; v < mw62num; v ++) {
+					t2[v] |= mask & base[v];
+				}
+				base += mw62num;
+			}
+		}
+
+		/*
+		 * Multiply with the looked-up value. We keep the product
+		 * only if the exponent bits are not all-zero.
+		 */
+		montymul(t1, x, t2, m, mw62num, m0i);
+		mask1 = -(uint64_t)EQ(bits, 0);
+		mask2 = ~mask1;
+		for (u = 0; u < mw62num; u ++) {
+			x[u] = (mask1 & x[u]) | (mask2 & t1[u]);
+		}
+	}
+
+	/*
+	 * Convert back from Montgomery representation.
+	 */
+	frommonty(x, m, mw62num, m0i);
+
+	/*
+	 * Convert result into 31-bit words.
+	 */
+	for (u = 0; u < mw31num; u += 2) {
+		uint64_t zw;
+
+		zw = x[u >> 1];
+		x31[u + 1] = (uint32_t)zw & 0x7FFFFFFF;
+		if ((u + 1) < mw31num) {
+			x31[u + 2] = (uint32_t)(zw >> 31);
+		}
+	}
+	return 1;
+}
+
+#else
+
+/* see inner.h */
+uint32_t
+br_i62_modpow_opt(uint32_t *x31, const unsigned char *e, size_t elen,
+	const uint32_t *m31, uint32_t m0i31, uint64_t *tmp, size_t twlen)
+{
+	size_t mwlen;
+
+	mwlen = (m31[0] + 63) >> 5;
+	if (twlen < mwlen) {
+		return 0;
+	}
+	return br_i31_modpow_opt(x31, e, elen, m31, m0i31,
+		(uint32_t *)tmp, twlen << 1);
+}
+
+#endif
diff --git a/src/rsa/rsa_default_pkcs1_sign.c b/src/rsa/rsa_default_pkcs1_sign.c
index 4e8d4ec..e926704 100644
--- a/src/rsa/rsa_default_pkcs1_sign.c
+++ b/src/rsa/rsa_default_pkcs1_sign.c
@@ -28,7 +28,9 @@
 br_rsa_pkcs1_sign
 br_rsa_pkcs1_sign_get_default(void)
 {
-#if BR_LOMUL
+#if BR_INT128 || BR_UMUL128
+	return &br_rsa_i62_pkcs1_sign;
+#elif BR_LOMUL
 	return &br_rsa_i15_pkcs1_sign;
 #else
 	return &br_rsa_i31_pkcs1_sign;
diff --git a/src/rsa/rsa_default_pkcs1_vrfy.c b/src/rsa/rsa_default_pkcs1_vrfy.c
index c5d81d6..b3dbeb7 100644
--- a/src/rsa/rsa_default_pkcs1_vrfy.c
+++ b/src/rsa/rsa_default_pkcs1_vrfy.c
@@ -28,7 +28,9 @@
 br_rsa_pkcs1_vrfy
 br_rsa_pkcs1_vrfy_get_default(void)
 {
-#if BR_LOMUL
+#if BR_INT128 || BR_UMUL128
+	return &br_rsa_i62_pkcs1_vrfy;
+#elif BR_LOMUL
 	return &br_rsa_i15_pkcs1_vrfy;
 #else
 	return &br_rsa_i31_pkcs1_vrfy;
diff --git a/src/rsa/rsa_default_priv.c b/src/rsa/rsa_default_priv.c
index 04e3381..bb0b2c0 100644
--- a/src/rsa/rsa_default_priv.c
+++ b/src/rsa/rsa_default_priv.c
@@ -28,7 +28,9 @@
 br_rsa_private
 br_rsa_private_get_default(void)
 {
-#if BR_LOMUL
+#if BR_INT128 || BR_UMUL128
+	return &br_rsa_i62_private;
+#elif BR_LOMUL
 	return &br_rsa_i15_private;
 #else
 	return &br_rsa_i31_private;
diff --git a/src/rsa/rsa_default_pub.c b/src/rsa/rsa_default_pub.c
index 1dbfb62..a1f03ef 100644
--- a/src/rsa/rsa_default_pub.c
+++ b/src/rsa/rsa_default_pub.c
@@ -28,7 +28,9 @@
 br_rsa_public
 br_rsa_public_get_default(void)
 {
-#if BR_LOMUL
+#if BR_INT128 || BR_UMUL128
+	return &br_rsa_i62_public;
+#elif BR_LOMUL
 	return &br_rsa_i15_public;
 #else
 	return &br_rsa_i31_public;
diff --git a/src/rsa/rsa_i31_priv.c b/src/rsa/rsa_i31_priv.c
index efff6ae..cb2858b 100644
--- a/src/rsa/rsa_i31_priv.c
+++ b/src/rsa/rsa_i31_priv.c
@@ -24,7 +24,8 @@
 
 #include "inner.h"
 
-#define U   (1 + ((BR_MAX_RSA_FACTOR + 30) / 31))
+#define U      (2 + ((BR_MAX_RSA_FACTOR + 30) / 31))
+#define TLEN   (8 * U)
 
 /* see bearssl_rsa.h */
 uint32_t
@@ -32,30 +33,18 @@ br_rsa_i31_private(unsigned char *x, const br_rsa_private_key *sk)
 {
 	const unsigned char *p, *q;
 	size_t plen, qlen;
-	uint32_t tmp[6 * U];
-	uint32_t *mp, *mq, *s1, *s2, *t1, *t2, *t3;
+	size_t fwlen;
 	uint32_t p0i, q0i;
 	size_t xlen;
+	uint32_t tmp[1 + TLEN];
+	long z;
+	uint32_t *mp, *mq, *s1, *s2, *t1, *t2, *t3;
+	uint32_t r;
 
 	/*
-	 * All our temporary buffers are from the tmp[] array.
-	 *
-	 * The mp, mq, s1, s2, t1 and t2 buffers are large enough to
-	 * contain a RSA factor. The t3 buffer can contain a complete
-	 * RSA modulus. t3 shares its storage space with s2, s1 and t1,
-	 * in that order (this is important, see below).
-	 */
-	mq = tmp;
-	mp = tmp + U;
-	t2 = tmp + 2 * U;
-	s2 = tmp + 3 * U;
-	s1 = tmp + 4 * U;
-	t1 = tmp + 5 * U;
-	t3 = s2;
-
-	/*
-	 * Compute the actual lengths (in bytes) of p and q, and check
-	 * that they fit within our stack buffers.
+	 * Compute the actual lengths of p and q, in bytes.
+	 * These lengths are not considered secret (we cannot really hide
+	 * them anyway in constant-time code).
 	 */
 	p = sk->p;
 	plen = sk->plen;
@@ -69,17 +58,28 @@ br_rsa_i31_private(unsigned char *x, const br_rsa_private_key *sk)
 		q ++;
 		qlen --;
 	}
-	if (plen > (BR_MAX_RSA_FACTOR >> 3)
-		|| qlen > (BR_MAX_RSA_FACTOR >> 3))
-	{
-		return 0;
+
+	/*
+	 * Compute the maximum factor length, in words.
+	 */
+	z = (long)(plen > qlen ? plen : qlen) << 3;
+	fwlen = 1;
+	while (z > 0) {
+		z -= 31;
+		fwlen ++;
 	}
 
 	/*
-	 * Decode p and q.
+	 * Round up the word length to an even number.
 	 */
-	br_i31_decode(mp, p, plen);
-	br_i31_decode(mq, q, qlen);
+	fwlen += (fwlen & 1);
+
+	/*
+	 * We need to fit at least 6 values in the stack buffer.
+	 */
+	if (6 * fwlen > TLEN) {
+		return 0;
+	}
 
 	/*
 	 * Compute signature length (in bytes).
@@ -87,18 +87,34 @@ br_rsa_i31_private(unsigned char *x, const br_rsa_private_key *sk)
 	xlen = (sk->n_bitlen + 7) >> 3;
 
 	/*
-	 * Compute s1 = x^dp mod p.
+	 * Decode q.
 	 */
-	p0i = br_i31_ninv31(mp[1]);
-	br_i31_decode_reduce(s1, x, xlen, mp);
-	br_i31_modpow(s1, sk->dp, sk->dplen, mp, p0i, t1, t2);
+	mq = tmp;
+	br_i31_decode(mq, q, qlen);
 
 	/*
 	 * Compute s2 = x^dq mod q.
 	 */
 	q0i = br_i31_ninv31(mq[1]);
+	s2 = mq + fwlen;
 	br_i31_decode_reduce(s2, x, xlen, mq);
-	br_i31_modpow(s2, sk->dq, sk->dqlen, mq, q0i, t1, t2);
+	r = br_i31_modpow_opt(s2, sk->dq, sk->dqlen, mq, q0i,
+		mq + 2 * fwlen, TLEN - 2 * fwlen);
+
+	/*
+	 * Decode p.
+	 */
+	mp = mq + 2 * fwlen;
+	br_i31_decode(mp, p, plen);
+
+	/*
+	 * Compute s1 = x^dp mod p.
+	 */
+	p0i = br_i31_ninv31(mp[1]);
+	s1 = mq + 3 * fwlen;
+	br_i31_decode_reduce(s1, x, xlen, mp);
+	r &= br_i31_modpow_opt(s1, sk->dp, sk->dplen, mp, p0i,
+		mq + 4 * fwlen, TLEN - 4 * fwlen);
 
 	/*
 	 * Compute:
@@ -113,6 +129,8 @@ br_rsa_i31_private(unsigned char *x, const br_rsa_private_key *sk)
 	 * inverse of q modulo p), we also tolerate improperly large
 	 * values for this parameter.
 	 */
+	t1 = mq + 4 * fwlen;
+	t2 = mq + 5 * fwlen;
 	br_i31_reduce(t2, s2, mp);
 	br_i31_add(s1, mp, br_i31_sub(s1, t2, 1));
 	br_i31_to_monty(s1, mp);
@@ -125,11 +143,13 @@ br_rsa_i31_private(unsigned char *x, const br_rsa_private_key *sk)
 	 * All these operations are non-modular.
 	 *
 	 * We need mq, s2 and t2. We use the t3 buffer as destination.
-	 * The buffers mp, s1 and t1 are no longer needed. Moreover,
-	 * the first step is to copy s2 into the destination buffer t3.
-	 * We thus arranged for t3 to actually share space with s2, and
-	 * to be followed by the space formerly used by s1 and t1.
+	 * The buffers mp, s1 and t1 are no longer needed, so we can
+	 * reuse them for t3. Moreover, the first step of the computation
+	 * is to copy s2 into t3, after which s2 is not needed. Right
+	 * now, mq is in slot 0, s2 is in slot 1, and t2 is in slot 5.
+	 * Therefore, we have ample room for t3 by simply using s2.
 	 */
+	t3 = s2;
 	br_i31_mulacc(t3, mq, t2);
 
 	/*
@@ -142,5 +162,5 @@ br_rsa_i31_private(unsigned char *x, const br_rsa_private_key *sk)
 	 * The only error conditions remaining at that point are invalid
 	 * values for p and q (even integers).
 	 */
-	return p0i & q0i & 1;
+	return p0i & q0i & r;
 }
diff --git a/src/rsa/rsa_i31_pub.c b/src/rsa/rsa_i31_pub.c
index 18e069f..d5f3fe2 100644
--- a/src/rsa/rsa_i31_pub.c
+++ b/src/rsa/rsa_i31_pub.c
@@ -24,6 +24,12 @@
 
 #include "inner.h"
 
+/*
+ * As a strict minimum, we need four buffers that can hold a
+ * modular integer.
+ */
+#define TLEN   (4 * (2 + ((BR_MAX_RSA_SIZE + 30) / 31)))
+
 /* see bearssl_rsa.h */
 uint32_t
 br_rsa_i31_public(unsigned char *x, size_t xlen,
@@ -31,10 +37,10 @@ br_rsa_i31_public(unsigned char *x, size_t xlen,
 {
 	const unsigned char *n;
 	size_t nlen;
-	uint32_t m[1 + ((BR_MAX_RSA_SIZE + 30) / 31)];
-	uint32_t a[1 + ((BR_MAX_RSA_SIZE + 30) / 31)];
-	uint32_t t1[1 + ((BR_MAX_RSA_SIZE + 30) / 31)];
-	uint32_t t2[1 + ((BR_MAX_RSA_SIZE + 30) / 31)];
+	uint32_t tmp[1 + TLEN];
+	uint32_t *m, *a, *t;
+	size_t fwlen;
+	long z;
 	uint32_t m0i, r;
 
 	/*
@@ -50,6 +56,29 @@ br_rsa_i31_public(unsigned char *x, size_t xlen,
 	if (nlen == 0 || nlen > (BR_MAX_RSA_SIZE >> 3) || xlen != nlen) {
 		return 0;
 	}
+	z = (long)nlen << 3;
+	fwlen = 1;
+	while (z > 0) {
+		z -= 31;
+		fwlen ++;
+	}
+	/*
+	 * Round up length to an even number.
+	 */
+	fwlen += (fwlen & 1);
+
+	/*
+	 * The modulus gets decoded into m[].
+	 * The value to exponentiate goes into a[].
+	 * The temporaries for modular exponentiation are in t[].
+	 */
+	m = tmp;
+	a = m + fwlen;
+	t = m + 2 * fwlen;
+
+	/*
+	 * Decode the modulus.
+	 */
 	br_i31_decode(m, n, nlen);
 	m0i = br_i31_ninv31(m[1]);
 
@@ -67,7 +96,7 @@ br_rsa_i31_public(unsigned char *x, size_t xlen,
 	/*
 	 * Compute the modular exponentiation.
 	 */
-	br_i31_modpow(a, pk->e, pk->elen, m, m0i, t1, t2);
+	br_i31_modpow_opt(a, pk->e, pk->elen, m, m0i, t, TLEN - 2 * fwlen);
 
 	/*
 	 * Encode the result.
diff --git a/src/rsa/rsa_i62_pkcs1_sign.c b/src/rsa/rsa_i62_pkcs1_sign.c
new file mode 100644
index 0000000..a20a084
--- /dev/null
+++ b/src/rsa/rsa_i62_pkcs1_sign.c
@@ -0,0 +1,57 @@
+/*
+ * Copyright (c) 2017 Thomas Pornin <pornin@bolet.org>
+ *
+ * Permission is hereby granted, free of charge, to any person obtaining 
+ * a copy of this software and associated documentation files (the
+ * "Software"), to deal in the Software without restriction, including
+ * without limitation the rights to use, copy, modify, merge, publish,
+ * distribute, sublicense, and/or sell copies of the Software, and to
+ * permit persons to whom the Software is furnished to do so, subject to
+ * the following conditions:
+ *
+ * The above copyright notice and this permission notice shall be 
+ * included in all copies or substantial portions of the Software.
+ *
+ * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, 
+ * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
+ * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND 
+ * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS
+ * BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN
+ * ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
+ * CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
+ * SOFTWARE.
+ */
+
+#include "inner.h"
+
+#if BR_INT128 || BR_UMUL128
+
+/* see bearssl_rsa.h */
+uint32_t
+br_rsa_i62_pkcs1_sign(const unsigned char *hash_oid,
+	const unsigned char *hash, size_t hash_len,
+	const br_rsa_private_key *sk, unsigned char *x)
+{
+	if (!br_rsa_pkcs1_sig_pad(hash_oid, hash, hash_len, sk->n_bitlen, x)) {
+		return 0;
+	}
+	return br_rsa_i62_private(x, sk);
+}
+
+/* see bearssl_rsa.h */
+br_rsa_pkcs1_sign
+br_rsa_i62_pkcs1_sign_get(void)
+{
+	return &br_rsa_i62_pkcs1_sign;
+}
+
+#else
+
+/* see bearssl_rsa.h */
+br_rsa_pkcs1_sign
+br_rsa_i62_pkcs1_sign_get(void)
+{
+	return 0;
+}
+
+#endif
diff --git a/src/rsa/rsa_i62_pkcs1_vrfy.c b/src/rsa/rsa_i62_pkcs1_vrfy.c
new file mode 100644
index 0000000..6519161
--- /dev/null
+++ b/src/rsa/rsa_i62_pkcs1_vrfy.c
@@ -0,0 +1,63 @@
+/*
+ * Copyright (c) 2017 Thomas Pornin <pornin@bolet.org>
+ *
+ * Permission is hereby granted, free of charge, to any person obtaining 
+ * a copy of this software and associated documentation files (the
+ * "Software"), to deal in the Software without restriction, including
+ * without limitation the rights to use, copy, modify, merge, publish,
+ * distribute, sublicense, and/or sell copies of the Software, and to
+ * permit persons to whom the Software is furnished to do so, subject to
+ * the following conditions:
+ *
+ * The above copyright notice and this permission notice shall be 
+ * included in all copies or substantial portions of the Software.
+ *
+ * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, 
+ * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
+ * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND 
+ * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS
+ * BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN
+ * ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
+ * CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
+ * SOFTWARE.
+ */
+
+#include "inner.h"
+
+#if BR_INT128 || BR_UMUL128
+
+/* see bearssl_rsa.h */
+uint32_t
+br_rsa_i62_pkcs1_vrfy(const unsigned char *x, size_t xlen,
+	const unsigned char *hash_oid, size_t hash_len,
+	const br_rsa_public_key *pk, unsigned char *hash_out)
+{
+	unsigned char sig[BR_MAX_RSA_SIZE >> 3];
+
+	if (xlen > (sizeof sig)) {
+		return 0;
+	}
+	memcpy(sig, x, xlen);
+	if (!br_rsa_i62_public(sig, xlen, pk)) {
+		return 0;
+	}
+	return br_rsa_pkcs1_sig_unpad(sig, xlen, hash_oid, hash_len, hash_out);
+}
+
+/* see bearssl_rsa.h */
+br_rsa_pkcs1_vrfy
+br_rsa_i62_pkcs1_vrfy_get(void)
+{
+	return &br_rsa_i62_pkcs1_vrfy;
+}
+
+#else
+
+/* see bearssl_rsa.h */
+br_rsa_pkcs1_vrfy
+br_rsa_i62_pkcs1_vrfy_get(void)
+{
+	return 0;
+}
+
+#endif
diff --git a/src/rsa/rsa_i62_priv.c b/src/rsa/rsa_i62_priv.c
new file mode 100644
index 0000000..ffa03c2
--- /dev/null
+++ b/src/rsa/rsa_i62_priv.c
@@ -0,0 +1,186 @@
+/*
+ * Copyright (c) 2016 Thomas Pornin <pornin@bolet.org>
+ *
+ * Permission is hereby granted, free of charge, to any person obtaining 
+ * a copy of this software and associated documentation files (the
+ * "Software"), to deal in the Software without restriction, including
+ * without limitation the rights to use, copy, modify, merge, publish,
+ * distribute, sublicense, and/or sell copies of the Software, and to
+ * permit persons to whom the Software is furnished to do so, subject to
+ * the following conditions:
+ *
+ * The above copyright notice and this permission notice shall be 
+ * included in all copies or substantial portions of the Software.
+ *
+ * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, 
+ * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
+ * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND 
+ * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS
+ * BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN
+ * ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
+ * CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
+ * SOFTWARE.
+ */
+
+#include "inner.h"
+
+#if BR_INT128 || BR_UMUL128
+
+#define U      (2 + ((BR_MAX_RSA_FACTOR + 30) / 31))
+#define TLEN   (4 * U)  /* TLEN is counted in 64-bit words */
+
+/* see bearssl_rsa.h */
+uint32_t
+br_rsa_i62_private(unsigned char *x, const br_rsa_private_key *sk)
+{
+	const unsigned char *p, *q;
+	size_t plen, qlen;
+	size_t fwlen;
+	uint32_t p0i, q0i;
+	size_t xlen;
+	uint64_t tmp[TLEN];
+	long z;
+	uint32_t *mp, *mq, *s1, *s2, *t1, *t2, *t3;
+	uint32_t r;
+
+	/*
+	 * Compute the actual lengths of p and q, in bytes.
+	 * These lengths are not considered secret (we cannot really hide
+	 * them anyway in constant-time code).
+	 */
+	p = sk->p;
+	plen = sk->plen;
+	while (plen > 0 && *p == 0) {
+		p ++;
+		plen --;
+	}
+	q = sk->q;
+	qlen = sk->qlen;
+	while (qlen > 0 && *q == 0) {
+		q ++;
+		qlen --;
+	}
+
+	/*
+	 * Compute the maximum factor length, in words.
+	 */
+	z = (long)(plen > qlen ? plen : qlen) << 3;
+	fwlen = 1;
+	while (z > 0) {
+		z -= 31;
+		fwlen ++;
+	}
+
+	/*
+	 * Convert size to 62-bit words.
+	 */
+	fwlen = (fwlen + 1) >> 1;
+
+	/*
+	 * We need to fit at least 6 values in the stack buffer.
+	 */
+	if (6 * fwlen > TLEN) {
+		return 0;
+	}
+
+	/*
+	 * Compute signature length (in bytes).
+	 */
+	xlen = (sk->n_bitlen + 7) >> 3;
+
+	/*
+	 * Decode q.
+	 */
+	mq = (uint32_t *)tmp;
+	br_i31_decode(mq, q, qlen);
+
+	/*
+	 * Compute s2 = x^dq mod q.
+	 */
+	q0i = br_i31_ninv31(mq[1]);
+	s2 = (uint32_t *)(tmp + fwlen);
+	br_i31_decode_reduce(s2, x, xlen, mq);
+	r = br_i62_modpow_opt(s2, sk->dq, sk->dqlen, mq, q0i,
+		tmp + 2 * fwlen, TLEN - 2 * fwlen);
+
+	/*
+	 * Decode p.
+	 */
+	mp = (uint32_t *)(tmp + 2 * fwlen);
+	br_i31_decode(mp, p, plen);
+
+	/*
+	 * Compute s1 = x^dp mod p.
+	 */
+	p0i = br_i31_ninv31(mp[1]);
+	s1 = (uint32_t *)(tmp + 3 * fwlen);
+	br_i31_decode_reduce(s1, x, xlen, mp);
+	r &= br_i62_modpow_opt(s1, sk->dp, sk->dplen, mp, p0i,
+		tmp + 4 * fwlen, TLEN - 4 * fwlen);
+
+	/*
+	 * Compute:
+	 *   h = (s1 - s2)*(1/q) mod p
+	 * s1 is an integer modulo p, but s2 is modulo q. PKCS#1 is
+	 * unclear about whether p may be lower than q (some existing,
+	 * widely deployed implementations of RSA don't tolerate p < q),
+	 * but we want to support that occurrence, so we need to use the
+	 * reduction function.
+	 *
+	 * Since we use br_i31_decode_reduce() for iq (purportedly, the
+	 * inverse of q modulo p), we also tolerate improperly large
+	 * values for this parameter.
+	 */
+	t1 = (uint32_t *)(tmp + 4 * fwlen);
+	t2 = (uint32_t *)(tmp + 5 * fwlen);
+	br_i31_reduce(t2, s2, mp);
+	br_i31_add(s1, mp, br_i31_sub(s1, t2, 1));
+	br_i31_to_monty(s1, mp);
+	br_i31_decode_reduce(t1, sk->iq, sk->iqlen, mp);
+	br_i31_montymul(t2, s1, t1, mp, p0i);
+
+	/*
+	 * h is now in t2. We compute the final result:
+	 *   s = s2 + q*h
+	 * All these operations are non-modular.
+	 *
+	 * We need mq, s2 and t2. We use the t3 buffer as destination.
+	 * The buffers mp, s1 and t1 are no longer needed, so we can
+	 * reuse them for t3. Moreover, the first step of the computation
+	 * is to copy s2 into t3, after which s2 is not needed. Right
+	 * now, mq is in slot 0, s2 is in slot 1, and t2 is in slot 5.
+	 * Therefore, we have ample room for t3 by simply using s2.
+	 */
+	t3 = s2;
+	br_i31_mulacc(t3, mq, t2);
+
+	/*
+	 * Encode the result. Since we already checked the value of xlen,
+	 * we can just use it right away.
+	 */
+	br_i31_encode(x, xlen, t3);
+
+	/*
+	 * The only error conditions remaining at that point are invalid
+	 * values for p and q (even integers).
+	 */
+	return p0i & q0i & r;
+}
+
+/* see bearssl_rsa.h */
+br_rsa_private
+br_rsa_i62_private_get(void)
+{
+	return &br_rsa_i62_private;
+}
+
+#else
+
+/* see bearssl_rsa.h */
+br_rsa_private
+br_rsa_i62_private_get(void)
+{
+	return 0;
+}
+
+#endif
diff --git a/src/rsa/rsa_i62_pub.c b/src/rsa/rsa_i62_pub.c
new file mode 100644
index 0000000..70cf61b
--- /dev/null
+++ b/src/rsa/rsa_i62_pub.c
@@ -0,0 +1,125 @@
+/*
+ * Copyright (c) 2016 Thomas Pornin <pornin@bolet.org>
+ *
+ * Permission is hereby granted, free of charge, to any person obtaining 
+ * a copy of this software and associated documentation files (the
+ * "Software"), to deal in the Software without restriction, including
+ * without limitation the rights to use, copy, modify, merge, publish,
+ * distribute, sublicense, and/or sell copies of the Software, and to
+ * permit persons to whom the Software is furnished to do so, subject to
+ * the following conditions:
+ *
+ * The above copyright notice and this permission notice shall be 
+ * included in all copies or substantial portions of the Software.
+ *
+ * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, 
+ * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
+ * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND 
+ * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS
+ * BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN
+ * ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
+ * CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
+ * SOFTWARE.
+ */
+
+#include "inner.h"
+
+#if BR_INT128 || BR_UMUL128
+
+/*
+ * As a strict minimum, we need four buffers that can hold a
+ * modular integer. But TLEN is expressed in 64-bit words.
+ */
+#define TLEN   (2 * (2 + ((BR_MAX_RSA_SIZE + 30) / 31)))
+
+/* see bearssl_rsa.h */
+uint32_t
+br_rsa_i62_public(unsigned char *x, size_t xlen,
+	const br_rsa_public_key *pk)
+{
+	const unsigned char *n;
+	size_t nlen;
+	uint64_t tmp[TLEN];
+	uint32_t *m, *a;
+	size_t fwlen;
+	long z;
+	uint32_t m0i, r;
+
+	/*
+	 * Get the actual length of the modulus, and see if it fits within
+	 * our stack buffer. We also check that the length of x[] is valid.
+	 */
+	n = pk->n;
+	nlen = pk->nlen;
+	while (nlen > 0 && *n == 0) {
+		n ++;
+		nlen --;
+	}
+	if (nlen == 0 || nlen > (BR_MAX_RSA_SIZE >> 3) || xlen != nlen) {
+		return 0;
+	}
+	z = (long)nlen << 3;
+	fwlen = 1;
+	while (z > 0) {
+		z -= 31;
+		fwlen ++;
+	}
+	/*
+	 * Convert fwlen to a count in 62-bit words.
+	 */
+	fwlen = (fwlen + 1) >> 1;
+
+	/*
+	 * The modulus gets decoded into m[].
+	 * The value to exponentiate goes into a[].
+	 */
+	m = (uint32_t *)tmp;
+	a = (uint32_t *)(tmp + fwlen);
+
+	/*
+	 * Decode the modulus.
+	 */
+	br_i31_decode(m, n, nlen);
+	m0i = br_i31_ninv31(m[1]);
+
+	/*
+	 * Note: if m[] is even, then m0i == 0. Otherwise, m0i must be
+	 * an odd integer.
+	 */
+	r = m0i & 1;
+
+	/*
+	 * Decode x[] into a[]; we also check that its value is proper.
+	 */
+	r &= br_i31_decode_mod(a, x, xlen, m);
+
+	/*
+	 * Compute the modular exponentiation.
+	 */
+	br_i62_modpow_opt(a, pk->e, pk->elen, m, m0i,
+		tmp + 2 * fwlen, TLEN - 2 * fwlen);
+
+	/*
+	 * Encode the result.
+	 */
+	br_i31_encode(x, xlen, a);
+	return r;
+}
+
+/* see bearssl_rsa.h */
+br_rsa_public
+br_rsa_i62_public_get(void)
+{
+	return &br_rsa_i62_public;
+}
+
+#else
+
+/* see bearssl_rsa.h */
+br_rsa_public
+br_rsa_i62_public_get(void)
+{
+	return 0;
+}
+
+#endif
diff --git a/src/ssl/ssl_client_default_rsapub.c b/src/ssl/ssl_client_default_rsapub.c
index 733151d..2cdaab8 100644
--- a/src/ssl/ssl_client_default_rsapub.c
+++ b/src/ssl/ssl_client_default_rsapub.c
@@ -28,9 +28,5 @@
 void
 br_ssl_client_set_default_rsapub(br_ssl_client_context *cc)
 {
-#if BR_LOMUL
-	br_ssl_client_set_rsapub(cc, &br_rsa_i15_public);
-#else
-	br_ssl_client_set_rsapub(cc, &br_rsa_i31_public);
-#endif
+	br_ssl_client_set_rsapub(cc, br_rsa_public_get_default());
 }
diff --git a/src/ssl/ssl_engine_default_rsavrfy.c b/src/ssl/ssl_engine_default_rsavrfy.c
index f05cc49..ad0628a 100644
--- a/src/ssl/ssl_engine_default_rsavrfy.c
+++ b/src/ssl/ssl_engine_default_rsavrfy.c
@@ -28,9 +28,5 @@
 void
 br_ssl_engine_set_default_rsavrfy(br_ssl_engine_context *cc)
 {
-#if BR_LOMUL
-	br_ssl_engine_set_rsavrfy(cc, &br_rsa_i15_pkcs1_vrfy);
-#else
-	br_ssl_engine_set_rsavrfy(cc, &br_rsa_i31_pkcs1_vrfy);
-#endif
+	br_ssl_engine_set_rsavrfy(cc, br_rsa_pkcs1_vrfy_get_default());
 }
diff --git a/src/ssl/ssl_server_full_rsa.c b/src/ssl/ssl_server_full_rsa.c
index cbb60f9..84471bb 100644
--- a/src/ssl/ssl_server_full_rsa.c
+++ b/src/ssl/ssl_server_full_rsa.c
@@ -97,12 +97,8 @@ br_ssl_server_init_full_rsa(br_ssl_server_context *cc,
 	 */
 	br_ssl_server_set_single_rsa(cc, chain, chain_len, sk,
 		BR_KEYTYPE_KEYX | BR_KEYTYPE_SIGN,
-#if BR_LOMUL
-		br_rsa_i15_private, br_rsa_i15_pkcs1_sign
-#else
-		br_rsa_i31_private, br_rsa_i31_pkcs1_sign
-#endif
-	);
+		br_rsa_private_get_default(),
+		br_rsa_pkcs1_sign_get_default());
 
 	/*
 	 * Set supported hash functions.
diff --git a/test/test_crypto.c b/test/test_crypto.c
index 95edd24..47c6bf6 100644
--- a/test/test_crypto.c
+++ b/test/test_crypto.c
@@ -4504,6 +4504,34 @@ test_RSA_i32(void)
 		&br_rsa_i32_pkcs1_sign, &br_rsa_i32_pkcs1_vrfy);
 }
 
+static void
+test_RSA_i62(void)
+{
+	br_rsa_public pub;
+	br_rsa_private priv;
+	br_rsa_pkcs1_sign sign;
+	br_rsa_pkcs1_vrfy vrfy;
+
+	pub = br_rsa_i62_public_get();
+	priv = br_rsa_i62_private_get();
+	sign = br_rsa_i62_pkcs1_sign_get();
+	vrfy = br_rsa_i62_pkcs1_vrfy_get();
+	if (pub) {
+		if (!priv || !sign || !vrfy) {
+			fprintf(stderr, "Inconsistent i62 availability\n");
+			exit(EXIT_FAILURE);
+		}
+		test_RSA_core("RSA i62 core", pub, priv);
+		test_RSA_sign("RSA i62 sign", priv, sign, vrfy);
+	} else {
+		if (priv || sign || vrfy) {
+			fprintf(stderr, "Inconsistent i62 availability\n");
+			exit(EXIT_FAILURE);
+		}
+		printf("Test RSA i62: UNAVAILABLE\n");
+	}
+}
+
 #if 0
 static void
 test_RSA_signatures(void)
@@ -5605,6 +5633,108 @@ test_ECDSA_i15(void)
 	fflush(stdout);
 }
 
+static void
+test_modpow_i31(void)
+{
+	br_hmac_drbg_context hc;
+	int k;
+
+	printf("Test ModPow/i31: ");
+
+	br_hmac_drbg_init(&hc, &br_sha256_vtable, "seed modpow", 11);
+	for (k = 10; k <= 500; k ++) {
+		size_t blen;
+		unsigned char bm[128], bx[128], bx1[128], bx2[128];
+		unsigned char be[128];
+		unsigned mask;
+		uint32_t x1[35], m1[35];
+		uint16_t x2[70], m2[70];
+		uint32_t tmp1[1000];
+		uint16_t tmp2[2000];
+
+		blen = (k + 7) >> 3;
+		br_hmac_drbg_generate(&hc, bm, blen);
+		br_hmac_drbg_generate(&hc, bx, blen);
+		br_hmac_drbg_generate(&hc, be, blen);
+		bm[blen - 1] |= 0x01;
+		mask = 0xFF >> ((int)(blen << 3) - k);
+		bm[0] &= mask;
+		bm[0] |= (mask - (mask >> 1));
+		bx[0] &= (mask >> 1);
+
+		br_i31_decode(m1, bm, blen);
+		br_i31_decode_mod(x1, bx, blen, m1);
+		br_i31_modpow_opt(x1, be, blen, m1, br_i31_ninv31(m1[1]),
+			tmp1, (sizeof tmp1) / (sizeof tmp1[0]));
+		br_i31_encode(bx1, blen, x1);
+
+		br_i15_decode(m2, bm, blen);
+		br_i15_decode_mod(x2, bx, blen, m2);
+		br_i15_modpow_opt(x2, be, blen, m2, br_i15_ninv15(m2[1]),
+			tmp2, (sizeof tmp2) / (sizeof tmp2[0]));
+		br_i15_encode(bx2, blen, x2);
+
+		check_equals("ModPow i31/i15", bx1, bx2, blen);
+
+		printf(".");
+		fflush(stdout);
+	}
+
+	printf(" done.\n");
+	fflush(stdout);
+}
+
+static void
+test_modpow_i62(void)
+{
+	br_hmac_drbg_context hc;
+	int k;
+
+	printf("Test ModPow/i62: ");
+
+	br_hmac_drbg_init(&hc, &br_sha256_vtable, "seed modpow", 11);
+	for (k = 10; k <= 500; k ++) {
+		size_t blen;
+		unsigned char bm[128], bx[128], bx1[128], bx2[128];
+		unsigned char be[128];
+		unsigned mask;
+		uint32_t x1[35], m1[35];
+		uint16_t x2[70], m2[70];
+		uint64_t tmp1[500];
+		uint16_t tmp2[2000];
+
+		blen = (k + 7) >> 3;
+		br_hmac_drbg_generate(&hc, bm, blen);
+		br_hmac_drbg_generate(&hc, bx, blen);
+		br_hmac_drbg_generate(&hc, be, blen);
+		bm[blen - 1] |= 0x01;
+		mask = 0xFF >> ((int)(blen << 3) - k);
+		bm[0] &= mask;
+		bm[0] |= (mask - (mask >> 1));
+		bx[0] &= (mask >> 1);
+
+		br_i31_decode(m1, bm, blen);
+		br_i31_decode_mod(x1, bx, blen, m1);
+		br_i62_modpow_opt(x1, be, blen, m1, br_i31_ninv31(m1[1]),
+			tmp1, (sizeof tmp1) / (sizeof tmp1[0]));
+		br_i31_encode(bx1, blen, x1);
+
+		br_i15_decode(m2, bm, blen);
+		br_i15_decode_mod(x2, bx, blen, m2);
+		br_i15_modpow_opt(x2, be, blen, m2, br_i15_ninv15(m2[1]),
+			tmp2, (sizeof tmp2) / (sizeof tmp2[0]));
+		br_i15_encode(bx2, blen, x2);
+
+		check_equals("ModPow i62/i15", bx1, bx2, blen);
+
+		printf(".");
+		fflush(stdout);
+	}
+
+	printf(" done.\n");
+	fflush(stdout);
+}
+
 static int
 eq_name(const char *s1, const char *s2)
 {
@@ -5677,6 +5807,7 @@ static const struct {
 	STU(RSA_i15),
 	STU(RSA_i31),
 	STU(RSA_i32),
+	STU(RSA_i62),
 	STU(GHASH_ctmul),
 	STU(GHASH_ctmul32),
 	STU(GHASH_ctmul64),
@@ -5692,6 +5823,8 @@ static const struct {
 	STU(EC_c25519_m31),
 	STU(ECDSA_i15),
 	STU(ECDSA_i31),
+	STU(modpow_i31),
+	STU(modpow_i62),
 	{ 0, 0 }
 };
 
diff --git a/test/test_speed.c b/test/test_speed.c
index 17c869f..a09aa04 100644
--- a/test/test_speed.c
+++ b/test/test_speed.c
@@ -666,6 +666,21 @@ test_speed_rsa_i32(void)
 		&br_rsa_i32_public, &br_rsa_i32_private);
 }
 
+static void
+test_speed_rsa_i62(void)
+{
+	br_rsa_public pub;
+	br_rsa_private priv;
+
+	pub = br_rsa_i62_public_get();
+	priv = br_rsa_i62_private_get();
+	if (pub) {
+		test_speed_rsa_inner("RSA i62", pub, priv);
+	} else {
+		printf("%-30s UNAVAILABLE\n", "RSA i62");
+	}
+}
+
 static void
 test_speed_ec_inner_1(const char *name,
 	const br_ec_impl *impl, const br_ec_curve_def *cd)
@@ -1279,6 +1294,7 @@ static const struct {
 	STU(rsa_i15),
 	STU(rsa_i31),
 	STU(rsa_i32),
+	STU(rsa_i62),
 	STU(ec_prime_i15),
 	STU(ec_prime_i31),
 	STU(ec_p256_m15),
diff --git a/tools/names.c b/tools/names.c
index 958e593..3b4aa83 100644
--- a/tools/names.c
+++ b/tools/names.c
@@ -406,24 +406,28 @@ static const struct {
 	const char *short_name;
 	const void *(*get)(void);
 } algo_names_dyn[] = {
-	{ "aes_pwr8_cbcenc",   "pwr8",
+	{ "aes_pwr8_cbcenc",      "pwr8",
 		(const void *(*)(void))&br_aes_pwr8_cbcenc_get_vtable },
-	{ "aes_pwr8_cbcdec",   "pwr8",
+	{ "aes_pwr8_cbcdec",      "pwr8",
 		(const void *(*)(void))&br_aes_pwr8_cbcdec_get_vtable },
-	{ "aes_pwr8_ctr",      "pwr8",
+	{ "aes_pwr8_ctr",         "pwr8",
 		(const void *(*)(void))&br_aes_pwr8_ctr_get_vtable },
-	{ "aes_x86ni_cbcenc",  "x86ni",
+	{ "aes_x86ni_cbcenc",     "x86ni",
 		(const void *(*)(void))&br_aes_x86ni_cbcenc_get_vtable },
-	{ "aes_x86ni_cbcdec",  "x86ni",
+	{ "aes_x86ni_cbcdec",     "x86ni",
 		(const void *(*)(void))&br_aes_x86ni_cbcdec_get_vtable },
-	{ "aes_x86ni_ctr",     "x86ni",
+	{ "aes_x86ni_ctr",        "x86ni",
 		(const void *(*)(void))&br_aes_x86ni_ctr_get_vtable },
-	{ "ghash_pclmul",      "pclmul",
+	{ "ghash_pclmul",         "pclmul",
 		(const void *(*)(void))&br_ghash_pclmul_get },
-	{ "ghash_pwr8",        "pwr8",
+	{ "ghash_pwr8",           "pwr8",
 		(const void *(*)(void))&br_ghash_pwr8_get },
-	{ "poly1305_ctmulq",   "ctmulq",
+	{ "poly1305_ctmulq",      "ctmulq",
 		(const void *(*)(void))&br_poly1305_ctmulq_get },
+	{ "rsa_i62_pkcs1_sign",   "i62",
+		(const void *(*)(void))&br_rsa_i62_pkcs1_sign_get },
+	{ "rsa_i62_pkcs1_vrfy",   "i62",
+		(const void *(*)(void))&br_rsa_i62_pkcs1_vrfy_get },
 	{ 0, 0, 0, }
 };
 
-- 
2.17.1