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;
81 printf("Generating RSA Public and Private keys, might take a while...\n");
88 printf("Finding p: ");
89 silc_math_gen_prime(&p, prime_bits, TRUE);
91 printf("\nFinding q: ");
92 silc_math_gen_prime(&q, prime_bits, TRUE);
94 if ((silc_mp_cmp(&p, &q)) == 0) {
95 printf("\nFound equal primes, not good, retrying...\n");
99 /* If p is smaller than q, switch them */
100 if ((silc_mp_cmp(&p, &q)) > 0) {
104 silc_mp_set(&hlp, &p);
106 silc_mp_set(&q, &hlp);
108 silc_mp_uninit(&hlp);
111 /* Generate the actual keys */
112 rsa_generate_keys((RsaKey *)context, keylen, &p, &q);
117 printf("\nKeys generated succesfully.\n");
122 SILC_PKCS_API_CLEAR_KEYS(rsa)
124 rsa_clear_keys((RsaKey *)context);
127 /* Returns SILC style encoded RSA public key. */
129 SILC_PKCS_API_GET_PUBLIC_KEY(rsa)
131 RsaKey *key = (RsaKey *)context;
132 unsigned char *e, *n, *ret;
134 unsigned char tmp[4];
136 e = silc_mp_mp2bin(&key->e, 0, &e_len);
137 n = silc_mp_mp2bin(&key->n, key->bits / 8, &n_len);
139 *ret_len = e_len + 4 + n_len + 4;
140 ret = silc_calloc(*ret_len, sizeof(unsigned char));
142 /* Put the length of the e. */
143 SILC_PUT32_MSB(e_len, tmp);
147 memcpy(ret + 4, e, e_len);
149 /* Put the length of the n. */
150 SILC_PUT32_MSB(n_len, tmp);
151 memcpy(ret + 4 + e_len, tmp, 4);
154 memcpy(ret + 4 + e_len + 4, n, n_len);
164 /* Returns SILC style encoded RSA private key. Public key is always
165 returned in private key as well. Public keys are often derived
166 directly from private key. */
168 SILC_PKCS_API_GET_PRIVATE_KEY(rsa)
170 RsaKey *key = (RsaKey *)context;
171 unsigned char *e, *n, *d, *ret;
172 uint32 e_len, n_len, d_len;
173 unsigned char tmp[4];
175 e = silc_mp_mp2bin(&key->e, 0, &e_len);
176 n = silc_mp_mp2bin(&key->n, key->bits / 8, &n_len);
177 d = silc_mp_mp2bin(&key->d, 0, &d_len);
179 *ret_len = e_len + 4 + n_len + 4 + d_len + 4;
180 ret = silc_calloc(*ret_len, sizeof(unsigned char));
182 /* Put the length of the e. */
183 SILC_PUT32_MSB(e_len, tmp);
187 memcpy(ret + 4, e, e_len);
189 /* Put the length of the n. */
190 SILC_PUT32_MSB(n_len, tmp);
191 memcpy(ret + 4 + e_len, tmp, 4);
194 memcpy(ret + 4 + e_len + 4, n, n_len);
196 /* Put the length of the d. */
197 SILC_PUT32_MSB(d_len, tmp);
198 memcpy(ret + 4 + e_len + 4 + n_len, tmp, 4);
201 memcpy(ret + 4 + e_len + 4 + n_len + 4, d, d_len);
215 SILC_PKCS_API_SET_PUBLIC_KEY(rsa)
217 RsaKey *key = (RsaKey *)context;
218 unsigned char tmp[4];
221 silc_mp_init(&key->e);
222 silc_mp_init(&key->n);
224 memcpy(tmp, key_data, 4);
225 SILC_GET32_MSB(e_len, tmp);
226 if (e_len > key_len) {
227 silc_mp_uninit(&key->e);
228 silc_mp_uninit(&key->n);
232 silc_mp_bin2mp(key_data + 4, e_len, &key->e);
234 memcpy(tmp, key_data + 4 + e_len, 4);
235 SILC_GET32_MSB(n_len, tmp);
236 if (e_len + n_len > key_len) {
237 silc_mp_uninit(&key->e);
238 silc_mp_uninit(&key->n);
242 silc_mp_bin2mp(key_data + 4 + e_len + 4, n_len, &key->n);
244 key->bits = n_len * 8;
249 /* Set private key. This derives the public key from the private
250 key and sets the public key as well. Public key should not be set
251 already and should not be set after setting private key. */
253 SILC_PKCS_API_SET_PRIVATE_KEY(rsa)
255 RsaKey *key = (RsaKey *)context;
256 unsigned char tmp[4];
257 uint32 e_len, n_len, d_len;
259 silc_mp_init(&key->e);
260 silc_mp_init(&key->n);
261 silc_mp_init(&key->d);
263 memcpy(tmp, key_data, 4);
264 SILC_GET32_MSB(e_len, tmp);
265 if (e_len > key_len) {
266 silc_mp_uninit(&key->e);
267 silc_mp_uninit(&key->n);
271 silc_mp_bin2mp(key_data + 4, e_len, &key->e);
273 memcpy(tmp, key_data + 4 + e_len, 4);
274 SILC_GET32_MSB(n_len, tmp);
275 if (e_len + n_len > key_len) {
276 silc_mp_uninit(&key->e);
277 silc_mp_uninit(&key->n);
281 silc_mp_bin2mp(key_data + 4 + e_len + 4, n_len, &key->n);
283 memcpy(tmp, key_data + 4 + e_len + 4 + n_len, 4);
284 SILC_GET32_MSB(d_len, tmp);
285 if (e_len + n_len + d_len > key_len) {
286 silc_mp_uninit(&key->e);
287 silc_mp_uninit(&key->n);
291 silc_mp_bin2mp(key_data + 4 + e_len + 4 + n_len + 4, d_len, &key->d);
293 key->bits = n_len * 8;
298 SILC_PKCS_API_CONTEXT_LEN(rsa)
300 return sizeof(RsaKey);
303 SILC_PKCS_API_ENCRYPT(rsa)
305 RsaKey *key = (RsaKey *)context;
310 silc_mp_init(&mp_tmp);
311 silc_mp_init(&mp_dst);
312 silc_mp_set_ui(&mp_tmp, 0);
313 silc_mp_set_ui(&mp_dst, 0);
315 /* Format the data into MP int */
316 for (i = 0; i < src_len; i++) {
317 silc_mp_mul_2exp(&mp_tmp, &mp_tmp, 8);
318 silc_mp_add_ui(&mp_tmp, &mp_tmp, src[i]);
322 rsa_en_de_crypt(&mp_dst, &mp_tmp, &key->e, &key->n);
324 tmplen = (key->bits + 7) / 8;
326 /* Format the MP int back into data */
327 for (i = tmplen; i > 0; i--) {
328 dst[i - 1] = (unsigned char)(silc_mp_get_ui(&mp_dst) & 0xff);
329 silc_mp_div_2exp(&mp_dst, &mp_dst, 8);
333 silc_mp_uninit(&mp_tmp);
334 silc_mp_uninit(&mp_dst);
339 SILC_PKCS_API_DECRYPT(rsa)
341 RsaKey *key = (RsaKey *)context;
346 silc_mp_init(&mp_tmp);
347 silc_mp_init(&mp_dst);
348 silc_mp_set_ui(&mp_tmp, 0);
349 silc_mp_set_ui(&mp_dst, 0);
351 /* Format the data into MP int */
352 for (i = 0; i < src_len; i++) {
353 silc_mp_mul_2exp(&mp_tmp, &mp_tmp, 8);
354 silc_mp_add_ui(&mp_tmp, &mp_tmp, src[i]);
358 rsa_en_de_crypt(&mp_dst, &mp_tmp, &key->d, &key->n);
360 tmplen = (key->bits + 7) / 8;
362 /* Format the MP int back into data */
363 for (i = tmplen; i > 0; i--) {
364 dst[i - 1] = (unsigned char)(silc_mp_get_ui(&mp_dst) & 0xff);
365 silc_mp_div_2exp(&mp_dst, &mp_dst, 8);
369 silc_mp_uninit(&mp_tmp);
370 silc_mp_uninit(&mp_dst);
375 SILC_PKCS_API_SIGN(rsa)
377 RsaKey *key = (RsaKey *)context;
382 silc_mp_init(&mp_tmp);
383 silc_mp_init(&mp_dst);
384 silc_mp_set_ui(&mp_tmp, 0);
385 silc_mp_set_ui(&mp_dst, 0);
387 /* Format the data into MP int */
388 for (i = 0; i < src_len; i++) {
389 silc_mp_mul_2exp(&mp_tmp, &mp_tmp, 8);
390 silc_mp_add_ui(&mp_tmp, &mp_tmp, src[i]);
394 rsa_en_de_crypt(&mp_dst, &mp_tmp, &key->d, &key->n);
396 tmplen = (key->bits + 7) / 8;
398 /* Format the MP int back into data */
399 for (i = tmplen; i > 0; i--) {
400 dst[i - 1] = (unsigned char)(silc_mp_get_ui(&mp_dst) & 0xff);
401 silc_mp_div_2exp(&mp_dst, &mp_dst, 8);
405 silc_mp_uninit(&mp_tmp);
406 silc_mp_uninit(&mp_dst);
411 SILC_PKCS_API_VERIFY(rsa)
413 RsaKey *key = (RsaKey *)context;
415 SilcMPInt mp_tmp, mp_tmp2;
418 silc_mp_init(&mp_tmp);
419 silc_mp_init(&mp_tmp2);
420 silc_mp_init(&mp_dst);
421 silc_mp_set_ui(&mp_tmp, 0);
422 silc_mp_set_ui(&mp_tmp2, 0);
423 silc_mp_set_ui(&mp_dst, 0);
425 /* Format the signature into MP int */
426 for (i = 0; i < signature_len; i++) {
427 silc_mp_mul_2exp(&mp_tmp2, &mp_tmp2, 8);
428 silc_mp_add_ui(&mp_tmp2, &mp_tmp2, signature[i]);
432 rsa_en_de_crypt(&mp_dst, &mp_tmp2, &key->e, &key->n);
434 /* Format the data into MP int */
435 for (i = 0; i < data_len; i++) {
436 silc_mp_mul_2exp(&mp_tmp, &mp_tmp, 8);
437 silc_mp_add_ui(&mp_tmp, &mp_tmp, data[i]);
443 if ((silc_mp_cmp(&mp_tmp, &mp_dst)) != 0)
446 silc_mp_uninit(&mp_tmp);
447 silc_mp_uninit(&mp_tmp2);
448 silc_mp_uninit(&mp_dst);
453 /* Generates RSA public and private keys. Primes p and q that are used
454 to compute the modulus n has to be generated before calling this. They
455 are then sent as argument for the function. */
457 void rsa_generate_keys(RsaKey *key, uint32 bits,
458 SilcMPInt *p, SilcMPInt *q)
464 /* Initialize variables */
465 silc_mp_init(&key->p);
466 silc_mp_init(&key->q);
467 silc_mp_init(&key->n);
468 silc_mp_init(&key->e);
469 silc_mp_init(&key->d);
477 /* Set modulus length */
481 silc_mp_set(&key->p, p);
482 silc_mp_set(&key->q, q);
484 /* Compute modulus, n = p * q */
485 silc_mp_mul(&key->n, &key->p, &key->q);
487 /* phi = (p - 1) * (q - 1) */
488 silc_mp_sub_ui(&pm1, &key->p, 1);
489 silc_mp_sub_ui(&qm1, &key->q, 1);
490 silc_mp_mul(&phi, &pm1, &qm1);
492 /* Set e, the public exponent. We try to use same public exponent
493 for all keys. Also, to make encryption faster we use small
495 silc_mp_set_ui(&key->e, 127);
497 /* See if e is relatively prime to phi. gcd == greates common divisor,
498 if gcd equals 1 they are relatively prime. */
499 silc_mp_gcd(&hlp, &key->e, &phi);
500 if((silc_mp_cmp_ui(&hlp, 1)) > 0) {
501 silc_mp_add_ui(&key->e, &key->e, 2);
505 /* Find d, the private exponent. */
506 silc_mp_gcd(&div, &pm1, &qm1);
507 silc_mp_div(&lcm, &phi, &div);
508 silc_mp_modinv(&key->d, &key->e, &lcm);
510 silc_mp_uninit(&phi);
511 silc_mp_uninit(&hlp);
512 silc_mp_uninit(&div);
513 silc_mp_uninit(&lcm);
514 silc_mp_uninit(&pm1);
515 silc_mp_uninit(&qm1);
518 /* Clears whole key structure. */
520 void rsa_clear_keys(RsaKey *key)
523 silc_mp_uninit(&key->p);
524 silc_mp_uninit(&key->q);
525 silc_mp_uninit(&key->n);
526 silc_mp_uninit(&key->e);
527 silc_mp_uninit(&key->d);
530 /* RSA encrypt/decrypt function. cm = ciphertext or plaintext,
531 mc = plaintext or ciphertext, expo = public or private exponent,
534 Encrypt: c = m ^ e mod n,
535 Decrypt: m = c ^ d mod n
538 void rsa_en_de_crypt(SilcMPInt *cm, SilcMPInt *mc,
539 SilcMPInt *expo, SilcMPInt *modu)
541 silc_mp_pow_mod(cm, mc, expo, modu);