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