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