1 /* $NetBSD: rsa-tfm.c,v 1.2 2017/01/28 21:31:47 christos Exp $ */
2
3 /*
4 * Copyright (c) 2006 - 2007, 2010 Kungliga Tekniska Högskolan
5 * (Royal Institute of Technology, Stockholm, Sweden).
6 * All rights reserved.
7 *
8 * Redistribution and use in source and binary forms, with or without
9 * modification, are permitted provided that the following conditions
10 * are met:
11 *
12 * 1. Redistributions of source code must retain the above copyright
13 * notice, this list of conditions and the following disclaimer.
14 *
15 * 2. Redistributions in binary form must reproduce the above copyright
16 * notice, this list of conditions and the following disclaimer in the
17 * documentation and/or other materials provided with the distribution.
18 *
19 * 3. Neither the name of the Institute nor the names of its contributors
20 * may be used to endorse or promote products derived from this software
21 * without specific prior written permission.
22 *
23 * THIS SOFTWARE IS PROVIDED BY THE INSTITUTE AND CONTRIBUTORS ``AS IS'' AND
24 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
25 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
26 * ARE DISCLAIMED. IN NO EVENT SHALL THE INSTITUTE OR CONTRIBUTORS BE LIABLE
27 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
28 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
29 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
30 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
31 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
32 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
33 * SUCH DAMAGE.
34 */
35
36 #include <config.h>
37 #include <krb5/roken.h>
38 #include <krb5/krb5-types.h>
39 #include <assert.h>
40
41 #include <rsa.h>
42
43 #ifdef USE_HCRYPTO_TFM
44
45 #include "tfm.h"
46
47 static void
BN2mpz(fp_int * s,const BIGNUM * bn)48 BN2mpz(fp_int *s, const BIGNUM *bn)
49 {
50 size_t len;
51 void *p;
52
53 fp_init(s);
54
55 len = BN_num_bytes(bn);
56 p = malloc(len);
57 BN_bn2bin(bn, p);
58 fp_read_unsigned_bin(s, p, len);
59 free(p);
60 }
61
62 static int
tfm_rsa_private_calculate(fp_int * in,fp_int * p,fp_int * q,fp_int * dmp1,fp_int * dmq1,fp_int * iqmp,fp_int * out)63 tfm_rsa_private_calculate(fp_int * in, fp_int * p, fp_int * q,
64 fp_int * dmp1, fp_int * dmq1, fp_int * iqmp,
65 fp_int * out)
66 {
67 fp_int vp, vq, u;
68
69 fp_init_multi(&vp, &vq, &u, NULL);
70
71 /* vq = c ^ (d mod (q - 1)) mod q */
72 /* vp = c ^ (d mod (p - 1)) mod p */
73 fp_mod(in, p, &u);
74 fp_exptmod(&u, dmp1, p, &vp);
75 fp_mod(in, q, &u);
76 fp_exptmod(&u, dmq1, q, &vq);
77
78 /* C2 = 1/q mod p (iqmp) */
79 /* u = (vp - vq)C2 mod p. */
80 fp_sub(&vp, &vq, &u);
81 if (fp_isneg(&u))
82 fp_add(&u, p, &u);
83 fp_mul(&u, iqmp, &u);
84 fp_mod(&u, p, &u);
85
86 /* c ^ d mod n = vq + u q */
87 fp_mul(&u, q, &u);
88 fp_add(&u, &vq, out);
89
90 fp_zero_multi(&vp, &vq, &u, NULL);
91
92 return 0;
93 }
94
95 /*
96 *
97 */
98
99 static int
tfm_rsa_public_encrypt(int flen,const unsigned char * from,unsigned char * to,RSA * rsa,int padding)100 tfm_rsa_public_encrypt(int flen, const unsigned char* from,
101 unsigned char* to, RSA* rsa, int padding)
102 {
103 unsigned char *p, *p0;
104 int res;
105 size_t size, padlen;
106 fp_int enc, dec, n, e;
107
108 if (padding != RSA_PKCS1_PADDING)
109 return -1;
110
111 size = RSA_size(rsa);
112
113 if (size < RSA_PKCS1_PADDING_SIZE || size - RSA_PKCS1_PADDING_SIZE < flen)
114 return -2;
115
116 BN2mpz(&n, rsa->n);
117 BN2mpz(&e, rsa->e);
118
119 p = p0 = malloc(size - 1);
120 if (p0 == NULL) {
121 fp_zero_multi(&e, &n, NULL);
122 return -3;
123 }
124
125 padlen = size - flen - 3;
126
127 *p++ = 2;
128 if (RAND_bytes(p, padlen) != 1) {
129 fp_zero_multi(&e, &n, NULL);
130 free(p0);
131 return -4;
132 }
133 while(padlen) {
134 if (*p == 0)
135 *p = 1;
136 padlen--;
137 p++;
138 }
139 *p++ = 0;
140 memcpy(p, from, flen);
141 p += flen;
142 assert((p - p0) == size - 1);
143
144 fp_init_multi(&enc, &dec, NULL);
145 fp_read_unsigned_bin(&dec, p0, size - 1);
146 free(p0);
147
148 res = fp_exptmod(&dec, &e, &n, &enc);
149
150 fp_zero_multi(&dec, &e, &n, NULL);
151
152 if (res != 0)
153 return -4;
154
155 {
156 size_t ssize;
157 ssize = fp_unsigned_bin_size(&enc);
158 assert(size >= ssize);
159 fp_to_unsigned_bin(&enc, to);
160 size = ssize;
161 }
162 fp_zero(&enc);
163
164 return size;
165 }
166
167 static int
tfm_rsa_public_decrypt(int flen,const unsigned char * from,unsigned char * to,RSA * rsa,int padding)168 tfm_rsa_public_decrypt(int flen, const unsigned char* from,
169 unsigned char* to, RSA* rsa, int padding)
170 {
171 unsigned char *p;
172 int res;
173 size_t size;
174 fp_int s, us, n, e;
175
176 if (padding != RSA_PKCS1_PADDING)
177 return -1;
178
179 if (flen > RSA_size(rsa))
180 return -2;
181
182 BN2mpz(&n, rsa->n);
183 BN2mpz(&e, rsa->e);
184
185 #if 0
186 /* Check that the exponent is larger then 3 */
187 if (mp_int_compare_value(&e, 3) <= 0) {
188 fp_zero_multi(&e, &n, NULL);
189 return -3;
190 }
191 #endif
192
193 fp_init_multi(&s, &us, NULL);
194 fp_read_unsigned_bin(&s, rk_UNCONST(from), flen);
195
196 if (fp_cmp(&s, &n) >= 0) {
197 fp_zero_multi(&e, &n, NULL);
198 return -4;
199 }
200
201 res = fp_exptmod(&s, &e, &n, &us);
202
203 fp_zero_multi(&s, &e, &n, NULL);
204
205 if (res != 0)
206 return -5;
207 p = to;
208
209
210 size = fp_unsigned_bin_size(&us);
211 assert(size <= RSA_size(rsa));
212 fp_to_unsigned_bin(&us, p);
213
214 fp_zero(&us);
215
216 /* head zero was skipped by fp_to_unsigned_bin */
217 if (*p == 0)
218 return -6;
219 if (*p != 1)
220 return -7;
221 size--; p++;
222 while (size && *p == 0xff) {
223 size--; p++;
224 }
225 if (size == 0 || *p != 0)
226 return -8;
227 size--; p++;
228
229 memmove(to, p, size);
230
231 return size;
232 }
233
234 static int
tfm_rsa_private_encrypt(int flen,const unsigned char * from,unsigned char * to,RSA * rsa,int padding)235 tfm_rsa_private_encrypt(int flen, const unsigned char* from,
236 unsigned char* to, RSA* rsa, int padding)
237 {
238 unsigned char *p, *p0;
239 int res;
240 int size;
241 fp_int in, out, n, e;
242
243 if (padding != RSA_PKCS1_PADDING)
244 return -1;
245
246 size = RSA_size(rsa);
247
248 if (size < RSA_PKCS1_PADDING_SIZE || size - RSA_PKCS1_PADDING_SIZE < flen)
249 return -2;
250
251 p0 = p = malloc(size);
252 *p++ = 0;
253 *p++ = 1;
254 memset(p, 0xff, size - flen - 3);
255 p += size - flen - 3;
256 *p++ = 0;
257 memcpy(p, from, flen);
258 p += flen;
259 assert((p - p0) == size);
260
261 BN2mpz(&n, rsa->n);
262 BN2mpz(&e, rsa->e);
263
264 fp_init_multi(&in, &out, NULL);
265 fp_read_unsigned_bin(&in, p0, size);
266 free(p0);
267
268 if(fp_isneg(&in) || fp_cmp(&in, &n) >= 0) {
269 size = -3;
270 goto out;
271 }
272
273 if (rsa->p && rsa->q && rsa->dmp1 && rsa->dmq1 && rsa->iqmp) {
274 fp_int p, q, dmp1, dmq1, iqmp;
275
276 BN2mpz(&p, rsa->p);
277 BN2mpz(&q, rsa->q);
278 BN2mpz(&dmp1, rsa->dmp1);
279 BN2mpz(&dmq1, rsa->dmq1);
280 BN2mpz(&iqmp, rsa->iqmp);
281
282 res = tfm_rsa_private_calculate(&in, &p, &q, &dmp1, &dmq1, &iqmp, &out);
283
284 fp_zero_multi(&p, &q, &dmp1, &dmq1, &iqmp, NULL);
285
286 if (res != 0) {
287 size = -4;
288 goto out;
289 }
290 } else {
291 fp_int d;
292
293 BN2mpz(&d, rsa->d);
294 res = fp_exptmod(&in, &d, &n, &out);
295 fp_zero(&d);
296 if (res != 0) {
297 size = -5;
298 goto out;
299 }
300 }
301
302 if (size > 0) {
303 size_t ssize;
304 ssize = fp_unsigned_bin_size(&out);
305 assert(size >= ssize);
306 fp_to_unsigned_bin(&out, to);
307 size = ssize;
308 }
309
310 out:
311 fp_zero_multi(&e, &n, &in, &out, NULL);
312
313 return size;
314 }
315
316 static int
tfm_rsa_private_decrypt(int flen,const unsigned char * from,unsigned char * to,RSA * rsa,int padding)317 tfm_rsa_private_decrypt(int flen, const unsigned char* from,
318 unsigned char* to, RSA* rsa, int padding)
319 {
320 unsigned char *ptr;
321 int res;
322 int size;
323 fp_int in, out, n, e;
324
325 if (padding != RSA_PKCS1_PADDING)
326 return -1;
327
328 size = RSA_size(rsa);
329 if (flen > size)
330 return -2;
331
332 fp_init_multi(&in, &out, NULL);
333
334 BN2mpz(&n, rsa->n);
335 BN2mpz(&e, rsa->e);
336
337 fp_read_unsigned_bin(&in, rk_UNCONST(from), flen);
338
339 if(fp_isneg(&in) || fp_cmp(&in, &n) >= 0) {
340 size = -2;
341 goto out;
342 }
343
344 if (rsa->p && rsa->q && rsa->dmp1 && rsa->dmq1 && rsa->iqmp) {
345 fp_int p, q, dmp1, dmq1, iqmp;
346
347 BN2mpz(&p, rsa->p);
348 BN2mpz(&q, rsa->q);
349 BN2mpz(&dmp1, rsa->dmp1);
350 BN2mpz(&dmq1, rsa->dmq1);
351 BN2mpz(&iqmp, rsa->iqmp);
352
353 res = tfm_rsa_private_calculate(&in, &p, &q, &dmp1, &dmq1, &iqmp, &out);
354
355 fp_zero_multi(&p, &q, &dmp1, &dmq1, &iqmp, NULL);
356
357 if (res != 0) {
358 size = -3;
359 goto out;
360 }
361
362 } else {
363 fp_int d;
364
365 if(fp_isneg(&in) || fp_cmp(&in, &n) >= 0)
366 return -4;
367
368 BN2mpz(&d, rsa->d);
369 res = fp_exptmod(&in, &d, &n, &out);
370 fp_zero(&d);
371 if (res != 0) {
372 size = -5;
373 goto out;
374 }
375 }
376
377 ptr = to;
378 {
379 size_t ssize;
380 ssize = fp_unsigned_bin_size(&out);
381 assert(size >= ssize);
382 fp_to_unsigned_bin(&out, ptr);
383 size = ssize;
384 }
385
386 /* head zero was skipped by mp_int_to_unsigned */
387 if (*ptr != 2) {
388 size = -6;
389 goto out;
390 }
391 size--; ptr++;
392 while (size && *ptr != 0) {
393 size--; ptr++;
394 }
395 if (size == 0)
396 return -7;
397 size--; ptr++;
398
399 memmove(to, ptr, size);
400
401 out:
402 fp_zero_multi(&e, &n, &in, &out, NULL);
403
404 return size;
405 }
406
407 static BIGNUM *
mpz2BN(fp_int * s)408 mpz2BN(fp_int *s)
409 {
410 size_t size;
411 BIGNUM *bn;
412 void *p;
413
414 size = fp_unsigned_bin_size(s);
415 p = malloc(size);
416 if (p == NULL && size != 0)
417 return NULL;
418
419 fp_to_unsigned_bin(s, p);
420
421 bn = BN_bin2bn(p, size, NULL);
422 free(p);
423 return bn;
424 }
425
426 static int
random_num(fp_int * num,size_t len)427 random_num(fp_int *num, size_t len)
428 {
429 unsigned char *p;
430
431 len = (len + 7) / 8;
432 p = malloc(len);
433 if (p == NULL)
434 return 1;
435 if (RAND_bytes(p, len) != 1) {
436 free(p);
437 return 1;
438 }
439 fp_read_unsigned_bin(num, p, len);
440 free(p);
441 return 0;
442 }
443
444 #define CHECK(f, v) if ((f) != (v)) { goto out; }
445
446 static int
tfm_rsa_generate_key(RSA * rsa,int bits,BIGNUM * e,BN_GENCB * cb)447 tfm_rsa_generate_key(RSA *rsa, int bits, BIGNUM *e, BN_GENCB *cb)
448 {
449 fp_int el, p, q, n, d, dmp1, dmq1, iqmp, t1, t2, t3;
450 int counter, ret, bitsp;
451
452 if (bits < 789)
453 return -1;
454
455 bitsp = (bits + 1) / 2;
456
457 ret = -1;
458
459 fp_init_multi(&el, &p, &q, &n, &n, &d, &dmp1, &dmq1, &iqmp, &t1, &t2, &t3, NULL);
460
461 BN2mpz(&el, e);
462
463 /* generate p and q so that p != q and bits(pq) ~ bits */
464 counter = 0;
465 do {
466 BN_GENCB_call(cb, 2, counter++);
467 CHECK(random_num(&p, bitsp), 0);
468 CHECK(fp_find_prime(&p), FP_YES);
469
470 fp_sub_d(&p, 1, &t1);
471 fp_gcd(&t1, &el, &t2);
472 } while(fp_cmp_d(&t2, 1) != 0);
473
474 BN_GENCB_call(cb, 3, 0);
475
476 counter = 0;
477 do {
478 BN_GENCB_call(cb, 2, counter++);
479 CHECK(random_num(&q, bits - bitsp), 0);
480 CHECK(fp_find_prime(&q), FP_YES);
481
482 if (fp_cmp(&p, &q) == 0) /* don't let p and q be the same */
483 continue;
484
485 fp_sub_d(&q, 1, &t1);
486 fp_gcd(&t1, &el, &t2);
487 } while(fp_cmp_d(&t2, 1) != 0);
488
489 /* make p > q */
490 if (fp_cmp(&p, &q) < 0) {
491 fp_int c;
492 fp_copy(&p, &c);
493 fp_copy(&q, &p);
494 fp_copy(&c, &q);
495 }
496
497 BN_GENCB_call(cb, 3, 1);
498
499 /* calculate n, n = p * q */
500 fp_mul(&p, &q, &n);
501
502 /* calculate d, d = 1/e mod (p - 1)(q - 1) */
503 fp_sub_d(&p, 1, &t1);
504 fp_sub_d(&q, 1, &t2);
505 fp_mul(&t1, &t2, &t3);
506 fp_invmod(&el, &t3, &d);
507
508 /* calculate dmp1 dmp1 = d mod (p-1) */
509 fp_mod(&d, &t1, &dmp1);
510 /* calculate dmq1 dmq1 = d mod (q-1) */
511 fp_mod(&d, &t2, &dmq1);
512 /* calculate iqmp iqmp = 1/q mod p */
513 fp_invmod(&q, &p, &iqmp);
514
515 /* fill in RSA key */
516
517 rsa->e = mpz2BN(&el);
518 rsa->p = mpz2BN(&p);
519 rsa->q = mpz2BN(&q);
520 rsa->n = mpz2BN(&n);
521 rsa->d = mpz2BN(&d);
522 rsa->dmp1 = mpz2BN(&dmp1);
523 rsa->dmq1 = mpz2BN(&dmq1);
524 rsa->iqmp = mpz2BN(&iqmp);
525
526 ret = 1;
527
528 out:
529 fp_zero_multi(&el, &p, &q, &n, &d, &dmp1,
530 &dmq1, &iqmp, &t1, &t2, &t3, NULL);
531
532 return ret;
533 }
534
535 static int
tfm_rsa_init(RSA * rsa)536 tfm_rsa_init(RSA *rsa)
537 {
538 return 1;
539 }
540
541 static int
tfm_rsa_finish(RSA * rsa)542 tfm_rsa_finish(RSA *rsa)
543 {
544 return 1;
545 }
546
547 const RSA_METHOD hc_rsa_tfm_method = {
548 "hcrypto tfm RSA",
549 tfm_rsa_public_encrypt,
550 tfm_rsa_public_decrypt,
551 tfm_rsa_private_encrypt,
552 tfm_rsa_private_decrypt,
553 NULL,
554 NULL,
555 tfm_rsa_init,
556 tfm_rsa_finish,
557 0,
558 NULL,
559 NULL,
560 NULL,
561 tfm_rsa_generate_key
562 };
563
564 #endif
565
566 const RSA_METHOD *
RSA_tfm_method(void)567 RSA_tfm_method(void)
568 {
569 #ifdef USE_HCRYPTO_TFM
570 return &hc_rsa_tfm_method;
571 #else
572 return NULL;
573 #endif
574 }
575
576