blob: 0239252959f0cd571813f845b41c26a773438339 [file] [log] [blame]
Damien Millerd4a8b7e1999-10-27 13:42:43 +10001/*
Damien Miller95def091999-11-25 00:26:21 +11002 *
3 * rsa.c
4 *
5 * Author: Tatu Ylonen <ylo@cs.hut.fi>
6 *
7 * Copyright (c) 1995 Tatu Ylonen <ylo@cs.hut.fi>, Espoo, Finland
8 * All rights reserved
9 *
10 * Created: Fri Mar 3 22:07:06 1995 ylo
11 *
12 * Description of the RSA algorithm can be found e.g. from the following sources:
13 *
14 * Bruce Schneier: Applied Cryptography. John Wiley & Sons, 1994.
15 *
16 * Jennifer Seberry and Josed Pieprzyk: Cryptography: An Introduction to
17 * Computer Security. Prentice-Hall, 1989.
18 *
19 * Man Young Rhee: Cryptography and Secure Data Communications. McGraw-Hill,
20 * 1994.
21 *
22 * R. Rivest, A. Shamir, and L. M. Adleman: Cryptographic Communications
23 * System and Method. US Patent 4,405,829, 1983.
24 *
25 * Hans Riesel: Prime Numbers and Computer Methods for Factorization.
26 * Birkhauser, 1994.
27 *
28 * The RSA Frequently Asked Questions document by RSA Data Security, Inc., 1995.
29 *
30 * RSA in 3 lines of perl by Adam Back <aba@atlax.ex.ac.uk>, 1995, as included
31 * below:
32 *
33 * [gone - had to be deleted - what a pity]
34 *
Damien Millerd4a8b7e1999-10-27 13:42:43 +100035*/
36
37#include "includes.h"
Damien Miller98c7ad62000-03-09 21:27:49 +110038RCSID("$Id: rsa.c,v 1.10 2000/03/09 10:27:51 damien Exp $");
Damien Millerd4a8b7e1999-10-27 13:42:43 +100039
40#include "rsa.h"
41#include "ssh.h"
42#include "xmalloc.h"
Damien Millerf07390e2000-01-29 20:40:22 +110043#include "random.h"
Damien Millerd4a8b7e1999-10-27 13:42:43 +100044
45int rsa_verbose = 1;
46
Damien Millercf87b5b2000-03-05 17:14:38 +110047/*
48 * Seed OpenSSL's random number generator
49 */
50void
51seed_rng()
52{
53 char buf[64];
54
55 get_random_bytes(buf, sizeof(buf));
56 RAND_seed(buf, sizeof(buf));
57 memset(buf, 0, sizeof(buf));
58}
59
Damien Millerd4a8b7e1999-10-27 13:42:43 +100060int
61rsa_alive()
62{
Damien Miller95def091999-11-25 00:26:21 +110063 RSA *key;
Damien Millerd4a8b7e1999-10-27 13:42:43 +100064
Damien Millerfac99cd2000-03-05 16:10:45 +110065 seed_rng();
Damien Miller95def091999-11-25 00:26:21 +110066 key = RSA_generate_key(32, 3, NULL, NULL);
67 if (key == NULL)
68 return (0);
69 RSA_free(key);
70 return (1);
Damien Millerd4a8b7e1999-10-27 13:42:43 +100071}
72
Damien Miller5428f641999-11-25 11:54:57 +110073/*
Damien Millerfdb5f131999-12-17 14:02:47 +110074 * Key generation progress meter callback
75 */
76void
77keygen_progress(int p, int n, void *arg)
78{
79 const char progress_chars[] = ".o+O?";
80
81 if ((p < 0) || (p > (sizeof(progress_chars) - 2)))
Damien Millerf07390e2000-01-29 20:40:22 +110082 p = sizeof(progress_chars) - 2;
Damien Millerfdb5f131999-12-17 14:02:47 +110083
Damien Millerf07390e2000-01-29 20:40:22 +110084 putchar(progress_chars[p]);
Damien Millerfdb5f131999-12-17 14:02:47 +110085 fflush(stdout);
86}
87
88/*
Damien Miller5428f641999-11-25 11:54:57 +110089 * Generates RSA public and private keys. This initializes the data
90 * structures; they should be freed with rsa_clear_private_key and
91 * rsa_clear_public_key.
92 */
Damien Millerd4a8b7e1999-10-27 13:42:43 +100093
94void
95rsa_generate_key(RSA *prv, RSA *pub, unsigned int bits)
96{
Damien Miller95def091999-11-25 00:26:21 +110097 RSA *key;
Damien Millerd4a8b7e1999-10-27 13:42:43 +100098
Damien Millerf07390e2000-01-29 20:40:22 +110099 seed_rng();
100
Damien Miller95def091999-11-25 00:26:21 +1100101 if (rsa_verbose) {
102 printf("Generating RSA keys: ");
103 fflush(stdout);
Damien Millerfdb5f131999-12-17 14:02:47 +1100104 key = RSA_generate_key(bits, 35, keygen_progress, NULL);
105 printf("\n");
106 } else {
107 key = RSA_generate_key(bits, 35, NULL, NULL);
Damien Miller95def091999-11-25 00:26:21 +1100108 }
Damien Miller95def091999-11-25 00:26:21 +1100109 if (key == NULL)
110 fatal("rsa_generate_key: key generation failed.");
Damien Millerd4a8b7e1999-10-27 13:42:43 +1000111
Damien Miller95def091999-11-25 00:26:21 +1100112 /* Copy public key parameters */
113 pub->n = BN_new();
114 BN_copy(pub->n, key->n);
115 pub->e = BN_new();
116 BN_copy(pub->e, key->e);
Damien Millerd4a8b7e1999-10-27 13:42:43 +1000117
Damien Miller95def091999-11-25 00:26:21 +1100118 /* Copy private key parameters */
119 prv->n = BN_new();
120 BN_copy(prv->n, key->n);
121 prv->e = BN_new();
122 BN_copy(prv->e, key->e);
123 prv->d = BN_new();
124 BN_copy(prv->d, key->d);
125 prv->p = BN_new();
126 BN_copy(prv->p, key->p);
127 prv->q = BN_new();
128 BN_copy(prv->q, key->q);
Damien Millerd4a8b7e1999-10-27 13:42:43 +1000129
Damien Miller95def091999-11-25 00:26:21 +1100130 prv->dmp1 = BN_new();
131 BN_copy(prv->dmp1, key->dmp1);
Damien Millerd4a8b7e1999-10-27 13:42:43 +1000132
Damien Miller95def091999-11-25 00:26:21 +1100133 prv->dmq1 = BN_new();
134 BN_copy(prv->dmq1, key->dmq1);
Damien Millerd4a8b7e1999-10-27 13:42:43 +1000135
Damien Miller95def091999-11-25 00:26:21 +1100136 prv->iqmp = BN_new();
137 BN_copy(prv->iqmp, key->iqmp);
Damien Millerd4a8b7e1999-10-27 13:42:43 +1000138
Damien Miller95def091999-11-25 00:26:21 +1100139 RSA_free(key);
Damien Millerd4a8b7e1999-10-27 13:42:43 +1000140
Damien Miller95def091999-11-25 00:26:21 +1100141 if (rsa_verbose)
142 printf("Key generation complete.\n");
Damien Millerd4a8b7e1999-10-27 13:42:43 +1000143}
144
145void
Damien Miller95def091999-11-25 00:26:21 +1100146rsa_public_encrypt(BIGNUM *out, BIGNUM *in, RSA *key)
Damien Millerd4a8b7e1999-10-27 13:42:43 +1000147{
Damien Miller95def091999-11-25 00:26:21 +1100148 char *inbuf, *outbuf;
149 int len, ilen, olen;
Damien Millerd4a8b7e1999-10-27 13:42:43 +1000150
Damien Miller95def091999-11-25 00:26:21 +1100151 if (BN_num_bits(key->e) < 2 || !BN_is_odd(key->e))
152 fatal("rsa_public_encrypt() exponent too small or not odd");
Damien Millerd4a8b7e1999-10-27 13:42:43 +1000153
Damien Miller95def091999-11-25 00:26:21 +1100154 olen = BN_num_bytes(key->n);
155 outbuf = xmalloc(olen);
Damien Millerd4a8b7e1999-10-27 13:42:43 +1000156
Damien Miller95def091999-11-25 00:26:21 +1100157 ilen = BN_num_bytes(in);
158 inbuf = xmalloc(ilen);
159 BN_bn2bin(in, inbuf);
Damien Millerd4a8b7e1999-10-27 13:42:43 +1000160
Damien Miller95def091999-11-25 00:26:21 +1100161 if ((len = RSA_public_encrypt(ilen, inbuf, outbuf, key,
Damien Miller98c7ad62000-03-09 21:27:49 +1100162 RSA_PKCS1_PADDING)) <= 0)
Damien Miller95def091999-11-25 00:26:21 +1100163 fatal("rsa_public_encrypt() failed");
Damien Millerd4a8b7e1999-10-27 13:42:43 +1000164
Damien Miller95def091999-11-25 00:26:21 +1100165 BN_bin2bn(outbuf, len, out);
Damien Millerd4a8b7e1999-10-27 13:42:43 +1000166
Damien Miller95def091999-11-25 00:26:21 +1100167 memset(outbuf, 0, olen);
168 memset(inbuf, 0, ilen);
169 xfree(outbuf);
170 xfree(inbuf);
Damien Millerd4a8b7e1999-10-27 13:42:43 +1000171}
172
173void
174rsa_private_decrypt(BIGNUM *out, BIGNUM *in, RSA *key)
175{
Damien Miller95def091999-11-25 00:26:21 +1100176 char *inbuf, *outbuf;
177 int len, ilen, olen;
Damien Millerd4a8b7e1999-10-27 13:42:43 +1000178
Damien Miller95def091999-11-25 00:26:21 +1100179 olen = BN_num_bytes(key->n);
180 outbuf = xmalloc(olen);
Damien Millerd4a8b7e1999-10-27 13:42:43 +1000181
Damien Miller95def091999-11-25 00:26:21 +1100182 ilen = BN_num_bytes(in);
183 inbuf = xmalloc(ilen);
184 BN_bn2bin(in, inbuf);
Damien Millerd4a8b7e1999-10-27 13:42:43 +1000185
Damien Miller95def091999-11-25 00:26:21 +1100186 if ((len = RSA_private_decrypt(ilen, inbuf, outbuf, key,
Damien Miller98c7ad62000-03-09 21:27:49 +1100187 RSA_PKCS1_PADDING)) <= 0)
Damien Miller95def091999-11-25 00:26:21 +1100188 fatal("rsa_private_decrypt() failed");
Damien Millerd4a8b7e1999-10-27 13:42:43 +1000189
Damien Miller95def091999-11-25 00:26:21 +1100190 BN_bin2bn(outbuf, len, out);
Damien Millerd4a8b7e1999-10-27 13:42:43 +1000191
Damien Miller95def091999-11-25 00:26:21 +1100192 memset(outbuf, 0, olen);
193 memset(inbuf, 0, ilen);
194 xfree(outbuf);
195 xfree(inbuf);
Damien Millerd4a8b7e1999-10-27 13:42:43 +1000196}
197
198/* Set whether to output verbose messages during key generation. */
199
200void
201rsa_set_verbose(int verbose)
202{
Damien Miller95def091999-11-25 00:26:21 +1100203 rsa_verbose = verbose;
Damien Millerd4a8b7e1999-10-27 13:42:43 +1000204}