1 /* $NetBSD: rsa-tfm.c,v 1.1.1.2 2014/04/24 12:45:30 pettai 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
38 #include <stdio.h>
39 #include <stdlib.h>
40 #include <krb5/krb5-types.h>
41 #include <assert.h>
42
43 #include <rsa.h>
44
45 #include <krb5/roken.h>
46
47 #ifdef USE_HCRYPTO_TFM
48
49 #include "tfm.h"
50
51 static void
BN2mpz(fp_int * s,const BIGNUM * bn)52 BN2mpz(fp_int *s, const BIGNUM *bn)
53 {
54 size_t len;
55 void *p;
56
57 fp_init(s);
58
59 len = BN_num_bytes(bn);
60 p = malloc(len);
61 BN_bn2bin(bn, p);
62 fp_read_unsigned_bin(s, p, len);
63 free(p);
64 }
65
66 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)67 tfm_rsa_private_calculate(fp_int * in, fp_int * p, fp_int * q,
68 fp_int * dmp1, fp_int * dmq1, fp_int * iqmp,
69 fp_int * out)
70 {
71 fp_int vp, vq, u;
72
73 fp_init_multi(&vp, &vq, &u, NULL);
74
75 /* vq = c ^ (d mod (q - 1)) mod q */
76 /* vp = c ^ (d mod (p - 1)) mod p */
77 fp_mod(in, p, &u);
78 fp_exptmod(&u, dmp1, p, &vp);
79 fp_mod(in, q, &u);
80 fp_exptmod(&u, dmq1, q, &vq);
81
82 /* C2 = 1/q mod p (iqmp) */
83 /* u = (vp - vq)C2 mod p. */
84 fp_sub(&vp, &vq, &u);
85 if (fp_isneg(&u))
86 fp_add(&u, p, &u);
87 fp_mul(&u, iqmp, &u);
88 fp_mod(&u, p, &u);
89
90 /* c ^ d mod n = vq + u q */
91 fp_mul(&u, q, &u);
92 fp_add(&u, &vq, out);
93
94 fp_zero_multi(&vp, &vq, &u, NULL);
95
96 return 0;
97 }
98
99 /*
100 *
101 */
102
103 static int
tfm_rsa_public_encrypt(int flen,const unsigned char * from,unsigned char * to,RSA * rsa,int padding)104 tfm_rsa_public_encrypt(int flen, const unsigned char* from,
105 unsigned char* to, RSA* rsa, int padding)
106 {
107 unsigned char *p, *p0;
108 int res;
109 size_t size, padlen;
110 fp_int enc, dec, n, e;
111
112 if (padding != RSA_PKCS1_PADDING)
113 return -1;
114
115 size = RSA_size(rsa);
116
117 if (size < RSA_PKCS1_PADDING_SIZE || size - RSA_PKCS1_PADDING_SIZE < flen)
118 return -2;
119
120 BN2mpz(&n, rsa->n);
121 BN2mpz(&e, rsa->e);
122
123 p = p0 = malloc(size - 1);
124 if (p0 == NULL) {
125 fp_zero_multi(&e, &n, NULL);
126 return -3;
127 }
128
129 padlen = size - flen - 3;
130
131 *p++ = 2;
132 if (RAND_bytes(p, padlen) != 1) {
133 fp_zero_multi(&e, &n, NULL);
134 free(p0);
135 return -4;
136 }
137 while(padlen) {
138 if (*p == 0)
139 *p = 1;
140 padlen--;
141 p++;
142 }
143 *p++ = 0;
144 memcpy(p, from, flen);
145 p += flen;
146 assert((p - p0) == size - 1);
147
148 fp_init_multi(&enc, &dec, NULL);
149 fp_read_unsigned_bin(&dec, p0, size - 1);
150 free(p0);
151
152 res = fp_exptmod(&dec, &e, &n, &enc);
153
154 fp_zero_multi(&dec, &e, &n, NULL);
155
156 if (res != 0)
157 return -4;
158
159 {
160 size_t ssize;
161 ssize = fp_unsigned_bin_size(&enc);
162 assert(size >= ssize);
163 fp_to_unsigned_bin(&enc, to);
164 size = ssize;
165 }
166 fp_zero(&enc);
167
168 return size;
169 }
170
171 static int
tfm_rsa_public_decrypt(int flen,const unsigned char * from,unsigned char * to,RSA * rsa,int padding)172 tfm_rsa_public_decrypt(int flen, const unsigned char* from,
173 unsigned char* to, RSA* rsa, int padding)
174 {
175 unsigned char *p;
176 int res;
177 size_t size;
178 fp_int s, us, n, e;
179
180 if (padding != RSA_PKCS1_PADDING)
181 return -1;
182
183 if (flen > RSA_size(rsa))
184 return -2;
185
186 BN2mpz(&n, rsa->n);
187 BN2mpz(&e, rsa->e);
188
189 #if 0
190 /* Check that the exponent is larger then 3 */
191 if (mp_int_compare_value(&e, 3) <= 0) {
192 fp_zero_multi(&e, &n, NULL);
193 return -3;
194 }
195 #endif
196
197 fp_init_multi(&s, &us, NULL);
198 fp_read_unsigned_bin(&s, rk_UNCONST(from), flen);
199
200 if (fp_cmp(&s, &n) >= 0) {
201 fp_zero_multi(&e, &n, NULL);
202 return -4;
203 }
204
205 res = fp_exptmod(&s, &e, &n, &us);
206
207 fp_zero_multi(&s, &e, &n, NULL);
208
209 if (res != 0)
210 return -5;
211 p = to;
212
213
214 size = fp_unsigned_bin_size(&us);
215 assert(size <= RSA_size(rsa));
216 fp_to_unsigned_bin(&us, p);
217
218 fp_zero(&us);
219
220 /* head zero was skipped by fp_to_unsigned_bin */
221 if (*p == 0)
222 return -6;
223 if (*p != 1)
224 return -7;
225 size--; p++;
226 while (size && *p == 0xff) {
227 size--; p++;
228 }
229 if (size == 0 || *p != 0)
230 return -8;
231 size--; p++;
232
233 memmove(to, p, size);
234
235 return size;
236 }
237
238 static int
tfm_rsa_private_encrypt(int flen,const unsigned char * from,unsigned char * to,RSA * rsa,int padding)239 tfm_rsa_private_encrypt(int flen, const unsigned char* from,
240 unsigned char* to, RSA* rsa, int padding)
241 {
242 unsigned char *p, *p0;
243 int res;
244 int size;
245 fp_int in, out, n, e;
246
247 if (padding != RSA_PKCS1_PADDING)
248 return -1;
249
250 size = RSA_size(rsa);
251
252 if (size < RSA_PKCS1_PADDING_SIZE || size - RSA_PKCS1_PADDING_SIZE < flen)
253 return -2;
254
255 p0 = p = malloc(size);
256 *p++ = 0;
257 *p++ = 1;
258 memset(p, 0xff, size - flen - 3);
259 p += size - flen - 3;
260 *p++ = 0;
261 memcpy(p, from, flen);
262 p += flen;
263 assert((p - p0) == size);
264
265 BN2mpz(&n, rsa->n);
266 BN2mpz(&e, rsa->e);
267
268 fp_init_multi(&in, &out, NULL);
269 fp_read_unsigned_bin(&in, p0, size);
270 free(p0);
271
272 if(fp_isneg(&in) || fp_cmp(&in, &n) >= 0) {
273 size = -3;
274 goto out;
275 }
276
277 if (rsa->p && rsa->q && rsa->dmp1 && rsa->dmq1 && rsa->iqmp) {
278 fp_int p, q, dmp1, dmq1, iqmp;
279
280 BN2mpz(&p, rsa->p);
281 BN2mpz(&q, rsa->q);
282 BN2mpz(&dmp1, rsa->dmp1);
283 BN2mpz(&dmq1, rsa->dmq1);
284 BN2mpz(&iqmp, rsa->iqmp);
285
286 res = tfm_rsa_private_calculate(&in, &p, &q, &dmp1, &dmq1, &iqmp, &out);
287
288 fp_zero_multi(&p, &q, &dmp1, &dmq1, &iqmp, NULL);
289
290 if (res != 0) {
291 size = -4;
292 goto out;
293 }
294 } else {
295 fp_int d;
296
297 BN2mpz(&d, rsa->d);
298 res = fp_exptmod(&in, &d, &n, &out);
299 fp_zero(&d);
300 if (res != 0) {
301 size = -5;
302 goto out;
303 }
304 }
305
306 if (size > 0) {
307 size_t ssize;
308 ssize = fp_unsigned_bin_size(&out);
309 assert(size >= ssize);
310 fp_to_unsigned_bin(&out, to);
311 size = ssize;
312 }
313
314 out:
315 fp_zero_multi(&e, &n, &in, &out, NULL);
316
317 return size;
318 }
319
320 static int
tfm_rsa_private_decrypt(int flen,const unsigned char * from,unsigned char * to,RSA * rsa,int padding)321 tfm_rsa_private_decrypt(int flen, const unsigned char* from,
322 unsigned char* to, RSA* rsa, int padding)
323 {
324 unsigned char *ptr;
325 int res;
326 int size;
327 fp_int in, out, n, e;
328
329 if (padding != RSA_PKCS1_PADDING)
330 return -1;
331
332 size = RSA_size(rsa);
333 if (flen > size)
334 return -2;
335
336 fp_init_multi(&in, &out, NULL);
337
338 BN2mpz(&n, rsa->n);
339 BN2mpz(&e, rsa->e);
340
341 fp_read_unsigned_bin(&in, rk_UNCONST(from), flen);
342
343 if(fp_isneg(&in) || fp_cmp(&in, &n) >= 0) {
344 size = -2;
345 goto out;
346 }
347
348 if (rsa->p && rsa->q && rsa->dmp1 && rsa->dmq1 && rsa->iqmp) {
349 fp_int p, q, dmp1, dmq1, iqmp;
350
351 BN2mpz(&p, rsa->p);
352 BN2mpz(&q, rsa->q);
353 BN2mpz(&dmp1, rsa->dmp1);
354 BN2mpz(&dmq1, rsa->dmq1);
355 BN2mpz(&iqmp, rsa->iqmp);
356
357 res = tfm_rsa_private_calculate(&in, &p, &q, &dmp1, &dmq1, &iqmp, &out);
358
359 fp_zero_multi(&p, &q, &dmp1, &dmq1, &iqmp, NULL);
360
361 if (res != 0) {
362 size = -3;
363 goto out;
364 }
365
366 } else {
367 fp_int d;
368
369 if(fp_isneg(&in) || fp_cmp(&in, &n) >= 0)
370 return -4;
371
372 BN2mpz(&d, rsa->d);
373 res = fp_exptmod(&in, &d, &n, &out);
374 fp_zero(&d);
375 if (res != 0) {
376 size = -5;
377 goto out;
378 }
379 }
380
381 ptr = to;
382 {
383 size_t ssize;
384 ssize = fp_unsigned_bin_size(&out);
385 assert(size >= ssize);
386 fp_to_unsigned_bin(&out, ptr);
387 size = ssize;
388 }
389
390 /* head zero was skipped by mp_int_to_unsigned */
391 if (*ptr != 2) {
392 size = -6;
393 goto out;
394 }
395 size--; ptr++;
396 while (size && *ptr != 0) {
397 size--; ptr++;
398 }
399 if (size == 0)
400 return -7;
401 size--; ptr++;
402
403 memmove(to, ptr, size);
404
405 out:
406 fp_zero_multi(&e, &n, &in, &out, NULL);
407
408 return size;
409 }
410
411 static BIGNUM *
mpz2BN(fp_int * s)412 mpz2BN(fp_int *s)
413 {
414 size_t size;
415 BIGNUM *bn;
416 void *p;
417
418 size = fp_unsigned_bin_size(s);
419 p = malloc(size);
420 if (p == NULL && size != 0)
421 return NULL;
422
423 fp_to_unsigned_bin(s, p);
424
425 bn = BN_bin2bn(p, size, NULL);
426 free(p);
427 return bn;
428 }
429
430 static int
random_num(fp_int * num,size_t len)431 random_num(fp_int *num, size_t len)
432 {
433 unsigned char *p;
434
435 len = (len + 7) / 8;
436 p = malloc(len);
437 if (p == NULL)
438 return 1;
439 if (RAND_bytes(p, len) != 1) {
440 free(p);
441 return 1;
442 }
443 fp_read_unsigned_bin(num, p, len);
444 free(p);
445 return 0;
446 }
447
448 #define CHECK(f, v) if ((f) != (v)) { goto out; }
449
450 static int
tfm_rsa_generate_key(RSA * rsa,int bits,BIGNUM * e,BN_GENCB * cb)451 tfm_rsa_generate_key(RSA *rsa, int bits, BIGNUM *e, BN_GENCB *cb)
452 {
453 fp_int el, p, q, n, d, dmp1, dmq1, iqmp, t1, t2, t3;
454 int counter, ret, bitsp;
455
456 if (bits < 789)
457 return -1;
458
459 bitsp = (bits + 1) / 2;
460
461 ret = -1;
462
463 fp_init_multi(&el, &p, &q, &n, &n, &d, &dmp1, &dmq1, &iqmp, &t1, &t2, &t3, NULL);
464
465 BN2mpz(&el, e);
466
467 /* generate p and q so that p != q and bits(pq) ~ bits */
468 counter = 0;
469 do {
470 BN_GENCB_call(cb, 2, counter++);
471 CHECK(random_num(&p, bitsp), 0);
472 CHECK(fp_find_prime(&p), FP_YES);
473
474 fp_sub_d(&p, 1, &t1);
475 fp_gcd(&t1, &el, &t2);
476 } while(fp_cmp_d(&t2, 1) != 0);
477
478 BN_GENCB_call(cb, 3, 0);
479
480 counter = 0;
481 do {
482 BN_GENCB_call(cb, 2, counter++);
483 CHECK(random_num(&q, bits - bitsp), 0);
484 CHECK(fp_find_prime(&q), FP_YES);
485
486 if (fp_cmp(&p, &q) == 0) /* don't let p and q be the same */
487 continue;
488
489 fp_sub_d(&q, 1, &t1);
490 fp_gcd(&t1, &el, &t2);
491 } while(fp_cmp_d(&t2, 1) != 0);
492
493 /* make p > q */
494 if (fp_cmp(&p, &q) < 0) {
495 fp_int c;
496 fp_copy(&p, &c);
497 fp_copy(&q, &p);
498 fp_copy(&c, &q);
499 }
500
501 BN_GENCB_call(cb, 3, 1);
502
503 /* calculate n, n = p * q */
504 fp_mul(&p, &q, &n);
505
506 /* calculate d, d = 1/e mod (p - 1)(q - 1) */
507 fp_sub_d(&p, 1, &t1);
508 fp_sub_d(&q, 1, &t2);
509 fp_mul(&t1, &t2, &t3);
510 fp_invmod(&el, &t3, &d);
511
512 /* calculate dmp1 dmp1 = d mod (p-1) */
513 fp_mod(&d, &t1, &dmp1);
514 /* calculate dmq1 dmq1 = d mod (q-1) */
515 fp_mod(&d, &t2, &dmq1);
516 /* calculate iqmp iqmp = 1/q mod p */
517 fp_invmod(&q, &p, &iqmp);
518
519 /* fill in RSA key */
520
521 rsa->e = mpz2BN(&el);
522 rsa->p = mpz2BN(&p);
523 rsa->q = mpz2BN(&q);
524 rsa->n = mpz2BN(&n);
525 rsa->d = mpz2BN(&d);
526 rsa->dmp1 = mpz2BN(&dmp1);
527 rsa->dmq1 = mpz2BN(&dmq1);
528 rsa->iqmp = mpz2BN(&iqmp);
529
530 ret = 1;
531
532 out:
533 fp_zero_multi(&el, &p, &q, &n, &d, &dmp1,
534 &dmq1, &iqmp, &t1, &t2, &t3, NULL);
535
536 return ret;
537 }
538
539 static int
tfm_rsa_init(RSA * rsa)540 tfm_rsa_init(RSA *rsa)
541 {
542 return 1;
543 }
544
545 static int
tfm_rsa_finish(RSA * rsa)546 tfm_rsa_finish(RSA *rsa)
547 {
548 return 1;
549 }
550
551 const RSA_METHOD hc_rsa_tfm_method = {
552 "hcrypto tfm RSA",
553 tfm_rsa_public_encrypt,
554 tfm_rsa_public_decrypt,
555 tfm_rsa_private_encrypt,
556 tfm_rsa_private_decrypt,
557 NULL,
558 NULL,
559 tfm_rsa_init,
560 tfm_rsa_finish,
561 0,
562 NULL,
563 NULL,
564 NULL,
565 tfm_rsa_generate_key
566 };
567
568 #endif
569
570 const RSA_METHOD *
RSA_tfm_method(void)571 RSA_tfm_method(void)
572 {
573 #ifdef USE_HCRYPTO_TFM
574 return &hc_rsa_tfm_method;
575 #else
576 return NULL;
577 #endif
578 }
579
580