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.
66 #include "silcincludes.h"
67 #include "rsa_internal.h"
71 * SILC PKCS API for RSA
74 /* Generates RSA key pair. */
76 SILC_PKCS_API_INIT(rsa)
78 uint32 prime_bits = keylen / 2;
82 printf("Generating RSA Public and Private keys, might take a while...\n");
89 printf("Finding p: ");
90 silc_math_gen_prime(&p, prime_bits, TRUE);
92 printf("\nFinding q: ");
93 silc_math_gen_prime(&q, prime_bits, TRUE);
95 if ((silc_mp_cmp(&p, &q)) == 0)
96 printf("\nFound equal primes, not good, retrying...\n");
101 /* If p is smaller than q, switch them */
102 if ((silc_mp_cmp(&p, &q)) > 0) {
106 silc_mp_set(&hlp, &p);
108 silc_mp_set(&q, &hlp);
110 silc_mp_uninit(&hlp);
113 /* Generate the actual keys */
114 rsa_generate_keys((RsaKey *)context, keylen, &p, &q);
119 printf("\nKeys generated succesfully.\n");
124 SILC_PKCS_API_CLEAR_KEYS(rsa)
126 rsa_clear_keys((RsaKey *)context);
129 /* Returns SILC style encoded RSA public key. */
131 SILC_PKCS_API_GET_PUBLIC_KEY(rsa)
133 RsaKey *key = (RsaKey *)context;
134 unsigned char *e, *n, *ret;
136 unsigned char tmp[4];
138 e = silc_mp_mp2bin(&key->e, 0, &e_len);
139 n = silc_mp_mp2bin(&key->n, key->bits / 8, &n_len);
141 *ret_len = e_len + 4 + n_len + 4;
142 ret = silc_calloc(*ret_len, sizeof(unsigned char));
144 /* Put the length of the e. */
145 SILC_PUT32_MSB(e_len, tmp);
149 memcpy(ret + 4, e, e_len);
151 /* Put the length of the n. */
152 SILC_PUT32_MSB(n_len, tmp);
153 memcpy(ret + 4 + e_len, tmp, 4);
156 memcpy(ret + 4 + e_len + 4, n, n_len);
166 /* Returns SILC style encoded RSA private key. Public key is always
167 returned in private key as well. Public keys are often derived
168 directly from private key. */
170 SILC_PKCS_API_GET_PRIVATE_KEY(rsa)
172 RsaKey *key = (RsaKey *)context;
173 unsigned char *e, *n, *d, *ret;
174 uint32 e_len, n_len, d_len;
175 unsigned char tmp[4];
177 e = silc_mp_mp2bin(&key->e, 0, &e_len);
178 n = silc_mp_mp2bin(&key->n, key->bits / 8, &n_len);
179 d = silc_mp_mp2bin(&key->d, 0, &d_len);
181 *ret_len = e_len + 4 + n_len + 4 + d_len + 4;
182 ret = silc_calloc(*ret_len, sizeof(unsigned char));
184 /* Put the length of the e. */
185 SILC_PUT32_MSB(e_len, tmp);
189 memcpy(ret + 4, e, e_len);
191 /* Put the length of the n. */
192 SILC_PUT32_MSB(n_len, tmp);
193 memcpy(ret + 4 + e_len, tmp, 4);
196 memcpy(ret + 4 + e_len + 4, n, n_len);
198 /* Put the length of the d. */
199 SILC_PUT32_MSB(d_len, tmp);
200 memcpy(ret + 4 + e_len + 4 + n_len, tmp, 4);
203 memcpy(ret + 4 + e_len + 4 + n_len + 4, d, d_len);
217 SILC_PKCS_API_SET_PUBLIC_KEY(rsa)
219 RsaKey *key = (RsaKey *)context;
220 unsigned char tmp[4];
223 silc_mp_init(&key->e);
224 silc_mp_init(&key->n);
226 memcpy(tmp, key_data, 4);
227 SILC_GET32_MSB(e_len, tmp);
228 if (e_len > key_len) {
229 silc_mp_uninit(&key->e);
230 silc_mp_uninit(&key->n);
234 silc_mp_bin2mp(key_data + 4, e_len, &key->e);
236 memcpy(tmp, key_data + 4 + e_len, 4);
237 SILC_GET32_MSB(n_len, tmp);
238 if (e_len + n_len > key_len) {
239 silc_mp_uninit(&key->e);
240 silc_mp_uninit(&key->n);
244 silc_mp_bin2mp(key_data + 4 + e_len + 4, n_len, &key->n);
246 key->bits = n_len * 8;
251 /* Set private key. This derives the public key from the private
252 key and sets the public key as well. Public key should not be set
253 already and should not be set after setting private key. */
255 SILC_PKCS_API_SET_PRIVATE_KEY(rsa)
257 RsaKey *key = (RsaKey *)context;
258 unsigned char tmp[4];
259 uint32 e_len, n_len, d_len;
261 silc_mp_init(&key->e);
262 silc_mp_init(&key->n);
263 silc_mp_init(&key->d);
265 memcpy(tmp, key_data, 4);
266 SILC_GET32_MSB(e_len, tmp);
267 if (e_len > key_len) {
268 silc_mp_uninit(&key->e);
269 silc_mp_uninit(&key->n);
273 silc_mp_bin2mp(key_data + 4, e_len, &key->e);
275 memcpy(tmp, key_data + 4 + e_len, 4);
276 SILC_GET32_MSB(n_len, tmp);
277 if (e_len + n_len > key_len) {
278 silc_mp_uninit(&key->e);
279 silc_mp_uninit(&key->n);
283 silc_mp_bin2mp(key_data + 4 + e_len + 4, n_len, &key->n);
285 memcpy(tmp, key_data + 4 + e_len + 4 + n_len, 4);
286 SILC_GET32_MSB(d_len, tmp);
287 if (e_len + n_len + d_len > key_len) {
288 silc_mp_uninit(&key->e);
289 silc_mp_uninit(&key->n);
293 silc_mp_bin2mp(key_data + 4 + e_len + 4 + n_len + 4, d_len, &key->d);
295 key->bits = n_len * 8;
300 SILC_PKCS_API_CONTEXT_LEN(rsa)
302 return sizeof(RsaKey);
305 SILC_PKCS_API_ENCRYPT(rsa)
307 RsaKey *key = (RsaKey *)context;
312 silc_mp_init(&mp_tmp);
313 silc_mp_init(&mp_dst);
314 silc_mp_set_ui(&mp_tmp, 0);
315 silc_mp_set_ui(&mp_dst, 0);
317 /* Format the data into MP int */
318 for (i = 0; i < src_len; i++) {
319 silc_mp_mul_2exp(&mp_tmp, &mp_tmp, 8);
320 silc_mp_add_ui(&mp_tmp, &mp_tmp, src[i]);
324 rsa_en_de_crypt(&mp_dst, &mp_tmp, &key->e, &key->n);
326 tmplen = (key->bits + 7) / 8;
328 /* Format the MP int back into data */
329 for (i = tmplen; i > 0; i--) {
330 dst[i - 1] = (unsigned char)(silc_mp_get_ui(&mp_dst) & 0xff);
331 silc_mp_div_2exp(&mp_dst, &mp_dst, 8);
335 silc_mp_uninit(&mp_tmp);
336 silc_mp_uninit(&mp_dst);
341 SILC_PKCS_API_DECRYPT(rsa)
343 RsaKey *key = (RsaKey *)context;
348 silc_mp_init(&mp_tmp);
349 silc_mp_init(&mp_dst);
350 silc_mp_set_ui(&mp_tmp, 0);
351 silc_mp_set_ui(&mp_dst, 0);
353 /* Format the data into MP int */
354 for (i = 0; i < src_len; i++) {
355 silc_mp_mul_2exp(&mp_tmp, &mp_tmp, 8);
356 silc_mp_add_ui(&mp_tmp, &mp_tmp, src[i]);
360 rsa_en_de_crypt(&mp_dst, &mp_tmp, &key->d, &key->n);
362 tmplen = (key->bits + 7) / 8;
364 /* Format the MP int back into data */
365 for (i = tmplen; i > 0; i--) {
366 dst[i - 1] = (unsigned char)(silc_mp_get_ui(&mp_dst) & 0xff);
367 silc_mp_div_2exp(&mp_dst, &mp_dst, 8);
371 silc_mp_uninit(&mp_tmp);
372 silc_mp_uninit(&mp_dst);
377 SILC_PKCS_API_SIGN(rsa)
379 RsaKey *key = (RsaKey *)context;
384 silc_mp_init(&mp_tmp);
385 silc_mp_init(&mp_dst);
386 silc_mp_set_ui(&mp_tmp, 0);
387 silc_mp_set_ui(&mp_dst, 0);
389 /* Format the data into MP int */
390 for (i = 0; i < src_len; i++) {
391 silc_mp_mul_2exp(&mp_tmp, &mp_tmp, 8);
392 silc_mp_add_ui(&mp_tmp, &mp_tmp, src[i]);
396 rsa_en_de_crypt(&mp_dst, &mp_tmp, &key->d, &key->n);
398 tmplen = (key->bits + 7) / 8;
400 /* Format the MP int back into data */
401 for (i = tmplen; i > 0; i--) {
402 dst[i - 1] = (unsigned char)(silc_mp_get_ui(&mp_dst) & 0xff);
403 silc_mp_div_2exp(&mp_dst, &mp_dst, 8);
407 silc_mp_uninit(&mp_tmp);
408 silc_mp_uninit(&mp_dst);
413 SILC_PKCS_API_VERIFY(rsa)
415 RsaKey *key = (RsaKey *)context;
417 SilcMPInt mp_tmp, mp_tmp2;
420 silc_mp_init(&mp_tmp);
421 silc_mp_init(&mp_tmp2);
422 silc_mp_init(&mp_dst);
423 silc_mp_set_ui(&mp_tmp, 0);
424 silc_mp_set_ui(&mp_tmp2, 0);
425 silc_mp_set_ui(&mp_dst, 0);
427 /* Format the signature into MP int */
428 for (i = 0; i < signature_len; i++) {
429 silc_mp_mul_2exp(&mp_tmp2, &mp_tmp2, 8);
430 silc_mp_add_ui(&mp_tmp2, &mp_tmp2, signature[i]);
434 rsa_en_de_crypt(&mp_dst, &mp_tmp2, &key->e, &key->n);
436 /* Format the data into MP int */
437 for (i = 0; i < data_len; i++) {
438 silc_mp_mul_2exp(&mp_tmp, &mp_tmp, 8);
439 silc_mp_add_ui(&mp_tmp, &mp_tmp, data[i]);
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, uint32 bits,
460 SilcMPInt *p, SilcMPInt *q)
466 /* Initialize variables */
467 silc_mp_init(&key->p);
468 silc_mp_init(&key->q);
469 silc_mp_init(&key->n);
470 silc_mp_init(&key->e);
471 silc_mp_init(&key->d);
479 /* Set modulus length */
483 silc_mp_set(&key->p, p);
484 silc_mp_set(&key->q, q);
486 /* Compute modulus, n = p * q */
487 silc_mp_mul(&key->n, &key->p, &key->q);
489 /* phi = (p - 1) * (q - 1) */
490 silc_mp_sub_ui(&pm1, &key->p, 1);
491 silc_mp_sub_ui(&qm1, &key->q, 1);
492 silc_mp_mul(&phi, &pm1, &qm1);
494 /* Set e, the public exponent. We try to use same public exponent
495 for all keys. Also, to make encryption faster we use small
497 silc_mp_set_ui(&key->e, 127);
499 /* See if e is relatively prime to phi. gcd == greates common divisor,
500 if gcd equals 1 they are relatively prime. */
501 silc_mp_gcd(&hlp, &key->e, &phi);
502 if((silc_mp_cmp_ui(&hlp, 1)) > 0) {
503 silc_mp_add_ui(&key->e, &key->e, 2);
507 /* Find d, the private exponent. */
508 silc_mp_gcd(&div, &pm1, &qm1);
509 silc_mp_div(&lcm, &phi, &div);
510 silc_mp_modinv(&key->d, &key->e, &lcm);
512 silc_mp_uninit(&phi);
513 silc_mp_uninit(&hlp);
514 silc_mp_uninit(&div);
515 silc_mp_uninit(&lcm);
516 silc_mp_uninit(&pm1);
517 silc_mp_uninit(&qm1);
520 /* Clears whole key structure. */
522 void rsa_clear_keys(RsaKey *key)
525 silc_mp_uninit(&key->p);
526 silc_mp_uninit(&key->q);
527 silc_mp_uninit(&key->n);
528 silc_mp_uninit(&key->e);
529 silc_mp_uninit(&key->d);
532 /* RSA encrypt/decrypt function. cm = ciphertext or plaintext,
533 mc = plaintext or ciphertext, expo = public or private exponent,
536 Encrypt: c = m ^ e mod n,
537 Decrypt: m = c ^ d mod n
540 void rsa_en_de_crypt(SilcMPInt *cm, SilcMPInt *mc,
541 SilcMPInt *expo, SilcMPInt *modu)
543 silc_mp_pow_mod(cm, mc, expo, modu);