Debian Codegraph @

lib/hcrypto/rsa-ltm.c

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