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
;