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 "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 }