source: heimdal/vendor/current/lib/hcrypto/rsa-ltm.c

Last change on this file was 1, checked in by Paul Smedley, 10 years ago

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