1 /* Originally written by Bodo Moeller and Nils Larsch for the OpenSSL project.
2  * ====================================================================
3  * Copyright (c) 1998-2005 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 /* ====================================================================
56  * Copyright 2002 Sun Microsystems, Inc. ALL RIGHTS RESERVED.
57  *
58  * Portions of the attached software ("Contribution") are developed by
59  * SUN MICROSYSTEMS, INC., and are contributed to the OpenSSL project.
60  *
61  * The Contribution is licensed pursuant to the OpenSSL open source
62  * license provided above.
63  *
64  * The elliptic curve binary polynomial software is originally written by
65  * Sheueling Chang Shantz and Douglas Stebila of Sun Microsystems
66  * Laboratories. */
67 
68 #include <openssl/ec.h>
69 
70 #include <openssl/bn.h>
71 #include <openssl/err.h>
72 #include <openssl/mem.h>
73 
74 #include "internal.h"
75 
76 
ec_GFp_mont_group_init(EC_GROUP * group)77 int ec_GFp_mont_group_init(EC_GROUP *group) {
78   int ok;
79 
80   ok = ec_GFp_simple_group_init(group);
81   group->mont = NULL;
82   group->one = NULL;
83   return ok;
84 }
85 
ec_GFp_mont_group_finish(EC_GROUP * group)86 void ec_GFp_mont_group_finish(EC_GROUP *group) {
87   BN_MONT_CTX_free(group->mont);
88   group->mont = NULL;
89   BN_free(group->one);
90   group->one = NULL;
91   ec_GFp_simple_group_finish(group);
92 }
93 
ec_GFp_mont_group_clear_finish(EC_GROUP * group)94 void ec_GFp_mont_group_clear_finish(EC_GROUP *group) {
95   BN_MONT_CTX_free(group->mont);
96   group->mont = NULL;
97   BN_clear_free(group->one);
98   group->one = NULL;
99   ec_GFp_simple_group_clear_finish(group);
100 }
101 
ec_GFp_mont_group_copy(EC_GROUP * dest,const EC_GROUP * src)102 int ec_GFp_mont_group_copy(EC_GROUP *dest, const EC_GROUP *src) {
103   BN_MONT_CTX_free(dest->mont);
104   dest->mont = NULL;
105   BN_clear_free(dest->one);
106   dest->one = NULL;
107 
108   if (!ec_GFp_simple_group_copy(dest, src)) {
109     return 0;
110   }
111 
112   if (src->mont != NULL) {
113     dest->mont = BN_MONT_CTX_new();
114     if (dest->mont == NULL) {
115       return 0;
116     }
117     if (!BN_MONT_CTX_copy(dest->mont, src->mont)) {
118       goto err;
119     }
120   }
121   if (src->one != NULL) {
122     dest->one = BN_dup(src->one);
123     if (dest->one == NULL) {
124       goto err;
125     }
126   }
127 
128   return 1;
129 
130 err:
131   BN_MONT_CTX_free(dest->mont);
132   dest->mont = NULL;
133   return 0;
134 }
135 
ec_GFp_mont_group_set_curve(EC_GROUP * group,const BIGNUM * p,const BIGNUM * a,const BIGNUM * b,BN_CTX * ctx)136 int ec_GFp_mont_group_set_curve(EC_GROUP *group, const BIGNUM *p,
137                                 const BIGNUM *a, const BIGNUM *b, BN_CTX *ctx) {
138   BN_CTX *new_ctx = NULL;
139   BN_MONT_CTX *mont = NULL;
140   BIGNUM *one = NULL;
141   int ret = 0;
142 
143   BN_MONT_CTX_free(group->mont);
144   group->mont = NULL;
145   BN_free(group->one);
146   group->one = NULL;
147 
148   if (ctx == NULL) {
149     ctx = new_ctx = BN_CTX_new();
150     if (ctx == NULL) {
151       return 0;
152     }
153   }
154 
155   mont = BN_MONT_CTX_new();
156   if (mont == NULL) {
157     goto err;
158   }
159   if (!BN_MONT_CTX_set(mont, p, ctx)) {
160     OPENSSL_PUT_ERROR(EC, ERR_R_BN_LIB);
161     goto err;
162   }
163   one = BN_new();
164   if (one == NULL || !BN_to_montgomery(one, BN_value_one(), mont, ctx)) {
165     goto err;
166   }
167 
168   group->mont = mont;
169   mont = NULL;
170   group->one = one;
171   one = NULL;
172 
173   ret = ec_GFp_simple_group_set_curve(group, p, a, b, ctx);
174 
175   if (!ret) {
176     BN_MONT_CTX_free(group->mont);
177     group->mont = NULL;
178     BN_free(group->one);
179     group->one = NULL;
180   }
181 
182 err:
183   BN_CTX_free(new_ctx);
184   BN_MONT_CTX_free(mont);
185   BN_free(one);
186   return ret;
187 }
188 
ec_GFp_mont_field_mul(const EC_GROUP * group,BIGNUM * r,const BIGNUM * a,const BIGNUM * b,BN_CTX * ctx)189 int ec_GFp_mont_field_mul(const EC_GROUP *group, BIGNUM *r, const BIGNUM *a,
190                           const BIGNUM *b, BN_CTX *ctx) {
191   if (group->mont == NULL) {
192     OPENSSL_PUT_ERROR(EC, EC_R_NOT_INITIALIZED);
193     return 0;
194   }
195 
196   return BN_mod_mul_montgomery(r, a, b, group->mont, ctx);
197 }
198 
ec_GFp_mont_field_sqr(const EC_GROUP * group,BIGNUM * r,const BIGNUM * a,BN_CTX * ctx)199 int ec_GFp_mont_field_sqr(const EC_GROUP *group, BIGNUM *r, const BIGNUM *a,
200                           BN_CTX *ctx) {
201   if (group->mont == NULL) {
202     OPENSSL_PUT_ERROR(EC, EC_R_NOT_INITIALIZED);
203     return 0;
204   }
205 
206   return BN_mod_mul_montgomery(r, a, a, group->mont, ctx);
207 }
208 
ec_GFp_mont_field_encode(const EC_GROUP * group,BIGNUM * r,const BIGNUM * a,BN_CTX * ctx)209 int ec_GFp_mont_field_encode(const EC_GROUP *group, BIGNUM *r, const BIGNUM *a,
210                              BN_CTX *ctx) {
211   if (group->mont == NULL) {
212     OPENSSL_PUT_ERROR(EC, EC_R_NOT_INITIALIZED);
213     return 0;
214   }
215 
216   return BN_to_montgomery(r, a, group->mont, ctx);
217 }
218 
ec_GFp_mont_field_decode(const EC_GROUP * group,BIGNUM * r,const BIGNUM * a,BN_CTX * ctx)219 int ec_GFp_mont_field_decode(const EC_GROUP *group, BIGNUM *r, const BIGNUM *a,
220                              BN_CTX *ctx) {
221   if (group->mont == NULL) {
222     OPENSSL_PUT_ERROR(EC, EC_R_NOT_INITIALIZED);
223     return 0;
224   }
225 
226   return BN_from_montgomery(r, a, group->mont, ctx);
227 }
228 
ec_GFp_mont_field_set_to_one(const EC_GROUP * group,BIGNUM * r,BN_CTX * ctx)229 int ec_GFp_mont_field_set_to_one(const EC_GROUP *group, BIGNUM *r,
230                                  BN_CTX *ctx) {
231   if (group->one == NULL) {
232     OPENSSL_PUT_ERROR(EC, EC_R_NOT_INITIALIZED);
233     return 0;
234   }
235 
236   if (!BN_copy(r, group->one)) {
237     return 0;
238   }
239   return 1;
240 }
241 
ec_GFp_mont_check_pub_key_order(const EC_GROUP * group,const EC_POINT * pub_key,BN_CTX * ctx)242 static int ec_GFp_mont_check_pub_key_order(const EC_GROUP *group,
243                                            const EC_POINT* pub_key,
244                                            BN_CTX *ctx) {
245   EC_POINT *point = EC_POINT_new(group);
246   int ret = 0;
247 
248   if (point == NULL ||
249       !ec_wNAF_mul(group, point, NULL, pub_key, EC_GROUP_get0_order(group),
250                    ctx) ||
251       !EC_POINT_is_at_infinity(group, point)) {
252     goto err;
253   }
254 
255   ret = 1;
256 
257 err:
258   EC_POINT_free(point);
259   return ret;
260 }
261 
EC_GFp_mont_method(void)262 const EC_METHOD *EC_GFp_mont_method(void) {
263   static const EC_METHOD ret = {
264     ec_GFp_mont_group_init,
265     ec_GFp_mont_group_finish,
266     ec_GFp_mont_group_clear_finish,
267     ec_GFp_mont_group_copy,
268     ec_GFp_mont_group_set_curve,
269     ec_GFp_simple_point_get_affine_coordinates,
270     ec_wNAF_mul /* XXX: Not constant time. */,
271     ec_GFp_mont_check_pub_key_order,
272     ec_GFp_mont_field_mul,
273     ec_GFp_mont_field_sqr,
274     ec_GFp_mont_field_encode,
275     ec_GFp_mont_field_decode,
276     ec_GFp_mont_field_set_to_one,
277   };
278 
279   return &ret;
280 }
281