← Back to branch summary

~ubuntu-branches/ubuntu/precise/openssl098/precise

« back to all changes in this revision

Viewing changes to crypto/ecdsa/ecs_ossl.c

  • Committer: Bazaar Package Importer
  • Author(s): Kurt Roeckx
  • Date: 2011-03-23 19:50:31 UTC
  • Revision ID: james.westby@ubuntu.com-20110323195031-6h9crj4bymhhr8b8
Tags: upstream-0.9.8o
Import upstream version 0.9.8o

Show diffs side-by-side

added added

removed removed

Lines of Context:
crypto/ecdsa/ecs_ossl.c
 
1
/* crypto/ecdsa/ecs_ossl.c */
 
2
/*
 
3
 * Written by Nils Larsch for the OpenSSL project
 
4
 */
 
5
/* ====================================================================
 
6
 * Copyright (c) 1998-2004 The OpenSSL Project.  All rights reserved.
 
7
 *
 
8
 * Redistribution and use in source and binary forms, with or without
 
9
 * modification, are permitted provided that the following conditions
 
10
 * are met:
 
11
 *
 
12
 * 1. Redistributions of source code must retain the above copyright
 
13
 *    notice, this list of conditions and the following disclaimer. 
 
14
 *
 
15
 * 2. Redistributions in binary form must reproduce the above copyright
 
16
 *    notice, this list of conditions and the following disclaimer in
 
17
 *    the documentation and/or other materials provided with the
 
18
 *    distribution.
 
19
 *
 
20
 * 3. All advertising materials mentioning features or use of this
 
21
 *    software must display the following acknowledgment:
 
22
 *    "This product includes software developed by the OpenSSL Project
 
23
 *    for use in the OpenSSL Toolkit. (http://www.OpenSSL.org/)"
 
24
 *
 
25
 * 4. The names "OpenSSL Toolkit" and "OpenSSL Project" must not be used to
 
26
 *    endorse or promote products derived from this software without
 
27
 *    prior written permission. For written permission, please contact
 
28
 *    openssl-core@OpenSSL.org.
 
29
 *
 
30
 * 5. Products derived from this software may not be called "OpenSSL"
 
31
 *    nor may "OpenSSL" appear in their names without prior written
 
32
 *    permission of the OpenSSL Project.
 
33
 *
 
34
 * 6. Redistributions of any form whatsoever must retain the following
 
35
 *    acknowledgment:
 
36
 *    "This product includes software developed by the OpenSSL Project
 
37
 *    for use in the OpenSSL Toolkit (http://www.OpenSSL.org/)"
 
38
 *
 
39
 * THIS SOFTWARE IS PROVIDED BY THE OpenSSL PROJECT ``AS IS'' AND ANY
 
40
 * EXPRESSED OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
 
41
 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
 
42
 * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL THE OpenSSL PROJECT OR
 
43
 * ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
 
44
 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
 
45
 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
 
46
 * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
 
47
 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
 
48
 * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
 
49
 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED
 
50
 * OF THE POSSIBILITY OF SUCH DAMAGE.
 
51
 * ====================================================================
 
52
 *
 
53
 * This product includes cryptographic software written by Eric Young
 
54
 * (eay@cryptsoft.com).  This product includes software written by Tim
 
55
 * Hudson (tjh@cryptsoft.com).
 
56
 *
 
57
 */
 
58
 
 
59
#include "ecs_locl.h"
 
60
#include <openssl/err.h>
 
61
#include <openssl/obj_mac.h>
 
62
#include <openssl/bn.h>
 
63
 
 
64
static ECDSA_SIG *ecdsa_do_sign(const unsigned char *dgst, int dlen, 
 
65
                const BIGNUM *, const BIGNUM *, EC_KEY *eckey);
 
66
static int ecdsa_sign_setup(EC_KEY *eckey, BN_CTX *ctx_in, BIGNUM **kinvp, 
 
67
                BIGNUM **rp);
 
68
static int ecdsa_do_verify(const unsigned char *dgst, int dgst_len, 
 
69
                const ECDSA_SIG *sig, EC_KEY *eckey);
 
70
 
 
71
static ECDSA_METHOD openssl_ecdsa_meth = {
 
72
        "OpenSSL ECDSA method",
 
73
        ecdsa_do_sign,
 
74
        ecdsa_sign_setup,
 
75
        ecdsa_do_verify,
 
76
#if 0
 
77
        NULL, /* init     */
 
78
        NULL, /* finish   */
 
79
#endif
 
80
        0,    /* flags    */
 
81
        NULL  /* app_data */
 
82
};
 
