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