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 - 2000 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 ((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.
48 #include "silcincludes.h"
52 * SILC PKCS API for RSA
55 /* Generates RSA key pair. */
57 SILC_PKCS_API_INIT(rsa)
59 unsigned int prime_bits = keylen / 2;
62 printf("Generating RSA Public and Private keys, might take a while...\n");
69 printf("Finding p: ");
70 silc_math_gen_prime(&p, prime_bits, TRUE);
72 printf("\nFinding q: ");
73 silc_math_gen_prime(&q, prime_bits, TRUE);
75 if ((silc_mp_cmp(&p, &q)) == 0) {
76 printf("\nFound equal primes, not good, retrying...\n");
80 /* If p is smaller than q, switch them */
81 if ((silc_mp_cmp(&p, &q)) > 0) {
85 silc_mp_set(&hlp, &p);
87 silc_mp_set(&q, &hlp);
92 /* Generate the actual keys */
93 rsa_generate_keys((RsaKey *)context, keylen, &p, &q);
98 printf("\nKeys generated succesfully.\n");
103 SILC_PKCS_API_CLEAR_KEYS(rsa)
105 rsa_clear_keys((RsaKey *)context);
108 /* Returns SILC style encoded RSA public key. */
110 SILC_PKCS_API_GET_PUBLIC_KEY(rsa)
112 RsaKey *key = (RsaKey *)context;
113 unsigned char *e, *n, *ret;
114 unsigned int e_len, n_len;
115 unsigned char tmp[4];
117 e = silc_mp_mp2bin(&key->e, &e_len);
118 n = silc_mp_mp2bin(&key->n, &n_len);
120 *ret_len = e_len + 4 + n_len + 4;
121 ret = silc_calloc(*ret_len, sizeof(unsigned char));
123 /* Put the length of the e. */
124 SILC_PUT32_MSB(e_len, tmp);
128 memcpy(ret + 4, e, e_len);
130 /* Put the length of the n. */
131 SILC_PUT32_MSB(n_len, tmp);
132 memcpy(ret + 4 + e_len, tmp, 4);
135 memcpy(ret + 4 + e_len + 4, n, n_len);
145 /* Returns SILC style encoded RSA private key. Public key is always
146 returned in private key as well. Public keys are often derived
147 directly from private key. */
149 SILC_PKCS_API_GET_PRIVATE_KEY(rsa)
151 RsaKey *key = (RsaKey *)context;
152 unsigned char *e, *n, *d, *ret;
153 unsigned int e_len, n_len, d_len;
154 unsigned char tmp[4];
156 e = silc_mp_mp2bin(&key->e, &e_len);
157 n = silc_mp_mp2bin(&key->n, &n_len);
158 d = silc_mp_mp2bin(&key->d, &d_len);
160 *ret_len = e_len + 4 + n_len + 4 + d_len + 4;
161 ret = silc_calloc(*ret_len, sizeof(unsigned char));
163 /* Put the length of the e. */
164 SILC_PUT32_MSB(e_len, tmp);
168 memcpy(ret + 4, e, e_len);
170 /* Put the length of the n. */
171 SILC_PUT32_MSB(n_len, tmp);
172 memcpy(ret + 4 + e_len, tmp, 4);
175 memcpy(ret + 4 + e_len + 4, n, n_len);
177 /* Put the length of the d. */
178 SILC_PUT32_MSB(d_len, tmp);
179 memcpy(ret + 4 + e_len + 4 + n_len, tmp, 4);
182 memcpy(ret + 4 + e_len + 4 + n_len + 4, d, d_len);
196 SILC_PKCS_API_SET_PUBLIC_KEY(rsa)
198 RsaKey *key = (RsaKey *)context;
199 unsigned char tmp[4];
200 unsigned int e_len, n_len;
202 silc_mp_init(&key->e);
203 silc_mp_init(&key->n);
205 memcpy(tmp, key_data, 4);
206 SILC_GET32_MSB(e_len, tmp);
207 if (e_len > key_len) {
208 silc_mp_clear(&key->e);
209 silc_mp_clear(&key->n);
213 silc_mp_bin2mp(key_data + 4, e_len, &key->e);
215 memcpy(tmp, key_data + 4 + e_len, 4);
216 SILC_GET32_MSB(n_len, tmp);
217 if (e_len + n_len > key_len) {
218 silc_mp_clear(&key->e);
219 silc_mp_clear(&key->n);
223 silc_mp_bin2mp(key_data + 4 + e_len + 4, n_len, &key->n);
228 /* Set private key. This derives the public key from the private
229 key and sets the public key as well. Public key should not be set
230 already and should not be set after setting private key. */
232 SILC_PKCS_API_SET_PRIVATE_KEY(rsa)
234 RsaKey *key = (RsaKey *)context;
235 unsigned char tmp[4];
236 unsigned int e_len, n_len, d_len;
238 silc_mp_init(&key->e);
239 silc_mp_init(&key->n);
240 silc_mp_init(&key->d);
242 memcpy(tmp, key_data, 4);
243 SILC_GET32_MSB(e_len, tmp);
244 if (e_len > key_len) {
245 silc_mp_clear(&key->e);
246 silc_mp_clear(&key->n);
250 silc_mp_bin2mp(key_data + 4, e_len, &key->e);
252 memcpy(tmp, key_data + 4 + e_len, 4);
253 SILC_GET32_MSB(n_len, tmp);
254 if (e_len + n_len > key_len) {
255 silc_mp_clear(&key->e);
256 silc_mp_clear(&key->n);
260 silc_mp_bin2mp(key_data + 4 + e_len + 4, n_len, &key->n);
262 memcpy(tmp, key_data + 4 + e_len + 4 + n_len, 4);
263 SILC_GET32_MSB(d_len, tmp);
264 if (e_len + n_len + d_len > key_len) {
265 silc_mp_clear(&key->e);
266 silc_mp_clear(&key->n);
270 silc_mp_bin2mp(key_data + 4 + e_len + 4 + n_len + 4, d_len, &key->d);
275 SILC_PKCS_API_CONTEXT_LEN(rsa)
277 return sizeof(RsaKey);
280 SILC_PKCS_API_DATA_CONTEXT_LEN(rsa)
282 return sizeof(RsaDataContext);
285 SILC_PKCS_API_SET_ARG(rsa)
287 RsaDataContext *data_ctx = (RsaDataContext *)data_context;
314 SILC_PKCS_API_ENCRYPT(rsa)
316 RsaKey *key = (RsaKey *)context;
321 silc_mp_init_set_ui(&mp_tmp, 0);
322 silc_mp_init_set_ui(&mp_dst, 0);
324 /* Format the data into MP int */
325 for (i = 0; i < src_len; i++) {
326 silc_mp_mul_2exp(&mp_tmp, &mp_tmp, 8);
327 silc_mp_add_ui(&mp_tmp, &mp_tmp, src[i]);
330 silc_mp_out_str(stderr, 16, &mp_tmp);
333 rsa_en_de_crypt(&mp_dst, &mp_tmp, &key->e, &key->n);
335 fprintf(stderr, "\n");
336 silc_mp_out_str(stderr, 16, &mp_dst);
338 tmplen = (1024 + 7) / 8;
340 /* Format the MP int back into data */
341 for (i = tmplen; i > 0; i--) {
342 dst[i - 1] = (unsigned char)(silc_mp_get_ui(&mp_dst) & 0xff);
343 silc_mp_fdiv_q_2exp(&mp_dst, &mp_dst, 8);
347 silc_mp_clear(&mp_tmp);
348 silc_mp_clear(&mp_dst);
353 SILC_PKCS_API_DECRYPT(rsa)
355 RsaKey *key = (RsaKey *)context;
360 silc_mp_init_set_ui(&mp_tmp, 0);
361 silc_mp_init_set_ui(&mp_dst, 0);
363 /* Format the data into MP int */
364 for (i = 0; i < src_len; i++) {
365 silc_mp_mul_2exp(&mp_tmp, &mp_tmp, 8);
366 silc_mp_add_ui(&mp_tmp, &mp_tmp, src[i]);
369 silc_mp_out_str(stderr, 16, &mp_tmp);
372 rsa_en_de_crypt(&mp_dst, &mp_tmp, &key->d, &key->n);
374 fprintf(stderr, "\n");
375 silc_mp_out_str(stderr, 16, &mp_dst);
377 tmplen = (1024 + 7) / 8;
379 /* Format the MP int back into data */
380 for (i = tmplen; i > 0; i--) {
381 dst[i - 1] = (unsigned char)(silc_mp_get_ui(&mp_dst) & 0xff);
382 silc_mp_fdiv_q_2exp(&mp_dst, &mp_dst, 8);
386 silc_mp_clear(&mp_tmp);
387 silc_mp_clear(&mp_dst);
392 SILC_PKCS_API_SIGN(rsa)
394 RsaKey *key = (RsaKey *)context;
399 silc_mp_init_set_ui(&mp_tmp, 0);
400 silc_mp_init_set_ui(&mp_dst, 0);
402 /* Format the data into MP int */
403 for (i = 0; i < src_len; i++) {
404 silc_mp_mul_2exp(&mp_tmp, &mp_tmp, 8);
405 silc_mp_add_ui(&mp_tmp, &mp_tmp, src[i]);
409 rsa_en_de_crypt(&mp_dst, &mp_tmp, &key->d, &key->n);
411 tmplen = (1024 + 7) / 8;
413 /* Format the MP int back into data */
414 for (i = tmplen; i > 0; i--) {
415 dst[i - 1] = (unsigned char)(silc_mp_get_ui(&mp_dst) & 0xff);
416 silc_mp_fdiv_q_2exp(&mp_dst, &mp_dst, 8);
420 silc_mp_clear(&mp_tmp);
421 silc_mp_clear(&mp_dst);
426 SILC_PKCS_API_VERIFY(rsa)
428 RsaKey *key = (RsaKey *)context;
430 SilcInt mp_tmp, mp_tmp2;
433 silc_mp_init_set_ui(&mp_tmp, 0);
434 silc_mp_init_set_ui(&mp_tmp2, 0);
435 silc_mp_init_set_ui(&mp_dst, 0);
437 /* Format the signature into MP int */
438 for (i = 0; i < signature_len; i++) {
439 silc_mp_mul_2exp(&mp_tmp2, &mp_tmp2, 8);
440 silc_mp_add_ui(&mp_tmp2, &mp_tmp2, signature[i]);
444 rsa_en_de_crypt(&mp_dst, &mp_tmp2, &key->e, &key->n);
446 /* Format the data into MP int */
447 for (i = 0; i < data_len; i++) {
448 silc_mp_mul_2exp(&mp_tmp, &mp_tmp, 8);
449 silc_mp_add_ui(&mp_tmp, &mp_tmp, data[i]);
455 if ((silc_mp_cmp(&mp_tmp, &mp_dst)) != 0)
458 silc_mp_clear(&mp_tmp);
459 silc_mp_clear(&mp_tmp2);
460 silc_mp_clear(&mp_dst);
465 /* Generates RSA public and private keys. Primes p and q that are used
466 to compute the modulus n has to be generated before calling this. They
467 are then sent as argument for the function. */
469 void rsa_generate_keys(RsaKey *key, unsigned int bits,
470 SilcInt *p, SilcInt *q)
476 /* Initialize variables */
477 silc_mp_init(&key->p);
478 silc_mp_init(&key->q);
479 silc_mp_init(&key->n);
480 silc_mp_init(&key->e);
481 silc_mp_init(&key->d);
489 silc_mp_set(&key->p, p);
490 silc_mp_set(&key->q, q);
492 /* Compute modulus, n = p * q */
493 silc_mp_mul(&key->n, &key->p, &key->q);
495 /* phi = (p - 1) * (q - 1) */
496 silc_mp_sub_ui(&pm1, &key->p, 1);
497 silc_mp_sub_ui(&qm1, &key->q, 1);
498 silc_mp_mul(&phi, &pm1, &qm1);
500 /* Set e, the public exponent. We try to use same public exponent
501 for all keys. Also, to make encryption faster we use small
503 silc_mp_set_ui(&key->e, 127);
505 /* See if e is relatively prime to phi. gcd == greates common divisor,
506 if gcd equals 1 they are relatively prime. */
507 silc_mp_gcd(&hlp, &key->e, &phi);
508 if((silc_mp_cmp_ui(&hlp, 1)) > 0) {
509 silc_mp_add_ui(&key->e, &key->e, 2);
513 /* Find d, the private exponent. First we do phi / 2, to get it a
515 silc_mp_div_ui(&dq, &phi, 2);
516 silc_mp_modinv(&key->d, &key->e, &dq);
525 /* Clears whole key structure. */
527 void rsa_clear_keys(RsaKey *key)
530 silc_mp_clear(&key->p);
531 silc_mp_clear(&key->q);
532 silc_mp_clear(&key->n);
533 silc_mp_clear(&key->e);
534 silc_mp_clear(&key->d);
537 /* RSA encrypt/decrypt function. cm = ciphertext or plaintext,
538 mc = plaintext or ciphertext, expo = public or private exponent,
541 Encrypt: c = m ^ e mod n,
542 Decrypt: m = c ^ d mod n
545 void rsa_en_de_crypt(SilcInt *cm, SilcInt *mc,
546 SilcInt *expo, SilcInt *modu)
548 silc_mp_powm(cm, mc, expo, modu);