X-Git-Url: http://git.silcnet.org/gitweb/?a=blobdiff_plain;f=lib%2Fsilccrypt%2Frsa.c;h=18399a5a393a0c49707d0803dad3eb402b27dab8;hb=40f8443d8d3a6577336ee66d18e04d9ac4d956bb;hp=a4479334ddf35701a36af6a51fe8a5302bdeaae4;hpb=fb8dbc2d9cd7ff5d197654f873ac18aa6ef9c5e3;p=silc.git diff --git a/lib/silccrypt/rsa.c b/lib/silccrypt/rsa.c index a4479334..18399a5a 100644 --- a/lib/silccrypt/rsa.c +++ b/lib/silccrypt/rsa.c @@ -1,48 +1,51 @@ -/* - * rsa.c RSA Public and Private key generation functions, - * RSA encrypt and decrypt functions. - * - * Author: Pekka Riikonen - * - * Copyright (C) 1997 - 2001 Pekka Riikonen - * - * This program is free software; you can redistribute it and/or modify - * it under the terms of the GNU General Public License as published by - * the Free Software Foundation; either version 2 of the License, or - * (at your option) any later version. - * - * This program is distributed in the hope that it will be useful, - * but WITHOUT ANY WARRANTY; without even the implied warranty of - * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the - * GNU General Public License for more details. - * - * Created: Sat Mar 1 13:26:45 1997 pekka - * - * RSA public key cryptographic algorithm used in this distribution is: - * - * Key generation: - * p, q primes - * p != q - * n = p * q modulus - * - * Public key exponent: - * e relatively prime to (p-1) * (q-1) - * Private key exponent: - * d = e ^ -1 mod lcm(((p-1) * (q-1))) - * - * Encryption: - * c = m ^ e mod n - * Decryption: - * m = c ^ d mod n - * - * This code is based on SSH's (Secure Shell), PGP's (Pretty Good Privacy) - * and RSAREF Toolkit's RSA source codes. They all were a big help for me. - * - * I also suggest reading Bruce Schneier's; Applied Cryptography, Second - * Edition, John Wiley & Sons, Inc. 1996. This book deals about RSA and - * everything else too about cryptography. - * - */ +/* + + rsa.c RSA Public and Private key generation functions, + RSA encrypt and decrypt functions. + + Author: Pekka Riikonen + + Copyright (C) 1997 - 2005 Pekka Riikonen + + This program is free software; you can redistribute it and/or modify + it under the terms of the GNU General Public License as published by + the Free Software Foundation; version 2 of the License. + + This program is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + GNU General Public License for more details. + + Created: Sat Mar 1 13:26:45 1997 pekka + + RSA public key cryptographic algorithm used in this distribution is: + + Key generation: + p, q primes + p != q + n = p * q modulus + + Public key exponent: + e relatively prime to (p-1) * (q-1) + Private key exponent: + d = e ^ -1 mod lcm(((p-1) * (q-1))) + + Encryption: + c = m ^ e mod n + Decryption: + m = c ^ d mod n + + Supports CRT (Chinese Remainder Theorem) for private key operations. + + The SSH's (Secure Shell), PGP's (Pretty Good Privacy) and RSAREF + Toolkit were used as reference when coding this implementation. They + all were a big help for me. + + I also suggest reading Bruce Schneier's; Applied Cryptography, Second + Edition, John Wiley & Sons, Inc. 1996. This book deals about RSA and + everything else too about cryptography. + +*/ /* $Id$ */ /* @@ -60,9 +63,20 @@ The `tmplen' in encrypt, decrypt, sign and verify PKCS API functions is now calculated by (key->bits + 7) / 8. It is the length of one block. + o Sat Mar 16 18:27:19 EET 2002 Pekka + + Use the SilcRng sent as argument to SILC_PKCS_API_INIT in prime + generation. + + o Sat Sep 26 19:59:48 EEST 2002 Pekka + + Fixed double free in public key setting. Use a bit larger e as + starting point in key generation. + */ -#include "silcincludes.h" +#include "silc.h" +#include "rsa_internal.h" #include "rsa.h" /* @@ -73,8 +87,12 @@ SILC_PKCS_API_INIT(rsa) { - uint32 prime_bits = keylen / 2; - SilcInt p, q; + SilcUInt32 prime_bits = keylen / 2; + SilcMPInt p, q; + SilcBool found = FALSE; + + if (keylen < 768 || keylen > 16384) + return FALSE; printf("Generating RSA Public and Private keys, might take a while...\n"); @@ -82,37 +100,38 @@ SILC_PKCS_API_INIT(rsa) silc_mp_init(&q); /* Find p and q */ - retry_primes: - printf("Finding p: "); - silc_math_gen_prime(&p, prime_bits, TRUE); - - printf("\nFinding q: "); - silc_math_gen_prime(&q, prime_bits, TRUE); - - if ((silc_mp_cmp(&p, &q)) == 0) { - printf("\nFound equal primes, not good, retrying...\n"); - goto retry_primes; + while (!found) { + printf("Finding p: "); + silc_math_gen_prime(&p, prime_bits, TRUE, rng); + + printf("\nFinding q: "); + silc_math_gen_prime(&q, prime_bits, TRUE, rng); + + if ((silc_mp_cmp(&p, &q)) == 0) + printf("\nFound equal primes, not good, retrying...\n"); + else + found = TRUE; } /* If p is smaller than q, switch them */ if ((silc_mp_cmp(&p, &q)) > 0) { - SilcInt hlp; + SilcMPInt hlp; silc_mp_init(&hlp); silc_mp_set(&hlp, &p); silc_mp_set(&p, &q); silc_mp_set(&q, &hlp); - silc_mp_clear(&hlp); + silc_mp_uninit(&hlp); } /* Generate the actual keys */ rsa_generate_keys((RsaKey *)context, keylen, &p, &q); - silc_mp_clear(&p); - silc_mp_clear(&q); - - printf("\nKeys generated succesfully.\n"); + silc_mp_uninit(&p); + silc_mp_uninit(&q); + + printf("\nKeys generated successfully.\n"); return TRUE; } @@ -128,11 +147,11 @@ SILC_PKCS_API_GET_PUBLIC_KEY(rsa) { RsaKey *key = (RsaKey *)context; unsigned char *e, *n, *ret; - uint32 e_len, n_len; + SilcUInt32 e_len, n_len; unsigned char tmp[4]; e = silc_mp_mp2bin(&key->e, 0, &e_len); - n = silc_mp_mp2bin(&key->n, key->bits / 8, &n_len); + n = silc_mp_mp2bin(&key->n, (key->bits + 7) / 8, &n_len); *ret_len = e_len + 4 + n_len + 4; ret = silc_calloc(*ret_len, sizeof(unsigned char)); @@ -166,45 +185,75 @@ SILC_PKCS_API_GET_PUBLIC_KEY(rsa) SILC_PKCS_API_GET_PRIVATE_KEY(rsa) { RsaKey *key = (RsaKey *)context; - unsigned char *e, *n, *d, *ret; - uint32 e_len, n_len, d_len; - unsigned char tmp[4]; + SilcBuffer buf; + unsigned char *e, *n, *d, *ret, *dp = NULL, *dq = NULL; + unsigned char *pq = NULL, *qp = NULL, *p = NULL, *q = NULL; + SilcUInt32 e_len, n_len, d_len, dp_len, dq_len, pq_len, qp_len, p_len, q_len; + SilcUInt32 len = 0; e = silc_mp_mp2bin(&key->e, 0, &e_len); - n = silc_mp_mp2bin(&key->n, key->bits / 8, &n_len); + n = silc_mp_mp2bin(&key->n, (key->bits + 7) / 8, &n_len); d = silc_mp_mp2bin(&key->d, 0, &d_len); + if (key->crt) { + dp = silc_mp_mp2bin(&key->dP, 0, &dp_len); + dq = silc_mp_mp2bin(&key->dQ, 0, &dq_len); + pq = silc_mp_mp2bin(&key->pQ, 0, &pq_len); + qp = silc_mp_mp2bin(&key->qP, 0, &qp_len); + p = silc_mp_mp2bin(&key->p, 0, &p_len); + q = silc_mp_mp2bin(&key->q, 0, &q_len); + len = dp_len + 4 + dq_len + 4 + pq_len + 4 + qp_len + 4 + p_len + 4 + + q_len + 4; + } - *ret_len = e_len + 4 + n_len + 4 + d_len + 4; - ret = silc_calloc(*ret_len, sizeof(unsigned char)); - - /* Put the length of the e. */ - SILC_PUT32_MSB(e_len, tmp); - memcpy(ret, tmp, 4); - - /* Put the e. */ - memcpy(ret + 4, e, e_len); - - /* Put the length of the n. */ - SILC_PUT32_MSB(n_len, tmp); - memcpy(ret + 4 + e_len, tmp, 4); - - /* Put the n. */ - memcpy(ret + 4 + e_len + 4, n, n_len); - - /* Put the length of the d. */ - SILC_PUT32_MSB(d_len, tmp); - memcpy(ret + 4 + e_len + 4 + n_len, tmp, 4); - - /* Put the n. */ - memcpy(ret + 4 + e_len + 4 + n_len + 4, d, d_len); + buf = silc_buffer_alloc_size(e_len + 4 + n_len + 4 + d_len + 4 + len); + len = silc_buffer_format(buf, + SILC_STR_UI_INT(e_len), + SILC_STR_UI_XNSTRING(e, e_len), + SILC_STR_UI_INT(n_len), + SILC_STR_UI_XNSTRING(n, n_len), + SILC_STR_UI_INT(d_len), + SILC_STR_UI_XNSTRING(d, d_len), + SILC_STR_END); + + if (key->crt) { + silc_buffer_pull(buf, len); + silc_buffer_format(buf, + SILC_STR_UI_INT(dp_len), + SILC_STR_UI_XNSTRING(dp, dp_len), + SILC_STR_UI_INT(dq_len), + SILC_STR_UI_XNSTRING(dq, dq_len), + SILC_STR_UI_INT(pq_len), + SILC_STR_UI_XNSTRING(pq, pq_len), + SILC_STR_UI_INT(qp_len), + SILC_STR_UI_XNSTRING(qp, qp_len), + SILC_STR_UI_INT(p_len), + SILC_STR_UI_XNSTRING(p, p_len), + SILC_STR_UI_INT(q_len), + SILC_STR_UI_XNSTRING(q, q_len), + SILC_STR_END); + silc_buffer_push(buf, len); + + memset(dp, 0, dp_len); + memset(dq, 0, dq_len); + memset(pq, 0, pq_len); + memset(qp, 0, qp_len); + memset(p, 0, p_len); + memset(q, 0, q_len); + silc_free(dp); + silc_free(dq); + silc_free(pq); + silc_free(qp); + silc_free(p); + silc_free(q); + } - memset(e, 0, e_len); - memset(n, 0, n_len); memset(d, 0, d_len); silc_free(e); silc_free(n); silc_free(d); + ret = silc_buffer_steal(buf, ret_len); + silc_buffer_free(buf); return ret; } @@ -214,32 +263,48 @@ SILC_PKCS_API_SET_PUBLIC_KEY(rsa) { RsaKey *key = (RsaKey *)context; unsigned char tmp[4]; - uint32 e_len, n_len; + SilcUInt32 e_len, n_len; + + if (key->pub_set) { + silc_mp_uninit(&key->e); + silc_mp_uninit(&key->n); + key->pub_set = FALSE; + } + + if (key_len < 4) + return 0; silc_mp_init(&key->e); silc_mp_init(&key->n); memcpy(tmp, key_data, 4); SILC_GET32_MSB(e_len, tmp); - if (e_len > key_len) { - silc_mp_clear(&key->e); - silc_mp_clear(&key->n); + if (!e_len || e_len + 4 > key_len) { + silc_mp_uninit(&key->e); + silc_mp_uninit(&key->n); return 0; } silc_mp_bin2mp(key_data + 4, e_len, &key->e); - + + if (key_len < 4 + e_len + 4) { + silc_mp_uninit(&key->e); + silc_mp_uninit(&key->n); + return 0; + } + memcpy(tmp, key_data + 4 + e_len, 4); SILC_GET32_MSB(n_len, tmp); - if (e_len + n_len > key_len) { - silc_mp_clear(&key->e); - silc_mp_clear(&key->n); + if (!n_len || e_len + 4 + n_len + 4 > key_len) { + silc_mp_uninit(&key->e); + silc_mp_uninit(&key->n); return 0; } silc_mp_bin2mp(key_data + 4 + e_len + 4, n_len, &key->n); - key->bits = n_len * 8; + key->bits = silc_mp_sizeinbase(&key->n, 2); + key->pub_set = TRUE; return key->bits; } @@ -251,46 +316,166 @@ SILC_PKCS_API_SET_PUBLIC_KEY(rsa) SILC_PKCS_API_SET_PRIVATE_KEY(rsa) { RsaKey *key = (RsaKey *)context; - unsigned char tmp[4]; - uint32 e_len, n_len, d_len; + SilcBufferStruct k; + unsigned char *tmp; + SilcUInt32 len; - silc_mp_init(&key->e); - silc_mp_init(&key->n); - silc_mp_init(&key->d); + if (key->prv_set) { + silc_mp_uninit(&key->d); + key->prv_set = FALSE; + } - memcpy(tmp, key_data, 4); - SILC_GET32_MSB(e_len, tmp); - if (e_len > key_len) { - silc_mp_clear(&key->e); - silc_mp_clear(&key->n); - return FALSE; + if (key->pub_set) { + silc_mp_uninit(&key->e); + silc_mp_uninit(&key->n); + key->pub_set = FALSE; } - silc_mp_bin2mp(key_data + 4, e_len, &key->e); - - memcpy(tmp, key_data + 4 + e_len, 4); - SILC_GET32_MSB(n_len, tmp); - if (e_len + n_len > key_len) { - silc_mp_clear(&key->e); - silc_mp_clear(&key->n); + if (key_len < 4) return FALSE; - } - silc_mp_bin2mp(key_data + 4 + e_len + 4, n_len, &key->n); + silc_buffer_set(&k, key_data, key_len); - memcpy(tmp, key_data + 4 + e_len + 4 + n_len, 4); - SILC_GET32_MSB(d_len, tmp); - if (e_len + n_len + d_len > key_len) { - silc_mp_clear(&key->e); - silc_mp_clear(&key->n); - return FALSE; + silc_mp_init(&key->e); + silc_mp_init(&key->n); + silc_mp_init(&key->d); + key->prv_set = TRUE; + key->pub_set = TRUE; + + /* Get e */ + if (silc_buffer_unformat(&k, + SILC_STR_UI_INT(&len), + SILC_STR_END) < 0) + goto err; + silc_buffer_pull(&k, 4); + if (silc_buffer_unformat(&k, + SILC_STR_UI_XNSTRING(&tmp, len), + SILC_STR_END) < 0) + goto err; + silc_mp_bin2mp(tmp, len, &key->e); + silc_buffer_pull(&k, len); + + /* Get n */ + if (silc_buffer_unformat(&k, + SILC_STR_UI_INT(&len), + SILC_STR_END) < 0) + goto err; + silc_buffer_pull(&k, 4); + if (silc_buffer_unformat(&k, + SILC_STR_UI_XNSTRING(&tmp, len), + SILC_STR_END) < 0) + goto err; + silc_mp_bin2mp(tmp, len, &key->n); + silc_buffer_pull(&k, len); + + /* Get d */ + if (silc_buffer_unformat(&k, + SILC_STR_UI_INT(&len), + SILC_STR_END) < 0) + goto err; + silc_buffer_pull(&k, 4); + if (silc_buffer_unformat(&k, + SILC_STR_UI_XNSTRING(&tmp, len), + SILC_STR_END) < 0) + goto err; + silc_mp_bin2mp(tmp, len, &key->d); + silc_buffer_pull(&k, len); + + /* Get optimized d for CRT, if present. */ + if (silc_buffer_len(&k) > 4) { + key->crt = TRUE; + silc_mp_init(&key->dP); + silc_mp_init(&key->dQ); + silc_mp_init(&key->pQ); + silc_mp_init(&key->qP); + silc_mp_init(&key->p); + silc_mp_init(&key->q); + + /* Get dP */ + if (silc_buffer_unformat(&k, + SILC_STR_UI_INT(&len), + SILC_STR_END) < 0) + goto err; + silc_buffer_pull(&k, 4); + if (silc_buffer_unformat(&k, + SILC_STR_UI_XNSTRING(&tmp, len), + SILC_STR_END) < 0) + goto err; + silc_mp_bin2mp(tmp, len, &key->dP); + silc_buffer_pull(&k, len); + + /* Get dQ */ + if (silc_buffer_unformat(&k, + SILC_STR_UI_INT(&len), + SILC_STR_END) < 0) + goto err; + silc_buffer_pull(&k, 4); + if (silc_buffer_unformat(&k, + SILC_STR_UI_XNSTRING(&tmp, len), + SILC_STR_END) < 0) + goto err; + silc_mp_bin2mp(tmp, len, &key->dQ); + silc_buffer_pull(&k, len); + + /* Get pQ */ + if (silc_buffer_unformat(&k, + SILC_STR_UI_INT(&len), + SILC_STR_END) < 0) + goto err; + silc_buffer_pull(&k, 4); + if (silc_buffer_unformat(&k, + SILC_STR_UI_XNSTRING(&tmp, len), + SILC_STR_END) < 0) + goto err; + silc_mp_bin2mp(tmp, len, &key->pQ); + silc_buffer_pull(&k, len); + + /* Get qP */ + if (silc_buffer_unformat(&k, + SILC_STR_UI_INT(&len), + SILC_STR_END) < 0) + goto err; + silc_buffer_pull(&k, 4); + if (silc_buffer_unformat(&k, + SILC_STR_UI_XNSTRING(&tmp, len), + SILC_STR_END) < 0) + goto err; + silc_mp_bin2mp(tmp, len, &key->qP); + silc_buffer_pull(&k, len); + + /* Get p */ + if (silc_buffer_unformat(&k, + SILC_STR_UI_INT(&len), + SILC_STR_END) < 0) + goto err; + silc_buffer_pull(&k, 4); + if (silc_buffer_unformat(&k, + SILC_STR_UI_XNSTRING(&tmp, len), + SILC_STR_END) < 0) + goto err; + silc_mp_bin2mp(tmp, len, &key->p); + silc_buffer_pull(&k, len); + + /* Get q */ + if (silc_buffer_unformat(&k, + SILC_STR_UI_INT(&len), + SILC_STR_END) < 0) + goto err; + silc_buffer_pull(&k, 4); + if (silc_buffer_unformat(&k, + SILC_STR_UI_XNSTRING(&tmp, len), + SILC_STR_END) < 0) + goto err; + silc_mp_bin2mp(tmp, len, &key->q); + silc_buffer_pull(&k, len); } - silc_mp_bin2mp(key_data + 4 + e_len + 4 + n_len + 4, d_len, &key->d); - - key->bits = n_len * 8; + key->bits = silc_mp_sizeinbase(&key->n, 2); + return key->bits; - return TRUE; + err: + rsa_clear_keys(key); + return FALSE; } SILC_PKCS_API_CONTEXT_LEN(rsa) @@ -298,36 +483,32 @@ SILC_PKCS_API_CONTEXT_LEN(rsa) return sizeof(RsaKey); } +/* Raw RSA routines */ + SILC_PKCS_API_ENCRYPT(rsa) { RsaKey *key = (RsaKey *)context; - int i, tmplen; - SilcInt mp_tmp; - SilcInt mp_dst; + int tmplen; + SilcMPInt mp_tmp; + SilcMPInt mp_dst; - silc_mp_init_set_ui(&mp_tmp, 0); - silc_mp_init_set_ui(&mp_dst, 0); + silc_mp_init(&mp_tmp); + silc_mp_init(&mp_dst); /* Format the data into MP int */ - for (i = 0; i < src_len; i++) { - silc_mp_mul_2exp(&mp_tmp, &mp_tmp, 8); - silc_mp_add_ui(&mp_tmp, &mp_tmp, src[i]); - } + silc_mp_bin2mp(src, src_len, &mp_tmp); /* Encrypt */ - rsa_en_de_crypt(&mp_dst, &mp_tmp, &key->e, &key->n); - + rsa_public_operation(key, &mp_tmp, &mp_dst); + tmplen = (key->bits + 7) / 8; /* Format the MP int back into data */ - for (i = tmplen; i > 0; i--) { - dst[i - 1] = (unsigned char)(silc_mp_get_ui(&mp_dst) & 0xff); - silc_mp_fdiv_q_2exp(&mp_dst, &mp_dst, 8); - } + silc_mp_mp2bin_noalloc(&mp_dst, dst, tmplen); *dst_len = tmplen; - silc_mp_clear(&mp_tmp); - silc_mp_clear(&mp_dst); + silc_mp_uninit(&mp_tmp); + silc_mp_uninit(&mp_dst); return TRUE; } @@ -335,33 +516,27 @@ SILC_PKCS_API_ENCRYPT(rsa) SILC_PKCS_API_DECRYPT(rsa) { RsaKey *key = (RsaKey *)context; - int i, tmplen; - SilcInt mp_tmp; - SilcInt mp_dst; + int tmplen; + SilcMPInt mp_tmp; + SilcMPInt mp_dst; - silc_mp_init_set_ui(&mp_tmp, 0); - silc_mp_init_set_ui(&mp_dst, 0); + silc_mp_init(&mp_tmp); + silc_mp_init(&mp_dst); /* Format the data into MP int */ - for (i = 0; i < src_len; i++) { - silc_mp_mul_2exp(&mp_tmp, &mp_tmp, 8); - silc_mp_add_ui(&mp_tmp, &mp_tmp, src[i]); - } + silc_mp_bin2mp(src, src_len, &mp_tmp); /* Decrypt */ - rsa_en_de_crypt(&mp_dst, &mp_tmp, &key->d, &key->n); + rsa_private_operation(key, &mp_tmp, &mp_dst); tmplen = (key->bits + 7) / 8; /* Format the MP int back into data */ - for (i = tmplen; i > 0; i--) { - dst[i - 1] = (unsigned char)(silc_mp_get_ui(&mp_dst) & 0xff); - silc_mp_fdiv_q_2exp(&mp_dst, &mp_dst, 8); - } + silc_mp_mp2bin_noalloc(&mp_dst, dst, tmplen); *dst_len = tmplen; - silc_mp_clear(&mp_tmp); - silc_mp_clear(&mp_dst); + silc_mp_uninit(&mp_tmp); + silc_mp_uninit(&mp_dst); return TRUE; } @@ -369,33 +544,27 @@ SILC_PKCS_API_DECRYPT(rsa) SILC_PKCS_API_SIGN(rsa) { RsaKey *key = (RsaKey *)context; - int i, tmplen; - SilcInt mp_tmp; - SilcInt mp_dst; + int tmplen; + SilcMPInt mp_tmp; + SilcMPInt mp_dst; - silc_mp_init_set_ui(&mp_tmp, 0); - silc_mp_init_set_ui(&mp_dst, 0); + silc_mp_init(&mp_tmp); + silc_mp_init(&mp_dst); /* Format the data into MP int */ - for (i = 0; i < src_len; i++) { - silc_mp_mul_2exp(&mp_tmp, &mp_tmp, 8); - silc_mp_add_ui(&mp_tmp, &mp_tmp, src[i]); - } + silc_mp_bin2mp(src, src_len, &mp_tmp); /* Sign */ - rsa_en_de_crypt(&mp_dst, &mp_tmp, &key->d, &key->n); + rsa_private_operation(key, &mp_tmp, &mp_dst); tmplen = (key->bits + 7) / 8; /* Format the MP int back into data */ - for (i = tmplen; i > 0; i--) { - dst[i - 1] = (unsigned char)(silc_mp_get_ui(&mp_dst) & 0xff); - silc_mp_fdiv_q_2exp(&mp_dst, &mp_dst, 8); - } + silc_mp_mp2bin_noalloc(&mp_dst, dst, tmplen); *dst_len = tmplen; - silc_mp_clear(&mp_tmp); - silc_mp_clear(&mp_dst); + silc_mp_uninit(&mp_tmp); + silc_mp_uninit(&mp_dst); return TRUE; } @@ -403,28 +572,22 @@ SILC_PKCS_API_SIGN(rsa) SILC_PKCS_API_VERIFY(rsa) { RsaKey *key = (RsaKey *)context; - int i, ret; - SilcInt mp_tmp, mp_tmp2; - SilcInt mp_dst; + int ret; + SilcMPInt mp_tmp, mp_tmp2; + SilcMPInt mp_dst; - silc_mp_init_set_ui(&mp_tmp, 0); - silc_mp_init_set_ui(&mp_tmp2, 0); - silc_mp_init_set_ui(&mp_dst, 0); + silc_mp_init(&mp_tmp); + silc_mp_init(&mp_tmp2); + silc_mp_init(&mp_dst); /* Format the signature into MP int */ - for (i = 0; i < signature_len; i++) { - silc_mp_mul_2exp(&mp_tmp2, &mp_tmp2, 8); - silc_mp_add_ui(&mp_tmp2, &mp_tmp2, signature[i]); - } + silc_mp_bin2mp(signature, signature_len, &mp_tmp2); /* Verify */ - rsa_en_de_crypt(&mp_dst, &mp_tmp2, &key->e, &key->n); + rsa_public_operation(key, &mp_tmp2, &mp_dst); /* Format the data into MP int */ - for (i = 0; i < data_len; i++) { - silc_mp_mul_2exp(&mp_tmp, &mp_tmp, 8); - silc_mp_add_ui(&mp_tmp, &mp_tmp, data[i]); - } + silc_mp_bin2mp(data, data_len, &mp_tmp); ret = TRUE; @@ -432,9 +595,170 @@ SILC_PKCS_API_VERIFY(rsa) if ((silc_mp_cmp(&mp_tmp, &mp_dst)) != 0) ret = FALSE; - silc_mp_clear(&mp_tmp); - silc_mp_clear(&mp_tmp2); - silc_mp_clear(&mp_dst); + silc_mp_uninit(&mp_tmp); + silc_mp_uninit(&mp_tmp2); + silc_mp_uninit(&mp_dst); + + return ret; +} + + +/* PKCS#1 RSA routines */ + +SILC_PKCS_API_ENCRYPT(pkcs1) +{ + RsaKey *key = (RsaKey *)context; + SilcMPInt mp_tmp; + SilcMPInt mp_dst; + unsigned char padded[2048 + 1]; + SilcUInt32 len = (key->bits + 7) / 8; + + if (sizeof(padded) < len) + return FALSE; + + /* Pad data */ + if (!silc_pkcs1_encode(SILC_PKCS1_BT_PUB, src, src_len, + padded, len, NULL)) + return FALSE; + + silc_mp_init(&mp_tmp); + silc_mp_init(&mp_dst); + + /* Data to MP */ + silc_mp_bin2mp(padded, len, &mp_tmp); + + /* Encrypt */ + rsa_public_operation(key, &mp_tmp, &mp_dst); + + /* MP to data */ + silc_mp_mp2bin_noalloc(&mp_dst, dst, len); + *dst_len = len; + + memset(padded, 0, sizeof(padded)); + silc_mp_uninit(&mp_tmp); + silc_mp_uninit(&mp_dst); + + return TRUE; +} + +SILC_PKCS_API_DECRYPT(pkcs1) +{ + RsaKey *key = (RsaKey *)context; + SilcMPInt mp_tmp; + SilcMPInt mp_dst; + unsigned char *padded, unpadded[2048 + 1]; + SilcUInt32 padded_len; + + silc_mp_init(&mp_tmp); + silc_mp_init(&mp_dst); + + /* Data to MP */ + silc_mp_bin2mp(src, src_len, &mp_tmp); + + /* Decrypt */ + rsa_private_operation(key, &mp_tmp, &mp_dst); + + /* MP to data */ + padded = silc_mp_mp2bin(&mp_dst, (key->bits + 7) / 8, &padded_len); + + /* Unpad data */ + if (!silc_pkcs1_decode(SILC_PKCS1_BT_PUB, padded, padded_len, + unpadded, sizeof(unpadded), dst_len)) { + memset(padded, 0, padded_len); + silc_free(padded); + silc_mp_uninit(&mp_tmp); + silc_mp_uninit(&mp_dst); + return FALSE; + } + + /* Copy to destination */ + memcpy(dst, unpadded, *dst_len); + + memset(padded, 0, padded_len); + memset(unpadded, 0, sizeof(unpadded)); + silc_free(padded); + silc_mp_uninit(&mp_tmp); + silc_mp_uninit(&mp_dst); + + return TRUE; +} + +SILC_PKCS_API_SIGN(pkcs1) +{ + RsaKey *key = (RsaKey *)context; + SilcMPInt mp_tmp; + SilcMPInt mp_dst; + unsigned char padded[2048 + 1]; + SilcUInt32 len = (key->bits + 7) / 8; + + if (sizeof(padded) < len) + return FALSE; + + /* Pad data */ + if (!silc_pkcs1_encode(SILC_PKCS1_BT_PRV1, src, src_len, + padded, len, NULL)) + return FALSE; + + silc_mp_init(&mp_tmp); + silc_mp_init(&mp_dst); + + /* Data to MP */ + silc_mp_bin2mp(padded, len, &mp_tmp); + + /* Sign */ + rsa_private_operation(key, &mp_tmp, &mp_dst); + + /* MP to data */ + silc_mp_mp2bin_noalloc(&mp_dst, dst, len); + *dst_len = len; + + memset(padded, 0, sizeof(padded)); + silc_mp_uninit(&mp_tmp); + silc_mp_uninit(&mp_dst); + + return TRUE; +} + +SILC_PKCS_API_VERIFY(pkcs1) +{ + RsaKey *key = (RsaKey *)context; + int ret = TRUE; + SilcMPInt mp_tmp2; + SilcMPInt mp_dst; + unsigned char *verify, unpadded[2048 + 1]; + SilcUInt32 verify_len, len = (key->bits + 7) / 8; + + silc_mp_init(&mp_tmp2); + silc_mp_init(&mp_dst); + + /* Format the signature into MP int */ + silc_mp_bin2mp(signature, signature_len, &mp_tmp2); + + /* Verify */ + rsa_public_operation(key, &mp_tmp2, &mp_dst); + + /* MP to data */ + verify = silc_mp_mp2bin(&mp_dst, len, &verify_len); + + /* Unpad data */ + if (!silc_pkcs1_decode(SILC_PKCS1_BT_PRV1, verify, verify_len, + unpadded, sizeof(unpadded), &len)) { + memset(verify, 0, verify_len); + silc_free(verify); + silc_mp_uninit(&mp_tmp2); + silc_mp_uninit(&mp_dst); + return FALSE; + } + + /* Compare */ + if (memcmp(data, unpadded, len)) + ret = FALSE; + + memset(verify, 0, verify_len); + memset(unpadded, 0, sizeof(unpadded)); + silc_free(verify); + silc_mp_uninit(&mp_tmp2); + silc_mp_uninit(&mp_dst); return ret; } @@ -443,19 +767,21 @@ SILC_PKCS_API_VERIFY(rsa) to compute the modulus n has to be generated before calling this. They are then sent as argument for the function. */ -void rsa_generate_keys(RsaKey *key, uint32 bits, - SilcInt *p, SilcInt *q) +SilcBool rsa_generate_keys(RsaKey *key, SilcUInt32 bits, + SilcMPInt *p, SilcMPInt *q) { - SilcInt phi, hlp; - SilcInt div, lcm; - SilcInt pm1, qm1; - + SilcMPInt phi, hlp; + SilcMPInt div, lcm; + SilcMPInt pm1, qm1; + /* Initialize variables */ - silc_mp_init(&key->p); - silc_mp_init(&key->q); silc_mp_init(&key->n); silc_mp_init(&key->e); silc_mp_init(&key->d); + silc_mp_init(&key->dP); + silc_mp_init(&key->dQ); + silc_mp_init(&key->pQ); + silc_mp_init(&key->qP); silc_mp_init(&phi); silc_mp_init(&hlp); silc_mp_init(&div); @@ -466,66 +792,109 @@ void rsa_generate_keys(RsaKey *key, uint32 bits, /* Set modulus length */ key->bits = bits; - /* Set the primes */ - silc_mp_set(&key->p, p); - silc_mp_set(&key->q, q); - /* Compute modulus, n = p * q */ - silc_mp_mul(&key->n, &key->p, &key->q); - + silc_mp_mul(&key->n, p, q); + /* phi = (p - 1) * (q - 1) */ - silc_mp_sub_ui(&pm1, &key->p, 1); - silc_mp_sub_ui(&qm1, &key->q, 1); + silc_mp_sub_ui(&pm1, p, 1); + silc_mp_sub_ui(&qm1, q, 1); silc_mp_mul(&phi, &pm1, &qm1); - + /* Set e, the public exponent. We try to use same public exponent - for all keys. Also, to make encryption faster we use small + for all keys. Also, to make encryption faster we use small number. */ - silc_mp_set_ui(&key->e, 127); + silc_mp_set_ui(&key->e, 65533); retry_e: /* See if e is relatively prime to phi. gcd == greates common divisor, if gcd equals 1 they are relatively prime. */ silc_mp_gcd(&hlp, &key->e, &phi); - if((silc_mp_cmp_ui(&hlp, 1)) > 0) { + if ((silc_mp_cmp_ui(&hlp, 1)) > 0) { silc_mp_add_ui(&key->e, &key->e, 2); goto retry_e; } - - /* Find d, the private exponent. */ + + /* Find d, the private exponent, e ^ -1 mod lcm(phi). */ silc_mp_gcd(&div, &pm1, &qm1); - silc_mp_fdiv_q(&lcm, &phi, &div); + silc_mp_div(&lcm, &phi, &div); silc_mp_modinv(&key->d, &key->e, &lcm); - - silc_mp_clear(&phi); - silc_mp_clear(&hlp); - silc_mp_clear(&div); - silc_mp_clear(&lcm); - silc_mp_clear(&pm1); - silc_mp_clear(&qm1); + + /* Optimize d with CRT. We precompute as much as possible. */ + silc_mp_mod(&key->dP, &key->d, &pm1); + silc_mp_mod(&key->dQ, &key->d, &qm1); + silc_mp_modinv(&key->pQ, p, q); + silc_mp_mul(&key->pQ, p, &key->pQ); + silc_mp_mod(&key->pQ, &key->pQ, &key->n); + silc_mp_modinv(&key->qP, q, p); + silc_mp_mul(&key->qP, q, &key->qP); + silc_mp_mod(&key->qP, &key->qP, &key->n); + silc_mp_set(&key->p, p); + silc_mp_set(&key->q, q); + key->crt = TRUE; + + silc_mp_uninit(&phi); + silc_mp_uninit(&hlp); + silc_mp_uninit(&div); + silc_mp_uninit(&lcm); + silc_mp_uninit(&pm1); + silc_mp_uninit(&qm1); + + return TRUE; } /* Clears whole key structure. */ -void rsa_clear_keys(RsaKey *key) +SilcBool rsa_clear_keys(RsaKey *key) { key->bits = 0; - silc_mp_clear(&key->p); - silc_mp_clear(&key->q); - silc_mp_clear(&key->n); - silc_mp_clear(&key->e); - silc_mp_clear(&key->d); + if (key->pub_set) { + silc_mp_uninit(&key->n); + silc_mp_uninit(&key->e); + } + if (key->prv_set) + silc_mp_uninit(&key->d); + if (key->prv_set && key->crt) { + silc_mp_uninit(&key->dP); + silc_mp_uninit(&key->dQ); + silc_mp_uninit(&key->pQ); + silc_mp_uninit(&key->qP); + silc_mp_uninit(&key->p); + silc_mp_uninit(&key->q); + } + return TRUE; } -/* RSA encrypt/decrypt function. cm = ciphertext or plaintext, - mc = plaintext or ciphertext, expo = public or private exponent, - and modu = modulus. +/* RSA public key operation */ - Encrypt: c = m ^ e mod n, - Decrypt: m = c ^ d mod n -*/ +SilcBool rsa_public_operation(RsaKey *key, SilcMPInt *src, SilcMPInt *dst) +{ + /* dst = src ^ e mod n */ + silc_mp_pow_mod(dst, src, &key->e, &key->n); + return TRUE; +} + +/* RSA private key operation */ -void rsa_en_de_crypt(SilcInt *cm, SilcInt *mc, - SilcInt *expo, SilcInt *modu) +SilcBool rsa_private_operation(RsaKey *key, SilcMPInt *src, SilcMPInt *dst) { - silc_mp_powm(cm, mc, expo, modu); + if (!key->crt) { + /* dst = src ^ d mod n */ + silc_mp_pow_mod(dst, src, &key->d, &key->n); + } else { + /* CRT */ + SilcMPInt tmp; + + silc_mp_init(&tmp); + + /* dst = ((src ^ dP mod p) * qP) + ((src ^ dQ mod q) * pQ) mod n */ + silc_mp_pow_mod(dst, src, &key->dP, &key->p); + silc_mp_mul(dst, dst, &key->qP); + silc_mp_pow_mod(&tmp, src, &key->dQ, &key->q); + silc_mp_mul(&tmp, &tmp, &key->pQ); + silc_mp_add(dst, dst, &tmp); + silc_mp_mod(dst, dst, &key->n); + + silc_mp_uninit(&tmp); + } + + return TRUE; }