]>
Commit | Line | Data |
---|---|---|
be9a8cc2 AP |
1 | /* crypto/engine/eng_rsax.c */ |
2 | /* Copyright (c) 2010-2010 Intel Corp. | |
3 | * Author: Vinodh.Gopal@intel.com | |
4 | * Jim Guilford | |
5 | * Erdinc.Ozturk@intel.com | |
6 | * Maxim.Perminov@intel.com | |
7 | * Ying.Huang@intel.com | |
8 | * | |
9 | * More information about algorithm used can be found at: | |
10 | * http://www.cse.buffalo.edu/srds2009/escs2009_submission_Gopal.pdf | |
11 | */ | |
12 | /* ==================================================================== | |
13 | * Copyright (c) 1999-2001 The OpenSSL Project. All rights reserved. | |
14 | * | |
15 | * Redistribution and use in source and binary forms, with or without | |
16 | * modification, are permitted provided that the following conditions | |
17 | * are met: | |
18 | * | |
19 | * 1. Redistributions of source code must retain the above copyright | |
20 | * notice, this list of conditions and the following disclaimer. | |
21 | * | |
22 | * 2. Redistributions in binary form must reproduce the above copyright | |
23 | * notice, this list of conditions and the following disclaimer in | |
24 | * the documentation and/or other materials provided with the | |
25 | * distribution. | |
26 | * | |
27 | * 3. All advertising materials mentioning features or use of this | |
28 | * software must display the following acknowledgment: | |
29 | * "This product includes software developed by the OpenSSL Project | |
30 | * for use in the OpenSSL Toolkit. (http://www.OpenSSL.org/)" | |
31 | * | |
32 | * 4. The names "OpenSSL Toolkit" and "OpenSSL Project" must not be used to | |
33 | * endorse or promote products derived from this software without | |
34 | * prior written permission. For written permission, please contact | |
35 | * licensing@OpenSSL.org. | |
36 | * | |
37 | * 5. Products derived from this software may not be called "OpenSSL" | |
38 | * nor may "OpenSSL" appear in their names without prior written | |
39 | * permission of the OpenSSL Project. | |
40 | * | |
41 | * 6. Redistributions of any form whatsoever must retain the following | |
42 | * acknowledgment: | |
43 | * "This product includes software developed by the OpenSSL Project | |
44 | * for use in the OpenSSL Toolkit (http://www.OpenSSL.org/)" | |
45 | * | |
46 | * THIS SOFTWARE IS PROVIDED BY THE OpenSSL PROJECT ``AS IS'' AND ANY | |
47 | * EXPRESSED OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE | |
48 | * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR | |
49 | * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE OpenSSL PROJECT OR | |
50 | * ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, | |
51 | * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT | |
52 | * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; | |
53 | * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) | |
54 | * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, | |
55 | * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) | |
56 | * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED | |
57 | * OF THE POSSIBILITY OF SUCH DAMAGE. | |
58 | * ==================================================================== | |
59 | * | |
60 | * This product includes cryptographic software written by Eric Young | |
61 | * (eay@cryptsoft.com). This product includes software written by Tim | |
62 | * Hudson (tjh@cryptsoft.com). | |
63 | */ | |
64 | ||
65 | #include <openssl/opensslconf.h> | |
66 | ||
67 | #include <stdio.h> | |
68 | #include <string.h> | |
69 | #include <openssl/crypto.h> | |
70 | #include <openssl/buffer.h> | |
71 | #include <openssl/engine.h> | |
72 | #ifndef OPENSSL_NO_RSA | |
0f113f3e | 73 | # include <openssl/rsa.h> |
be9a8cc2 AP |
74 | #endif |
75 | #include <openssl/bn.h> | |
4f275f24 | 76 | #include <openssl/err.h> |
be9a8cc2 AP |
77 | |
78 | /* RSAX is available **ONLY* on x86_64 CPUs */ | |
79 | #undef COMPILE_RSAX | |
80 | ||
81 | #if (defined(__x86_64) || defined(__x86_64__) || \ | |
82 | defined(_M_AMD64) || defined (_M_X64)) && !defined(OPENSSL_NO_ASM) | |
0f113f3e MC |
83 | # define COMPILE_RSAX |
84 | static ENGINE *ENGINE_rsax(void); | |
be9a8cc2 AP |
85 | #endif |
86 | ||
0f113f3e MC |
87 | void ENGINE_load_rsax(void) |
88 | { | |
be9a8cc2 AP |
89 | /* On non-x86 CPUs it just returns. */ |
90 | #ifdef COMPILE_RSAX | |
0f113f3e MC |
91 | ENGINE *toadd = ENGINE_rsax(); |
92 | if (!toadd) | |
93 | return; | |
94 | ENGINE_add(toadd); | |
95 | ENGINE_free(toadd); | |
96 | ERR_clear_error(); | |
be9a8cc2 | 97 | #endif |
0f113f3e | 98 | } |
be9a8cc2 AP |
99 | |
100 | #ifdef COMPILE_RSAX | |
0f113f3e | 101 | # define E_RSAX_LIB_NAME "rsax engine" |
be9a8cc2 AP |
102 | |
103 | static int e_rsax_destroy(ENGINE *e); | |
104 | static int e_rsax_init(ENGINE *e); | |
105 | static int e_rsax_finish(ENGINE *e); | |
0f113f3e | 106 | static int e_rsax_ctrl(ENGINE *e, int cmd, long i, void *p, void (*f) (void)); |
be9a8cc2 | 107 | |
0f113f3e | 108 | # ifndef OPENSSL_NO_RSA |
be9a8cc2 | 109 | /* RSA stuff */ |
0f113f3e MC |
110 | static int e_rsax_rsa_mod_exp(BIGNUM *r, const BIGNUM *I, RSA *rsa, |
111 | BN_CTX *ctx); | |
be9a8cc2 | 112 | static int e_rsax_rsa_finish(RSA *r); |
0f113f3e | 113 | # endif |
be9a8cc2 AP |
114 | |
115 | static const ENGINE_CMD_DEFN e_rsax_cmd_defns[] = { | |
0f113f3e MC |
116 | {0, NULL, NULL, 0} |
117 | }; | |
be9a8cc2 | 118 | |
0f113f3e | 119 | # ifndef OPENSSL_NO_RSA |
be9a8cc2 | 120 | /* Our internal RSA_METHOD that we provide pointers to */ |
0f113f3e MC |
121 | static RSA_METHOD e_rsax_rsa = { |
122 | "Intel RSA-X method", | |
123 | NULL, | |
124 | NULL, | |
125 | NULL, | |
126 | NULL, | |
127 | e_rsax_rsa_mod_exp, | |
128 | NULL, | |
129 | NULL, | |
130 | e_rsax_rsa_finish, | |
131 | RSA_FLAG_CACHE_PUBLIC | RSA_FLAG_CACHE_PRIVATE, | |
132 | NULL, | |
133 | NULL, | |
134 | NULL | |
135 | }; | |
136 | # endif | |
be9a8cc2 AP |
137 | |
138 | /* Constants used when creating the ENGINE */ | |
139 | static const char *engine_e_rsax_id = "rsax"; | |
140 | static const char *engine_e_rsax_name = "RSAX engine support"; | |
141 | ||
142 | /* This internal function is used by ENGINE_rsax() */ | |
143 | static int bind_helper(ENGINE *e) | |
0f113f3e MC |
144 | { |
145 | # ifndef OPENSSL_NO_RSA | |
146 | const RSA_METHOD *meth1; | |
147 | # endif | |
148 | if (!ENGINE_set_id(e, engine_e_rsax_id) || | |
149 | !ENGINE_set_name(e, engine_e_rsax_name) || | |
150 | # ifndef OPENSSL_NO_RSA | |
151 | !ENGINE_set_RSA(e, &e_rsax_rsa) || | |
152 | # endif | |
153 | !ENGINE_set_destroy_function(e, e_rsax_destroy) || | |
154 | !ENGINE_set_init_function(e, e_rsax_init) || | |
155 | !ENGINE_set_finish_function(e, e_rsax_finish) || | |
156 | !ENGINE_set_ctrl_function(e, e_rsax_ctrl) || | |
157 | !ENGINE_set_cmd_defns(e, e_rsax_cmd_defns)) | |
158 | return 0; | |
be9a8cc2 | 159 | |
0f113f3e MC |
160 | # ifndef OPENSSL_NO_RSA |
161 | meth1 = RSA_PKCS1_SSLeay(); | |
162 | e_rsax_rsa.rsa_pub_enc = meth1->rsa_pub_enc; | |
163 | e_rsax_rsa.rsa_pub_dec = meth1->rsa_pub_dec; | |
164 | e_rsax_rsa.rsa_priv_enc = meth1->rsa_priv_enc; | |
165 | e_rsax_rsa.rsa_priv_dec = meth1->rsa_priv_dec; | |
166 | e_rsax_rsa.bn_mod_exp = meth1->bn_mod_exp; | |
167 | # endif | |
168 | return 1; | |
169 | } | |
be9a8cc2 AP |
170 | |
171 | static ENGINE *ENGINE_rsax(void) | |
0f113f3e MC |
172 | { |
173 | ENGINE *ret = ENGINE_new(); | |
174 | if (!ret) | |
175 | return NULL; | |
176 | if (!bind_helper(ret)) { | |
177 | ENGINE_free(ret); | |
178 | return NULL; | |
179 | } | |
180 | return ret; | |
181 | } | |
be9a8cc2 | 182 | |
0f113f3e | 183 | # ifndef OPENSSL_NO_RSA |
be9a8cc2 AP |
184 | /* Used to attach our own key-data to an RSA structure */ |
185 | static int rsax_ex_data_idx = -1; | |
0f113f3e | 186 | # endif |
be9a8cc2 AP |
187 | |
188 | static int e_rsax_destroy(ENGINE *e) | |
0f113f3e MC |
189 | { |
190 | return 1; | |
191 | } | |
be9a8cc2 AP |
192 | |
193 | /* (de)initialisation functions. */ | |
194 | static int e_rsax_init(ENGINE *e) | |
0f113f3e MC |
195 | { |
196 | # ifndef OPENSSL_NO_RSA | |
197 | if (rsax_ex_data_idx == -1) | |
198 | rsax_ex_data_idx = RSA_get_ex_new_index(0, NULL, NULL, NULL, NULL); | |
199 | # endif | |
200 | if (rsax_ex_data_idx == -1) | |
201 | return 0; | |
202 | return 1; | |
203 | } | |
be9a8cc2 AP |
204 | |
205 | static int e_rsax_finish(ENGINE *e) | |
0f113f3e MC |
206 | { |
207 | return 1; | |
208 | } | |
be9a8cc2 | 209 | |
0f113f3e MC |
210 | static int e_rsax_ctrl(ENGINE *e, int cmd, long i, void *p, void (*f) (void)) |
211 | { | |
212 | int to_return = 1; | |
be9a8cc2 | 213 | |
0f113f3e MC |
214 | switch (cmd) { |
215 | /* The command isn't understood by this engine */ | |
216 | default: | |
217 | to_return = 0; | |
218 | break; | |
219 | } | |
be9a8cc2 | 220 | |
0f113f3e MC |
221 | return to_return; |
222 | } | |
be9a8cc2 | 223 | |
0f113f3e | 224 | # ifndef OPENSSL_NO_RSA |
be9a8cc2 | 225 | |
0f113f3e | 226 | # ifdef _WIN32 |
c2d4c286 | 227 | typedef unsigned __int64 UINT64; |
0f113f3e | 228 | # else |
c2d4c286 | 229 | typedef unsigned long long UINT64; |
0f113f3e | 230 | # endif |
c2d4c286 | 231 | typedef unsigned short UINT16; |
be9a8cc2 | 232 | |
0f113f3e MC |
233 | /* |
234 | * Table t is interleaved in the following manner: The order in memory is | |
235 | * t[0][0], t[0][1], ..., t[0][7], t[1][0], ... A particular 512-bit value is | |
236 | * stored in t[][index] rather than the more normal t[index][]; i.e. the | |
237 | * qwords of a particular entry in t are not adjacent in memory | |
be9a8cc2 AP |
238 | */ |
239 | ||
240 | /* Init BIGNUM b from the interleaved UINT64 array */ | |
0f113f3e | 241 | static int interleaved_array_to_bn_512(BIGNUM *b, UINT64 *array); |
be9a8cc2 | 242 | |
0f113f3e MC |
243 | /* |
244 | * Extract array elements from BIGNUM b To set the whole array from b, call | |
245 | * with n=8 | |
be9a8cc2 | 246 | */ |
0f113f3e MC |
247 | static int bn_extract_to_array_512(const BIGNUM *b, unsigned int n, |
248 | UINT64 *array); | |
be9a8cc2 AP |
249 | |
250 | struct mod_ctx_512 { | |
251 | UINT64 t[8][8]; | |
252 | UINT64 m[8]; | |
0f113f3e MC |
253 | UINT64 m1[8]; /* 2^278 % m */ |
254 | UINT64 m2[8]; /* 2^640 % m */ | |
255 | UINT64 k1[2]; /* (- 1/m) % 2^128 */ | |
be9a8cc2 AP |
256 | }; |
257 | ||
258 | static int mod_exp_pre_compute_data_512(UINT64 *m, struct mod_ctx_512 *data); | |
259 | ||
260 | void mod_exp_512(UINT64 *result, /* 512 bits, 8 qwords */ | |
0f113f3e MC |
261 | UINT64 *g, /* 512 bits, 8 qwords */ |
262 | UINT64 *exp, /* 512 bits, 8 qwords */ | |
263 | struct mod_ctx_512 *data); | |
be9a8cc2 | 264 | |
0f113f3e MC |
265 | typedef struct st_e_rsax_mod_ctx { |
266 | UINT64 type; | |
267 | union { | |
268 | struct mod_ctx_512 b512; | |
269 | } ctx; | |
be9a8cc2 AP |
270 | |
271 | } E_RSAX_MOD_CTX; | |
272 | ||
0f113f3e | 273 | static E_RSAX_MOD_CTX *e_rsax_get_ctx(RSA *rsa, int idx, BIGNUM *m) |
be9a8cc2 | 274 | { |
0f113f3e MC |
275 | E_RSAX_MOD_CTX *hptr; |
276 | ||
277 | if (idx < 0 || idx > 2) | |
278 | return NULL; | |
279 | ||
280 | hptr = RSA_get_ex_data(rsa, rsax_ex_data_idx); | |
281 | if (!hptr) { | |
282 | hptr = OPENSSL_malloc(3 * sizeof(E_RSAX_MOD_CTX)); | |
283 | if (!hptr) | |
284 | return NULL; | |
285 | hptr[2].type = hptr[1].type = hptr[0].type = 0; | |
286 | RSA_set_ex_data(rsa, rsax_ex_data_idx, hptr); | |
287 | } | |
be9a8cc2 | 288 | |
0f113f3e MC |
289 | if (hptr[idx].type == (UINT64)BN_num_bits(m)) |
290 | return hptr + idx; | |
be9a8cc2 | 291 | |
0f113f3e MC |
292 | if (BN_num_bits(m) == 512) { |
293 | UINT64 _m[8]; | |
294 | bn_extract_to_array_512(m, 8, _m); | |
295 | memset(&hptr[idx].ctx.b512, 0, sizeof(struct mod_ctx_512)); | |
296 | mod_exp_pre_compute_data_512(_m, &hptr[idx].ctx.b512); | |
297 | } | |
be9a8cc2 | 298 | |
0f113f3e MC |
299 | hptr[idx].type = BN_num_bits(m); |
300 | return hptr + idx; | |
be9a8cc2 AP |
301 | } |
302 | ||
303 | static int e_rsax_rsa_finish(RSA *rsa) | |
0f113f3e MC |
304 | { |
305 | E_RSAX_MOD_CTX *hptr = RSA_get_ex_data(rsa, rsax_ex_data_idx); | |
306 | if (hptr) { | |
307 | OPENSSL_free(hptr); | |
308 | RSA_set_ex_data(rsa, rsax_ex_data_idx, NULL); | |
309 | } | |
310 | if (rsa->_method_mod_n) | |
311 | BN_MONT_CTX_free(rsa->_method_mod_n); | |
312 | if (rsa->_method_mod_p) | |
313 | BN_MONT_CTX_free(rsa->_method_mod_p); | |
314 | if (rsa->_method_mod_q) | |
315 | BN_MONT_CTX_free(rsa->_method_mod_q); | |
316 | return 1; | |
317 | } | |
be9a8cc2 AP |
318 | |
319 | static int e_rsax_bn_mod_exp(BIGNUM *r, const BIGNUM *g, const BIGNUM *e, | |
0f113f3e MC |
320 | const BIGNUM *m, BN_CTX *ctx, |
321 | BN_MONT_CTX *in_mont, | |
322 | E_RSAX_MOD_CTX *rsax_mod_ctx) | |
be9a8cc2 | 323 | { |
0f113f3e MC |
324 | if (rsax_mod_ctx && BN_get_flags(e, BN_FLG_CONSTTIME) != 0) { |
325 | if (BN_num_bits(m) == 512) { | |
326 | UINT64 _r[8]; | |
327 | UINT64 _g[8]; | |
328 | UINT64 _e[8]; | |
329 | ||
330 | /* Init the arrays from the BIGNUMs */ | |
331 | bn_extract_to_array_512(g, 8, _g); | |
332 | bn_extract_to_array_512(e, 8, _e); | |
333 | ||
334 | mod_exp_512(_r, _g, _e, &rsax_mod_ctx->ctx.b512); | |
335 | /* Return the result in the BIGNUM */ | |
336 | interleaved_array_to_bn_512(r, _r); | |
337 | return 1; | |
be9a8cc2 | 338 | } |
0f113f3e | 339 | } |
be9a8cc2 | 340 | |
0f113f3e | 341 | return BN_mod_exp_mont(r, g, e, m, ctx, in_mont); |
be9a8cc2 AP |
342 | } |
343 | ||
0f113f3e MC |
344 | /* |
345 | * Declares for the Intel CIAP 512-bit / CRT / 1024 bit RSA modular | |
be9a8cc2 | 346 | * exponentiation routine precalculations and a structure to hold the |
0f113f3e MC |
347 | * necessary values. These files are meant to live in crypto/rsa/ in the |
348 | * target openssl. | |
be9a8cc2 AP |
349 | */ |
350 | ||
351 | /* | |
352 | * Local method: extracts a piece from a BIGNUM, to fit it into | |
353 | * an array. Call with n=8 to extract an entire 512-bit BIGNUM | |
354 | */ | |
0f113f3e MC |
355 | static int bn_extract_to_array_512(const BIGNUM *b, unsigned int n, |
356 | UINT64 *array) | |
be9a8cc2 | 357 | { |
0f113f3e MC |
358 | int i; |
359 | UINT64 tmp; | |
360 | unsigned char bn_buff[64]; | |
361 | memset(bn_buff, 0, 64); | |
362 | if (BN_num_bytes(b) > 64) { | |
363 | printf("Can't support this byte size\n"); | |
364 | return 0; | |
365 | } | |
366 | if (BN_num_bytes(b) != 0) { | |
367 | if (!BN_bn2bin(b, bn_buff + (64 - BN_num_bytes(b)))) { | |
368 | printf("Error's in bn2bin\n"); | |
369 | /* We have to error, here */ | |
370 | return 0; | |
371 | } | |
372 | } | |
373 | while (n-- > 0) { | |
374 | array[n] = 0; | |
375 | for (i = 7; i >= 0; i--) { | |
376 | tmp = bn_buff[63 - (n * 8 + i)]; | |
377 | array[n] |= tmp << (8 * i); | |
378 | } | |
379 | } | |
380 | return 1; | |
be9a8cc2 AP |
381 | } |
382 | ||
383 | /* Init a 512-bit BIGNUM from the UINT64*_ (8 * 64) interleaved array */ | |
0f113f3e | 384 | static int interleaved_array_to_bn_512(BIGNUM *b, UINT64 *array) |
be9a8cc2 | 385 | { |
0f113f3e MC |
386 | unsigned char tmp[64]; |
387 | int n = 8; | |
388 | int i; | |
389 | while (n-- > 0) { | |
390 | for (i = 7; i >= 0; i--) { | |
391 | tmp[63 - (n * 8 + i)] = (unsigned char)(array[n] >> (8 * i)); | |
392 | }} | |
393 | BN_bin2bn(tmp, 64, b); | |
394 | return 0; | |
be9a8cc2 AP |
395 | } |
396 | ||
be9a8cc2 AP |
397 | /* The main 512bit precompute call */ |
398 | static int mod_exp_pre_compute_data_512(UINT64 *m, struct mod_ctx_512 *data) | |
0f113f3e | 399 | { |
be9a8cc2 AP |
400 | BIGNUM two_768, two_640, two_128, two_512, tmp, _m, tmp2; |
401 | ||
402 | /* We need a BN_CTX for the modulo functions */ | |
0f113f3e | 403 | BN_CTX *ctx; |
be9a8cc2 AP |
404 | /* Some tmps */ |
405 | UINT64 _t[8]; | |
406 | int i, j, ret = 0; | |
71fa4513 | 407 | |
be9a8cc2 AP |
408 | /* Init _m with m */ |
409 | BN_init(&_m); | |
410 | interleaved_array_to_bn_512(&_m, m); | |
411 | memset(_t, 0, 64); | |
412 | ||
413 | /* Inits */ | |
414 | BN_init(&two_768); | |
415 | BN_init(&two_640); | |
416 | BN_init(&two_128); | |
417 | BN_init(&two_512); | |
418 | BN_init(&tmp); | |
419 | BN_init(&tmp2); | |
420 | ||
421 | /* Create our context */ | |
0f113f3e MC |
422 | if ((ctx = BN_CTX_new()) == NULL) { |
423 | goto err; | |
424 | } | |
425 | BN_CTX_start(ctx); | |
be9a8cc2 AP |
426 | |
427 | /* | |
428 | * For production, if you care, these only need to be set once, | |
429 | * and may be made constants. | |
430 | */ | |
431 | BN_lshift(&two_768, BN_value_one(), 768); | |
432 | BN_lshift(&two_640, BN_value_one(), 640); | |
433 | BN_lshift(&two_128, BN_value_one(), 128); | |
434 | BN_lshift(&two_512, BN_value_one(), 512); | |
435 | ||
436 | if (0 == (m[7] & 0x8000000000000000)) { | |
437 | exit(1); | |
438 | } | |
0f113f3e | 439 | if (0 == (m[0] & 0x1)) { /* Odd modulus required for Mont */ |
be9a8cc2 AP |
440 | exit(1); |
441 | } | |
442 | ||
443 | /* Precompute m1 */ | |
444 | BN_mod(&tmp, &two_768, &_m, ctx); | |
445 | if (!bn_extract_to_array_512(&tmp, 8, &data->m1[0])) { | |
0f113f3e MC |
446 | goto err; |
447 | } | |
be9a8cc2 AP |
448 | |
449 | /* Precompute m2 */ | |
450 | BN_mod(&tmp, &two_640, &_m, ctx); | |
451 | if (!bn_extract_to_array_512(&tmp, 8, &data->m2[0])) { | |
0f113f3e | 452 | goto err; |
be9a8cc2 AP |
453 | } |
454 | ||
455 | /* | |
456 | * Precompute k1, a 128b number = ((-1)* m-1 ) mod 2128; k1 should | |
457 | * be non-negative. | |
458 | */ | |
459 | BN_mod_inverse(&tmp, &_m, &two_128, ctx); | |
0f113f3e MC |
460 | if (!BN_is_zero(&tmp)) { |
461 | BN_sub(&tmp, &two_128, &tmp); | |
462 | } | |
be9a8cc2 | 463 | if (!bn_extract_to_array_512(&tmp, 2, &data->k1[0])) { |
0f113f3e MC |
464 | goto err; |
465 | } | |
be9a8cc2 AP |
466 | |
467 | /* Precompute t */ | |
0f113f3e | 468 | for (i = 0; i < 8; i++) { |
be9a8cc2 | 469 | BN_zero(&tmp); |
0f113f3e MC |
470 | if (i & 1) { |
471 | BN_add(&tmp, &two_512, &tmp); | |
472 | } | |
473 | if (i & 2) { | |
474 | BN_add(&tmp, &two_512, &tmp); | |
475 | } | |
476 | if (i & 4) { | |
477 | BN_add(&tmp, &two_640, &tmp); | |
478 | } | |
be9a8cc2 AP |
479 | |
480 | BN_nnmod(&tmp2, &tmp, &_m, ctx); | |
481 | if (!bn_extract_to_array_512(&tmp2, 8, _t)) { | |
0f113f3e MC |
482 | goto err; |
483 | } | |
484 | for (j = 0; j < 8; j++) | |
485 | data->t[j][i] = _t[j]; | |
486 | } | |
be9a8cc2 AP |
487 | |
488 | /* Precompute m */ | |
0f113f3e MC |
489 | for (i = 0; i < 8; i++) { |
490 | data->m[i] = m[i]; | |
491 | } | |
be9a8cc2 AP |
492 | |
493 | ret = 1; | |
494 | ||
0f113f3e | 495 | err: |
be9a8cc2 | 496 | /* Cleanup */ |
0f113f3e MC |
497 | if (ctx != NULL) { |
498 | BN_CTX_end(ctx); | |
499 | BN_CTX_free(ctx); | |
500 | } | |
be9a8cc2 AP |
501 | BN_free(&two_768); |
502 | BN_free(&two_640); | |
503 | BN_free(&two_128); | |
504 | BN_free(&two_512); | |
505 | BN_free(&tmp); | |
506 | BN_free(&tmp2); | |
507 | BN_free(&_m); | |
508 | ||
509 | return ret; | |
510 | } | |
511 | ||
0f113f3e MC |
512 | static int e_rsax_rsa_mod_exp(BIGNUM *r0, const BIGNUM *I, RSA *rsa, |
513 | BN_CTX *ctx) | |
514 | { | |
515 | BIGNUM *r1, *m1, *vrfy; | |
516 | BIGNUM local_dmp1, local_dmq1, local_c, local_r1; | |
517 | BIGNUM *dmp1, *dmq1, *c, *pr1; | |
518 | int ret = 0; | |
519 | ||
520 | BN_CTX_start(ctx); | |
521 | r1 = BN_CTX_get(ctx); | |
522 | m1 = BN_CTX_get(ctx); | |
523 | vrfy = BN_CTX_get(ctx); | |
524 | ||
525 | { | |
526 | BIGNUM local_p, local_q; | |
527 | BIGNUM *p = NULL, *q = NULL; | |
528 | int error = 0; | |
529 | ||
530 | /* | |
531 | * Make sure BN_mod_inverse in Montgomery intialization uses the | |
532 | * BN_FLG_CONSTTIME flag (unless RSA_FLAG_NO_CONSTTIME is set) | |
533 | */ | |
534 | if (!(rsa->flags & RSA_FLAG_NO_CONSTTIME)) { | |
535 | BN_init(&local_p); | |
536 | p = &local_p; | |
537 | BN_with_flags(p, rsa->p, BN_FLG_CONSTTIME); | |
538 | ||
539 | BN_init(&local_q); | |
540 | q = &local_q; | |
541 | BN_with_flags(q, rsa->q, BN_FLG_CONSTTIME); | |
542 | } else { | |
543 | p = rsa->p; | |
544 | q = rsa->q; | |
545 | } | |
546 | ||
547 | if (rsa->flags & RSA_FLAG_CACHE_PRIVATE) { | |
548 | if (!BN_MONT_CTX_set_locked | |
549 | (&rsa->_method_mod_p, CRYPTO_LOCK_RSA, p, ctx)) | |
550 | error = 1; | |
551 | if (!BN_MONT_CTX_set_locked | |
552 | (&rsa->_method_mod_q, CRYPTO_LOCK_RSA, q, ctx)) | |
553 | error = 1; | |
554 | } | |
555 | ||
556 | /* clean up */ | |
557 | if (!(rsa->flags & RSA_FLAG_NO_CONSTTIME)) { | |
558 | BN_free(&local_p); | |
559 | BN_free(&local_q); | |
560 | } | |
561 | if (error) | |
562 | goto err; | |
563 | } | |
564 | ||
565 | if (rsa->flags & RSA_FLAG_CACHE_PUBLIC) | |
566 | if (!BN_MONT_CTX_set_locked | |
567 | (&rsa->_method_mod_n, CRYPTO_LOCK_RSA, rsa->n, ctx)) | |
568 | goto err; | |
569 | ||
570 | /* compute I mod q */ | |
571 | if (!(rsa->flags & RSA_FLAG_NO_CONSTTIME)) { | |
572 | c = &local_c; | |
573 | BN_with_flags(c, I, BN_FLG_CONSTTIME); | |
574 | if (!BN_mod(r1, c, rsa->q, ctx)) | |
575 | goto err; | |
576 | } else { | |
577 | if (!BN_mod(r1, I, rsa->q, ctx)) | |
578 | goto err; | |
579 | } | |
580 | ||
581 | /* compute r1^dmq1 mod q */ | |
582 | if (!(rsa->flags & RSA_FLAG_NO_CONSTTIME)) { | |
583 | dmq1 = &local_dmq1; | |
584 | BN_with_flags(dmq1, rsa->dmq1, BN_FLG_CONSTTIME); | |
585 | } else | |
586 | dmq1 = rsa->dmq1; | |
587 | ||
588 | if (!e_rsax_bn_mod_exp(m1, r1, dmq1, rsa->q, ctx, | |
589 | rsa->_method_mod_q, e_rsax_get_ctx(rsa, 0, | |
590 | rsa->q))) | |
591 | goto err; | |
592 | ||
593 | /* compute I mod p */ | |
594 | if (!(rsa->flags & RSA_FLAG_NO_CONSTTIME)) { | |
595 | c = &local_c; | |
596 | BN_with_flags(c, I, BN_FLG_CONSTTIME); | |
597 | if (!BN_mod(r1, c, rsa->p, ctx)) | |
598 | goto err; | |
599 | } else { | |
600 | if (!BN_mod(r1, I, rsa->p, ctx)) | |
601 | goto err; | |
602 | } | |
603 | ||
604 | /* compute r1^dmp1 mod p */ | |
605 | if (!(rsa->flags & RSA_FLAG_NO_CONSTTIME)) { | |
606 | dmp1 = &local_dmp1; | |
607 | BN_with_flags(dmp1, rsa->dmp1, BN_FLG_CONSTTIME); | |
608 | } else | |
609 | dmp1 = rsa->dmp1; | |
610 | ||
611 | if (!e_rsax_bn_mod_exp(r0, r1, dmp1, rsa->p, ctx, | |
612 | rsa->_method_mod_p, e_rsax_get_ctx(rsa, 1, | |
613 | rsa->p))) | |
614 | goto err; | |
be9a8cc2 | 615 | |
0f113f3e MC |
616 | if (!BN_sub(r0, r0, m1)) |
617 | goto err; | |
618 | /* | |
619 | * This will help stop the size of r0 increasing, which does affect the | |
620 | * multiply if it optimised for a power of 2 size | |
621 | */ | |
622 | if (BN_is_negative(r0)) | |
623 | if (!BN_add(r0, r0, rsa->p)) | |
624 | goto err; | |
625 | ||
626 | if (!BN_mul(r1, r0, rsa->iqmp, ctx)) | |
627 | goto err; | |
628 | ||
629 | /* Turn BN_FLG_CONSTTIME flag on before division operation */ | |
630 | if (!(rsa->flags & RSA_FLAG_NO_CONSTTIME)) { | |
631 | pr1 = &local_r1; | |
632 | BN_with_flags(pr1, r1, BN_FLG_CONSTTIME); | |
633 | } else | |
634 | pr1 = r1; | |
635 | if (!BN_mod(r0, pr1, rsa->p, ctx)) | |
636 | goto err; | |
637 | ||
638 | /* | |
639 | * If p < q it is occasionally possible for the correction of adding 'p' | |
640 | * if r0 is negative above to leave the result still negative. This can | |
641 | * break the private key operations: the following second correction | |
642 | * should *always* correct this rare occurrence. This will *never* happen | |
643 | * with OpenSSL generated keys because they ensure p > q [steve] | |
644 | */ | |
645 | if (BN_is_negative(r0)) | |
646 | if (!BN_add(r0, r0, rsa->p)) | |
647 | goto err; | |
648 | if (!BN_mul(r1, r0, rsa->q, ctx)) | |
649 | goto err; | |
650 | if (!BN_add(r0, r1, m1)) | |
651 | goto err; | |
652 | ||
653 | if (rsa->e && rsa->n) { | |
654 | if (!e_rsax_bn_mod_exp | |
655 | (vrfy, r0, rsa->e, rsa->n, ctx, rsa->_method_mod_n, | |
656 | e_rsax_get_ctx(rsa, 2, rsa->n))) | |
657 | goto err; | |
658 | ||
659 | /* | |
660 | * If 'I' was greater than (or equal to) rsa->n, the operation will | |
661 | * be equivalent to using 'I mod n'. However, the result of the | |
662 | * verify will *always* be less than 'n' so we don't check for | |
663 | * absolute equality, just congruency. | |
be9a8cc2 | 664 | */ |
0f113f3e MC |
665 | if (!BN_sub(vrfy, vrfy, I)) |
666 | goto err; | |
667 | if (!BN_mod(vrfy, vrfy, rsa->n, ctx)) | |
668 | goto err; | |
669 | if (BN_is_negative(vrfy)) | |
670 | if (!BN_add(vrfy, vrfy, rsa->n)) | |
671 | goto err; | |
672 | if (!BN_is_zero(vrfy)) { | |
673 | /* | |
674 | * 'I' and 'vrfy' aren't congruent mod n. Don't leak | |
675 | * miscalculated CRT output, just do a raw (slower) mod_exp and | |
676 | * return that instead. | |
677 | */ | |
678 | ||
679 | BIGNUM local_d; | |
680 | BIGNUM *d = NULL; | |
681 | ||
682 | if (!(rsa->flags & RSA_FLAG_NO_CONSTTIME)) { | |
683 | d = &local_d; | |
684 | BN_with_flags(d, rsa->d, BN_FLG_CONSTTIME); | |
685 | } else | |
686 | d = rsa->d; | |
687 | if (!e_rsax_bn_mod_exp(r0, I, d, rsa->n, ctx, | |
688 | rsa->_method_mod_n, e_rsax_get_ctx(rsa, 2, | |
689 | rsa->n))) | |
690 | goto err; | |
691 | } | |
692 | } | |
693 | ret = 1; | |
694 | ||
695 | err: | |
696 | BN_CTX_end(ctx); | |
697 | ||
698 | return ret; | |
699 | } | |
700 | # endif /* !OPENSSL_NO_RSA */ | |
701 | #endif /* !COMPILE_RSAX */ |