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
24 struct 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
crypto_rsa_parse_integer(const u8 * pos,const u8 * end,struct bignum * num)38 static 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 */
68 struct crypto_rsa_key *
crypto_rsa_import_public_key(const u8 * buf,size_t len)69 crypto_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
120 error:
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 */
132 struct crypto_rsa_key *
crypto_rsa_import_private_key(const u8 * buf,size_t len)133 crypto_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
222 error:
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 */
crypto_rsa_get_modulus_len(struct crypto_rsa_key * key)233 size_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 */
crypto_rsa_exptmod(const u8 * in,size_t inlen,u8 * out,size_t * outlen,struct crypto_rsa_key * key,int use_private)249 int 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
331 error:
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 */
crypto_rsa_free(struct crypto_rsa_key * key)346 void 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