5a36707cfbd38b885859a87acd5a883b8b556bdf
[openssl.git] / crypto / ecdsa / ecs_ossl.c
1 /* crypto/ecdsa/ecs_ossl.c */
2 /* ====================================================================
3  * Copyright (c) 1998-2002 The OpenSSL Project.  All rights reserved.
4  *
5  * Redistribution and use in source and binary forms, with or without
6  * modification, are permitted provided that the following conditions
7  * are met:
8  *
9  * 1. Redistributions of source code must retain the above copyright
10  *    notice, this list of conditions and the following disclaimer. 
11  *
12  * 2. Redistributions in binary form must reproduce the above copyright
13  *    notice, this list of conditions and the following disclaimer in
14  *    the documentation and/or other materials provided with the
15  *    distribution.
16  *
17  * 3. All advertising materials mentioning features or use of this
18  *    software must display the following acknowledgment:
19  *    "This product includes software developed by the OpenSSL Project
20  *    for use in the OpenSSL Toolkit. (http://www.OpenSSL.org/)"
21  *
22  * 4. The names "OpenSSL Toolkit" and "OpenSSL Project" must not be used to
23  *    endorse or promote products derived from this software without
24  *    prior written permission. For written permission, please contact
25  *    openssl-core@OpenSSL.org.
26  *
27  * 5. Products derived from this software may not be called "OpenSSL"
28  *    nor may "OpenSSL" appear in their names without prior written
29  *    permission of the OpenSSL Project.
30  *
31  * 6. Redistributions of any form whatsoever must retain the following
32  *    acknowledgment:
33  *    "This product includes software developed by the OpenSSL Project
34  *    for use in the OpenSSL Toolkit (http://www.OpenSSL.org/)"
35  *
36  * THIS SOFTWARE IS PROVIDED BY THE OpenSSL PROJECT ``AS IS'' AND ANY
37  * EXPRESSED OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
38  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
39  * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL THE OpenSSL PROJECT OR
40  * ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
41  * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
42  * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
43  * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
44  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
45  * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
46  * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED
47  * OF THE POSSIBILITY OF SUCH DAMAGE.
48  * ====================================================================
49  *
50  * This product includes cryptographic software written by Eric Young
51  * (eay@cryptsoft.com).  This product includes software written by Tim
52  * Hudson (tjh@cryptsoft.com).
53  *
54  */
55 /* Copyright (C) 1995-1998 Eric Young (eay@cryptsoft.com)
56  * All rights reserved.
57  *
58  * This package is an SSL implementation written
59  * by Eric Young (eay@cryptsoft.com).
60  * The implementation was written so as to conform with Netscapes SSL.
61  * 
62  * This library is free for commercial and non-commercial use as long as
63  * the following conditions are aheared to.  The following conditions
64  * apply to all code found in this distribution, be it the RC4, RSA,
65  * lhash, DES, etc., code; not just the SSL code.  The SSL documentation
66  * included with this distribution is covered by the same copyright terms
67  * except that the holder is Tim Hudson (tjh@cryptsoft.com).
68  * 
69  * Copyright remains Eric Young's, and as such any Copyright notices in
70  * the code are not to be removed.
71  * If this package is used in a product, Eric Young should be given attribution
72  * as the author of the parts of the library used.
73  * This can be in the form of a textual message at program startup or
74  * in documentation (online or textual) provided with the package.
75  * 
76  * Redistribution and use in source and binary forms, with or without
77  * modification, are permitted provided that the following conditions
78  * are met:
79  * 1. Redistributions of source code must retain the copyright
80  *    notice, this list of conditions and the following disclaimer.
81  * 2. Redistributions in binary form must reproduce the above copyright
82  *    notice, this list of conditions and the following disclaimer in the
83  *    documentation and/or other materials provided with the distribution.
84  * 3. All advertising materials mentioning features or use of this software
85  *    must display the following acknowledgement:
86  *    "This product includes cryptographic software written by
87  *     Eric Young (eay@cryptsoft.com)"
88  *    The word 'cryptographic' can be left out if the rouines from the library
89  *    being used are not cryptographic related :-).
90  * 4. If you include any Windows specific code (or a derivative thereof) from 
91  *    the apps directory (application code) you must include an acknowledgement:
92  *    "This product includes software written by Tim Hudson (tjh@cryptsoft.com)"
93  * 
94  * THIS SOFTWARE IS PROVIDED BY ERIC YOUNG ``AS IS'' AND
95  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
96  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
97  * ARE DISCLAIMED.  IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
98  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
99  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
100  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
101  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
102  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
103  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
104  * SUCH DAMAGE.
105  * 
106  * The licence and distribution terms for any publically available version or
107  * derivative of this code cannot be changed.  i.e. this code cannot simply be
108  * copied and put under another distribution licence
109  * [including the GNU Public Licence.]
110  */
111 #include "cryptlib.h"
112 #include <openssl/ecdsa.h>
113
114 /* TODO : general case */
115 #define EC_POINT_get_affine_coordinates EC_POINT_get_affine_coordinates_GFp
116
117 static ECDSA_SIG *ecdsa_do_sign(const unsigned char *dgst, int dlen, ECDSA *ecdsa);
118 static int ecdsa_sign_setup(ECDSA *ecdsa, BN_CTX *ctx_in, BIGNUM **kinvp, BIGNUM **rp);
119 static int ecdsa_do_verify(const unsigned char *dgst, int dgst_len, ECDSA_SIG *sig,
120                            ECDSA *ecdsa);
121
122 static ECDSA_METHOD openssl_ecdsa_meth = {
123 "OpenSSL ECDSA method",
124 ecdsa_do_sign,
125 ecdsa_sign_setup,
126 ecdsa_do_verify,
127 0,
128 NULL
129 };
130
131 const ECDSA_METHOD *ECDSA_OpenSSL(void)
132 {
133         return &openssl_ecdsa_meth;
134 }
135
136 static int ecdsa_sign_setup(ECDSA *ecdsa, BN_CTX *ctx_in, BIGNUM **kinvp, BIGNUM **rp)
137 {
138         BN_CTX   *ctx = NULL;
139         BIGNUM   k,*kinv=NULL,*r=NULL,*order=NULL,*X=NULL;
140         EC_POINT *tmp_point=NULL;
141         int      ret = 0,reason = ERR_R_BN_LIB;
142         if (!ecdsa  || !ecdsa->group || !ecdsa->pub_key || !ecdsa->priv_key)
143         {
144                 reason = ECDSA_R_MISSING_PARAMETERS;
145                 return 0;
146         }
147         if (ctx_in == NULL) 
148         {
149                 if ((ctx=BN_CTX_new()) == NULL) goto err;
150         }
151         else
152                 ctx=ctx_in;
153
154         if ((r = BN_new()) == NULL) goto err;
155         if ((order = BN_new()) == NULL) goto err;
156         if ((X = BN_new()) == NULL) goto err;
157         if ((tmp_point = EC_POINT_new(ecdsa->group)) == NULL)
158         {
159                 reason = ERR_R_EC_LIB;
160                 goto err;
161         }
162         if (!EC_POINT_copy(tmp_point,EC_GROUP_get0_generator(ecdsa->group)))
163         {
164                 reason = ERR_R_EC_LIB;
165                 goto err;
166         }
167         if (!EC_GROUP_get_order(ecdsa->group,order,ctx))
168         {
169                 reason = ERR_R_EC_LIB;
170                 goto err;
171         }
172         
173         do
174         {
175                 /* get random k */      
176                 BN_init(&k);
177                 do
178                         if (!BN_rand_range(&k,order))
179                         {
180                                 reason = ECDSA_R_RANDOM_NUMBER_GENERATION_FAILED;
181                                 goto err;
182                         }
183                 while (BN_is_zero(&k));
184
185                 /* compute r the x-coordinate of generator * k */
186                 if (!EC_POINT_mul(ecdsa->group,tmp_point,&k,NULL,NULL,ctx) 
187                     || !EC_POINT_get_affine_coordinates(ecdsa->group,tmp_point,X,NULL,ctx))
188                 {
189                         reason = ERR_R_EC_LIB;
190                         goto err;
191                 }
192                 if (!BN_nnmod(r,X,order,ctx)) goto err;
193         }
194         while (BN_is_zero(r));
195
196         /* compute the inverse of k */
197         if ((kinv = BN_mod_inverse(NULL,&k,order,ctx)) == NULL) goto err;
198
199         if (*rp == NULL)
200                 BN_clear_free(*rp);
201         *rp = r;
202         if (*kinvp == NULL) 
203                 BN_clear_free(*kinvp);
204         *kinvp = kinv;
205         kinv = NULL;
206         ret = 1;
207 err:
208         if (!ret)
209         {
210                 ECDSAerr(ECDSA_F_ECDSA_SIGN_SETUP,reason);
211                 if (kinv != NULL) BN_clear_free(kinv);
212                 if (r != NULL) BN_clear_free(r);
213         }
214         if (ctx_in == NULL) 
215                 BN_CTX_free(ctx);
216         if (kinv != NULL)
217                 BN_clear_free(kinv);
218         if (order != NULL)
219                 BN_clear_free(order);
220         if (tmp_point != NULL) 
221                 EC_POINT_free(tmp_point);
222         if (X)  BN_clear_free(X);
223         BN_clear_free(&k);
224         return(ret);
225 }
226
227
228 static ECDSA_SIG *ecdsa_do_sign(const unsigned char *dgst, int dgst_len, ECDSA *ecdsa)
229 {
230         BIGNUM *kinv=NULL,*r=NULL,*s=NULL,*m=NULL,*tmp=NULL,*order=NULL;
231         BIGNUM xr;
232         BN_CTX *ctx=NULL;
233         int reason=ERR_R_BN_LIB;
234         ECDSA_SIG *ret=NULL;
235
236         if (!ecdsa || !ecdsa->group || !ecdsa->pub_key || !ecdsa->priv_key)
237         {
238                 reason = ECDSA_R_MISSING_PARAMETERS;
239                 goto err;
240         }
241         BN_init(&xr);
242
243         if ((ctx = BN_CTX_new()) == NULL) goto err;
244         if ((order = BN_new()) == NULL) goto err;
245         if ((tmp = BN_new()) == NULL) goto err;
246         if ((m = BN_new()) == NULL) goto err;
247         if ((s = BN_new()) == NULL) goto err;
248
249         if (!EC_GROUP_get_order(ecdsa->group,order,ctx))
250         {
251                 reason = ECDSA_R_ERR_EC_LIB;
252                 goto err;
253         }
254         if (dgst_len > BN_num_bytes(order))
255         {
256                 reason = ECDSA_R_DATA_TOO_LARGE_FOR_KEY_SIZE;
257                 goto err;
258         }
259
260         if (BN_bin2bn(dgst,dgst_len,m) == NULL) goto err;
261         do
262         {
263                 if ((ecdsa->kinv == NULL) || (ecdsa->r == NULL))
264                 {
265                         if (!ECDSA_sign_setup(ecdsa,ctx,&kinv,&r)) goto err;
266                 }
267                 else
268                 {
269                         kinv = ecdsa->kinv;
270                         ecdsa->kinv = NULL;
271                         r = ecdsa->r;
272                         ecdsa->r = NULL;
273                 }
274
275                 if (!BN_mod_mul(tmp,ecdsa->priv_key,r,order,ctx)) goto err;
276                 if (!BN_add(s,tmp,m)) goto err;
277                 if (BN_cmp(s,order) > 0)
278                         BN_sub(s,s,order);
279                 if (!BN_mod_mul(s,s,kinv,order,ctx)) goto err;
280         }
281         while (BN_is_zero(s));
282
283         if ((ret = ECDSA_SIG_new()) == NULL)
284         {
285                 reason = ECDSA_R_SIGNATURE_MALLOC_FAILED;
286                 goto err;
287         }
288         ret->r = r;
289         ret->s = s;
290         
291 err:
292         if (!ret)
293                 {
294                 ECDSAerr(ECDSA_F_ECDSA_DO_SIGN,reason);
295                 BN_free(r);
296                 BN_free(s);
297                 }
298         if (ctx   != NULL) BN_CTX_free(ctx);
299         if (m     != NULL) BN_clear_free(m);
300         if (tmp   != NULL) BN_clear_free(tmp);
301         if (order != NULL) BN_clear_free(order);
302         if (kinv  != NULL) BN_clear_free(kinv);
303         return(ret);
304 }
305
306 static int ecdsa_do_verify(const unsigned char *dgst, int dgst_len, ECDSA_SIG *sig,
307                            ECDSA *ecdsa)
308 {
309         BN_CTX *ctx;
310         BIGNUM *order=NULL,*u1=NULL,*u2=NULL,*m=NULL,*X=NULL;
311         EC_POINT *point=NULL;
312         int ret = -1,reason = ERR_R_BN_LIB;
313         if (!ecdsa || !ecdsa->group || !ecdsa->pub_key || !sig)
314         {
315                 reason = ECDSA_R_MISSING_PARAMETERS;
316                 return -1;
317         }
318
319         if ((ctx = BN_CTX_new()) == NULL) goto err;
320         if ((order = BN_new()) == NULL) goto err;
321         if ((u1 = BN_new()) == NULL) goto err;
322         if ((u2 = BN_new()) == NULL) goto err;
323         if ((m  = BN_new()) == NULL) goto err;
324         if ((X  = BN_new()) == NULL) goto err;
325         if (!EC_GROUP_get_order(ecdsa->group,order,ctx)) goto err;
326
327         if (BN_is_zero(sig->r) || sig->r->neg || BN_ucmp(sig->r, order) >= 0)
328         {
329                 reason = ECDSA_R_BAD_SIGNATURE;
330                 ret = 0;
331                 goto err;
332         }
333         if (BN_is_zero(sig->s) || sig->s->neg || BN_ucmp(sig->s, order) >= 0)
334         {
335                 reason = ECDSA_R_BAD_SIGNATURE;
336                 ret = 0;
337                 goto err;
338         }
339
340         /* calculate tmp1 = inv(S) mod order */
341         if ((BN_mod_inverse(u2,sig->s,order,ctx)) == NULL) goto err;
342         /* digest -> m */
343         if (BN_bin2bn(dgst,dgst_len,m) == NULL) goto err;
344         /* u1 = m * tmp mod order */
345         if (!BN_mod_mul(u1,m,u2,order,ctx)) goto err;
346         /* u2 = r * w mod q */
347         if (!BN_mod_mul(u2,sig->r,u2,order,ctx)) goto err;
348
349         if ((point = EC_POINT_new(ecdsa->group)) == NULL)
350         {
351                 reason = ERR_R_EC_LIB;
352                 goto err;
353         }
354         if (!EC_POINT_copy(point,EC_GROUP_get0_generator(ecdsa->group)))
355         {
356                 reason = ERR_R_EC_LIB;
357                 goto err;
358         }
359         if (!EC_POINT_mul(ecdsa->group,point,u1,ecdsa->pub_key,u2,ctx)
360             || !EC_POINT_get_affine_coordinates(ecdsa->group,point,X,NULL,ctx))
361         {
362                 reason = ERR_R_EC_LIB;
363                 goto err;
364         }
365         if (!BN_nnmod(u1,X,order,ctx)) goto err;
366
367         /*  is now in u1.  If the signature is correct, it will be
368          * equal to R. */
369         ret = (BN_ucmp(u1,sig->r) == 0);
370
371         err:
372         if (ret != 1) ECDSAerr(ECDSA_F_ECDSA_DO_VERIFY,reason);
373         if (ctx != NULL) BN_CTX_free(ctx);
374         if (u1  != NULL) BN_clear_free(u1);
375         if (u2  != NULL) BN_clear_free(u2);
376         if (m   != NULL) BN_clear_free(m);
377         if (X   != NULL) BN_clear_free(X);
378         if (order != NULL) BN_clear_free(order);
379         if (point != NULL) EC_POINT_free(point);
380         return(ret);
381 }