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