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 + 7) / 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 + 7) / 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 || 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 (!n_len || 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 = silc_mp_sizeinbase(&key->n, 2);
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 = silc_mp_sizeinbase(&key->n, 2);
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);
348 /* Format the data into MP int */
349 silc_mp_bin2mp(src, src_len, &mp_tmp);
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 silc_mp_mp2bin_noalloc(&mp_dst, dst, tmplen);
360 silc_mp_uninit(&mp_tmp);
361 silc_mp_uninit(&mp_dst);
366 SILC_PKCS_API_DECRYPT(rsa)
368 RsaKey *key = (RsaKey *)context;
373 silc_mp_init(&mp_tmp);
374 silc_mp_init(&mp_dst);
376 /* Format the data into MP int */
377 silc_mp_bin2mp(src, src_len, &mp_tmp);
380 rsa_en_de_crypt(&mp_dst, &mp_tmp, &key->d, &key->n);
382 tmplen = (key->bits + 7) / 8;
384 /* Format the MP int back into data */
385 silc_mp_mp2bin_noalloc(&mp_dst, dst, tmplen);
388 silc_mp_uninit(&mp_tmp);
389 silc_mp_uninit(&mp_dst);
394 SILC_PKCS_API_SIGN(rsa)
396 RsaKey *key = (RsaKey *)context;
401 silc_mp_init(&mp_tmp);
402 silc_mp_init(&mp_dst);
404 /* Format the data into MP int */
405 silc_mp_bin2mp(src, src_len, &mp_tmp);
408 rsa_en_de_crypt(&mp_dst, &mp_tmp, &key->d, &key->n);
410 tmplen = (key->bits + 7) / 8;
412 /* Format the MP int back into data */
413 silc_mp_mp2bin_noalloc(&mp_dst, dst, tmplen);
416 silc_mp_uninit(&mp_tmp);
417 silc_mp_uninit(&mp_dst);
422 SILC_PKCS_API_VERIFY(rsa)
424 RsaKey *key = (RsaKey *)context;
426 SilcMPInt mp_tmp, mp_tmp2;
429 silc_mp_init(&mp_tmp);
430 silc_mp_init(&mp_tmp2);
431 silc_mp_init(&mp_dst);
433 /* Format the signature into MP int */
434 silc_mp_bin2mp(signature, signature_len, &mp_tmp2);
437 rsa_en_de_crypt(&mp_dst, &mp_tmp2, &key->e, &key->n);
439 /* Format the data into MP int */
440 silc_mp_bin2mp(data, data_len, &mp_tmp);
445 if ((silc_mp_cmp(&mp_tmp, &mp_dst)) != 0)
448 silc_mp_uninit(&mp_tmp);
449 silc_mp_uninit(&mp_tmp2);
450 silc_mp_uninit(&mp_dst);
455 /* Generates RSA public and private keys. Primes p and q that are used
456 to compute the modulus n has to be generated before calling this. They
457 are then sent as argument for the function. */
459 void rsa_generate_keys(RsaKey *key, SilcUInt32 bits,
460 SilcMPInt *p, SilcMPInt *q)
466 /* Initialize variables */
467 silc_mp_init(&key->n);
468 silc_mp_init(&key->e);
469 silc_mp_init(&key->d);
477 /* Set modulus length */
480 /* Compute modulus, n = p * q */
481 silc_mp_mul(&key->n, p, q);
483 /* phi = (p - 1) * (q - 1) */
484 silc_mp_sub_ui(&pm1, p, 1);
485 silc_mp_sub_ui(&qm1, q, 1);
486 silc_mp_mul(&phi, &pm1, &qm1);
488 /* Set e, the public exponent. We try to use same public exponent
489 for all keys. Also, to make encryption faster we use small
491 silc_mp_set_ui(&key->e, 65533);
493 /* See if e is relatively prime to phi. gcd == greates common divisor,
494 if gcd equals 1 they are relatively prime. */
495 silc_mp_gcd(&hlp, &key->e, &phi);
496 if((silc_mp_cmp_ui(&hlp, 1)) > 0) {
497 silc_mp_add_ui(&key->e, &key->e, 2);
501 /* Find d, the private exponent, e ^ -1 mod lcm(phi). */
502 silc_mp_gcd(&div, &pm1, &qm1);
503 silc_mp_div(&lcm, &phi, &div);
504 silc_mp_modinv(&key->d, &key->e, &lcm);
506 silc_mp_uninit(&phi);
507 silc_mp_uninit(&hlp);
508 silc_mp_uninit(&div);
509 silc_mp_uninit(&lcm);
510 silc_mp_uninit(&pm1);
511 silc_mp_uninit(&qm1);
514 /* Clears whole key structure. */
516 void rsa_clear_keys(RsaKey *key)
520 silc_mp_uninit(&key->n);
521 silc_mp_uninit(&key->e);
524 silc_mp_uninit(&key->d);
527 /* RSA encrypt/decrypt function. cm = ciphertext or plaintext,
528 mc = plaintext or ciphertext, expo = public or private exponent,
531 Encrypt: c = m ^ e mod n,
532 Decrypt: m = c ^ d mod n
535 void rsa_en_de_crypt(SilcMPInt *cm, SilcMPInt *mc,
536 SilcMPInt *expo, SilcMPInt *modu)
538 silc_mp_pow_mod(cm, mc, expo, modu);