*
* Author: Pekka Riikonen <priikone@poseidon.pspt.fi>
*
- * Copyright (C) 1997 - 2000 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
* Public key exponent:
* e relatively prime to (p-1) * (q-1)
* Private key exponent:
- * d = e ^ -1 mod ((p-1) * (q-1))
+ * d = e ^ -1 mod lcm(((p-1) * (q-1)))
*
* Encryption:
* c = m ^ e mod n
* everything else too about cryptography.
*
*/
+/* $Id$ */
+
+/*
+ ChangeLog
+
+ o Mon Feb 12 11:20:32 EET 2001 Pekka
+
+ Changed RSA private exponent generation to what PKCS #1 suggests. We
+ try to find the smallest possible d by doing modinv(e, lcm(phi)) instead
+ of modinv(e, phi). Note: this is not security fix but optimization.
+
+ o Tue Feb 20 13:58:58 EET 2001 Pekka
+
+ Set key->bits in rsa_generate_key. It is the modulus length in bits.
+ 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.
+
+*/
#include "silcincludes.h"
#include "rsa.h"
SILC_PKCS_API_INIT(rsa)
{
- unsigned int prime_bits = keylen / 2;
+ uint32 prime_bits = keylen / 2;
SilcInt p, q;
printf("Generating RSA Public and Private keys, might take a while...\n");
{
RsaKey *key = (RsaKey *)context;
unsigned char *e, *n, *ret;
- unsigned short e_len, n_len;
- unsigned char tmp[2];
+ uint32 e_len, n_len;
+ unsigned char tmp[4];
- e_len = silc_mp_sizeinbase(&key->e, 16);
- n_len = silc_mp_sizeinbase(&key->n, 16);
- e = silc_calloc(e_len + 1, sizeof(unsigned char));
- n = silc_calloc(n_len + 1, sizeof(unsigned char));
- silc_mp_get_str(e, 16, &key->e);
- silc_mp_get_str(n, 16, &key->n);
+ e = silc_mp_mp2bin(&key->e, 0, &e_len);
+ n = silc_mp_mp2bin(&key->n, key->bits / 8, &n_len);
- *ret_len = e_len + 2 + n_len + 2;
+ *ret_len = e_len + 4 + n_len + 4;
ret = silc_calloc(*ret_len, sizeof(unsigned char));
/* Put the length of the e. */
- tmp[0] = e_len >> 8;
- tmp[1] = e_len;
- memcpy(ret, tmp, 2);
+ SILC_PUT32_MSB(e_len, tmp);
+ memcpy(ret, tmp, 4);
/* Put the e. */
- memcpy(ret + 2, e, e_len);
+ memcpy(ret + 4, e, e_len);
/* Put the length of the n. */
- tmp[0] = n_len >> 8;
- tmp[1] = n_len;
- memcpy(ret + 2 + e_len, tmp, 2);
+ SILC_PUT32_MSB(n_len, tmp);
+ memcpy(ret + 4 + e_len, tmp, 4);
/* Put the n. */
- memcpy(ret + 2 + e_len + 2, n, n_len);
+ memcpy(ret + 4 + e_len + 4, n, n_len);
memset(e, 0, e_len);
memset(n, 0, n_len);
{
RsaKey *key = (RsaKey *)context;
unsigned char *e, *n, *d, *ret;
- unsigned short e_len, n_len, d_len;
- unsigned char tmp[2];
-
- e_len = silc_mp_sizeinbase(&key->e, 16);
- n_len = silc_mp_sizeinbase(&key->n, 16);
- d_len = silc_mp_sizeinbase(&key->d, 16);
- e = silc_calloc(e_len + 1, sizeof(unsigned char));
- n = silc_calloc(n_len + 1, sizeof(unsigned char));
- d = silc_calloc(d_len + 1, sizeof(unsigned char));
- silc_mp_get_str(e, 16, &key->e);
- silc_mp_get_str(n, 16, &key->n);
- silc_mp_get_str(d, 16, &key->d);
-
- *ret_len = e_len + 2 + n_len + 2 + d_len + 2;
+ uint32 e_len, n_len, d_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);
+ d = silc_mp_mp2bin(&key->d, 0, &d_len);
+
+ *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. */
- tmp[0] = e_len >> 8;
- tmp[1] = e_len;
- memcpy(ret, tmp, 2);
+ SILC_PUT32_MSB(e_len, tmp);
+ memcpy(ret, tmp, 4);
/* Put the e. */
- memcpy(ret + 2, e, e_len);
+ memcpy(ret + 4, e, e_len);
/* Put the length of the n. */
- tmp[0] = n_len >> 8;
- tmp[1] = n_len;
- memcpy(ret + 2 + e_len, tmp, 2);
+ SILC_PUT32_MSB(n_len, tmp);
+ memcpy(ret + 4 + e_len, tmp, 4);
/* Put the n. */
- memcpy(ret + 2 + e_len + 2, n, n_len);
+ memcpy(ret + 4 + e_len + 4, n, n_len);
/* Put the length of the d. */
- tmp[0] = d_len >> 8;
- tmp[1] = d_len;
- memcpy(ret + 2 + e_len + 2 + n_len, tmp, 2);
+ SILC_PUT32_MSB(d_len, tmp);
+ memcpy(ret + 4 + e_len + 4 + n_len, tmp, 4);
/* Put the n. */
- memcpy(ret + 2 + e_len + 2 + n_len + 2, d, d_len);
+ memcpy(ret + 4 + e_len + 4 + n_len + 4, d, d_len);
memset(e, 0, e_len);
memset(n, 0, n_len);
SILC_PKCS_API_SET_PUBLIC_KEY(rsa)
{
RsaKey *key = (RsaKey *)context;
- unsigned char *e, *n, tmp[2];
- unsigned short e_len, n_len;
+ unsigned char tmp[4];
+ uint32 e_len, n_len;
silc_mp_init(&key->e);
silc_mp_init(&key->n);
- memcpy(tmp, key_data, 2);
- e_len = ((unsigned int)tmp[0] << 8) | ((unsigned int)tmp[1]);
+ 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;
+ return 0;
}
- e = silc_calloc(e_len + 1, sizeof(unsigned char));
- memcpy(e, key_data + 2, e_len);
- silc_mp_set_str(&key->e, e, 16);
+ silc_mp_bin2mp(key_data + 4, e_len, &key->e);
- memcpy(tmp, key_data + 2 + e_len, 2);
- n_len = ((unsigned int)tmp[0] << 8) | ((unsigned int)tmp[1]);
+ memcpy(tmp, key_data + 4 + e_len, 4);
+ SILC_GET32_MSB(n_len, tmp);
if (e_len + n_len > key_len) {
- memset(e, 0, e_len);
- silc_free(e);
silc_mp_clear(&key->e);
silc_mp_clear(&key->n);
- return FALSE;
+ return 0;
}
- n = silc_calloc(n_len + 1, sizeof(unsigned char));
- memcpy(n, key_data + 2 + e_len + 2, n_len);
- silc_mp_set_str(&key->n, n, 16);
+ silc_mp_bin2mp(key_data + 4 + e_len + 4, n_len, &key->n);
- memset(e, 0, e_len);
- memset(n, 0, n_len);
- silc_free(e);
- silc_free(n);
+ key->bits = n_len * 8;
- return TRUE;
+ return key->bits;
}
/* Set private key. This derives the public key from the private
SILC_PKCS_API_SET_PRIVATE_KEY(rsa)
{
RsaKey *key = (RsaKey *)context;
- unsigned char *e, *n, *d, tmp[2];
- unsigned short e_len, n_len, d_len;
+ unsigned char tmp[4];
+ uint32 e_len, n_len, d_len;
silc_mp_init(&key->e);
silc_mp_init(&key->n);
silc_mp_init(&key->d);
- memcpy(tmp, key_data, 2);
- e_len = ((unsigned int)tmp[0] << 8) | ((unsigned int)tmp[1]);
+ 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;
}
- e = silc_calloc(e_len + 1, sizeof(unsigned char));
- memcpy(e, key_data + 2, e_len);
- silc_mp_set_str(&key->e, e, 16);
+ silc_mp_bin2mp(key_data + 4, e_len, &key->e);
- memcpy(tmp, key_data + 2 + e_len, 2);
- n_len = ((unsigned int)tmp[0] << 8) | ((unsigned int)tmp[1]);
+ memcpy(tmp, key_data + 4 + e_len, 4);
+ SILC_GET32_MSB(n_len, tmp);
if (e_len + n_len > key_len) {
- memset(e, 0, e_len);
- silc_free(e);
silc_mp_clear(&key->e);
silc_mp_clear(&key->n);
return FALSE;
}
- n = silc_calloc(n_len + 1, sizeof(unsigned char));
- memcpy(n, key_data + 2 + e_len + 2, n_len);
- silc_mp_set_str(&key->n, n, 16);
+ silc_mp_bin2mp(key_data + 4 + e_len + 4, n_len, &key->n);
- memcpy(tmp, key_data + 2 + e_len + 2 + n_len, 2);
- d_len = ((unsigned int)tmp[0] << 8) | ((unsigned int)tmp[1]);
+ 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) {
- memset(n, 0, n_len);
- silc_free(n);
- memset(e, 0, e_len);
- silc_free(e);
silc_mp_clear(&key->e);
silc_mp_clear(&key->n);
return FALSE;
}
- d = silc_calloc(d_len + 1, sizeof(unsigned char));
- memcpy(d, key_data + 2 + e_len + 2 + n_len + 2, d_len);
- silc_mp_set_str(&key->d, d, 16);
+ silc_mp_bin2mp(key_data + 4 + e_len + 4 + n_len + 4, d_len, &key->d);
- memset(e, 0, e_len);
- memset(n, 0, n_len);
- memset(d, 0, d_len);
- silc_free(e);
- silc_free(n);
- silc_free(d);
+ key->bits = n_len * 8;
return TRUE;
}
return sizeof(RsaKey);
}
-SILC_PKCS_API_DATA_CONTEXT_LEN(rsa)
-{
- return sizeof(RsaDataContext);
-}
-
-SILC_PKCS_API_SET_ARG(rsa)
-{
- RsaDataContext *data_ctx = (RsaDataContext *)data_context;
-
- switch(argnum) {
- case 1:
- data_ctx->src = val;
- return TRUE;
- break;
- case 2:
- data_ctx->dst = val;
- return TRUE;
- break;
- case 3:
- data_ctx->exp = val;
- return TRUE;
- break;
- case 4:
- data_ctx->mod = val;
- return TRUE;
- break;
- default:
- return FALSE;
- break;
- }
-
- return FALSE;
-}
-
SILC_PKCS_API_ENCRYPT(rsa)
{
RsaKey *key = (RsaKey *)context;
silc_mp_add_ui(&mp_tmp, &mp_tmp, src[i]);
}
- silc_mp_out_str(stderr, 16, &mp_tmp);
-
/* Encrypt */
rsa_en_de_crypt(&mp_dst, &mp_tmp, &key->e, &key->n);
- fprintf(stderr, "\n");
- silc_mp_out_str(stderr, 16, &mp_dst);
-
- tmplen = (1024 + 7) / 8;
+ tmplen = (key->bits + 7) / 8;
/* Format the MP int back into data */
for (i = tmplen; i > 0; i--) {
silc_mp_add_ui(&mp_tmp, &mp_tmp, src[i]);
}
- silc_mp_out_str(stderr, 16, &mp_tmp);
-
/* Decrypt */
rsa_en_de_crypt(&mp_dst, &mp_tmp, &key->d, &key->n);
- fprintf(stderr, "\n");
- silc_mp_out_str(stderr, 16, &mp_dst);
-
- tmplen = (1024 + 7) / 8;
+ tmplen = (key->bits + 7) / 8;
/* Format the MP int back into data */
for (i = tmplen; i > 0; i--) {
/* Sign */
rsa_en_de_crypt(&mp_dst, &mp_tmp, &key->d, &key->n);
- tmplen = (1024 + 7) / 8;
+ tmplen = (key->bits + 7) / 8;
/* Format the MP int back into data */
for (i = tmplen; i > 0; i--) {
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, unsigned int bits,
+void rsa_generate_keys(RsaKey *key, uint32 bits,
SilcInt *p, SilcInt *q)
{
SilcInt phi, hlp;
- SilcInt dq;
+ SilcInt div, lcm;
SilcInt pm1, qm1;
/* Initialize variables */
silc_mp_init(&key->d);
silc_mp_init(&phi);
silc_mp_init(&hlp);
- silc_mp_init(&dq);
+ silc_mp_init(&div);
+ silc_mp_init(&lcm);
silc_mp_init(&pm1);
silc_mp_init(&qm1);
+ /* Set modulus length */
+ key->bits = bits;
+
/* Set the primes */
silc_mp_set(&key->p, p);
silc_mp_set(&key->q, q);
goto retry_e;
}
- /* Find d, the private exponent. First we do phi / 2, to get it a
- bit smaller */
- silc_mp_div_ui(&dq, &phi, 2);
- silc_mp_modinv(&key->d, &key->e, &dq);
+ /* Find d, the private exponent. */
+ silc_mp_gcd(&div, &pm1, &qm1);
+ silc_mp_fdiv_q(&lcm, &phi, &div);
+ silc_mp_modinv(&key->d, &key->e, &lcm);
silc_mp_clear(&phi);
silc_mp_clear(&hlp);
- silc_mp_clear(&dq);
+ silc_mp_clear(&div);
+ silc_mp_clear(&lcm);
silc_mp_clear(&pm1);
silc_mp_clear(&qm1);
}