/src/boringssl/crypto/fipsmodule/ec/oct.c.inc
Line | Count | Source (jump to first uncovered line) |
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 <openssl/bn.h> |
71 | | #include <openssl/err.h> |
72 | | |
73 | | #include "internal.h" |
74 | | |
75 | | |
76 | 0 | size_t ec_point_byte_len(const EC_GROUP *group, point_conversion_form_t form) { |
77 | 0 | if (form != POINT_CONVERSION_COMPRESSED && |
78 | 0 | form != POINT_CONVERSION_UNCOMPRESSED) { |
79 | 0 | OPENSSL_PUT_ERROR(EC, EC_R_INVALID_FORM); |
80 | 0 | return 0; |
81 | 0 | } |
82 | | |
83 | 0 | const size_t field_len = BN_num_bytes(&group->field.N); |
84 | 0 | size_t output_len = 1 /* type byte */ + field_len; |
85 | 0 | if (form == POINT_CONVERSION_UNCOMPRESSED) { |
86 | | // Uncompressed points have a second coordinate. |
87 | 0 | output_len += field_len; |
88 | 0 | } |
89 | 0 | return output_len; |
90 | 0 | } |
91 | | |
92 | | size_t ec_point_to_bytes(const EC_GROUP *group, const EC_AFFINE *point, |
93 | | point_conversion_form_t form, uint8_t *buf, |
94 | 0 | size_t max_out) { |
95 | 0 | size_t output_len = ec_point_byte_len(group, form); |
96 | 0 | if (max_out < output_len) { |
97 | 0 | OPENSSL_PUT_ERROR(EC, EC_R_BUFFER_TOO_SMALL); |
98 | 0 | return 0; |
99 | 0 | } |
100 | | |
101 | 0 | size_t field_len; |
102 | 0 | ec_felem_to_bytes(group, buf + 1, &field_len, &point->X); |
103 | 0 | assert(field_len == BN_num_bytes(&group->field.N)); |
104 | | |
105 | 0 | if (form == POINT_CONVERSION_UNCOMPRESSED) { |
106 | 0 | ec_felem_to_bytes(group, buf + 1 + field_len, &field_len, &point->Y); |
107 | 0 | assert(field_len == BN_num_bytes(&group->field.N)); |
108 | 0 | buf[0] = form; |
109 | 0 | } else { |
110 | 0 | uint8_t y_buf[EC_MAX_BYTES]; |
111 | 0 | ec_felem_to_bytes(group, y_buf, &field_len, &point->Y); |
112 | 0 | buf[0] = form + (y_buf[field_len - 1] & 1); |
113 | 0 | } |
114 | | |
115 | 0 | return output_len; |
116 | 0 | } |
117 | | |
118 | | int ec_point_from_uncompressed(const EC_GROUP *group, EC_AFFINE *out, |
119 | 0 | const uint8_t *in, size_t len) { |
120 | 0 | const size_t field_len = BN_num_bytes(&group->field.N); |
121 | 0 | if (len != 1 + 2 * field_len || in[0] != POINT_CONVERSION_UNCOMPRESSED) { |
122 | 0 | OPENSSL_PUT_ERROR(EC, EC_R_INVALID_ENCODING); |
123 | 0 | return 0; |
124 | 0 | } |
125 | | |
126 | 0 | EC_FELEM x, y; |
127 | 0 | if (!ec_felem_from_bytes(group, &x, in + 1, field_len) || |
128 | 0 | !ec_felem_from_bytes(group, &y, in + 1 + field_len, field_len) || |
129 | 0 | !ec_point_set_affine_coordinates(group, out, &x, &y)) { |
130 | 0 | return 0; |
131 | 0 | } |
132 | | |
133 | 0 | return 1; |
134 | 0 | } |
135 | | |
136 | | static int ec_GFp_simple_oct2point(const EC_GROUP *group, EC_POINT *point, |
137 | | const uint8_t *buf, size_t len, |
138 | 0 | BN_CTX *ctx) { |
139 | 0 | if (len == 0) { |
140 | 0 | OPENSSL_PUT_ERROR(EC, EC_R_BUFFER_TOO_SMALL); |
141 | 0 | return 0; |
142 | 0 | } |
143 | | |
144 | 0 | point_conversion_form_t form = buf[0]; |
145 | 0 | if (form == POINT_CONVERSION_UNCOMPRESSED) { |
146 | 0 | EC_AFFINE affine; |
147 | 0 | if (!ec_point_from_uncompressed(group, &affine, buf, len)) { |
148 | | // In the event of an error, defend against the caller not checking the |
149 | | // return value by setting a known safe value. |
150 | 0 | ec_set_to_safe_point(group, &point->raw); |
151 | 0 | return 0; |
152 | 0 | } |
153 | 0 | ec_affine_to_jacobian(group, &point->raw, &affine); |
154 | 0 | return 1; |
155 | 0 | } |
156 | | |
157 | 0 | const int y_bit = form & 1; |
158 | 0 | const size_t field_len = BN_num_bytes(&group->field.N); |
159 | 0 | form = form & ~1u; |
160 | 0 | if (form != POINT_CONVERSION_COMPRESSED || |
161 | 0 | len != 1 /* type byte */ + field_len) { |
162 | 0 | OPENSSL_PUT_ERROR(EC, EC_R_INVALID_ENCODING); |
163 | 0 | return 0; |
164 | 0 | } |
165 | | |
166 | | // TODO(davidben): Integrate compressed coordinates with the lower-level EC |
167 | | // abstractions. This requires a way to compute square roots, which is tricky |
168 | | // for primes which are not 3 (mod 4), namely P-224 and custom curves. P-224's |
169 | | // prime is particularly inconvenient for compressed coordinates. See |
170 | | // https://cr.yp.to/papers/sqroot.pdf |
171 | 0 | BN_CTX *new_ctx = NULL; |
172 | 0 | if (ctx == NULL) { |
173 | 0 | ctx = new_ctx = BN_CTX_new(); |
174 | 0 | if (ctx == NULL) { |
175 | 0 | return 0; |
176 | 0 | } |
177 | 0 | } |
178 | | |
179 | 0 | int ret = 0; |
180 | 0 | BN_CTX_start(ctx); |
181 | 0 | BIGNUM *x = BN_CTX_get(ctx); |
182 | 0 | if (x == NULL || !BN_bin2bn(buf + 1, field_len, x)) { |
183 | 0 | goto err; |
184 | 0 | } |
185 | 0 | if (BN_ucmp(x, &group->field.N) >= 0) { |
186 | 0 | OPENSSL_PUT_ERROR(EC, EC_R_INVALID_ENCODING); |
187 | 0 | goto err; |
188 | 0 | } |
189 | | |
190 | 0 | if (!EC_POINT_set_compressed_coordinates_GFp(group, point, x, y_bit, ctx)) { |
191 | 0 | goto err; |
192 | 0 | } |
193 | | |
194 | 0 | ret = 1; |
195 | |
|
196 | 0 | err: |
197 | 0 | BN_CTX_end(ctx); |
198 | 0 | BN_CTX_free(new_ctx); |
199 | 0 | return ret; |
200 | 0 | } |
201 | | |
202 | | int EC_POINT_oct2point(const EC_GROUP *group, EC_POINT *point, |
203 | 0 | const uint8_t *buf, size_t len, BN_CTX *ctx) { |
204 | 0 | if (EC_GROUP_cmp(group, point->group, NULL) != 0) { |
205 | 0 | OPENSSL_PUT_ERROR(EC, EC_R_INCOMPATIBLE_OBJECTS); |
206 | 0 | return 0; |
207 | 0 | } |
208 | 0 | return ec_GFp_simple_oct2point(group, point, buf, len, ctx); |
209 | 0 | } |
210 | | |
211 | | size_t EC_POINT_point2oct(const EC_GROUP *group, const EC_POINT *point, |
212 | | point_conversion_form_t form, uint8_t *buf, |
213 | 0 | size_t max_out, BN_CTX *ctx) { |
214 | 0 | if (EC_GROUP_cmp(group, point->group, NULL) != 0) { |
215 | 0 | OPENSSL_PUT_ERROR(EC, EC_R_INCOMPATIBLE_OBJECTS); |
216 | 0 | return 0; |
217 | 0 | } |
218 | 0 | if (buf == NULL) { |
219 | | // When |buf| is NULL, just return the number of bytes that would be |
220 | | // written, without doing an expensive Jacobian-to-affine conversion. |
221 | 0 | if (ec_GFp_simple_is_at_infinity(group, &point->raw)) { |
222 | 0 | OPENSSL_PUT_ERROR(EC, EC_R_POINT_AT_INFINITY); |
223 | 0 | return 0; |
224 | 0 | } |
225 | 0 | return ec_point_byte_len(group, form); |
226 | 0 | } |
227 | 0 | EC_AFFINE affine; |
228 | 0 | if (!ec_jacobian_to_affine(group, &affine, &point->raw)) { |
229 | 0 | return 0; |
230 | 0 | } |
231 | 0 | return ec_point_to_bytes(group, &affine, form, buf, max_out); |
232 | 0 | } |
233 | | |
234 | | size_t EC_POINT_point2buf(const EC_GROUP *group, const EC_POINT *point, |
235 | | point_conversion_form_t form, uint8_t **out_buf, |
236 | 0 | BN_CTX *ctx) { |
237 | 0 | *out_buf = NULL; |
238 | 0 | size_t len = EC_POINT_point2oct(group, point, form, NULL, 0, ctx); |
239 | 0 | if (len == 0) { |
240 | 0 | return 0; |
241 | 0 | } |
242 | 0 | uint8_t *buf = OPENSSL_malloc(len); |
243 | 0 | if (buf == NULL) { |
244 | 0 | return 0; |
245 | 0 | } |
246 | 0 | len = EC_POINT_point2oct(group, point, form, buf, len, ctx); |
247 | 0 | if (len == 0) { |
248 | 0 | OPENSSL_free(buf); |
249 | 0 | return 0; |
250 | 0 | } |
251 | 0 | *out_buf = buf; |
252 | 0 | return len; |
253 | 0 | } |
254 | | |
255 | | int EC_POINT_set_compressed_coordinates_GFp(const EC_GROUP *group, |
256 | | EC_POINT *point, const BIGNUM *x, |
257 | 0 | int y_bit, BN_CTX *ctx) { |
258 | 0 | if (EC_GROUP_cmp(group, point->group, NULL) != 0) { |
259 | 0 | OPENSSL_PUT_ERROR(EC, EC_R_INCOMPATIBLE_OBJECTS); |
260 | 0 | return 0; |
261 | 0 | } |
262 | | |
263 | 0 | const BIGNUM *field = &group->field.N; |
264 | 0 | if (BN_is_negative(x) || BN_cmp(x, field) >= 0) { |
265 | 0 | OPENSSL_PUT_ERROR(EC, EC_R_INVALID_COMPRESSED_POINT); |
266 | 0 | return 0; |
267 | 0 | } |
268 | | |
269 | 0 | BN_CTX *new_ctx = NULL; |
270 | 0 | int ret = 0; |
271 | |
|
272 | 0 | ERR_clear_error(); |
273 | |
|
274 | 0 | if (ctx == NULL) { |
275 | 0 | ctx = new_ctx = BN_CTX_new(); |
276 | 0 | if (ctx == NULL) { |
277 | 0 | return 0; |
278 | 0 | } |
279 | 0 | } |
280 | | |
281 | 0 | y_bit = (y_bit != 0); |
282 | |
|
283 | 0 | BN_CTX_start(ctx); |
284 | 0 | BIGNUM *tmp1 = BN_CTX_get(ctx); |
285 | 0 | BIGNUM *tmp2 = BN_CTX_get(ctx); |
286 | 0 | BIGNUM *a = BN_CTX_get(ctx); |
287 | 0 | BIGNUM *b = BN_CTX_get(ctx); |
288 | 0 | BIGNUM *y = BN_CTX_get(ctx); |
289 | 0 | if (y == NULL || |
290 | 0 | !EC_GROUP_get_curve_GFp(group, NULL, a, b, ctx)) { |
291 | 0 | goto err; |
292 | 0 | } |
293 | | |
294 | | // Recover y. We have a Weierstrass equation |
295 | | // y^2 = x^3 + a*x + b, |
296 | | // so y is one of the square roots of x^3 + a*x + b. |
297 | | |
298 | | // tmp1 := x^3 |
299 | 0 | if (!BN_mod_sqr(tmp2, x, field, ctx) || |
300 | 0 | !BN_mod_mul(tmp1, tmp2, x, field, ctx)) { |
301 | 0 | goto err; |
302 | 0 | } |
303 | | |
304 | | // tmp1 := tmp1 + a*x |
305 | 0 | if (group->a_is_minus3) { |
306 | 0 | if (!bn_mod_lshift1_consttime(tmp2, x, field, ctx) || |
307 | 0 | !bn_mod_add_consttime(tmp2, tmp2, x, field, ctx) || |
308 | 0 | !bn_mod_sub_consttime(tmp1, tmp1, tmp2, field, ctx)) { |
309 | 0 | goto err; |
310 | 0 | } |
311 | 0 | } else { |
312 | 0 | if (!BN_mod_mul(tmp2, a, x, field, ctx) || |
313 | 0 | !bn_mod_add_consttime(tmp1, tmp1, tmp2, field, ctx)) { |
314 | 0 | goto err; |
315 | 0 | } |
316 | 0 | } |
317 | | |
318 | | // tmp1 := tmp1 + b |
319 | 0 | if (!bn_mod_add_consttime(tmp1, tmp1, b, field, ctx)) { |
320 | 0 | goto err; |
321 | 0 | } |
322 | | |
323 | 0 | if (!BN_mod_sqrt(y, tmp1, field, ctx)) { |
324 | 0 | uint32_t err = ERR_peek_last_error(); |
325 | 0 | if (ERR_GET_LIB(err) == ERR_LIB_BN && |
326 | 0 | ERR_GET_REASON(err) == BN_R_NOT_A_SQUARE) { |
327 | 0 | ERR_clear_error(); |
328 | 0 | OPENSSL_PUT_ERROR(EC, EC_R_INVALID_COMPRESSED_POINT); |
329 | 0 | } else { |
330 | 0 | OPENSSL_PUT_ERROR(EC, ERR_R_BN_LIB); |
331 | 0 | } |
332 | 0 | goto err; |
333 | 0 | } |
334 | | |
335 | 0 | if (y_bit != BN_is_odd(y)) { |
336 | 0 | if (BN_is_zero(y)) { |
337 | 0 | OPENSSL_PUT_ERROR(EC, EC_R_INVALID_COMPRESSION_BIT); |
338 | 0 | goto err; |
339 | 0 | } |
340 | 0 | if (!BN_usub(y, field, y)) { |
341 | 0 | goto err; |
342 | 0 | } |
343 | 0 | } |
344 | 0 | if (y_bit != BN_is_odd(y)) { |
345 | 0 | OPENSSL_PUT_ERROR(EC, ERR_R_INTERNAL_ERROR); |
346 | 0 | goto err; |
347 | 0 | } |
348 | | |
349 | 0 | if (!EC_POINT_set_affine_coordinates_GFp(group, point, x, y, ctx)) { |
350 | 0 | goto err; |
351 | 0 | } |
352 | | |
353 | 0 | ret = 1; |
354 | |
|
355 | 0 | err: |
356 | 0 | BN_CTX_end(ctx); |
357 | 0 | BN_CTX_free(new_ctx); |
358 | 0 | return ret; |
359 | 0 | } |