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 * The SSH's (Secure Shell), PGP's (Pretty Good Privacy) and RSAREF
39 * Toolkit were used as reference when coding this implementation. They
40 * all were a big help for me.
42 * I also suggest reading Bruce Schneier's; Applied Cryptography, Second
43 * Edition, John Wiley & Sons, Inc. 1996. This book deals about RSA and
44 * everything else too about cryptography.
52 o Mon Feb 12 11:20:32 EET 2001 Pekka
54 Changed RSA private exponent generation to what PKCS #1 suggests. We
55 try to find the smallest possible d by doing modinv(e, lcm(phi)) instead
56 of modinv(e, phi). Note: this is not security fix but optimization.
58 o Tue Feb 20 13:58:58 EET 2001 Pekka
60 Set key->bits in rsa_generate_key. It is the modulus length in bits.
61 The `tmplen' in encrypt, decrypt, sign and verify PKCS API functions
62 is now calculated by (key->bits + 7) / 8. It is the length of one block.
64 o Sat Mar 16 18:27:19 EET 2002 Pekka
66 Use the SilcRng sent as argument to SILC_PKCS_API_INIT in prime
69 o Sat Sep 26 19:59:48 EEST 2002 Pekka
71 Fixed double free in public key setting. Use a bit larger e as
72 starting point in key generation.
76 #include "silcincludes.h"
77 #include "rsa_internal.h"
81 * SILC PKCS API for RSA
84 /* Generates RSA key pair. */
86 SILC_PKCS_API_INIT(rsa)
88 SilcUInt32 prime_bits = keylen / 2;
92 printf("Generating RSA Public and Private keys, might take a while...\n");
99 printf("Finding p: ");
100 silc_math_gen_prime(&p, prime_bits, TRUE, rng);
102 printf("\nFinding q: ");
103 silc_math_gen_prime(&q, prime_bits, TRUE, rng);
105 if ((silc_mp_cmp(&p, &q)) == 0)
106 printf("\nFound equal primes, not good, retrying...\n");
111 /* If p is smaller than q, switch them */
112 if ((silc_mp_cmp(&p, &q)) > 0) {
116 silc_mp_set(&hlp, &p);
118 silc_mp_set(&q, &hlp);
120 silc_mp_uninit(&hlp);
123 /* Generate the actual keys */
124 rsa_generate_keys((RsaKey *)context, keylen, &p, &q);
129 printf("\nKeys generated successfully.\n");
134 SILC_PKCS_API_CLEAR_KEYS(rsa)
136 rsa_clear_keys((RsaKey *)context);
139 /* Returns SILC style encoded RSA public key. */
141 SILC_PKCS_API_GET_PUBLIC_KEY(rsa)
143 RsaKey *key = (RsaKey *)context;
144 unsigned char *e, *n, *ret;
145 SilcUInt32 e_len, n_len;
146 unsigned char tmp[4];
148 e = silc_mp_mp2bin(&key->e, 0, &e_len);
149 n = silc_mp_mp2bin(&key->n, key->bits / 8, &n_len);
151 *ret_len = e_len + 4 + n_len + 4;
152 ret = silc_calloc(*ret_len, sizeof(unsigned char));
154 /* Put the length of the e. */
155 SILC_PUT32_MSB(e_len, tmp);
159 memcpy(ret + 4, e, e_len);
161 /* Put the length of the n. */
162 SILC_PUT32_MSB(n_len, tmp);
163 memcpy(ret + 4 + e_len, tmp, 4);
166 memcpy(ret + 4 + e_len + 4, n, n_len);
176 /* Returns SILC style encoded RSA private key. Public key is always
177 returned in private key as well. Public keys are often derived
178 directly from private key. */
180 SILC_PKCS_API_GET_PRIVATE_KEY(rsa)
182 RsaKey *key = (RsaKey *)context;
183 unsigned char *e, *n, *d, *ret;
184 SilcUInt32 e_len, n_len, d_len;
185 unsigned char tmp[4];
187 e = silc_mp_mp2bin(&key->e, 0, &e_len);
188 n = silc_mp_mp2bin(&key->n, key->bits / 8, &n_len);
189 d = silc_mp_mp2bin(&key->d, 0, &d_len);
191 *ret_len = e_len + 4 + n_len + 4 + d_len + 4;
192 ret = silc_calloc(*ret_len, sizeof(unsigned char));
194 /* Put the length of the e. */
195 SILC_PUT32_MSB(e_len, tmp);
199 memcpy(ret + 4, e, e_len);
201 /* Put the length of the n. */
202 SILC_PUT32_MSB(n_len, tmp);
203 memcpy(ret + 4 + e_len, tmp, 4);
206 memcpy(ret + 4 + e_len + 4, n, n_len);
208 /* Put the length of the d. */
209 SILC_PUT32_MSB(d_len, tmp);
210 memcpy(ret + 4 + e_len + 4 + n_len, tmp, 4);
213 memcpy(ret + 4 + e_len + 4 + n_len + 4, d, d_len);
227 SILC_PKCS_API_SET_PUBLIC_KEY(rsa)
229 RsaKey *key = (RsaKey *)context;
230 unsigned char tmp[4];
231 SilcUInt32 e_len, n_len;
234 silc_mp_uninit(&key->e);
235 silc_mp_uninit(&key->n);
236 key->pub_set = FALSE;
239 silc_mp_init(&key->e);
240 silc_mp_init(&key->n);
242 memcpy(tmp, key_data, 4);
243 SILC_GET32_MSB(e_len, tmp);
244 if (e_len > key_len) {
245 silc_mp_uninit(&key->e);
246 silc_mp_uninit(&key->n);
250 silc_mp_bin2mp(key_data + 4, e_len, &key->e);
252 memcpy(tmp, key_data + 4 + e_len, 4);
253 SILC_GET32_MSB(n_len, tmp);
254 if (e_len + n_len > key_len) {
255 silc_mp_uninit(&key->e);
256 silc_mp_uninit(&key->n);
260 silc_mp_bin2mp(key_data + 4 + e_len + 4, n_len, &key->n);
262 key->bits = n_len * 8;
268 /* Set private key. This derives the public key from the private
269 key and sets the public key as well. Public key should not be set
270 already and should not be set after setting private key. */
272 SILC_PKCS_API_SET_PRIVATE_KEY(rsa)
274 RsaKey *key = (RsaKey *)context;
275 unsigned char tmp[4];
276 SilcUInt32 e_len, n_len, d_len;
279 silc_mp_uninit(&key->d);
280 key->prv_set = FALSE;
284 silc_mp_uninit(&key->e);
285 silc_mp_uninit(&key->n);
286 key->pub_set = FALSE;
289 silc_mp_init(&key->e);
290 silc_mp_init(&key->n);
291 silc_mp_init(&key->d);
293 memcpy(tmp, key_data, 4);
294 SILC_GET32_MSB(e_len, tmp);
295 if (e_len > key_len) {
296 silc_mp_uninit(&key->e);
297 silc_mp_uninit(&key->n);
298 silc_mp_uninit(&key->d);
302 silc_mp_bin2mp(key_data + 4, e_len, &key->e);
304 memcpy(tmp, key_data + 4 + e_len, 4);
305 SILC_GET32_MSB(n_len, tmp);
306 if (e_len + n_len > key_len) {
307 silc_mp_uninit(&key->e);
308 silc_mp_uninit(&key->n);
309 silc_mp_uninit(&key->d);
313 silc_mp_bin2mp(key_data + 4 + e_len + 4, n_len, &key->n);
315 memcpy(tmp, key_data + 4 + e_len + 4 + n_len, 4);
316 SILC_GET32_MSB(d_len, tmp);
317 if (e_len + n_len + d_len > key_len) {
318 silc_mp_uninit(&key->e);
319 silc_mp_uninit(&key->n);
320 silc_mp_uninit(&key->d);
324 silc_mp_bin2mp(key_data + 4 + e_len + 4 + n_len + 4, d_len, &key->d);
326 key->bits = n_len * 8;
333 SILC_PKCS_API_CONTEXT_LEN(rsa)
335 return sizeof(RsaKey);
338 SILC_PKCS_API_ENCRYPT(rsa)
340 RsaKey *key = (RsaKey *)context;
345 silc_mp_init(&mp_tmp);
346 silc_mp_init(&mp_dst);
347 silc_mp_set_ui(&mp_tmp, 0);
348 silc_mp_set_ui(&mp_dst, 0);
350 /* Format the data into MP int */
351 for (i = 0; i < src_len; i++) {
352 silc_mp_mul_2exp(&mp_tmp, &mp_tmp, 8);
353 silc_mp_add_ui(&mp_tmp, &mp_tmp, src[i]);
357 rsa_en_de_crypt(&mp_dst, &mp_tmp, &key->e, &key->n);
359 tmplen = (key->bits + 7) / 8;
361 /* Format the MP int back into data */
362 for (i = tmplen; i > 0; i--) {
363 dst[i - 1] = (unsigned char)(silc_mp_get_ui(&mp_dst) & 0xff);
364 silc_mp_div_2exp(&mp_dst, &mp_dst, 8);
368 silc_mp_uninit(&mp_tmp);
369 silc_mp_uninit(&mp_dst);
374 SILC_PKCS_API_DECRYPT(rsa)
376 RsaKey *key = (RsaKey *)context;
381 silc_mp_init(&mp_tmp);
382 silc_mp_init(&mp_dst);
383 silc_mp_set_ui(&mp_tmp, 0);
384 silc_mp_set_ui(&mp_dst, 0);
386 /* Format the data into MP int */
387 for (i = 0; i < src_len; i++) {
388 silc_mp_mul_2exp(&mp_tmp, &mp_tmp, 8);
389 silc_mp_add_ui(&mp_tmp, &mp_tmp, src[i]);
393 rsa_en_de_crypt(&mp_dst, &mp_tmp, &key->d, &key->n);
395 tmplen = (key->bits + 7) / 8;
397 /* Format the MP int back into data */
398 for (i = tmplen; i > 0; i--) {
399 dst[i - 1] = (unsigned char)(silc_mp_get_ui(&mp_dst) & 0xff);
400 silc_mp_div_2exp(&mp_dst, &mp_dst, 8);
404 silc_mp_uninit(&mp_tmp);
405 silc_mp_uninit(&mp_dst);
410 SILC_PKCS_API_SIGN(rsa)
412 RsaKey *key = (RsaKey *)context;
417 silc_mp_init(&mp_tmp);
418 silc_mp_init(&mp_dst);
419 silc_mp_set_ui(&mp_tmp, 0);
420 silc_mp_set_ui(&mp_dst, 0);
422 /* Format the data into MP int */
423 for (i = 0; i < src_len; i++) {
424 silc_mp_mul_2exp(&mp_tmp, &mp_tmp, 8);
425 silc_mp_add_ui(&mp_tmp, &mp_tmp, src[i]);
429 rsa_en_de_crypt(&mp_dst, &mp_tmp, &key->d, &key->n);
431 tmplen = (key->bits + 7) / 8;
433 /* Format the MP int back into data */
434 for (i = tmplen; i > 0; i--) {
435 dst[i - 1] = (unsigned char)(silc_mp_get_ui(&mp_dst) & 0xff);
436 silc_mp_div_2exp(&mp_dst, &mp_dst, 8);
440 silc_mp_uninit(&mp_tmp);
441 silc_mp_uninit(&mp_dst);
446 SILC_PKCS_API_VERIFY(rsa)
448 RsaKey *key = (RsaKey *)context;
450 SilcMPInt mp_tmp, mp_tmp2;
453 silc_mp_init(&mp_tmp);
454 silc_mp_init(&mp_tmp2);
455 silc_mp_init(&mp_dst);
456 silc_mp_set_ui(&mp_tmp, 0);
457 silc_mp_set_ui(&mp_tmp2, 0);
458 silc_mp_set_ui(&mp_dst, 0);
460 /* Format the signature into MP int */
461 for (i = 0; i < signature_len; i++) {
462 silc_mp_mul_2exp(&mp_tmp2, &mp_tmp2, 8);
463 silc_mp_add_ui(&mp_tmp2, &mp_tmp2, signature[i]);
467 rsa_en_de_crypt(&mp_dst, &mp_tmp2, &key->e, &key->n);
469 /* Format the data into MP int */
470 for (i = 0; i < data_len; i++) {
471 silc_mp_mul_2exp(&mp_tmp, &mp_tmp, 8);
472 silc_mp_add_ui(&mp_tmp, &mp_tmp, data[i]);
478 if ((silc_mp_cmp(&mp_tmp, &mp_dst)) != 0)
481 silc_mp_uninit(&mp_tmp);
482 silc_mp_uninit(&mp_tmp2);
483 silc_mp_uninit(&mp_dst);
488 /* Generates RSA public and private keys. Primes p and q that are used
489 to compute the modulus n has to be generated before calling this. They
490 are then sent as argument for the function. */
492 void rsa_generate_keys(RsaKey *key, SilcUInt32 bits,
493 SilcMPInt *p, SilcMPInt *q)
499 /* Initialize variables */
500 silc_mp_init(&key->n);
501 silc_mp_init(&key->e);
502 silc_mp_init(&key->d);
510 /* Set modulus length */
513 /* Compute modulus, n = p * q */
514 silc_mp_mul(&key->n, p, q);
516 /* phi = (p - 1) * (q - 1) */
517 silc_mp_sub_ui(&pm1, p, 1);
518 silc_mp_sub_ui(&qm1, q, 1);
519 silc_mp_mul(&phi, &pm1, &qm1);
521 /* Set e, the public exponent. We try to use same public exponent
522 for all keys. Also, to make encryption faster we use small
524 silc_mp_set_ui(&key->e, 65533);
526 /* See if e is relatively prime to phi. gcd == greates common divisor,
527 if gcd equals 1 they are relatively prime. */
528 silc_mp_gcd(&hlp, &key->e, &phi);
529 if((silc_mp_cmp_ui(&hlp, 1)) > 0) {
530 silc_mp_add_ui(&key->e, &key->e, 2);
534 /* Find d, the private exponent, e ^ -1 mod lcm(phi). */
535 silc_mp_gcd(&div, &pm1, &qm1);
536 silc_mp_div(&lcm, &phi, &div);
537 silc_mp_modinv(&key->d, &key->e, &lcm);
539 silc_mp_uninit(&phi);
540 silc_mp_uninit(&hlp);
541 silc_mp_uninit(&div);
542 silc_mp_uninit(&lcm);
543 silc_mp_uninit(&pm1);
544 silc_mp_uninit(&qm1);
547 /* Clears whole key structure. */
549 void rsa_clear_keys(RsaKey *key)
553 silc_mp_uninit(&key->n);
554 silc_mp_uninit(&key->e);
557 silc_mp_uninit(&key->d);
560 /* RSA encrypt/decrypt function. cm = ciphertext or plaintext,
561 mc = plaintext or ciphertext, expo = public or private exponent,
564 Encrypt: c = m ^ e mod n,
565 Decrypt: m = c ^ d mod n
568 void rsa_en_de_crypt(SilcMPInt *cm, SilcMPInt *mc,
569 SilcMPInt *expo, SilcMPInt *modu)
571 silc_mp_pow_mod(cm, mc, expo, modu);