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