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