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