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;
242 silc_mp_init(&key->e);
243 silc_mp_init(&key->n);
245 memcpy(tmp, key_data, 4);
246 SILC_GET32_MSB(e_len, tmp);
247 if (!e_len || e_len + 4 > key_len) {
248 silc_mp_uninit(&key->e);
249 silc_mp_uninit(&key->n);
253 silc_mp_bin2mp(key_data + 4, e_len, &key->e);
255 if (key_len < 4 + e_len + 4) {
256 silc_mp_uninit(&key->e);
257 silc_mp_uninit(&key->n);
261 memcpy(tmp, key_data + 4 + e_len, 4);
262 SILC_GET32_MSB(n_len, tmp);
263 if (!n_len || e_len + 4 + n_len + 4 > key_len) {
264 silc_mp_uninit(&key->e);
265 silc_mp_uninit(&key->n);
269 silc_mp_bin2mp(key_data + 4 + e_len + 4, n_len, &key->n);
271 key->bits = silc_mp_sizeinbase(&key->n, 2);
277 /* Set private key. This derives the public key from the private
278 key and sets the public key as well. Public key should not be set
279 already and should not be set after setting private key. */
281 SILC_PKCS_API_SET_PRIVATE_KEY(rsa)
283 RsaKey *key = (RsaKey *)context;
284 unsigned char tmp[4];
285 SilcUInt32 e_len, n_len, d_len;
288 silc_mp_uninit(&key->d);
289 key->prv_set = FALSE;
293 silc_mp_uninit(&key->e);
294 silc_mp_uninit(&key->n);
295 key->pub_set = FALSE;
301 silc_mp_init(&key->e);
302 silc_mp_init(&key->n);
303 silc_mp_init(&key->d);
305 memcpy(tmp, key_data, 4);
306 SILC_GET32_MSB(e_len, tmp);
307 if (e_len + 4 > key_len) {
308 silc_mp_uninit(&key->e);
309 silc_mp_uninit(&key->n);
310 silc_mp_uninit(&key->d);
314 silc_mp_bin2mp(key_data + 4, e_len, &key->e);
316 if (key_len < e_len + 4 + 4) {
317 silc_mp_uninit(&key->e);
318 silc_mp_uninit(&key->n);
319 silc_mp_uninit(&key->d);
323 memcpy(tmp, key_data + 4 + e_len, 4);
324 SILC_GET32_MSB(n_len, tmp);
325 if (e_len + 4 + n_len + 4 > key_len) {
326 silc_mp_uninit(&key->e);
327 silc_mp_uninit(&key->n);
328 silc_mp_uninit(&key->d);
332 silc_mp_bin2mp(key_data + 4 + e_len + 4, n_len, &key->n);
334 if (key_len < e_len + 4 + n_len + 4 + 4) {
335 silc_mp_uninit(&key->e);
336 silc_mp_uninit(&key->n);
337 silc_mp_uninit(&key->d);
341 memcpy(tmp, key_data + 4 + e_len + 4 + n_len, 4);
342 SILC_GET32_MSB(d_len, tmp);
343 if (e_len + 4 + n_len + 4 + d_len + 4 > key_len) {
344 silc_mp_uninit(&key->e);
345 silc_mp_uninit(&key->n);
346 silc_mp_uninit(&key->d);
350 silc_mp_bin2mp(key_data + 4 + e_len + 4 + n_len + 4, d_len, &key->d);
352 key->bits = silc_mp_sizeinbase(&key->n, 2);
359 SILC_PKCS_API_CONTEXT_LEN(rsa)
361 return sizeof(RsaKey);
364 SILC_PKCS_API_ENCRYPT(rsa)
366 RsaKey *key = (RsaKey *)context;
371 silc_mp_init(&mp_tmp);
372 silc_mp_init(&mp_dst);
374 /* Format the data into MP int */
375 silc_mp_bin2mp(src, src_len, &mp_tmp);
378 rsa_en_de_crypt(&mp_dst, &mp_tmp, &key->e, &key->n);
380 tmplen = (key->bits + 7) / 8;
382 /* Format the MP int back into data */
383 silc_mp_mp2bin_noalloc(&mp_dst, dst, tmplen);
386 silc_mp_uninit(&mp_tmp);
387 silc_mp_uninit(&mp_dst);
392 SILC_PKCS_API_DECRYPT(rsa)
394 RsaKey *key = (RsaKey *)context;
399 silc_mp_init(&mp_tmp);
400 silc_mp_init(&mp_dst);
402 /* Format the data into MP int */
403 silc_mp_bin2mp(src, src_len, &mp_tmp);
406 rsa_en_de_crypt(&mp_dst, &mp_tmp, &key->d, &key->n);
408 tmplen = (key->bits + 7) / 8;
410 /* Format the MP int back into data */
411 silc_mp_mp2bin_noalloc(&mp_dst, dst, tmplen);
414 silc_mp_uninit(&mp_tmp);
415 silc_mp_uninit(&mp_dst);
420 SILC_PKCS_API_SIGN(rsa)
422 RsaKey *key = (RsaKey *)context;
427 silc_mp_init(&mp_tmp);
428 silc_mp_init(&mp_dst);
430 /* Format the data into MP int */
431 silc_mp_bin2mp(src, src_len, &mp_tmp);
434 rsa_en_de_crypt(&mp_dst, &mp_tmp, &key->d, &key->n);
436 tmplen = (key->bits + 7) / 8;
438 /* Format the MP int back into data */
439 silc_mp_mp2bin_noalloc(&mp_dst, dst, tmplen);
442 silc_mp_uninit(&mp_tmp);
443 silc_mp_uninit(&mp_dst);
448 SILC_PKCS_API_VERIFY(rsa)
450 RsaKey *key = (RsaKey *)context;
452 SilcMPInt mp_tmp, mp_tmp2;
455 silc_mp_init(&mp_tmp);
456 silc_mp_init(&mp_tmp2);
457 silc_mp_init(&mp_dst);
459 /* Format the signature into MP int */
460 silc_mp_bin2mp(signature, signature_len, &mp_tmp2);
463 rsa_en_de_crypt(&mp_dst, &mp_tmp2, &key->e, &key->n);
465 /* Format the data into MP int */
466 silc_mp_bin2mp(data, data_len, &mp_tmp);
471 if ((silc_mp_cmp(&mp_tmp, &mp_dst)) != 0)
474 silc_mp_uninit(&mp_tmp);
475 silc_mp_uninit(&mp_tmp2);
476 silc_mp_uninit(&mp_dst);
481 /* Generates RSA public and private keys. Primes p and q that are used
482 to compute the modulus n has to be generated before calling this. They
483 are then sent as argument for the function. */
485 void rsa_generate_keys(RsaKey *key, SilcUInt32 bits,
486 SilcMPInt *p, SilcMPInt *q)
492 /* Initialize variables */
493 silc_mp_init(&key->n);
494 silc_mp_init(&key->e);
495 silc_mp_init(&key->d);
503 /* Set modulus length */
506 /* Compute modulus, n = p * q */
507 silc_mp_mul(&key->n, p, q);
509 /* phi = (p - 1) * (q - 1) */
510 silc_mp_sub_ui(&pm1, p, 1);
511 silc_mp_sub_ui(&qm1, q, 1);
512 silc_mp_mul(&phi, &pm1, &qm1);
514 /* Set e, the public exponent. We try to use same public exponent
515 for all keys. Also, to make encryption faster we use small
517 silc_mp_set_ui(&key->e, 65533);
519 /* See if e is relatively prime to phi. gcd == greates common divisor,
520 if gcd equals 1 they are relatively prime. */
521 silc_mp_gcd(&hlp, &key->e, &phi);
522 if((silc_mp_cmp_ui(&hlp, 1)) > 0) {
523 silc_mp_add_ui(&key->e, &key->e, 2);
527 /* Find d, the private exponent, e ^ -1 mod lcm(phi). */
528 silc_mp_gcd(&div, &pm1, &qm1);
529 silc_mp_div(&lcm, &phi, &div);
530 silc_mp_modinv(&key->d, &key->e, &lcm);
532 silc_mp_uninit(&phi);
533 silc_mp_uninit(&hlp);
534 silc_mp_uninit(&div);
535 silc_mp_uninit(&lcm);
536 silc_mp_uninit(&pm1);
537 silc_mp_uninit(&qm1);
540 /* Clears whole key structure. */
542 void rsa_clear_keys(RsaKey *key)
546 silc_mp_uninit(&key->n);
547 silc_mp_uninit(&key->e);
550 silc_mp_uninit(&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(SilcMPInt *cm, SilcMPInt *mc,
562 SilcMPInt *expo, SilcMPInt *modu)
564 silc_mp_pow_mod(cm, mc, expo, modu);