1 /* Originally written by Bodo Moeller 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 <assert.h>
71 #include <string.h>
72
73 #include <openssl/bn.h>
74 #include <openssl/err.h>
75 #include <openssl/mem.h>
76 #include <openssl/nid.h>
77
78 #include "internal.h"
79 #include "../../internal.h"
80 #include "../bn/internal.h"
81 #include "../delocate.h"
82
83
84 static void ec_point_free(EC_POINT *point, int free_group);
85
86 static const uint8_t kP224Params[6 * 28] = {
87 // p = 2^224 - 2^96 + 1
88 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF,
89 0xFF, 0xFF, 0xFF, 0xFF, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
90 0x00, 0x00, 0x00, 0x01,
91 // a
92 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF,
93 0xFF, 0xFF, 0xFF, 0xFE, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF,
94 0xFF, 0xFF, 0xFF, 0xFE,
95 // b
96 0xB4, 0x05, 0x0A, 0x85, 0x0C, 0x04, 0xB3, 0xAB, 0xF5, 0x41, 0x32, 0x56,
97 0x50, 0x44, 0xB0, 0xB7, 0xD7, 0xBF, 0xD8, 0xBA, 0x27, 0x0B, 0x39, 0x43,
98 0x23, 0x55, 0xFF, 0xB4,
99 // x
100 0xB7, 0x0E, 0x0C, 0xBD, 0x6B, 0xB4, 0xBF, 0x7F, 0x32, 0x13, 0x90, 0xB9,
101 0x4A, 0x03, 0xC1, 0xD3, 0x56, 0xC2, 0x11, 0x22, 0x34, 0x32, 0x80, 0xD6,
102 0x11, 0x5C, 0x1D, 0x21,
103 // y
104 0xbd, 0x37, 0x63, 0x88, 0xb5, 0xf7, 0x23, 0xfb, 0x4c, 0x22, 0xdf, 0xe6,
105 0xcd, 0x43, 0x75, 0xa0, 0x5a, 0x07, 0x47, 0x64, 0x44, 0xd5, 0x81, 0x99,
106 0x85, 0x00, 0x7e, 0x34,
107 // order
108 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF,
109 0xFF, 0xFF, 0x16, 0xA2, 0xE0, 0xB8, 0xF0, 0x3E, 0x13, 0xDD, 0x29, 0x45,
110 0x5C, 0x5C, 0x2A, 0x3D,
111 };
112
113 static const uint8_t kP256Params[6 * 32] = {
114 // p = 2^256 - 2^224 + 2^192 + 2^96 - 1
115 0xFF, 0xFF, 0xFF, 0xFF, 0x00, 0x00, 0x00, 0x01, 0x00, 0x00, 0x00, 0x00,
116 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0xFF, 0xFF, 0xFF, 0xFF,
117 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF,
118 // a
119 0xFF, 0xFF, 0xFF, 0xFF, 0x00, 0x00, 0x00, 0x01, 0x00, 0x00, 0x00, 0x00,
120 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0xFF, 0xFF, 0xFF, 0xFF,
121 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFC,
122 // b
123 0x5A, 0xC6, 0x35, 0xD8, 0xAA, 0x3A, 0x93, 0xE7, 0xB3, 0xEB, 0xBD, 0x55,
124 0x76, 0x98, 0x86, 0xBC, 0x65, 0x1D, 0x06, 0xB0, 0xCC, 0x53, 0xB0, 0xF6,
125 0x3B, 0xCE, 0x3C, 0x3E, 0x27, 0xD2, 0x60, 0x4B,
126 // x
127 0x6B, 0x17, 0xD1, 0xF2, 0xE1, 0x2C, 0x42, 0x47, 0xF8, 0xBC, 0xE6, 0xE5,
128 0x63, 0xA4, 0x40, 0xF2, 0x77, 0x03, 0x7D, 0x81, 0x2D, 0xEB, 0x33, 0xA0,
129 0xF4, 0xA1, 0x39, 0x45, 0xD8, 0x98, 0xC2, 0x96,
130 // y
131 0x4f, 0xe3, 0x42, 0xe2, 0xfe, 0x1a, 0x7f, 0x9b, 0x8e, 0xe7, 0xeb, 0x4a,
132 0x7c, 0x0f, 0x9e, 0x16, 0x2b, 0xce, 0x33, 0x57, 0x6b, 0x31, 0x5e, 0xce,
133 0xcb, 0xb6, 0x40, 0x68, 0x37, 0xbf, 0x51, 0xf5,
134 // order
135 0xFF, 0xFF, 0xFF, 0xFF, 0x00, 0x00, 0x00, 0x00, 0xFF, 0xFF, 0xFF, 0xFF,
136 0xFF, 0xFF, 0xFF, 0xFF, 0xBC, 0xE6, 0xFA, 0xAD, 0xA7, 0x17, 0x9E, 0x84,
137 0xF3, 0xB9, 0xCA, 0xC2, 0xFC, 0x63, 0x25, 0x51,
138 };
139
140 static const uint8_t kP384Params[6 * 48] = {
141 // p = 2^384 - 2^128 - 2^96 + 2^32 - 1
142 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF,
143 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF,
144 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFE, 0xFF, 0xFF, 0xFF, 0xFF,
145 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0xFF, 0xFF, 0xFF, 0xFF,
146 // a
147 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF,
148 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF,
149 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFE, 0xFF, 0xFF, 0xFF, 0xFF,
150 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0xFF, 0xFF, 0xFF, 0xFC,
151 // b
152 0xB3, 0x31, 0x2F, 0xA7, 0xE2, 0x3E, 0xE7, 0xE4, 0x98, 0x8E, 0x05, 0x6B,
153 0xE3, 0xF8, 0x2D, 0x19, 0x18, 0x1D, 0x9C, 0x6E, 0xFE, 0x81, 0x41, 0x12,
154 0x03, 0x14, 0x08, 0x8F, 0x50, 0x13, 0x87, 0x5A, 0xC6, 0x56, 0x39, 0x8D,
155 0x8A, 0x2E, 0xD1, 0x9D, 0x2A, 0x85, 0xC8, 0xED, 0xD3, 0xEC, 0x2A, 0xEF,
156 // x
157 0xAA, 0x87, 0xCA, 0x22, 0xBE, 0x8B, 0x05, 0x37, 0x8E, 0xB1, 0xC7, 0x1E,
158 0xF3, 0x20, 0xAD, 0x74, 0x6E, 0x1D, 0x3B, 0x62, 0x8B, 0xA7, 0x9B, 0x98,
159 0x59, 0xF7, 0x41, 0xE0, 0x82, 0x54, 0x2A, 0x38, 0x55, 0x02, 0xF2, 0x5D,
160 0xBF, 0x55, 0x29, 0x6C, 0x3A, 0x54, 0x5E, 0x38, 0x72, 0x76, 0x0A, 0xB7,
161 // y
162 0x36, 0x17, 0xde, 0x4a, 0x96, 0x26, 0x2c, 0x6f, 0x5d, 0x9e, 0x98, 0xbf,
163 0x92, 0x92, 0xdc, 0x29, 0xf8, 0xf4, 0x1d, 0xbd, 0x28, 0x9a, 0x14, 0x7c,
164 0xe9, 0xda, 0x31, 0x13, 0xb5, 0xf0, 0xb8, 0xc0, 0x0a, 0x60, 0xb1, 0xce,
165 0x1d, 0x7e, 0x81, 0x9d, 0x7a, 0x43, 0x1d, 0x7c, 0x90, 0xea, 0x0e, 0x5f,
166 // order
167 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF,
168 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF,
169 0xC7, 0x63, 0x4D, 0x81, 0xF4, 0x37, 0x2D, 0xDF, 0x58, 0x1A, 0x0D, 0xB2,
170 0x48, 0xB0, 0xA7, 0x7A, 0xEC, 0xEC, 0x19, 0x6A, 0xCC, 0xC5, 0x29, 0x73,
171 };
172
173 static const uint8_t kP521Params[6 * 66] = {
174 // p = 2^521 - 1
175 0x01, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF,
176 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF,
177 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF,
178 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF,
179 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF,
180 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF,
181 // a
182 0x01, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF,
183 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF,
184 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF,
185 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF,
186 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF,
187 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFC,
188 // b
189 0x00, 0x51, 0x95, 0x3E, 0xB9, 0x61, 0x8E, 0x1C, 0x9A, 0x1F, 0x92, 0x9A,
190 0x21, 0xA0, 0xB6, 0x85, 0x40, 0xEE, 0xA2, 0xDA, 0x72, 0x5B, 0x99, 0xB3,
191 0x15, 0xF3, 0xB8, 0xB4, 0x89, 0x91, 0x8E, 0xF1, 0x09, 0xE1, 0x56, 0x19,
192 0x39, 0x51, 0xEC, 0x7E, 0x93, 0x7B, 0x16, 0x52, 0xC0, 0xBD, 0x3B, 0xB1,
193 0xBF, 0x07, 0x35, 0x73, 0xDF, 0x88, 0x3D, 0x2C, 0x34, 0xF1, 0xEF, 0x45,
194 0x1F, 0xD4, 0x6B, 0x50, 0x3F, 0x00,
195 // x
196 0x00, 0xC6, 0x85, 0x8E, 0x06, 0xB7, 0x04, 0x04, 0xE9, 0xCD, 0x9E, 0x3E,
197 0xCB, 0x66, 0x23, 0x95, 0xB4, 0x42, 0x9C, 0x64, 0x81, 0x39, 0x05, 0x3F,
198 0xB5, 0x21, 0xF8, 0x28, 0xAF, 0x60, 0x6B, 0x4D, 0x3D, 0xBA, 0xA1, 0x4B,
199 0x5E, 0x77, 0xEF, 0xE7, 0x59, 0x28, 0xFE, 0x1D, 0xC1, 0x27, 0xA2, 0xFF,
200 0xA8, 0xDE, 0x33, 0x48, 0xB3, 0xC1, 0x85, 0x6A, 0x42, 0x9B, 0xF9, 0x7E,
201 0x7E, 0x31, 0xC2, 0xE5, 0xBD, 0x66,
202 // y
203 0x01, 0x18, 0x39, 0x29, 0x6a, 0x78, 0x9a, 0x3b, 0xc0, 0x04, 0x5c, 0x8a,
204 0x5f, 0xb4, 0x2c, 0x7d, 0x1b, 0xd9, 0x98, 0xf5, 0x44, 0x49, 0x57, 0x9b,
205 0x44, 0x68, 0x17, 0xaf, 0xbd, 0x17, 0x27, 0x3e, 0x66, 0x2c, 0x97, 0xee,
206 0x72, 0x99, 0x5e, 0xf4, 0x26, 0x40, 0xc5, 0x50, 0xb9, 0x01, 0x3f, 0xad,
207 0x07, 0x61, 0x35, 0x3c, 0x70, 0x86, 0xa2, 0x72, 0xc2, 0x40, 0x88, 0xbe,
208 0x94, 0x76, 0x9f, 0xd1, 0x66, 0x50,
209 // order
210 0x01, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF,
211 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF,
212 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFA, 0x51, 0x86,
213 0x87, 0x83, 0xBF, 0x2F, 0x96, 0x6B, 0x7F, 0xCC, 0x01, 0x48, 0xF7, 0x09,
214 0xA5, 0xD0, 0x3B, 0xB5, 0xC9, 0xB8, 0x89, 0x9C, 0x47, 0xAE, 0xBB, 0x6F,
215 0xB7, 0x1E, 0x91, 0x38, 0x64, 0x09,
216 };
217
DEFINE_METHOD_FUNCTION(struct built_in_curves,OPENSSL_built_in_curves)218 DEFINE_METHOD_FUNCTION(struct built_in_curves, OPENSSL_built_in_curves) {
219 // 1.3.132.0.35
220 static const uint8_t kOIDP521[] = {0x2b, 0x81, 0x04, 0x00, 0x23};
221 out->curves[0].nid = NID_secp521r1;
222 out->curves[0].oid = kOIDP521;
223 out->curves[0].oid_len = sizeof(kOIDP521);
224 out->curves[0].comment = "NIST P-521";
225 out->curves[0].param_len = 66;
226 out->curves[0].params = kP521Params;
227 out->curves[0].method = EC_GFp_mont_method();
228
229 // 1.3.132.0.34
230 static const uint8_t kOIDP384[] = {0x2b, 0x81, 0x04, 0x00, 0x22};
231 out->curves[1].nid = NID_secp384r1;
232 out->curves[1].oid = kOIDP384;
233 out->curves[1].oid_len = sizeof(kOIDP384);
234 out->curves[1].comment = "NIST P-384";
235 out->curves[1].param_len = 48;
236 out->curves[1].params = kP384Params;
237 out->curves[1].method = EC_GFp_mont_method();
238
239 // 1.2.840.10045.3.1.7
240 static const uint8_t kOIDP256[] = {0x2a, 0x86, 0x48, 0xce,
241 0x3d, 0x03, 0x01, 0x07};
242 out->curves[2].nid = NID_X9_62_prime256v1;
243 out->curves[2].oid = kOIDP256;
244 out->curves[2].oid_len = sizeof(kOIDP256);
245 out->curves[2].comment = "NIST P-256";
246 out->curves[2].param_len = 32;
247 out->curves[2].params = kP256Params;
248 out->curves[2].method =
249 #if !defined(OPENSSL_NO_ASM) && defined(OPENSSL_X86_64) && \
250 !defined(OPENSSL_SMALL)
251 EC_GFp_nistz256_method();
252 #else
253 EC_GFp_nistp256_method();
254 #endif
255
256 // 1.3.132.0.33
257 static const uint8_t kOIDP224[] = {0x2b, 0x81, 0x04, 0x00, 0x21};
258 out->curves[3].nid = NID_secp224r1;
259 out->curves[3].oid = kOIDP224;
260 out->curves[3].oid_len = sizeof(kOIDP224);
261 out->curves[3].comment = "NIST P-224";
262 out->curves[3].param_len = 28;
263 out->curves[3].params = kP224Params;
264 out->curves[3].method =
265 #if defined(BORINGSSL_HAS_UINT128) && !defined(OPENSSL_SMALL)
266 EC_GFp_nistp224_method();
267 #else
268 EC_GFp_mont_method();
269 #endif
270 }
271
ec_group_new(const EC_METHOD * meth)272 EC_GROUP *ec_group_new(const EC_METHOD *meth) {
273 EC_GROUP *ret;
274
275 if (meth == NULL) {
276 OPENSSL_PUT_ERROR(EC, EC_R_SLOT_FULL);
277 return NULL;
278 }
279
280 if (meth->group_init == 0) {
281 OPENSSL_PUT_ERROR(EC, ERR_R_SHOULD_NOT_HAVE_BEEN_CALLED);
282 return NULL;
283 }
284
285 ret = OPENSSL_malloc(sizeof(EC_GROUP));
286 if (ret == NULL) {
287 OPENSSL_PUT_ERROR(EC, ERR_R_MALLOC_FAILURE);
288 return NULL;
289 }
290 OPENSSL_memset(ret, 0, sizeof(EC_GROUP));
291
292 ret->references = 1;
293 ret->meth = meth;
294 BN_init(&ret->order);
295
296 if (!meth->group_init(ret)) {
297 OPENSSL_free(ret);
298 return NULL;
299 }
300
301 return ret;
302 }
303
ec_group_set_generator(EC_GROUP * group,const EC_AFFINE * generator,const BIGNUM * order)304 static int ec_group_set_generator(EC_GROUP *group, const EC_AFFINE *generator,
305 const BIGNUM *order) {
306 assert(group->generator == NULL);
307
308 if (!BN_copy(&group->order, order)) {
309 return 0;
310 }
311 // Store the order in minimal form, so it can be used with |BN_ULONG| arrays.
312 bn_set_minimal_width(&group->order);
313
314 BN_MONT_CTX_free(group->order_mont);
315 group->order_mont = BN_MONT_CTX_new_for_modulus(&group->order, NULL);
316 if (group->order_mont == NULL) {
317 return 0;
318 }
319
320 group->field_greater_than_order = BN_cmp(&group->field, order) > 0;
321 if (group->field_greater_than_order) {
322 BIGNUM tmp;
323 BN_init(&tmp);
324 int ok =
325 BN_sub(&tmp, &group->field, order) &&
326 bn_copy_words(group->field_minus_order.words, group->field.width, &tmp);
327 BN_free(&tmp);
328 if (!ok) {
329 return 0;
330 }
331 }
332
333 group->generator = EC_POINT_new(group);
334 if (group->generator == NULL) {
335 return 0;
336 }
337 ec_affine_to_jacobian(group, &group->generator->raw, generator);
338 assert(ec_felem_equal(group, &group->one, &group->generator->raw.Z));
339
340 // Avoid a reference cycle. |group->generator| does not maintain an owning
341 // pointer to |group|.
342 int is_zero = CRYPTO_refcount_dec_and_test_zero(&group->references);
343
344 assert(!is_zero);
345 (void)is_zero;
346 return 1;
347 }
348
EC_GROUP_new_curve_GFp(const BIGNUM * p,const BIGNUM * a,const BIGNUM * b,BN_CTX * ctx)349 EC_GROUP *EC_GROUP_new_curve_GFp(const BIGNUM *p, const BIGNUM *a,
350 const BIGNUM *b, BN_CTX *ctx) {
351 if (BN_num_bytes(p) > EC_MAX_BYTES) {
352 OPENSSL_PUT_ERROR(EC, EC_R_INVALID_FIELD);
353 return NULL;
354 }
355
356 BN_CTX *new_ctx = NULL;
357 if (ctx == NULL) {
358 ctx = new_ctx = BN_CTX_new();
359 if (ctx == NULL) {
360 return NULL;
361 }
362 }
363
364 // Historically, |a| and |b| were not required to be fully reduced.
365 // TODO(davidben): Can this be removed?
366 EC_GROUP *ret = NULL;
367 BN_CTX_start(ctx);
368 BIGNUM *a_reduced = BN_CTX_get(ctx);
369 BIGNUM *b_reduced = BN_CTX_get(ctx);
370 if (a_reduced == NULL || b_reduced == NULL ||
371 !BN_nnmod(a_reduced, a, p, ctx) ||
372 !BN_nnmod(b_reduced, b, p, ctx)) {
373 goto err;
374 }
375
376 ret = ec_group_new(EC_GFp_mont_method());
377 if (ret == NULL ||
378 !ret->meth->group_set_curve(ret, p, a_reduced, b_reduced, ctx)) {
379 EC_GROUP_free(ret);
380 ret = NULL;
381 goto err;
382 }
383
384 err:
385 BN_CTX_end(ctx);
386 BN_CTX_free(new_ctx);
387 return ret;
388 }
389
EC_GROUP_set_generator(EC_GROUP * group,const EC_POINT * generator,const BIGNUM * order,const BIGNUM * cofactor)390 int EC_GROUP_set_generator(EC_GROUP *group, const EC_POINT *generator,
391 const BIGNUM *order, const BIGNUM *cofactor) {
392 if (group->curve_name != NID_undef || group->generator != NULL ||
393 generator->group != group) {
394 // |EC_GROUP_set_generator| may only be used with |EC_GROUP|s returned by
395 // |EC_GROUP_new_curve_GFp| and may only used once on each group.
396 // |generator| must have been created from |EC_GROUP_new_curve_GFp|, not a
397 // copy, so that |generator->group->generator| is set correctly.
398 OPENSSL_PUT_ERROR(EC, ERR_R_SHOULD_NOT_HAVE_BEEN_CALLED);
399 return 0;
400 }
401
402 if (BN_num_bytes(order) > EC_MAX_BYTES) {
403 OPENSSL_PUT_ERROR(EC, EC_R_INVALID_GROUP_ORDER);
404 return 0;
405 }
406
407 // Require a cofactor of one for custom curves, which implies prime order.
408 if (!BN_is_one(cofactor)) {
409 OPENSSL_PUT_ERROR(EC, EC_R_INVALID_COFACTOR);
410 return 0;
411 }
412
413 // Require that p < 2×order. This simplifies some ECDSA operations.
414 //
415 // Note any curve which did not satisfy this must have been invalid or use a
416 // tiny prime (less than 17). See the proof in |field_element_to_scalar| in
417 // the ECDSA implementation.
418 int ret = 0;
419 BIGNUM *tmp = BN_new();
420 if (tmp == NULL ||
421 !BN_lshift1(tmp, order)) {
422 goto err;
423 }
424 if (BN_cmp(tmp, &group->field) <= 0) {
425 OPENSSL_PUT_ERROR(EC, EC_R_INVALID_GROUP_ORDER);
426 goto err;
427 }
428
429 EC_AFFINE affine;
430 if (!ec_jacobian_to_affine(group, &affine, &generator->raw) ||
431 !ec_group_set_generator(group, &affine, order)) {
432 goto err;
433 }
434
435 ret = 1;
436
437 err:
438 BN_free(tmp);
439 return ret;
440 }
441
ec_group_new_from_data(const struct built_in_curve * curve)442 static EC_GROUP *ec_group_new_from_data(const struct built_in_curve *curve) {
443 EC_GROUP *group = NULL;
444 BIGNUM *p = NULL, *a = NULL, *b = NULL, *order = NULL;
445 int ok = 0;
446
447 BN_CTX *ctx = BN_CTX_new();
448 if (ctx == NULL) {
449 OPENSSL_PUT_ERROR(EC, ERR_R_MALLOC_FAILURE);
450 goto err;
451 }
452
453 const unsigned param_len = curve->param_len;
454 const uint8_t *params = curve->params;
455
456 if (!(p = BN_bin2bn(params + 0 * param_len, param_len, NULL)) ||
457 !(a = BN_bin2bn(params + 1 * param_len, param_len, NULL)) ||
458 !(b = BN_bin2bn(params + 2 * param_len, param_len, NULL)) ||
459 !(order = BN_bin2bn(params + 5 * param_len, param_len, NULL))) {
460 OPENSSL_PUT_ERROR(EC, ERR_R_BN_LIB);
461 goto err;
462 }
463
464 group = ec_group_new(curve->method);
465 if (group == NULL ||
466 !group->meth->group_set_curve(group, p, a, b, ctx)) {
467 OPENSSL_PUT_ERROR(EC, ERR_R_EC_LIB);
468 goto err;
469 }
470
471 EC_AFFINE G;
472 EC_FELEM x, y;
473 if (!ec_felem_from_bytes(group, &x, params + 3 * param_len, param_len) ||
474 !ec_felem_from_bytes(group, &y, params + 4 * param_len, param_len) ||
475 !ec_point_set_affine_coordinates(group, &G, &x, &y)) {
476 goto err;
477 }
478
479 if (!ec_group_set_generator(group, &G, order)) {
480 goto err;
481 }
482
483 ok = 1;
484
485 err:
486 if (!ok) {
487 EC_GROUP_free(group);
488 group = NULL;
489 }
490 BN_CTX_free(ctx);
491 BN_free(p);
492 BN_free(a);
493 BN_free(b);
494 BN_free(order);
495 return group;
496 }
497
498 // Built-in groups are allocated lazily and static once allocated.
499 // TODO(davidben): Make these actually static. https://crbug.com/boringssl/20.
500 struct built_in_groups_st {
501 EC_GROUP *groups[OPENSSL_NUM_BUILT_IN_CURVES];
502 };
DEFINE_BSS_GET(struct built_in_groups_st,built_in_groups)503 DEFINE_BSS_GET(struct built_in_groups_st, built_in_groups)
504 DEFINE_STATIC_MUTEX(built_in_groups_lock)
505
506 EC_GROUP *EC_GROUP_new_by_curve_name(int nid) {
507 struct built_in_groups_st *groups = built_in_groups_bss_get();
508 EC_GROUP **group_ptr = NULL;
509 const struct built_in_curves *const curves = OPENSSL_built_in_curves();
510 const struct built_in_curve *curve = NULL;
511 for (size_t i = 0; i < OPENSSL_NUM_BUILT_IN_CURVES; i++) {
512 if (curves->curves[i].nid == nid) {
513 curve = &curves->curves[i];
514 group_ptr = &groups->groups[i];
515 break;
516 }
517 }
518
519 if (curve == NULL) {
520 OPENSSL_PUT_ERROR(EC, EC_R_UNKNOWN_GROUP);
521 return NULL;
522 }
523
524 CRYPTO_STATIC_MUTEX_lock_read(built_in_groups_lock_bss_get());
525 EC_GROUP *ret = *group_ptr;
526 CRYPTO_STATIC_MUTEX_unlock_read(built_in_groups_lock_bss_get());
527 if (ret != NULL) {
528 return ret;
529 }
530
531 ret = ec_group_new_from_data(curve);
532 if (ret == NULL) {
533 return NULL;
534 }
535
536 EC_GROUP *to_free = NULL;
537 CRYPTO_STATIC_MUTEX_lock_write(built_in_groups_lock_bss_get());
538 if (*group_ptr == NULL) {
539 *group_ptr = ret;
540 // Filling in |ret->curve_name| makes |EC_GROUP_free| and |EC_GROUP_dup|
541 // into no-ops. At this point, |ret| is considered static.
542 ret->curve_name = nid;
543 } else {
544 to_free = ret;
545 ret = *group_ptr;
546 }
547 CRYPTO_STATIC_MUTEX_unlock_write(built_in_groups_lock_bss_get());
548
549 EC_GROUP_free(to_free);
550 return ret;
551 }
552
EC_GROUP_free(EC_GROUP * group)553 void EC_GROUP_free(EC_GROUP *group) {
554 if (group == NULL ||
555 // Built-in curves are static.
556 group->curve_name != NID_undef ||
557 !CRYPTO_refcount_dec_and_test_zero(&group->references)) {
558 return;
559 }
560
561 if (group->meth->group_finish != NULL) {
562 group->meth->group_finish(group);
563 }
564
565 ec_point_free(group->generator, 0 /* don't free group */);
566 BN_free(&group->order);
567 BN_MONT_CTX_free(group->order_mont);
568
569 OPENSSL_free(group);
570 }
571
EC_GROUP_dup(const EC_GROUP * a)572 EC_GROUP *EC_GROUP_dup(const EC_GROUP *a) {
573 if (a == NULL ||
574 // Built-in curves are static.
575 a->curve_name != NID_undef) {
576 return (EC_GROUP *)a;
577 }
578
579 // Groups are logically immutable (but for |EC_GROUP_set_generator| which must
580 // be called early on), so we simply take a reference.
581 EC_GROUP *group = (EC_GROUP *)a;
582 CRYPTO_refcount_inc(&group->references);
583 return group;
584 }
585
EC_GROUP_cmp(const EC_GROUP * a,const EC_GROUP * b,BN_CTX * ignored)586 int EC_GROUP_cmp(const EC_GROUP *a, const EC_GROUP *b, BN_CTX *ignored) {
587 // Note this function returns 0 if equal and non-zero otherwise.
588 if (a == b) {
589 return 0;
590 }
591 if (a->curve_name != b->curve_name) {
592 return 1;
593 }
594 if (a->curve_name != NID_undef) {
595 // Built-in curves may be compared by curve name alone.
596 return 0;
597 }
598
599 // |a| and |b| are both custom curves. We compare the entire curve
600 // structure. If |a| or |b| is incomplete (due to legacy OpenSSL mistakes,
601 // custom curve construction is sadly done in two parts) but otherwise not the
602 // same object, we consider them always unequal.
603 return a->meth != b->meth ||
604 a->generator == NULL ||
605 b->generator == NULL ||
606 BN_cmp(&a->order, &b->order) != 0 ||
607 BN_cmp(&a->field, &b->field) != 0 ||
608 !ec_felem_equal(a, &a->a, &b->a) ||
609 !ec_felem_equal(a, &a->b, &b->b) ||
610 !ec_GFp_simple_points_equal(a, &a->generator->raw, &b->generator->raw);
611 }
612
EC_GROUP_get0_generator(const EC_GROUP * group)613 const EC_POINT *EC_GROUP_get0_generator(const EC_GROUP *group) {
614 return group->generator;
615 }
616
EC_GROUP_get0_order(const EC_GROUP * group)617 const BIGNUM *EC_GROUP_get0_order(const EC_GROUP *group) {
618 assert(!BN_is_zero(&group->order));
619 return &group->order;
620 }
621
EC_GROUP_get_order(const EC_GROUP * group,BIGNUM * order,BN_CTX * ctx)622 int EC_GROUP_get_order(const EC_GROUP *group, BIGNUM *order, BN_CTX *ctx) {
623 if (BN_copy(order, EC_GROUP_get0_order(group)) == NULL) {
624 return 0;
625 }
626 return 1;
627 }
628
EC_GROUP_order_bits(const EC_GROUP * group)629 int EC_GROUP_order_bits(const EC_GROUP *group) {
630 return BN_num_bits(&group->order);
631 }
632
EC_GROUP_get_cofactor(const EC_GROUP * group,BIGNUM * cofactor,BN_CTX * ctx)633 int EC_GROUP_get_cofactor(const EC_GROUP *group, BIGNUM *cofactor,
634 BN_CTX *ctx) {
635 // All |EC_GROUP|s have cofactor 1.
636 return BN_set_word(cofactor, 1);
637 }
638
EC_GROUP_get_curve_GFp(const EC_GROUP * group,BIGNUM * out_p,BIGNUM * out_a,BIGNUM * out_b,BN_CTX * ctx)639 int EC_GROUP_get_curve_GFp(const EC_GROUP *group, BIGNUM *out_p, BIGNUM *out_a,
640 BIGNUM *out_b, BN_CTX *ctx) {
641 return ec_GFp_simple_group_get_curve(group, out_p, out_a, out_b);
642 }
643
EC_GROUP_get_curve_name(const EC_GROUP * group)644 int EC_GROUP_get_curve_name(const EC_GROUP *group) { return group->curve_name; }
645
EC_GROUP_get_degree(const EC_GROUP * group)646 unsigned EC_GROUP_get_degree(const EC_GROUP *group) {
647 return BN_num_bits(&group->field);
648 }
649
EC_curve_nid2nist(int nid)650 const char *EC_curve_nid2nist(int nid) {
651 switch (nid) {
652 case NID_secp224r1:
653 return "P-224";
654 case NID_X9_62_prime256v1:
655 return "P-256";
656 case NID_secp384r1:
657 return "P-384";
658 case NID_secp521r1:
659 return "P-521";
660 }
661 return NULL;
662 }
663
EC_curve_nist2nid(const char * name)664 int EC_curve_nist2nid(const char *name) {
665 if (strcmp(name, "P-224") == 0) {
666 return NID_secp224r1;
667 }
668 if (strcmp(name, "P-256") == 0) {
669 return NID_X9_62_prime256v1;
670 }
671 if (strcmp(name, "P-384") == 0) {
672 return NID_secp384r1;
673 }
674 if (strcmp(name, "P-521") == 0) {
675 return NID_secp521r1;
676 }
677 return NID_undef;
678 }
679
EC_POINT_new(const EC_GROUP * group)680 EC_POINT *EC_POINT_new(const EC_GROUP *group) {
681 if (group == NULL) {
682 OPENSSL_PUT_ERROR(EC, ERR_R_PASSED_NULL_PARAMETER);
683 return NULL;
684 }
685
686 EC_POINT *ret = OPENSSL_malloc(sizeof *ret);
687 if (ret == NULL) {
688 OPENSSL_PUT_ERROR(EC, ERR_R_MALLOC_FAILURE);
689 return NULL;
690 }
691
692 ret->group = EC_GROUP_dup(group);
693 ec_GFp_simple_point_init(&ret->raw);
694 return ret;
695 }
696
ec_point_free(EC_POINT * point,int free_group)697 static void ec_point_free(EC_POINT *point, int free_group) {
698 if (!point) {
699 return;
700 }
701 if (free_group) {
702 EC_GROUP_free(point->group);
703 }
704 OPENSSL_free(point);
705 }
706
EC_POINT_free(EC_POINT * point)707 void EC_POINT_free(EC_POINT *point) {
708 ec_point_free(point, 1 /* free group */);
709 }
710
EC_POINT_clear_free(EC_POINT * point)711 void EC_POINT_clear_free(EC_POINT *point) { EC_POINT_free(point); }
712
EC_POINT_copy(EC_POINT * dest,const EC_POINT * src)713 int EC_POINT_copy(EC_POINT *dest, const EC_POINT *src) {
714 if (EC_GROUP_cmp(dest->group, src->group, NULL) != 0) {
715 OPENSSL_PUT_ERROR(EC, EC_R_INCOMPATIBLE_OBJECTS);
716 return 0;
717 }
718 if (dest == src) {
719 return 1;
720 }
721 ec_GFp_simple_point_copy(&dest->raw, &src->raw);
722 return 1;
723 }
724
EC_POINT_dup(const EC_POINT * a,const EC_GROUP * group)725 EC_POINT *EC_POINT_dup(const EC_POINT *a, const EC_GROUP *group) {
726 if (a == NULL) {
727 return NULL;
728 }
729
730 EC_POINT *ret = EC_POINT_new(group);
731 if (ret == NULL ||
732 !EC_POINT_copy(ret, a)) {
733 EC_POINT_free(ret);
734 return NULL;
735 }
736
737 return ret;
738 }
739
EC_POINT_set_to_infinity(const EC_GROUP * group,EC_POINT * point)740 int EC_POINT_set_to_infinity(const EC_GROUP *group, EC_POINT *point) {
741 if (EC_GROUP_cmp(group, point->group, NULL) != 0) {
742 OPENSSL_PUT_ERROR(EC, EC_R_INCOMPATIBLE_OBJECTS);
743 return 0;
744 }
745 ec_GFp_simple_point_set_to_infinity(group, &point->raw);
746 return 1;
747 }
748
EC_POINT_is_at_infinity(const EC_GROUP * group,const EC_POINT * point)749 int EC_POINT_is_at_infinity(const EC_GROUP *group, const EC_POINT *point) {
750 if (EC_GROUP_cmp(group, point->group, NULL) != 0) {
751 OPENSSL_PUT_ERROR(EC, EC_R_INCOMPATIBLE_OBJECTS);
752 return 0;
753 }
754 return ec_GFp_simple_is_at_infinity(group, &point->raw);
755 }
756
EC_POINT_is_on_curve(const EC_GROUP * group,const EC_POINT * point,BN_CTX * ctx)757 int EC_POINT_is_on_curve(const EC_GROUP *group, const EC_POINT *point,
758 BN_CTX *ctx) {
759 if (EC_GROUP_cmp(group, point->group, NULL) != 0) {
760 OPENSSL_PUT_ERROR(EC, EC_R_INCOMPATIBLE_OBJECTS);
761 return 0;
762 }
763 return ec_GFp_simple_is_on_curve(group, &point->raw);
764 }
765
EC_POINT_cmp(const EC_GROUP * group,const EC_POINT * a,const EC_POINT * b,BN_CTX * ctx)766 int EC_POINT_cmp(const EC_GROUP *group, const EC_POINT *a, const EC_POINT *b,
767 BN_CTX *ctx) {
768 if (EC_GROUP_cmp(group, a->group, NULL) != 0 ||
769 EC_GROUP_cmp(group, b->group, NULL) != 0) {
770 OPENSSL_PUT_ERROR(EC, EC_R_INCOMPATIBLE_OBJECTS);
771 return -1;
772 }
773
774 // Note |EC_POINT_cmp| returns zero for equality and non-zero for inequality.
775 return ec_GFp_simple_points_equal(group, &a->raw, &b->raw) ? 0 : 1;
776 }
777
EC_POINT_get_affine_coordinates_GFp(const EC_GROUP * group,const EC_POINT * point,BIGNUM * x,BIGNUM * y,BN_CTX * ctx)778 int EC_POINT_get_affine_coordinates_GFp(const EC_GROUP *group,
779 const EC_POINT *point, BIGNUM *x,
780 BIGNUM *y, BN_CTX *ctx) {
781 if (group->meth->point_get_affine_coordinates == 0) {
782 OPENSSL_PUT_ERROR(EC, ERR_R_SHOULD_NOT_HAVE_BEEN_CALLED);
783 return 0;
784 }
785 if (EC_GROUP_cmp(group, point->group, NULL) != 0) {
786 OPENSSL_PUT_ERROR(EC, EC_R_INCOMPATIBLE_OBJECTS);
787 return 0;
788 }
789 EC_FELEM x_felem, y_felem;
790 if (!group->meth->point_get_affine_coordinates(group, &point->raw,
791 x == NULL ? NULL : &x_felem,
792 y == NULL ? NULL : &y_felem) ||
793 (x != NULL && !ec_felem_to_bignum(group, x, &x_felem)) ||
794 (y != NULL && !ec_felem_to_bignum(group, y, &y_felem))) {
795 return 0;
796 }
797 return 1;
798 }
799
EC_POINT_get_affine_coordinates(const EC_GROUP * group,const EC_POINT * point,BIGNUM * x,BIGNUM * y,BN_CTX * ctx)800 int EC_POINT_get_affine_coordinates(const EC_GROUP *group,
801 const EC_POINT *point, BIGNUM *x, BIGNUM *y,
802 BN_CTX *ctx) {
803 return EC_POINT_get_affine_coordinates_GFp(group, point, x, y, ctx);
804 }
805
ec_affine_to_jacobian(const EC_GROUP * group,EC_RAW_POINT * out,const EC_AFFINE * p)806 void ec_affine_to_jacobian(const EC_GROUP *group, EC_RAW_POINT *out,
807 const EC_AFFINE *p) {
808 out->X = p->X;
809 out->Y = p->Y;
810 out->Z = group->one;
811 }
812
ec_jacobian_to_affine(const EC_GROUP * group,EC_AFFINE * out,const EC_RAW_POINT * p)813 int ec_jacobian_to_affine(const EC_GROUP *group, EC_AFFINE *out,
814 const EC_RAW_POINT *p) {
815 return group->meth->point_get_affine_coordinates(group, p, &out->X, &out->Y);
816 }
817
ec_jacobian_to_affine_batch(const EC_GROUP * group,EC_AFFINE * out,const EC_RAW_POINT * in,size_t num)818 int ec_jacobian_to_affine_batch(const EC_GROUP *group, EC_AFFINE *out,
819 const EC_RAW_POINT *in, size_t num) {
820 if (group->meth->jacobian_to_affine_batch == NULL) {
821 OPENSSL_PUT_ERROR(EC, ERR_R_SHOULD_NOT_HAVE_BEEN_CALLED);
822 return 0;
823 }
824 return group->meth->jacobian_to_affine_batch(group, out, in, num);
825 }
826
ec_point_set_affine_coordinates(const EC_GROUP * group,EC_AFFINE * out,const EC_FELEM * x,const EC_FELEM * y)827 int ec_point_set_affine_coordinates(const EC_GROUP *group, EC_AFFINE *out,
828 const EC_FELEM *x, const EC_FELEM *y) {
829 void (*const felem_mul)(const EC_GROUP *, EC_FELEM *r, const EC_FELEM *a,
830 const EC_FELEM *b) = group->meth->felem_mul;
831 void (*const felem_sqr)(const EC_GROUP *, EC_FELEM *r, const EC_FELEM *a) =
832 group->meth->felem_sqr;
833
834 // Check if the point is on the curve.
835 EC_FELEM lhs, rhs;
836 felem_sqr(group, &lhs, y); // lhs = y^2
837 felem_sqr(group, &rhs, x); // rhs = x^2
838 ec_felem_add(group, &rhs, &rhs, &group->a); // rhs = x^2 + a
839 felem_mul(group, &rhs, &rhs, x); // rhs = x^3 + ax
840 ec_felem_add(group, &rhs, &rhs, &group->b); // rhs = x^3 + ax + b
841 if (!ec_felem_equal(group, &lhs, &rhs)) {
842 OPENSSL_PUT_ERROR(EC, EC_R_POINT_IS_NOT_ON_CURVE);
843 // In the event of an error, defend against the caller not checking the
844 // return value by setting a known safe value. Note this may not be possible
845 // if the caller is in the process of constructing an arbitrary group and
846 // the generator is missing.
847 if (group->generator != NULL) {
848 assert(ec_felem_equal(group, &group->one, &group->generator->raw.Z));
849 out->X = group->generator->raw.X;
850 out->Y = group->generator->raw.Y;
851 }
852 return 0;
853 }
854
855 out->X = *x;
856 out->Y = *y;
857 return 1;
858 }
859
EC_POINT_set_affine_coordinates_GFp(const EC_GROUP * group,EC_POINT * point,const BIGNUM * x,const BIGNUM * y,BN_CTX * ctx)860 int EC_POINT_set_affine_coordinates_GFp(const EC_GROUP *group, EC_POINT *point,
861 const BIGNUM *x, const BIGNUM *y,
862 BN_CTX *ctx) {
863 if (EC_GROUP_cmp(group, point->group, NULL) != 0) {
864 OPENSSL_PUT_ERROR(EC, EC_R_INCOMPATIBLE_OBJECTS);
865 return 0;
866 }
867
868 if (x == NULL || y == NULL) {
869 OPENSSL_PUT_ERROR(EC, ERR_R_PASSED_NULL_PARAMETER);
870 return 0;
871 }
872
873 EC_FELEM x_felem, y_felem;
874 EC_AFFINE affine;
875 if (!ec_bignum_to_felem(group, &x_felem, x) ||
876 !ec_bignum_to_felem(group, &y_felem, y) ||
877 !ec_point_set_affine_coordinates(group, &affine, &x_felem, &y_felem)) {
878 // In the event of an error, defend against the caller not checking the
879 // return value by setting a known safe value.
880 ec_set_to_safe_point(group, &point->raw);
881 return 0;
882 }
883
884 ec_affine_to_jacobian(group, &point->raw, &affine);
885 return 1;
886 }
887
EC_POINT_set_affine_coordinates(const EC_GROUP * group,EC_POINT * point,const BIGNUM * x,const BIGNUM * y,BN_CTX * ctx)888 int EC_POINT_set_affine_coordinates(const EC_GROUP *group, EC_POINT *point,
889 const BIGNUM *x, const BIGNUM *y,
890 BN_CTX *ctx) {
891 return EC_POINT_set_affine_coordinates_GFp(group, point, x, y, ctx);
892 }
893
EC_POINT_add(const EC_GROUP * group,EC_POINT * r,const EC_POINT * a,const EC_POINT * b,BN_CTX * ctx)894 int EC_POINT_add(const EC_GROUP *group, EC_POINT *r, const EC_POINT *a,
895 const EC_POINT *b, BN_CTX *ctx) {
896 if (EC_GROUP_cmp(group, r->group, NULL) != 0 ||
897 EC_GROUP_cmp(group, a->group, NULL) != 0 ||
898 EC_GROUP_cmp(group, b->group, NULL) != 0) {
899 OPENSSL_PUT_ERROR(EC, EC_R_INCOMPATIBLE_OBJECTS);
900 return 0;
901 }
902 group->meth->add(group, &r->raw, &a->raw, &b->raw);
903 return 1;
904 }
905
EC_POINT_dbl(const EC_GROUP * group,EC_POINT * r,const EC_POINT * a,BN_CTX * ctx)906 int EC_POINT_dbl(const EC_GROUP *group, EC_POINT *r, const EC_POINT *a,
907 BN_CTX *ctx) {
908 if (EC_GROUP_cmp(group, r->group, NULL) != 0 ||
909 EC_GROUP_cmp(group, a->group, NULL) != 0) {
910 OPENSSL_PUT_ERROR(EC, EC_R_INCOMPATIBLE_OBJECTS);
911 return 0;
912 }
913 group->meth->dbl(group, &r->raw, &a->raw);
914 return 1;
915 }
916
917
EC_POINT_invert(const EC_GROUP * group,EC_POINT * a,BN_CTX * ctx)918 int EC_POINT_invert(const EC_GROUP *group, EC_POINT *a, BN_CTX *ctx) {
919 if (EC_GROUP_cmp(group, a->group, NULL) != 0) {
920 OPENSSL_PUT_ERROR(EC, EC_R_INCOMPATIBLE_OBJECTS);
921 return 0;
922 }
923 ec_GFp_simple_invert(group, &a->raw);
924 return 1;
925 }
926
arbitrary_bignum_to_scalar(const EC_GROUP * group,EC_SCALAR * out,const BIGNUM * in,BN_CTX * ctx)927 static int arbitrary_bignum_to_scalar(const EC_GROUP *group, EC_SCALAR *out,
928 const BIGNUM *in, BN_CTX *ctx) {
929 if (ec_bignum_to_scalar(group, out, in)) {
930 return 1;
931 }
932
933 ERR_clear_error();
934
935 // This is an unusual input, so we do not guarantee constant-time processing.
936 const BIGNUM *order = &group->order;
937 BN_CTX_start(ctx);
938 BIGNUM *tmp = BN_CTX_get(ctx);
939 int ok = tmp != NULL &&
940 BN_nnmod(tmp, in, order, ctx) &&
941 ec_bignum_to_scalar(group, out, tmp);
942 BN_CTX_end(ctx);
943 return ok;
944 }
945
EC_POINT_mul(const EC_GROUP * group,EC_POINT * r,const BIGNUM * g_scalar,const EC_POINT * p,const BIGNUM * p_scalar,BN_CTX * ctx)946 int EC_POINT_mul(const EC_GROUP *group, EC_POINT *r, const BIGNUM *g_scalar,
947 const EC_POINT *p, const BIGNUM *p_scalar, BN_CTX *ctx) {
948 // Previously, this function set |r| to the point at infinity if there was
949 // nothing to multiply. But, nobody should be calling this function with
950 // nothing to multiply in the first place.
951 if ((g_scalar == NULL && p_scalar == NULL) ||
952 (p == NULL) != (p_scalar == NULL)) {
953 OPENSSL_PUT_ERROR(EC, ERR_R_PASSED_NULL_PARAMETER);
954 return 0;
955 }
956
957 if (EC_GROUP_cmp(group, r->group, NULL) != 0 ||
958 (p != NULL && EC_GROUP_cmp(group, p->group, NULL) != 0)) {
959 OPENSSL_PUT_ERROR(EC, EC_R_INCOMPATIBLE_OBJECTS);
960 return 0;
961 }
962
963 int ret = 0;
964 BN_CTX *new_ctx = NULL;
965 if (ctx == NULL) {
966 new_ctx = BN_CTX_new();
967 if (new_ctx == NULL) {
968 goto err;
969 }
970 ctx = new_ctx;
971 }
972
973 // If both |g_scalar| and |p_scalar| are non-NULL,
974 // |ec_point_mul_scalar_public| would share the doublings between the two
975 // products, which would be more efficient. However, we conservatively assume
976 // the caller needs a constant-time operation. (ECDSA verification does not
977 // use this function.)
978 //
979 // Previously, the low-level constant-time multiplication function aligned
980 // with this function's calling convention, but this was misleading. Curves
981 // which combined the two multiplications did not avoid the doubling case
982 // in the incomplete addition formula and were not constant-time.
983
984 if (g_scalar != NULL) {
985 EC_SCALAR scalar;
986 if (!arbitrary_bignum_to_scalar(group, &scalar, g_scalar, ctx) ||
987 !ec_point_mul_scalar_base(group, &r->raw, &scalar)) {
988 goto err;
989 }
990 }
991
992 if (p_scalar != NULL) {
993 EC_SCALAR scalar;
994 EC_RAW_POINT tmp;
995 if (!arbitrary_bignum_to_scalar(group, &scalar, p_scalar, ctx) ||
996 !ec_point_mul_scalar(group, &tmp, &p->raw, &scalar)) {
997 goto err;
998 }
999 if (g_scalar == NULL) {
1000 OPENSSL_memcpy(&r->raw, &tmp, sizeof(EC_RAW_POINT));
1001 } else {
1002 group->meth->add(group, &r->raw, &r->raw, &tmp);
1003 }
1004 }
1005
1006 ret = 1;
1007
1008 err:
1009 BN_CTX_free(new_ctx);
1010 return ret;
1011 }
1012
ec_point_mul_scalar_public(const EC_GROUP * group,EC_RAW_POINT * r,const EC_SCALAR * g_scalar,const EC_RAW_POINT * p,const EC_SCALAR * p_scalar)1013 int ec_point_mul_scalar_public(const EC_GROUP *group, EC_RAW_POINT *r,
1014 const EC_SCALAR *g_scalar, const EC_RAW_POINT *p,
1015 const EC_SCALAR *p_scalar) {
1016 if (g_scalar == NULL || p_scalar == NULL || p == NULL) {
1017 OPENSSL_PUT_ERROR(EC, ERR_R_PASSED_NULL_PARAMETER);
1018 return 0;
1019 }
1020
1021 if (group->meth->mul_public == NULL) {
1022 return group->meth->mul_public_batch(group, r, g_scalar, p, p_scalar, 1);
1023 }
1024
1025 group->meth->mul_public(group, r, g_scalar, p, p_scalar);
1026 return 1;
1027 }
1028
ec_point_mul_scalar_public_batch(const EC_GROUP * group,EC_RAW_POINT * r,const EC_SCALAR * g_scalar,const EC_RAW_POINT * points,const EC_SCALAR * scalars,size_t num)1029 int ec_point_mul_scalar_public_batch(const EC_GROUP *group, EC_RAW_POINT *r,
1030 const EC_SCALAR *g_scalar,
1031 const EC_RAW_POINT *points,
1032 const EC_SCALAR *scalars, size_t num) {
1033 if (group->meth->mul_public_batch == NULL) {
1034 OPENSSL_PUT_ERROR(EC, ERR_R_SHOULD_NOT_HAVE_BEEN_CALLED);
1035 return 0;
1036 }
1037
1038 return group->meth->mul_public_batch(group, r, g_scalar, points, scalars,
1039 num);
1040 }
1041
ec_point_mul_scalar(const EC_GROUP * group,EC_RAW_POINT * r,const EC_RAW_POINT * p,const EC_SCALAR * scalar)1042 int ec_point_mul_scalar(const EC_GROUP *group, EC_RAW_POINT *r,
1043 const EC_RAW_POINT *p, const EC_SCALAR *scalar) {
1044 if (p == NULL || scalar == NULL) {
1045 OPENSSL_PUT_ERROR(EC, ERR_R_PASSED_NULL_PARAMETER);
1046 return 0;
1047 }
1048
1049 group->meth->mul(group, r, p, scalar);
1050
1051 // Check the result is on the curve to defend against fault attacks or bugs.
1052 // This has negligible cost compared to the multiplication.
1053 if (!ec_GFp_simple_is_on_curve(group, r)) {
1054 OPENSSL_PUT_ERROR(EC, ERR_R_INTERNAL_ERROR);
1055 return 0;
1056 }
1057
1058 return 1;
1059 }
1060
ec_point_mul_scalar_base(const EC_GROUP * group,EC_RAW_POINT * r,const EC_SCALAR * scalar)1061 int ec_point_mul_scalar_base(const EC_GROUP *group, EC_RAW_POINT *r,
1062 const EC_SCALAR *scalar) {
1063 if (scalar == NULL) {
1064 OPENSSL_PUT_ERROR(EC, ERR_R_PASSED_NULL_PARAMETER);
1065 return 0;
1066 }
1067
1068 group->meth->mul_base(group, r, scalar);
1069
1070 // Check the result is on the curve to defend against fault attacks or bugs.
1071 // This has negligible cost compared to the multiplication.
1072 if (!ec_GFp_simple_is_on_curve(group, r)) {
1073 OPENSSL_PUT_ERROR(EC, ERR_R_INTERNAL_ERROR);
1074 return 0;
1075 }
1076
1077 return 1;
1078 }
1079
ec_point_mul_scalar_batch(const EC_GROUP * group,EC_RAW_POINT * r,const EC_RAW_POINT * p0,const EC_SCALAR * scalar0,const EC_RAW_POINT * p1,const EC_SCALAR * scalar1,const EC_RAW_POINT * p2,const EC_SCALAR * scalar2)1080 int ec_point_mul_scalar_batch(const EC_GROUP *group, EC_RAW_POINT *r,
1081 const EC_RAW_POINT *p0, const EC_SCALAR *scalar0,
1082 const EC_RAW_POINT *p1, const EC_SCALAR *scalar1,
1083 const EC_RAW_POINT *p2,
1084 const EC_SCALAR *scalar2) {
1085 if (group->meth->mul_batch == NULL) {
1086 OPENSSL_PUT_ERROR(EC, ERR_R_SHOULD_NOT_HAVE_BEEN_CALLED);
1087 return 0;
1088 }
1089
1090 group->meth->mul_batch(group, r, p0, scalar0, p1, scalar1, p2, scalar2);
1091
1092 // Check the result is on the curve to defend against fault attacks or bugs.
1093 // This has negligible cost compared to the multiplication.
1094 if (!ec_GFp_simple_is_on_curve(group, r)) {
1095 OPENSSL_PUT_ERROR(EC, ERR_R_INTERNAL_ERROR);
1096 return 0;
1097 }
1098
1099 return 1;
1100 }
1101
ec_init_precomp(const EC_GROUP * group,EC_PRECOMP * out,const EC_RAW_POINT * p)1102 int ec_init_precomp(const EC_GROUP *group, EC_PRECOMP *out,
1103 const EC_RAW_POINT *p) {
1104 if (group->meth->init_precomp == NULL) {
1105 OPENSSL_PUT_ERROR(EC, ERR_R_SHOULD_NOT_HAVE_BEEN_CALLED);
1106 return 0;
1107 }
1108
1109 return group->meth->init_precomp(group, out, p);
1110 }
1111
ec_point_mul_scalar_precomp(const EC_GROUP * group,EC_RAW_POINT * r,const EC_PRECOMP * p0,const EC_SCALAR * scalar0,const EC_PRECOMP * p1,const EC_SCALAR * scalar1,const EC_PRECOMP * p2,const EC_SCALAR * scalar2)1112 int ec_point_mul_scalar_precomp(const EC_GROUP *group, EC_RAW_POINT *r,
1113 const EC_PRECOMP *p0, const EC_SCALAR *scalar0,
1114 const EC_PRECOMP *p1, const EC_SCALAR *scalar1,
1115 const EC_PRECOMP *p2,
1116 const EC_SCALAR *scalar2) {
1117 if (group->meth->mul_precomp == NULL) {
1118 OPENSSL_PUT_ERROR(EC, ERR_R_SHOULD_NOT_HAVE_BEEN_CALLED);
1119 return 0;
1120 }
1121
1122 group->meth->mul_precomp(group, r, p0, scalar0, p1, scalar1, p2, scalar2);
1123
1124 // Check the result is on the curve to defend against fault attacks or bugs.
1125 // This has negligible cost compared to the multiplication.
1126 if (!ec_GFp_simple_is_on_curve(group, r)) {
1127 OPENSSL_PUT_ERROR(EC, ERR_R_INTERNAL_ERROR);
1128 return 0;
1129 }
1130
1131 return 1;
1132 }
1133
ec_point_select(const EC_GROUP * group,EC_RAW_POINT * out,BN_ULONG mask,const EC_RAW_POINT * a,const EC_RAW_POINT * b)1134 void ec_point_select(const EC_GROUP *group, EC_RAW_POINT *out, BN_ULONG mask,
1135 const EC_RAW_POINT *a, const EC_RAW_POINT *b) {
1136 ec_felem_select(group, &out->X, mask, &a->X, &b->X);
1137 ec_felem_select(group, &out->Y, mask, &a->Y, &b->Y);
1138 ec_felem_select(group, &out->Z, mask, &a->Z, &b->Z);
1139 }
1140
ec_affine_select(const EC_GROUP * group,EC_AFFINE * out,BN_ULONG mask,const EC_AFFINE * a,const EC_AFFINE * b)1141 void ec_affine_select(const EC_GROUP *group, EC_AFFINE *out, BN_ULONG mask,
1142 const EC_AFFINE *a, const EC_AFFINE *b) {
1143 ec_felem_select(group, &out->X, mask, &a->X, &b->X);
1144 ec_felem_select(group, &out->Y, mask, &a->Y, &b->Y);
1145 }
1146
ec_precomp_select(const EC_GROUP * group,EC_PRECOMP * out,BN_ULONG mask,const EC_PRECOMP * a,const EC_PRECOMP * b)1147 void ec_precomp_select(const EC_GROUP *group, EC_PRECOMP *out, BN_ULONG mask,
1148 const EC_PRECOMP *a, const EC_PRECOMP *b) {
1149 OPENSSL_STATIC_ASSERT(sizeof(out->comb) == sizeof(*out),
1150 "out->comb does not span the entire structure");
1151 for (size_t i = 0; i < OPENSSL_ARRAY_SIZE(out->comb); i++) {
1152 ec_affine_select(group, &out->comb[i], mask, &a->comb[i], &b->comb[i]);
1153 }
1154 }
1155
ec_cmp_x_coordinate(const EC_GROUP * group,const EC_RAW_POINT * p,const EC_SCALAR * r)1156 int ec_cmp_x_coordinate(const EC_GROUP *group, const EC_RAW_POINT *p,
1157 const EC_SCALAR *r) {
1158 return group->meth->cmp_x_coordinate(group, p, r);
1159 }
1160
ec_get_x_coordinate_as_scalar(const EC_GROUP * group,EC_SCALAR * out,const EC_RAW_POINT * p)1161 int ec_get_x_coordinate_as_scalar(const EC_GROUP *group, EC_SCALAR *out,
1162 const EC_RAW_POINT *p) {
1163 uint8_t bytes[EC_MAX_BYTES];
1164 size_t len;
1165 if (!ec_get_x_coordinate_as_bytes(group, bytes, &len, sizeof(bytes), p)) {
1166 return 0;
1167 }
1168
1169 // For simplicity, in case of width mismatches between |group->field| and
1170 // |group->order|, zero any untouched words in |out|.
1171 OPENSSL_memset(out, 0, sizeof(EC_SCALAR));
1172 for (size_t i = 0; i < len; i++) {
1173 out->bytes[len - i - 1] = bytes[i];
1174 }
1175
1176 // We must have p < 2×order, assuming p is not tiny (p >= 17). Thus rather we
1177 // can reduce by performing at most one subtraction.
1178 //
1179 // Proof: We only work with prime order curves, so the number of points on
1180 // the curve is the order. Thus Hasse's theorem gives:
1181 //
1182 // |order - (p + 1)| <= 2×sqrt(p)
1183 // p + 1 - order <= 2×sqrt(p)
1184 // p + 1 - 2×sqrt(p) <= order
1185 // p + 1 - 2×(p/4) < order (p/4 > sqrt(p) for p >= 17)
1186 // p/2 < p/2 + 1 < order
1187 // p < 2×order
1188 //
1189 // Additionally, one can manually check this property for built-in curves. It
1190 // is enforced for legacy custom curves in |EC_GROUP_set_generator|.
1191
1192 // The above does not guarantee |group->field| is not one word larger than
1193 // |group->order|, so read one extra carry word.
1194 BN_ULONG tmp[EC_MAX_WORDS];
1195 BN_ULONG carry =
1196 group->order.width < EC_MAX_WORDS ? out->words[group->order.width] : 0;
1197 bn_reduce_once_in_place(out->words, carry, group->order.d, tmp,
1198 group->order.width);
1199 return 1;
1200 }
1201
ec_get_x_coordinate_as_bytes(const EC_GROUP * group,uint8_t * out,size_t * out_len,size_t max_out,const EC_RAW_POINT * p)1202 int ec_get_x_coordinate_as_bytes(const EC_GROUP *group, uint8_t *out,
1203 size_t *out_len, size_t max_out,
1204 const EC_RAW_POINT *p) {
1205 size_t len = BN_num_bytes(&group->field);
1206 assert(len <= EC_MAX_BYTES);
1207 if (max_out < len) {
1208 OPENSSL_PUT_ERROR(EC, EC_R_BUFFER_TOO_SMALL);
1209 return 0;
1210 }
1211
1212 EC_FELEM x;
1213 if (!group->meth->point_get_affine_coordinates(group, p, &x, NULL)) {
1214 return 0;
1215 }
1216
1217 ec_felem_to_bytes(group, out, out_len, &x);
1218 *out_len = len;
1219 return 1;
1220 }
1221
ec_set_to_safe_point(const EC_GROUP * group,EC_RAW_POINT * out)1222 void ec_set_to_safe_point(const EC_GROUP *group, EC_RAW_POINT *out) {
1223 if (group->generator != NULL) {
1224 ec_GFp_simple_point_copy(out, &group->generator->raw);
1225 } else {
1226 // The generator can be missing if the caller is in the process of
1227 // constructing an arbitrary group. In this case, we give up and use the
1228 // point at infinity.
1229 ec_GFp_simple_point_set_to_infinity(group, out);
1230 }
1231 }
1232
EC_GROUP_set_asn1_flag(EC_GROUP * group,int flag)1233 void EC_GROUP_set_asn1_flag(EC_GROUP *group, int flag) {}
1234
EC_GROUP_get_asn1_flag(const EC_GROUP * group)1235 int EC_GROUP_get_asn1_flag(const EC_GROUP *group) {
1236 return OPENSSL_EC_NAMED_CURVE;
1237 }
1238
EC_GROUP_method_of(const EC_GROUP * group)1239 const EC_METHOD *EC_GROUP_method_of(const EC_GROUP *group) {
1240 // This function exists purely to give callers a way to call
1241 // |EC_METHOD_get_field_type|. cryptography.io crashes if |EC_GROUP_method_of|
1242 // returns NULL, so return some other garbage pointer.
1243 return (const EC_METHOD *)0x12340000;
1244 }
1245
EC_METHOD_get_field_type(const EC_METHOD * meth)1246 int EC_METHOD_get_field_type(const EC_METHOD *meth) {
1247 return NID_X9_62_prime_field;
1248 }
1249
EC_GROUP_set_point_conversion_form(EC_GROUP * group,point_conversion_form_t form)1250 void EC_GROUP_set_point_conversion_form(EC_GROUP *group,
1251 point_conversion_form_t form) {
1252 if (form != POINT_CONVERSION_UNCOMPRESSED) {
1253 abort();
1254 }
1255 }
1256
EC_get_builtin_curves(EC_builtin_curve * out_curves,size_t max_num_curves)1257 size_t EC_get_builtin_curves(EC_builtin_curve *out_curves,
1258 size_t max_num_curves) {
1259 const struct built_in_curves *const curves = OPENSSL_built_in_curves();
1260
1261 for (size_t i = 0; i < max_num_curves && i < OPENSSL_NUM_BUILT_IN_CURVES;
1262 i++) {
1263 out_curves[i].comment = curves->curves[i].comment;
1264 out_curves[i].nid = curves->curves[i].nid;
1265 }
1266
1267 return OPENSSL_NUM_BUILT_IN_CURVES;
1268 }
1269