← Back to branch summary

~ubuntu-branches/ubuntu/gutsy/wpasupplicant/gutsy

« back to all changes in this revision

Viewing changes to src/tls/rsa.c

  • Committer: Bazaar Package Importer
  • Author(s): Reinhard Tartler, Alexander Sack
  • Date: 2007-08-26 16:06:57 UTC
  • mfrom: (1.1.9 upstream)
  • Revision ID: james.westby@ubuntu.com-20070826160657-2m8pxoweuxe8f93t
Tags: 0.6.0+0.5.8-0ubuntu1
https://launchpad.net/bugs/140763
https://launchpad.net/bugs/141233
* New upstream release
* remove patch 11_erroneous_manpage_ref, applied upstream
* remove patch 25_wpas_dbus_unregister_iface_fix, applied upstream

[ Alexander Sack ]
* bumping upstream version to replace development version 0.6.0 with
  this package from stable release branch.
* attempt to fix wierd timeout and high latency issues by going
  back to stable upstream version (0.5.9) (LP: #140763,
  LP: #141233).

Show diffs side-by-side

added added

removed removed

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