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
43 #include <krb5-types.h>
55 BN2mpz(mpz_t s
, const BIGNUM
*bn
)
60 len
= BN_num_bytes(bn
);
63 mpz_import(s
, len
, 1, 1, 1, 0, p
);
75 mpz_export(NULL
, &size
, 1, 1, 1, 0, s
);
77 if (p
== NULL
&& size
!= 0)
79 mpz_export(p
, &size
, 1, 1, 1, 0, s
);
81 bn
= BN_bin2bn(p
, size
, NULL
);
87 rsa_private_calculate(mpz_t in
, mpz_t p
, mpz_t q
,
88 mpz_t dmp1
, mpz_t dmq1
, mpz_t iqmp
,
92 mpz_init(vp
); mpz_init(vq
); mpz_init(u
);
94 /* vq = c ^ (d mod (q - 1)) mod q */
95 /* vp = c ^ (d mod (p - 1)) mod p */
97 mpz_powm(vp
, vp
, dmp1
, p
);
99 mpz_powm(vq
, vq
, dmq1
, q
);
101 /* C2 = 1/q mod p (iqmp) */
102 /* u = (vp - vq)C2 mod p. */
105 if (mp_int_compare_zero(&u
) < 0)
106 mp_int_add(&u
, p
, &u
);
111 /* c ^ d mod n = vq + u q */
127 gmp_rsa_public_encrypt(int flen
, const unsigned char* from
,
128 unsigned char* to
, RSA
* rsa
, int padding
)
130 unsigned char *p
, *p0
;
133 mpz_t enc
, dec
, n
, e
;
135 if (padding
!= RSA_PKCS1_PADDING
)
138 size
= RSA_size(rsa
);
140 if (size
< RSA_PKCS1_PADDING_SIZE
|| size
- RSA_PKCS1_PADDING_SIZE
< flen
)
146 p
= p0
= malloc(size
- 1);
153 padlen
= size
- flen
- 3;
157 if (RAND_bytes(p
, padlen
) != 1) {
170 memcpy(p
, from
, flen
);
172 assert((p
- p0
) == size
- 1);
176 mpz_import(dec
, size
- 1, 1, 1, 1, 0, p0
);
179 mpz_powm(enc
, dec
, e
, n
);
186 mpz_export(to
, &ssize
, 1, 1, 1, 0, enc
);
187 assert(size
>= ssize
);
196 gmp_rsa_public_decrypt(int flen
, const unsigned char* from
,
197 unsigned char* to
, RSA
* rsa
, int padding
)
203 if (padding
!= RSA_PKCS1_PADDING
)
206 if (flen
> RSA_size(rsa
))
213 /* Check that the exponent is larger then 3 */
214 if (mp_int_compare_value(&e
, 3) <= 0) {
223 mpz_import(s
, flen
, 1, 1, 1, 0, rk_UNCONST(from
));
225 if (mpz_cmp(s
, n
) >= 0) {
231 mpz_powm(us
, s
, e
, n
);
239 mpz_export(p
, &size
, 1, 1, 1, 0, us
);
240 assert(size
<= RSA_size(rsa
));
244 /* head zero was skipped by mp_int_to_unsigned */
250 while (size
&& *p
== 0xff) {
253 if (size
== 0 || *p
!= 0)
257 memmove(to
, p
, size
);
263 gmp_rsa_private_encrypt(int flen
, const unsigned char* from
,
264 unsigned char* to
, RSA
* rsa
, int padding
)
266 unsigned char *p
, *p0
;
268 mpz_t in
, out
, n
, e
, b
, bi
;
270 if (padding
!= RSA_PKCS1_PADDING
)
273 size
= RSA_size(rsa
);
275 if (size
< RSA_PKCS1_PADDING_SIZE
|| size
- RSA_PKCS1_PADDING_SIZE
< flen
)
278 p0
= p
= malloc(size
);
281 memset(p
, 0xff, size
- flen
- 3);
282 p
+= size
- flen
- 3;
284 memcpy(p
, from
, flen
);
286 assert((p
- p0
) == size
);
293 mpz_import(in
, size
, 1, 1, 1, 0, p0
);
297 if(mp_int_compare_zero(&in
) < 0 ||
298 mp_int_compare(&in
, &n
) >= 0) {
304 if (rsa
->p
&& rsa
->q
&& rsa
->dmp1
&& rsa
->dmq1
&& rsa
->iqmp
) {
305 mpz_t p
, q
, dmp1
, dmq1
, iqmp
;
309 BN2mpz(dmp1
, rsa
->dmp1
);
310 BN2mpz(dmq1
, rsa
->dmq1
);
311 BN2mpz(iqmp
, rsa
->iqmp
);
313 rsa_private_calculate(in
, p
, q
, dmp1
, dmq1
, iqmp
, out
);
324 mpz_powm(out
, in
, d
, n
);
334 mpz_export(to
, &ssize
, 1, 1, 1, 0, out
);
335 assert(size
>= ssize
);
349 gmp_rsa_private_decrypt(int flen
, const unsigned char* from
,
350 unsigned char* to
, RSA
* rsa
, int padding
)
354 mpz_t in
, out
, n
, e
, b
, bi
;
356 if (padding
!= RSA_PKCS1_PADDING
)
359 size
= RSA_size(rsa
);
369 res
= mp_int_read_unsigned(&in
, rk_UNCONST(from
), flen
);
375 if(mp_int_compare_zero(&in
) < 0 ||
376 mp_int_compare(&in
, &n
) >= 0) {
381 if (rsa
->p
&& rsa
->q
&& rsa
->dmp1
&& rsa
->dmq1
&& rsa
->iqmp
) {
382 mpz_t p
, q
, dmp1
, dmq1
, iqmp
;
386 BN2mpz(dmp1
, rsa
->dmp1
);
387 BN2mpz(dmq1
, rsa
->dmq1
);
388 BN2mpz(iqmp
, rsa
->iqmp
);
390 res
= rsa_private_calculate(in
, p
, q
, dmp1
, dmq1
, iqmp
, out
);
401 if(mp_int_compare_zero(&in
) < 0 ||
402 mp_int_compare(&in
, &n
) >= 0)
407 mpz_powm(out
, in
, d
, n
);
418 mpz_export(ptr
, &ssize
, 1, 1, 1, 0, out
);
419 assert(size
>= ssize
);
423 /* head zero was skipped by mp_int_to_unsigned */
427 while (size
&& *ptr
!= 0) {
434 memmove(to
, ptr
, size
);
446 gmp_rsa_generate_key(RSA
*rsa
, int bits
, BIGNUM
*e
, BN_GENCB
*cb
)
448 mpz_t el
, p
, q
, n
, d
, dmp1
, dmq1
, iqmp
, t1
, t2
, t3
;
470 /* generate p and q so that p != q and bits(pq) ~ bits */
474 BN_GENCB_call(cb
, 2, counter
++);
475 CHECK(random_num(&p
, bits
/ 2 + 1), 0);
476 CHECK(mp_int_find_prime(&p
), MP_TRUE
);
478 CHECK(mp_int_sub_value(&p
, 1, &t1
), MP_OK
);
479 CHECK(mp_int_gcd(&t1
, &el
, &t2
), MP_OK
);
480 } while(mp_int_compare_value(&t2
, 1) != 0);
482 BN_GENCB_call(cb
, 3, 0);
486 BN_GENCB_call(cb
, 2, counter
++);
487 CHECK(random_num(&q
, bits
/ 2 + 1), 0);
488 CHECK(mp_int_find_prime(&q
), MP_TRUE
);
490 if (mp_int_compare(&p
, &q
) == 0) /* don't let p and q be the same */
493 CHECK(mp_int_sub_value(&q
, 1, &t1
), MP_OK
);
494 CHECK(mp_int_gcd(&t1
, &el
, &t2
), MP_OK
);
495 } while(mp_int_compare_value(&t2
, 1) != 0);
498 if (mp_int_compare(&p
, &q
) < 0)
501 BN_GENCB_call(cb
, 3, 1);
503 /* calculate n, n = p * q */
504 CHECK(mp_int_mul(&p
, &q
, &n
), MP_OK
);
506 /* calculate d, d = 1/e mod (p - 1)(q - 1) */
507 CHECK(mp_int_sub_value(&p
, 1, &t1
), MP_OK
);
508 CHECK(mp_int_sub_value(&q
, 1, &t2
), MP_OK
);
509 CHECK(mp_int_mul(&t1
, &t2
, &t3
), MP_OK
);
510 CHECK(mp_int_invmod(&el
, &t3
, &d
), MP_OK
);
512 /* calculate dmp1 dmp1 = d mod (p-1) */
513 CHECK(mp_int_mod(&d
, &t1
, &dmp1
), MP_OK
);
514 /* calculate dmq1 dmq1 = d mod (q-1) */
515 CHECK(mp_int_mod(&d
, &t2
, &dmq1
), MP_OK
);
516 /* calculate iqmp iqmp = 1/q mod p */
517 CHECK(mp_int_invmod(&q
, &p
, &iqmp
), MP_OK
);
519 /* fill in RSA key */
521 rsa
->e
= mpz2BN(&el
);
526 rsa
->dmp1
= mpz2BN(&dmp1
);
527 rsa
->dmq1
= mpz2BN(&dmq1
);
528 rsa
->iqmp
= mpz2BN(&iqmp
);
549 gmp_rsa_init(RSA
*rsa
)
555 gmp_rsa_finish(RSA
*rsa
)
560 const RSA_METHOD hc_rsa_gmp_method
= {
562 gmp_rsa_public_encrypt
,
563 gmp_rsa_public_decrypt
,
564 gmp_rsa_private_encrypt
,
565 gmp_rsa_private_decrypt
,
577 #endif /* HAVE_GMP */
580 * RSA implementation using Gnu Multipresistion Library.
587 return &hc_rsa_gmp_method
;