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