Coverage Report

Created: 2025-06-13 06:58

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