rsa_ossl.c@ 83531

Last change on this file since 83531 was 83531, checked in by vboxsync, 5 years ago
setting svn:sync-process=export for openssl-1.1.1f, all files except tests
File size: 29.3 KB

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

Note: See TracBrowser for help on using the repository browser.

source: vbox/trunk/src/libs/openssl-1.1.1f/crypto/rsa/rsa_ossl.c@ 83531

Download in other formats: