1189251Ssam/* 2189251Ssam * RSA 3189251Ssam * Copyright (c) 2006, Jouni Malinen <j@w1.fi> 4189251Ssam * 5252726Srpaulo * This software may be distributed under the terms of the BSD license. 6252726Srpaulo * See README for more details. 7189251Ssam */ 8189251Ssam 9189251Ssam#include "includes.h" 10189251Ssam 11189251Ssam#include "common.h" 12189251Ssam#include "asn1.h" 13189251Ssam#include "bignum.h" 14189251Ssam#include "rsa.h" 15189251Ssam 16189251Ssam 17189251Ssamstruct crypto_rsa_key { 18189251Ssam int private_key; /* whether private key is set */ 19189251Ssam struct bignum *n; /* modulus (p * q) */ 20189251Ssam struct bignum *e; /* public exponent */ 21189251Ssam /* The following parameters are available only if private_key is set */ 22189251Ssam struct bignum *d; /* private exponent */ 23189251Ssam struct bignum *p; /* prime p (factor of n) */ 24189251Ssam struct bignum *q; /* prime q (factor of n) */ 25189251Ssam struct bignum *dmp1; /* d mod (p - 1); CRT exponent */ 26189251Ssam struct bignum *dmq1; /* d mod (q - 1); CRT exponent */ 27189251Ssam struct bignum *iqmp; /* 1 / q mod p; CRT coefficient */ 28189251Ssam}; 29189251Ssam 30189251Ssam 31189251Ssamstatic const u8 * crypto_rsa_parse_integer(const u8 *pos, const u8 *end, 32189251Ssam struct bignum *num) 33189251Ssam{ 34189251Ssam struct asn1_hdr hdr; 35189251Ssam 36189251Ssam if (pos == NULL) 37189251Ssam return NULL; 38189251Ssam 39189251Ssam if (asn1_get_next(pos, end - pos, &hdr) < 0 || 40189251Ssam hdr.class != ASN1_CLASS_UNIVERSAL || hdr.tag != ASN1_TAG_INTEGER) { 41189251Ssam wpa_printf(MSG_DEBUG, "RSA: Expected INTEGER - found class %d " 42189251Ssam "tag 0x%x", hdr.class, hdr.tag); 43189251Ssam return NULL; 44189251Ssam } 45189251Ssam 46189251Ssam if (bignum_set_unsigned_bin(num, hdr.payload, hdr.length) < 0) { 47189251Ssam wpa_printf(MSG_DEBUG, "RSA: Failed to parse INTEGER"); 48189251Ssam return NULL; 49189251Ssam } 50189251Ssam 51189251Ssam return hdr.payload + hdr.length; 52189251Ssam} 53189251Ssam 54189251Ssam 55189251Ssam/** 56189251Ssam * crypto_rsa_import_public_key - Import an RSA public key 57189251Ssam * @buf: Key buffer (DER encoded RSA public key) 58189251Ssam * @len: Key buffer length in bytes 59189251Ssam * Returns: Pointer to the public key or %NULL on failure 60189251Ssam */ 61189251Ssamstruct crypto_rsa_key * 62189251Ssamcrypto_rsa_import_public_key(const u8 *buf, size_t len) 63189251Ssam{ 64189251Ssam struct crypto_rsa_key *key; 65189251Ssam struct asn1_hdr hdr; 66189251Ssam const u8 *pos, *end; 67189251Ssam 68189251Ssam key = os_zalloc(sizeof(*key)); 69189251Ssam if (key == NULL) 70189251Ssam return NULL; 71189251Ssam 72189251Ssam key->n = bignum_init(); 73189251Ssam key->e = bignum_init(); 74189251Ssam if (key->n == NULL || key->e == NULL) { 75189251Ssam crypto_rsa_free(key); 76189251Ssam return NULL; 77189251Ssam } 78189251Ssam 79189251Ssam /* 80189251Ssam * PKCS #1, 7.1: 81189251Ssam * RSAPublicKey ::= SEQUENCE { 82189251Ssam * modulus INTEGER, -- n 83189251Ssam * publicExponent INTEGER -- e 84189251Ssam * } 85189251Ssam */ 86189251Ssam 87189251Ssam if (asn1_get_next(buf, len, &hdr) < 0 || 88189251Ssam hdr.class != ASN1_CLASS_UNIVERSAL || 89189251Ssam hdr.tag != ASN1_TAG_SEQUENCE) { 90189251Ssam wpa_printf(MSG_DEBUG, "RSA: Expected SEQUENCE " 91189251Ssam "(public key) - found class %d tag 0x%x", 92189251Ssam hdr.class, hdr.tag); 93189251Ssam goto error; 94189251Ssam } 95189251Ssam pos = hdr.payload; 96189251Ssam end = pos + hdr.length; 97189251Ssam 98189251Ssam pos = crypto_rsa_parse_integer(pos, end, key->n); 99189251Ssam pos = crypto_rsa_parse_integer(pos, end, key->e); 100189251Ssam 101189251Ssam if (pos == NULL) 102189251Ssam goto error; 103189251Ssam 104189251Ssam if (pos != end) { 105189251Ssam wpa_hexdump(MSG_DEBUG, 106189251Ssam "RSA: Extra data in public key SEQUENCE", 107189251Ssam pos, end - pos); 108189251Ssam goto error; 109189251Ssam } 110189251Ssam 111189251Ssam return key; 112189251Ssam 113189251Ssamerror: 114189251Ssam crypto_rsa_free(key); 115189251Ssam return NULL; 116189251Ssam} 117189251Ssam 118189251Ssam 119189251Ssam/** 120189251Ssam * crypto_rsa_import_private_key - Import an RSA private key 121189251Ssam * @buf: Key buffer (DER encoded RSA private key) 122189251Ssam * @len: Key buffer length in bytes 123189251Ssam * Returns: Pointer to the private key or %NULL on failure 124189251Ssam */ 125189251Ssamstruct crypto_rsa_key * 126189251Ssamcrypto_rsa_import_private_key(const u8 *buf, size_t len) 127189251Ssam{ 128189251Ssam struct crypto_rsa_key *key; 129189251Ssam struct bignum *zero; 130189251Ssam struct asn1_hdr hdr; 131189251Ssam const u8 *pos, *end; 132189251Ssam 133189251Ssam key = os_zalloc(sizeof(*key)); 134189251Ssam if (key == NULL) 135189251Ssam return NULL; 136189251Ssam 137189251Ssam key->private_key = 1; 138189251Ssam 139189251Ssam key->n = bignum_init(); 140189251Ssam key->e = bignum_init(); 141189251Ssam key->d = bignum_init(); 142189251Ssam key->p = bignum_init(); 143189251Ssam key->q = bignum_init(); 144189251Ssam key->dmp1 = bignum_init(); 145189251Ssam key->dmq1 = bignum_init(); 146189251Ssam key->iqmp = bignum_init(); 147189251Ssam 148189251Ssam if (key->n == NULL || key->e == NULL || key->d == NULL || 149189251Ssam key->p == NULL || key->q == NULL || key->dmp1 == NULL || 150189251Ssam key->dmq1 == NULL || key->iqmp == NULL) { 151189251Ssam crypto_rsa_free(key); 152189251Ssam return NULL; 153189251Ssam } 154189251Ssam 155189251Ssam /* 156189251Ssam * PKCS #1, 7.2: 157189251Ssam * RSAPrivateKey ::= SEQUENCE { 158189251Ssam * version Version, 159189251Ssam * modulus INTEGER, -- n 160189251Ssam * publicExponent INTEGER, -- e 161189251Ssam * privateExponent INTEGER, -- d 162189251Ssam * prime1 INTEGER, -- p 163189251Ssam * prime2 INTEGER, -- q 164189251Ssam * exponent1 INTEGER, -- d mod (p-1) 165189251Ssam * exponent2 INTEGER, -- d mod (q-1) 166189251Ssam * coefficient INTEGER -- (inverse of q) mod p 167189251Ssam * } 168189251Ssam * 169189251Ssam * Version ::= INTEGER -- shall be 0 for this version of the standard 170189251Ssam */ 171189251Ssam if (asn1_get_next(buf, len, &hdr) < 0 || 172189251Ssam hdr.class != ASN1_CLASS_UNIVERSAL || 173189251Ssam hdr.tag != ASN1_TAG_SEQUENCE) { 174189251Ssam wpa_printf(MSG_DEBUG, "RSA: Expected SEQUENCE " 175189251Ssam "(public key) - found class %d tag 0x%x", 176189251Ssam hdr.class, hdr.tag); 177189251Ssam goto error; 178189251Ssam } 179189251Ssam pos = hdr.payload; 180189251Ssam end = pos + hdr.length; 181189251Ssam 182189251Ssam zero = bignum_init(); 183189251Ssam if (zero == NULL) 184189251Ssam goto error; 185189251Ssam pos = crypto_rsa_parse_integer(pos, end, zero); 186189251Ssam if (pos == NULL || bignum_cmp_d(zero, 0) != 0) { 187189251Ssam wpa_printf(MSG_DEBUG, "RSA: Expected zero INTEGER in the " 188189251Ssam "beginning of private key; not found"); 189189251Ssam bignum_deinit(zero); 190189251Ssam goto error; 191189251Ssam } 192189251Ssam bignum_deinit(zero); 193189251Ssam 194189251Ssam pos = crypto_rsa_parse_integer(pos, end, key->n); 195189251Ssam pos = crypto_rsa_parse_integer(pos, end, key->e); 196189251Ssam pos = crypto_rsa_parse_integer(pos, end, key->d); 197189251Ssam pos = crypto_rsa_parse_integer(pos, end, key->p); 198189251Ssam pos = crypto_rsa_parse_integer(pos, end, key->q); 199189251Ssam pos = crypto_rsa_parse_integer(pos, end, key->dmp1); 200189251Ssam pos = crypto_rsa_parse_integer(pos, end, key->dmq1); 201189251Ssam pos = crypto_rsa_parse_integer(pos, end, key->iqmp); 202189251Ssam 203189251Ssam if (pos == NULL) 204189251Ssam goto error; 205189251Ssam 206189251Ssam if (pos != end) { 207189251Ssam wpa_hexdump(MSG_DEBUG, 208189251Ssam "RSA: Extra data in public key SEQUENCE", 209189251Ssam pos, end - pos); 210189251Ssam goto error; 211189251Ssam } 212189251Ssam 213189251Ssam return key; 214189251Ssam 215189251Ssamerror: 216189251Ssam crypto_rsa_free(key); 217189251Ssam return NULL; 218189251Ssam} 219189251Ssam 220189251Ssam 221189251Ssam/** 222189251Ssam * crypto_rsa_get_modulus_len - Get the modulus length of the RSA key 223189251Ssam * @key: RSA key 224189251Ssam * Returns: Modulus length of the key 225189251Ssam */ 226189251Ssamsize_t crypto_rsa_get_modulus_len(struct crypto_rsa_key *key) 227189251Ssam{ 228189251Ssam return bignum_get_unsigned_bin_len(key->n); 229189251Ssam} 230189251Ssam 231189251Ssam 232189251Ssam/** 233189251Ssam * crypto_rsa_exptmod - RSA modular exponentiation 234189251Ssam * @in: Input data 235189251Ssam * @inlen: Input data length 236189251Ssam * @out: Buffer for output data 237189251Ssam * @outlen: Maximum size of the output buffer and used size on success 238189251Ssam * @key: RSA key 239189251Ssam * @use_private: 1 = Use RSA private key, 0 = Use RSA public key 240189251Ssam * Returns: 0 on success, -1 on failure 241189251Ssam */ 242189251Ssamint crypto_rsa_exptmod(const u8 *in, size_t inlen, u8 *out, size_t *outlen, 243189251Ssam struct crypto_rsa_key *key, int use_private) 244189251Ssam{ 245189251Ssam struct bignum *tmp, *a = NULL, *b = NULL; 246189251Ssam int ret = -1; 247189251Ssam size_t modlen; 248189251Ssam 249189251Ssam if (use_private && !key->private_key) 250189251Ssam return -1; 251189251Ssam 252189251Ssam tmp = bignum_init(); 253189251Ssam if (tmp == NULL) 254189251Ssam return -1; 255189251Ssam 256189251Ssam if (bignum_set_unsigned_bin(tmp, in, inlen) < 0) 257189251Ssam goto error; 258189251Ssam if (bignum_cmp(key->n, tmp) < 0) { 259189251Ssam /* Too large input value for the RSA key modulus */ 260189251Ssam goto error; 261189251Ssam } 262189251Ssam 263189251Ssam if (use_private) { 264189251Ssam /* 265189251Ssam * Decrypt (or sign) using Chinese remainer theorem to speed 266189251Ssam * up calculation. This is equivalent to tmp = tmp^d mod n 267189251Ssam * (which would require more CPU to calculate directly). 268189251Ssam * 269189251Ssam * dmp1 = (1/e) mod (p-1) 270189251Ssam * dmq1 = (1/e) mod (q-1) 271189251Ssam * iqmp = (1/q) mod p, where p > q 272189251Ssam * m1 = c^dmp1 mod p 273189251Ssam * m2 = c^dmq1 mod q 274189251Ssam * h = q^-1 (m1 - m2) mod p 275189251Ssam * m = m2 + hq 276189251Ssam */ 277189251Ssam a = bignum_init(); 278189251Ssam b = bignum_init(); 279189251Ssam if (a == NULL || b == NULL) 280189251Ssam goto error; 281189251Ssam 282189251Ssam /* a = tmp^dmp1 mod p */ 283189251Ssam if (bignum_exptmod(tmp, key->dmp1, key->p, a) < 0) 284189251Ssam goto error; 285189251Ssam 286189251Ssam /* b = tmp^dmq1 mod q */ 287189251Ssam if (bignum_exptmod(tmp, key->dmq1, key->q, b) < 0) 288189251Ssam goto error; 289189251Ssam 290189251Ssam /* tmp = (a - b) * (1/q mod p) (mod p) */ 291189251Ssam if (bignum_sub(a, b, tmp) < 0 || 292189251Ssam bignum_mulmod(tmp, key->iqmp, key->p, tmp) < 0) 293189251Ssam goto error; 294189251Ssam 295189251Ssam /* tmp = b + q * tmp */ 296189251Ssam if (bignum_mul(tmp, key->q, tmp) < 0 || 297189251Ssam bignum_add(tmp, b, tmp) < 0) 298189251Ssam goto error; 299189251Ssam } else { 300189251Ssam /* Encrypt (or verify signature) */ 301189251Ssam /* tmp = tmp^e mod N */ 302189251Ssam if (bignum_exptmod(tmp, key->e, key->n, tmp) < 0) 303189251Ssam goto error; 304189251Ssam } 305189251Ssam 306189251Ssam modlen = crypto_rsa_get_modulus_len(key); 307189251Ssam if (modlen > *outlen) { 308189251Ssam *outlen = modlen; 309189251Ssam goto error; 310189251Ssam } 311189251Ssam 312189251Ssam if (bignum_get_unsigned_bin_len(tmp) > modlen) 313189251Ssam goto error; /* should never happen */ 314189251Ssam 315189251Ssam *outlen = modlen; 316189251Ssam os_memset(out, 0, modlen); 317189251Ssam if (bignum_get_unsigned_bin( 318189251Ssam tmp, out + 319189251Ssam (modlen - bignum_get_unsigned_bin_len(tmp)), NULL) < 0) 320189251Ssam goto error; 321189251Ssam 322189251Ssam ret = 0; 323189251Ssam 324189251Ssamerror: 325189251Ssam bignum_deinit(tmp); 326189251Ssam bignum_deinit(a); 327189251Ssam bignum_deinit(b); 328189251Ssam return ret; 329189251Ssam} 330189251Ssam 331189251Ssam 332189251Ssam/** 333189251Ssam * crypto_rsa_free - Free RSA key 334189251Ssam * @key: RSA key to be freed 335189251Ssam * 336189251Ssam * This function frees an RSA key imported with either 337189251Ssam * crypto_rsa_import_public_key() or crypto_rsa_import_private_key(). 338189251Ssam */ 339189251Ssamvoid crypto_rsa_free(struct crypto_rsa_key *key) 340189251Ssam{ 341189251Ssam if (key) { 342189251Ssam bignum_deinit(key->n); 343189251Ssam bignum_deinit(key->e); 344189251Ssam bignum_deinit(key->d); 345189251Ssam bignum_deinit(key->p); 346189251Ssam bignum_deinit(key->q); 347189251Ssam bignum_deinit(key->dmp1); 348189251Ssam bignum_deinit(key->dmq1); 349189251Ssam bignum_deinit(key->iqmp); 350189251Ssam os_free(key); 351189251Ssam } 352189251Ssam} 353