• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
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 
17 struct 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 
crypto_rsa_parse_integer(const u8 * pos,const u8 * end,struct bignum * num)31 static 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  */
61 struct crypto_rsa_key *
crypto_rsa_import_public_key(const u8 * buf,size_t len)62 crypto_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 
113 error:
114 	crypto_rsa_free(key);
115 	return NULL;
116 }
117 
118 
119 struct crypto_rsa_key *
crypto_rsa_import_public_key_parts(const u8 * n,size_t n_len,const u8 * e,size_t e_len)120 crypto_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  */
148 struct crypto_rsa_key *
crypto_rsa_import_private_key(const u8 * buf,size_t len)149 crypto_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 
238 error:
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  */
crypto_rsa_get_modulus_len(struct crypto_rsa_key * key)249 size_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  */
crypto_rsa_exptmod(const u8 * in,size_t inlen,u8 * out,size_t * outlen,struct crypto_rsa_key * key,int use_private)265 int 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 
347 error:
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  */
crypto_rsa_free(struct crypto_rsa_key * key)362 void 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