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