$search
00001 /* 00002 * RSA 00003 * Copyright (c) 2006, Jouni Malinen <j@w1.fi> 00004 * 00005 * This program is free software; you can redistribute it and/or modify 00006 * it under the terms of the GNU General Public License version 2 as 00007 * published by the Free Software Foundation. 00008 * 00009 * Alternatively, this software may be distributed under the terms of BSD 00010 * license. 00011 * 00012 * See README and COPYING for more details. 00013 */ 00014 00015 #include "includes.h" 00016 00017 #include "common.h" 00018 #include "asn1.h" 00019 #include "bignum.h" 00020 #include "rsa.h" 00021 00022 00023 struct crypto_rsa_key { 00024 int private_key; /* whether private key is set */ 00025 struct bignum *n; /* modulus (p * q) */ 00026 struct bignum *e; /* public exponent */ 00027 /* The following parameters are available only if private_key is set */ 00028 struct bignum *d; /* private exponent */ 00029 struct bignum *p; /* prime p (factor of n) */ 00030 struct bignum *q; /* prime q (factor of n) */ 00031 struct bignum *dmp1; /* d mod (p - 1); CRT exponent */ 00032 struct bignum *dmq1; /* d mod (q - 1); CRT exponent */ 00033 struct bignum *iqmp; /* 1 / q mod p; CRT coefficient */ 00034 }; 00035 00036 00037 static const u8 * crypto_rsa_parse_integer(const u8 *pos, const u8 *end, 00038 struct bignum *num) 00039 { 00040 struct asn1_hdr hdr; 00041 00042 if (pos == NULL) 00043 return NULL; 00044 00045 if (asn1_get_next(pos, end - pos, &hdr) < 0 || 00046 hdr.class != ASN1_CLASS_UNIVERSAL || hdr.tag != ASN1_TAG_INTEGER) { 00047 wpa_printf(MSG_DEBUG, "RSA: Expected INTEGER - found class %d " 00048 "tag 0x%x", hdr.class, hdr.tag); 00049 return NULL; 00050 } 00051 00052 if (bignum_set_unsigned_bin(num, hdr.payload, hdr.length) < 0) { 00053 wpa_printf(MSG_DEBUG, "RSA: Failed to parse INTEGER"); 00054 return NULL; 00055 } 00056 00057 return hdr.payload + hdr.length; 00058 } 00059 00060 00067 struct crypto_rsa_key * 00068 crypto_rsa_import_public_key(const u8 *buf, size_t len) 00069 { 00070 struct crypto_rsa_key *key; 00071 struct asn1_hdr hdr; 00072 const u8 *pos, *end; 00073 00074 key = os_zalloc(sizeof(*key)); 00075 if (key == NULL) 00076 return NULL; 00077 00078 key->n = bignum_init(); 00079 key->e = bignum_init(); 00080 if (key->n == NULL || key->e == NULL) { 00081 crypto_rsa_free(key); 00082 return NULL; 00083 } 00084 00085 /* 00086 * PKCS #1, 7.1: 00087 * RSAPublicKey ::= SEQUENCE { 00088 * modulus INTEGER, -- n 00089 * publicExponent INTEGER -- e 00090 * } 00091 */ 00092 00093 if (asn1_get_next(buf, len, &hdr) < 0 || 00094 hdr.class != ASN1_CLASS_UNIVERSAL || 00095 hdr.tag != ASN1_TAG_SEQUENCE) { 00096 wpa_printf(MSG_DEBUG, "RSA: Expected SEQUENCE " 00097 "(public key) - found class %d tag 0x%x", 00098 hdr.class, hdr.tag); 00099 goto error; 00100 } 00101 pos = hdr.payload; 00102 end = pos + hdr.length; 00103 00104 pos = crypto_rsa_parse_integer(pos, end, key->n); 00105 pos = crypto_rsa_parse_integer(pos, end, key->e); 00106 00107 if (pos == NULL) 00108 goto error; 00109 00110 if (pos != end) { 00111 wpa_hexdump(MSG_DEBUG, 00112 "RSA: Extra data in public key SEQUENCE", 00113 pos, end - pos); 00114 goto error; 00115 } 00116 00117 return key; 00118 00119 error: 00120 crypto_rsa_free(key); 00121 return NULL; 00122 } 00123 00124 00131 struct crypto_rsa_key * 00132 crypto_rsa_import_private_key(const u8 *buf, size_t len) 00133 { 00134 struct crypto_rsa_key *key; 00135 struct bignum *zero; 00136 struct asn1_hdr hdr; 00137 const u8 *pos, *end; 00138 00139 key = os_zalloc(sizeof(*key)); 00140 if (key == NULL) 00141 return NULL; 00142 00143 key->private_key = 1; 00144 00145 key->n = bignum_init(); 00146 key->e = bignum_init(); 00147 key->d = bignum_init(); 00148 key->p = bignum_init(); 00149 key->q = bignum_init(); 00150 key->dmp1 = bignum_init(); 00151 key->dmq1 = bignum_init(); 00152 key->iqmp = bignum_init(); 00153 00154 if (key->n == NULL || key->e == NULL || key->d == NULL || 00155 key->p == NULL || key->q == NULL || key->dmp1 == NULL || 00156 key->dmq1 == NULL || key->iqmp == NULL) { 00157 crypto_rsa_free(key); 00158 return NULL; 00159 } 00160 00161 /* 00162 * PKCS #1, 7.2: 00163 * RSAPrivateKey ::= SEQUENCE { 00164 * version Version, 00165 * modulus INTEGER, -- n 00166 * publicExponent INTEGER, -- e 00167 * privateExponent INTEGER, -- d 00168 * prime1 INTEGER, -- p 00169 * prime2 INTEGER, -- q 00170 * exponent1 INTEGER, -- d mod (p-1) 00171 * exponent2 INTEGER, -- d mod (q-1) 00172 * coefficient INTEGER -- (inverse of q) mod p 00173 * } 00174 * 00175 * Version ::= INTEGER -- shall be 0 for this version of the standard 00176 */ 00177 if (asn1_get_next(buf, len, &hdr) < 0 || 00178 hdr.class != ASN1_CLASS_UNIVERSAL || 00179 hdr.tag != ASN1_TAG_SEQUENCE) { 00180 wpa_printf(MSG_DEBUG, "RSA: Expected SEQUENCE " 00181 "(public key) - found class %d tag 0x%x", 00182 hdr.class, hdr.tag); 00183 goto error; 00184 } 00185 pos = hdr.payload; 00186 end = pos + hdr.length; 00187 00188 zero = bignum_init(); 00189 if (zero == NULL) 00190 goto error; 00191 pos = crypto_rsa_parse_integer(pos, end, zero); 00192 if (pos == NULL || bignum_cmp_d(zero, 0) != 0) { 00193 wpa_printf(MSG_DEBUG, "RSA: Expected zero INTEGER in the " 00194 "beginning of private key; not found"); 00195 bignum_deinit(zero); 00196 goto error; 00197 } 00198 bignum_deinit(zero); 00199 00200 pos = crypto_rsa_parse_integer(pos, end, key->n); 00201 pos = crypto_rsa_parse_integer(pos, end, key->e); 00202 pos = crypto_rsa_parse_integer(pos, end, key->d); 00203 pos = crypto_rsa_parse_integer(pos, end, key->p); 00204 pos = crypto_rsa_parse_integer(pos, end, key->q); 00205 pos = crypto_rsa_parse_integer(pos, end, key->dmp1); 00206 pos = crypto_rsa_parse_integer(pos, end, key->dmq1); 00207 pos = crypto_rsa_parse_integer(pos, end, key->iqmp); 00208 00209 if (pos == NULL) 00210 goto error; 00211 00212 if (pos != end) { 00213 wpa_hexdump(MSG_DEBUG, 00214 "RSA: Extra data in public key SEQUENCE", 00215 pos, end - pos); 00216 goto error; 00217 } 00218 00219 return key; 00220 00221 error: 00222 crypto_rsa_free(key); 00223 return NULL; 00224 } 00225 00226 00232 size_t crypto_rsa_get_modulus_len(struct crypto_rsa_key *key) 00233 { 00234 return bignum_get_unsigned_bin_len(key->n); 00235 } 00236 00237 00248 int crypto_rsa_exptmod(const u8 *in, size_t inlen, u8 *out, size_t *outlen, 00249 struct crypto_rsa_key *key, int use_private) 00250 { 00251 struct bignum *tmp, *a = NULL, *b = NULL; 00252 int ret = -1; 00253 size_t modlen; 00254 00255 if (use_private && !key->private_key) 00256 return -1; 00257 00258 tmp = bignum_init(); 00259 if (tmp == NULL) 00260 return -1; 00261 00262 if (bignum_set_unsigned_bin(tmp, in, inlen) < 0) 00263 goto error; 00264 if (bignum_cmp(key->n, tmp) < 0) { 00265 /* Too large input value for the RSA key modulus */ 00266 goto error; 00267 } 00268 00269 if (use_private) { 00270 /* 00271 * Decrypt (or sign) using Chinese remainer theorem to speed 00272 * up calculation. This is equivalent to tmp = tmp^d mod n 00273 * (which would require more CPU to calculate directly). 00274 * 00275 * dmp1 = (1/e) mod (p-1) 00276 * dmq1 = (1/e) mod (q-1) 00277 * iqmp = (1/q) mod p, where p > q 00278 * m1 = c^dmp1 mod p 00279 * m2 = c^dmq1 mod q 00280 * h = q^-1 (m1 - m2) mod p 00281 * m = m2 + hq 00282 */ 00283 a = bignum_init(); 00284 b = bignum_init(); 00285 if (a == NULL || b == NULL) 00286 goto error; 00287 00288 /* a = tmp^dmp1 mod p */ 00289 if (bignum_exptmod(tmp, key->dmp1, key->p, a) < 0) 00290 goto error; 00291 00292 /* b = tmp^dmq1 mod q */ 00293 if (bignum_exptmod(tmp, key->dmq1, key->q, b) < 0) 00294 goto error; 00295 00296 /* tmp = (a - b) * (1/q mod p) (mod p) */ 00297 if (bignum_sub(a, b, tmp) < 0 || 00298 bignum_mulmod(tmp, key->iqmp, key->p, tmp) < 0) 00299 goto error; 00300 00301 /* tmp = b + q * tmp */ 00302 if (bignum_mul(tmp, key->q, tmp) < 0 || 00303 bignum_add(tmp, b, tmp) < 0) 00304 goto error; 00305 } else { 00306 /* Encrypt (or verify signature) */ 00307 /* tmp = tmp^e mod N */ 00308 if (bignum_exptmod(tmp, key->e, key->n, tmp) < 0) 00309 goto error; 00310 } 00311 00312 modlen = crypto_rsa_get_modulus_len(key); 00313 if (modlen > *outlen) { 00314 *outlen = modlen; 00315 goto error; 00316 } 00317 00318 if (bignum_get_unsigned_bin_len(tmp) > modlen) 00319 goto error; /* should never happen */ 00320 00321 *outlen = modlen; 00322 os_memset(out, 0, modlen); 00323 if (bignum_get_unsigned_bin( 00324 tmp, out + 00325 (modlen - bignum_get_unsigned_bin_len(tmp)), NULL) < 0) 00326 goto error; 00327 00328 ret = 0; 00329 00330 error: 00331 bignum_deinit(tmp); 00332 bignum_deinit(a); 00333 bignum_deinit(b); 00334 return ret; 00335 } 00336 00337 00345 void crypto_rsa_free(struct crypto_rsa_key *key) 00346 { 00347 if (key) { 00348 bignum_deinit(key->n); 00349 bignum_deinit(key->e); 00350 bignum_deinit(key->d); 00351 bignum_deinit(key->p); 00352 bignum_deinit(key->q); 00353 bignum_deinit(key->dmp1); 00354 bignum_deinit(key->dmq1); 00355 bignum_deinit(key->iqmp); 00356 os_free(key); 00357 } 00358 }