1 /*
2 * RSA
3 * Copyright (c) 2006, 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 /**
120 * crypto_rsa_import_private_key - Import an RSA private key
121 * @buf: Key buffer (DER encoded RSA private key)
122 * @len: Key buffer length in bytes
123 * Returns: Pointer to the private key or %NULL on failure
124 */
125 struct crypto_rsa_key *
crypto_rsa_import_private_key(const u8 * buf,size_t len)126 crypto_rsa_import_private_key(const u8 *buf, size_t len)
127 {
128 struct crypto_rsa_key *key;
129 struct bignum *zero;
130 struct asn1_hdr hdr;
131 const u8 *pos, *end;
132
133 key = os_zalloc(sizeof(*key));
134 if (key == NULL)
135 return NULL;
136
137 key->private_key = 1;
138
139 key->n = bignum_init();
140 key->e = bignum_init();
141 key->d = bignum_init();
142 key->p = bignum_init();
143 key->q = bignum_init();
144 key->dmp1 = bignum_init();
145 key->dmq1 = bignum_init();
146 key->iqmp = bignum_init();
147
148 if (key->n == NULL || key->e == NULL || key->d == NULL ||
149 key->p == NULL || key->q == NULL || key->dmp1 == NULL ||
150 key->dmq1 == NULL || key->iqmp == NULL) {
151 crypto_rsa_free(key);
152 return NULL;
153 }
154
155 /*
156 * PKCS #1, 7.2:
157 * RSAPrivateKey ::= SEQUENCE {
158 * version Version,
159 * modulus INTEGER, -- n
160 * publicExponent INTEGER, -- e
161 * privateExponent INTEGER, -- d
162 * prime1 INTEGER, -- p
163 * prime2 INTEGER, -- q
164 * exponent1 INTEGER, -- d mod (p-1)
165 * exponent2 INTEGER, -- d mod (q-1)
166 * coefficient INTEGER -- (inverse of q) mod p
167 * }
168 *
169 * Version ::= INTEGER -- shall be 0 for this version of the standard
170 */
171 if (asn1_get_next(buf, len, &hdr) < 0 ||
172 hdr.class != ASN1_CLASS_UNIVERSAL ||
173 hdr.tag != ASN1_TAG_SEQUENCE) {
174 wpa_printf(MSG_DEBUG, "RSA: Expected SEQUENCE "
175 "(public key) - found class %d tag 0x%x",
176 hdr.class, hdr.tag);
177 goto error;
178 }
179 pos = hdr.payload;
180 end = pos + hdr.length;
181
182 zero = bignum_init();
183 if (zero == NULL)
184 goto error;
185 pos = crypto_rsa_parse_integer(pos, end, zero);
186 if (pos == NULL || bignum_cmp_d(zero, 0) != 0) {
187 wpa_printf(MSG_DEBUG, "RSA: Expected zero INTEGER in the "
188 "beginning of private key; not found");
189 bignum_deinit(zero);
190 goto error;
191 }
192 bignum_deinit(zero);
193
194 pos = crypto_rsa_parse_integer(pos, end, key->n);
195 pos = crypto_rsa_parse_integer(pos, end, key->e);
196 pos = crypto_rsa_parse_integer(pos, end, key->d);
197 pos = crypto_rsa_parse_integer(pos, end, key->p);
198 pos = crypto_rsa_parse_integer(pos, end, key->q);
199 pos = crypto_rsa_parse_integer(pos, end, key->dmp1);
200 pos = crypto_rsa_parse_integer(pos, end, key->dmq1);
201 pos = crypto_rsa_parse_integer(pos, end, key->iqmp);
202
203 if (pos == NULL)
204 goto error;
205
206 if (pos != end) {
207 wpa_hexdump(MSG_DEBUG,
208 "RSA: Extra data in public key SEQUENCE",
209 pos, end - pos);
210 goto error;
211 }
212
213 return key;
214
215 error:
216 crypto_rsa_free(key);
217 return NULL;
218 }
219
220
221 /**
222 * crypto_rsa_get_modulus_len - Get the modulus length of the RSA key
223 * @key: RSA key
224 * Returns: Modulus length of the key
225 */
crypto_rsa_get_modulus_len(struct crypto_rsa_key * key)226 size_t crypto_rsa_get_modulus_len(struct crypto_rsa_key *key)
227 {
228 return bignum_get_unsigned_bin_len(key->n);
229 }
230
231
232 /**
233 * crypto_rsa_exptmod - RSA modular exponentiation
234 * @in: Input data
235 * @inlen: Input data length
236 * @out: Buffer for output data
237 * @outlen: Maximum size of the output buffer and used size on success
238 * @key: RSA key
239 * @use_private: 1 = Use RSA private key, 0 = Use RSA public key
240 * Returns: 0 on success, -1 on failure
241 */
crypto_rsa_exptmod(const u8 * in,size_t inlen,u8 * out,size_t * outlen,struct crypto_rsa_key * key,int use_private)242 int crypto_rsa_exptmod(const u8 *in, size_t inlen, u8 *out, size_t *outlen,
243 struct crypto_rsa_key *key, int use_private)
244 {
245 struct bignum *tmp, *a = NULL, *b = NULL;
246 int ret = -1;
247 size_t modlen;
248
249 if (use_private && !key->private_key)
250 return -1;
251
252 tmp = bignum_init();
253 if (tmp == NULL)
254 return -1;
255
256 if (bignum_set_unsigned_bin(tmp, in, inlen) < 0)
257 goto error;
258 if (bignum_cmp(key->n, tmp) < 0) {
259 /* Too large input value for the RSA key modulus */
260 goto error;
261 }
262
263 if (use_private) {
264 /*
265 * Decrypt (or sign) using Chinese remainer theorem to speed
266 * up calculation. This is equivalent to tmp = tmp^d mod n
267 * (which would require more CPU to calculate directly).
268 *
269 * dmp1 = (1/e) mod (p-1)
270 * dmq1 = (1/e) mod (q-1)
271 * iqmp = (1/q) mod p, where p > q
272 * m1 = c^dmp1 mod p
273 * m2 = c^dmq1 mod q
274 * h = q^-1 (m1 - m2) mod p
275 * m = m2 + hq
276 */
277 a = bignum_init();
278 b = bignum_init();
279 if (a == NULL || b == NULL)
280 goto error;
281
282 /* a = tmp^dmp1 mod p */
283 if (bignum_exptmod(tmp, key->dmp1, key->p, a) < 0)
284 goto error;
285
286 /* b = tmp^dmq1 mod q */
287 if (bignum_exptmod(tmp, key->dmq1, key->q, b) < 0)
288 goto error;
289
290 /* tmp = (a - b) * (1/q mod p) (mod p) */
291 if (bignum_sub(a, b, tmp) < 0 ||
292 bignum_mulmod(tmp, key->iqmp, key->p, tmp) < 0)
293 goto error;
294
295 /* tmp = b + q * tmp */
296 if (bignum_mul(tmp, key->q, tmp) < 0 ||
297 bignum_add(tmp, b, tmp) < 0)
298 goto error;
299 } else {
300 /* Encrypt (or verify signature) */
301 /* tmp = tmp^e mod N */
302 if (bignum_exptmod(tmp, key->e, key->n, tmp) < 0)
303 goto error;
304 }
305
306 modlen = crypto_rsa_get_modulus_len(key);
307 if (modlen > *outlen) {
308 *outlen = modlen;
309 goto error;
310 }
311
312 if (bignum_get_unsigned_bin_len(tmp) > modlen)
313 goto error; /* should never happen */
314
315 *outlen = modlen;
316 os_memset(out, 0, modlen);
317 if (bignum_get_unsigned_bin(
318 tmp, out +
319 (modlen - bignum_get_unsigned_bin_len(tmp)), NULL) < 0)
320 goto error;
321
322 ret = 0;
323
324 error:
325 bignum_deinit(tmp);
326 bignum_deinit(a);
327 bignum_deinit(b);
328 return ret;
329 }
330
331
332 /**
333 * crypto_rsa_free - Free RSA key
334 * @key: RSA key to be freed
335 *
336 * This function frees an RSA key imported with either
337 * crypto_rsa_import_public_key() or crypto_rsa_import_private_key().
338 */
crypto_rsa_free(struct crypto_rsa_key * key)339 void crypto_rsa_free(struct crypto_rsa_key *key)
340 {
341 if (key) {
342 bignum_deinit(key->n);
343 bignum_deinit(key->e);
344 bignum_deinit(key->d);
345 bignum_deinit(key->p);
346 bignum_deinit(key->q);
347 bignum_deinit(key->dmp1);
348 bignum_deinit(key->dmq1);
349 bignum_deinit(key->iqmp);
350 os_free(key);
351 }
352 }
353