Debian Codegraph @

lib/hcrypto/rsa-gmp.c

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