2 * rsa.c RSA Public and Private key generation functions,
3 * RSA encrypt and decrypt functions.
5 * Author: Pekka Riikonen <priikone@poseidon.pspt.fi>
7 * Copyright (C) 1997 - 2001 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 * This code is based on SSH's (Secure Shell), PGP's (Pretty Good Privacy)
39 * and RSAREF Toolkit's RSA source codes. They all were a big help for me.
41 * I also suggest reading Bruce Schneier's; Applied Cryptography, Second
42 * Edition, John Wiley & Sons, Inc. 1996. This book deals about RSA and
43 * everything else too about cryptography.
51 o Mon Feb 12 11:20:32 EET 2001 Pekka
53 Changed RSA private exponent generation to what PKCS #1 suggests. We
54 try to find the smallest possible d by doing modinv(e, lcm(phi)) instead
55 of modinv(e, phi). Note: this is not security fix but optimization.
57 o Tue Feb 20 13:58:58 EET 2001 Pekka
59 Set key->bits in rsa_generate_key. It is the modulus length in bits.
60 The `tmplen' in encrypt, decrypt, sign and verify PKCS API functions
61 is now calculated by (key->bits + 7) / 8. It is the length of one block.
65 #include "silcincludes.h"
69 * SILC PKCS API for RSA
72 /* Generates RSA key pair. */
74 SILC_PKCS_API_INIT(rsa)
76 unsigned int prime_bits = keylen / 2;
79 printf("Generating RSA Public and Private keys, might take a while...\n");
86 printf("Finding p: ");
87 silc_math_gen_prime(&p, prime_bits, TRUE);
89 printf("\nFinding q: ");
90 silc_math_gen_prime(&q, prime_bits, TRUE);
92 if ((silc_mp_cmp(&p, &q)) == 0) {
93 printf("\nFound equal primes, not good, retrying...\n");
97 /* If p is smaller than q, switch them */
98 if ((silc_mp_cmp(&p, &q)) > 0) {
102 silc_mp_set(&hlp, &p);
104 silc_mp_set(&q, &hlp);
109 /* Generate the actual keys */
110 rsa_generate_keys((RsaKey *)context, keylen, &p, &q);
115 printf("\nKeys generated succesfully.\n");
120 SILC_PKCS_API_CLEAR_KEYS(rsa)
122 rsa_clear_keys((RsaKey *)context);
125 /* Returns SILC style encoded RSA public key. */
127 SILC_PKCS_API_GET_PUBLIC_KEY(rsa)
129 RsaKey *key = (RsaKey *)context;
130 unsigned char *e, *n, *ret;
131 unsigned int e_len, n_len;
132 unsigned char tmp[4];
134 e = silc_mp_mp2bin(&key->e, 0, &e_len);
135 n = silc_mp_mp2bin(&key->n, key->bits / 8, &n_len);
137 *ret_len = e_len + 4 + n_len + 4;
138 ret = silc_calloc(*ret_len, sizeof(unsigned char));
140 /* Put the length of the e. */
141 SILC_PUT32_MSB(e_len, tmp);
145 memcpy(ret + 4, e, e_len);
147 /* Put the length of the n. */
148 SILC_PUT32_MSB(n_len, tmp);
149 memcpy(ret + 4 + e_len, tmp, 4);
152 memcpy(ret + 4 + e_len + 4, n, n_len);
162 /* Returns SILC style encoded RSA private key. Public key is always
163 returned in private key as well. Public keys are often derived
164 directly from private key. */
166 SILC_PKCS_API_GET_PRIVATE_KEY(rsa)
168 RsaKey *key = (RsaKey *)context;
169 unsigned char *e, *n, *d, *ret;
170 unsigned int e_len, n_len, d_len;
171 unsigned char tmp[4];
173 e = silc_mp_mp2bin(&key->e, 0, &e_len);
174 n = silc_mp_mp2bin(&key->n, key->bits / 8, &n_len);
175 d = silc_mp_mp2bin(&key->d, 0, &d_len);
177 *ret_len = e_len + 4 + n_len + 4 + d_len + 4;
178 ret = silc_calloc(*ret_len, sizeof(unsigned char));
180 /* Put the length of the e. */
181 SILC_PUT32_MSB(e_len, tmp);
185 memcpy(ret + 4, e, e_len);
187 /* Put the length of the n. */
188 SILC_PUT32_MSB(n_len, tmp);
189 memcpy(ret + 4 + e_len, tmp, 4);
192 memcpy(ret + 4 + e_len + 4, n, n_len);
194 /* Put the length of the d. */
195 SILC_PUT32_MSB(d_len, tmp);
196 memcpy(ret + 4 + e_len + 4 + n_len, tmp, 4);
199 memcpy(ret + 4 + e_len + 4 + n_len + 4, d, d_len);
213 SILC_PKCS_API_SET_PUBLIC_KEY(rsa)
215 RsaKey *key = (RsaKey *)context;
216 unsigned char tmp[4];
217 unsigned int e_len, n_len;
219 silc_mp_init(&key->e);
220 silc_mp_init(&key->n);
222 memcpy(tmp, key_data, 4);
223 SILC_GET32_MSB(e_len, tmp);
224 if (e_len > key_len) {
225 silc_mp_clear(&key->e);
226 silc_mp_clear(&key->n);
230 silc_mp_bin2mp(key_data + 4, e_len, &key->e);
232 memcpy(tmp, key_data + 4 + e_len, 4);
233 SILC_GET32_MSB(n_len, tmp);
234 if (e_len + n_len > key_len) {
235 silc_mp_clear(&key->e);
236 silc_mp_clear(&key->n);
240 silc_mp_bin2mp(key_data + 4 + e_len + 4, n_len, &key->n);
242 key->bits = n_len * 8;
247 /* Set private key. This derives the public key from the private
248 key and sets the public key as well. Public key should not be set
249 already and should not be set after setting private key. */
251 SILC_PKCS_API_SET_PRIVATE_KEY(rsa)
253 RsaKey *key = (RsaKey *)context;
254 unsigned char tmp[4];
255 unsigned int e_len, n_len, d_len;
257 silc_mp_init(&key->e);
258 silc_mp_init(&key->n);
259 silc_mp_init(&key->d);
261 memcpy(tmp, key_data, 4);
262 SILC_GET32_MSB(e_len, tmp);
263 if (e_len > key_len) {
264 silc_mp_clear(&key->e);
265 silc_mp_clear(&key->n);
269 silc_mp_bin2mp(key_data + 4, e_len, &key->e);
271 memcpy(tmp, key_data + 4 + e_len, 4);
272 SILC_GET32_MSB(n_len, tmp);
273 if (e_len + n_len > key_len) {
274 silc_mp_clear(&key->e);
275 silc_mp_clear(&key->n);
279 silc_mp_bin2mp(key_data + 4 + e_len + 4, n_len, &key->n);
281 memcpy(tmp, key_data + 4 + e_len + 4 + n_len, 4);
282 SILC_GET32_MSB(d_len, tmp);
283 if (e_len + n_len + d_len > key_len) {
284 silc_mp_clear(&key->e);
285 silc_mp_clear(&key->n);
289 silc_mp_bin2mp(key_data + 4 + e_len + 4 + n_len + 4, d_len, &key->d);
291 key->bits = n_len * 8;
296 SILC_PKCS_API_CONTEXT_LEN(rsa)
298 return sizeof(RsaKey);
301 SILC_PKCS_API_DATA_CONTEXT_LEN(rsa)
303 return sizeof(RsaDataContext);
306 SILC_PKCS_API_SET_ARG(rsa)
308 RsaDataContext *data_ctx = (RsaDataContext *)data_context;
335 SILC_PKCS_API_ENCRYPT(rsa)
337 RsaKey *key = (RsaKey *)context;
342 silc_mp_init_set_ui(&mp_tmp, 0);
343 silc_mp_init_set_ui(&mp_dst, 0);
345 /* Format the data into MP int */
346 for (i = 0; i < src_len; i++) {
347 silc_mp_mul_2exp(&mp_tmp, &mp_tmp, 8);
348 silc_mp_add_ui(&mp_tmp, &mp_tmp, src[i]);
352 rsa_en_de_crypt(&mp_dst, &mp_tmp, &key->e, &key->n);
354 tmplen = (key->bits + 7) / 8;
356 /* Format the MP int back into data */
357 for (i = tmplen; i > 0; i--) {
358 dst[i - 1] = (unsigned char)(silc_mp_get_ui(&mp_dst) & 0xff);
359 silc_mp_fdiv_q_2exp(&mp_dst, &mp_dst, 8);
363 silc_mp_clear(&mp_tmp);
364 silc_mp_clear(&mp_dst);
369 SILC_PKCS_API_DECRYPT(rsa)
371 RsaKey *key = (RsaKey *)context;
376 silc_mp_init_set_ui(&mp_tmp, 0);
377 silc_mp_init_set_ui(&mp_dst, 0);
379 /* Format the data into MP int */
380 for (i = 0; i < src_len; i++) {
381 silc_mp_mul_2exp(&mp_tmp, &mp_tmp, 8);
382 silc_mp_add_ui(&mp_tmp, &mp_tmp, src[i]);
386 rsa_en_de_crypt(&mp_dst, &mp_tmp, &key->d, &key->n);
388 tmplen = (key->bits + 7) / 8;
390 /* Format the MP int back into data */
391 for (i = tmplen; i > 0; i--) {
392 dst[i - 1] = (unsigned char)(silc_mp_get_ui(&mp_dst) & 0xff);
393 silc_mp_fdiv_q_2exp(&mp_dst, &mp_dst, 8);
397 silc_mp_clear(&mp_tmp);
398 silc_mp_clear(&mp_dst);
403 SILC_PKCS_API_SIGN(rsa)
405 RsaKey *key = (RsaKey *)context;
410 silc_mp_init_set_ui(&mp_tmp, 0);
411 silc_mp_init_set_ui(&mp_dst, 0);
413 /* Format the data into MP int */
414 for (i = 0; i < src_len; i++) {
415 silc_mp_mul_2exp(&mp_tmp, &mp_tmp, 8);
416 silc_mp_add_ui(&mp_tmp, &mp_tmp, src[i]);
420 rsa_en_de_crypt(&mp_dst, &mp_tmp, &key->d, &key->n);
422 tmplen = (key->bits + 7) / 8;
424 /* Format the MP int back into data */
425 for (i = tmplen; i > 0; i--) {
426 dst[i - 1] = (unsigned char)(silc_mp_get_ui(&mp_dst) & 0xff);
427 silc_mp_fdiv_q_2exp(&mp_dst, &mp_dst, 8);
431 silc_mp_clear(&mp_tmp);
432 silc_mp_clear(&mp_dst);
437 SILC_PKCS_API_VERIFY(rsa)
439 RsaKey *key = (RsaKey *)context;
441 SilcInt mp_tmp, mp_tmp2;
444 silc_mp_init_set_ui(&mp_tmp, 0);
445 silc_mp_init_set_ui(&mp_tmp2, 0);
446 silc_mp_init_set_ui(&mp_dst, 0);
448 /* Format the signature into MP int */
449 for (i = 0; i < signature_len; i++) {
450 silc_mp_mul_2exp(&mp_tmp2, &mp_tmp2, 8);
451 silc_mp_add_ui(&mp_tmp2, &mp_tmp2, signature[i]);
455 rsa_en_de_crypt(&mp_dst, &mp_tmp2, &key->e, &key->n);
457 /* Format the data into MP int */
458 for (i = 0; i < data_len; i++) {
459 silc_mp_mul_2exp(&mp_tmp, &mp_tmp, 8);
460 silc_mp_add_ui(&mp_tmp, &mp_tmp, data[i]);
466 if ((silc_mp_cmp(&mp_tmp, &mp_dst)) != 0)
469 silc_mp_clear(&mp_tmp);
470 silc_mp_clear(&mp_tmp2);
471 silc_mp_clear(&mp_dst);
476 /* Generates RSA public and private keys. Primes p and q that are used
477 to compute the modulus n has to be generated before calling this. They
478 are then sent as argument for the function. */
480 void rsa_generate_keys(RsaKey *key, unsigned int bits,
481 SilcInt *p, SilcInt *q)
487 /* Initialize variables */
488 silc_mp_init(&key->p);
489 silc_mp_init(&key->q);
490 silc_mp_init(&key->n);
491 silc_mp_init(&key->e);
492 silc_mp_init(&key->d);
500 /* Set modulus length */
504 silc_mp_set(&key->p, p);
505 silc_mp_set(&key->q, q);
507 /* Compute modulus, n = p * q */
508 silc_mp_mul(&key->n, &key->p, &key->q);
510 /* phi = (p - 1) * (q - 1) */
511 silc_mp_sub_ui(&pm1, &key->p, 1);
512 silc_mp_sub_ui(&qm1, &key->q, 1);
513 silc_mp_mul(&phi, &pm1, &qm1);
515 /* Set e, the public exponent. We try to use same public exponent
516 for all keys. Also, to make encryption faster we use small
518 silc_mp_set_ui(&key->e, 127);
520 /* See if e is relatively prime to phi. gcd == greates common divisor,
521 if gcd equals 1 they are relatively prime. */
522 silc_mp_gcd(&hlp, &key->e, &phi);
523 if((silc_mp_cmp_ui(&hlp, 1)) > 0) {
524 silc_mp_add_ui(&key->e, &key->e, 2);
528 /* Find d, the private exponent. */
529 silc_mp_gcd(&div, &pm1, &qm1);
530 silc_mp_fdiv_q(&lcm, &phi, &div);
531 silc_mp_modinv(&key->d, &key->e, &lcm);
541 /* Clears whole key structure. */
543 void rsa_clear_keys(RsaKey *key)
546 silc_mp_clear(&key->p);
547 silc_mp_clear(&key->q);
548 silc_mp_clear(&key->n);
549 silc_mp_clear(&key->e);
550 silc_mp_clear(&key->d);
553 /* RSA encrypt/decrypt function. cm = ciphertext or plaintext,
554 mc = plaintext or ciphertext, expo = public or private exponent,
557 Encrypt: c = m ^ e mod n,
558 Decrypt: m = c ^ d mod n
561 void rsa_en_de_crypt(SilcInt *cm, SilcInt *mc,
562 SilcInt *expo, SilcInt *modu)
564 silc_mp_powm(cm, mc, expo, modu);