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 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 * 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 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) 122 { 123 struct crypto_rsa_key *key; 124 125 key = os_zalloc(sizeof(*key)); 126 if (key == NULL) 127 return NULL; 128 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); 135 return NULL; 136 } 137 138 return key; 139 } 140 141 142 /** 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 147 */ 148 struct crypto_rsa_key * 149 crypto_rsa_import_private_key(const u8 *buf, size_t len) 150 { 151 struct crypto_rsa_key *key; 152 struct bignum *zero; 153 struct asn1_hdr hdr; 154 const u8 *pos, *end; 155 156 key = os_zalloc(sizeof(*key)); 157 if (key == NULL) 158 return NULL; 159 160 key->private_key = 1; 161 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(); 170 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); 175 return NULL; 176 } 177 178 /* 179 * PKCS #1, 7.2: 180 * RSAPrivateKey ::= SEQUENCE { 181 * version Version, 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 190 * } 191 * 192 * Version ::= INTEGER -- shall be 0 for this version of the standard 193 */ 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", 199 hdr.class, hdr.tag); 200 goto error; 201 } 202 pos = hdr.payload; 203 end = pos + hdr.length; 204 205 zero = bignum_init(); 206 if (zero == NULL) 207 goto error; 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"); 212 bignum_deinit(zero); 213 goto error; 214 } 215 bignum_deinit(zero); 216 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); 225 226 if (pos == NULL) 227 goto error; 228 229 if (pos != end) { 230 wpa_hexdump(MSG_DEBUG, 231 "RSA: Extra data in public key SEQUENCE", 232 pos, end - pos); 233 goto error; 234 } 235 236 return key; 237 238 error: 239 crypto_rsa_free(key); 240 return NULL; 241 } 242 243 244 /** 245 * crypto_rsa_get_modulus_len - Get the modulus length of the RSA key 246 * @key: RSA key 247 * Returns: Modulus length of the key 248 */ 249 size_t crypto_rsa_get_modulus_len(struct crypto_rsa_key *key) 250 { 251 return bignum_get_unsigned_bin_len(key->n); 252 } 253 254 255 /** 256 * crypto_rsa_exptmod - RSA modular exponentiation 257 * @in: Input data 258 * @inlen: Input data length 259 * @out: Buffer for output data 260 * @outlen: Maximum size of the output buffer and used size on success 261 * @key: RSA key 262 * @use_private: 1 = Use RSA private key, 0 = Use RSA public key 263 * Returns: 0 on success, -1 on failure 264 */ 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) 267 { 268 struct bignum *tmp, *a = NULL, *b = NULL; 269 int ret = -1; 270 size_t modlen; 271 272 if (use_private && !key->private_key) 273 return -1; 274 275 tmp = bignum_init(); 276 if (tmp == NULL) 277 return -1; 278 279 if (bignum_set_unsigned_bin(tmp, in, inlen) < 0) 280 goto error; 281 if (bignum_cmp(key->n, tmp) < 0) { 282 /* Too large input value for the RSA key modulus */ 283 goto error; 284 } 285 286 if (use_private) { 287 /* 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). 291 * 292 * dmp1 = (1/e) mod (p-1) 293 * dmq1 = (1/e) mod (q-1) 294 * iqmp = (1/q) mod p, where p > q 295 * m1 = c^dmp1 mod p 296 * m2 = c^dmq1 mod q 297 * h = q^-1 (m1 - m2) mod p 298 * m = m2 + hq 299 */ 300 a = bignum_init(); 301 b = bignum_init(); 302 if (a == NULL || b == NULL) 303 goto error; 304 305 /* a = tmp^dmp1 mod p */ 306 if (bignum_exptmod(tmp, key->dmp1, key->p, a) < 0) 307 goto error; 308 309 /* b = tmp^dmq1 mod q */ 310 if (bignum_exptmod(tmp, key->dmq1, key->q, b) < 0) 311 goto error; 312 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) 316 goto error; 317 318 /* tmp = b + q * tmp */ 319 if (bignum_mul(tmp, key->q, tmp) < 0 || 320 bignum_add(tmp, b, tmp) < 0) 321 goto error; 322 } else { 323 /* Encrypt (or verify signature) */ 324 /* tmp = tmp^e mod N */ 325 if (bignum_exptmod(tmp, key->e, key->n, tmp) < 0) 326 goto error; 327 } 328 329 modlen = crypto_rsa_get_modulus_len(key); 330 if (modlen > *outlen) { 331 *outlen = modlen; 332 goto error; 333 } 334 335 if (bignum_get_unsigned_bin_len(tmp) > modlen) 336 goto error; /* should never happen */ 337 338 *outlen = modlen; 339 os_memset(out, 0, modlen); 340 if (bignum_get_unsigned_bin( 341 tmp, out + 342 (modlen - bignum_get_unsigned_bin_len(tmp)), NULL) < 0) 343 goto error; 344 345 ret = 0; 346 347 error: 348 bignum_deinit(tmp); 349 bignum_deinit(a); 350 bignum_deinit(b); 351 return ret; 352 } 353 354 355 /** 356 * crypto_rsa_free - Free RSA key 357 * @key: RSA key to be freed 358 * 359 * This function frees an RSA key imported with either 360 * crypto_rsa_import_public_key() or crypto_rsa_import_private_key(). 361 */ 362 void crypto_rsa_free(struct crypto_rsa_key *key) 363 { 364 if (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); 373 os_free(key); 374 } 375 } 376