From 8b2fe3add686db5cbd977e75d3bef02fa4c98c8f Mon Sep 17 00:00:00 2001 From: Thomas Pornin 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 + * + * 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 + * + * 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 + +#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 + * + * 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 + * + * 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 + * + * 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 + * + * 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