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