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