Debian Codegraph @

external/boringssl/crypto/ec/ec.c

raw
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 * [email protected].
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 * ([email protected]). This product includes software written by Tim
52 * Hudson ([email protected]).
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
81
82 static const struct curve_data P224 = {
83 "NIST P-224",
84 28,
85 1,
86 {/* p */
87 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF,
88 0xFF, 0xFF, 0xFF, 0xFF, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
89 0x00, 0x00, 0x00, 0x01,
90 /* a */
91 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF,
92 0xFF, 0xFF, 0xFF, 0xFE, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF,
93 0xFF, 0xFF, 0xFF, 0xFE,
94 /* b */
95 0xB4, 0x05, 0x0A, 0x85, 0x0C, 0x04, 0xB3, 0xAB, 0xF5, 0x41, 0x32, 0x56,
96 0x50, 0x44, 0xB0, 0xB7, 0xD7, 0xBF, 0xD8, 0xBA, 0x27, 0x0B, 0x39, 0x43,
97 0x23, 0x55, 0xFF, 0xB4,
98 /* x */
99 0xB7, 0x0E, 0x0C, 0xBD, 0x6B, 0xB4, 0xBF, 0x7F, 0x32, 0x13, 0x90, 0xB9,
100 0x4A, 0x03, 0xC1, 0xD3, 0x56, 0xC2, 0x11, 0x22, 0x34, 0x32, 0x80, 0xD6,
101 0x11, 0x5C, 0x1D, 0x21,
102 /* y */
103 0xbd, 0x37, 0x63, 0x88, 0xb5, 0xf7, 0x23, 0xfb, 0x4c, 0x22, 0xdf, 0xe6,
104 0xcd, 0x43, 0x75, 0xa0, 0x5a, 0x07, 0x47, 0x64, 0x44, 0xd5, 0x81, 0x99,
105 0x85, 0x00, 0x7e, 0x34,
106 /* order */
107 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF,
108 0xFF, 0xFF, 0x16, 0xA2, 0xE0, 0xB8, 0xF0, 0x3E, 0x13, 0xDD, 0x29, 0x45,
109 0x5C, 0x5C, 0x2A, 0x3D,
110 }};
111
112 static const struct curve_data P256 = {
113 "NIST P-256",
114 32,
115 1,
116 {/* p */
117 0xFF, 0xFF, 0xFF, 0xFF, 0x00, 0x00, 0x00, 0x01, 0x00, 0x00, 0x00, 0x00,
118 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0xFF, 0xFF, 0xFF, 0xFF,
119 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF,
120 /* a */
121 0xFF, 0xFF, 0xFF, 0xFF, 0x00, 0x00, 0x00, 0x01, 0x00, 0x00, 0x00, 0x00,
122 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0xFF, 0xFF, 0xFF, 0xFF,
123 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFC,
124 /* b */
125 0x5A, 0xC6, 0x35, 0xD8, 0xAA, 0x3A, 0x93, 0xE7, 0xB3, 0xEB, 0xBD, 0x55,
126 0x76, 0x98, 0x86, 0xBC, 0x65, 0x1D, 0x06, 0xB0, 0xCC, 0x53, 0xB0, 0xF6,
127 0x3B, 0xCE, 0x3C, 0x3E, 0x27, 0xD2, 0x60, 0x4B,
128 /* x */
129 0x6B, 0x17, 0xD1, 0xF2, 0xE1, 0x2C, 0x42, 0x47, 0xF8, 0xBC, 0xE6, 0xE5,
130 0x63, 0xA4, 0x40, 0xF2, 0x77, 0x03, 0x7D, 0x81, 0x2D, 0xEB, 0x33, 0xA0,
131 0xF4, 0xA1, 0x39, 0x45, 0xD8, 0x98, 0xC2, 0x96,
132 /* y */
133 0x4f, 0xe3, 0x42, 0xe2, 0xfe, 0x1a, 0x7f, 0x9b, 0x8e, 0xe7, 0xeb, 0x4a,
134 0x7c, 0x0f, 0x9e, 0x16, 0x2b, 0xce, 0x33, 0x57, 0x6b, 0x31, 0x5e, 0xce,
135 0xcb, 0xb6, 0x40, 0x68, 0x37, 0xbf, 0x51, 0xf5,
136 /* order */
137 0xFF, 0xFF, 0xFF, 0xFF, 0x00, 0x00, 0x00, 0x00, 0xFF, 0xFF, 0xFF, 0xFF,
138 0xFF, 0xFF, 0xFF, 0xFF, 0xBC, 0xE6, 0xFA, 0xAD, 0xA7, 0x17, 0x9E, 0x84,
139 0xF3, 0xB9, 0xCA, 0xC2, 0xFC, 0x63, 0x25, 0x51}};
140
141 static const struct curve_data P384 = {
142 "NIST P-384",
143 48,
144 1,
145 {/* p */
146 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF,
147 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF,
148 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFE, 0xFF, 0xFF, 0xFF, 0xFF,
149 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0xFF, 0xFF, 0xFF, 0xFF,
150 /* a */
151 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF,
152 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF,
153 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFE, 0xFF, 0xFF, 0xFF, 0xFF,
154 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0xFF, 0xFF, 0xFF, 0xFC,
155 /* b */
156 0xB3, 0x31, 0x2F, 0xA7, 0xE2, 0x3E, 0xE7, 0xE4, 0x98, 0x8E, 0x05, 0x6B,
157 0xE3, 0xF8, 0x2D, 0x19, 0x18, 0x1D, 0x9C, 0x6E, 0xFE, 0x81, 0x41, 0x12,
158 0x03, 0x14, 0x08, 0x8F, 0x50, 0x13, 0x87, 0x5A, 0xC6, 0x56, 0x39, 0x8D,
159 0x8A, 0x2E, 0xD1, 0x9D, 0x2A, 0x85, 0xC8, 0xED, 0xD3, 0xEC, 0x2A, 0xEF,
160 /* x */
161 0xAA, 0x87, 0xCA, 0x22, 0xBE, 0x8B, 0x05, 0x37, 0x8E, 0xB1, 0xC7, 0x1E,
162 0xF3, 0x20, 0xAD, 0x74, 0x6E, 0x1D, 0x3B, 0x62, 0x8B, 0xA7, 0x9B, 0x98,
163 0x59, 0xF7, 0x41, 0xE0, 0x82, 0x54, 0x2A, 0x38, 0x55, 0x02, 0xF2, 0x5D,
164 0xBF, 0x55, 0x29, 0x6C, 0x3A, 0x54, 0x5E, 0x38, 0x72, 0x76, 0x0A, 0xB7,
165 /* y */
166 0x36, 0x17, 0xde, 0x4a, 0x96, 0x26, 0x2c, 0x6f, 0x5d, 0x9e, 0x98, 0xbf,
167 0x92, 0x92, 0xdc, 0x29, 0xf8, 0xf4, 0x1d, 0xbd, 0x28, 0x9a, 0x14, 0x7c,
168 0xe9, 0xda, 0x31, 0x13, 0xb5, 0xf0, 0xb8, 0xc0, 0x0a, 0x60, 0xb1, 0xce,
169 0x1d, 0x7e, 0x81, 0x9d, 0x7a, 0x43, 0x1d, 0x7c, 0x90, 0xea, 0x0e, 0x5f,
170 /* order */
171 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF,
172 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF,
173 0xC7, 0x63, 0x4D, 0x81, 0xF4, 0x37, 0x2D, 0xDF, 0x58, 0x1A, 0x0D, 0xB2,
174 0x48, 0xB0, 0xA7, 0x7A, 0xEC, 0xEC, 0x19, 0x6A, 0xCC, 0xC5, 0x29, 0x73}};
175
176 static const struct curve_data P521 = {
177 "NIST P-521",
178 66,
179 1,
180 {/* p */
181 0x01, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF,
182 0xFF, 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,
187 /* a */
188 0x01, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF,
189 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF,
190 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF,
191 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF,
192 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF,
193 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFC,
194 /* b */
195 0x00, 0x51, 0x95, 0x3E, 0xB9, 0x61, 0x8E, 0x1C, 0x9A, 0x1F, 0x92, 0x9A,
196 0x21, 0xA0, 0xB6, 0x85, 0x40, 0xEE, 0xA2, 0xDA, 0x72, 0x5B, 0x99, 0xB3,
197 0x15, 0xF3, 0xB8, 0xB4, 0x89, 0x91, 0x8E, 0xF1, 0x09, 0xE1, 0x56, 0x19,
198 0x39, 0x51, 0xEC, 0x7E, 0x93, 0x7B, 0x16, 0x52, 0xC0, 0xBD, 0x3B, 0xB1,
199 0xBF, 0x07, 0x35, 0x73, 0xDF, 0x88, 0x3D, 0x2C, 0x34, 0xF1, 0xEF, 0x45,
200 0x1F, 0xD4, 0x6B, 0x50, 0x3F, 0x00,
201 /* x */
202 0x00, 0xC6, 0x85, 0x8E, 0x06, 0xB7, 0x04, 0x04, 0xE9, 0xCD, 0x9E, 0x3E,
203 0xCB, 0x66, 0x23, 0x95, 0xB4, 0x42, 0x9C, 0x64, 0x81, 0x39, 0x05, 0x3F,
204 0xB5, 0x21, 0xF8, 0x28, 0xAF, 0x60, 0x6B, 0x4D, 0x3D, 0xBA, 0xA1, 0x4B,
205 0x5E, 0x77, 0xEF, 0xE7, 0x59, 0x28, 0xFE, 0x1D, 0xC1, 0x27, 0xA2, 0xFF,
206 0xA8, 0xDE, 0x33, 0x48, 0xB3, 0xC1, 0x85, 0x6A, 0x42, 0x9B, 0xF9, 0x7E,
207 0x7E, 0x31, 0xC2, 0xE5, 0xBD, 0x66,
208 /* y */
209 0x01, 0x18, 0x39, 0x29, 0x6a, 0x78, 0x9a, 0x3b, 0xc0, 0x04, 0x5c, 0x8a,
210 0x5f, 0xb4, 0x2c, 0x7d, 0x1b, 0xd9, 0x98, 0xf5, 0x44, 0x49, 0x57, 0x9b,
211 0x44, 0x68, 0x17, 0xaf, 0xbd, 0x17, 0x27, 0x3e, 0x66, 0x2c, 0x97, 0xee,
212 0x72, 0x99, 0x5e, 0xf4, 0x26, 0x40, 0xc5, 0x50, 0xb9, 0x01, 0x3f, 0xad,
213 0x07, 0x61, 0x35, 0x3c, 0x70, 0x86, 0xa2, 0x72, 0xc2, 0x40, 0x88, 0xbe,
214 0x94, 0x76, 0x9f, 0xd1, 0x66, 0x50,
215 /* order */
216 0x01, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF,
217 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF,
218 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFA, 0x51, 0x86,
219 0x87, 0x83, 0xBF, 0x2F, 0x96, 0x6B, 0x7F, 0xCC, 0x01, 0x48, 0xF7, 0x09,
220 0xA5, 0xD0, 0x3B, 0xB5, 0xC9, 0xB8, 0x89, 0x9C, 0x47, 0xAE, 0xBB, 0x6F,
221 0xB7, 0x1E, 0x91, 0x38, 0x64, 0x09}};
222
223 /* MSan appears to have a bug that causes code to be miscompiled in opt mode.
224 * While that is being looked at, don't run the uint128_t code under MSan. */
225 #if defined(OPENSSL_64_BIT) && !defined(OPENSSL_WINDOWS) && \
226 !defined(MEMORY_SANITIZER) && __BYTE_ORDER__ != __ORDER_BIG_ENDIAN__
227 #define BORINGSSL_USE_INT128_CODE
228 #endif
229
230 const struct built_in_curve OPENSSL_built_in_curves[] = {
231 {
232 NID_secp521r1,
233 /* 1.3.132.0.35 */
234 {0x2b, 0x81, 0x04, 0x00, 0x23}, 5,
235 &P521,
236 NULL,
237 },
238 {
239 NID_secp384r1,
240 /* 1.3.132.0.34 */
241 {0x2b, 0x81, 0x04, 0x00, 0x22}, 5,
242 &P384,
243 NULL,
244 },
245 {
246 NID_X9_62_prime256v1,
247 /* 1.2.840.10045.3.1.7 */
248 {0x2a, 0x86, 0x48, 0xce, 0x3d, 0x03, 0x01, 0x07}, 8,
249 &P256,
250 #if defined(BORINGSSL_USE_INT128_CODE)
251 #if !defined(OPENSSL_NO_ASM) && defined(OPENSSL_X86_64) && \
252 !defined(OPENSSL_SMALL)
253 EC_GFp_nistz256_method,
254 #else
255 EC_GFp_nistp256_method,
256 #endif
257 #else
258 NULL,
259 #endif
260 },
261 {
262 NID_secp224r1,
263 /* 1.3.132.0.33 */
264 {0x2b, 0x81, 0x04, 0x00, 0x21}, 5,
265 &P224,
266 #if defined(BORINGSSL_USE_INT128_CODE) && !defined(OPENSSL_SMALL)
267 EC_GFp_nistp224_method,
268 #else
269 NULL,
270 #endif
271 },
272 {NID_undef, {0}, 0, NULL, NULL},
273 };
274
275 /* built_in_curve_scalar_field_monts contains Montgomery contexts for
276 * performing inversions in the scalar fields of each of the built-in
277 * curves. It's protected by |built_in_curve_scalar_field_monts_once|. */
278 static const BN_MONT_CTX **built_in_curve_scalar_field_monts;
279
280 static CRYPTO_once_t built_in_curve_scalar_field_monts_once;
281
282 static void built_in_curve_scalar_field_monts_init(void) {
283 unsigned num_built_in_curves;
284 for (num_built_in_curves = 0;; num_built_in_curves++) {
285 if (OPENSSL_built_in_curves[num_built_in_curves].nid == NID_undef) {
286 break;
287 }
288 }
289
290 assert(0 < num_built_in_curves);
291
292 built_in_curve_scalar_field_monts =
293 OPENSSL_malloc(sizeof(BN_MONT_CTX *) * num_built_in_curves);
294 if (built_in_curve_scalar_field_monts == NULL) {
295 return;
296 }
297
298 BIGNUM *order = BN_new();
299 BN_CTX *bn_ctx = BN_CTX_new();
300 BN_MONT_CTX *mont_ctx = NULL;
301
302 if (bn_ctx == NULL ||
303 order == NULL) {
304 goto err;
305 }
306
307 unsigned i;
308 for (i = 0; i < num_built_in_curves; i++) {
309 const struct curve_data *curve = OPENSSL_built_in_curves[i].data;
310 const unsigned param_len = curve->param_len;
311 const uint8_t *params = curve->data;
312
313 mont_ctx = BN_MONT_CTX_new();
314 if (mont_ctx == NULL) {
315 goto err;
316 }
317
318 if (!BN_bin2bn(params + 5 * param_len, param_len, order) ||
319 !BN_MONT_CTX_set(mont_ctx, order, bn_ctx)) {
320 goto err;
321 }
322
323 built_in_curve_scalar_field_monts[i] = mont_ctx;
324 mont_ctx = NULL;
325 }
326
327 goto out;
328
329 err:
330 BN_MONT_CTX_free(mont_ctx);
331 OPENSSL_free((BN_MONT_CTX**) built_in_curve_scalar_field_monts);
332 built_in_curve_scalar_field_monts = NULL;
333
334 out:
335 BN_free(order);
336 BN_CTX_free(bn_ctx);
337 }
338
339 EC_GROUP *ec_group_new(const EC_METHOD *meth) {
340 EC_GROUP *ret;
341
342 if (meth == NULL) {
343 OPENSSL_PUT_ERROR(EC, EC_R_SLOT_FULL);
344 return NULL;
345 }
346
347 if (meth->group_init == 0) {
348 OPENSSL_PUT_ERROR(EC, ERR_R_SHOULD_NOT_HAVE_BEEN_CALLED);
349 return NULL;
350 }
351
352 ret = OPENSSL_malloc(sizeof(EC_GROUP));
353 if (ret == NULL) {
354 OPENSSL_PUT_ERROR(EC, ERR_R_MALLOC_FAILURE);
355 return NULL;
356 }
357 memset(ret, 0, sizeof(EC_GROUP));
358
359 ret->meth = meth;
360 BN_init(&ret->order);
361 BN_init(&ret->cofactor);
362
363 if (!meth->group_init(ret)) {
364 OPENSSL_free(ret);
365 return NULL;
366 }
367
368 return ret;
369 }
370
371 EC_GROUP *EC_GROUP_new_curve_GFp(const BIGNUM *p, const BIGNUM *a,
372 const BIGNUM *b, BN_CTX *ctx) {
373 const EC_METHOD *meth = EC_GFp_mont_method();
374 EC_GROUP *ret;
375
376 ret = ec_group_new(meth);
377 if (ret == NULL) {
378 return NULL;
379 }
380
381 if (ret->meth->group_set_curve == 0) {
382 OPENSSL_PUT_ERROR(EC, ERR_R_SHOULD_NOT_HAVE_BEEN_CALLED);
383 return 0;
384 }
385 if (!ret->meth->group_set_curve(ret, p, a, b, ctx)) {
386 EC_GROUP_free(ret);
387 return NULL;
388 }
389 return ret;
390 }
391
392 int EC_GROUP_set_generator(EC_GROUP *group, const EC_POINT *generator,
393 const BIGNUM *order, const BIGNUM *cofactor) {
394 if (group->curve_name != NID_undef || group->generator != NULL) {
395 /* |EC_GROUP_set_generator| may only be used with |EC_GROUP|s returned by
396 * |EC_GROUP_new_curve_GFp| and may only used once on each group. */
397 return 0;
398 }
399
400 group->generator = EC_POINT_new(group);
401 return group->generator != NULL &&
402 EC_POINT_copy(group->generator, generator) &&
403 BN_copy(&group->order, order) &&
404 BN_copy(&group->cofactor, cofactor);
405 }
406
407 EC_GROUP *EC_GROUP_new_arbitrary(const BIGNUM *p, const BIGNUM *a,
408 const BIGNUM *b, const BIGNUM *gx,
409 const BIGNUM *gy, const BIGNUM *order,
410 const BIGNUM *cofactor) {
411 BN_CTX *ctx = BN_CTX_new();
412 if (ctx == NULL) {
413 return NULL;
414 }
415
416 EC_POINT *generator = NULL;
417 EC_GROUP *ret = EC_GROUP_new_curve_GFp(p, a, b, ctx);
418 if (ret == NULL) {
419 goto err;
420 }
421
422 generator = EC_POINT_new(ret);
423 if (generator == NULL ||
424 !EC_POINT_set_affine_coordinates_GFp(ret, generator, gx, gy, ctx) ||
425 !EC_GROUP_set_generator(ret, generator, order, cofactor)) {
426 goto err;
427 }
428
429 EC_POINT_free(generator);
430 BN_CTX_free(ctx);
431 return ret;
432
433 err:
434 EC_POINT_free(generator);
435 EC_GROUP_free(ret);
436 BN_CTX_free(ctx);
437 return NULL;
438 }
439
440 static EC_GROUP *ec_group_new_from_data(unsigned built_in_index) {
441 const struct built_in_curve *curve = &OPENSSL_built_in_curves[built_in_index];
442 EC_GROUP *group = NULL;
443 EC_POINT *P = NULL;
444 BIGNUM *p = NULL, *a = NULL, *b = NULL, *x = NULL, *y = NULL;
445 const EC_METHOD *meth;
446 int ok = 0;
447
448 BN_CTX *ctx = BN_CTX_new();
449 if (ctx == NULL) {
450 OPENSSL_PUT_ERROR(EC, ERR_R_MALLOC_FAILURE);
451 goto err;
452 }
453
454 const struct curve_data *data = curve->data;
455 const unsigned param_len = data->param_len;
456 const uint8_t *params = data->data;
457
458 if (!(p = BN_bin2bn(params + 0 * param_len, param_len, NULL)) ||
459 !(a = BN_bin2bn(params + 1 * param_len, param_len, NULL)) ||
460 !(b = BN_bin2bn(params + 2 * param_len, param_len, NULL))) {
461 OPENSSL_PUT_ERROR(EC, ERR_R_BN_LIB);
462 goto err;
463 }
464
465 if (curve->method != 0) {
466 meth = curve->method();
467 if (((group = ec_group_new(meth)) == NULL) ||
468 (!(group->meth->group_set_curve(group, p, a, b, ctx)))) {
469 OPENSSL_PUT_ERROR(EC, ERR_R_EC_LIB);
470 goto err;
471 }
472 } else {
473 if ((group = EC_GROUP_new_curve_GFp(p, a, b, ctx)) == NULL) {
474 OPENSSL_PUT_ERROR(EC, ERR_R_EC_LIB);
475 goto err;
476 }
477 }
478
479 if ((P = EC_POINT_new(group)) == NULL) {
480 OPENSSL_PUT_ERROR(EC, ERR_R_EC_LIB);
481 goto err;
482 }
483
484 if (!(x = BN_bin2bn(params + 3 * param_len, param_len, NULL)) ||
485 !(y = BN_bin2bn(params + 4 * param_len, param_len, NULL))) {
486 OPENSSL_PUT_ERROR(EC, ERR_R_BN_LIB);
487 goto err;
488 }
489
490 if (!EC_POINT_set_affine_coordinates_GFp(group, P, x, y, ctx)) {
491 OPENSSL_PUT_ERROR(EC, ERR_R_EC_LIB);
492 goto err;
493 }
494 if (!BN_bin2bn(params + 5 * param_len, param_len, &group->order) ||
495 !BN_set_word(&group->cofactor, (BN_ULONG)data->cofactor)) {
496 OPENSSL_PUT_ERROR(EC, ERR_R_BN_LIB);
497 goto err;
498 }
499
500 CRYPTO_once(&built_in_curve_scalar_field_monts_once,
501 built_in_curve_scalar_field_monts_init);
502 if (built_in_curve_scalar_field_monts != NULL) {
503 group->mont_data = built_in_curve_scalar_field_monts[built_in_index];
504 }
505
506 group->generator = P;
507 P = NULL;
508 ok = 1;
509
510 err:
511 if (!ok) {
512 EC_GROUP_free(group);
513 group = NULL;
514 }
515 EC_POINT_free(P);
516 BN_CTX_free(ctx);
517 BN_free(p);
518 BN_free(a);
519 BN_free(b);
520 BN_free(x);
521 BN_free(y);
522 return group;
523 }
524
525 EC_GROUP *EC_GROUP_new_by_curve_name(int nid) {
526 unsigned i;
527 const struct built_in_curve *curve;
528 EC_GROUP *ret = NULL;
529
530 for (i = 0; OPENSSL_built_in_curves[i].nid != NID_undef; i++) {
531 curve = &OPENSSL_built_in_curves[i];
532 if (curve->nid == nid) {
533 ret = ec_group_new_from_data(i);
534 break;
535 }
536 }
537
538 if (ret == NULL) {
539 OPENSSL_PUT_ERROR(EC, EC_R_UNKNOWN_GROUP);
540 return NULL;
541 }
542
543 ret->curve_name = nid;
544 return ret;
545 }
546
547 void EC_GROUP_free(EC_GROUP *group) {
548 if (!group) {
549 return;
550 }
551
552 if (group->meth->group_finish != 0) {
553 group->meth->group_finish(group);
554 }
555
556 EC_POINT_free(group->generator);
557 BN_free(&group->order);
558 BN_free(&group->cofactor);
559
560 OPENSSL_free(group);
561 }
562
563 int ec_group_copy(EC_GROUP *dest, const EC_GROUP *src) {
564 if (dest->meth->group_copy == 0) {
565 OPENSSL_PUT_ERROR(EC, ERR_R_SHOULD_NOT_HAVE_BEEN_CALLED);
566 return 0;
567 }
568 if (dest->meth != src->meth) {
569 OPENSSL_PUT_ERROR(EC, EC_R_INCOMPATIBLE_OBJECTS);
570 return 0;
571 }
572 if (dest == src) {
573 return 1;
574 }
575
576 dest->mont_data = src->mont_data;
577
578 if (src->generator != NULL) {
579 if (dest->generator == NULL) {
580 dest->generator = EC_POINT_new(dest);
581 if (dest->generator == NULL) {
582 return 0;
583 }
584 }
585 if (!EC_POINT_copy(dest->generator, src->generator)) {
586 return 0;
587 }
588 } else {
589 EC_POINT_clear_free(dest->generator);
590 dest->generator = NULL;
591 }
592
593 if (!BN_copy(&dest->order, &src->order) ||
594 !BN_copy(&dest->cofactor, &src->cofactor)) {
595 return 0;
596 }
597
598 dest->curve_name = src->curve_name;
599
600 return dest->meth->group_copy(dest, src);
601 }
602
603 const BN_MONT_CTX *ec_group_get_mont_data(const EC_GROUP *group) {
604 return group->mont_data;
605 }
606
607 EC_GROUP *EC_GROUP_dup(const EC_GROUP *a) {
608 EC_GROUP *t = NULL;
609 int ok = 0;
610
611 if (a == NULL) {
612 return NULL;
613 }
614
615 t = ec_group_new(a->meth);
616 if (t == NULL) {
617 return NULL;
618 }
619 if (!ec_group_copy(t, a)) {
620 goto err;
621 }
622
623 ok = 1;
624
625 err:
626 if (!ok) {
627 EC_GROUP_free(t);
628 return NULL;
629 } else {
630 return t;
631 }
632 }
633
634 int EC_GROUP_cmp(const EC_GROUP *a, const EC_GROUP *b, BN_CTX *ignored) {
635 return a->curve_name == NID_undef ||
636 b->curve_name == NID_undef ||
637 a->curve_name != b->curve_name;
638 }
639
640 const EC_POINT *EC_GROUP_get0_generator(const EC_GROUP *group) {
641 return group->generator;
642 }
643
644 const BIGNUM *EC_GROUP_get0_order(const EC_GROUP *group) {
645 assert(!BN_is_zero(&group->order));
646 return &group->order;
647 }
648
649 int EC_GROUP_get_order(const EC_GROUP *group, BIGNUM *order, BN_CTX *ctx) {
650 if (BN_copy(order, EC_GROUP_get0_order(group)) == NULL) {
651 return 0;
652 }
653 return 1;
654 }
655
656 int EC_GROUP_get_cofactor(const EC_GROUP *group, BIGNUM *cofactor,
657 BN_CTX *ctx) {
658 if (!BN_copy(cofactor, &group->cofactor)) {
659 return 0;
660 }
661
662 return !BN_is_zero(&group->cofactor);
663 }
664
665 int EC_GROUP_get_curve_GFp(const EC_GROUP *group, BIGNUM *out_p, BIGNUM *out_a,
666 BIGNUM *out_b, BN_CTX *ctx) {
667 return ec_GFp_simple_group_get_curve(group, out_p, out_a, out_b, ctx);
668 }
669
670 int EC_GROUP_get_curve_name(const EC_GROUP *group) { return group->curve_name; }
671
672 unsigned EC_GROUP_get_degree(const EC_GROUP *group) {
673 return ec_GFp_simple_group_get_degree(group);
674 }
675
676 EC_POINT *EC_POINT_new(const EC_GROUP *group) {
677 EC_POINT *ret;
678
679 if (group == NULL) {
680 OPENSSL_PUT_ERROR(EC, ERR_R_PASSED_NULL_PARAMETER);
681 return NULL;
682 }
683
684 ret = OPENSSL_malloc(sizeof *ret);
685 if (ret == NULL) {
686 OPENSSL_PUT_ERROR(EC, ERR_R_MALLOC_FAILURE);
687 return NULL;
688 }
689
690 ret->meth = group->meth;
691
692 if (!ec_GFp_simple_point_init(ret)) {
693 OPENSSL_free(ret);
694 return NULL;
695 }
696
697 return ret;
698 }
699
700 void EC_POINT_free(EC_POINT *point) {
701 if (!point) {
702 return;
703 }
704
705 ec_GFp_simple_point_finish(point);
706
707 OPENSSL_free(point);
708 }
709
710 void EC_POINT_clear_free(EC_POINT *point) {
711 if (!point) {
712 return;
713 }
714
715 ec_GFp_simple_point_clear_finish(point);
716
717 OPENSSL_cleanse(point, sizeof *point);
718 OPENSSL_free(point);
719 }
720
721 int EC_POINT_copy(EC_POINT *dest, const EC_POINT *src) {
722 if (dest->meth != src->meth) {
723 OPENSSL_PUT_ERROR(EC, EC_R_INCOMPATIBLE_OBJECTS);
724 return 0;
725 }
726 if (dest == src) {
727 return 1;
728 }
729 return ec_GFp_simple_point_copy(dest, src);
730 }
731
732 EC_POINT *EC_POINT_dup(const EC_POINT *a, const EC_GROUP *group) {
733 EC_POINT *t;
734 int r;
735
736 if (a == NULL) {
737 return NULL;
738 }
739
740 t = EC_POINT_new(group);
741 if (t == NULL) {
742 OPENSSL_PUT_ERROR(EC, ERR_R_MALLOC_FAILURE);
743 return NULL;
744 }
745 r = EC_POINT_copy(t, a);
746 if (!r) {
747 EC_POINT_free(t);
748 return NULL;
749 } else {
750 return t;
751 }
752 }
753
754 int EC_POINT_set_to_infinity(const EC_GROUP *group, EC_POINT *point) {
755 if (group->meth != point->meth) {
756 OPENSSL_PUT_ERROR(EC, EC_R_INCOMPATIBLE_OBJECTS);
757 return 0;
758 }
759 return ec_GFp_simple_point_set_to_infinity(group, point);
760 }
761
762 int EC_POINT_is_at_infinity(const EC_GROUP *group, const EC_POINT *point) {
763 if (group->meth != point->meth) {
764 OPENSSL_PUT_ERROR(EC, EC_R_INCOMPATIBLE_OBJECTS);
765 return 0;
766 }
767 return ec_GFp_simple_is_at_infinity(group, point);
768 }
769
770 int EC_POINT_is_on_curve(const EC_GROUP *group, const EC_POINT *point,
771 BN_CTX *ctx) {
772 if (group->meth != point->meth) {
773 OPENSSL_PUT_ERROR(EC, EC_R_INCOMPATIBLE_OBJECTS);
774 return 0;
775 }
776 return ec_GFp_simple_is_on_curve(group, point, ctx);
777 }
778
779 int EC_POINT_cmp(const EC_GROUP *group, const EC_POINT *a, const EC_POINT *b,
780 BN_CTX *ctx) {
781 if ((group->meth != a->meth) || (a->meth != b->meth)) {
782 OPENSSL_PUT_ERROR(EC, EC_R_INCOMPATIBLE_OBJECTS);
783 return -1;
784 }
785 return ec_GFp_simple_cmp(group, a, b, ctx);
786 }
787
788 int EC_POINT_make_affine(const EC_GROUP *group, EC_POINT *point, BN_CTX *ctx) {
789 if (group->meth != point->meth) {
790 OPENSSL_PUT_ERROR(EC, EC_R_INCOMPATIBLE_OBJECTS);
791 return 0;
792 }
793 return ec_GFp_simple_make_affine(group, point, ctx);
794 }
795
796 int EC_POINTs_make_affine(const EC_GROUP *group, size_t num, EC_POINT *points[],
797 BN_CTX *ctx) {
798 size_t i;
799
800 for (i = 0; i < num; i++) {
801 if (group->meth != points[i]->meth) {
802 OPENSSL_PUT_ERROR(EC, EC_R_INCOMPATIBLE_OBJECTS);
803 return 0;
804 }
805 }
806 return ec_GFp_simple_points_make_affine(group, num, points, ctx);
807 }
808
809 int EC_POINT_get_affine_coordinates_GFp(const EC_GROUP *group,
810 const EC_POINT *point, BIGNUM *x,
811 BIGNUM *y, BN_CTX *ctx) {
812 if (group->meth->point_get_affine_coordinates == 0) {
813 OPENSSL_PUT_ERROR(EC, ERR_R_SHOULD_NOT_HAVE_BEEN_CALLED);
814 return 0;
815 }
816 if (group->meth != point->meth) {
817 OPENSSL_PUT_ERROR(EC, EC_R_INCOMPATIBLE_OBJECTS);
818 return 0;
819 }
820 return group->meth->point_get_affine_coordinates(group, point, x, y, ctx);
821 }
822
823 int EC_POINT_set_affine_coordinates_GFp(const EC_GROUP *group, EC_POINT *point,
824 const BIGNUM *x, const BIGNUM *y,
825 BN_CTX *ctx) {
826 if (group->meth != point->meth) {
827 OPENSSL_PUT_ERROR(EC, EC_R_INCOMPATIBLE_OBJECTS);
828 return 0;
829 }
830 if (!ec_GFp_simple_point_set_affine_coordinates(group, point, x, y, ctx)) {
831 return 0;
832 }
833
834 if (!EC_POINT_is_on_curve(group, point, ctx)) {
835 OPENSSL_PUT_ERROR(EC, EC_R_POINT_IS_NOT_ON_CURVE);
836 return 0;
837 }
838
839 return 1;
840 }
841
842 int EC_POINT_add(const EC_GROUP *group, EC_POINT *r, const EC_POINT *a,
843 const EC_POINT *b, BN_CTX *ctx) {
844 if ((group->meth != r->meth) || (r->meth != a->meth) ||
845 (a->meth != b->meth)) {
846 OPENSSL_PUT_ERROR(EC, EC_R_INCOMPATIBLE_OBJECTS);
847 return 0;
848 }
849 return ec_GFp_simple_add(group, r, a, b, ctx);
850 }
851
852
853 int EC_POINT_dbl(const EC_GROUP *group, EC_POINT *r, const EC_POINT *a,
854 BN_CTX *ctx) {
855 if ((group->meth != r->meth) || (r->meth != a->meth)) {
856 OPENSSL_PUT_ERROR(EC, EC_R_INCOMPATIBLE_OBJECTS);
857 return 0;
858 }
859 return ec_GFp_simple_dbl(group, r, a, ctx);
860 }
861
862
863 int EC_POINT_invert(const EC_GROUP *group, EC_POINT *a, BN_CTX *ctx) {
864 if (group->meth != a->meth) {
865 OPENSSL_PUT_ERROR(EC, EC_R_INCOMPATIBLE_OBJECTS);
866 return 0;
867 }
868 return ec_GFp_simple_invert(group, a, ctx);
869 }
870
871 int EC_POINT_mul(const EC_GROUP *group, EC_POINT *r, const BIGNUM *g_scalar,
872 const EC_POINT *p, const BIGNUM *p_scalar, BN_CTX *ctx) {
873 /* Previously, this function set |r| to the point at infinity if there was
874 * nothing to multiply. But, nobody should be calling this function with
875 * nothing to multiply in the first place. */
876 if ((g_scalar == NULL && p_scalar == NULL) ||
877 ((p == NULL) != (p_scalar == NULL))) {
878 OPENSSL_PUT_ERROR(EC, ERR_R_PASSED_NULL_PARAMETER);
879 return 0;
880 }
881
882 if (group->meth != r->meth ||
883 (p != NULL && group->meth != p->meth)) {
884 OPENSSL_PUT_ERROR(EC, EC_R_INCOMPATIBLE_OBJECTS);
885 return 0;
886 }
887
888 return group->meth->mul(group, r, g_scalar, p, p_scalar, ctx);
889 }
890
891 int ec_point_set_Jprojective_coordinates_GFp(const EC_GROUP *group, EC_POINT *point,
892 const BIGNUM *x, const BIGNUM *y,
893 const BIGNUM *z, BN_CTX *ctx) {
894 if (group->meth != point->meth) {
895 OPENSSL_PUT_ERROR(EC, EC_R_INCOMPATIBLE_OBJECTS);
896 return 0;
897 }
898 return ec_GFp_simple_set_Jprojective_coordinates_GFp(group, point, x, y, z,
899 ctx);
900 }
901
902 void EC_GROUP_set_asn1_flag(EC_GROUP *group, int flag) {}
903
904 const EC_METHOD *EC_GROUP_method_of(const EC_GROUP *group) {
905 return NULL;
906 }
907
908 int EC_METHOD_get_field_type(const EC_METHOD *meth) {
909 return NID_X9_62_prime_field;
910 }
911
912 void EC_GROUP_set_point_conversion_form(EC_GROUP *group,
913 point_conversion_form_t form) {
914 if (form != POINT_CONVERSION_UNCOMPRESSED) {
915 abort();
916 }
917 }
918
919 size_t EC_get_builtin_curves(EC_builtin_curve *out_curves,
920 size_t max_num_curves) {
921 unsigned num_built_in_curves;
922 for (num_built_in_curves = 0;; num_built_in_curves++) {
923 if (OPENSSL_built_in_curves[num_built_in_curves].nid == NID_undef) {
924 break;
925 }
926 }
927
928 unsigned i;
929 for (i = 0; i < max_num_curves && i < num_built_in_curves; i++) {
930 out_curves[i].comment = OPENSSL_built_in_curves[i].data->comment;
931 out_curves[i].nid = OPENSSL_built_in_curves[i].nid;
932 }
933
934 return num_built_in_curves;
935 }