83
 
 
84
const ECDSA_METHOD *ECDSA_OpenSSL(void)
 
85
{
 
86
        return &openssl_ecdsa_meth;
 
87
}
 
88
 
 
89
static int ecdsa_sign_setup(EC_KEY *eckey, BN_CTX *ctx_in, BIGNUM **kinvp,
 
90
                BIGNUM **rp)
 
91
{
 
92
        BN_CTX   *ctx = NULL;
 
93
        BIGNUM   *k = NULL, *r = NULL, *order = NULL, *X = NULL;
 
94
        EC_POINT *tmp_point=NULL;
 
95
        const EC_GROUP *group;
 
96
        int      ret = 0;
 
97
 
 
98
        if (eckey == NULL || (group = EC_KEY_get0_group(eckey)) == NULL)
 
99
        {
 
100
                ECDSAerr(ECDSA_F_ECDSA_SIGN_SETUP, ERR_R_PASSED_NULL_PARAMETER);
 
101
                return 0;
 
102
        }
 
103
 
 
104
        if (ctx_in == NULL) 
 
105
        {
 
106
                if ((ctx = BN_CTX_new()) == NULL)
 
107
                {
 
108
                        ECDSAerr(ECDSA_F_ECDSA_SIGN_SETUP,ERR_R_MALLOC_FAILURE);
 
109
                        return 0;
 
110
                }
 
111
        }
 
112
        else
 
113
                ctx = ctx_in;
 
114
 
 
115
        k     = BN_new();       /* this value is later returned in *kinvp */
 
116
        r     = BN_new();       /* this value is later returned in *rp    */
 
117
        order = BN_new();
 
118
        X     = BN_new();
 
119
        if (!k || !r || !order || !X)
 
120
        {
 
121
                ECDSAerr(ECDSA_F_ECDSA_SIGN_SETUP, ERR_R_MALLOC_FAILURE);
 
122
                goto err;
 
123
        }
 
124
        if ((tmp_point = EC_POINT_new(group)) == NULL)
 
125
        {
 
126
                ECDSAerr(ECDSA_F_ECDSA_SIGN_SETUP, ERR_R_EC_LIB);
 
127
                goto err;
 
128
        }
 
129
        if (!EC_GROUP_get_order(group, order, ctx))
 
130
        {
 
131
                ECDSAerr(ECDSA_F_ECDSA_SIGN_SETUP, ERR_R_EC_LIB);
 
132
                goto err;
 
133
        }
 
134
        
 
135
        do
 
136
        {
 
137
                /* get random k */      
 
138
                do
 
139
                        if (!BN_rand_range(k, order))
 
140
                        {
 
141
                                ECDSAerr(ECDSA_F_ECDSA_SIGN_SETUP,
 
142
                                 ECDSA_R_RANDOM_NUMBER_GENERATION_FAILED);      
 
143
                                goto err;
 
144
                        }
 
145
                while (BN_is_zero(k));
 
146
 
 
147
                /* compute r the x-coordinate of generator * k */
 
148
                if (!EC_POINT_mul(group, tmp_point, k, NULL, NULL, ctx))
 
149
                {
 
150
                        ECDSAerr(ECDSA_F_ECDSA_SIGN_SETUP, ERR_R_EC_LIB);
 
151
                        goto err;
 
152
                }
 
153
                if (EC_METHOD_get_field_type(EC_GROUP_method_of(group)) == NID_X9_62_prime_field)
 
154
                {
 
155
                        if (!EC_POINT_get_affine_coordinates_GFp(group,
 
156
                                tmp_point, X, NULL, ctx))
 
157
                        {
 
158
                                ECDSAerr(ECDSA_F_ECDSA_SIGN_SETUP,ERR_R_EC_LIB);
 
159
                                goto err;
 
160
                        }
 
161
                }
 
162
                else /* NID_X9_62_characteristic_two_field */
 
163
                {
 
164
                        if (!EC_POINT_get_affine_coordinates_GF2m(group,
 
165
                                tmp_point, X, NULL, ctx))
 
166
                        {
 
167
                                ECDSAerr(ECDSA_F_ECDSA_SIGN_SETUP,ERR_R_EC_LIB);
 
168
                                goto err;
 
169
                        }
 
170
                }
 
171
                if (!BN_nnmod(r, X, order, ctx))
 
172
                {
 
173
                        ECDSAerr(ECDSA_F_ECDSA_SIGN_SETUP, ERR_R_BN_LIB);
 
174
                        goto err;
 
175
                }
 
176
        }
 
177
        while (BN_is_zero(r));
 
178
 
 
179
        /* compute the inverse of k */
 
180
        if (!BN_mod_inverse(k, k, order, ctx))
 
181
        {
 
182
                ECDSAerr(ECDSA_F_ECDSA_SIGN_SETUP, ERR_R_BN_LIB);
 
183
                goto err;       
 
184
        }
 
185
        /* clear old values if necessary */
 
186
        if (*rp != NULL)
 
187
                BN_clear_free(*rp);
 
188
        if (*kinvp != NULL) 
 
189
                BN_clear_free(*kinvp);
 
190
        /* save the pre-computed values  */
 
191
        *rp    = r;
 
192
        *kinvp = k;
 
193
        ret = 1;
 
194
err:
 
195
        if (!ret)
 
196
        {
 
197
                if (k != NULL) BN_clear_free(k);
 
198
                if (r != NULL) BN_clear_free(r);
 
199
        }
 
200
        if (ctx_in == NULL) 
 
201
                BN_CTX_free(ctx);
 
202
        if (order != NULL)
 
203
                BN_free(order);
 
204
        if (tmp_point != NULL) 
 
205
                EC_POINT_free(tmp_point);
 
206
        if (X)
 
207
                BN_clear_free(X);
 
208
        return(ret);
 
209
}
 
