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
71 #include "silcincludes.h"
72 #include "rsa_internal.h"
76 * SILC PKCS API for RSA
79 /* Generates RSA key pair. */
81 SILC_PKCS_API_INIT(rsa)
83 SilcUInt32 prime_bits = keylen / 2;
87 printf("Generating RSA Public and Private keys, might take a while...\n");
94 printf("Finding p: ");
95 silc_math_gen_prime(&p, prime_bits, TRUE, rng);
97 printf("\nFinding q: ");
98 silc_math_gen_prime(&q, prime_bits, TRUE, rng);
100 if ((silc_mp_cmp(&p, &q)) == 0)
101 printf("\nFound equal primes, not good, retrying...\n");
106 /* If p is smaller than q, switch them */
107 if ((silc_mp_cmp(&p, &q)) > 0) {
111 silc_mp_set(&hlp, &p);
113 silc_mp_set(&q, &hlp);
115 silc_mp_uninit(&hlp);
118 /* Generate the actual keys */
119 rsa_generate_keys((RsaKey *)context, keylen, &p, &q);
124 printf("\nKeys generated succesfully.\n");
129 SILC_PKCS_API_CLEAR_KEYS(rsa)
131 rsa_clear_keys((RsaKey *)context);
134 /* Returns SILC style encoded RSA public key. */
136 SILC_PKCS_API_GET_PUBLIC_KEY(rsa)
138 RsaKey *key = (RsaKey *)context;
139 unsigned char *e, *n, *ret;
140 SilcUInt32 e_len, n_len;
141 unsigned char tmp[4];
143 e = silc_mp_mp2bin(&key->e, 0, &e_len);
144 n = silc_mp_mp2bin(&key->n, key->bits / 8, &n_len);
146 *ret_len = e_len + 4 + n_len + 4;
147 ret = silc_calloc(*ret_len, sizeof(unsigned char));
149 /* Put the length of the e. */
150 SILC_PUT32_MSB(e_len, tmp);
154 memcpy(ret + 4, e, e_len);
156 /* Put the length of the n. */
157 SILC_PUT32_MSB(n_len, tmp);
158 memcpy(ret + 4 + e_len, tmp, 4);
161 memcpy(ret + 4 + e_len + 4, n, n_len);
171 /* Returns SILC style encoded RSA private key. Public key is always
172 returned in private key as well. Public keys are often derived
173 directly from private key. */
175 SILC_PKCS_API_GET_PRIVATE_KEY(rsa)
177 RsaKey *key = (RsaKey *)context;
178 unsigned char *e, *n, *d, *ret;
179 SilcUInt32 e_len, n_len, d_len;
180 unsigned char tmp[4];
182 e = silc_mp_mp2bin(&key->e, 0, &e_len);
183 n = silc_mp_mp2bin(&key->n, key->bits / 8, &n_len);
184 d = silc_mp_mp2bin(&key->d, 0, &d_len);
186 *ret_len = e_len + 4 + n_len + 4 + d_len + 4;
187 ret = silc_calloc(*ret_len, sizeof(unsigned char));
189 /* Put the length of the e. */
190 SILC_PUT32_MSB(e_len, tmp);
194 memcpy(ret + 4, e, e_len);
196 /* Put the length of the n. */
197 SILC_PUT32_MSB(n_len, tmp);
198 memcpy(ret + 4 + e_len, tmp, 4);
201 memcpy(ret + 4 + e_len + 4, n, n_len);
203 /* Put the length of the d. */
204 SILC_PUT32_MSB(d_len, tmp);
205 memcpy(ret + 4 + e_len + 4 + n_len, tmp, 4);
208 memcpy(ret + 4 + e_len + 4 + n_len + 4, d, d_len);
222 SILC_PKCS_API_SET_PUBLIC_KEY(rsa)
224 RsaKey *key = (RsaKey *)context;
225 unsigned char tmp[4];
226 SilcUInt32 e_len, n_len;
229 silc_mp_uninit(&key->e);
230 silc_mp_uninit(&key->n);
231 key->pub_set = FALSE;
234 silc_mp_init(&key->e);
235 silc_mp_init(&key->n);
237 memcpy(tmp, key_data, 4);
238 SILC_GET32_MSB(e_len, tmp);
239 if (e_len > key_len) {
240 silc_mp_uninit(&key->e);
241 silc_mp_uninit(&key->n);
245 silc_mp_bin2mp(key_data + 4, e_len, &key->e);
247 memcpy(tmp, key_data + 4 + e_len, 4);
248 SILC_GET32_MSB(n_len, tmp);
249 if (e_len + n_len > key_len) {
250 silc_mp_uninit(&key->e);
251 silc_mp_uninit(&key->n);
255 silc_mp_bin2mp(key_data + 4 + e_len + 4, n_len, &key->n);
257 key->bits = n_len * 8;
263 /* Set private key. This derives the public key from the private
264 key and sets the public key as well. Public key should not be set
265 already and should not be set after setting private key. */
267 SILC_PKCS_API_SET_PRIVATE_KEY(rsa)
269 RsaKey *key = (RsaKey *)context;
270 unsigned char tmp[4];
271 SilcUInt32 e_len, n_len, d_len;
274 silc_mp_uninit(&key->d);
275 key->prv_set = FALSE;
279 silc_mp_uninit(&key->e);
280 silc_mp_uninit(&key->n);
281 key->pub_set = FALSE;
284 silc_mp_init(&key->e);
285 silc_mp_init(&key->n);
286 silc_mp_init(&key->d);
288 memcpy(tmp, key_data, 4);
289 SILC_GET32_MSB(e_len, tmp);
290 if (e_len > key_len) {
291 silc_mp_uninit(&key->e);
292 silc_mp_uninit(&key->n);
293 silc_mp_uninit(&key->d);
297 silc_mp_bin2mp(key_data + 4, e_len, &key->e);
299 memcpy(tmp, key_data + 4 + e_len, 4);
300 SILC_GET32_MSB(n_len, tmp);
301 if (e_len + n_len > key_len) {
302 silc_mp_uninit(&key->e);
303 silc_mp_uninit(&key->n);
304 silc_mp_uninit(&key->d);
308 silc_mp_bin2mp(key_data + 4 + e_len + 4, n_len, &key->n);
310 memcpy(tmp, key_data + 4 + e_len + 4 + n_len, 4);
311 SILC_GET32_MSB(d_len, tmp);
312 if (e_len + n_len + d_len > key_len) {
313 silc_mp_uninit(&key->e);
314 silc_mp_uninit(&key->n);
315 silc_mp_uninit(&key->d);
319 silc_mp_bin2mp(key_data + 4 + e_len + 4 + n_len + 4, d_len, &key->d);
321 key->bits = n_len * 8;
328 SILC_PKCS_API_CONTEXT_LEN(rsa)
330 return sizeof(RsaKey);
333 SILC_PKCS_API_ENCRYPT(rsa)
335 RsaKey *key = (RsaKey *)context;
340 silc_mp_init(&mp_tmp);
341 silc_mp_init(&mp_dst);
342 silc_mp_set_ui(&mp_tmp, 0);
343 silc_mp_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_div_2exp(&mp_dst, &mp_dst, 8);
363 silc_mp_uninit(&mp_tmp);
364 silc_mp_uninit(&mp_dst);
369 SILC_PKCS_API_DECRYPT(rsa)
371 RsaKey *key = (RsaKey *)context;
376 silc_mp_init(&mp_tmp);
377 silc_mp_init(&mp_dst);
378 silc_mp_set_ui(&mp_tmp, 0);
379 silc_mp_set_ui(&mp_dst, 0);
381 /* Format the data into MP int */
382 for (i = 0; i < src_len; i++) {
383 silc_mp_mul_2exp(&mp_tmp, &mp_tmp, 8);
384 silc_mp_add_ui(&mp_tmp, &mp_tmp, src[i]);
388 rsa_en_de_crypt(&mp_dst, &mp_tmp, &key->d, &key->n);
390 tmplen = (key->bits + 7) / 8;
392 /* Format the MP int back into data */
393 for (i = tmplen; i > 0; i--) {
394 dst[i - 1] = (unsigned char)(silc_mp_get_ui(&mp_dst) & 0xff);
395 silc_mp_div_2exp(&mp_dst, &mp_dst, 8);
399 silc_mp_uninit(&mp_tmp);
400 silc_mp_uninit(&mp_dst);
405 SILC_PKCS_API_SIGN(rsa)
407 RsaKey *key = (RsaKey *)context;
412 silc_mp_init(&mp_tmp);
413 silc_mp_init(&mp_dst);
414 silc_mp_set_ui(&mp_tmp, 0);
415 silc_mp_set_ui(&mp_dst, 0);
417 /* Format the data into MP int */
418 for (i = 0; i < src_len; i++) {
419 silc_mp_mul_2exp(&mp_tmp, &mp_tmp, 8);
420 silc_mp_add_ui(&mp_tmp, &mp_tmp, src[i]);
424 rsa_en_de_crypt(&mp_dst, &mp_tmp, &key->d, &key->n);
426 tmplen = (key->bits + 7) / 8;
428 /* Format the MP int back into data */
429 for (i = tmplen; i > 0; i--) {
430 dst[i - 1] = (unsigned char)(silc_mp_get_ui(&mp_dst) & 0xff);
431 silc_mp_div_2exp(&mp_dst, &mp_dst, 8);
435 silc_mp_uninit(&mp_tmp);
436 silc_mp_uninit(&mp_dst);
441 SILC_PKCS_API_VERIFY(rsa)
443 RsaKey *key = (RsaKey *)context;
445 SilcMPInt mp_tmp, mp_tmp2;
448 silc_mp_init(&mp_tmp);
449 silc_mp_init(&mp_tmp2);
450 silc_mp_init(&mp_dst);
451 silc_mp_set_ui(&mp_tmp, 0);
452 silc_mp_set_ui(&mp_tmp2, 0);
453 silc_mp_set_ui(&mp_dst, 0);
455 /* Format the signature into MP int */
456 for (i = 0; i < signature_len; i++) {
457 silc_mp_mul_2exp(&mp_tmp2, &mp_tmp2, 8);
458 silc_mp_add_ui(&mp_tmp2, &mp_tmp2, signature[i]);
462 rsa_en_de_crypt(&mp_dst, &mp_tmp2, &key->e, &key->n);
464 /* Format the data into MP int */
465 for (i = 0; i < data_len; i++) {
466 silc_mp_mul_2exp(&mp_tmp, &mp_tmp, 8);
467 silc_mp_add_ui(&mp_tmp, &mp_tmp, data[i]);
473 if ((silc_mp_cmp(&mp_tmp, &mp_dst)) != 0)
476 silc_mp_uninit(&mp_tmp);
477 silc_mp_uninit(&mp_tmp2);
478 silc_mp_uninit(&mp_dst);
483 /* Generates RSA public and private keys. Primes p and q that are used
484 to compute the modulus n has to be generated before calling this. They
485 are then sent as argument for the function. */
487 void rsa_generate_keys(RsaKey *key, SilcUInt32 bits,
488 SilcMPInt *p, SilcMPInt *q)
494 /* Initialize variables */
495 silc_mp_init(&key->n);
496 silc_mp_init(&key->e);
497 silc_mp_init(&key->d);
505 /* Set modulus length */
508 /* Compute modulus, n = p * q */
509 silc_mp_mul(&key->n, p, q);
511 /* phi = (p - 1) * (q - 1) */
512 silc_mp_sub_ui(&pm1, p, 1);
513 silc_mp_sub_ui(&qm1, q, 1);
514 silc_mp_mul(&phi, &pm1, &qm1);
516 /* Set e, the public exponent. We try to use same public exponent
517 for all keys. Also, to make encryption faster we use small
519 silc_mp_set_ui(&key->e, 127);
521 /* See if e is relatively prime to phi. gcd == greates common divisor,
522 if gcd equals 1 they are relatively prime. */
523 silc_mp_gcd(&hlp, &key->e, &phi);
524 if((silc_mp_cmp_ui(&hlp, 1)) > 0) {
525 silc_mp_add_ui(&key->e, &key->e, 2);
529 /* Find d, the private exponent. */
530 silc_mp_gcd(&div, &pm1, &qm1);
531 silc_mp_div(&lcm, &phi, &div);
532 silc_mp_modinv(&key->d, &key->e, &lcm);
534 silc_mp_uninit(&phi);
535 silc_mp_uninit(&hlp);
536 silc_mp_uninit(&div);
537 silc_mp_uninit(&lcm);
538 silc_mp_uninit(&pm1);
539 silc_mp_uninit(&qm1);
542 /* Clears whole key structure. */
544 void rsa_clear_keys(RsaKey *key)
548 silc_mp_uninit(&key->n);
549 silc_mp_uninit(&key->e);
552 silc_mp_uninit(&key->d);
555 /* RSA encrypt/decrypt function. cm = ciphertext or plaintext,
556 mc = plaintext or ciphertext, expo = public or private exponent,
559 Encrypt: c = m ^ e mod n,
560 Decrypt: m = c ^ d mod n
563 void rsa_en_de_crypt(SilcMPInt *cm, SilcMPInt *mc,
564 SilcMPInt *expo, SilcMPInt *modu)
566 silc_mp_pow_mod(cm, mc, expo, modu);