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 random_num(mp_int
*num
, size_t len
)
56 if (RAND_bytes(p
, len
) != 1) {
60 mp_read_unsigned_bin(num
, p
, len
);
66 BN2mpz(mp_int
*s
, const BIGNUM
*bn
)
71 len
= BN_num_bytes(bn
);
74 mp_read_unsigned_bin(s
, p
, len
);
79 setup_blind(mp_int
*n
, mp_int
*b
, mp_int
*bi
)
81 random_num(b
, mp_count_bits(n
));
87 blind(mp_int
*in
, mp_int
*b
, mp_int
*e
, mp_int
*n
)
91 /* in' = (in * b^e) mod n */
92 mp_exptmod(b
, e
, n
, &t1
);
99 unblind(mp_int
*out
, mp_int
*bi
, mp_int
*n
)
101 /* out' = (out * 1/b) mod n */
102 mp_mul(out
, bi
, out
);
107 ltm_rsa_private_calculate(mp_int
* in
, mp_int
* p
, mp_int
* q
,
108 mp_int
* dmp1
, mp_int
* dmq1
, mp_int
* iqmp
,
113 mp_init_multi(&vp
, &vq
, &u
, NULL
);
115 /* vq = c ^ (d mod (q - 1)) mod q */
116 /* vp = c ^ (d mod (p - 1)) mod p */
118 mp_exptmod(&u
, dmp1
, p
, &vp
);
120 mp_exptmod(&u
, dmq1
, q
, &vq
);
122 /* C2 = 1/q mod p (iqmp) */
123 /* u = (vp - vq)C2 mod p. */
124 mp_sub(&vp
, &vq
, &u
);
127 mp_mul(&u
, iqmp
, &u
);
130 /* c ^ d mod n = vq + u q */
132 mp_add(&u
, &vq
, out
);
134 mp_clear_multi(&vp
, &vq
, &u
, NULL
);
144 ltm_rsa_public_encrypt(int flen
, const unsigned char* from
,
145 unsigned char* to
, RSA
* rsa
, int padding
)
147 unsigned char *p
, *p0
;
150 mp_int enc
, dec
, n
, e
;
152 if (padding
!= RSA_PKCS1_PADDING
)
155 mp_init_multi(&n
, &e
, &enc
, &dec
, NULL
);
157 size
= RSA_size(rsa
);
159 if (size
< RSA_PKCS1_PADDING_SIZE
|| size
- RSA_PKCS1_PADDING_SIZE
< flen
) {
160 mp_clear_multi(&n
, &e
, &enc
, &dec
);
167 p
= p0
= malloc(size
- 1);
169 mp_clear_multi(&e
, &n
, &enc
, &dec
, NULL
);
173 padlen
= size
- flen
- 3;
176 if (RAND_bytes(p
, padlen
) != 1) {
177 mp_clear_multi(&e
, &n
, &enc
, &dec
, NULL
);
188 memcpy(p
, from
, flen
);
190 assert((p
- p0
) == size
- 1);
192 mp_read_unsigned_bin(&dec
, p0
, size
- 1);
195 res
= mp_exptmod(&dec
, &e
, &n
, &enc
);
197 mp_clear_multi(&dec
, &e
, &n
, NULL
);
206 ssize
= mp_unsigned_bin_size(&enc
);
207 assert(size
>= ssize
);
208 mp_to_unsigned_bin(&enc
, to
);
217 ltm_rsa_public_decrypt(int flen
, const unsigned char* from
,
218 unsigned char* to
, RSA
* rsa
, int padding
)
225 if (padding
!= RSA_PKCS1_PADDING
)
228 if (flen
> RSA_size(rsa
))
231 mp_init_multi(&e
, &n
, &s
, &us
, NULL
);
237 /* Check that the exponent is larger then 3 */
238 if (mp_int_compare_value(&e
, 3) <= 0) {
239 mp_clear_multi(&e
, &n
, &s
, &us
, NULL
);
244 mp_read_unsigned_bin(&s
, rk_UNCONST(from
), flen
);
246 if (mp_cmp(&s
, &n
) >= 0) {
247 mp_clear_multi(&e
, &n
, &s
, &us
, NULL
);
251 res
= mp_exptmod(&s
, &e
, &n
, &us
);
253 mp_clear_multi(&e
, &n
, &s
, NULL
);
262 size
= mp_unsigned_bin_size(&us
);
263 assert(size
<= RSA_size(rsa
));
264 mp_to_unsigned_bin(&us
, p
);
268 /* head zero was skipped by mp_to_unsigned_bin */
274 while (size
&& *p
== 0xff) {
277 if (size
== 0 || *p
!= 0)
281 memmove(to
, p
, size
);
287 ltm_rsa_private_encrypt(int flen
, const unsigned char* from
,
288 unsigned char* to
, RSA
* rsa
, int padding
)
290 unsigned char *p
, *p0
;
293 mp_int in
, out
, n
, e
;
295 int blinding
= (rsa
->flags
& RSA_FLAG_NO_BLINDING
) == 0;
298 if (padding
!= RSA_PKCS1_PADDING
)
301 mp_init_multi(&e
, &n
, &in
, &out
, &b
, &bi
, NULL
);
303 size
= RSA_size(rsa
);
305 if (size
< RSA_PKCS1_PADDING_SIZE
|| size
- RSA_PKCS1_PADDING_SIZE
< flen
)
308 p0
= p
= malloc(size
);
311 memset(p
, 0xff, size
- flen
- 3);
312 p
+= size
- flen
- 3;
314 memcpy(p
, from
, flen
);
316 assert((p
- p0
) == size
);
321 mp_read_unsigned_bin(&in
, p0
, size
);
324 if(mp_isneg(&in
) || mp_cmp(&in
, &n
) >= 0) {
330 setup_blind(&n
, &b
, &bi
);
331 blind(&in
, &b
, &e
, &n
);
335 if (rsa
->p
&& rsa
->q
&& rsa
->dmp1
&& rsa
->dmq1
&& rsa
->iqmp
) {
336 mp_int p
, q
, dmp1
, dmq1
, iqmp
;
338 mp_init_multi(&p
, &q
, &dmp1
, &dmq1
, &iqmp
, NULL
);
342 BN2mpz(&dmp1
, rsa
->dmp1
);
343 BN2mpz(&dmq1
, rsa
->dmq1
);
344 BN2mpz(&iqmp
, rsa
->iqmp
);
346 res
= ltm_rsa_private_calculate(&in
, &p
, &q
, &dmp1
, &dmq1
, &iqmp
, &out
);
348 mp_clear_multi(&p
, &q
, &dmp1
, &dmq1
, &iqmp
, NULL
);
358 res
= mp_exptmod(&in
, &d
, &n
, &out
);
367 unblind(&out
, &bi
, &n
);
371 ssize
= mp_unsigned_bin_size(&out
);
372 assert(size
>= ssize
);
373 mp_to_unsigned_bin(&out
, to
);
378 mp_clear_multi(&e
, &n
, &in
, &out
, &b
, &bi
, NULL
);
384 ltm_rsa_private_decrypt(int flen
, const unsigned char* from
,
385 unsigned char* to
, RSA
* rsa
, int padding
)
390 mp_int in
, out
, n
, e
, b
, bi
;
391 int blinding
= (rsa
->flags
& RSA_FLAG_NO_BLINDING
) == 0;
394 if (padding
!= RSA_PKCS1_PADDING
)
397 size
= RSA_size(rsa
);
401 mp_init_multi(&in
, &n
, &e
, &out
, &bi
, &b
, NULL
);
406 mp_read_unsigned_bin(&in
, rk_UNCONST(from
), flen
);
408 if(mp_isneg(&in
) || mp_cmp(&in
, &n
) >= 0) {
414 setup_blind(&n
, &b
, &bi
);
415 blind(&in
, &b
, &e
, &n
);
419 if (rsa
->p
&& rsa
->q
&& rsa
->dmp1
&& rsa
->dmq1
&& rsa
->iqmp
) {
420 mp_int p
, q
, dmp1
, dmq1
, iqmp
;
422 mp_init_multi(&p
, &q
, &dmp1
, &dmq1
, &iqmp
, NULL
);
426 BN2mpz(&dmp1
, rsa
->dmp1
);
427 BN2mpz(&dmq1
, rsa
->dmq1
);
428 BN2mpz(&iqmp
, rsa
->iqmp
);
430 res
= ltm_rsa_private_calculate(&in
, &p
, &q
, &dmp1
, &dmq1
, &iqmp
, &out
);
432 mp_clear_multi(&p
, &q
, &dmp1
, &dmq1
, &iqmp
, NULL
);
442 if(mp_isneg(&in
) || mp_cmp(&in
, &n
) >= 0)
446 res
= mp_exptmod(&in
, &d
, &n
, &out
);
455 unblind(&out
, &bi
, &n
);
460 ssize
= mp_unsigned_bin_size(&out
);
461 assert(size
>= ssize
);
462 mp_to_unsigned_bin(&out
, ptr
);
466 /* head zero was skipped by mp_int_to_unsigned */
472 while (size
&& *ptr
!= 0) {
479 memmove(to
, ptr
, size
);
482 mp_clear_multi(&e
, &n
, &in
, &out
, NULL
);
494 size
= mp_unsigned_bin_size(s
);
496 if (p
== NULL
&& size
!= 0)
499 mp_to_unsigned_bin(s
, p
);
501 bn
= BN_bin2bn(p
, size
, NULL
);
506 #define CHECK(f, v) if ((f) != (v)) { goto out; }
509 ltm_rsa_generate_key(RSA
*rsa
, int bits
, BIGNUM
*e
, BN_GENCB
*cb
)
511 mp_int el
, p
, q
, n
, d
, dmp1
, dmq1
, iqmp
, t1
, t2
, t3
;
512 int counter
, ret
, bitsp
;
517 bitsp
= (bits
+ 1) / 2;
521 mp_init_multi(&el
, &p
, &q
, &n
, &n
, &d
, &dmp1
, &dmq1
, &iqmp
, &t1
, &t2
, &t3
, NULL
);
525 /* generate p and q so that p != q and bits(pq) ~ bits */
528 BN_GENCB_call(cb
, 2, counter
++);
529 CHECK(random_num(&p
, bitsp
), 0);
530 CHECK(mp_find_prime(&p
), MP_YES
);
532 mp_sub_d(&p
, 1, &t1
);
533 mp_gcd(&t1
, &el
, &t2
);
534 } while(mp_cmp_d(&t2
, 1) != 0);
536 BN_GENCB_call(cb
, 3, 0);
540 BN_GENCB_call(cb
, 2, counter
++);
541 CHECK(random_num(&q
, bits
- bitsp
), 0);
542 CHECK(mp_find_prime(&q
), MP_YES
);
544 if (mp_cmp(&p
, &q
) == 0) /* don't let p and q be the same */
547 mp_sub_d(&q
, 1, &t1
);
548 mp_gcd(&t1
, &el
, &t2
);
549 } while(mp_cmp_d(&t2
, 1) != 0);
552 if (mp_cmp(&p
, &q
) < 0) {
559 BN_GENCB_call(cb
, 3, 1);
561 /* calculate n, n = p * q */
564 /* calculate d, d = 1/e mod (p - 1)(q - 1) */
565 mp_sub_d(&p
, 1, &t1
);
566 mp_sub_d(&q
, 1, &t2
);
567 mp_mul(&t1
, &t2
, &t3
);
568 mp_invmod(&el
, &t3
, &d
);
570 /* calculate dmp1 dmp1 = d mod (p-1) */
571 mp_mod(&d
, &t1
, &dmp1
);
572 /* calculate dmq1 dmq1 = d mod (q-1) */
573 mp_mod(&d
, &t2
, &dmq1
);
574 /* calculate iqmp iqmp = 1/q mod p */
575 mp_invmod(&q
, &p
, &iqmp
);
577 /* fill in RSA key */
579 rsa
->e
= mpz2BN(&el
);
584 rsa
->dmp1
= mpz2BN(&dmp1
);
585 rsa
->dmq1
= mpz2BN(&dmq1
);
586 rsa
->iqmp
= mpz2BN(&iqmp
);
591 mp_clear_multi(&el
, &p
, &q
, &n
, &d
, &dmp1
,
592 &dmq1
, &iqmp
, &t1
, &t2
, &t3
, NULL
);
598 ltm_rsa_init(RSA
*rsa
)
604 ltm_rsa_finish(RSA
*rsa
)
609 const RSA_METHOD hc_rsa_ltm_method
= {
611 ltm_rsa_public_encrypt
,
612 ltm_rsa_public_decrypt
,
613 ltm_rsa_private_encrypt
,
614 ltm_rsa_private_decrypt
,
629 return &hc_rsa_ltm_method
;