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