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