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"
70 * SILC PKCS API for RSA
73 /* Generates RSA key pair. */
75 SILC_PKCS_API_INIT(rsa)
77 uint32 prime_bits = keylen / 2;
80 printf("Generating RSA Public and Private keys, might take a while...\n");
87 printf("Finding p: ");
88 silc_math_gen_prime(&p, prime_bits, TRUE);
90 printf("\nFinding q: ");
91 silc_math_gen_prime(&q, prime_bits, TRUE);
93 if ((silc_mp_cmp(&p, &q)) == 0) {
94 printf("\nFound equal primes, not good, retrying...\n");
98 /* If p is smaller than q, switch them */
99 if ((silc_mp_cmp(&p, &q)) > 0) {
103 silc_mp_set(&hlp, &p);
105 silc_mp_set(&q, &hlp);
107 silc_mp_uninit(&hlp);
110 /* Generate the actual keys */
111 rsa_generate_keys((RsaKey *)context, keylen, &p, &q);
116 printf("\nKeys generated succesfully.\n");
121 SILC_PKCS_API_CLEAR_KEYS(rsa)
123 rsa_clear_keys((RsaKey *)context);
126 /* Returns SILC style encoded RSA public key. */
128 SILC_PKCS_API_GET_PUBLIC_KEY(rsa)
130 RsaKey *key = (RsaKey *)context;
131 unsigned char *e, *n, *ret;
133 unsigned char tmp[4];
135 e = silc_mp_mp2bin(&key->e, 0, &e_len);
136 n = silc_mp_mp2bin(&key->n, key->bits / 8, &n_len);
138 *ret_len = e_len + 4 + n_len + 4;
139 ret = silc_calloc(*ret_len, sizeof(unsigned char));
141 /* Put the length of the e. */
142 SILC_PUT32_MSB(e_len, tmp);
146 memcpy(ret + 4, e, e_len);
148 /* Put the length of the n. */
149 SILC_PUT32_MSB(n_len, tmp);
150 memcpy(ret + 4 + e_len, tmp, 4);
153 memcpy(ret + 4 + e_len + 4, n, n_len);
163 /* Returns SILC style encoded RSA private key. Public key is always
164 returned in private key as well. Public keys are often derived
165 directly from private key. */
167 SILC_PKCS_API_GET_PRIVATE_KEY(rsa)
169 RsaKey *key = (RsaKey *)context;
170 unsigned char *e, *n, *d, *ret;
171 uint32 e_len, n_len, d_len;
172 unsigned char tmp[4];
174 e = silc_mp_mp2bin(&key->e, 0, &e_len);
175 n = silc_mp_mp2bin(&key->n, key->bits / 8, &n_len);
176 d = silc_mp_mp2bin(&key->d, 0, &d_len);
178 *ret_len = e_len + 4 + n_len + 4 + d_len + 4;
179 ret = silc_calloc(*ret_len, sizeof(unsigned char));
181 /* Put the length of the e. */
182 SILC_PUT32_MSB(e_len, tmp);
186 memcpy(ret + 4, e, e_len);
188 /* Put the length of the n. */
189 SILC_PUT32_MSB(n_len, tmp);
190 memcpy(ret + 4 + e_len, tmp, 4);
193 memcpy(ret + 4 + e_len + 4, n, n_len);
195 /* Put the length of the d. */
196 SILC_PUT32_MSB(d_len, tmp);
197 memcpy(ret + 4 + e_len + 4 + n_len, tmp, 4);
200 memcpy(ret + 4 + e_len + 4 + n_len + 4, d, d_len);
214 SILC_PKCS_API_SET_PUBLIC_KEY(rsa)
216 RsaKey *key = (RsaKey *)context;
217 unsigned char tmp[4];
220 silc_mp_init(&key->e);
221 silc_mp_init(&key->n);
223 memcpy(tmp, key_data, 4);
224 SILC_GET32_MSB(e_len, tmp);
225 if (e_len > key_len) {
226 silc_mp_uninit(&key->e);
227 silc_mp_uninit(&key->n);
231 silc_mp_bin2mp(key_data + 4, e_len, &key->e);
233 memcpy(tmp, key_data + 4 + e_len, 4);
234 SILC_GET32_MSB(n_len, tmp);
235 if (e_len + n_len > key_len) {
236 silc_mp_uninit(&key->e);
237 silc_mp_uninit(&key->n);
241 silc_mp_bin2mp(key_data + 4 + e_len + 4, n_len, &key->n);
243 key->bits = n_len * 8;
248 /* Set private key. This derives the public key from the private
249 key and sets the public key as well. Public key should not be set
250 already and should not be set after setting private key. */
252 SILC_PKCS_API_SET_PRIVATE_KEY(rsa)
254 RsaKey *key = (RsaKey *)context;
255 unsigned char tmp[4];
256 uint32 e_len, n_len, d_len;
258 silc_mp_init(&key->e);
259 silc_mp_init(&key->n);
260 silc_mp_init(&key->d);
262 memcpy(tmp, key_data, 4);
263 SILC_GET32_MSB(e_len, tmp);
264 if (e_len > key_len) {
265 silc_mp_uninit(&key->e);
266 silc_mp_uninit(&key->n);
270 silc_mp_bin2mp(key_data + 4, e_len, &key->e);
272 memcpy(tmp, key_data + 4 + e_len, 4);
273 SILC_GET32_MSB(n_len, tmp);
274 if (e_len + n_len > key_len) {
275 silc_mp_uninit(&key->e);
276 silc_mp_uninit(&key->n);
280 silc_mp_bin2mp(key_data + 4 + e_len + 4, n_len, &key->n);
282 memcpy(tmp, key_data + 4 + e_len + 4 + n_len, 4);
283 SILC_GET32_MSB(d_len, tmp);
284 if (e_len + n_len + d_len > key_len) {
285 silc_mp_uninit(&key->e);
286 silc_mp_uninit(&key->n);
290 silc_mp_bin2mp(key_data + 4 + e_len + 4 + n_len + 4, d_len, &key->d);
292 key->bits = n_len * 8;
297 SILC_PKCS_API_CONTEXT_LEN(rsa)
299 return sizeof(RsaKey);
302 SILC_PKCS_API_ENCRYPT(rsa)
304 RsaKey *key = (RsaKey *)context;
309 silc_mp_init(&mp_tmp);
310 silc_mp_init(&mp_dst);
311 silc_mp_set_ui(&mp_tmp, 0);
312 silc_mp_set_ui(&mp_dst, 0);
314 /* Format the data into MP int */
315 for (i = 0; i < src_len; i++) {
316 silc_mp_mul_2exp(&mp_tmp, &mp_tmp, 8);
317 silc_mp_add_ui(&mp_tmp, &mp_tmp, src[i]);
321 rsa_en_de_crypt(&mp_dst, &mp_tmp, &key->e, &key->n);
323 tmplen = (key->bits + 7) / 8;
325 /* Format the MP int back into data */
326 for (i = tmplen; i > 0; i--) {
327 dst[i - 1] = (unsigned char)(silc_mp_get_ui(&mp_dst) & 0xff);
328 silc_mp_div_2exp(&mp_dst, &mp_dst, 8);
332 silc_mp_uninit(&mp_tmp);
333 silc_mp_uninit(&mp_dst);
338 SILC_PKCS_API_DECRYPT(rsa)
340 RsaKey *key = (RsaKey *)context;
345 silc_mp_init(&mp_tmp);
346 silc_mp_init(&mp_dst);
347 silc_mp_set_ui(&mp_tmp, 0);
348 silc_mp_set_ui(&mp_dst, 0);
350 /* Format the data into MP int */
351 for (i = 0; i < src_len; i++) {
352 silc_mp_mul_2exp(&mp_tmp, &mp_tmp, 8);
353 silc_mp_add_ui(&mp_tmp, &mp_tmp, src[i]);
357 rsa_en_de_crypt(&mp_dst, &mp_tmp, &key->d, &key->n);
359 tmplen = (key->bits + 7) / 8;
361 /* Format the MP int back into data */
362 for (i = tmplen; i > 0; i--) {
363 dst[i - 1] = (unsigned char)(silc_mp_get_ui(&mp_dst) & 0xff);
364 silc_mp_div_2exp(&mp_dst, &mp_dst, 8);
368 silc_mp_uninit(&mp_tmp);
369 silc_mp_uninit(&mp_dst);
374 SILC_PKCS_API_SIGN(rsa)
376 RsaKey *key = (RsaKey *)context;
381 silc_mp_init(&mp_tmp);
382 silc_mp_init(&mp_dst);
383 silc_mp_set_ui(&mp_tmp, 0);
384 silc_mp_set_ui(&mp_dst, 0);
386 /* Format the data into MP int */
387 for (i = 0; i < src_len; i++) {
388 silc_mp_mul_2exp(&mp_tmp, &mp_tmp, 8);
389 silc_mp_add_ui(&mp_tmp, &mp_tmp, src[i]);
393 rsa_en_de_crypt(&mp_dst, &mp_tmp, &key->d, &key->n);
395 tmplen = (key->bits + 7) / 8;
397 /* Format the MP int back into data */
398 for (i = tmplen; i > 0; i--) {
399 dst[i - 1] = (unsigned char)(silc_mp_get_ui(&mp_dst) & 0xff);
400 silc_mp_div_2exp(&mp_dst, &mp_dst, 8);
404 silc_mp_uninit(&mp_tmp);
405 silc_mp_uninit(&mp_dst);
410 SILC_PKCS_API_VERIFY(rsa)
412 RsaKey *key = (RsaKey *)context;
414 SilcMPInt mp_tmp, mp_tmp2;
417 silc_mp_init(&mp_tmp);
418 silc_mp_init(&mp_tmp2);
419 silc_mp_init(&mp_dst);
420 silc_mp_set_ui(&mp_tmp, 0);
421 silc_mp_set_ui(&mp_tmp2, 0);
422 silc_mp_set_ui(&mp_dst, 0);
424 /* Format the signature into MP int */
425 for (i = 0; i < signature_len; i++) {
426 silc_mp_mul_2exp(&mp_tmp2, &mp_tmp2, 8);
427 silc_mp_add_ui(&mp_tmp2, &mp_tmp2, signature[i]);
431 rsa_en_de_crypt(&mp_dst, &mp_tmp2, &key->e, &key->n);
433 /* Format the data into MP int */
434 for (i = 0; i < data_len; i++) {
435 silc_mp_mul_2exp(&mp_tmp, &mp_tmp, 8);
436 silc_mp_add_ui(&mp_tmp, &mp_tmp, data[i]);
442 if ((silc_mp_cmp(&mp_tmp, &mp_dst)) != 0)
445 silc_mp_uninit(&mp_tmp);
446 silc_mp_uninit(&mp_tmp2);
447 silc_mp_uninit(&mp_dst);
452 /* Generates RSA public and private keys. Primes p and q that are used
453 to compute the modulus n has to be generated before calling this. They
454 are then sent as argument for the function. */
456 void rsa_generate_keys(RsaKey *key, uint32 bits,
457 SilcMPInt *p, SilcMPInt *q)
463 /* Initialize variables */
464 silc_mp_init(&key->p);
465 silc_mp_init(&key->q);
466 silc_mp_init(&key->n);
467 silc_mp_init(&key->e);
468 silc_mp_init(&key->d);
476 /* Set modulus length */
480 silc_mp_set(&key->p, p);
481 silc_mp_set(&key->q, q);
483 /* Compute modulus, n = p * q */
484 silc_mp_mul(&key->n, &key->p, &key->q);
486 /* phi = (p - 1) * (q - 1) */
487 silc_mp_sub_ui(&pm1, &key->p, 1);
488 silc_mp_sub_ui(&qm1, &key->q, 1);
489 silc_mp_mul(&phi, &pm1, &qm1);
491 /* Set e, the public exponent. We try to use same public exponent
492 for all keys. Also, to make encryption faster we use small
494 silc_mp_set_ui(&key->e, 127);
496 /* See if e is relatively prime to phi. gcd == greates common divisor,
497 if gcd equals 1 they are relatively prime. */
498 silc_mp_gcd(&hlp, &key->e, &phi);
499 if((silc_mp_cmp_ui(&hlp, 1)) > 0) {
500 silc_mp_add_ui(&key->e, &key->e, 2);
504 /* Find d, the private exponent. */
505 silc_mp_gcd(&div, &pm1, &qm1);
506 silc_mp_div(&lcm, &phi, &div);
507 silc_mp_modinv(&key->d, &key->e, &lcm);
509 silc_mp_uninit(&phi);
510 silc_mp_uninit(&hlp);
511 silc_mp_uninit(&div);
512 silc_mp_uninit(&lcm);
513 silc_mp_uninit(&pm1);
514 silc_mp_uninit(&qm1);
517 /* Clears whole key structure. */
519 void rsa_clear_keys(RsaKey *key)
522 silc_mp_uninit(&key->p);
523 silc_mp_uninit(&key->q);
524 silc_mp_uninit(&key->n);
525 silc_mp_uninit(&key->e);
526 silc_mp_uninit(&key->d);
529 /* RSA encrypt/decrypt function. cm = ciphertext or plaintext,
530 mc = plaintext or ciphertext, expo = public or private exponent,
533 Encrypt: c = m ^ e mod n,
534 Decrypt: m = c ^ d mod n
537 void rsa_en_de_crypt(SilcMPInt *cm, SilcMPInt *mc,
538 SilcMPInt *expo, SilcMPInt *modu)
540 silc_mp_pow_mod(cm, mc, expo, modu);