ced11ad883c98e17b53e073e4da63c5010d5f0ea
[openssl.git] / crypto / rsa / rsa_ossl.c
1 /*
2  * Copyright 1995-2017 The OpenSSL Project Authors. All Rights Reserved.
3  *
4  * Licensed under the OpenSSL license (the "License").  You may not use
5  * this file except in compliance with the License.  You can obtain a copy
6  * in the file LICENSE in the source distribution or at
7  * https://www.openssl.org/source/license.html
8  */
9
10 #include "internal/cryptlib.h"
11 #include "internal/bn_int.h"
12 #include "rsa_locl.h"
13
14 static int rsa_ossl_public_encrypt(int flen, const unsigned char *from,
15                                   unsigned char *to, RSA *rsa, int padding);
16 static int rsa_ossl_private_encrypt(int flen, const unsigned char *from,
17                                    unsigned char *to, RSA *rsa, int padding);
18 static int rsa_ossl_public_decrypt(int flen, const unsigned char *from,
19                                   unsigned char *to, RSA *rsa, int padding);
20 static int rsa_ossl_private_decrypt(int flen, const unsigned char *from,
21                                    unsigned char *to, RSA *rsa, int padding);
22 static int rsa_ossl_mod_exp(BIGNUM *r0, const BIGNUM *i, RSA *rsa,
23                            BN_CTX *ctx);
24 static int rsa_ossl_init(RSA *rsa);
25 static int rsa_ossl_finish(RSA *rsa);
26 static RSA_METHOD rsa_pkcs1_ossl_meth = {
27     "OpenSSL PKCS#1 RSA",
28     rsa_ossl_public_encrypt,
29     rsa_ossl_public_decrypt,     /* signature verification */
30     rsa_ossl_private_encrypt,    /* signing */
31     rsa_ossl_private_decrypt,
32     rsa_ossl_mod_exp,
33     BN_mod_exp_mont,            /* XXX probably we should not use Montgomery
34                                  * if e == 3 */
35     rsa_ossl_init,
36     rsa_ossl_finish,
37     RSA_FLAG_FIPS_METHOD,       /* flags */
38     NULL,
39     0,                          /* rsa_sign */
40     0,                          /* rsa_verify */
41     NULL,                       /* rsa_keygen */
42     NULL                        /* rsa_multi_prime_keygen */
43 };
44
45 static const RSA_METHOD *default_RSA_meth = &rsa_pkcs1_ossl_meth;
46
47 void RSA_set_default_method(const RSA_METHOD *meth)
48 {
49     default_RSA_meth = meth;
50 }
51
52 const RSA_METHOD *RSA_get_default_method(void)
53 {
54     return default_RSA_meth;
55 }
56
57 const RSA_METHOD *RSA_PKCS1_OpenSSL(void)
58 {
59     return &rsa_pkcs1_ossl_meth;
60 }
61
62 const RSA_METHOD *RSA_null_method(void)
63 {
64     return NULL;
65 }
66
67 static int rsa_ossl_public_encrypt(int flen, const unsigned char *from,
68                                   unsigned char *to, RSA *rsa, int padding)
69 {
70     BIGNUM *f, *ret;
71     int i, j, k, num = 0, r = -1;
72     unsigned char *buf = NULL;
73     BN_CTX *ctx = NULL;
74
75     if (BN_num_bits(rsa->n) > OPENSSL_RSA_MAX_MODULUS_BITS) {
76         RSAerr(RSA_F_RSA_OSSL_PUBLIC_ENCRYPT, RSA_R_MODULUS_TOO_LARGE);
77         return -1;
78     }
79
80     if (BN_ucmp(rsa->n, rsa->e) <= 0) {
81         RSAerr(RSA_F_RSA_OSSL_PUBLIC_ENCRYPT, RSA_R_BAD_E_VALUE);
82         return -1;
83     }
84
85     /* for large moduli, enforce exponent limit */
86     if (BN_num_bits(rsa->n) > OPENSSL_RSA_SMALL_MODULUS_BITS) {
87         if (BN_num_bits(rsa->e) > OPENSSL_RSA_MAX_PUBEXP_BITS) {
88             RSAerr(RSA_F_RSA_OSSL_PUBLIC_ENCRYPT, RSA_R_BAD_E_VALUE);
89             return -1;
90         }
91     }
92
93     if ((ctx = BN_CTX_new()) == NULL)
94         goto err;
95     BN_CTX_start(ctx);
96     f = BN_CTX_get(ctx);
97     ret = BN_CTX_get(ctx);
98     num = BN_num_bytes(rsa->n);
99     buf = OPENSSL_malloc(num);
100     if (ret == NULL || buf == NULL) {
101         RSAerr(RSA_F_RSA_OSSL_PUBLIC_ENCRYPT, ERR_R_MALLOC_FAILURE);
102         goto err;
103     }
104
105     switch (padding) {
106     case RSA_PKCS1_PADDING:
107         i = RSA_padding_add_PKCS1_type_2(buf, num, from, flen);
108         break;
109     case RSA_PKCS1_OAEP_PADDING:
110         i = RSA_padding_add_PKCS1_OAEP(buf, num, from, flen, NULL, 0);
111         break;
112     case RSA_SSLV23_PADDING:
113         i = RSA_padding_add_SSLv23(buf, num, from, flen);
114         break;
115     case RSA_NO_PADDING:
116         i = RSA_padding_add_none(buf, num, from, flen);
117         break;
118     default:
119         RSAerr(RSA_F_RSA_OSSL_PUBLIC_ENCRYPT, RSA_R_UNKNOWN_PADDING_TYPE);
120         goto err;
121     }
122     if (i <= 0)
123         goto err;
124
125     if (BN_bin2bn(buf, num, f) == NULL)
126         goto err;
127
128     if (BN_ucmp(f, rsa->n) >= 0) {
129         /* usually the padding functions would catch this */
130         RSAerr(RSA_F_RSA_OSSL_PUBLIC_ENCRYPT,
131                RSA_R_DATA_TOO_LARGE_FOR_MODULUS);
132         goto err;
133     }
134
135     if (rsa->flags & RSA_FLAG_CACHE_PUBLIC)
136         if (!BN_MONT_CTX_set_locked
137             (&rsa->_method_mod_n, rsa->lock, rsa->n, ctx))
138             goto err;
139
140     if (!rsa->meth->bn_mod_exp(ret, f, rsa->e, rsa->n, ctx,
141                                rsa->_method_mod_n))
142         goto err;
143
144     /*
145      * put in leading 0 bytes if the number is less than the length of the
146      * modulus
147      */
148     j = BN_num_bytes(ret);
149     i = BN_bn2bin(ret, &(to[num - j]));
150     for (k = 0; k < (num - i); k++)
151         to[k] = 0;
152
153     r = num;
154  err:
155     if (ctx != NULL)
156         BN_CTX_end(ctx);
157     BN_CTX_free(ctx);
158     OPENSSL_clear_free(buf, num);
159     return r;
160 }
161
162 static BN_BLINDING *rsa_get_blinding(RSA *rsa, int *local, BN_CTX *ctx)
163 {
164     BN_BLINDING *ret;
165
166     CRYPTO_THREAD_write_lock(rsa->lock);
167
168     if (rsa->blinding == NULL) {
169         rsa->blinding = RSA_setup_blinding(rsa, ctx);
170     }
171
172     ret = rsa->blinding;
173     if (ret == NULL)
174         goto err;
175
176     if (BN_BLINDING_is_current_thread(ret)) {
177         /* rsa->blinding is ours! */
178
179         *local = 1;
180     } else {
181         /* resort to rsa->mt_blinding instead */
182
183         /*
184          * instructs rsa_blinding_convert(), rsa_blinding_invert() that the
185          * BN_BLINDING is shared, meaning that accesses require locks, and
186          * that the blinding factor must be stored outside the BN_BLINDING
187          */
188         *local = 0;
189
190         if (rsa->mt_blinding == NULL) {
191             rsa->mt_blinding = RSA_setup_blinding(rsa, ctx);
192         }
193         ret = rsa->mt_blinding;
194     }
195
196  err:
197     CRYPTO_THREAD_unlock(rsa->lock);
198     return ret;
199 }
200
201 static int rsa_blinding_convert(BN_BLINDING *b, BIGNUM *f, BIGNUM *unblind,
202                                 BN_CTX *ctx)
203 {
204     if (unblind == NULL) {
205         /*
206          * Local blinding: store the unblinding factor in BN_BLINDING.
207          */
208         return BN_BLINDING_convert_ex(f, NULL, b, ctx);
209     } else {
210         /*
211          * Shared blinding: store the unblinding factor outside BN_BLINDING.
212          */
213         int ret;
214
215         BN_BLINDING_lock(b);
216         ret = BN_BLINDING_convert_ex(f, unblind, b, ctx);
217         BN_BLINDING_unlock(b);
218
219         return ret;
220     }
221 }
222
223 static int rsa_blinding_invert(BN_BLINDING *b, BIGNUM *f, BIGNUM *unblind,
224                                BN_CTX *ctx)
225 {
226     /*
227      * For local blinding, unblind is set to NULL, and BN_BLINDING_invert_ex
228      * will use the unblinding factor stored in BN_BLINDING. If BN_BLINDING
229      * is shared between threads, unblind must be non-null:
230      * BN_BLINDING_invert_ex will then use the local unblinding factor, and
231      * will only read the modulus from BN_BLINDING. In both cases it's safe
232      * to access the blinding without a lock.
233      */
234     return BN_BLINDING_invert_ex(f, unblind, b, ctx);
235 }
236
237 /* signing */
238 static int rsa_ossl_private_encrypt(int flen, const unsigned char *from,
239                                    unsigned char *to, RSA *rsa, int padding)
240 {
241     BIGNUM *f, *ret, *res;
242     int i, j, k, num = 0, r = -1;
243     unsigned char *buf = NULL;
244     BN_CTX *ctx = NULL;
245     int local_blinding = 0;
246     /*
247      * Used only if the blinding structure is shared. A non-NULL unblind
248      * instructs rsa_blinding_convert() and rsa_blinding_invert() to store
249      * the unblinding factor outside the blinding structure.
250      */
251     BIGNUM *unblind = NULL;
252     BN_BLINDING *blinding = NULL;
253
254     if ((ctx = BN_CTX_new()) == NULL)
255         goto err;
256     BN_CTX_start(ctx);
257     f = BN_CTX_get(ctx);
258     ret = BN_CTX_get(ctx);
259     num = BN_num_bytes(rsa->n);
260     buf = OPENSSL_malloc(num);
261     if (ret == NULL || buf == NULL) {
262         RSAerr(RSA_F_RSA_OSSL_PRIVATE_ENCRYPT, ERR_R_MALLOC_FAILURE);
263         goto err;
264     }
265
266     switch (padding) {
267     case RSA_PKCS1_PADDING:
268         i = RSA_padding_add_PKCS1_type_1(buf, num, from, flen);
269         break;
270     case RSA_X931_PADDING:
271         i = RSA_padding_add_X931(buf, num, from, flen);
272         break;
273     case RSA_NO_PADDING:
274         i = RSA_padding_add_none(buf, num, from, flen);
275         break;
276     case RSA_SSLV23_PADDING:
277     default:
278         RSAerr(RSA_F_RSA_OSSL_PRIVATE_ENCRYPT, RSA_R_UNKNOWN_PADDING_TYPE);
279         goto err;
280     }
281     if (i <= 0)
282         goto err;
283
284     if (BN_bin2bn(buf, num, f) == NULL)
285         goto err;
286
287     if (BN_ucmp(f, rsa->n) >= 0) {
288         /* usually the padding functions would catch this */
289         RSAerr(RSA_F_RSA_OSSL_PRIVATE_ENCRYPT,
290                RSA_R_DATA_TOO_LARGE_FOR_MODULUS);
291         goto err;
292     }
293
294     if (!(rsa->flags & RSA_FLAG_NO_BLINDING)) {
295         blinding = rsa_get_blinding(rsa, &local_blinding, ctx);
296         if (blinding == NULL) {
297             RSAerr(RSA_F_RSA_OSSL_PRIVATE_ENCRYPT, ERR_R_INTERNAL_ERROR);
298             goto err;
299         }
300     }
301
302     if (blinding != NULL) {
303         if (!local_blinding && ((unblind = BN_CTX_get(ctx)) == NULL)) {
304             RSAerr(RSA_F_RSA_OSSL_PRIVATE_ENCRYPT, ERR_R_MALLOC_FAILURE);
305             goto err;
306         }
307         if (!rsa_blinding_convert(blinding, f, unblind, ctx))
308             goto err;
309     }
310
311     if ((rsa->flags & RSA_FLAG_EXT_PKEY) ||
312         (rsa->version == RSA_ASN1_VERSION_MULTI) ||
313         ((rsa->p != NULL) &&
314          (rsa->q != NULL) &&
315          (rsa->dmp1 != NULL) && (rsa->dmq1 != NULL) && (rsa->iqmp != NULL))) {
316         if (!rsa->meth->rsa_mod_exp(ret, f, rsa, ctx))
317             goto err;
318     } else {
319         BIGNUM *d = BN_new();
320         if (d == NULL) {
321             RSAerr(RSA_F_RSA_OSSL_PRIVATE_ENCRYPT, ERR_R_MALLOC_FAILURE);
322             goto err;
323         }
324         BN_with_flags(d, rsa->d, BN_FLG_CONSTTIME);
325
326         if (rsa->flags & RSA_FLAG_CACHE_PUBLIC)
327             if (!BN_MONT_CTX_set_locked
328                 (&rsa->_method_mod_n, rsa->lock, rsa->n, ctx)) {
329                 BN_free(d);
330                 goto err;
331             }
332
333         if (!rsa->meth->bn_mod_exp(ret, f, d, rsa->n, ctx,
334                                    rsa->_method_mod_n)) {
335             BN_free(d);
336             goto err;
337         }
338         /* We MUST free d before any further use of rsa->d */
339         BN_free(d);
340     }
341
342     if (blinding)
343         if (!rsa_blinding_invert(blinding, ret, unblind, ctx))
344             goto err;
345
346     if (padding == RSA_X931_PADDING) {
347         BN_sub(f, rsa->n, ret);
348         if (BN_cmp(ret, f) > 0)
349             res = f;
350         else
351             res = ret;
352     } else {
353         res = ret;
354     }
355
356     /*
357      * put in leading 0 bytes if the number is less than the length of the
358      * modulus
359      */
360     j = BN_num_bytes(res);
361     i = BN_bn2bin(res, &(to[num - j]));
362     for (k = 0; k < (num - i); k++)
363         to[k] = 0;
364
365     r = num;
366  err:
367     if (ctx != NULL)
368         BN_CTX_end(ctx);
369     BN_CTX_free(ctx);
370     OPENSSL_clear_free(buf, num);
371     return r;
372 }
373
374 static int rsa_ossl_private_decrypt(int flen, const unsigned char *from,
375                                    unsigned char *to, RSA *rsa, int padding)
376 {
377     BIGNUM *f, *ret;
378     int j, num = 0, r = -1;
379     unsigned char *p;
380     unsigned char *buf = NULL;
381     BN_CTX *ctx = NULL;
382     int local_blinding = 0;
383     /*
384      * Used only if the blinding structure is shared. A non-NULL unblind
385      * instructs rsa_blinding_convert() and rsa_blinding_invert() to store
386      * the unblinding factor outside the blinding structure.
387      */
388     BIGNUM *unblind = NULL;
389     BN_BLINDING *blinding = NULL;
390
391     if ((ctx = BN_CTX_new()) == NULL)
392         goto err;
393     BN_CTX_start(ctx);
394     f = BN_CTX_get(ctx);
395     ret = BN_CTX_get(ctx);
396     num = BN_num_bytes(rsa->n);
397     buf = OPENSSL_malloc(num);
398     if (ret == NULL || buf == NULL) {
399         RSAerr(RSA_F_RSA_OSSL_PRIVATE_DECRYPT, ERR_R_MALLOC_FAILURE);
400         goto err;
401     }
402
403     /*
404      * This check was for equality but PGP does evil things and chops off the
405      * top '0' bytes
406      */
407     if (flen > num) {
408         RSAerr(RSA_F_RSA_OSSL_PRIVATE_DECRYPT,
409                RSA_R_DATA_GREATER_THAN_MOD_LEN);
410         goto err;
411     }
412
413     /* make data into a big number */
414     if (BN_bin2bn(from, (int)flen, f) == NULL)
415         goto err;
416
417     if (BN_ucmp(f, rsa->n) >= 0) {
418         RSAerr(RSA_F_RSA_OSSL_PRIVATE_DECRYPT,
419                RSA_R_DATA_TOO_LARGE_FOR_MODULUS);
420         goto err;
421     }
422
423     if (!(rsa->flags & RSA_FLAG_NO_BLINDING)) {
424         blinding = rsa_get_blinding(rsa, &local_blinding, ctx);
425         if (blinding == NULL) {
426             RSAerr(RSA_F_RSA_OSSL_PRIVATE_DECRYPT, ERR_R_INTERNAL_ERROR);
427             goto err;
428         }
429     }
430
431     if (blinding != NULL) {
432         if (!local_blinding && ((unblind = BN_CTX_get(ctx)) == NULL)) {
433             RSAerr(RSA_F_RSA_OSSL_PRIVATE_DECRYPT, ERR_R_MALLOC_FAILURE);
434             goto err;
435         }
436         if (!rsa_blinding_convert(blinding, f, unblind, ctx))
437             goto err;
438     }
439
440     /* do the decrypt */
441     if ((rsa->flags & RSA_FLAG_EXT_PKEY) ||
442         (rsa->version == RSA_ASN1_VERSION_MULTI) ||
443         ((rsa->p != NULL) &&
444          (rsa->q != NULL) &&
445          (rsa->dmp1 != NULL) && (rsa->dmq1 != NULL) && (rsa->iqmp != NULL))) {
446         if (!rsa->meth->rsa_mod_exp(ret, f, rsa, ctx))
447             goto err;
448     } else {
449         BIGNUM *d = BN_new();
450         if (d == NULL) {
451             RSAerr(RSA_F_RSA_OSSL_PRIVATE_DECRYPT, ERR_R_MALLOC_FAILURE);
452             goto err;
453         }
454         BN_with_flags(d, rsa->d, BN_FLG_CONSTTIME);
455
456         if (rsa->flags & RSA_FLAG_CACHE_PUBLIC)
457             if (!BN_MONT_CTX_set_locked
458                 (&rsa->_method_mod_n, rsa->lock, rsa->n, ctx)) {
459                 BN_free(d);
460                 goto err;
461             }
462         if (!rsa->meth->bn_mod_exp(ret, f, d, rsa->n, ctx,
463                                    rsa->_method_mod_n)) {
464             BN_free(d);
465             goto err;
466         }
467         /* We MUST free d before any further use of rsa->d */
468         BN_free(d);
469     }
470
471     if (blinding)
472         if (!rsa_blinding_invert(blinding, ret, unblind, ctx))
473             goto err;
474
475     p = buf;
476     j = BN_bn2bin(ret, p);      /* j is only used with no-padding mode */
477
478     switch (padding) {
479     case RSA_PKCS1_PADDING:
480         r = RSA_padding_check_PKCS1_type_2(to, num, buf, j, num);
481         break;
482     case RSA_PKCS1_OAEP_PADDING:
483         r = RSA_padding_check_PKCS1_OAEP(to, num, buf, j, num, NULL, 0);
484         break;
485     case RSA_SSLV23_PADDING:
486         r = RSA_padding_check_SSLv23(to, num, buf, j, num);
487         break;
488     case RSA_NO_PADDING:
489         r = RSA_padding_check_none(to, num, buf, j, num);
490         break;
491     default:
492         RSAerr(RSA_F_RSA_OSSL_PRIVATE_DECRYPT, RSA_R_UNKNOWN_PADDING_TYPE);
493         goto err;
494     }
495     if (r < 0)
496         RSAerr(RSA_F_RSA_OSSL_PRIVATE_DECRYPT, RSA_R_PADDING_CHECK_FAILED);
497
498  err:
499     if (ctx != NULL)
500         BN_CTX_end(ctx);
501     BN_CTX_free(ctx);
502     OPENSSL_clear_free(buf, num);
503     return r;
504 }
505
506 /* signature verification */
507 static int rsa_ossl_public_decrypt(int flen, const unsigned char *from,
508                                   unsigned char *to, RSA *rsa, int padding)
509 {
510     BIGNUM *f, *ret;
511     int i, num = 0, r = -1;
512     unsigned char *p;
513     unsigned char *buf = NULL;
514     BN_CTX *ctx = NULL;
515
516     if (BN_num_bits(rsa->n) > OPENSSL_RSA_MAX_MODULUS_BITS) {
517         RSAerr(RSA_F_RSA_OSSL_PUBLIC_DECRYPT, RSA_R_MODULUS_TOO_LARGE);
518         return -1;
519     }
520
521     if (BN_ucmp(rsa->n, rsa->e) <= 0) {
522         RSAerr(RSA_F_RSA_OSSL_PUBLIC_DECRYPT, RSA_R_BAD_E_VALUE);
523         return -1;
524     }
525
526     /* for large moduli, enforce exponent limit */
527     if (BN_num_bits(rsa->n) > OPENSSL_RSA_SMALL_MODULUS_BITS) {
528         if (BN_num_bits(rsa->e) > OPENSSL_RSA_MAX_PUBEXP_BITS) {
529             RSAerr(RSA_F_RSA_OSSL_PUBLIC_DECRYPT, RSA_R_BAD_E_VALUE);
530             return -1;
531         }
532     }
533
534     if ((ctx = BN_CTX_new()) == NULL)
535         goto err;
536     BN_CTX_start(ctx);
537     f = BN_CTX_get(ctx);
538     ret = BN_CTX_get(ctx);
539     num = BN_num_bytes(rsa->n);
540     buf = OPENSSL_malloc(num);
541     if (ret == NULL || buf == NULL) {
542         RSAerr(RSA_F_RSA_OSSL_PUBLIC_DECRYPT, ERR_R_MALLOC_FAILURE);
543         goto err;
544     }
545
546     /*
547      * This check was for equality but PGP does evil things and chops off the
548      * top '0' bytes
549      */
550     if (flen > num) {
551         RSAerr(RSA_F_RSA_OSSL_PUBLIC_DECRYPT, RSA_R_DATA_GREATER_THAN_MOD_LEN);
552         goto err;
553     }
554
555     if (BN_bin2bn(from, flen, f) == NULL)
556         goto err;
557
558     if (BN_ucmp(f, rsa->n) >= 0) {
559         RSAerr(RSA_F_RSA_OSSL_PUBLIC_DECRYPT,
560                RSA_R_DATA_TOO_LARGE_FOR_MODULUS);
561         goto err;
562     }
563
564     if (rsa->flags & RSA_FLAG_CACHE_PUBLIC)
565         if (!BN_MONT_CTX_set_locked
566             (&rsa->_method_mod_n, rsa->lock, rsa->n, ctx))
567             goto err;
568
569     if (!rsa->meth->bn_mod_exp(ret, f, rsa->e, rsa->n, ctx,
570                                rsa->_method_mod_n))
571         goto err;
572
573     if ((padding == RSA_X931_PADDING) && ((bn_get_words(ret)[0] & 0xf) != 12))
574         if (!BN_sub(ret, rsa->n, ret))
575             goto err;
576
577     p = buf;
578     i = BN_bn2bin(ret, p);
579
580     switch (padding) {
581     case RSA_PKCS1_PADDING:
582         r = RSA_padding_check_PKCS1_type_1(to, num, buf, i, num);
583         break;
584     case RSA_X931_PADDING:
585         r = RSA_padding_check_X931(to, num, buf, i, num);
586         break;
587     case RSA_NO_PADDING:
588         r = RSA_padding_check_none(to, num, buf, i, num);
589         break;
590     default:
591         RSAerr(RSA_F_RSA_OSSL_PUBLIC_DECRYPT, RSA_R_UNKNOWN_PADDING_TYPE);
592         goto err;
593     }
594     if (r < 0)
595         RSAerr(RSA_F_RSA_OSSL_PUBLIC_DECRYPT, RSA_R_PADDING_CHECK_FAILED);
596
597  err:
598     if (ctx != NULL)
599         BN_CTX_end(ctx);
600     BN_CTX_free(ctx);
601     OPENSSL_clear_free(buf, num);
602     return r;
603 }
604
605 static int rsa_ossl_mod_exp(BIGNUM *r0, const BIGNUM *I, RSA *rsa, BN_CTX *ctx)
606 {
607     BIGNUM *r1, *m1, *vrfy, *r2, *m[RSA_MAX_PRIME_NUM];
608     int ret = 0, i, ex_primes = 0;
609     RSA_PRIME_INFO *pinfo;
610
611     BN_CTX_start(ctx);
612
613     r1 = BN_CTX_get(ctx);
614     r2 = BN_CTX_get(ctx);
615     m1 = BN_CTX_get(ctx);
616     vrfy = BN_CTX_get(ctx);
617     if (vrfy == NULL)
618         goto err;
619
620     if (rsa->version == RSA_ASN1_VERSION_MULTI
621         && (ex_primes = sk_RSA_PRIME_INFO_num(rsa->prime_infos)) <= 0)
622         goto err;
623
624     {
625         BIGNUM *p = BN_new(), *q = BN_new();
626
627         /*
628          * Make sure BN_mod_inverse in Montgomery initialization uses the
629          * BN_FLG_CONSTTIME flag
630          */
631         if (p == NULL || q == NULL) {
632             BN_free(p);
633             BN_free(q);
634             goto err;
635         }
636         BN_with_flags(p, rsa->p, BN_FLG_CONSTTIME);
637         BN_with_flags(q, rsa->q, BN_FLG_CONSTTIME);
638
639         if (rsa->flags & RSA_FLAG_CACHE_PRIVATE) {
640             if (!BN_MONT_CTX_set_locked
641                 (&rsa->_method_mod_p, rsa->lock, p, ctx)
642                 || !BN_MONT_CTX_set_locked(&rsa->_method_mod_q,
643                                            rsa->lock, q, ctx)) {
644                 BN_free(p);
645                 BN_free(q);
646                 goto err;
647             }
648             if (ex_primes > 0) {
649                 /* cache BN_MONT_CTX for other primes */
650                 BIGNUM *r = BN_new();
651
652                 if (r == NULL) {
653                     BN_free(p);
654                     BN_free(q);
655                     goto err;
656                 }
657
658                 for (i = 0; i < ex_primes; i++) {
659                     pinfo = sk_RSA_PRIME_INFO_value(rsa->prime_infos, i);
660                     BN_with_flags(r, pinfo->r, BN_FLG_CONSTTIME);
661                     if (!BN_MONT_CTX_set_locked(&pinfo->m, rsa->lock, r, ctx)) {
662                         BN_free(p);
663                         BN_free(q);
664                         BN_free(r);
665                         goto err;
666                     }
667                 }
668                 BN_free(r);
669             }
670         }
671         /*
672          * We MUST free p and q before any further use of rsa->p and rsa->q
673          */
674         BN_free(p);
675         BN_free(q);
676     }
677
678     if (rsa->flags & RSA_FLAG_CACHE_PUBLIC)
679         if (!BN_MONT_CTX_set_locked
680             (&rsa->_method_mod_n, rsa->lock, rsa->n, ctx))
681             goto err;
682
683     /* compute I mod q */
684     {
685         BIGNUM *c = BN_new();
686         if (c == NULL)
687             goto err;
688         BN_with_flags(c, I, BN_FLG_CONSTTIME);
689
690         if (!BN_mod(r1, c, rsa->q, ctx)) {
691             BN_free(c);
692             goto err;
693         }
694
695         {
696             BIGNUM *dmq1 = BN_new();
697             if (dmq1 == NULL) {
698                 BN_free(c);
699                 goto err;
700             }
701             BN_with_flags(dmq1, rsa->dmq1, BN_FLG_CONSTTIME);
702
703             /* compute r1^dmq1 mod q */
704             if (!rsa->meth->bn_mod_exp(m1, r1, dmq1, rsa->q, ctx,
705                 rsa->_method_mod_q)) {
706                 BN_free(c);
707                 BN_free(dmq1);
708                 goto err;
709             }
710             /* We MUST free dmq1 before any further use of rsa->dmq1 */
711             BN_free(dmq1);
712         }
713
714         /* compute I mod p */
715         if (!BN_mod(r1, c, rsa->p, ctx)) {
716             BN_free(c);
717             goto err;
718         }
719         /* We MUST free c before any further use of I */
720         BN_free(c);
721     }
722
723     {
724         BIGNUM *dmp1 = BN_new();
725         if (dmp1 == NULL)
726             goto err;
727         BN_with_flags(dmp1, rsa->dmp1, BN_FLG_CONSTTIME);
728
729         /* compute r1^dmp1 mod p */
730         if (!rsa->meth->bn_mod_exp(r0, r1, dmp1, rsa->p, ctx,
731                                    rsa->_method_mod_p)) {
732             BN_free(dmp1);
733             goto err;
734         }
735         /* We MUST free dmp1 before any further use of rsa->dmp1 */
736         BN_free(dmp1);
737     }
738
739     /*
740      * calculate m_i in multi-prime case
741      *
742      * TODO:
743      * 1. squash the following two loops and calculate |m_i| there.
744      * 2. remove cc and reuse |c|.
745      * 3. remove |dmq1| and |dmp1| in previous block and use |di|.
746      *
747      * If these things are done, the code will be more readable.
748      */
749     if (ex_primes > 0) {
750         BIGNUM *di = BN_new(), *cc = BN_new();
751
752         if (cc == NULL || di == NULL) {
753             BN_free(cc);
754             BN_free(di);
755             goto err;
756         }
757
758         for (i = 0; i < ex_primes; i++) {
759             /* prepare m_i */
760             if ((m[i] = BN_CTX_get(ctx)) == NULL) {
761                 BN_free(cc);
762                 BN_free(di);
763                 goto err;
764             }
765
766             pinfo = sk_RSA_PRIME_INFO_value(rsa->prime_infos, i);
767
768             /* prepare c and d_i */
769             BN_with_flags(cc, I, BN_FLG_CONSTTIME);
770             BN_with_flags(di, pinfo->d, BN_FLG_CONSTTIME);
771
772             if (!BN_mod(r1, cc, pinfo->r, ctx)) {
773                 BN_free(cc);
774                 BN_free(di);
775                 goto err;
776             }
777             /* compute r1 ^ d_i mod r_i */
778             if (!rsa->meth->bn_mod_exp(m[i], r1, di, pinfo->r, ctx, pinfo->m)) {
779                 BN_free(cc);
780                 BN_free(di);
781                 goto err;
782             }
783         }
784
785         BN_free(cc);
786         BN_free(di);
787     }
788
789     if (!BN_sub(r0, r0, m1))
790         goto err;
791     /*
792      * This will help stop the size of r0 increasing, which does affect the
793      * multiply if it optimised for a power of 2 size
794      */
795     if (BN_is_negative(r0))
796         if (!BN_add(r0, r0, rsa->p))
797             goto err;
798
799     if (!BN_mul(r1, r0, rsa->iqmp, ctx))
800         goto err;
801
802     {
803         BIGNUM *pr1 = BN_new();
804         if (pr1 == NULL)
805             goto err;
806         BN_with_flags(pr1, r1, BN_FLG_CONSTTIME);
807
808         if (!BN_mod(r0, pr1, rsa->p, ctx)) {
809             BN_free(pr1);
810             goto err;
811         }
812         /* We MUST free pr1 before any further use of r1 */
813         BN_free(pr1);
814     }
815
816     /*
817      * If p < q it is occasionally possible for the correction of adding 'p'
818      * if r0 is negative above to leave the result still negative. This can
819      * break the private key operations: the following second correction
820      * should *always* correct this rare occurrence. This will *never* happen
821      * with OpenSSL generated keys because they ensure p > q [steve]
822      */
823     if (BN_is_negative(r0))
824         if (!BN_add(r0, r0, rsa->p))
825             goto err;
826     if (!BN_mul(r1, r0, rsa->q, ctx))
827         goto err;
828     if (!BN_add(r0, r1, m1))
829         goto err;
830
831     /* add m_i to m in multi-prime case */
832     if (ex_primes > 0) {
833         BIGNUM *pr2 = BN_new();
834
835         if (pr2 == NULL)
836             goto err;
837
838         for (i = 0; i < ex_primes; i++) {
839             pinfo = sk_RSA_PRIME_INFO_value(rsa->prime_infos, i);
840             if (!BN_sub(r1, m[i], r0)) {
841                 BN_free(pr2);
842                 goto err;
843             }
844
845             if (!BN_mul(r2, r1, pinfo->t, ctx)) {
846                 BN_free(pr2);
847                 goto err;
848             }
849
850             BN_with_flags(pr2, r2, BN_FLG_CONSTTIME);
851
852             if (!BN_mod(r1, pr2, pinfo->r, ctx)) {
853                 BN_free(pr2);
854                 goto err;
855             }
856
857             if (BN_is_negative(r1))
858                 if (!BN_add(r1, r1, pinfo->r)) {
859                     BN_free(pr2);
860                     goto err;
861                 }
862             if (!BN_mul(r1, r1, pinfo->pp, ctx)) {
863                 BN_free(pr2);
864                 goto err;
865             }
866             if (!BN_add(r0, r0, r1)) {
867                 BN_free(pr2);
868                 goto err;
869             }
870         }
871         BN_free(pr2);
872     }
873
874     if (rsa->e && rsa->n) {
875         if (!rsa->meth->bn_mod_exp(vrfy, r0, rsa->e, rsa->n, ctx,
876                                    rsa->_method_mod_n))
877             goto err;
878         /*
879          * If 'I' was greater than (or equal to) rsa->n, the operation will
880          * be equivalent to using 'I mod n'. However, the result of the
881          * verify will *always* be less than 'n' so we don't check for
882          * absolute equality, just congruency.
883          */
884         if (!BN_sub(vrfy, vrfy, I))
885             goto err;
886         if (!BN_mod(vrfy, vrfy, rsa->n, ctx))
887             goto err;
888         if (BN_is_negative(vrfy))
889             if (!BN_add(vrfy, vrfy, rsa->n))
890                 goto err;
891         if (!BN_is_zero(vrfy)) {
892             /*
893              * 'I' and 'vrfy' aren't congruent mod n. Don't leak
894              * miscalculated CRT output, just do a raw (slower) mod_exp and
895              * return that instead.
896              */
897
898             BIGNUM *d = BN_new();
899             if (d == NULL)
900                 goto err;
901             BN_with_flags(d, rsa->d, BN_FLG_CONSTTIME);
902
903             if (!rsa->meth->bn_mod_exp(r0, I, d, rsa->n, ctx,
904                                        rsa->_method_mod_n)) {
905                 BN_free(d);
906                 goto err;
907             }
908             /* We MUST free d before any further use of rsa->d */
909             BN_free(d);
910         }
911     }
912     ret = 1;
913  err:
914     BN_CTX_end(ctx);
915     return ret;
916 }
917
918 static int rsa_ossl_init(RSA *rsa)
919 {
920     rsa->flags |= RSA_FLAG_CACHE_PUBLIC | RSA_FLAG_CACHE_PRIVATE;
921     return 1;
922 }
923
924 static int rsa_ossl_finish(RSA *rsa)
925 {
926     int i;
927     RSA_PRIME_INFO *pinfo;
928
929     BN_MONT_CTX_free(rsa->_method_mod_n);
930     BN_MONT_CTX_free(rsa->_method_mod_p);
931     BN_MONT_CTX_free(rsa->_method_mod_q);
932     for (i = 0; i < sk_RSA_PRIME_INFO_num(rsa->prime_infos); i++) {
933         pinfo = sk_RSA_PRIME_INFO_value(rsa->prime_infos, i);
934         BN_MONT_CTX_free(pinfo->m);
935     }
936     return 1;
937 }