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 73280304Sjkim# 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) 83280304Sjkim# define COMPILE_RSAX 84280304Sjkimstatic ENGINE *ENGINE_rsax(void); 85238384Sjkim#endif 86238384Sjkim 87280304Sjkimvoid ENGINE_load_rsax(void) 88280304Sjkim{ 89238384Sjkim/* On non-x86 CPUs it just returns. */ 90238384Sjkim#ifdef COMPILE_RSAX 91280304Sjkim ENGINE *toadd = ENGINE_rsax(); 92280304Sjkim if (!toadd) 93280304Sjkim return; 94280304Sjkim ENGINE_add(toadd); 95280304Sjkim ENGINE_free(toadd); 96280304Sjkim ERR_clear_error(); 97238384Sjkim#endif 98280304Sjkim} 99238384Sjkim 100238384Sjkim#ifdef COMPILE_RSAX 101280304Sjkim# 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); 106280304Sjkimstatic int e_rsax_ctrl(ENGINE *e, int cmd, long i, void *p, void (*f) (void)); 107238384Sjkim 108280304Sjkim# ifndef OPENSSL_NO_RSA 109238384Sjkim/* RSA stuff */ 110280304Sjkimstatic int e_rsax_rsa_mod_exp(BIGNUM *r, const BIGNUM *I, RSA *rsa, 111280304Sjkim BN_CTX *ctx); 112238384Sjkimstatic int e_rsax_rsa_finish(RSA *r); 113280304Sjkim# endif 114238384Sjkim 115238384Sjkimstatic const ENGINE_CMD_DEFN e_rsax_cmd_defns[] = { 116280304Sjkim {0, NULL, NULL, 0} 117280304Sjkim}; 118238384Sjkim 119280304Sjkim# ifndef OPENSSL_NO_RSA 120238384Sjkim/* Our internal RSA_METHOD that we provide pointers to */ 121280304Sjkimstatic RSA_METHOD e_rsax_rsa = { 122280304Sjkim "Intel RSA-X method", 123280304Sjkim NULL, 124280304Sjkim NULL, 125280304Sjkim NULL, 126280304Sjkim NULL, 127280304Sjkim e_rsax_rsa_mod_exp, 128280304Sjkim NULL, 129280304Sjkim NULL, 130280304Sjkim e_rsax_rsa_finish, 131280304Sjkim RSA_FLAG_CACHE_PUBLIC | RSA_FLAG_CACHE_PRIVATE, 132280304Sjkim NULL, 133280304Sjkim NULL, 134280304Sjkim NULL 135280304Sjkim}; 136280304Sjkim# 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) 144280304Sjkim{ 145280304Sjkim# ifndef OPENSSL_NO_RSA 146280304Sjkim const RSA_METHOD *meth1; 147280304Sjkim# endif 148280304Sjkim if (!ENGINE_set_id(e, engine_e_rsax_id) || 149280304Sjkim !ENGINE_set_name(e, engine_e_rsax_name) || 150280304Sjkim# ifndef OPENSSL_NO_RSA 151280304Sjkim !ENGINE_set_RSA(e, &e_rsax_rsa) || 152280304Sjkim# endif 153280304Sjkim !ENGINE_set_destroy_function(e, e_rsax_destroy) || 154280304Sjkim !ENGINE_set_init_function(e, e_rsax_init) || 155280304Sjkim !ENGINE_set_finish_function(e, e_rsax_finish) || 156280304Sjkim !ENGINE_set_ctrl_function(e, e_rsax_ctrl) || 157280304Sjkim !ENGINE_set_cmd_defns(e, e_rsax_cmd_defns)) 158280304Sjkim return 0; 159238384Sjkim 160280304Sjkim# ifndef OPENSSL_NO_RSA 161280304Sjkim meth1 = RSA_PKCS1_SSLeay(); 162280304Sjkim e_rsax_rsa.rsa_pub_enc = meth1->rsa_pub_enc; 163280304Sjkim e_rsax_rsa.rsa_pub_dec = meth1->rsa_pub_dec; 164280304Sjkim e_rsax_rsa.rsa_priv_enc = meth1->rsa_priv_enc; 165280304Sjkim e_rsax_rsa.rsa_priv_dec = meth1->rsa_priv_dec; 166280304Sjkim e_rsax_rsa.bn_mod_exp = meth1->bn_mod_exp; 167280304Sjkim# endif 168280304Sjkim return 1; 169280304Sjkim} 170238384Sjkim 171238384Sjkimstatic ENGINE *ENGINE_rsax(void) 172280304Sjkim{ 173280304Sjkim ENGINE *ret = ENGINE_new(); 174280304Sjkim if (!ret) 175280304Sjkim return NULL; 176280304Sjkim if (!bind_helper(ret)) { 177280304Sjkim ENGINE_free(ret); 178280304Sjkim return NULL; 179280304Sjkim } 180280304Sjkim return ret; 181280304Sjkim} 182238384Sjkim 183280304Sjkim# ifndef OPENSSL_NO_RSA 184238384Sjkim/* Used to attach our own key-data to an RSA structure */ 185238384Sjkimstatic int rsax_ex_data_idx = -1; 186280304Sjkim# endif 187238384Sjkim 188238384Sjkimstatic int e_rsax_destroy(ENGINE *e) 189280304Sjkim{ 190280304Sjkim return 1; 191280304Sjkim} 192238384Sjkim 193238384Sjkim/* (de)initialisation functions. */ 194238384Sjkimstatic int e_rsax_init(ENGINE *e) 195280304Sjkim{ 196280304Sjkim# ifndef OPENSSL_NO_RSA 197280304Sjkim if (rsax_ex_data_idx == -1) 198280304Sjkim rsax_ex_data_idx = RSA_get_ex_new_index(0, NULL, NULL, NULL, NULL); 199280304Sjkim# endif 200280304Sjkim if (rsax_ex_data_idx == -1) 201280304Sjkim return 0; 202280304Sjkim return 1; 203280304Sjkim} 204238384Sjkim 205238384Sjkimstatic int e_rsax_finish(ENGINE *e) 206280304Sjkim{ 207280304Sjkim return 1; 208280304Sjkim} 209238384Sjkim 210280304Sjkimstatic int e_rsax_ctrl(ENGINE *e, int cmd, long i, void *p, void (*f) (void)) 211280304Sjkim{ 212280304Sjkim int to_return = 1; 213238384Sjkim 214280304Sjkim switch (cmd) { 215280304Sjkim /* The command isn't understood by this engine */ 216280304Sjkim default: 217280304Sjkim to_return = 0; 218280304Sjkim break; 219280304Sjkim } 220238384Sjkim 221280304Sjkim return to_return; 222280304Sjkim} 223238384Sjkim 224280304Sjkim# ifndef OPENSSL_NO_RSA 225238384Sjkim 226280304Sjkim# ifdef _WIN32 227238384Sjkimtypedef unsigned __int64 UINT64; 228280304Sjkim# else 229238384Sjkimtypedef unsigned long long UINT64; 230280304Sjkim# endif 231238384Sjkimtypedef unsigned short UINT16; 232238384Sjkim 233280304Sjkim/* 234280304Sjkim * Table t is interleaved in the following manner: The order in memory is 235280304Sjkim * t[0][0], t[0][1], ..., t[0][7], t[1][0], ... A particular 512-bit value is 236280304Sjkim * stored in t[][index] rather than the more normal t[index][]; i.e. the 237280304Sjkim * qwords of a particular entry in t are not adjacent in memory 238238384Sjkim */ 239238384Sjkim 240238384Sjkim/* Init BIGNUM b from the interleaved UINT64 array */ 241280304Sjkimstatic int interleaved_array_to_bn_512(BIGNUM *b, UINT64 *array); 242238384Sjkim 243280304Sjkim/* 244280304Sjkim * Extract array elements from BIGNUM b To set the whole array from b, call 245280304Sjkim * with n=8 246238384Sjkim */ 247280304Sjkimstatic int bn_extract_to_array_512(const BIGNUM *b, unsigned int n, 248280304Sjkim UINT64 *array); 249238384Sjkim 250238384Sjkimstruct mod_ctx_512 { 251238384Sjkim UINT64 t[8][8]; 252238384Sjkim UINT64 m[8]; 253280304Sjkim UINT64 m1[8]; /* 2^278 % m */ 254280304Sjkim UINT64 m2[8]; /* 2^640 % m */ 255280304Sjkim 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 */ 261280304Sjkim UINT64 *g, /* 512 bits, 8 qwords */ 262280304Sjkim UINT64 *exp, /* 512 bits, 8 qwords */ 263280304Sjkim struct mod_ctx_512 *data); 264238384Sjkim 265280304Sjkimtypedef struct st_e_rsax_mod_ctx { 266280304Sjkim UINT64 type; 267280304Sjkim union { 268280304Sjkim struct mod_ctx_512 b512; 269280304Sjkim } ctx; 270238384Sjkim 271238384Sjkim} E_RSAX_MOD_CTX; 272238384Sjkim 273280304Sjkimstatic E_RSAX_MOD_CTX *e_rsax_get_ctx(RSA *rsa, int idx, BIGNUM *m) 274238384Sjkim{ 275280304Sjkim E_RSAX_MOD_CTX *hptr; 276238384Sjkim 277280304Sjkim if (idx < 0 || idx > 2) 278280304Sjkim return NULL; 279238384Sjkim 280280304Sjkim hptr = RSA_get_ex_data(rsa, rsax_ex_data_idx); 281280304Sjkim if (!hptr) { 282280304Sjkim hptr = OPENSSL_malloc(3 * sizeof(E_RSAX_MOD_CTX)); 283280304Sjkim if (!hptr) 284280304Sjkim return NULL; 285280304Sjkim hptr[2].type = hptr[1].type = hptr[0].type = 0; 286280304Sjkim RSA_set_ex_data(rsa, rsax_ex_data_idx, hptr); 287280304Sjkim } 288238384Sjkim 289280304Sjkim if (hptr[idx].type == (UINT64)BN_num_bits(m)) 290280304Sjkim return hptr + idx; 291238384Sjkim 292280304Sjkim if (BN_num_bits(m) == 512) { 293280304Sjkim UINT64 _m[8]; 294280304Sjkim bn_extract_to_array_512(m, 8, _m); 295280304Sjkim memset(&hptr[idx].ctx.b512, 0, sizeof(struct mod_ctx_512)); 296280304Sjkim mod_exp_pre_compute_data_512(_m, &hptr[idx].ctx.b512); 297280304Sjkim } 298238384Sjkim 299280304Sjkim hptr[idx].type = BN_num_bits(m); 300280304Sjkim return hptr + idx; 301238384Sjkim} 302238384Sjkim 303238384Sjkimstatic int e_rsax_rsa_finish(RSA *rsa) 304280304Sjkim{ 305280304Sjkim E_RSAX_MOD_CTX *hptr = RSA_get_ex_data(rsa, rsax_ex_data_idx); 306280304Sjkim if (hptr) { 307280304Sjkim OPENSSL_free(hptr); 308280304Sjkim RSA_set_ex_data(rsa, rsax_ex_data_idx, NULL); 309280304Sjkim } 310280304Sjkim if (rsa->_method_mod_n) 311280304Sjkim BN_MONT_CTX_free(rsa->_method_mod_n); 312280304Sjkim if (rsa->_method_mod_p) 313280304Sjkim BN_MONT_CTX_free(rsa->_method_mod_p); 314280304Sjkim if (rsa->_method_mod_q) 315280304Sjkim BN_MONT_CTX_free(rsa->_method_mod_q); 316280304Sjkim return 1; 317280304Sjkim} 318238384Sjkim 319238384Sjkimstatic int e_rsax_bn_mod_exp(BIGNUM *r, const BIGNUM *g, const BIGNUM *e, 320280304Sjkim const BIGNUM *m, BN_CTX *ctx, 321280304Sjkim BN_MONT_CTX *in_mont, 322280304Sjkim E_RSAX_MOD_CTX *rsax_mod_ctx) 323238384Sjkim{ 324280304Sjkim if (rsax_mod_ctx && BN_get_flags(e, BN_FLG_CONSTTIME) != 0) { 325280304Sjkim if (BN_num_bits(m) == 512) { 326280304Sjkim UINT64 _r[8]; 327280304Sjkim UINT64 _g[8]; 328280304Sjkim UINT64 _e[8]; 329238384Sjkim 330280304Sjkim /* Init the arrays from the BIGNUMs */ 331280304Sjkim bn_extract_to_array_512(g, 8, _g); 332280304Sjkim bn_extract_to_array_512(e, 8, _e); 333238384Sjkim 334280304Sjkim mod_exp_512(_r, _g, _e, &rsax_mod_ctx->ctx.b512); 335280304Sjkim /* Return the result in the BIGNUM */ 336280304Sjkim interleaved_array_to_bn_512(r, _r); 337280304Sjkim return 1; 338238384Sjkim } 339280304Sjkim } 340238384Sjkim 341280304Sjkim return BN_mod_exp_mont(r, g, e, m, ctx, in_mont); 342238384Sjkim} 343238384Sjkim 344280304Sjkim/* 345280304Sjkim * Declares for the Intel CIAP 512-bit / CRT / 1024 bit RSA modular 346238384Sjkim * exponentiation routine precalculations and a structure to hold the 347280304Sjkim * necessary values. These files are meant to live in crypto/rsa/ in the 348280304Sjkim * 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 */ 355280304Sjkimstatic int bn_extract_to_array_512(const BIGNUM *b, unsigned int n, 356280304Sjkim UINT64 *array) 357238384Sjkim{ 358280304Sjkim int i; 359280304Sjkim UINT64 tmp; 360280304Sjkim unsigned char bn_buff[64]; 361280304Sjkim memset(bn_buff, 0, 64); 362280304Sjkim if (BN_num_bytes(b) > 64) { 363280304Sjkim printf("Can't support this byte size\n"); 364280304Sjkim return 0; 365280304Sjkim } 366280304Sjkim if (BN_num_bytes(b) != 0) { 367280304Sjkim if (!BN_bn2bin(b, bn_buff + (64 - BN_num_bytes(b)))) { 368280304Sjkim printf("Error's in bn2bin\n"); 369280304Sjkim /* We have to error, here */ 370280304Sjkim return 0; 371280304Sjkim } 372280304Sjkim } 373280304Sjkim while (n-- > 0) { 374280304Sjkim array[n] = 0; 375280304Sjkim for (i = 7; i >= 0; i--) { 376280304Sjkim tmp = bn_buff[63 - (n * 8 + i)]; 377280304Sjkim array[n] |= tmp << (8 * i); 378280304Sjkim } 379280304Sjkim } 380280304Sjkim return 1; 381238384Sjkim} 382238384Sjkim 383238384Sjkim/* Init a 512-bit BIGNUM from the UINT64*_ (8 * 64) interleaved array */ 384280304Sjkimstatic int interleaved_array_to_bn_512(BIGNUM *b, UINT64 *array) 385238384Sjkim{ 386280304Sjkim unsigned char tmp[64]; 387280304Sjkim int n = 8; 388280304Sjkim int i; 389280304Sjkim while (n-- > 0) { 390280304Sjkim for (i = 7; i >= 0; i--) { 391280304Sjkim tmp[63 - (n * 8 + i)] = (unsigned char)(array[n] >> (8 * i)); 392280304Sjkim }} 393280304Sjkim BN_bin2bn(tmp, 64, b); 394280304Sjkim 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) 399280304Sjkim{ 400238384Sjkim BIGNUM two_768, two_640, two_128, two_512, tmp, _m, tmp2; 401238384Sjkim 402238384Sjkim /* We need a BN_CTX for the modulo functions */ 403280304Sjkim 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 */ 422280304Sjkim if ((ctx = BN_CTX_new()) == NULL) { 423280304Sjkim goto err; 424280304Sjkim } 425280304Sjkim 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)) { 437280304Sjkim goto err; 438238384Sjkim } 439280304Sjkim if (0 == (m[0] & 0x1)) { /* Odd modulus required for Mont */ 440280304Sjkim 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])) { 446280304Sjkim goto err; 447280304Sjkim } 448238384Sjkim 449238384Sjkim /* Precompute m2 */ 450238384Sjkim BN_mod(&tmp, &two_640, &_m, ctx); 451238384Sjkim if (!bn_extract_to_array_512(&tmp, 8, &data->m2[0])) { 452280304Sjkim 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); 460280304Sjkim if (!BN_is_zero(&tmp)) { 461280304Sjkim BN_sub(&tmp, &two_128, &tmp); 462280304Sjkim } 463238384Sjkim if (!bn_extract_to_array_512(&tmp, 2, &data->k1[0])) { 464280304Sjkim goto err; 465280304Sjkim } 466238384Sjkim 467238384Sjkim /* Precompute t */ 468280304Sjkim for (i = 0; i < 8; i++) { 469238384Sjkim BN_zero(&tmp); 470280304Sjkim if (i & 1) { 471280304Sjkim BN_add(&tmp, &two_512, &tmp); 472280304Sjkim } 473280304Sjkim if (i & 2) { 474280304Sjkim BN_add(&tmp, &two_512, &tmp); 475280304Sjkim } 476280304Sjkim if (i & 4) { 477280304Sjkim BN_add(&tmp, &two_640, &tmp); 478280304Sjkim } 479238384Sjkim 480238384Sjkim BN_nnmod(&tmp2, &tmp, &_m, ctx); 481238384Sjkim if (!bn_extract_to_array_512(&tmp2, 8, _t)) { 482280304Sjkim goto err; 483280304Sjkim } 484280304Sjkim for (j = 0; j < 8; j++) 485280304Sjkim data->t[j][i] = _t[j]; 486280304Sjkim } 487238384Sjkim 488238384Sjkim /* Precompute m */ 489280304Sjkim for (i = 0; i < 8; i++) { 490280304Sjkim data->m[i] = m[i]; 491280304Sjkim } 492238384Sjkim 493238384Sjkim ret = 1; 494238384Sjkim 495280304Sjkim err: 496238384Sjkim /* Cleanup */ 497280304Sjkim if (ctx != NULL) { 498280304Sjkim BN_CTX_end(ctx); 499280304Sjkim BN_CTX_free(ctx); 500280304Sjkim } 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 512280304Sjkimstatic int e_rsax_rsa_mod_exp(BIGNUM *r0, const BIGNUM *I, RSA *rsa, 513280304Sjkim BN_CTX *ctx) 514280304Sjkim{ 515280304Sjkim BIGNUM *r1, *m1, *vrfy; 516280304Sjkim BIGNUM local_dmp1, local_dmq1, local_c, local_r1; 517280304Sjkim BIGNUM *dmp1, *dmq1, *c, *pr1; 518280304Sjkim int ret = 0; 519238384Sjkim 520280304Sjkim BN_CTX_start(ctx); 521280304Sjkim r1 = BN_CTX_get(ctx); 522280304Sjkim m1 = BN_CTX_get(ctx); 523280304Sjkim vrfy = BN_CTX_get(ctx); 524238384Sjkim 525280304Sjkim { 526280304Sjkim BIGNUM local_p, local_q; 527280304Sjkim BIGNUM *p = NULL, *q = NULL; 528280304Sjkim int error = 0; 529238384Sjkim 530280304Sjkim /* 531280304Sjkim * Make sure BN_mod_inverse in Montgomery intialization uses the 532280304Sjkim * BN_FLG_CONSTTIME flag (unless RSA_FLAG_NO_CONSTTIME is set) 533280304Sjkim */ 534280304Sjkim if (!(rsa->flags & RSA_FLAG_NO_CONSTTIME)) { 535280304Sjkim BN_init(&local_p); 536280304Sjkim p = &local_p; 537280304Sjkim BN_with_flags(p, rsa->p, BN_FLG_CONSTTIME); 538238384Sjkim 539280304Sjkim BN_init(&local_q); 540280304Sjkim q = &local_q; 541280304Sjkim BN_with_flags(q, rsa->q, BN_FLG_CONSTTIME); 542280304Sjkim } else { 543280304Sjkim p = rsa->p; 544280304Sjkim q = rsa->q; 545280304Sjkim } 546238384Sjkim 547280304Sjkim if (rsa->flags & RSA_FLAG_CACHE_PRIVATE) { 548280304Sjkim if (!BN_MONT_CTX_set_locked 549280304Sjkim (&rsa->_method_mod_p, CRYPTO_LOCK_RSA, p, ctx)) 550280304Sjkim error = 1; 551280304Sjkim if (!BN_MONT_CTX_set_locked 552280304Sjkim (&rsa->_method_mod_q, CRYPTO_LOCK_RSA, q, ctx)) 553280304Sjkim error = 1; 554280304Sjkim } 555238384Sjkim 556280304Sjkim /* clean up */ 557280304Sjkim if (!(rsa->flags & RSA_FLAG_NO_CONSTTIME)) { 558280304Sjkim BN_free(&local_p); 559280304Sjkim BN_free(&local_q); 560280304Sjkim } 561280304Sjkim if (error) 562280304Sjkim goto err; 563280304Sjkim } 564238384Sjkim 565280304Sjkim if (rsa->flags & RSA_FLAG_CACHE_PUBLIC) 566280304Sjkim if (!BN_MONT_CTX_set_locked 567280304Sjkim (&rsa->_method_mod_n, CRYPTO_LOCK_RSA, rsa->n, ctx)) 568280304Sjkim goto err; 569238384Sjkim 570280304Sjkim /* compute I mod q */ 571280304Sjkim if (!(rsa->flags & RSA_FLAG_NO_CONSTTIME)) { 572280304Sjkim c = &local_c; 573280304Sjkim BN_with_flags(c, I, BN_FLG_CONSTTIME); 574280304Sjkim if (!BN_mod(r1, c, rsa->q, ctx)) 575280304Sjkim goto err; 576280304Sjkim } else { 577280304Sjkim if (!BN_mod(r1, I, rsa->q, ctx)) 578280304Sjkim goto err; 579280304Sjkim } 580238384Sjkim 581280304Sjkim /* compute r1^dmq1 mod q */ 582280304Sjkim if (!(rsa->flags & RSA_FLAG_NO_CONSTTIME)) { 583280304Sjkim dmq1 = &local_dmq1; 584280304Sjkim BN_with_flags(dmq1, rsa->dmq1, BN_FLG_CONSTTIME); 585280304Sjkim } else 586280304Sjkim dmq1 = rsa->dmq1; 587238384Sjkim 588280304Sjkim if (!e_rsax_bn_mod_exp(m1, r1, dmq1, rsa->q, ctx, 589280304Sjkim rsa->_method_mod_q, e_rsax_get_ctx(rsa, 0, 590280304Sjkim rsa->q))) 591280304Sjkim goto err; 592238384Sjkim 593280304Sjkim /* compute I mod p */ 594280304Sjkim if (!(rsa->flags & RSA_FLAG_NO_CONSTTIME)) { 595280304Sjkim c = &local_c; 596280304Sjkim BN_with_flags(c, I, BN_FLG_CONSTTIME); 597280304Sjkim if (!BN_mod(r1, c, rsa->p, ctx)) 598280304Sjkim goto err; 599280304Sjkim } else { 600280304Sjkim if (!BN_mod(r1, I, rsa->p, ctx)) 601280304Sjkim goto err; 602280304Sjkim } 603238384Sjkim 604280304Sjkim /* compute r1^dmp1 mod p */ 605280304Sjkim if (!(rsa->flags & RSA_FLAG_NO_CONSTTIME)) { 606280304Sjkim dmp1 = &local_dmp1; 607280304Sjkim BN_with_flags(dmp1, rsa->dmp1, BN_FLG_CONSTTIME); 608280304Sjkim } else 609280304Sjkim dmp1 = rsa->dmp1; 610238384Sjkim 611280304Sjkim if (!e_rsax_bn_mod_exp(r0, r1, dmp1, rsa->p, ctx, 612280304Sjkim rsa->_method_mod_p, e_rsax_get_ctx(rsa, 1, 613280304Sjkim rsa->p))) 614280304Sjkim goto err; 615238384Sjkim 616280304Sjkim if (!BN_sub(r0, r0, m1)) 617280304Sjkim goto err; 618280304Sjkim /* 619280304Sjkim * This will help stop the size of r0 increasing, which does affect the 620280304Sjkim * multiply if it optimised for a power of 2 size 621280304Sjkim */ 622280304Sjkim if (BN_is_negative(r0)) 623280304Sjkim if (!BN_add(r0, r0, rsa->p)) 624280304Sjkim goto err; 625238384Sjkim 626280304Sjkim if (!BN_mul(r1, r0, rsa->iqmp, ctx)) 627280304Sjkim goto err; 628238384Sjkim 629280304Sjkim /* Turn BN_FLG_CONSTTIME flag on before division operation */ 630280304Sjkim if (!(rsa->flags & RSA_FLAG_NO_CONSTTIME)) { 631280304Sjkim pr1 = &local_r1; 632280304Sjkim BN_with_flags(pr1, r1, BN_FLG_CONSTTIME); 633280304Sjkim } else 634280304Sjkim pr1 = r1; 635280304Sjkim if (!BN_mod(r0, pr1, rsa->p, ctx)) 636280304Sjkim goto err; 637238384Sjkim 638280304Sjkim /* 639280304Sjkim * If p < q it is occasionally possible for the correction of adding 'p' 640280304Sjkim * if r0 is negative above to leave the result still negative. This can 641280304Sjkim * break the private key operations: the following second correction 642280304Sjkim * should *always* correct this rare occurrence. This will *never* happen 643280304Sjkim * with OpenSSL generated keys because they ensure p > q [steve] 644280304Sjkim */ 645280304Sjkim if (BN_is_negative(r0)) 646280304Sjkim if (!BN_add(r0, r0, rsa->p)) 647280304Sjkim goto err; 648280304Sjkim if (!BN_mul(r1, r0, rsa->q, ctx)) 649280304Sjkim goto err; 650280304Sjkim if (!BN_add(r0, r1, m1)) 651280304Sjkim goto err; 652238384Sjkim 653280304Sjkim if (rsa->e && rsa->n) { 654280304Sjkim if (!e_rsax_bn_mod_exp 655280304Sjkim (vrfy, r0, rsa->e, rsa->n, ctx, rsa->_method_mod_n, 656280304Sjkim e_rsax_get_ctx(rsa, 2, rsa->n))) 657280304Sjkim goto err; 658280304Sjkim 659280304Sjkim /* 660280304Sjkim * If 'I' was greater than (or equal to) rsa->n, the operation will 661280304Sjkim * be equivalent to using 'I mod n'. However, the result of the 662280304Sjkim * verify will *always* be less than 'n' so we don't check for 663280304Sjkim * absolute equality, just congruency. 664238384Sjkim */ 665280304Sjkim if (!BN_sub(vrfy, vrfy, I)) 666280304Sjkim goto err; 667280304Sjkim if (!BN_mod(vrfy, vrfy, rsa->n, ctx)) 668280304Sjkim goto err; 669280304Sjkim if (BN_is_negative(vrfy)) 670280304Sjkim if (!BN_add(vrfy, vrfy, rsa->n)) 671280304Sjkim goto err; 672280304Sjkim if (!BN_is_zero(vrfy)) { 673280304Sjkim /* 674280304Sjkim * 'I' and 'vrfy' aren't congruent mod n. Don't leak 675280304Sjkim * miscalculated CRT output, just do a raw (slower) mod_exp and 676280304Sjkim * return that instead. 677280304Sjkim */ 678238384Sjkim 679280304Sjkim BIGNUM local_d; 680280304Sjkim BIGNUM *d = NULL; 681238384Sjkim 682280304Sjkim if (!(rsa->flags & RSA_FLAG_NO_CONSTTIME)) { 683280304Sjkim d = &local_d; 684280304Sjkim BN_with_flags(d, rsa->d, BN_FLG_CONSTTIME); 685280304Sjkim } else 686280304Sjkim d = rsa->d; 687280304Sjkim if (!e_rsax_bn_mod_exp(r0, I, d, rsa->n, ctx, 688280304Sjkim rsa->_method_mod_n, e_rsax_get_ctx(rsa, 2, 689280304Sjkim rsa->n))) 690280304Sjkim goto err; 691280304Sjkim } 692280304Sjkim } 693280304Sjkim ret = 1; 694238384Sjkim 695280304Sjkim err: 696280304Sjkim BN_CTX_end(ctx); 697238384Sjkim 698280304Sjkim return ret; 699280304Sjkim} 700280304Sjkim# endif /* !OPENSSL_NO_RSA */ 701280304Sjkim#endif /* !COMPILE_RSAX */ 702