210
 
 
211
 
 
212
static ECDSA_SIG *ecdsa_do_sign(const unsigned char *dgst, int dgst_len, 
 
213
                const BIGNUM *in_kinv, const BIGNUM *in_r, EC_KEY *eckey)
 
214
{
 
215
        int     ok = 0, i;
 
216
        BIGNUM *kinv=NULL, *s, *m=NULL,*tmp=NULL,*order=NULL;
 
217
        const BIGNUM *ckinv;
 
218
        BN_CTX     *ctx = NULL;
 
219
        const EC_GROUP   *group;
 
220
        ECDSA_SIG  *ret;
 
221
        ECDSA_DATA *ecdsa;
 
222
        const BIGNUM *priv_key;
 
223
 
 
224
        ecdsa    = ecdsa_check(eckey);
 
225
        group    = EC_KEY_get0_group(eckey);
 
226
        priv_key = EC_KEY_get0_private_key(eckey);
 
227
        
 
228
        if (group == NULL || priv_key == NULL || ecdsa == NULL)
 
229
        {
 
230
                ECDSAerr(ECDSA_F_ECDSA_DO_SIGN, ERR_R_PASSED_NULL_PARAMETER);
 
231
                return NULL;
 
232
        }
 
233
 
 
234
        ret = ECDSA_SIG_new();
 
235
        if (!ret)
 
236
        {
 
237
                ECDSAerr(ECDSA_F_ECDSA_DO_SIGN, ERR_R_MALLOC_FAILURE);
 
238
                return NULL;
 
239
        }
 
240
        s = ret->s;
 
241
 
 
242
        if ((ctx = BN_CTX_new()) == NULL || (order = BN_new()) == NULL ||
 
243
                (tmp = BN_new()) == NULL || (m = BN_new()) == NULL)
 
244
        {
 
245
                ECDSAerr(ECDSA_F_ECDSA_DO_SIGN, ERR_R_MALLOC_FAILURE);
 
246
                goto err;
 
247
        }
 
248
 
 
249
        if (!EC_GROUP_get_order(group, order, ctx))
 
250
        {
 
251
                ECDSAerr(ECDSA_F_ECDSA_DO_SIGN, ERR_R_EC_LIB);
 
252
                goto err;
 
253
        }
 
254
        i = BN_num_bits(order);
 
255
        /* Need to truncate digest if it is too long: first truncate whole
 
256
         * bytes.
 
257
         */
 
258
        if (8 * dgst_len > i)
 
259
                dgst_len = (i + 7)/8;
 
260
        if (!BN_bin2bn(dgst, dgst_len, m))
 
261
        {
 
262
                ECDSAerr(ECDSA_F_ECDSA_DO_SIGN, ERR_R_BN_LIB);
 
263
                goto err;
 
264
        }
 
265
        /* If still too long truncate remaining bits with a shift */
 
266
        if ((8 * dgst_len > i) && !BN_rshift(m, m, 8 - (i & 0x7)))
 
267
        {
 
268
                ECDSAerr(ECDSA_F_ECDSA_DO_SIGN, ERR_R_BN_LIB);
 
269
                goto err;
 
270
        }
 
271
        do
 
272
        {
 
273
                if (in_kinv == NULL || in_r == NULL)
 
274
                {
 
275
                        if (!ECDSA_sign_setup(eckey, ctx, &kinv, &ret->r))
 
276
                        {
 
277
                                ECDSAerr(ECDSA_F_ECDSA_DO_SIGN,ERR_R_ECDSA_LIB);
 
278
                                goto err;
 
279
                        }
 
280
                        ckinv = kinv;
 
281
                }
 
282
                else
 
283
                {
 
284
                        ckinv  = in_kinv;
 
285
                        if (BN_copy(ret->r, in_r) == NULL)
 
286
                        {
 
287
                                ECDSAerr(ECDSA_F_ECDSA_DO_SIGN, ERR_R_MALLOC_FAILURE);
 
288
                                goto err;
 
289
                        }
 
290
                }
 
291
 
 
292
                if (!BN_mod_mul(tmp, priv_key, ret->r, order, ctx))
 
293
                {
 
294
                        ECDSAerr(ECDSA_F_ECDSA_DO_SIGN, ERR_R_BN_LIB);
 
295
                        goto err;
 
296
                }
 
297
                if (!BN_mod_add_quick(s, tmp, m, order))
 
298
                {
 
299
                        ECDSAerr(ECDSA_F_ECDSA_DO_SIGN, ERR_R_BN_LIB);
 
300
                        goto err;
 
301
                }
 
302
                if (!BN_mod_mul(s, s, ckinv, order, ctx))
 
303
                {
 
304
                        ECDSAerr(ECDSA_F_ECDSA_DO_SIGN, ERR_R_BN_LIB);
 
305
                        goto err;
 
306
                }
 
307
                if (BN_is_zero(s))
 
308
                {
 
309
                        /* if kinv and r have been supplied by the caller
 
310
                         * don't to generate new kinv and r values */
 
311
                        if (in_kinv != NULL && in_r != NULL)
 
312
                        {
 
313
                                ECDSAerr(ECDSA_F_ECDSA_DO_SIGN, ECDSA_R_NEED_NEW_SETUP_VALUES);
 
314
                                goto err;
 
315
                        }
 
316
                }
 
317
                else
 
318
                        /* s != 0 => we have a valid signature */
 
319
                        break;
 
320
        }
 
321
        while (1);
 
322
 
 
323
        ok = 1;
 
324
err:
 
325
        if (!ok)
 
326
        {
 
327
                ECDSA_SIG_free(ret);
 
328
                ret = NULL;
 
329
        }
 
330
        if (ctx)
 
331
                BN_CTX_free(ctx);
 
332
        if (m)
 
333
                BN_clear_free(m);
 
334
        if (tmp)
 
335
                BN_clear_free(tmp);
 
336
        if (order)
 
337
                BN_free(order);
 
338
        if (kinv)
 
339
                BN_clear_free(kinv);
 
340
        return ret;
 
341
}
 
