rsa_ossl.c@ 94113

最後變更在這個檔案從94113是 94082,由 vboxsync 提交於 3 年前
libs/openssl-3.0.1: started applying and adjusting our OpenSSL changes to 3.0.1. bugref:10128
檔案大小: 29.4 KB

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

注意: 瀏覽 TracBrowser 來幫助您使用儲存庫瀏覽器

source: vbox/trunk/src/libs/openssl-3.0.1/crypto/rsa/rsa_ossl.c@ 94113

以其他格式下載: