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 uint32 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);
106 silc_mp_uninit(&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;
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 uint32 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];
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_uninit(&key->e);
226 silc_mp_uninit(&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_uninit(&key->e);
236 silc_mp_uninit(&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 uint32 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_uninit(&key->e);
265 silc_mp_uninit(&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_uninit(&key->e);
275 silc_mp_uninit(&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_uninit(&key->e);
285 silc_mp_uninit(&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_ENCRYPT(rsa)
303 RsaKey *key = (RsaKey *)context;
308 silc_mp_init(&mp_tmp);
309 silc_mp_init(&mp_dst);
310 silc_mp_set_ui(&mp_tmp, 0);
311 silc_mp_set_ui(&mp_dst, 0);
313 /* Format the data into MP int */
314 for (i = 0; i < src_len; i++) {
315 silc_mp_mul_2exp(&mp_tmp, &mp_tmp, 8);
316 silc_mp_add_ui(&mp_tmp, &mp_tmp, src[i]);
320 rsa_en_de_crypt(&mp_dst, &mp_tmp, &key->e, &key->n);
322 tmplen = (key->bits + 7) / 8;
324 /* Format the MP int back into data */
325 for (i = tmplen; i > 0; i--) {
326 dst[i - 1] = (unsigned char)(silc_mp_get_ui(&mp_dst) & 0xff);
327 silc_mp_div_2exp(&mp_dst, &mp_dst, 8);
331 silc_mp_uninit(&mp_tmp);
332 silc_mp_uninit(&mp_dst);
337 SILC_PKCS_API_DECRYPT(rsa)
339 RsaKey *key = (RsaKey *)context;
344 silc_mp_init(&mp_tmp);
345 silc_mp_init(&mp_dst);
346 silc_mp_set_ui(&mp_tmp, 0);
347 silc_mp_set_ui(&mp_dst, 0);
349 /* Format the data into MP int */
350 for (i = 0; i < src_len; i++) {
351 silc_mp_mul_2exp(&mp_tmp, &mp_tmp, 8);
352 silc_mp_add_ui(&mp_tmp, &mp_tmp, src[i]);
356 rsa_en_de_crypt(&mp_dst, &mp_tmp, &key->d, &key->n);
358 tmplen = (key->bits + 7) / 8;
360 /* Format the MP int back into data */
361 for (i = tmplen; i > 0; i--) {
362 dst[i - 1] = (unsigned char)(silc_mp_get_ui(&mp_dst) & 0xff);
363 silc_mp_div_2exp(&mp_dst, &mp_dst, 8);
367 silc_mp_uninit(&mp_tmp);
368 silc_mp_uninit(&mp_dst);
373 SILC_PKCS_API_SIGN(rsa)
375 RsaKey *key = (RsaKey *)context;
380 silc_mp_init(&mp_tmp);
381 silc_mp_init(&mp_dst);
382 silc_mp_set_ui(&mp_tmp, 0);
383 silc_mp_set_ui(&mp_dst, 0);
385 /* Format the data into MP int */
386 for (i = 0; i < src_len; i++) {
387 silc_mp_mul_2exp(&mp_tmp, &mp_tmp, 8);
388 silc_mp_add_ui(&mp_tmp, &mp_tmp, src[i]);
392 rsa_en_de_crypt(&mp_dst, &mp_tmp, &key->d, &key->n);
394 tmplen = (key->bits + 7) / 8;
396 /* Format the MP int back into data */
397 for (i = tmplen; i > 0; i--) {
398 dst[i - 1] = (unsigned char)(silc_mp_get_ui(&mp_dst) & 0xff);
399 silc_mp_div_2exp(&mp_dst, &mp_dst, 8);
403 silc_mp_uninit(&mp_tmp);
404 silc_mp_uninit(&mp_dst);
409 SILC_PKCS_API_VERIFY(rsa)
411 RsaKey *key = (RsaKey *)context;
413 SilcMPInt mp_tmp, mp_tmp2;
416 silc_mp_init(&mp_tmp);
417 silc_mp_init(&mp_tmp2);
418 silc_mp_init(&mp_dst);
419 silc_mp_set_ui(&mp_tmp, 0);
420 silc_mp_set_ui(&mp_tmp2, 0);
421 silc_mp_set_ui(&mp_dst, 0);
423 /* Format the signature into MP int */
424 for (i = 0; i < signature_len; i++) {
425 silc_mp_mul_2exp(&mp_tmp2, &mp_tmp2, 8);
426 silc_mp_add_ui(&mp_tmp2, &mp_tmp2, signature[i]);
430 rsa_en_de_crypt(&mp_dst, &mp_tmp2, &key->e, &key->n);
432 /* Format the data into MP int */
433 for (i = 0; i < data_len; i++) {
434 silc_mp_mul_2exp(&mp_tmp, &mp_tmp, 8);
435 silc_mp_add_ui(&mp_tmp, &mp_tmp, data[i]);
441 if ((silc_mp_cmp(&mp_tmp, &mp_dst)) != 0)
444 silc_mp_uninit(&mp_tmp);
445 silc_mp_uninit(&mp_tmp2);
446 silc_mp_uninit(&mp_dst);
451 /* Generates RSA public and private keys. Primes p and q that are used
452 to compute the modulus n has to be generated before calling this. They
453 are then sent as argument for the function. */
455 void rsa_generate_keys(RsaKey *key, uint32 bits,
456 SilcMPInt *p, SilcMPInt *q)
462 /* Initialize variables */
463 silc_mp_init(&key->p);
464 silc_mp_init(&key->q);
465 silc_mp_init(&key->n);
466 silc_mp_init(&key->e);
467 silc_mp_init(&key->d);
475 /* Set modulus length */
479 silc_mp_set(&key->p, p);
480 silc_mp_set(&key->q, q);
482 /* Compute modulus, n = p * q */
483 silc_mp_mul(&key->n, &key->p, &key->q);
485 /* phi = (p - 1) * (q - 1) */
486 silc_mp_sub_ui(&pm1, &key->p, 1);
487 silc_mp_sub_ui(&qm1, &key->q, 1);
488 silc_mp_mul(&phi, &pm1, &qm1);
490 /* Set e, the public exponent. We try to use same public exponent
491 for all keys. Also, to make encryption faster we use small
493 silc_mp_set_ui(&key->e, 127);
495 /* See if e is relatively prime to phi. gcd == greates common divisor,
496 if gcd equals 1 they are relatively prime. */
497 silc_mp_gcd(&hlp, &key->e, &phi);
498 if((silc_mp_cmp_ui(&hlp, 1)) > 0) {
499 silc_mp_add_ui(&key->e, &key->e, 2);
503 /* Find d, the private exponent. */
504 silc_mp_gcd(&div, &pm1, &qm1);
505 silc_mp_div(&lcm, &phi, &div);
506 silc_mp_modinv(&key->d, &key->e, &lcm);
508 silc_mp_uninit(&phi);
509 silc_mp_uninit(&hlp);
510 silc_mp_uninit(&div);
511 silc_mp_uninit(&lcm);
512 silc_mp_uninit(&pm1);
513 silc_mp_uninit(&qm1);
516 /* Clears whole key structure. */
518 void rsa_clear_keys(RsaKey *key)
521 silc_mp_uninit(&key->p);
522 silc_mp_uninit(&key->q);
523 silc_mp_uninit(&key->n);
524 silc_mp_uninit(&key->e);
525 silc_mp_uninit(&key->d);
528 /* RSA encrypt/decrypt function. cm = ciphertext or plaintext,
529 mc = plaintext or ciphertext, expo = public or private exponent,
532 Encrypt: c = m ^ e mod n,
533 Decrypt: m = c ^ d mod n
536 void rsa_en_de_crypt(SilcMPInt *cm, SilcMPInt *mc,
537 SilcMPInt *expo, SilcMPInt *modu)
539 silc_mp_pow_mod(cm, mc, expo, modu);