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
24struct 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
39static 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 */
69struct crypto_rsa_key *
70crypto_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
121error:
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 */
133struct crypto_rsa_key *
134crypto_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
223error:
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 */
235size_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 */
251int 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
333error:
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 */
348void 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