342
 
 
343
static int ecdsa_do_verify(const unsigned char *dgst, int dgst_len,
 
344
                const ECDSA_SIG *sig, EC_KEY *eckey)
 
345
{
 
346
        int ret = -1, i;
 
347
        BN_CTX   *ctx;
 
348
        BIGNUM   *order, *u1, *u2, *m, *X;
 
349
        EC_POINT *point = NULL;
 
350
        const EC_GROUP *group;
 
351
        const EC_POINT *pub_key;
 
352
 
 
353
        /* check input values */
 
354
        if (eckey == NULL || (group = EC_KEY_get0_group(eckey)) == NULL ||
 
355
            (pub_key = EC_KEY_get0_public_key(eckey)) == NULL || sig == NULL)
 
356
        {
 
357
                ECDSAerr(ECDSA_F_ECDSA_DO_VERIFY, ECDSA_R_MISSING_PARAMETERS);
 
358
                return -1;
 
359
        }
 
360
 
 
361
        ctx = BN_CTX_new();
 
362
        if (!ctx)
 
363
        {
 
364
                ECDSAerr(ECDSA_F_ECDSA_DO_VERIFY, ERR_R_MALLOC_FAILURE);
 
365
                return -1;
 
366
        }
 
367
        BN_CTX_start(ctx);
 
368
        order = BN_CTX_get(ctx);        
 
369
        u1    = BN_CTX_get(ctx);
 
370
        u2    = BN_CTX_get(ctx);
 
371
        m     = BN_CTX_get(ctx);
 
372
        X     = BN_CTX_get(ctx);
 
373
        if (!X)
 
374
        {
 
375
                ECDSAerr(ECDSA_F_ECDSA_DO_VERIFY, ERR_R_BN_LIB);
 
376
                goto err;
 
377
        }
 
378
        
 
379
        if (!EC_GROUP_get_order(group, order, ctx))
 
380
        {
 
381
                ECDSAerr(ECDSA_F_ECDSA_DO_VERIFY, ERR_R_EC_LIB);
 
382
                goto err;
 
383
        }
 
384
 
 
385
        if (BN_is_zero(sig->r)          || BN_is_negative(sig->r) || 
 
386
            BN_ucmp(sig->r, order) >= 0 || BN_is_zero(sig->s)  ||
 
387
            BN_is_negative(sig->s)      || BN_ucmp(sig->s, order) >= 0)
 
388
        {
 
389
                ECDSAerr(ECDSA_F_ECDSA_DO_VERIFY, ECDSA_R_BAD_SIGNATURE);
 
390
                ret = 0;        /* signature is invalid */
 
391
                goto err;
 
392
        }
 
393
        /* calculate tmp1 = inv(S) mod order */
 
394
        if (!BN_mod_inverse(u2, sig->s, order, ctx))
 
395
        {
 
396
                ECDSAerr(ECDSA_F_ECDSA_DO_VERIFY, ERR_R_BN_LIB);
 
397
                goto err;
 
398
        }
 
399
        /* digest -> m */
 
400
        i = BN_num_bits(order);
 
401
        /* Need to truncate digest if it is too long: first truncate whole
 
402
         * bytes.
 
403
         */
 
404
        if (8 * dgst_len > i)
 
405
                dgst_len = (i + 7)/8;
 
406
        if (!BN_bin2bn(dgst, dgst_len, m))
 
407
        {
 
408
                ECDSAerr(ECDSA_F_ECDSA_DO_VERIFY, ERR_R_BN_LIB);
 
409
                goto err;
 
410
        }
 
411
        /* If still too long truncate remaining bits with a shift */
 
412
        if ((8 * dgst_len > i) && !BN_rshift(m, m, 8 - (i & 0x7)))
 
413
        {
 
414
                ECDSAerr(ECDSA_F_ECDSA_DO_VERIFY, ERR_R_BN_LIB);
 
415
                goto err;
 
416
        }
 
417
        /* u1 = m * tmp mod order */
 
418
        if (!BN_mod_mul(u1, m, u2, order, ctx))
 
419
        {
 
420
                ECDSAerr(ECDSA_F_ECDSA_DO_VERIFY, ERR_R_BN_LIB);
 
421
                goto err;
 
422
        }
 
423
        /* u2 = r * w mod q */
 
424
        if (!BN_mod_mul(u2, sig->r, u2, order, ctx))
 
425
        {
 
426
                ECDSAerr(ECDSA_F_ECDSA_DO_VERIFY, ERR_R_BN_LIB);
 
427
                goto err;
 
428
        }
 
429
 
 
430
        if ((point = EC_POINT_new(group)) == NULL)
 
431
        {
 
432
                ECDSAerr(ECDSA_F_ECDSA_DO_VERIFY, ERR_R_MALLOC_FAILURE);
 
433
                goto err;
 
434
        }
 
435
        if (!EC_POINT_mul(group, point, u1, pub_key, u2, ctx))
 
436
        {
 
437
                ECDSAerr(ECDSA_F_ECDSA_DO_VERIFY, ERR_R_EC_LIB);
 
438
                goto err;
 
439
        }
 
440
        if (EC_METHOD_get_field_type(EC_GROUP_method_of(group)) == NID_X9_62_prime_field)
 
441
        {
 
442
                if (!EC_POINT_get_affine_coordinates_GFp(group,
 
443
                        point, X, NULL, ctx))
 
444
                {
 
445
                        ECDSAerr(ECDSA_F_ECDSA_DO_VERIFY, ERR_R_EC_LIB);
 
446
                        goto err;
 
447
                }
 
448
        }
 
449
        else /* NID_X9_62_characteristic_two_field */
 
450
        {
 
451
                if (!EC_POINT_get_affine_coordinates_GF2m(group,
 
452
                        point, X, NULL, ctx))
 
453
                {
 
454
                        ECDSAerr(ECDSA_F_ECDSA_DO_VERIFY, ERR_R_EC_LIB);
 
455
                        goto err;
 
456
                }
 
457
        }
 
458
        
 
459
        if (!BN_nnmod(u1, X, order, ctx))
 
460
        {
 
461
                ECDSAerr(ECDSA_F_ECDSA_DO_VERIFY, ERR_R_BN_LIB);
 
462
                goto err;
 
463
        }
 
464
        /*  if the signature is correct u1 is equal to sig->r */
 
465
        ret = (BN_ucmp(u1, sig->r) == 0);
 
466
err:
 
467
        BN_CTX_end(ctx);
 
468
        BN_CTX_free(ctx);
 
469
        if (point)
 
470
                EC_POINT_free(point);
 
471
        return ret;
 
472
}