libeap/src/tls/rsa.c

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