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
