3 * Copyright (c) 2006-2014, Jouni Malinen <j@w1.fi>
5 * This software may be distributed under the terms of the BSD license.
6 * See README for more details.
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 */
31 static const u8 * crypto_rsa_parse_integer(const u8 *pos, const u8 *end,
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);
46 if (bignum_set_unsigned_bin(num, hdr.payload, hdr.length) < 0) {
47 wpa_printf(MSG_DEBUG, "RSA: Failed to parse INTEGER");
51 return hdr.payload + hdr.length;
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
61 struct crypto_rsa_key *
62 crypto_rsa_import_public_key(const u8 *buf, size_t len)
64 struct crypto_rsa_key *key;
68 key = os_zalloc(sizeof(*key));
72 key->n = bignum_init();
73 key->e = bignum_init();
74 if (key->n == NULL || key->e == NULL) {
81 * RSAPublicKey ::= SEQUENCE {
82 * modulus INTEGER, -- n
83 * publicExponent INTEGER -- e
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",
96 end = pos + hdr.length;
98 pos = crypto_rsa_parse_integer(pos, end, key->n);
99 pos = crypto_rsa_parse_integer(pos, end, key->e);
105 wpa_hexdump(MSG_DEBUG,
106 "RSA: Extra data in public key SEQUENCE",
114 crypto_rsa_free(key);
119 struct crypto_rsa_key *
120 crypto_rsa_import_public_key_parts(const u8 *n, size_t n_len,
121 const u8 *e, size_t e_len)
123 struct crypto_rsa_key *key;
125 key = os_zalloc(sizeof(*key));
129 key->n = bignum_init();
130 key->e = bignum_init();
131 if (key->n == NULL || key->e == NULL ||
132 bignum_set_unsigned_bin(key->n, n, n_len) < 0 ||
133 bignum_set_unsigned_bin(key->e, e, e_len) < 0) {
134 crypto_rsa_free(key);
143 * crypto_rsa_import_private_key - Import an RSA private key
144 * @buf: Key buffer (DER encoded RSA private key)
145 * @len: Key buffer length in bytes
146 * Returns: Pointer to the private key or %NULL on failure
148 struct crypto_rsa_key *
149 crypto_rsa_import_private_key(const u8 *buf, size_t len)
151 struct crypto_rsa_key *key;
156 key = os_zalloc(sizeof(*key));
160 key->private_key = 1;
162 key->n = bignum_init();
163 key->e = bignum_init();
164 key->d = bignum_init();
165 key->p = bignum_init();
166 key->q = bignum_init();
167 key->dmp1 = bignum_init();
168 key->dmq1 = bignum_init();
169 key->iqmp = bignum_init();
171 if (key->n == NULL || key->e == NULL || key->d == NULL ||
172 key->p == NULL || key->q == NULL || key->dmp1 == NULL ||
173 key->dmq1 == NULL || key->iqmp == NULL) {
174 crypto_rsa_free(key);
180 * RSAPrivateKey ::= SEQUENCE {
182 * modulus INTEGER, -- n
183 * publicExponent INTEGER, -- e
184 * privateExponent INTEGER, -- d
185 * prime1 INTEGER, -- p
186 * prime2 INTEGER, -- q
187 * exponent1 INTEGER, -- d mod (p-1)
188 * exponent2 INTEGER, -- d mod (q-1)
189 * coefficient INTEGER -- (inverse of q) mod p
192 * Version ::= INTEGER -- shall be 0 for this version of the standard
194 if (asn1_get_next(buf, len, &hdr) < 0 ||
195 hdr.class != ASN1_CLASS_UNIVERSAL ||
196 hdr.tag != ASN1_TAG_SEQUENCE) {
197 wpa_printf(MSG_DEBUG, "RSA: Expected SEQUENCE "
198 "(public key) - found class %d tag 0x%x",
203 end = pos + hdr.length;
205 zero = bignum_init();
208 pos = crypto_rsa_parse_integer(pos, end, zero);
209 if (pos == NULL || bignum_cmp_d(zero, 0) != 0) {
210 wpa_printf(MSG_DEBUG, "RSA: Expected zero INTEGER in the "
211 "beginning of private key; not found");
217 pos = crypto_rsa_parse_integer(pos, end, key->n);
218 pos = crypto_rsa_parse_integer(pos, end, key->e);
219 pos = crypto_rsa_parse_integer(pos, end, key->d);
220 pos = crypto_rsa_parse_integer(pos, end, key->p);
221 pos = crypto_rsa_parse_integer(pos, end, key->q);
222 pos = crypto_rsa_parse_integer(pos, end, key->dmp1);
223 pos = crypto_rsa_parse_integer(pos, end, key->dmq1);
224 pos = crypto_rsa_parse_integer(pos, end, key->iqmp);
230 wpa_hexdump(MSG_DEBUG,
231 "RSA: Extra data in public key SEQUENCE",
239 crypto_rsa_free(key);
245 * crypto_rsa_get_modulus_len - Get the modulus length of the RSA key
247 * Returns: Modulus length of the key
249 size_t crypto_rsa_get_modulus_len(struct crypto_rsa_key *key)
251 return bignum_get_unsigned_bin_len(key->n);
256 * crypto_rsa_exptmod - RSA modular exponentiation
258 * @inlen: Input data length
259 * @out: Buffer for output data
260 * @outlen: Maximum size of the output buffer and used size on success
262 * @use_private: 1 = Use RSA private key, 0 = Use RSA public key
263 * Returns: 0 on success, -1 on failure
265 int crypto_rsa_exptmod(const u8 *in, size_t inlen, u8 *out, size_t *outlen,
266 struct crypto_rsa_key *key, int use_private)
268 struct bignum *tmp, *a = NULL, *b = NULL;
272 if (use_private && !key->private_key)
279 if (bignum_set_unsigned_bin(tmp, in, inlen) < 0)
281 if (bignum_cmp(key->n, tmp) < 0) {
282 /* Too large input value for the RSA key modulus */
288 * Decrypt (or sign) using Chinese remainer theorem to speed
289 * up calculation. This is equivalent to tmp = tmp^d mod n
290 * (which would require more CPU to calculate directly).
292 * dmp1 = (1/e) mod (p-1)
293 * dmq1 = (1/e) mod (q-1)
294 * iqmp = (1/q) mod p, where p > q
297 * h = q^-1 (m1 - m2) mod p
302 if (a == NULL || b == NULL)
305 /* a = tmp^dmp1 mod p */
306 if (bignum_exptmod(tmp, key->dmp1, key->p, a) < 0)
309 /* b = tmp^dmq1 mod q */
310 if (bignum_exptmod(tmp, key->dmq1, key->q, b) < 0)
313 /* tmp = (a - b) * (1/q mod p) (mod p) */
314 if (bignum_sub(a, b, tmp) < 0 ||
315 bignum_mulmod(tmp, key->iqmp, key->p, tmp) < 0)
318 /* tmp = b + q * tmp */
319 if (bignum_mul(tmp, key->q, tmp) < 0 ||
320 bignum_add(tmp, b, tmp) < 0)
323 /* Encrypt (or verify signature) */
324 /* tmp = tmp^e mod N */
325 if (bignum_exptmod(tmp, key->e, key->n, tmp) < 0)
329 modlen = crypto_rsa_get_modulus_len(key);
330 if (modlen > *outlen) {
335 if (bignum_get_unsigned_bin_len(tmp) > modlen)
336 goto error; /* should never happen */
339 os_memset(out, 0, modlen);
340 if (bignum_get_unsigned_bin(
342 (modlen - bignum_get_unsigned_bin_len(tmp)), NULL) < 0)
356 * crypto_rsa_free - Free RSA key
357 * @key: RSA key to be freed
359 * This function frees an RSA key imported with either
360 * crypto_rsa_import_public_key() or crypto_rsa_import_private_key().
362 void crypto_rsa_free(struct crypto_rsa_key *key)
365 bignum_deinit(key->n);
366 bignum_deinit(key->e);
367 bignum_deinit(key->d);
368 bignum_deinit(key->p);
369 bignum_deinit(key->q);
370 bignum_deinit(key->dmp1);
371 bignum_deinit(key->dmq1);
372 bignum_deinit(key->iqmp);