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 SilcUInt32 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;
135 SilcUInt32 e_len, n_len;
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 SilcUInt32 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];
221 SilcUInt32 e_len, n_len;
224 silc_mp_uninit(&key->e);
225 silc_mp_uninit(&key->e);
226 key->pub_set = FALSE;
229 silc_mp_init(&key->e);
230 silc_mp_init(&key->n);
232 memcpy(tmp, key_data, 4);
233 SILC_GET32_MSB(e_len, tmp);
234 if (e_len > key_len) {
235 silc_mp_uninit(&key->e);
236 silc_mp_uninit(&key->n);
240 silc_mp_bin2mp(key_data + 4, e_len, &key->e);
242 memcpy(tmp, key_data + 4 + e_len, 4);
243 SILC_GET32_MSB(n_len, tmp);
244 if (e_len + n_len > key_len) {
245 silc_mp_uninit(&key->e);
246 silc_mp_uninit(&key->n);
250 silc_mp_bin2mp(key_data + 4 + e_len + 4, n_len, &key->n);
252 key->bits = n_len * 8;
258 /* Set private key. This derives the public key from the private
259 key and sets the public key as well. Public key should not be set
260 already and should not be set after setting private key. */
262 SILC_PKCS_API_SET_PRIVATE_KEY(rsa)
264 RsaKey *key = (RsaKey *)context;
265 unsigned char tmp[4];
266 SilcUInt32 e_len, n_len, d_len;
269 silc_mp_uninit(&key->d);
270 key->prv_set = FALSE;
274 silc_mp_uninit(&key->e);
275 silc_mp_uninit(&key->n);
276 key->pub_set = FALSE;
279 silc_mp_init(&key->e);
280 silc_mp_init(&key->n);
281 silc_mp_init(&key->d);
283 memcpy(tmp, key_data, 4);
284 SILC_GET32_MSB(e_len, tmp);
285 if (e_len > key_len) {
286 silc_mp_uninit(&key->e);
287 silc_mp_uninit(&key->n);
288 silc_mp_uninit(&key->d);
292 silc_mp_bin2mp(key_data + 4, e_len, &key->e);
294 memcpy(tmp, key_data + 4 + e_len, 4);
295 SILC_GET32_MSB(n_len, tmp);
296 if (e_len + n_len > key_len) {
297 silc_mp_uninit(&key->e);
298 silc_mp_uninit(&key->n);
299 silc_mp_uninit(&key->d);
303 silc_mp_bin2mp(key_data + 4 + e_len + 4, n_len, &key->n);
305 memcpy(tmp, key_data + 4 + e_len + 4 + n_len, 4);
306 SILC_GET32_MSB(d_len, tmp);
307 if (e_len + n_len + d_len > 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 + 4 + n_len + 4, d_len, &key->d);
316 key->bits = n_len * 8;
323 SILC_PKCS_API_CONTEXT_LEN(rsa)
325 return sizeof(RsaKey);
328 SILC_PKCS_API_ENCRYPT(rsa)
330 RsaKey *key = (RsaKey *)context;
335 silc_mp_init(&mp_tmp);
336 silc_mp_init(&mp_dst);
337 silc_mp_set_ui(&mp_tmp, 0);
338 silc_mp_set_ui(&mp_dst, 0);
340 /* Format the data into MP int */
341 for (i = 0; i < src_len; i++) {
342 silc_mp_mul_2exp(&mp_tmp, &mp_tmp, 8);
343 silc_mp_add_ui(&mp_tmp, &mp_tmp, src[i]);
347 rsa_en_de_crypt(&mp_dst, &mp_tmp, &key->e, &key->n);
349 tmplen = (key->bits + 7) / 8;
351 /* Format the MP int back into data */
352 for (i = tmplen; i > 0; i--) {
353 dst[i - 1] = (unsigned char)(silc_mp_get_ui(&mp_dst) & 0xff);
354 silc_mp_div_2exp(&mp_dst, &mp_dst, 8);
358 silc_mp_uninit(&mp_tmp);
359 silc_mp_uninit(&mp_dst);
364 SILC_PKCS_API_DECRYPT(rsa)
366 RsaKey *key = (RsaKey *)context;
371 silc_mp_init(&mp_tmp);
372 silc_mp_init(&mp_dst);
373 silc_mp_set_ui(&mp_tmp, 0);
374 silc_mp_set_ui(&mp_dst, 0);
376 /* Format the data into MP int */
377 for (i = 0; i < src_len; i++) {
378 silc_mp_mul_2exp(&mp_tmp, &mp_tmp, 8);
379 silc_mp_add_ui(&mp_tmp, &mp_tmp, src[i]);
383 rsa_en_de_crypt(&mp_dst, &mp_tmp, &key->d, &key->n);
385 tmplen = (key->bits + 7) / 8;
387 /* Format the MP int back into data */
388 for (i = tmplen; i > 0; i--) {
389 dst[i - 1] = (unsigned char)(silc_mp_get_ui(&mp_dst) & 0xff);
390 silc_mp_div_2exp(&mp_dst, &mp_dst, 8);
394 silc_mp_uninit(&mp_tmp);
395 silc_mp_uninit(&mp_dst);
400 SILC_PKCS_API_SIGN(rsa)
402 RsaKey *key = (RsaKey *)context;
407 silc_mp_init(&mp_tmp);
408 silc_mp_init(&mp_dst);
409 silc_mp_set_ui(&mp_tmp, 0);
410 silc_mp_set_ui(&mp_dst, 0);
412 /* Format the data into MP int */
413 for (i = 0; i < src_len; i++) {
414 silc_mp_mul_2exp(&mp_tmp, &mp_tmp, 8);
415 silc_mp_add_ui(&mp_tmp, &mp_tmp, src[i]);
419 rsa_en_de_crypt(&mp_dst, &mp_tmp, &key->d, &key->n);
421 tmplen = (key->bits + 7) / 8;
423 /* Format the MP int back into data */
424 for (i = tmplen; i > 0; i--) {
425 dst[i - 1] = (unsigned char)(silc_mp_get_ui(&mp_dst) & 0xff);
426 silc_mp_div_2exp(&mp_dst, &mp_dst, 8);
430 silc_mp_uninit(&mp_tmp);
431 silc_mp_uninit(&mp_dst);
436 SILC_PKCS_API_VERIFY(rsa)
438 RsaKey *key = (RsaKey *)context;
440 SilcMPInt mp_tmp, mp_tmp2;
443 silc_mp_init(&mp_tmp);
444 silc_mp_init(&mp_tmp2);
445 silc_mp_init(&mp_dst);
446 silc_mp_set_ui(&mp_tmp, 0);
447 silc_mp_set_ui(&mp_tmp2, 0);
448 silc_mp_set_ui(&mp_dst, 0);
450 /* Format the signature into MP int */
451 for (i = 0; i < signature_len; i++) {
452 silc_mp_mul_2exp(&mp_tmp2, &mp_tmp2, 8);
453 silc_mp_add_ui(&mp_tmp2, &mp_tmp2, signature[i]);
457 rsa_en_de_crypt(&mp_dst, &mp_tmp2, &key->e, &key->n);
459 /* Format the data into MP int */
460 for (i = 0; i < data_len; i++) {
461 silc_mp_mul_2exp(&mp_tmp, &mp_tmp, 8);
462 silc_mp_add_ui(&mp_tmp, &mp_tmp, data[i]);
468 if ((silc_mp_cmp(&mp_tmp, &mp_dst)) != 0)
471 silc_mp_uninit(&mp_tmp);
472 silc_mp_uninit(&mp_tmp2);
473 silc_mp_uninit(&mp_dst);
478 /* Generates RSA public and private keys. Primes p and q that are used
479 to compute the modulus n has to be generated before calling this. They
480 are then sent as argument for the function. */
482 void rsa_generate_keys(RsaKey *key, SilcUInt32 bits,
483 SilcMPInt *p, SilcMPInt *q)
489 /* Initialize variables */
490 silc_mp_init(&key->n);
491 silc_mp_init(&key->e);
492 silc_mp_init(&key->d);
500 /* Set modulus length */
503 /* Compute modulus, n = p * q */
504 silc_mp_mul(&key->n, p, q);
506 /* phi = (p - 1) * (q - 1) */
507 silc_mp_sub_ui(&pm1, p, 1);
508 silc_mp_sub_ui(&qm1, q, 1);
509 silc_mp_mul(&phi, &pm1, &qm1);
511 /* Set e, the public exponent. We try to use same public exponent
512 for all keys. Also, to make encryption faster we use small
514 silc_mp_set_ui(&key->e, 127);
516 /* See if e is relatively prime to phi. gcd == greates common divisor,
517 if gcd equals 1 they are relatively prime. */
518 silc_mp_gcd(&hlp, &key->e, &phi);
519 if((silc_mp_cmp_ui(&hlp, 1)) > 0) {
520 silc_mp_add_ui(&key->e, &key->e, 2);
524 /* Find d, the private exponent. */
525 silc_mp_gcd(&div, &pm1, &qm1);
526 silc_mp_div(&lcm, &phi, &div);
527 silc_mp_modinv(&key->d, &key->e, &lcm);
529 silc_mp_uninit(&phi);
530 silc_mp_uninit(&hlp);
531 silc_mp_uninit(&div);
532 silc_mp_uninit(&lcm);
533 silc_mp_uninit(&pm1);
534 silc_mp_uninit(&qm1);
537 /* Clears whole key structure. */
539 void rsa_clear_keys(RsaKey *key)
543 silc_mp_uninit(&key->n);
544 silc_mp_uninit(&key->e);
547 silc_mp_uninit(&key->d);
550 /* RSA encrypt/decrypt function. cm = ciphertext or plaintext,
551 mc = plaintext or ciphertext, expo = public or private exponent,
554 Encrypt: c = m ^ e mod n,
555 Decrypt: m = c ^ d mod n
558 void rsa_en_de_crypt(SilcMPInt *cm, SilcMPInt *mc,
559 SilcMPInt *expo, SilcMPInt *modu)
561 silc_mp_pow_mod(cm, mc, expo, modu);