1238384Sjkim/* crypto/engine/eng_rsax.c */ 2238384Sjkim/* Copyright (c) 2010-2010 Intel Corp. 3238384Sjkim * Author: Vinodh.Gopal@intel.com 4238384Sjkim * Jim Guilford 5238384Sjkim * Erdinc.Ozturk@intel.com 6238384Sjkim * Maxim.Perminov@intel.com 7238384Sjkim * Ying.Huang@intel.com 8238384Sjkim * 9238384Sjkim * More information about algorithm used can be found at: 10238384Sjkim * http://www.cse.buffalo.edu/srds2009/escs2009_submission_Gopal.pdf 11238384Sjkim */ 12238384Sjkim/* ==================================================================== 13238384Sjkim * Copyright (c) 1999-2001 The OpenSSL Project. All rights reserved. 14238384Sjkim * 15238384Sjkim * Redistribution and use in source and binary forms, with or without 16238384Sjkim * modification, are permitted provided that the following conditions 17238384Sjkim * are met: 18238384Sjkim * 19238384Sjkim * 1. Redistributions of source code must retain the above copyright 20238384Sjkim * notice, this list of conditions and the following disclaimer. 21238384Sjkim * 22238384Sjkim * 2. Redistributions in binary form must reproduce the above copyright 23238384Sjkim * notice, this list of conditions and the following disclaimer in 24238384Sjkim * the documentation and/or other materials provided with the 25238384Sjkim * distribution. 26238384Sjkim * 27238384Sjkim * 3. All advertising materials mentioning features or use of this 28238384Sjkim * software must display the following acknowledgment: 29238384Sjkim * "This product includes software developed by the OpenSSL Project 30238384Sjkim * for use in the OpenSSL Toolkit. (http://www.OpenSSL.org/)" 31238384Sjkim * 32238384Sjkim * 4. The names "OpenSSL Toolkit" and "OpenSSL Project" must not be used to 33238384Sjkim * endorse or promote products derived from this software without 34238384Sjkim * prior written permission. For written permission, please contact 35238384Sjkim * licensing@OpenSSL.org. 36238384Sjkim * 37238384Sjkim * 5. Products derived from this software may not be called "OpenSSL" 38238384Sjkim * nor may "OpenSSL" appear in their names without prior written 39238384Sjkim * permission of the OpenSSL Project. 40238384Sjkim * 41238384Sjkim * 6. Redistributions of any form whatsoever must retain the following 42238384Sjkim * acknowledgment: 43238384Sjkim * "This product includes software developed by the OpenSSL Project 44238384Sjkim * for use in the OpenSSL Toolkit (http://www.OpenSSL.org/)" 45238384Sjkim * 46238384Sjkim * THIS SOFTWARE IS PROVIDED BY THE OpenSSL PROJECT ``AS IS'' AND ANY 47238384Sjkim * EXPRESSED OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 48238384Sjkim * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR 49238384Sjkim * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE OpenSSL PROJECT OR 50238384Sjkim * ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 51238384Sjkim * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT 52238384Sjkim * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; 53238384Sjkim * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 54238384Sjkim * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, 55238384Sjkim * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) 56238384Sjkim * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED 57238384Sjkim * OF THE POSSIBILITY OF SUCH DAMAGE. 58238384Sjkim * ==================================================================== 59238384Sjkim * 60238384Sjkim * This product includes cryptographic software written by Eric Young 61238384Sjkim * (eay@cryptsoft.com). This product includes software written by Tim 62238384Sjkim * Hudson (tjh@cryptsoft.com). 63238384Sjkim */ 64238384Sjkim 65238384Sjkim#include <openssl/opensslconf.h> 66238384Sjkim 67238384Sjkim#include <stdio.h> 68238384Sjkim#include <string.h> 69238384Sjkim#include <openssl/crypto.h> 70238384Sjkim#include <openssl/buffer.h> 71238384Sjkim#include <openssl/engine.h> 72238384Sjkim#ifndef OPENSSL_NO_RSA 73296341Sdelphij# include <openssl/rsa.h> 74238384Sjkim#endif 75238384Sjkim#include <openssl/bn.h> 76238384Sjkim#include <openssl/err.h> 77238384Sjkim 78238384Sjkim/* RSAX is available **ONLY* on x86_64 CPUs */ 79238384Sjkim#undef COMPILE_RSAX 80238384Sjkim 81238384Sjkim#if (defined(__x86_64) || defined(__x86_64__) || \ 82238384Sjkim defined(_M_AMD64) || defined (_M_X64)) && !defined(OPENSSL_NO_ASM) 83296341Sdelphij# define COMPILE_RSAX 84296341Sdelphijstatic ENGINE *ENGINE_rsax(void); 85238384Sjkim#endif 86238384Sjkim 87296341Sdelphijvoid ENGINE_load_rsax(void) 88296341Sdelphij{ 89238384Sjkim/* On non-x86 CPUs it just returns. */ 90238384Sjkim#ifdef COMPILE_RSAX 91296341Sdelphij ENGINE *toadd = ENGINE_rsax(); 92296341Sdelphij if (!toadd) 93296341Sdelphij return; 94296341Sdelphij ENGINE_add(toadd); 95296341Sdelphij ENGINE_free(toadd); 96296341Sdelphij ERR_clear_error(); 97238384Sjkim#endif 98296341Sdelphij} 99238384Sjkim 100238384Sjkim#ifdef COMPILE_RSAX 101296341Sdelphij# define E_RSAX_LIB_NAME "rsax engine" 102238384Sjkim 103238384Sjkimstatic int e_rsax_destroy(ENGINE *e); 104238384Sjkimstatic int e_rsax_init(ENGINE *e); 105238384Sjkimstatic int e_rsax_finish(ENGINE *e); 106296341Sdelphijstatic int e_rsax_ctrl(ENGINE *e, int cmd, long i, void *p, void (*f) (void)); 107238384Sjkim 108296341Sdelphij# ifndef OPENSSL_NO_RSA 109238384Sjkim/* RSA stuff */ 110296341Sdelphijstatic int e_rsax_rsa_mod_exp(BIGNUM *r, const BIGNUM *I, RSA *rsa, 111296341Sdelphij BN_CTX *ctx); 112238384Sjkimstatic int e_rsax_rsa_finish(RSA *r); 113296341Sdelphij# endif 114238384Sjkim 115238384Sjkimstatic const ENGINE_CMD_DEFN e_rsax_cmd_defns[] = { 116296341Sdelphij {0, NULL, NULL, 0} 117296341Sdelphij}; 118238384Sjkim 119296341Sdelphij# ifndef OPENSSL_NO_RSA 120238384Sjkim/* Our internal RSA_METHOD that we provide pointers to */ 121296341Sdelphijstatic RSA_METHOD e_rsax_rsa = { 122296341Sdelphij "Intel RSA-X method", 123296341Sdelphij NULL, 124296341Sdelphij NULL, 125296341Sdelphij NULL, 126296341Sdelphij NULL, 127296341Sdelphij e_rsax_rsa_mod_exp, 128296341Sdelphij NULL, 129296341Sdelphij NULL, 130296341Sdelphij e_rsax_rsa_finish, 131296341Sdelphij RSA_FLAG_CACHE_PUBLIC | RSA_FLAG_CACHE_PRIVATE, 132296341Sdelphij NULL, 133296341Sdelphij NULL, 134296341Sdelphij NULL 135296341Sdelphij}; 136296341Sdelphij# endif 137238384Sjkim 138238384Sjkim/* Constants used when creating the ENGINE */ 139238384Sjkimstatic const char *engine_e_rsax_id = "rsax"; 140238384Sjkimstatic const char *engine_e_rsax_name = "RSAX engine support"; 141238384Sjkim 142238384Sjkim/* This internal function is used by ENGINE_rsax() */ 143238384Sjkimstatic int bind_helper(ENGINE *e) 144296341Sdelphij{ 145296341Sdelphij# ifndef OPENSSL_NO_RSA 146296341Sdelphij const RSA_METHOD *meth1; 147296341Sdelphij# endif 148296341Sdelphij if (!ENGINE_set_id(e, engine_e_rsax_id) || 149296341Sdelphij !ENGINE_set_name(e, engine_e_rsax_name) || 150296341Sdelphij# ifndef OPENSSL_NO_RSA 151296341Sdelphij !ENGINE_set_RSA(e, &e_rsax_rsa) || 152296341Sdelphij# endif 153296341Sdelphij !ENGINE_set_destroy_function(e, e_rsax_destroy) || 154296341Sdelphij !ENGINE_set_init_function(e, e_rsax_init) || 155296341Sdelphij !ENGINE_set_finish_function(e, e_rsax_finish) || 156296341Sdelphij !ENGINE_set_ctrl_function(e, e_rsax_ctrl) || 157296341Sdelphij !ENGINE_set_cmd_defns(e, e_rsax_cmd_defns)) 158296341Sdelphij return 0; 159238384Sjkim 160296341Sdelphij# ifndef OPENSSL_NO_RSA 161296341Sdelphij meth1 = RSA_PKCS1_SSLeay(); 162296341Sdelphij e_rsax_rsa.rsa_pub_enc = meth1->rsa_pub_enc; 163296341Sdelphij e_rsax_rsa.rsa_pub_dec = meth1->rsa_pub_dec; 164296341Sdelphij e_rsax_rsa.rsa_priv_enc = meth1->rsa_priv_enc; 165296341Sdelphij e_rsax_rsa.rsa_priv_dec = meth1->rsa_priv_dec; 166296341Sdelphij e_rsax_rsa.bn_mod_exp = meth1->bn_mod_exp; 167296341Sdelphij# endif 168296341Sdelphij return 1; 169296341Sdelphij} 170238384Sjkim 171238384Sjkimstatic ENGINE *ENGINE_rsax(void) 172296341Sdelphij{ 173296341Sdelphij ENGINE *ret = ENGINE_new(); 174296341Sdelphij if (!ret) 175296341Sdelphij return NULL; 176296341Sdelphij if (!bind_helper(ret)) { 177296341Sdelphij ENGINE_free(ret); 178296341Sdelphij return NULL; 179296341Sdelphij } 180296341Sdelphij return ret; 181296341Sdelphij} 182238384Sjkim 183296341Sdelphij# ifndef OPENSSL_NO_RSA 184238384Sjkim/* Used to attach our own key-data to an RSA structure */ 185238384Sjkimstatic int rsax_ex_data_idx = -1; 186296341Sdelphij# endif 187238384Sjkim 188238384Sjkimstatic int e_rsax_destroy(ENGINE *e) 189296341Sdelphij{ 190296341Sdelphij return 1; 191296341Sdelphij} 192238384Sjkim 193238384Sjkim/* (de)initialisation functions. */ 194238384Sjkimstatic int e_rsax_init(ENGINE *e) 195296341Sdelphij{ 196296341Sdelphij# ifndef OPENSSL_NO_RSA 197296341Sdelphij if (rsax_ex_data_idx == -1) 198296341Sdelphij rsax_ex_data_idx = RSA_get_ex_new_index(0, NULL, NULL, NULL, NULL); 199296341Sdelphij# endif 200296341Sdelphij if (rsax_ex_data_idx == -1) 201296341Sdelphij return 0; 202296341Sdelphij return 1; 203296341Sdelphij} 204238384Sjkim 205238384Sjkimstatic int e_rsax_finish(ENGINE *e) 206296341Sdelphij{ 207296341Sdelphij return 1; 208296341Sdelphij} 209238384Sjkim 210296341Sdelphijstatic int e_rsax_ctrl(ENGINE *e, int cmd, long i, void *p, void (*f) (void)) 211296341Sdelphij{ 212296341Sdelphij int to_return = 1; 213238384Sjkim 214296341Sdelphij switch (cmd) { 215296341Sdelphij /* The command isn't understood by this engine */ 216296341Sdelphij default: 217296341Sdelphij to_return = 0; 218296341Sdelphij break; 219296341Sdelphij } 220238384Sjkim 221296341Sdelphij return to_return; 222296341Sdelphij} 223238384Sjkim 224296341Sdelphij# ifndef OPENSSL_NO_RSA 225238384Sjkim 226296341Sdelphij# ifdef _WIN32 227238384Sjkimtypedef unsigned __int64 UINT64; 228296341Sdelphij# else 229238384Sjkimtypedef unsigned long long UINT64; 230296341Sdelphij# endif 231238384Sjkimtypedef unsigned short UINT16; 232238384Sjkim 233296341Sdelphij/* 234296341Sdelphij * Table t is interleaved in the following manner: The order in memory is 235296341Sdelphij * t[0][0], t[0][1], ..., t[0][7], t[1][0], ... A particular 512-bit value is 236296341Sdelphij * stored in t[][index] rather than the more normal t[index][]; i.e. the 237296341Sdelphij * qwords of a particular entry in t are not adjacent in memory 238238384Sjkim */ 239238384Sjkim 240238384Sjkim/* Init BIGNUM b from the interleaved UINT64 array */ 241296341Sdelphijstatic int interleaved_array_to_bn_512(BIGNUM *b, UINT64 *array); 242238384Sjkim 243296341Sdelphij/* 244296341Sdelphij * Extract array elements from BIGNUM b To set the whole array from b, call 245296341Sdelphij * with n=8 246238384Sjkim */ 247296341Sdelphijstatic int bn_extract_to_array_512(const BIGNUM *b, unsigned int n, 248296341Sdelphij UINT64 *array); 249238384Sjkim 250238384Sjkimstruct mod_ctx_512 { 251238384Sjkim UINT64 t[8][8]; 252238384Sjkim UINT64 m[8]; 253296341Sdelphij UINT64 m1[8]; /* 2^278 % m */ 254296341Sdelphij UINT64 m2[8]; /* 2^640 % m */ 255296341Sdelphij UINT64 k1[2]; /* (- 1/m) % 2^128 */ 256238384Sjkim}; 257238384Sjkim 258238384Sjkimstatic int mod_exp_pre_compute_data_512(UINT64 *m, struct mod_ctx_512 *data); 259238384Sjkim 260238384Sjkimvoid mod_exp_512(UINT64 *result, /* 512 bits, 8 qwords */ 261296341Sdelphij UINT64 *g, /* 512 bits, 8 qwords */ 262296341Sdelphij UINT64 *exp, /* 512 bits, 8 qwords */ 263296341Sdelphij struct mod_ctx_512 *data); 264238384Sjkim 265296341Sdelphijtypedef struct st_e_rsax_mod_ctx { 266296341Sdelphij UINT64 type; 267296341Sdelphij union { 268296341Sdelphij struct mod_ctx_512 b512; 269296341Sdelphij } ctx; 270238384Sjkim 271238384Sjkim} E_RSAX_MOD_CTX; 272238384Sjkim 273296341Sdelphijstatic E_RSAX_MOD_CTX *e_rsax_get_ctx(RSA *rsa, int idx, BIGNUM *m) 274238384Sjkim{ 275296341Sdelphij E_RSAX_MOD_CTX *hptr; 276238384Sjkim 277296341Sdelphij if (idx < 0 || idx > 2) 278296341Sdelphij return NULL; 279238384Sjkim 280296341Sdelphij hptr = RSA_get_ex_data(rsa, rsax_ex_data_idx); 281296341Sdelphij if (!hptr) { 282296341Sdelphij hptr = OPENSSL_malloc(3 * sizeof(E_RSAX_MOD_CTX)); 283296341Sdelphij if (!hptr) 284296341Sdelphij return NULL; 285296341Sdelphij hptr[2].type = hptr[1].type = hptr[0].type = 0; 286296341Sdelphij RSA_set_ex_data(rsa, rsax_ex_data_idx, hptr); 287296341Sdelphij } 288238384Sjkim 289296341Sdelphij if (hptr[idx].type == (UINT64)BN_num_bits(m)) 290296341Sdelphij return hptr + idx; 291238384Sjkim 292296341Sdelphij if (BN_num_bits(m) == 512) { 293296341Sdelphij UINT64 _m[8]; 294296341Sdelphij bn_extract_to_array_512(m, 8, _m); 295296341Sdelphij memset(&hptr[idx].ctx.b512, 0, sizeof(struct mod_ctx_512)); 296296341Sdelphij mod_exp_pre_compute_data_512(_m, &hptr[idx].ctx.b512); 297296341Sdelphij } 298238384Sjkim 299296341Sdelphij hptr[idx].type = BN_num_bits(m); 300296341Sdelphij return hptr + idx; 301238384Sjkim} 302238384Sjkim 303238384Sjkimstatic int e_rsax_rsa_finish(RSA *rsa) 304296341Sdelphij{ 305296341Sdelphij E_RSAX_MOD_CTX *hptr = RSA_get_ex_data(rsa, rsax_ex_data_idx); 306296341Sdelphij if (hptr) { 307296341Sdelphij OPENSSL_free(hptr); 308296341Sdelphij RSA_set_ex_data(rsa, rsax_ex_data_idx, NULL); 309296341Sdelphij } 310296341Sdelphij if (rsa->_method_mod_n) 311296341Sdelphij BN_MONT_CTX_free(rsa->_method_mod_n); 312296341Sdelphij if (rsa->_method_mod_p) 313296341Sdelphij BN_MONT_CTX_free(rsa->_method_mod_p); 314296341Sdelphij if (rsa->_method_mod_q) 315296341Sdelphij BN_MONT_CTX_free(rsa->_method_mod_q); 316296341Sdelphij return 1; 317296341Sdelphij} 318238384Sjkim 319238384Sjkimstatic int e_rsax_bn_mod_exp(BIGNUM *r, const BIGNUM *g, const BIGNUM *e, 320296341Sdelphij const BIGNUM *m, BN_CTX *ctx, 321296341Sdelphij BN_MONT_CTX *in_mont, 322296341Sdelphij E_RSAX_MOD_CTX *rsax_mod_ctx) 323238384Sjkim{ 324296341Sdelphij if (rsax_mod_ctx && BN_get_flags(e, BN_FLG_CONSTTIME) != 0) { 325296341Sdelphij if (BN_num_bits(m) == 512) { 326296341Sdelphij UINT64 _r[8]; 327296341Sdelphij UINT64 _g[8]; 328296341Sdelphij UINT64 _e[8]; 329238384Sjkim 330296341Sdelphij /* Init the arrays from the BIGNUMs */ 331296341Sdelphij bn_extract_to_array_512(g, 8, _g); 332296341Sdelphij bn_extract_to_array_512(e, 8, _e); 333238384Sjkim 334296341Sdelphij mod_exp_512(_r, _g, _e, &rsax_mod_ctx->ctx.b512); 335296341Sdelphij /* Return the result in the BIGNUM */ 336296341Sdelphij interleaved_array_to_bn_512(r, _r); 337296341Sdelphij return 1; 338238384Sjkim } 339296341Sdelphij } 340238384Sjkim 341296341Sdelphij return BN_mod_exp_mont(r, g, e, m, ctx, in_mont); 342238384Sjkim} 343238384Sjkim 344296341Sdelphij/* 345296341Sdelphij * Declares for the Intel CIAP 512-bit / CRT / 1024 bit RSA modular 346238384Sjkim * exponentiation routine precalculations and a structure to hold the 347296341Sdelphij * necessary values. These files are meant to live in crypto/rsa/ in the 348296341Sdelphij * target openssl. 349238384Sjkim */ 350238384Sjkim 351238384Sjkim/* 352238384Sjkim * Local method: extracts a piece from a BIGNUM, to fit it into 353238384Sjkim * an array. Call with n=8 to extract an entire 512-bit BIGNUM 354238384Sjkim */ 355296341Sdelphijstatic int bn_extract_to_array_512(const BIGNUM *b, unsigned int n, 356296341Sdelphij UINT64 *array) 357238384Sjkim{ 358296341Sdelphij int i; 359296341Sdelphij UINT64 tmp; 360296341Sdelphij unsigned char bn_buff[64]; 361296341Sdelphij memset(bn_buff, 0, 64); 362296341Sdelphij if (BN_num_bytes(b) > 64) { 363296341Sdelphij printf("Can't support this byte size\n"); 364296341Sdelphij return 0; 365296341Sdelphij } 366296341Sdelphij if (BN_num_bytes(b) != 0) { 367296341Sdelphij if (!BN_bn2bin(b, bn_buff + (64 - BN_num_bytes(b)))) { 368296341Sdelphij printf("Error's in bn2bin\n"); 369296341Sdelphij /* We have to error, here */ 370296341Sdelphij return 0; 371296341Sdelphij } 372296341Sdelphij } 373296341Sdelphij while (n-- > 0) { 374296341Sdelphij array[n] = 0; 375296341Sdelphij for (i = 7; i >= 0; i--) { 376296341Sdelphij tmp = bn_buff[63 - (n * 8 + i)]; 377296341Sdelphij array[n] |= tmp << (8 * i); 378296341Sdelphij } 379296341Sdelphij } 380296341Sdelphij return 1; 381238384Sjkim} 382238384Sjkim 383238384Sjkim/* Init a 512-bit BIGNUM from the UINT64*_ (8 * 64) interleaved array */ 384296341Sdelphijstatic int interleaved_array_to_bn_512(BIGNUM *b, UINT64 *array) 385238384Sjkim{ 386296341Sdelphij unsigned char tmp[64]; 387296341Sdelphij int n = 8; 388296341Sdelphij int i; 389296341Sdelphij while (n-- > 0) { 390296341Sdelphij for (i = 7; i >= 0; i--) { 391296341Sdelphij tmp[63 - (n * 8 + i)] = (unsigned char)(array[n] >> (8 * i)); 392296341Sdelphij }} 393296341Sdelphij BN_bin2bn(tmp, 64, b); 394296341Sdelphij return 0; 395238384Sjkim} 396238384Sjkim 397238384Sjkim/* The main 512bit precompute call */ 398238384Sjkimstatic int mod_exp_pre_compute_data_512(UINT64 *m, struct mod_ctx_512 *data) 399296341Sdelphij{ 400238384Sjkim BIGNUM two_768, two_640, two_128, two_512, tmp, _m, tmp2; 401238384Sjkim 402238384Sjkim /* We need a BN_CTX for the modulo functions */ 403296341Sdelphij BN_CTX *ctx; 404238384Sjkim /* Some tmps */ 405238384Sjkim UINT64 _t[8]; 406238384Sjkim int i, j, ret = 0; 407238384Sjkim 408238384Sjkim /* Init _m with m */ 409238384Sjkim BN_init(&_m); 410238384Sjkim interleaved_array_to_bn_512(&_m, m); 411238384Sjkim memset(_t, 0, 64); 412238384Sjkim 413238384Sjkim /* Inits */ 414238384Sjkim BN_init(&two_768); 415238384Sjkim BN_init(&two_640); 416238384Sjkim BN_init(&two_128); 417238384Sjkim BN_init(&two_512); 418238384Sjkim BN_init(&tmp); 419238384Sjkim BN_init(&tmp2); 420238384Sjkim 421238384Sjkim /* Create our context */ 422296341Sdelphij if ((ctx = BN_CTX_new()) == NULL) { 423296341Sdelphij goto err; 424296341Sdelphij } 425296341Sdelphij BN_CTX_start(ctx); 426238384Sjkim 427238384Sjkim /* 428238384Sjkim * For production, if you care, these only need to be set once, 429238384Sjkim * and may be made constants. 430238384Sjkim */ 431238384Sjkim BN_lshift(&two_768, BN_value_one(), 768); 432238384Sjkim BN_lshift(&two_640, BN_value_one(), 640); 433238384Sjkim BN_lshift(&two_128, BN_value_one(), 128); 434238384Sjkim BN_lshift(&two_512, BN_value_one(), 512); 435238384Sjkim 436238384Sjkim if (0 == (m[7] & 0x8000000000000000)) { 437296341Sdelphij goto err; 438238384Sjkim } 439296341Sdelphij if (0 == (m[0] & 0x1)) { /* Odd modulus required for Mont */ 440296341Sdelphij goto err; 441238384Sjkim } 442238384Sjkim 443238384Sjkim /* Precompute m1 */ 444238384Sjkim BN_mod(&tmp, &two_768, &_m, ctx); 445238384Sjkim if (!bn_extract_to_array_512(&tmp, 8, &data->m1[0])) { 446296341Sdelphij goto err; 447296341Sdelphij } 448238384Sjkim 449238384Sjkim /* Precompute m2 */ 450238384Sjkim BN_mod(&tmp, &two_640, &_m, ctx); 451238384Sjkim if (!bn_extract_to_array_512(&tmp, 8, &data->m2[0])) { 452296341Sdelphij goto err; 453238384Sjkim } 454238384Sjkim 455238384Sjkim /* 456238384Sjkim * Precompute k1, a 128b number = ((-1)* m-1 ) mod 2128; k1 should 457238384Sjkim * be non-negative. 458238384Sjkim */ 459238384Sjkim BN_mod_inverse(&tmp, &_m, &two_128, ctx); 460296341Sdelphij if (!BN_is_zero(&tmp)) { 461296341Sdelphij BN_sub(&tmp, &two_128, &tmp); 462296341Sdelphij } 463238384Sjkim if (!bn_extract_to_array_512(&tmp, 2, &data->k1[0])) { 464296341Sdelphij goto err; 465296341Sdelphij } 466238384Sjkim 467238384Sjkim /* Precompute t */ 468296341Sdelphij for (i = 0; i < 8; i++) { 469238384Sjkim BN_zero(&tmp); 470296341Sdelphij if (i & 1) { 471296341Sdelphij BN_add(&tmp, &two_512, &tmp); 472296341Sdelphij } 473296341Sdelphij if (i & 2) { 474296341Sdelphij BN_add(&tmp, &two_512, &tmp); 475296341Sdelphij } 476296341Sdelphij if (i & 4) { 477296341Sdelphij BN_add(&tmp, &two_640, &tmp); 478296341Sdelphij } 479238384Sjkim 480238384Sjkim BN_nnmod(&tmp2, &tmp, &_m, ctx); 481238384Sjkim if (!bn_extract_to_array_512(&tmp2, 8, _t)) { 482296341Sdelphij goto err; 483296341Sdelphij } 484296341Sdelphij for (j = 0; j < 8; j++) 485296341Sdelphij data->t[j][i] = _t[j]; 486296341Sdelphij } 487238384Sjkim 488238384Sjkim /* Precompute m */ 489296341Sdelphij for (i = 0; i < 8; i++) { 490296341Sdelphij data->m[i] = m[i]; 491296341Sdelphij } 492238384Sjkim 493238384Sjkim ret = 1; 494238384Sjkim 495296341Sdelphij err: 496238384Sjkim /* Cleanup */ 497296341Sdelphij if (ctx != NULL) { 498296341Sdelphij BN_CTX_end(ctx); 499296341Sdelphij BN_CTX_free(ctx); 500296341Sdelphij } 501238384Sjkim BN_free(&two_768); 502238384Sjkim BN_free(&two_640); 503238384Sjkim BN_free(&two_128); 504238384Sjkim BN_free(&two_512); 505238384Sjkim BN_free(&tmp); 506238384Sjkim BN_free(&tmp2); 507238384Sjkim BN_free(&_m); 508238384Sjkim 509238384Sjkim return ret; 510238384Sjkim} 511238384Sjkim 512296341Sdelphijstatic int e_rsax_rsa_mod_exp(BIGNUM *r0, const BIGNUM *I, RSA *rsa, 513296341Sdelphij BN_CTX *ctx) 514296341Sdelphij{ 515296341Sdelphij BIGNUM *r1, *m1, *vrfy; 516296341Sdelphij BIGNUM local_dmp1, local_dmq1, local_c, local_r1; 517296341Sdelphij BIGNUM *dmp1, *dmq1, *c, *pr1; 518296341Sdelphij int ret = 0; 519238384Sjkim 520296341Sdelphij BN_CTX_start(ctx); 521296341Sdelphij r1 = BN_CTX_get(ctx); 522296341Sdelphij m1 = BN_CTX_get(ctx); 523296341Sdelphij vrfy = BN_CTX_get(ctx); 524238384Sjkim 525296341Sdelphij { 526296341Sdelphij BIGNUM local_p, local_q; 527296341Sdelphij BIGNUM *p = NULL, *q = NULL; 528296341Sdelphij int error = 0; 529238384Sjkim 530296341Sdelphij /* 531296341Sdelphij * Make sure BN_mod_inverse in Montgomery intialization uses the 532296341Sdelphij * BN_FLG_CONSTTIME flag (unless RSA_FLAG_NO_CONSTTIME is set) 533296341Sdelphij */ 534296341Sdelphij if (!(rsa->flags & RSA_FLAG_NO_CONSTTIME)) { 535296341Sdelphij BN_init(&local_p); 536296341Sdelphij p = &local_p; 537296341Sdelphij BN_with_flags(p, rsa->p, BN_FLG_CONSTTIME); 538238384Sjkim 539296341Sdelphij BN_init(&local_q); 540296341Sdelphij q = &local_q; 541296341Sdelphij BN_with_flags(q, rsa->q, BN_FLG_CONSTTIME); 542296341Sdelphij } else { 543296341Sdelphij p = rsa->p; 544296341Sdelphij q = rsa->q; 545296341Sdelphij } 546238384Sjkim 547296341Sdelphij if (rsa->flags & RSA_FLAG_CACHE_PRIVATE) { 548296341Sdelphij if (!BN_MONT_CTX_set_locked 549296341Sdelphij (&rsa->_method_mod_p, CRYPTO_LOCK_RSA, p, ctx)) 550296341Sdelphij error = 1; 551296341Sdelphij if (!BN_MONT_CTX_set_locked 552296341Sdelphij (&rsa->_method_mod_q, CRYPTO_LOCK_RSA, q, ctx)) 553296341Sdelphij error = 1; 554296341Sdelphij } 555238384Sjkim 556296341Sdelphij /* clean up */ 557296341Sdelphij if (!(rsa->flags & RSA_FLAG_NO_CONSTTIME)) { 558296341Sdelphij BN_free(&local_p); 559296341Sdelphij BN_free(&local_q); 560296341Sdelphij } 561296341Sdelphij if (error) 562296341Sdelphij goto err; 563296341Sdelphij } 564238384Sjkim 565296341Sdelphij if (rsa->flags & RSA_FLAG_CACHE_PUBLIC) 566296341Sdelphij if (!BN_MONT_CTX_set_locked 567296341Sdelphij (&rsa->_method_mod_n, CRYPTO_LOCK_RSA, rsa->n, ctx)) 568296341Sdelphij goto err; 569238384Sjkim 570296341Sdelphij /* compute I mod q */ 571296341Sdelphij if (!(rsa->flags & RSA_FLAG_NO_CONSTTIME)) { 572296341Sdelphij c = &local_c; 573296341Sdelphij BN_with_flags(c, I, BN_FLG_CONSTTIME); 574296341Sdelphij if (!BN_mod(r1, c, rsa->q, ctx)) 575296341Sdelphij goto err; 576296341Sdelphij } else { 577296341Sdelphij if (!BN_mod(r1, I, rsa->q, ctx)) 578296341Sdelphij goto err; 579296341Sdelphij } 580238384Sjkim 581296341Sdelphij /* compute r1^dmq1 mod q */ 582296341Sdelphij if (!(rsa->flags & RSA_FLAG_NO_CONSTTIME)) { 583296341Sdelphij dmq1 = &local_dmq1; 584296341Sdelphij BN_with_flags(dmq1, rsa->dmq1, BN_FLG_CONSTTIME); 585296341Sdelphij } else 586296341Sdelphij dmq1 = rsa->dmq1; 587238384Sjkim 588296341Sdelphij if (!e_rsax_bn_mod_exp(m1, r1, dmq1, rsa->q, ctx, 589296341Sdelphij rsa->_method_mod_q, e_rsax_get_ctx(rsa, 0, 590296341Sdelphij rsa->q))) 591296341Sdelphij goto err; 592238384Sjkim 593296341Sdelphij /* compute I mod p */ 594296341Sdelphij if (!(rsa->flags & RSA_FLAG_NO_CONSTTIME)) { 595296341Sdelphij c = &local_c; 596296341Sdelphij BN_with_flags(c, I, BN_FLG_CONSTTIME); 597296341Sdelphij if (!BN_mod(r1, c, rsa->p, ctx)) 598296341Sdelphij goto err; 599296341Sdelphij } else { 600296341Sdelphij if (!BN_mod(r1, I, rsa->p, ctx)) 601296341Sdelphij goto err; 602296341Sdelphij } 603238384Sjkim 604296341Sdelphij /* compute r1^dmp1 mod p */ 605296341Sdelphij if (!(rsa->flags & RSA_FLAG_NO_CONSTTIME)) { 606296341Sdelphij dmp1 = &local_dmp1; 607296341Sdelphij BN_with_flags(dmp1, rsa->dmp1, BN_FLG_CONSTTIME); 608296341Sdelphij } else 609296341Sdelphij dmp1 = rsa->dmp1; 610238384Sjkim 611296341Sdelphij if (!e_rsax_bn_mod_exp(r0, r1, dmp1, rsa->p, ctx, 612296341Sdelphij rsa->_method_mod_p, e_rsax_get_ctx(rsa, 1, 613296341Sdelphij rsa->p))) 614296341Sdelphij goto err; 615238384Sjkim 616296341Sdelphij if (!BN_sub(r0, r0, m1)) 617296341Sdelphij goto err; 618296341Sdelphij /* 619296341Sdelphij * This will help stop the size of r0 increasing, which does affect the 620296341Sdelphij * multiply if it optimised for a power of 2 size 621296341Sdelphij */ 622296341Sdelphij if (BN_is_negative(r0)) 623296341Sdelphij if (!BN_add(r0, r0, rsa->p)) 624296341Sdelphij goto err; 625238384Sjkim 626296341Sdelphij if (!BN_mul(r1, r0, rsa->iqmp, ctx)) 627296341Sdelphij goto err; 628238384Sjkim 629296341Sdelphij /* Turn BN_FLG_CONSTTIME flag on before division operation */ 630296341Sdelphij if (!(rsa->flags & RSA_FLAG_NO_CONSTTIME)) { 631296341Sdelphij pr1 = &local_r1; 632296341Sdelphij BN_with_flags(pr1, r1, BN_FLG_CONSTTIME); 633296341Sdelphij } else 634296341Sdelphij pr1 = r1; 635296341Sdelphij if (!BN_mod(r0, pr1, rsa->p, ctx)) 636296341Sdelphij goto err; 637238384Sjkim 638296341Sdelphij /* 639296341Sdelphij * If p < q it is occasionally possible for the correction of adding 'p' 640296341Sdelphij * if r0 is negative above to leave the result still negative. This can 641296341Sdelphij * break the private key operations: the following second correction 642296341Sdelphij * should *always* correct this rare occurrence. This will *never* happen 643296341Sdelphij * with OpenSSL generated keys because they ensure p > q [steve] 644296341Sdelphij */ 645296341Sdelphij if (BN_is_negative(r0)) 646296341Sdelphij if (!BN_add(r0, r0, rsa->p)) 647296341Sdelphij goto err; 648296341Sdelphij if (!BN_mul(r1, r0, rsa->q, ctx)) 649296341Sdelphij goto err; 650296341Sdelphij if (!BN_add(r0, r1, m1)) 651296341Sdelphij goto err; 652238384Sjkim 653296341Sdelphij if (rsa->e && rsa->n) { 654296341Sdelphij if (!e_rsax_bn_mod_exp 655296341Sdelphij (vrfy, r0, rsa->e, rsa->n, ctx, rsa->_method_mod_n, 656296341Sdelphij e_rsax_get_ctx(rsa, 2, rsa->n))) 657296341Sdelphij goto err; 658296341Sdelphij 659296341Sdelphij /* 660296341Sdelphij * If 'I' was greater than (or equal to) rsa->n, the operation will 661296341Sdelphij * be equivalent to using 'I mod n'. However, the result of the 662296341Sdelphij * verify will *always* be less than 'n' so we don't check for 663296341Sdelphij * absolute equality, just congruency. 664238384Sjkim */ 665296341Sdelphij if (!BN_sub(vrfy, vrfy, I)) 666296341Sdelphij goto err; 667296341Sdelphij if (!BN_mod(vrfy, vrfy, rsa->n, ctx)) 668296341Sdelphij goto err; 669296341Sdelphij if (BN_is_negative(vrfy)) 670296341Sdelphij if (!BN_add(vrfy, vrfy, rsa->n)) 671296341Sdelphij goto err; 672296341Sdelphij if (!BN_is_zero(vrfy)) { 673296341Sdelphij /* 674296341Sdelphij * 'I' and 'vrfy' aren't congruent mod n. Don't leak 675296341Sdelphij * miscalculated CRT output, just do a raw (slower) mod_exp and 676296341Sdelphij * return that instead. 677296341Sdelphij */ 678238384Sjkim 679296341Sdelphij BIGNUM local_d; 680296341Sdelphij BIGNUM *d = NULL; 681238384Sjkim 682296341Sdelphij if (!(rsa->flags & RSA_FLAG_NO_CONSTTIME)) { 683296341Sdelphij d = &local_d; 684296341Sdelphij BN_with_flags(d, rsa->d, BN_FLG_CONSTTIME); 685296341Sdelphij } else 686296341Sdelphij d = rsa->d; 687296341Sdelphij if (!e_rsax_bn_mod_exp(r0, I, d, rsa->n, ctx, 688296341Sdelphij rsa->_method_mod_n, e_rsax_get_ctx(rsa, 2, 689296341Sdelphij rsa->n))) 690296341Sdelphij goto err; 691296341Sdelphij } 692296341Sdelphij } 693296341Sdelphij ret = 1; 694238384Sjkim 695296341Sdelphij err: 696296341Sdelphij BN_CTX_end(ctx); 697238384Sjkim 698296341Sdelphij return ret; 699296341Sdelphij} 700296341Sdelphij# endif /* !OPENSSL_NO_RSA */ 701296341Sdelphij#endif /* !COMPILE_RSAX */ 702