1 /* 2 * RSA 3 * Copyright (c) 2006, Jouni Malinen <j@w1.fi> 4 * 5 * This program is free software; you can redistribute it and/or modify 6 * it under the terms of the GNU General Public License version 2 as 7 * published by the Free Software Foundation. 8 * 9 * Alternatively, this software may be distributed under the terms of BSD 10 * license. 11 * 12 * See README and COPYING for more details. 13 */ 14 15 #include "includes.h" 16 17 #include "common.h" 18 #include "crypto.h" 19 #include "asn1.h" 20 #include "bignum.h" 21 #include "rsa.h" 22 23 24 struct crypto_rsa_key { 25 int private_key; /* whether private key is set */ 26 struct bignum *n; /* modulus (p * q) */ 27 struct bignum *e; /* public exponent */ 28 /* The following parameters are available only if private_key is set */ 29 struct bignum *d; /* private exponent */ 30 struct bignum *p; /* prime p (factor of n) */ 31 struct bignum *q; /* prime q (factor of n) */ 32 struct bignum *dmp1; /* d mod (p - 1); CRT exponent */ 33 struct bignum *dmq1; /* d mod (q - 1); CRT exponent */ 34 struct bignum *iqmp; /* 1 / q mod p; CRT coefficient */ 35 }; 36 37 38 #ifdef EAP_TLS_FUNCS 39 static const u8 * crypto_rsa_parse_integer(const u8 *pos, const u8 *end, 40 struct bignum *num) 41 { 42 struct asn1_hdr hdr; 43 44 if (pos == NULL) 45 return NULL; 46 47 if (asn1_get_next(pos, end - pos, &hdr) < 0 || 48 hdr.class != ASN1_CLASS_UNIVERSAL || hdr.tag != ASN1_TAG_INTEGER) { 49 wpa_printf(MSG_DEBUG, "RSA: Expected INTEGER - found class %d " 50 "tag 0x%x", hdr.class, hdr.tag); 51 return NULL; 52 } 53 54 if (bignum_set_unsigned_bin(num, hdr.payload, hdr.length) < 0) { 55 wpa_printf(MSG_DEBUG, "RSA: Failed to parse INTEGER"); 56 return NULL; 57 } 58 59 return hdr.payload + hdr.length; 60 } 61 62 63 /** 64 * crypto_rsa_import_public_key - Import an RSA public key 65 * @buf: Key buffer (DER encoded RSA public key) 66 * @len: Key buffer length in bytes 67 * Returns: Pointer to the public key or %NULL on failure 68 */ 69 struct crypto_rsa_key * 70 crypto_rsa_import_public_key(const u8 *buf, size_t len) 71 { 72 struct crypto_rsa_key *key; 73 struct asn1_hdr hdr; 74 const u8 *pos, *end; 75 76 key = os_zalloc(sizeof(*key)); 77 if (key == NULL) 78 return NULL; 79 80 key->n = bignum_init(); 81 key->e = bignum_init(); 82 if (key->n == NULL || key->e == NULL) { 83 crypto_rsa_free(key); 84 return NULL; 85 } 86 87 /* 88 * PKCS #1, 7.1: 89 * RSAPublicKey ::= SEQUENCE { 90 * modulus INTEGER, -- n 91 * publicExponent INTEGER -- e 92 * } 93 */ 94 95 if (asn1_get_next(buf, len, &hdr) < 0 || 96 hdr.class != ASN1_CLASS_UNIVERSAL || 97 hdr.tag != ASN1_TAG_SEQUENCE) { 98 wpa_printf(MSG_DEBUG, "RSA: Expected SEQUENCE " 99 "(public key) - found class %d tag 0x%x", 100 hdr.class, hdr.tag); 101 goto error; 102 } 103 pos = hdr.payload; 104 end = pos + hdr.length; 105 106 pos = crypto_rsa_parse_integer(pos, end, key->n); 107 pos = crypto_rsa_parse_integer(pos, end, key->e); 108 109 if (pos == NULL) 110 goto error; 111 112 if (pos != end) { 113 wpa_hexdump(MSG_DEBUG, 114 "RSA: Extra data in public key SEQUENCE", 115 pos, end - pos); 116 goto error; 117 } 118 119 return key; 120 121 error: 122 crypto_rsa_free(key); 123 return NULL; 124 } 125 126 127 /** 128 * crypto_rsa_import_private_key - Import an RSA private key 129 * @buf: Key buffer (DER encoded RSA private key) 130 * @len: Key buffer length in bytes 131 * Returns: Pointer to the private key or %NULL on failure 132 */ 133 struct crypto_rsa_key * 134 crypto_rsa_import_private_key(const u8 *buf, size_t len) 135 { 136 struct crypto_rsa_key *key; 137 struct bignum *zero; 138 struct asn1_hdr hdr; 139 const u8 *pos, *end; 140 141 key = os_zalloc(sizeof(*key)); 142 if (key == NULL) 143 return NULL; 144 145 key->private_key = 1; 146 147 key->n = bignum_init(); 148 key->e = bignum_init(); 149 key->d = bignum_init(); 150 key->p = bignum_init(); 151 key->q = bignum_init(); 152 key->dmp1 = bignum_init(); 153 key->dmq1 = bignum_init(); 154 key->iqmp = bignum_init(); 155 156 if (key->n == NULL || key->e == NULL || key->d == NULL || 157 key->p == NULL || key->q == NULL || key->dmp1 == NULL || 158 key->dmq1 == NULL || key->iqmp == NULL) { 159 crypto_rsa_free(key); 160 return NULL; 161 } 162 163 /* 164 * PKCS #1, 7.2: 165 * RSAPrivateKey ::= SEQUENCE { 166 * version Version, 167 * modulus INTEGER, -- n 168 * publicExponent INTEGER, -- e 169 * privateExponent INTEGER, -- d 170 * prime1 INTEGER, -- p 171 * prime2 INTEGER, -- q 172 * exponent1 INTEGER, -- d mod (p-1) 173 * exponent2 INTEGER, -- d mod (q-1) 174 * coefficient INTEGER -- (inverse of q) mod p 175 * } 176 * 177 * Version ::= INTEGER -- shall be 0 for this version of the standard 178 */ 179 if (asn1_get_next(buf, len, &hdr) < 0 || 180 hdr.class != ASN1_CLASS_UNIVERSAL || 181 hdr.tag != ASN1_TAG_SEQUENCE) { 182 wpa_printf(MSG_DEBUG, "RSA: Expected SEQUENCE " 183 "(public key) - found class %d tag 0x%x", 184 hdr.class, hdr.tag); 185 goto error; 186 } 187 pos = hdr.payload; 188 end = pos + hdr.length; 189 190 zero = bignum_init(); 191 if (zero == NULL) 192 goto error; 193 pos = crypto_rsa_parse_integer(pos, end, zero); 194 if (pos == NULL || bignum_cmp_d(zero, 0) != 0) { 195 wpa_printf(MSG_DEBUG, "RSA: Expected zero INTEGER in the " 196 "beginning of private key; not found"); 197 bignum_deinit(zero); 198 goto error; 199 } 200 bignum_deinit(zero); 201 202 pos = crypto_rsa_parse_integer(pos, end, key->n); 203 pos = crypto_rsa_parse_integer(pos, end, key->e); 204 pos = crypto_rsa_parse_integer(pos, end, key->d); 205 pos = crypto_rsa_parse_integer(pos, end, key->p); 206 pos = crypto_rsa_parse_integer(pos, end, key->q); 207 pos = crypto_rsa_parse_integer(pos, end, key->dmp1); 208 pos = crypto_rsa_parse_integer(pos, end, key->dmq1); 209 pos = crypto_rsa_parse_integer(pos, end, key->iqmp); 210 211 if (pos == NULL) 212 goto error; 213 214 if (pos != end) { 215 wpa_hexdump(MSG_DEBUG, 216 "RSA: Extra data in public key SEQUENCE", 217 pos, end - pos); 218 goto error; 219 } 220 221 return key; 222 223 error: 224 crypto_rsa_free(key); 225 return NULL; 226 } 227 #endif /* EAP_TLS_FUNCS */ 228 229 230 /** 231 * crypto_rsa_get_modulus_len - Get the modulus length of the RSA key 232 * @key: RSA key 233 * Returns: Modulus length of the key 234 */ 235 size_t crypto_rsa_get_modulus_len(struct crypto_rsa_key *key) 236 { 237 return bignum_get_unsigned_bin_len(key->n); 238 } 239 240 241 /** 242 * crypto_rsa_exptmod - RSA modular exponentiation 243 * @in: Input data 244 * @inlen: Input data length 245 * @out: Buffer for output data 246 * @outlen: Maximum size of the output buffer and used size on success 247 * @key: RSA key 248 * @use_private: 1 = Use RSA private key, 0 = Use RSA public key 249 * Returns: 0 on success, -1 on failure 250 */ 251 int crypto_rsa_exptmod(const u8 *in, size_t inlen, u8 *out, size_t *outlen, 252 struct crypto_rsa_key *key, int use_private) 253 { 254 struct bignum *tmp, *a = NULL, *b = NULL; 255 int ret = -1; 256 size_t modlen; 257 258 if (use_private && !key->private_key) 259 return -1; 260 261 tmp = bignum_init(); 262 if (tmp == NULL) 263 return -1; 264 265 if (bignum_set_unsigned_bin(tmp, in, inlen) < 0) 266 goto error; 267 if (bignum_cmp(key->n, tmp) < 0) { 268 /* Too large input value for the RSA key modulus */ 269 goto error; 270 } 271 272 if (use_private) { 273 /* 274 * Decrypt (or sign) using Chinese remainer theorem to speed 275 * up calculation. This is equivalent to tmp = tmp^d mod n 276 * (which would require more CPU to calculate directly). 277 * 278 * dmp1 = (1/e) mod (p-1) 279 * dmq1 = (1/e) mod (q-1) 280 * iqmp = (1/q) mod p, where p > q 281 * m1 = c^dmp1 mod p 282 * m2 = c^dmq1 mod q 283 * h = q^-1 (m1 - m2) mod p 284 * m = m2 + hq 285 */ 286 a = bignum_init(); 287 b = bignum_init(); 288 if (a == NULL || b == NULL) 289 goto error; 290 291 /* a = tmp^dmp1 mod p */ 292 if (bignum_exptmod(tmp, key->dmp1, key->p, a) < 0) 293 goto error; 294 295 /* b = tmp^dmq1 mod q */ 296 if (bignum_exptmod(tmp, key->dmq1, key->q, b) < 0) 297 goto error; 298 299 /* tmp = (a - b) * (1/q mod p) (mod p) */ 300 if (bignum_sub(a, b, tmp) < 0 || 301 bignum_mulmod(tmp, key->iqmp, key->p, tmp) < 0) 302 goto error; 303 304 /* tmp = b + q * tmp */ 305 if (bignum_mul(tmp, key->q, tmp) < 0 || 306 bignum_add(tmp, b, tmp) < 0) 307 goto error; 308 } else { 309 /* Encrypt (or verify signature) */ 310 /* tmp = tmp^e mod N */ 311 if (bignum_exptmod(tmp, key->e, key->n, tmp) < 0) 312 goto error; 313 } 314 315 modlen = crypto_rsa_get_modulus_len(key); 316 if (modlen > *outlen) { 317 *outlen = modlen; 318 goto error; 319 } 320 321 if (bignum_get_unsigned_bin_len(tmp) > modlen) 322 goto error; /* should never happen */ 323 324 *outlen = modlen; 325 os_memset(out, 0, modlen); 326 if (bignum_get_unsigned_bin( 327 tmp, out + 328 (modlen - bignum_get_unsigned_bin_len(tmp)), NULL) < 0) 329 goto error; 330 331 ret = 0; 332 333 error: 334 bignum_deinit(tmp); 335 bignum_deinit(a); 336 bignum_deinit(b); 337 return ret; 338 } 339 340 341 /** 342 * crypto_rsa_free - Free RSA key 343 * @key: RSA key to be freed 344 * 345 * This function frees an RSA key imported with either 346 * crypto_rsa_import_public_key() or crypto_rsa_import_private_key(). 347 */ 348 void crypto_rsa_free(struct crypto_rsa_key *key) 349 { 350 if (key) { 351 bignum_deinit(key->n); 352 bignum_deinit(key->e); 353 bignum_deinit(key->d); 354 bignum_deinit(key->p); 355 bignum_deinit(key->q); 356 bignum_deinit(key->dmp1); 357 bignum_deinit(key->dmq1); 358 bignum_deinit(key->iqmp); 359 os_free(key); 360 } 361 } 362