2 * Copyright (c) 2006 - 2007, 2010 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>
48 BN2mpz(fp_int
*s
, const BIGNUM
*bn
)
55 len
= BN_num_bytes(bn
);
58 fp_read_unsigned_bin(s
, p
, len
);
63 tfm_rsa_private_calculate(fp_int
* in
, fp_int
* p
, fp_int
* q
,
64 fp_int
* dmp1
, fp_int
* dmq1
, fp_int
* iqmp
,
69 fp_init_multi(&vp
, &vq
, &u
, NULL
);
71 /* vq = c ^ (d mod (q - 1)) mod q */
72 /* vp = c ^ (d mod (p - 1)) mod p */
74 fp_exptmod(&u
, dmp1
, p
, &vp
);
76 fp_exptmod(&u
, dmq1
, q
, &vq
);
78 /* C2 = 1/q mod p (iqmp) */
79 /* u = (vp - vq)C2 mod p. */
86 /* c ^ d mod n = vq + u q */
102 tfm_rsa_public_encrypt(int flen
, const unsigned char* from
,
103 unsigned char* to
, RSA
* rsa
, int padding
)
105 unsigned char *p
, *p0
;
108 fp_int enc
, dec
, n
, e
;
110 if (padding
!= RSA_PKCS1_PADDING
)
113 size
= RSA_size(rsa
);
115 if (size
< RSA_PKCS1_PADDING_SIZE
|| size
- RSA_PKCS1_PADDING_SIZE
< flen
)
121 p
= p0
= malloc(size
- 1);
128 padlen
= size
- flen
- 3;
131 if (RAND_bytes(p
, padlen
) != 1) {
144 memcpy(p
, from
, flen
);
146 assert((p
- p0
) == size
- 1);
148 fp_init_multi(&enc
, &dec
, NULL
);
149 fp_read_unsigned_bin(&dec
, p0
, size
- 1);
152 res
= fp_exptmod(&dec
, &e
, &n
, &enc
);
163 ssize
= fp_unsigned_bin_size(&enc
);
164 assert(size
>= ssize
);
165 fp_to_unsigned_bin(&enc
, to
);
174 tfm_rsa_public_decrypt(int flen
, const unsigned char* from
,
175 unsigned char* to
, RSA
* rsa
, int padding
)
182 if (padding
!= RSA_PKCS1_PADDING
)
185 if (flen
> RSA_size(rsa
))
192 /* Check that the exponent is larger then 3 */
193 if (mp_int_compare_value(&e
, 3) <= 0) {
200 fp_init_multi(&s
, &us
, NULL
);
201 fp_read_unsigned_bin(&s
, rk_UNCONST(from
), flen
);
203 if (fp_cmp(&s
, &n
) >= 0) {
209 res
= fp_exptmod(&s
, &e
, &n
, &us
);
220 size
= fp_unsigned_bin_size(&us
);
221 assert(size
<= RSA_size(rsa
));
222 fp_to_unsigned_bin(&us
, p
);
226 /* head zero was skipped by fp_to_unsigned_bin */
232 while (size
&& *p
== 0xff) {
235 if (size
== 0 || *p
!= 0)
239 memmove(to
, p
, size
);
245 tfm_rsa_private_encrypt(int flen
, const unsigned char* from
,
246 unsigned char* to
, RSA
* rsa
, int padding
)
248 unsigned char *p
, *p0
;
251 fp_int in
, out
, n
, e
;
253 if (padding
!= RSA_PKCS1_PADDING
)
256 size
= RSA_size(rsa
);
258 if (size
< RSA_PKCS1_PADDING_SIZE
|| size
- RSA_PKCS1_PADDING_SIZE
< flen
)
261 p0
= p
= malloc(size
);
264 memset(p
, 0xff, size
- flen
- 3);
265 p
+= size
- flen
- 3;
267 memcpy(p
, from
, flen
);
269 assert((p
- p0
) == size
);
274 fp_init_multi(&in
, &out
, NULL
);
275 fp_read_unsigned_bin(&in
, p0
, size
);
278 if(in
.sign
== FP_NEG
||
279 fp_cmp(&in
, &n
) >= 0) {
284 if (rsa
->p
&& rsa
->q
&& rsa
->dmp1
&& rsa
->dmq1
&& rsa
->iqmp
) {
285 fp_int p
, q
, dmp1
, dmq1
, iqmp
;
289 BN2mpz(&dmp1
, rsa
->dmp1
);
290 BN2mpz(&dmq1
, rsa
->dmq1
);
291 BN2mpz(&iqmp
, rsa
->iqmp
);
293 res
= tfm_rsa_private_calculate(&in
, &p
, &q
, &dmp1
, &dmq1
, &iqmp
, &out
);
309 res
= fp_exptmod(&in
, &d
, &n
, &out
);
319 ssize
= fp_unsigned_bin_size(&out
);
320 assert(size
>= ssize
);
321 fp_to_unsigned_bin(&out
, to
);
335 tfm_rsa_private_decrypt(int flen
, const unsigned char* from
,
336 unsigned char* to
, RSA
* rsa
, int padding
)
341 fp_int in
, out
, n
, e
;
343 if (padding
!= RSA_PKCS1_PADDING
)
346 size
= RSA_size(rsa
);
350 fp_init_multi(&in
, &out
, NULL
);
355 fp_read_unsigned_bin(&in
, rk_UNCONST(from
), flen
);
357 if(in
.sign
== FP_NEG
||
358 fp_cmp(&in
, &n
) >= 0) {
363 if (rsa
->p
&& rsa
->q
&& rsa
->dmp1
&& rsa
->dmq1
&& rsa
->iqmp
) {
364 fp_int p
, q
, dmp1
, dmq1
, iqmp
;
368 BN2mpz(&dmp1
, rsa
->dmp1
);
369 BN2mpz(&dmq1
, rsa
->dmq1
);
370 BN2mpz(&iqmp
, rsa
->iqmp
);
372 res
= tfm_rsa_private_calculate(&in
, &p
, &q
, &dmp1
, &dmq1
, &iqmp
, &out
);
388 if(in
.sign
== FP_NEG
||
389 fp_cmp(&in
, &n
) >= 0)
393 res
= fp_exptmod(&in
, &d
, &n
, &out
);
404 ssize
= fp_unsigned_bin_size(&out
);
405 assert(size
>= ssize
);
406 fp_to_unsigned_bin(&out
, ptr
);
410 /* head zero was skipped by mp_int_to_unsigned */
416 while (size
&& *ptr
!= 0) {
423 memmove(to
, ptr
, size
);
441 size
= fp_unsigned_bin_size(s
);
443 if (p
== NULL
&& size
!= 0)
446 fp_to_unsigned_bin(s
, p
);
448 bn
= BN_bin2bn(p
, size
, NULL
);
454 random_num(fp_int
*num
, size_t len
)
462 if (RAND_bytes(p
, len
) != 1) {
466 fp_read_unsigned_bin(num
, p
, len
);
471 #define CHECK(f, v) if ((f) != (v)) { goto out; }
474 tfm_rsa_generate_key(RSA
*rsa
, int bits
, BIGNUM
*e
, BN_GENCB
*cb
)
476 fp_int el
, p
, q
, n
, d
, dmp1
, dmq1
, iqmp
, t1
, t2
, t3
;
477 int counter
, ret
, bitsp
;
482 bitsp
= (bits
+ 1) / 2;
486 fp_init_multi(&el
, &p
, &q
, &n
, &n
, &d
, &dmp1
, &dmq1
, &iqmp
, &t1
, &t2
, &t3
, NULL
);
490 /* generate p and q so that p != q and bits(pq) ~ bits */
493 BN_GENCB_call(cb
, 2, counter
++);
494 CHECK(random_num(&p
, bitsp
), 0);
495 CHECK(fp_find_prime(&p
), FP_YES
);
497 fp_sub_d(&p
, 1, &t1
);
498 fp_gcd(&t1
, &el
, &t2
);
499 } while(fp_cmp_d(&t2
, 1) != 0);
501 BN_GENCB_call(cb
, 3, 0);
505 BN_GENCB_call(cb
, 2, counter
++);
506 CHECK(random_num(&q
, bits
- bitsp
), 0);
507 CHECK(fp_find_prime(&q
), FP_YES
);
509 if (fp_cmp(&p
, &q
) == 0) /* don't let p and q be the same */
512 fp_sub_d(&q
, 1, &t1
);
513 fp_gcd(&t1
, &el
, &t2
);
514 } while(fp_cmp_d(&t2
, 1) != 0);
517 if (fp_cmp(&p
, &q
) < 0) {
524 BN_GENCB_call(cb
, 3, 1);
526 /* calculate n, n = p * q */
529 /* calculate d, d = 1/e mod (p - 1)(q - 1) */
530 fp_sub_d(&p
, 1, &t1
);
531 fp_sub_d(&q
, 1, &t2
);
532 fp_mul(&t1
, &t2
, &t3
);
533 fp_invmod(&el
, &t3
, &d
);
535 /* calculate dmp1 dmp1 = d mod (p-1) */
536 fp_mod(&d
, &t1
, &dmp1
);
537 /* calculate dmq1 dmq1 = d mod (q-1) */
538 fp_mod(&d
, &t2
, &dmq1
);
539 /* calculate iqmp iqmp = 1/q mod p */
540 fp_invmod(&q
, &p
, &iqmp
);
542 /* fill in RSA key */
544 rsa
->e
= mpz2BN(&el
);
549 rsa
->dmp1
= mpz2BN(&dmp1
);
550 rsa
->dmq1
= mpz2BN(&dmq1
);
551 rsa
->iqmp
= mpz2BN(&iqmp
);
572 tfm_rsa_init(RSA
*rsa
)
578 tfm_rsa_finish(RSA
*rsa
)
583 const RSA_METHOD hc_rsa_tfm_method
= {
585 tfm_rsa_public_encrypt
,
586 tfm_rsa_public_decrypt
,
587 tfm_rsa_private_encrypt
,
588 tfm_rsa_private_decrypt
,
603 return &hc_rsa_tfm_method
;