rsa.c
Go to the documentation of this file.
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 }


wpa_supplicant_node
Author(s): Package maintained by Blaise Gassend
autogenerated on Thu Apr 24 2014 15:33:21