2 * rsa.c RSA Public and Private key generation functions,
3 * RSA encrypt and decrypt functions.
5 * Author: Pekka Riikonen <priikone@silcnet.org>
7 * Copyright (C) 1997 - 2003 Pekka Riikonen
9 * This program is free software; you can redistribute it and/or modify
10 * it under the terms of the GNU General Public License as published by
11 * the Free Software Foundation; either version 2 of the License, or
12 * (at your option) any later version.
14 * This program is distributed in the hope that it will be useful,
15 * but WITHOUT ANY WARRANTY; without even the implied warranty of
16 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
17 * GNU General Public License for more details.
19 * Created: Sat Mar 1 13:26:45 1997 pekka
21 * RSA public key cryptographic algorithm used in this distribution is:
28 * Public key exponent:
29 * e relatively prime to (p-1) * (q-1)
30 * Private key exponent:
31 * d = e ^ -1 mod lcm(((p-1) * (q-1)))
38 * Supports CRT (Chinese Remainder Theorem) for private key operations.
40 * The SSH's (Secure Shell), PGP's (Pretty Good Privacy) and RSAREF
41 * Toolkit were used as reference when coding this implementation. They
42 * all were a big help for me.
44 * I also suggest reading Bruce Schneier's; Applied Cryptography, Second
45 * Edition, John Wiley & Sons, Inc. 1996. This book deals about RSA and
46 * everything else too about cryptography.
54 o Mon Feb 12 11:20:32 EET 2001 Pekka
56 Changed RSA private exponent generation to what PKCS #1 suggests. We
57 try to find the smallest possible d by doing modinv(e, lcm(phi)) instead
58 of modinv(e, phi). Note: this is not security fix but optimization.
60 o Tue Feb 20 13:58:58 EET 2001 Pekka
62 Set key->bits in rsa_generate_key. It is the modulus length in bits.
63 The `tmplen' in encrypt, decrypt, sign and verify PKCS API functions
64 is now calculated by (key->bits + 7) / 8. It is the length of one block.
66 o Sat Mar 16 18:27:19 EET 2002 Pekka
68 Use the SilcRng sent as argument to SILC_PKCS_API_INIT in prime
71 o Sat Sep 26 19:59:48 EEST 2002 Pekka
73 Fixed double free in public key setting. Use a bit larger e as
74 starting point in key generation.
78 #include "silcincludes.h"
79 #include "rsa_internal.h"
83 * SILC PKCS API for RSA
86 /* Generates RSA key pair. */
88 SILC_PKCS_API_INIT(rsa)
90 SilcUInt32 prime_bits = keylen / 2;
94 if (keylen < 768 || keylen > 16384)
97 printf("Generating RSA Public and Private keys, might take a while...\n");
104 printf("Finding p: ");
105 silc_math_gen_prime(&p, prime_bits, TRUE, rng);
107 printf("\nFinding q: ");
108 silc_math_gen_prime(&q, prime_bits, TRUE, rng);
110 if ((silc_mp_cmp(&p, &q)) == 0)
111 printf("\nFound equal primes, not good, retrying...\n");
116 /* If p is smaller than q, switch them */
117 if ((silc_mp_cmp(&p, &q)) > 0) {
121 silc_mp_set(&hlp, &p);
123 silc_mp_set(&q, &hlp);
125 silc_mp_uninit(&hlp);
128 /* Generate the actual keys */
129 rsa_generate_keys((RsaKey *)context, keylen, &p, &q);
134 printf("\nKeys generated successfully.\n");
139 SILC_PKCS_API_CLEAR_KEYS(rsa)
141 rsa_clear_keys((RsaKey *)context);
144 /* Returns SILC style encoded RSA public key. */
146 SILC_PKCS_API_GET_PUBLIC_KEY(rsa)
148 RsaKey *key = (RsaKey *)context;
149 unsigned char *e, *n, *ret;
150 SilcUInt32 e_len, n_len;
151 unsigned char tmp[4];
153 e = silc_mp_mp2bin(&key->e, 0, &e_len);
154 n = silc_mp_mp2bin(&key->n, (key->bits + 7) / 8, &n_len);
156 *ret_len = e_len + 4 + n_len + 4;
157 ret = silc_calloc(*ret_len, sizeof(unsigned char));
159 /* Put the length of the e. */
160 SILC_PUT32_MSB(e_len, tmp);
164 memcpy(ret + 4, e, e_len);
166 /* Put the length of the n. */
167 SILC_PUT32_MSB(n_len, tmp);
168 memcpy(ret + 4 + e_len, tmp, 4);
171 memcpy(ret + 4 + e_len + 4, n, n_len);
181 /* Returns SILC style encoded RSA private key. Public key is always
182 returned in private key as well. Public keys are often derived
183 directly from private key. */
185 SILC_PKCS_API_GET_PRIVATE_KEY(rsa)
187 RsaKey *key = (RsaKey *)context;
189 unsigned char *e, *n, *d, *ret, *dp = NULL, *dq = NULL;
190 unsigned char *pq = NULL, *qp = NULL, *p = NULL, *q = NULL;
191 SilcUInt32 e_len, n_len, d_len, dp_len, dq_len, pq_len, qp_len, p_len, q_len;
194 e = silc_mp_mp2bin(&key->e, 0, &e_len);
195 n = silc_mp_mp2bin(&key->n, (key->bits + 7) / 8, &n_len);
196 d = silc_mp_mp2bin(&key->d, 0, &d_len);
198 dp = silc_mp_mp2bin(&key->dP, 0, &dp_len);
199 dq = silc_mp_mp2bin(&key->dQ, 0, &dq_len);
200 pq = silc_mp_mp2bin(&key->pQ, 0, &pq_len);
201 qp = silc_mp_mp2bin(&key->qP, 0, &qp_len);
202 p = silc_mp_mp2bin(&key->p, 0, &p_len);
203 q = silc_mp_mp2bin(&key->q, 0, &q_len);
204 len = dp_len + 4 + dq_len + 4 + pq_len + 4 + qp_len + 4 + p_len + 4 +
208 buf = silc_buffer_alloc_size(e_len + 4 + n_len + 4 + d_len + 4 + len);
209 len = silc_buffer_format(buf,
210 SILC_STR_UI_INT(e_len),
211 SILC_STR_UI_XNSTRING(e, e_len),
212 SILC_STR_UI_INT(n_len),
213 SILC_STR_UI_XNSTRING(n, n_len),
214 SILC_STR_UI_INT(d_len),
215 SILC_STR_UI_XNSTRING(d, d_len),
219 silc_buffer_pull(buf, len);
220 silc_buffer_format(buf,
221 SILC_STR_UI_INT(dp_len),
222 SILC_STR_UI_XNSTRING(dp, dp_len),
223 SILC_STR_UI_INT(dq_len),
224 SILC_STR_UI_XNSTRING(dq, dq_len),
225 SILC_STR_UI_INT(pq_len),
226 SILC_STR_UI_XNSTRING(pq, pq_len),
227 SILC_STR_UI_INT(qp_len),
228 SILC_STR_UI_XNSTRING(qp, qp_len),
229 SILC_STR_UI_INT(p_len),
230 SILC_STR_UI_XNSTRING(p, p_len),
231 SILC_STR_UI_INT(q_len),
232 SILC_STR_UI_XNSTRING(q, q_len),
234 silc_buffer_push(buf, len);
236 memset(dp, 0, dp_len);
237 memset(dq, 0, dq_len);
238 memset(pq, 0, pq_len);
239 memset(qp, 0, qp_len);
255 ret = silc_buffer_steal(buf, ret_len);
256 silc_buffer_free(buf);
262 SILC_PKCS_API_SET_PUBLIC_KEY(rsa)
264 RsaKey *key = (RsaKey *)context;
265 unsigned char tmp[4];
266 SilcUInt32 e_len, n_len;
269 silc_mp_uninit(&key->e);
270 silc_mp_uninit(&key->n);
271 key->pub_set = FALSE;
277 silc_mp_init(&key->e);
278 silc_mp_init(&key->n);
280 memcpy(tmp, key_data, 4);
281 SILC_GET32_MSB(e_len, tmp);
282 if (!e_len || e_len + 4 > key_len) {
283 silc_mp_uninit(&key->e);
284 silc_mp_uninit(&key->n);
288 silc_mp_bin2mp(key_data + 4, e_len, &key->e);
290 if (key_len < 4 + e_len + 4) {
291 silc_mp_uninit(&key->e);
292 silc_mp_uninit(&key->n);
296 memcpy(tmp, key_data + 4 + e_len, 4);
297 SILC_GET32_MSB(n_len, tmp);
298 if (!n_len || e_len + 4 + n_len + 4 > key_len) {
299 silc_mp_uninit(&key->e);
300 silc_mp_uninit(&key->n);
304 silc_mp_bin2mp(key_data + 4 + e_len + 4, n_len, &key->n);
306 key->bits = silc_mp_sizeinbase(&key->n, 2);
312 /* Set private key. This derives the public key from the private
313 key and sets the public key as well. Public key should not be set
314 already and should not be set after setting private key. */
316 SILC_PKCS_API_SET_PRIVATE_KEY(rsa)
318 RsaKey *key = (RsaKey *)context;
324 silc_mp_uninit(&key->d);
325 key->prv_set = FALSE;
329 silc_mp_uninit(&key->e);
330 silc_mp_uninit(&key->n);
331 key->pub_set = FALSE;
337 silc_buffer_set(&k, key_data, key_len);
339 silc_mp_init(&key->e);
340 silc_mp_init(&key->n);
341 silc_mp_init(&key->d);
346 if (silc_buffer_unformat(&k,
347 SILC_STR_UI_INT(&len),
350 silc_buffer_pull(&k, 4);
351 if (silc_buffer_unformat(&k,
352 SILC_STR_UI_XNSTRING(&tmp, len),
355 silc_mp_bin2mp(tmp, len, &key->e);
356 silc_buffer_pull(&k, len);
359 if (silc_buffer_unformat(&k,
360 SILC_STR_UI_INT(&len),
363 silc_buffer_pull(&k, 4);
364 if (silc_buffer_unformat(&k,
365 SILC_STR_UI_XNSTRING(&tmp, len),
368 silc_mp_bin2mp(tmp, len, &key->n);
369 silc_buffer_pull(&k, len);
372 if (silc_buffer_unformat(&k,
373 SILC_STR_UI_INT(&len),
376 silc_buffer_pull(&k, 4);
377 if (silc_buffer_unformat(&k,
378 SILC_STR_UI_XNSTRING(&tmp, len),
381 silc_mp_bin2mp(tmp, len, &key->d);
382 silc_buffer_pull(&k, len);
384 /* Get optimized d for CRT, if present. */
387 silc_mp_init(&key->dP);
388 silc_mp_init(&key->dQ);
389 silc_mp_init(&key->pQ);
390 silc_mp_init(&key->qP);
391 silc_mp_init(&key->p);
392 silc_mp_init(&key->q);
395 if (silc_buffer_unformat(&k,
396 SILC_STR_UI_INT(&len),
399 silc_buffer_pull(&k, 4);
400 if (silc_buffer_unformat(&k,
401 SILC_STR_UI_XNSTRING(&tmp, len),
404 silc_mp_bin2mp(tmp, len, &key->dP);
405 silc_buffer_pull(&k, len);
408 if (silc_buffer_unformat(&k,
409 SILC_STR_UI_INT(&len),
412 silc_buffer_pull(&k, 4);
413 if (silc_buffer_unformat(&k,
414 SILC_STR_UI_XNSTRING(&tmp, len),
417 silc_mp_bin2mp(tmp, len, &key->dQ);
418 silc_buffer_pull(&k, len);
421 if (silc_buffer_unformat(&k,
422 SILC_STR_UI_INT(&len),
425 silc_buffer_pull(&k, 4);
426 if (silc_buffer_unformat(&k,
427 SILC_STR_UI_XNSTRING(&tmp, len),
430 silc_mp_bin2mp(tmp, len, &key->pQ);
431 silc_buffer_pull(&k, len);
434 if (silc_buffer_unformat(&k,
435 SILC_STR_UI_INT(&len),
438 silc_buffer_pull(&k, 4);
439 if (silc_buffer_unformat(&k,
440 SILC_STR_UI_XNSTRING(&tmp, len),
443 silc_mp_bin2mp(tmp, len, &key->qP);
444 silc_buffer_pull(&k, len);
447 if (silc_buffer_unformat(&k,
448 SILC_STR_UI_INT(&len),
451 silc_buffer_pull(&k, 4);
452 if (silc_buffer_unformat(&k,
453 SILC_STR_UI_XNSTRING(&tmp, len),
456 silc_mp_bin2mp(tmp, len, &key->p);
457 silc_buffer_pull(&k, len);
460 if (silc_buffer_unformat(&k,
461 SILC_STR_UI_INT(&len),
464 silc_buffer_pull(&k, 4);
465 if (silc_buffer_unformat(&k,
466 SILC_STR_UI_XNSTRING(&tmp, len),
469 silc_mp_bin2mp(tmp, len, &key->q);
470 silc_buffer_pull(&k, len);
473 key->bits = silc_mp_sizeinbase(&key->n, 2);
481 SILC_PKCS_API_CONTEXT_LEN(rsa)
483 return sizeof(RsaKey);
486 /* Raw RSA routines */
488 SILC_PKCS_API_ENCRYPT(rsa)
490 RsaKey *key = (RsaKey *)context;
495 silc_mp_init(&mp_tmp);
496 silc_mp_init(&mp_dst);
498 /* Format the data into MP int */
499 silc_mp_bin2mp(src, src_len, &mp_tmp);
502 rsa_public_operation(key, &mp_tmp, &mp_dst);
504 tmplen = (key->bits + 7) / 8;
506 /* Format the MP int back into data */
507 silc_mp_mp2bin_noalloc(&mp_dst, dst, tmplen);
510 silc_mp_uninit(&mp_tmp);
511 silc_mp_uninit(&mp_dst);
516 SILC_PKCS_API_DECRYPT(rsa)
518 RsaKey *key = (RsaKey *)context;
523 silc_mp_init(&mp_tmp);
524 silc_mp_init(&mp_dst);
526 /* Format the data into MP int */
527 silc_mp_bin2mp(src, src_len, &mp_tmp);
530 rsa_private_operation(key, &mp_tmp, &mp_dst);
532 tmplen = (key->bits + 7) / 8;
534 /* Format the MP int back into data */
535 silc_mp_mp2bin_noalloc(&mp_dst, dst, tmplen);
538 silc_mp_uninit(&mp_tmp);
539 silc_mp_uninit(&mp_dst);
544 SILC_PKCS_API_SIGN(rsa)
546 RsaKey *key = (RsaKey *)context;
551 silc_mp_init(&mp_tmp);
552 silc_mp_init(&mp_dst);
554 /* Format the data into MP int */
555 silc_mp_bin2mp(src, src_len, &mp_tmp);
558 rsa_private_operation(key, &mp_tmp, &mp_dst);
560 tmplen = (key->bits + 7) / 8;
562 /* Format the MP int back into data */
563 silc_mp_mp2bin_noalloc(&mp_dst, dst, tmplen);
566 silc_mp_uninit(&mp_tmp);
567 silc_mp_uninit(&mp_dst);
572 SILC_PKCS_API_VERIFY(rsa)
574 RsaKey *key = (RsaKey *)context;
576 SilcMPInt mp_tmp, mp_tmp2;
579 silc_mp_init(&mp_tmp);
580 silc_mp_init(&mp_tmp2);
581 silc_mp_init(&mp_dst);
583 /* Format the signature into MP int */
584 silc_mp_bin2mp(signature, signature_len, &mp_tmp2);
587 rsa_public_operation(key, &mp_tmp2, &mp_dst);
589 /* Format the data into MP int */
590 silc_mp_bin2mp(data, data_len, &mp_tmp);
595 if ((silc_mp_cmp(&mp_tmp, &mp_dst)) != 0)
598 silc_mp_uninit(&mp_tmp);
599 silc_mp_uninit(&mp_tmp2);
600 silc_mp_uninit(&mp_dst);
606 /* PKCS#1 RSA routines */
608 SILC_PKCS_API_ENCRYPT(pkcs1)
610 RsaKey *key = (RsaKey *)context;
613 unsigned char padded[2048 + 1];
614 SilcUInt32 len = (key->bits + 7) / 8;
616 if (sizeof(padded) < len)
620 if (!silc_pkcs1_encode(SILC_PKCS1_BT_PUB, src, src_len,
624 silc_mp_init(&mp_tmp);
625 silc_mp_init(&mp_dst);
628 silc_mp_bin2mp(padded, len, &mp_tmp);
631 rsa_public_operation(key, &mp_tmp, &mp_dst);
634 silc_mp_mp2bin_noalloc(&mp_dst, dst, len);
637 memset(padded, 0, sizeof(padded));
638 silc_mp_uninit(&mp_tmp);
639 silc_mp_uninit(&mp_dst);
644 SILC_PKCS_API_DECRYPT(pkcs1)
646 RsaKey *key = (RsaKey *)context;
649 unsigned char *padded, unpadded[2048 + 1];
650 SilcUInt32 padded_len;
652 silc_mp_init(&mp_tmp);
653 silc_mp_init(&mp_dst);
656 silc_mp_bin2mp(src, src_len, &mp_tmp);
659 rsa_private_operation(key, &mp_tmp, &mp_dst);
662 padded = silc_mp_mp2bin(&mp_dst, (key->bits + 7) / 8, &padded_len);
665 if (!silc_pkcs1_decode(SILC_PKCS1_BT_PUB, padded, padded_len,
666 unpadded, sizeof(unpadded), dst_len)) {
667 memset(padded, 0, padded_len);
669 silc_mp_uninit(&mp_tmp);
670 silc_mp_uninit(&mp_dst);
674 /* Copy to destination */
675 memcpy(dst, unpadded, *dst_len);
677 memset(padded, 0, padded_len);
678 memset(unpadded, 0, sizeof(unpadded));
680 silc_mp_uninit(&mp_tmp);
681 silc_mp_uninit(&mp_dst);
686 SILC_PKCS_API_SIGN(pkcs1)
688 RsaKey *key = (RsaKey *)context;
691 unsigned char padded[2048 + 1];
692 SilcUInt32 len = (key->bits + 7) / 8;
694 if (sizeof(padded) < len)
698 if (!silc_pkcs1_encode(SILC_PKCS1_BT_PRV1, src, src_len,
702 silc_mp_init(&mp_tmp);
703 silc_mp_init(&mp_dst);
706 silc_mp_bin2mp(padded, len, &mp_tmp);
709 rsa_private_operation(key, &mp_tmp, &mp_dst);
712 silc_mp_mp2bin_noalloc(&mp_dst, dst, len);
715 memset(padded, 0, sizeof(padded));
716 silc_mp_uninit(&mp_tmp);
717 silc_mp_uninit(&mp_dst);
722 SILC_PKCS_API_VERIFY(pkcs1)
724 RsaKey *key = (RsaKey *)context;
728 unsigned char *verify, unpadded[2048 + 1];
729 SilcUInt32 verify_len, len = (key->bits + 7) / 8;
731 silc_mp_init(&mp_tmp2);
732 silc_mp_init(&mp_dst);
734 /* Format the signature into MP int */
735 silc_mp_bin2mp(signature, signature_len, &mp_tmp2);
738 rsa_public_operation(key, &mp_tmp2, &mp_dst);
741 verify = silc_mp_mp2bin(&mp_dst, len, &verify_len);
744 if (!silc_pkcs1_decode(SILC_PKCS1_BT_PRV1, verify, verify_len,
745 unpadded, sizeof(unpadded), &len)) {
746 memset(verify, 0, verify_len);
748 silc_mp_uninit(&mp_tmp2);
749 silc_mp_uninit(&mp_dst);
754 if (memcmp(data, unpadded, len))
757 memset(verify, 0, verify_len);
758 memset(unpadded, 0, sizeof(unpadded));
760 silc_mp_uninit(&mp_tmp2);
761 silc_mp_uninit(&mp_dst);
766 /* Generates RSA public and private keys. Primes p and q that are used
767 to compute the modulus n has to be generated before calling this. They
768 are then sent as argument for the function. */
770 bool rsa_generate_keys(RsaKey *key, SilcUInt32 bits,
771 SilcMPInt *p, SilcMPInt *q)
777 /* Initialize variables */
778 silc_mp_init(&key->n);
779 silc_mp_init(&key->e);
780 silc_mp_init(&key->d);
781 silc_mp_init(&key->dP);
782 silc_mp_init(&key->dQ);
783 silc_mp_init(&key->pQ);
784 silc_mp_init(&key->qP);
792 /* Set modulus length */
795 /* Compute modulus, n = p * q */
796 silc_mp_mul(&key->n, p, q);
798 /* phi = (p - 1) * (q - 1) */
799 silc_mp_sub_ui(&pm1, p, 1);
800 silc_mp_sub_ui(&qm1, q, 1);
801 silc_mp_mul(&phi, &pm1, &qm1);
803 /* Set e, the public exponent. We try to use same public exponent
804 for all keys. Also, to make encryption faster we use small
806 silc_mp_set_ui(&key->e, 65533);
808 /* See if e is relatively prime to phi. gcd == greates common divisor,
809 if gcd equals 1 they are relatively prime. */
810 silc_mp_gcd(&hlp, &key->e, &phi);
811 if ((silc_mp_cmp_ui(&hlp, 1)) > 0) {
812 silc_mp_add_ui(&key->e, &key->e, 2);
816 /* Find d, the private exponent, e ^ -1 mod lcm(phi). */
817 silc_mp_gcd(&div, &pm1, &qm1);
818 silc_mp_div(&lcm, &phi, &div);
819 silc_mp_modinv(&key->d, &key->e, &lcm);
821 /* Optimize d with CRT. We precompute as much as possible. */
822 silc_mp_mod(&key->dP, &key->d, &pm1);
823 silc_mp_mod(&key->dQ, &key->d, &qm1);
824 silc_mp_modinv(&key->pQ, p, q);
825 silc_mp_mul(&key->pQ, p, &key->pQ);
826 silc_mp_mod(&key->pQ, &key->pQ, &key->n);
827 silc_mp_modinv(&key->qP, q, p);
828 silc_mp_mul(&key->qP, q, &key->qP);
829 silc_mp_mod(&key->qP, &key->qP, &key->n);
830 silc_mp_set(&key->p, p);
831 silc_mp_set(&key->q, q);
834 silc_mp_uninit(&phi);
835 silc_mp_uninit(&hlp);
836 silc_mp_uninit(&div);
837 silc_mp_uninit(&lcm);
838 silc_mp_uninit(&pm1);
839 silc_mp_uninit(&qm1);
844 /* Clears whole key structure. */
846 bool rsa_clear_keys(RsaKey *key)
850 silc_mp_uninit(&key->n);
851 silc_mp_uninit(&key->e);
854 silc_mp_uninit(&key->d);
855 if (key->prv_set && key->crt) {
856 silc_mp_uninit(&key->dP);
857 silc_mp_uninit(&key->dQ);
858 silc_mp_uninit(&key->pQ);
859 silc_mp_uninit(&key->qP);
860 silc_mp_uninit(&key->p);
861 silc_mp_uninit(&key->q);
866 /* RSA public key operation */
868 bool rsa_public_operation(RsaKey *key, SilcMPInt *src, SilcMPInt *dst)
870 /* dst = src ^ e mod n */
871 silc_mp_pow_mod(dst, src, &key->e, &key->n);
875 /* RSA private key operation */
877 bool rsa_private_operation(RsaKey *key, SilcMPInt *src, SilcMPInt *dst)
880 /* dst = src ^ d mod n */
881 silc_mp_pow_mod(dst, src, &key->d, &key->n);
888 /* dst = ((src ^ dP mod p) * qP) + ((src ^ dQ mod q) * pQ) mod n */
889 silc_mp_pow_mod(dst, src, &key->dP, &key->p);
890 silc_mp_mul(dst, dst, &key->qP);
891 silc_mp_pow_mod(&tmp, src, &key->dQ, &key->q);
892 silc_mp_mul(&tmp, &tmp, &key->pQ);
893 silc_mp_add(dst, dst, &tmp);
894 silc_mp_mod(dst, dst, &key->n);
896 silc_mp_uninit(&tmp);