contrib/hostapd/src/tls/rsa.c

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