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  	    !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   */
60  struct crypto_rsa_key *
crypto_rsa_import_public_key(const u8 * buf,size_t len)61  crypto_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  
108  error:
109  	crypto_rsa_free(key);
110  	return NULL;
111  }
112  
113  
114  struct crypto_rsa_key *
crypto_rsa_import_public_key_parts(const u8 * n,size_t n_len,const u8 * e,size_t e_len)115  crypto_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   */
143  struct crypto_rsa_key *
crypto_rsa_import_private_key(const u8 * buf,size_t len)144  crypto_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  
229  error:
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   */
crypto_rsa_get_modulus_len(struct crypto_rsa_key * key)240  size_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   */
crypto_rsa_exptmod(const u8 * in,size_t inlen,u8 * out,size_t * outlen,struct crypto_rsa_key * key,int use_private)256  int 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  
338  error:
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   */
crypto_rsa_free(struct crypto_rsa_key * key)353  void 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