2 * Copyright (c) 2006 - 2007 Kungliga Tekniska Högskolan
3 * (Royal Institute of Technology, Stockholm, Sweden).
6 * Redistribution and use in source and binary forms, with or without
7 * modification, are permitted provided that the following conditions
10 * 1. Redistributions of source code must retain the above copyright
11 * notice, this list of conditions and the following disclaimer.
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.
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.
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
38 #include <krb5-types.h>
45 #include "imath/imath.h"
46 #include "imath/iprime.h"
49 BN2mpz(mpz_t *s, const BIGNUM *bn)
56 len = BN_num_bytes(bn);
59 mp_int_read_unsigned(s, p, len);
70 size = mp_int_unsigned_len(s);
72 if (p == NULL && size != 0)
74 mp_int_to_unsigned(s, p, size);
76 bn = BN_bin2bn(p, size, NULL);
81 static int random_num(mp_int, size_t);
84 setup_blind(mp_int n, mp_int b, mp_int bi)
88 random_num(b, mp_int_count_bits(n));
90 mp_int_invmod(b, n, bi);
94 blind(mp_int in, mp_int b, mp_int e, mp_int n)
98 /* in' = (in * b^e) mod n */
99 mp_int_exptmod(b, e, n, &t1);
100 mp_int_mul(&t1, in, in);
101 mp_int_mod(in, n, in);
106 unblind(mp_int out, mp_int bi, mp_int n)
108 /* out' = (out * 1/b) mod n */
109 mp_int_mul(out, bi, out);
110 mp_int_mod(out, n, out);
114 rsa_private_calculate(mp_int in, mp_int p, mp_int q,
115 mp_int dmp1, mp_int dmq1, mp_int iqmp,
119 mp_int_init(&vp); mp_int_init(&vq); mp_int_init(&u);
121 /* vq = c ^ (d mod (q - 1)) mod q */
122 /* vp = c ^ (d mod (p - 1)) mod p */
123 mp_int_mod(in, p, &u);
124 mp_int_exptmod(&u, dmp1, p, &vp);
125 mp_int_mod(in, q, &u);
126 mp_int_exptmod(&u, dmq1, q, &vq);
128 /* C2 = 1/q mod p (iqmp) */
129 /* u = (vp - vq)C2 mod p. */
130 mp_int_sub(&vp, &vq, &u);
131 if (mp_int_compare_zero(&u) < 0)
132 mp_int_add(&u, p, &u);
133 mp_int_mul(&u, iqmp, &u);
134 mp_int_mod(&u, p, &u);
136 /* c ^ d mod n = vq + u q */
137 mp_int_mul(&u, q, &u);
138 mp_int_add(&u, &vq, out);
152 imath_rsa_public_encrypt(int flen, const unsigned char* from,
153 unsigned char* to, RSA* rsa, int padding)
155 unsigned char *p, *p0;
158 mpz_t enc, dec, n, e;
160 if (padding != RSA_PKCS1_PADDING)
163 size = RSA_size(rsa);
165 if (size < RSA_PKCS1_PADDING_SIZE || size - RSA_PKCS1_PADDING_SIZE < flen)
171 p = p0 = malloc(size - 1);
178 padlen = size - flen - 3;
181 if (RAND_bytes(p, padlen) != 1) {
194 memcpy(p, from, flen);
196 assert((p - p0) == size - 1);
200 mp_int_read_unsigned(&dec, p0, size - 1);
203 res = mp_int_exptmod(&dec, &e, &n, &enc);
210 ssize = mp_int_unsigned_len(&enc);
211 assert(size >= ssize);
212 mp_int_to_unsigned(&enc, to, ssize);
221 imath_rsa_public_decrypt(int flen, const unsigned char* from,
222 unsigned char* to, RSA* rsa, int padding)
229 if (padding != RSA_PKCS1_PADDING)
232 if (flen > RSA_size(rsa))
239 /* Check that the exponent is larger then 3 */
240 if (mp_int_compare_value(&e, 3) <= 0) {
249 mp_int_read_unsigned(&s, rk_UNCONST(from), flen);
251 if (mp_int_compare(&s, &n) >= 0) {
257 res = mp_int_exptmod(&s, &e, &n, &us);
268 size = mp_int_unsigned_len(&us);
269 assert(size <= RSA_size(rsa));
270 mp_int_to_unsigned(&us, p, size);
274 /* head zero was skipped by mp_int_to_unsigned */
280 while (size && *p == 0xff) {
283 if (size == 0 || *p != 0)
287 memmove(to, p, size);
293 imath_rsa_private_encrypt(int flen, const unsigned char* from,
294 unsigned char* to, RSA* rsa, int padding)
296 unsigned char *p, *p0;
299 mpz_t in, out, n, e, b, bi;
300 int blinding = (rsa->flags & RSA_FLAG_NO_BLINDING) == 0;
302 if (padding != RSA_PKCS1_PADDING)
305 size = RSA_size(rsa);
307 if (size < RSA_PKCS1_PADDING_SIZE || size - RSA_PKCS1_PADDING_SIZE < flen)
310 p0 = p = malloc(size);
313 memset(p, 0xff, size - flen - 3);
314 p += size - flen - 3;
316 memcpy(p, from, flen);
318 assert((p - p0) == size);
325 mp_int_read_unsigned(&in, p0, size);
328 if(mp_int_compare_zero(&in) < 0 ||
329 mp_int_compare(&in, &n) >= 0) {
335 setup_blind(&n, &b, &bi);
336 blind(&in, &b, &e, &n);
339 if (rsa->p && rsa->q && rsa->dmp1 && rsa->dmq1 && rsa->iqmp) {
340 mpz_t p, q, dmp1, dmq1, iqmp;
344 BN2mpz(&dmp1, rsa->dmp1);
345 BN2mpz(&dmq1, rsa->dmq1);
346 BN2mpz(&iqmp, rsa->iqmp);
348 res = rsa_private_calculate(&in, &p, &q, &dmp1, &dmq1, &iqmp, &out);
359 res = mp_int_exptmod(&in, &d, &n, &out);
368 unblind(&out, &bi, &n);
375 ssize = mp_int_unsigned_len(&out);
376 assert(size >= ssize);
377 mp_int_to_unsigned(&out, to, size);
391 imath_rsa_private_decrypt(int flen, const unsigned char* from,
392 unsigned char* to, RSA* rsa, int padding)
397 mpz_t in, out, n, e, b, bi;
398 int blinding = (rsa->flags & RSA_FLAG_NO_BLINDING) == 0;
400 if (padding != RSA_PKCS1_PADDING)
403 size = RSA_size(rsa);
413 res = mp_int_read_unsigned(&in, rk_UNCONST(from), flen);
419 if(mp_int_compare_zero(&in) < 0 ||
420 mp_int_compare(&in, &n) >= 0) {
426 setup_blind(&n, &b, &bi);
427 blind(&in, &b, &e, &n);
430 if (rsa->p && rsa->q && rsa->dmp1 && rsa->dmq1 && rsa->iqmp) {
431 mpz_t p, q, dmp1, dmq1, iqmp;
435 BN2mpz(&dmp1, rsa->dmp1);
436 BN2mpz(&dmq1, rsa->dmq1);
437 BN2mpz(&iqmp, rsa->iqmp);
439 res = rsa_private_calculate(&in, &p, &q, &dmp1, &dmq1, &iqmp, &out);
449 if(mp_int_compare_zero(&in) < 0 ||
450 mp_int_compare(&in, &n) >= 0)
454 res = mp_int_exptmod(&in, &d, &n, &out);
463 unblind(&out, &bi, &n);
471 ssize = mp_int_unsigned_len(&out);
472 assert(size >= ssize);
473 mp_int_to_unsigned(&out, ptr, ssize);
477 /* head zero was skipped by mp_int_to_unsigned */
481 while (size && *ptr != 0) {
488 memmove(to, ptr, size);
500 random_num(mp_int num, size_t len)
509 if (RAND_bytes(p, len) != 1) {
513 res = mp_int_read_unsigned(num, p, len);
520 #define CHECK(f, v) if ((f) != (v)) { goto out; }
523 imath_rsa_generate_key(RSA *rsa, int bits, BIGNUM *e, BN_GENCB *cb)
525 mpz_t el, p, q, n, d, dmp1, dmq1, iqmp, t1, t2, t3;
547 /* generate p and q so that p != q and bits(pq) ~ bits */
550 BN_GENCB_call(cb, 2, counter++);
551 CHECK(random_num(&p, bits / 2 + 1), 0);
552 CHECK(mp_int_find_prime(&p), MP_TRUE);
554 CHECK(mp_int_sub_value(&p, 1, &t1), MP_OK);
555 CHECK(mp_int_gcd(&t1, &el, &t2), MP_OK);
556 } while(mp_int_compare_value(&t2, 1) != 0);
558 BN_GENCB_call(cb, 3, 0);
562 BN_GENCB_call(cb, 2, counter++);
563 CHECK(random_num(&q, bits / 2 + 1), 0);
564 CHECK(mp_int_find_prime(&q), MP_TRUE);
566 if (mp_int_compare(&p, &q) == 0) /* don't let p and q be the same */
569 CHECK(mp_int_sub_value(&q, 1, &t1), MP_OK);
570 CHECK(mp_int_gcd(&t1, &el, &t2), MP_OK);
571 } while(mp_int_compare_value(&t2, 1) != 0);
574 if (mp_int_compare(&p, &q) < 0)
577 BN_GENCB_call(cb, 3, 1);
579 /* calculate n, n = p * q */
580 CHECK(mp_int_mul(&p, &q, &n), MP_OK);
582 /* calculate d, d = 1/e mod (p - 1)(q - 1) */
583 CHECK(mp_int_sub_value(&p, 1, &t1), MP_OK);
584 CHECK(mp_int_sub_value(&q, 1, &t2), MP_OK);
585 CHECK(mp_int_mul(&t1, &t2, &t3), MP_OK);
586 CHECK(mp_int_invmod(&el, &t3, &d), MP_OK);
588 /* calculate dmp1 dmp1 = d mod (p-1) */
589 CHECK(mp_int_mod(&d, &t1, &dmp1), MP_OK);
590 /* calculate dmq1 dmq1 = d mod (q-1) */
591 CHECK(mp_int_mod(&d, &t2, &dmq1), MP_OK);
592 /* calculate iqmp iqmp = 1/q mod p */
593 CHECK(mp_int_invmod(&q, &p, &iqmp), MP_OK);
595 /* fill in RSA key */
597 rsa->e = mpz2BN(&el);
602 rsa->dmp1 = mpz2BN(&dmp1);
603 rsa->dmq1 = mpz2BN(&dmq1);
604 rsa->iqmp = mpz2BN(&iqmp);
624 imath_rsa_init(RSA *rsa)
630 imath_rsa_finish(RSA *rsa)
635 const RSA_METHOD hc_rsa_imath_method = {
637 imath_rsa_public_encrypt,
638 imath_rsa_public_decrypt,
639 imath_rsa_private_encrypt,
640 imath_rsa_private_decrypt,
649 imath_rsa_generate_key
653 RSA_imath_method(void)
655 return &hc_rsa_imath_method;