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