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