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.
59 #include "silcincludes.h"
63 * SILC PKCS API for RSA
66 /* Generates RSA key pair. */
68 SILC_PKCS_API_INIT(rsa)
70 unsigned int prime_bits = keylen / 2;
73 printf("Generating RSA Public and Private keys, might take a while...\n");
80 printf("Finding p: ");
81 silc_math_gen_prime(&p, prime_bits, TRUE);
83 printf("\nFinding q: ");
84 silc_math_gen_prime(&q, prime_bits, TRUE);
86 if ((silc_mp_cmp(&p, &q)) == 0) {
87 printf("\nFound equal primes, not good, retrying...\n");
91 /* If p is smaller than q, switch them */
92 if ((silc_mp_cmp(&p, &q)) > 0) {
96 silc_mp_set(&hlp, &p);
98 silc_mp_set(&q, &hlp);
103 /* Generate the actual keys */
104 rsa_generate_keys((RsaKey *)context, keylen, &p, &q);
109 printf("\nKeys generated succesfully.\n");
114 SILC_PKCS_API_CLEAR_KEYS(rsa)
116 rsa_clear_keys((RsaKey *)context);
119 /* Returns SILC style encoded RSA public key. */
121 SILC_PKCS_API_GET_PUBLIC_KEY(rsa)
123 RsaKey *key = (RsaKey *)context;
124 unsigned char *e, *n, *ret;
125 unsigned int e_len, n_len;
126 unsigned char tmp[4];
128 e = silc_mp_mp2bin(&key->e, &e_len);
129 n = silc_mp_mp2bin(&key->n, &n_len);
131 *ret_len = e_len + 4 + n_len + 4;
132 ret = silc_calloc(*ret_len, sizeof(unsigned char));
134 /* Put the length of the e. */
135 SILC_PUT32_MSB(e_len, tmp);
139 memcpy(ret + 4, e, e_len);
141 /* Put the length of the n. */
142 SILC_PUT32_MSB(n_len, tmp);
143 memcpy(ret + 4 + e_len, tmp, 4);
146 memcpy(ret + 4 + e_len + 4, n, n_len);
156 /* Returns SILC style encoded RSA private key. Public key is always
157 returned in private key as well. Public keys are often derived
158 directly from private key. */
160 SILC_PKCS_API_GET_PRIVATE_KEY(rsa)
162 RsaKey *key = (RsaKey *)context;
163 unsigned char *e, *n, *d, *ret;
164 unsigned int e_len, n_len, d_len;
165 unsigned char tmp[4];
167 e = silc_mp_mp2bin(&key->e, &e_len);
168 n = silc_mp_mp2bin(&key->n, &n_len);
169 d = silc_mp_mp2bin(&key->d, &d_len);
171 *ret_len = e_len + 4 + n_len + 4 + d_len + 4;
172 ret = silc_calloc(*ret_len, sizeof(unsigned char));
174 /* Put the length of the e. */
175 SILC_PUT32_MSB(e_len, tmp);
179 memcpy(ret + 4, e, e_len);
181 /* Put the length of the n. */
182 SILC_PUT32_MSB(n_len, tmp);
183 memcpy(ret + 4 + e_len, tmp, 4);
186 memcpy(ret + 4 + e_len + 4, n, n_len);
188 /* Put the length of the d. */
189 SILC_PUT32_MSB(d_len, tmp);
190 memcpy(ret + 4 + e_len + 4 + n_len, tmp, 4);
193 memcpy(ret + 4 + e_len + 4 + n_len + 4, d, d_len);
207 SILC_PKCS_API_SET_PUBLIC_KEY(rsa)
209 RsaKey *key = (RsaKey *)context;
210 unsigned char tmp[4];
211 unsigned int e_len, n_len;
213 silc_mp_init(&key->e);
214 silc_mp_init(&key->n);
216 memcpy(tmp, key_data, 4);
217 SILC_GET32_MSB(e_len, tmp);
218 if (e_len > key_len) {
219 silc_mp_clear(&key->e);
220 silc_mp_clear(&key->n);
224 silc_mp_bin2mp(key_data + 4, e_len, &key->e);
226 memcpy(tmp, key_data + 4 + e_len, 4);
227 SILC_GET32_MSB(n_len, tmp);
228 if (e_len + n_len > key_len) {
229 silc_mp_clear(&key->e);
230 silc_mp_clear(&key->n);
234 silc_mp_bin2mp(key_data + 4 + e_len + 4, n_len, &key->n);
239 /* Set private key. This derives the public key from the private
240 key and sets the public key as well. Public key should not be set
241 already and should not be set after setting private key. */
243 SILC_PKCS_API_SET_PRIVATE_KEY(rsa)
245 RsaKey *key = (RsaKey *)context;
246 unsigned char tmp[4];
247 unsigned int e_len, n_len, d_len;
249 silc_mp_init(&key->e);
250 silc_mp_init(&key->n);
251 silc_mp_init(&key->d);
253 memcpy(tmp, key_data, 4);
254 SILC_GET32_MSB(e_len, tmp);
255 if (e_len > key_len) {
256 silc_mp_clear(&key->e);
257 silc_mp_clear(&key->n);
261 silc_mp_bin2mp(key_data + 4, e_len, &key->e);
263 memcpy(tmp, key_data + 4 + e_len, 4);
264 SILC_GET32_MSB(n_len, tmp);
265 if (e_len + n_len > key_len) {
266 silc_mp_clear(&key->e);
267 silc_mp_clear(&key->n);
271 silc_mp_bin2mp(key_data + 4 + e_len + 4, n_len, &key->n);
273 memcpy(tmp, key_data + 4 + e_len + 4 + n_len, 4);
274 SILC_GET32_MSB(d_len, tmp);
275 if (e_len + n_len + d_len > key_len) {
276 silc_mp_clear(&key->e);
277 silc_mp_clear(&key->n);
281 silc_mp_bin2mp(key_data + 4 + e_len + 4 + n_len + 4, d_len, &key->d);
286 SILC_PKCS_API_CONTEXT_LEN(rsa)
288 return sizeof(RsaKey);
291 SILC_PKCS_API_DATA_CONTEXT_LEN(rsa)
293 return sizeof(RsaDataContext);
296 SILC_PKCS_API_SET_ARG(rsa)
298 RsaDataContext *data_ctx = (RsaDataContext *)data_context;
325 SILC_PKCS_API_ENCRYPT(rsa)
327 RsaKey *key = (RsaKey *)context;
332 silc_mp_init_set_ui(&mp_tmp, 0);
333 silc_mp_init_set_ui(&mp_dst, 0);
335 /* Format the data into MP int */
336 for (i = 0; i < src_len; i++) {
337 silc_mp_mul_2exp(&mp_tmp, &mp_tmp, 8);
338 silc_mp_add_ui(&mp_tmp, &mp_tmp, src[i]);
342 rsa_en_de_crypt(&mp_dst, &mp_tmp, &key->e, &key->n);
344 tmplen = (1024 + 7) / 8;
346 /* Format the MP int back into data */
347 for (i = tmplen; i > 0; i--) {
348 dst[i - 1] = (unsigned char)(silc_mp_get_ui(&mp_dst) & 0xff);
349 silc_mp_fdiv_q_2exp(&mp_dst, &mp_dst, 8);
353 silc_mp_clear(&mp_tmp);
354 silc_mp_clear(&mp_dst);
359 SILC_PKCS_API_DECRYPT(rsa)
361 RsaKey *key = (RsaKey *)context;
366 silc_mp_init_set_ui(&mp_tmp, 0);
367 silc_mp_init_set_ui(&mp_dst, 0);
369 /* Format the data into MP int */
370 for (i = 0; i < src_len; i++) {
371 silc_mp_mul_2exp(&mp_tmp, &mp_tmp, 8);
372 silc_mp_add_ui(&mp_tmp, &mp_tmp, src[i]);
376 rsa_en_de_crypt(&mp_dst, &mp_tmp, &key->d, &key->n);
378 tmplen = (1024 + 7) / 8;
380 /* Format the MP int back into data */
381 for (i = tmplen; i > 0; i--) {
382 dst[i - 1] = (unsigned char)(silc_mp_get_ui(&mp_dst) & 0xff);
383 silc_mp_fdiv_q_2exp(&mp_dst, &mp_dst, 8);
387 silc_mp_clear(&mp_tmp);
388 silc_mp_clear(&mp_dst);
393 SILC_PKCS_API_SIGN(rsa)
395 RsaKey *key = (RsaKey *)context;
400 silc_mp_init_set_ui(&mp_tmp, 0);
401 silc_mp_init_set_ui(&mp_dst, 0);
403 /* Format the data into MP int */
404 for (i = 0; i < src_len; i++) {
405 silc_mp_mul_2exp(&mp_tmp, &mp_tmp, 8);
406 silc_mp_add_ui(&mp_tmp, &mp_tmp, src[i]);
410 rsa_en_de_crypt(&mp_dst, &mp_tmp, &key->d, &key->n);
412 tmplen = (1024 + 7) / 8;
414 /* Format the MP int back into data */
415 for (i = tmplen; i > 0; i--) {
416 dst[i - 1] = (unsigned char)(silc_mp_get_ui(&mp_dst) & 0xff);
417 silc_mp_fdiv_q_2exp(&mp_dst, &mp_dst, 8);
421 silc_mp_clear(&mp_tmp);
422 silc_mp_clear(&mp_dst);
427 SILC_PKCS_API_VERIFY(rsa)
429 RsaKey *key = (RsaKey *)context;
431 SilcInt mp_tmp, mp_tmp2;
434 silc_mp_init_set_ui(&mp_tmp, 0);
435 silc_mp_init_set_ui(&mp_tmp2, 0);
436 silc_mp_init_set_ui(&mp_dst, 0);
438 /* Format the signature into MP int */
439 for (i = 0; i < signature_len; i++) {
440 silc_mp_mul_2exp(&mp_tmp2, &mp_tmp2, 8);
441 silc_mp_add_ui(&mp_tmp2, &mp_tmp2, signature[i]);
445 rsa_en_de_crypt(&mp_dst, &mp_tmp2, &key->e, &key->n);
447 /* Format the data into MP int */
448 for (i = 0; i < data_len; i++) {
449 silc_mp_mul_2exp(&mp_tmp, &mp_tmp, 8);
450 silc_mp_add_ui(&mp_tmp, &mp_tmp, data[i]);
456 if ((silc_mp_cmp(&mp_tmp, &mp_dst)) != 0)
459 silc_mp_clear(&mp_tmp);
460 silc_mp_clear(&mp_tmp2);
461 silc_mp_clear(&mp_dst);
466 /* Generates RSA public and private keys. Primes p and q that are used
467 to compute the modulus n has to be generated before calling this. They
468 are then sent as argument for the function. */
470 void rsa_generate_keys(RsaKey *key, unsigned int bits,
471 SilcInt *p, SilcInt *q)
477 /* Initialize variables */
478 silc_mp_init(&key->p);
479 silc_mp_init(&key->q);
480 silc_mp_init(&key->n);
481 silc_mp_init(&key->e);
482 silc_mp_init(&key->d);
491 silc_mp_set(&key->p, p);
492 silc_mp_set(&key->q, q);
494 /* Compute modulus, n = p * q */
495 silc_mp_mul(&key->n, &key->p, &key->q);
497 /* phi = (p - 1) * (q - 1) */
498 silc_mp_sub_ui(&pm1, &key->p, 1);
499 silc_mp_sub_ui(&qm1, &key->q, 1);
500 silc_mp_mul(&phi, &pm1, &qm1);
502 /* Set e, the public exponent. We try to use same public exponent
503 for all keys. Also, to make encryption faster we use small
505 silc_mp_set_ui(&key->e, 127);
507 /* See if e is relatively prime to phi. gcd == greates common divisor,
508 if gcd equals 1 they are relatively prime. */
509 silc_mp_gcd(&hlp, &key->e, &phi);
510 if((silc_mp_cmp_ui(&hlp, 1)) > 0) {
511 silc_mp_add_ui(&key->e, &key->e, 2);
515 /* Find d, the private exponent. */
516 silc_mp_gcd(&div, &pm1, &qm1);
517 silc_mp_fdiv_q(&lcm, &phi, &div);
518 silc_mp_modinv(&key->d, &key->e, &lcm);
528 /* Clears whole key structure. */
530 void rsa_clear_keys(RsaKey *key)
533 silc_mp_clear(&key->p);
534 silc_mp_clear(&key->q);
535 silc_mp_clear(&key->n);
536 silc_mp_clear(&key->e);
537 silc_mp_clear(&key->d);
540 /* RSA encrypt/decrypt function. cm = ciphertext or plaintext,
541 mc = plaintext or ciphertext, expo = public or private exponent,
544 Encrypt: c = m ^ e mod n,
545 Decrypt: m = c ^ d mod n
548 void rsa_en_de_crypt(SilcInt *cm, SilcInt *mc,
549 SilcInt *expo, SilcInt *modu)
551 silc_mp_powm(cm, mc, expo, modu);