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 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 * 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 * 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 * 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 */ 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 */ 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 */ 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