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