1 /*
2 * RSA
3 * Copyright (c) 2006, Jouni Malinen <j@w1.fi>
4 *
5 * This program is free software; you can redistribute it and/or modify
6 * it under the terms of the GNU General Public License version 2 as
7 * published by the Free Software Foundation.
8 *
9 * Alternatively, this software may be distributed under the terms of BSD
10 * license.
11 *
12 * See README and COPYING for more details.
13 */
14
15 #include "includes.h"
16
17 #include "common.h"
18 #include "crypto.h"
19 #include "asn1.h"
20 #include "bignum.h"
21 #include "rsa.h"
22
23
24 struct crypto_rsa_key {
25 int private_key; /* whether private key is set */
26 struct bignum *n; /* modulus (p * q) */
27 struct bignum *e; /* public exponent */
28 /* The following parameters are available only if private_key is set */
29 struct bignum *d; /* private exponent */
30 struct bignum *p; /* prime p (factor of n) */
31 struct bignum *q; /* prime q (factor of n) */
32 struct bignum *dmp1; /* d mod (p - 1); CRT exponent */
33 struct bignum *dmq1; /* d mod (q - 1); CRT exponent */
34 struct bignum *iqmp; /* 1 / q mod p; CRT coefficient */
35 };
36
37
38 #ifdef EAP_TLS_FUNCS
crypto_rsa_parse_integer(const u8 * pos,const u8 * end,struct bignum * num)39 static const u8 * crypto_rsa_parse_integer(const u8 *pos, const u8 *end,
40 struct bignum *num)
41 {
42 struct asn1_hdr hdr;
43
44 if (pos == NULL)
45 return NULL;
46
47 if (asn1_get_next(pos, end - pos, &hdr) < 0 ||
48 hdr.class != ASN1_CLASS_UNIVERSAL || hdr.tag != ASN1_TAG_INTEGER) {
49 wpa_printf(MSG_DEBUG, "RSA: Expected INTEGER - found class %d "
50 "tag 0x%x", hdr.class, hdr.tag);
51 return NULL;
52 }
53
54 if (bignum_set_unsigned_bin(num, hdr.payload, hdr.length) < 0) {
55 wpa_printf(MSG_DEBUG, "RSA: Failed to parse INTEGER");
56 return NULL;
57 }
58
59 return hdr.payload + hdr.length;
60 }
61
62
63 /**
64 * crypto_rsa_import_public_key - Import an RSA public key
65 * @buf: Key buffer (DER encoded RSA public key)
66 * @len: Key buffer length in bytes
67 * Returns: Pointer to the public key or %NULL on failure
68 */
69 struct crypto_rsa_key *
crypto_rsa_import_public_key(const u8 * buf,size_t len)70 crypto_rsa_import_public_key(const u8 *buf, size_t len)
71 {
72 struct crypto_rsa_key *key;
73 struct asn1_hdr hdr;
74 const u8 *pos, *end;
75
76 key = os_zalloc(sizeof(*key));
77 if (key == NULL)
78 return NULL;
79
80 key->n = bignum_init();
81 key->e = bignum_init();
82 if (key->n == NULL || key->e == NULL) {
83 crypto_rsa_free(key);
84 return NULL;
85 }
86
87 /*
88 * PKCS #1, 7.1:
89 * RSAPublicKey ::= SEQUENCE {
90 * modulus INTEGER, -- n
91 * publicExponent INTEGER -- e
92 * }
93 */
94
95 if (asn1_get_next(buf, len, &hdr) < 0 ||
96 hdr.class != ASN1_CLASS_UNIVERSAL ||
97 hdr.tag != ASN1_TAG_SEQUENCE) {
98 wpa_printf(MSG_DEBUG, "RSA: Expected SEQUENCE "
99 "(public key) - found class %d tag 0x%x",
100 hdr.class, hdr.tag);
101 goto error;
102 }
103 pos = hdr.payload;
104 end = pos + hdr.length;
105
106 pos = crypto_rsa_parse_integer(pos, end, key->n);
107 pos = crypto_rsa_parse_integer(pos, end, key->e);
108
109 if (pos == NULL)
110 goto error;
111
112 if (pos != end) {
113 wpa_hexdump(MSG_DEBUG,
114 "RSA: Extra data in public key SEQUENCE",
115 pos, end - pos);
116 goto error;
117 }
118
119 return key;
120
121 error:
122 crypto_rsa_free(key);
123 return NULL;
124 }
125
126
127 /**
128 * crypto_rsa_import_private_key - Import an RSA private key
129 * @buf: Key buffer (DER encoded RSA private key)
130 * @len: Key buffer length in bytes
131 * Returns: Pointer to the private key or %NULL on failure
132 */
133 struct crypto_rsa_key *
crypto_rsa_import_private_key(const u8 * buf,size_t len)134 crypto_rsa_import_private_key(const u8 *buf, size_t len)
135 {
136 struct crypto_rsa_key *key;
137 struct bignum *zero;
138 struct asn1_hdr hdr;
139 const u8 *pos, *end;
140
141 key = os_zalloc(sizeof(*key));
142 if (key == NULL)
143 return NULL;
144
145 key->private_key = 1;
146
147 key->n = bignum_init();
148 key->e = bignum_init();
149 key->d = bignum_init();
150 key->p = bignum_init();
151 key->q = bignum_init();
152 key->dmp1 = bignum_init();
153 key->dmq1 = bignum_init();
154 key->iqmp = bignum_init();
155
156 if (key->n == NULL || key->e == NULL || key->d == NULL ||
157 key->p == NULL || key->q == NULL || key->dmp1 == NULL ||
158 key->dmq1 == NULL || key->iqmp == NULL) {
159 crypto_rsa_free(key);
160 return NULL;
161 }
162
163 /*
164 * PKCS #1, 7.2:
165 * RSAPrivateKey ::= SEQUENCE {
166 * version Version,
167 * modulus INTEGER, -- n
168 * publicExponent INTEGER, -- e
169 * privateExponent INTEGER, -- d
170 * prime1 INTEGER, -- p
171 * prime2 INTEGER, -- q
172 * exponent1 INTEGER, -- d mod (p-1)
173 * exponent2 INTEGER, -- d mod (q-1)
174 * coefficient INTEGER -- (inverse of q) mod p
175 * }
176 *
177 * Version ::= INTEGER -- shall be 0 for this version of the standard
178 */
179 if (asn1_get_next(buf, len, &hdr) < 0 ||
180 hdr.class != ASN1_CLASS_UNIVERSAL ||
181 hdr.tag != ASN1_TAG_SEQUENCE) {
182 wpa_printf(MSG_DEBUG, "RSA: Expected SEQUENCE "
183 "(public key) - found class %d tag 0x%x",
184 hdr.class, hdr.tag);
185 goto error;
186 }
187 pos = hdr.payload;
188 end = pos + hdr.length;
189
190 zero = bignum_init();
191 if (zero == NULL)
192 goto error;
193 pos = crypto_rsa_parse_integer(pos, end, zero);
194 if (pos == NULL || bignum_cmp_d(zero, 0) != 0) {
195 wpa_printf(MSG_DEBUG, "RSA: Expected zero INTEGER in the "
196 "beginning of private key; not found");
197 bignum_deinit(zero);
198 goto error;
199 }
200 bignum_deinit(zero);
201
202 pos = crypto_rsa_parse_integer(pos, end, key->n);
203 pos = crypto_rsa_parse_integer(pos, end, key->e);
204 pos = crypto_rsa_parse_integer(pos, end, key->d);
205 pos = crypto_rsa_parse_integer(pos, end, key->p);
206 pos = crypto_rsa_parse_integer(pos, end, key->q);
207 pos = crypto_rsa_parse_integer(pos, end, key->dmp1);
208 pos = crypto_rsa_parse_integer(pos, end, key->dmq1);
209 pos = crypto_rsa_parse_integer(pos, end, key->iqmp);
210
211 if (pos == NULL)
212 goto error;
213
214 if (pos != end) {
215 wpa_hexdump(MSG_DEBUG,
216 "RSA: Extra data in public key SEQUENCE",
217 pos, end - pos);
218 goto error;
219 }
220
221 return key;
222
223 error:
224 crypto_rsa_free(key);
225 return NULL;
226 }
227 #endif /* EAP_TLS_FUNCS */
228
229
230 /**
231 * crypto_rsa_get_modulus_len - Get the modulus length of the RSA key
232 * @key: RSA key
233 * Returns: Modulus length of the key
234 */
crypto_rsa_get_modulus_len(struct crypto_rsa_key * key)235 size_t crypto_rsa_get_modulus_len(struct crypto_rsa_key *key)
236 {
237 return bignum_get_unsigned_bin_len(key->n);
238 }
239
240
241 /**
242 * crypto_rsa_exptmod - RSA modular exponentiation
243 * @in: Input data
244 * @inlen: Input data length
245 * @out: Buffer for output data
246 * @outlen: Maximum size of the output buffer and used size on success
247 * @key: RSA key
248 * @use_private: 1 = Use RSA private key, 0 = Use RSA public key
249 * Returns: 0 on success, -1 on failure
250 */
crypto_rsa_exptmod(const u8 * in,size_t inlen,u8 * out,size_t * outlen,struct crypto_rsa_key * key,int use_private)251 int crypto_rsa_exptmod(const u8 *in, size_t inlen, u8 *out, size_t *outlen,
252 struct crypto_rsa_key *key, int use_private)
253 {
254 struct bignum *tmp, *a = NULL, *b = NULL;
255 int ret = -1;
256 size_t modlen;
257
258 if (use_private && !key->private_key)
259 return -1;
260
261 tmp = bignum_init();
262 if (tmp == NULL)
263 return -1;
264
265 if (bignum_set_unsigned_bin(tmp, in, inlen) < 0)
266 goto error;
267 if (bignum_cmp(key->n, tmp) < 0) {
268 /* Too large input value for the RSA key modulus */
269 goto error;
270 }
271
272 if (use_private) {
273 /*
274 * Decrypt (or sign) using Chinese remainer theorem to speed
275 * up calculation. This is equivalent to tmp = tmp^d mod n
276 * (which would require more CPU to calculate directly).
277 *
278 * dmp1 = (1/e) mod (p-1)
279 * dmq1 = (1/e) mod (q-1)
280 * iqmp = (1/q) mod p, where p > q
281 * m1 = c^dmp1 mod p
282 * m2 = c^dmq1 mod q
283 * h = q^-1 (m1 - m2) mod p
284 * m = m2 + hq
285 */
286 a = bignum_init();
287 b = bignum_init();
288 if (a == NULL || b == NULL)
289 goto error;
290
291 /* a = tmp^dmp1 mod p */
292 if (bignum_exptmod(tmp, key->dmp1, key->p, a) < 0)
293 goto error;
294
295 /* b = tmp^dmq1 mod q */
296 if (bignum_exptmod(tmp, key->dmq1, key->q, b) < 0)
297 goto error;
298
299 /* tmp = (a - b) * (1/q mod p) (mod p) */
300 if (bignum_sub(a, b, tmp) < 0 ||
301 bignum_mulmod(tmp, key->iqmp, key->p, tmp) < 0)
302 goto error;
303
304 /* tmp = b + q * tmp */
305 if (bignum_mul(tmp, key->q, tmp) < 0 ||
306 bignum_add(tmp, b, tmp) < 0)
307 goto error;
308 } else {
309 /* Encrypt (or verify signature) */
310 /* tmp = tmp^e mod N */
311 if (bignum_exptmod(tmp, key->e, key->n, tmp) < 0)
312 goto error;
313 }
314
315 modlen = crypto_rsa_get_modulus_len(key);
316 if (modlen > *outlen) {
317 *outlen = modlen;
318 goto error;
319 }
320
321 if (bignum_get_unsigned_bin_len(tmp) > modlen)
322 goto error; /* should never happen */
323
324 *outlen = modlen;
325 os_memset(out, 0, modlen);
326 if (bignum_get_unsigned_bin(
327 tmp, out +
328 (modlen - bignum_get_unsigned_bin_len(tmp)), NULL) < 0)
329 goto error;
330
331 ret = 0;
332
333 error:
334 bignum_deinit(tmp);
335 bignum_deinit(a);
336 bignum_deinit(b);
337 return ret;
338 }
339
340
341 /**
342 * crypto_rsa_free - Free RSA key
343 * @key: RSA key to be freed
344 *
345 * This function frees an RSA key imported with either
346 * crypto_rsa_import_public_key() or crypto_rsa_import_private_key().
347 */
crypto_rsa_free(struct crypto_rsa_key * key)348 void crypto_rsa_free(struct crypto_rsa_key *key)
349 {
350 if (key) {
351 bignum_deinit(key->n);
352 bignum_deinit(key->e);
353 bignum_deinit(key->d);
354 bignum_deinit(key->p);
355 bignum_deinit(key->q);
356 bignum_deinit(key->dmp1);
357 bignum_deinit(key->dmq1);
358 bignum_deinit(key->iqmp);
359 os_free(key);
360 }
361 }
362