1 | /* |
2 | * Copyright 2011-2018 The OpenSSL Project Authors. All Rights Reserved. |
3 | * Copyright (c) 2002, Oracle and/or its affiliates. All rights reserved |
4 | * |
5 | * Licensed under the Apache License 2.0 (the "License"). You may not use |
6 | * this file except in compliance with the License. You can obtain a copy |
7 | * in the file LICENSE in the source distribution or at |
8 | * https://www.openssl.org/source/license.html |
9 | */ |
10 | |
11 | #include <openssl/err.h> |
12 | #include <openssl/symhacks.h> |
13 | |
14 | #include "ec_local.h" |
15 | |
16 | int ec_GFp_simple_set_compressed_coordinates(const EC_GROUP *group, |
17 | EC_POINT *point, |
18 | const BIGNUM *x_, int y_bit, |
19 | BN_CTX *ctx) |
20 | { |
21 | BN_CTX *new_ctx = NULL; |
22 | BIGNUM *tmp1, *tmp2, *x, *y; |
23 | int ret = 0; |
24 | |
25 | #ifndef FIPS_MODE |
26 | /* clear error queue */ |
27 | ERR_clear_error(); |
28 | #endif |
29 | |
30 | if (ctx == NULL) { |
31 | ctx = new_ctx = BN_CTX_new_ex(group->libctx); |
32 | if (ctx == NULL) |
33 | return 0; |
34 | } |
35 | |
36 | y_bit = (y_bit != 0); |
37 | |
38 | BN_CTX_start(ctx); |
39 | tmp1 = BN_CTX_get(ctx); |
40 | tmp2 = BN_CTX_get(ctx); |
41 | x = BN_CTX_get(ctx); |
42 | y = BN_CTX_get(ctx); |
43 | if (y == NULL) |
44 | goto err; |
45 | |
46 | /*- |
47 | * Recover y. We have a Weierstrass equation |
48 | * y^2 = x^3 + a*x + b, |
49 | * so y is one of the square roots of x^3 + a*x + b. |
50 | */ |
51 | |
52 | /* tmp1 := x^3 */ |
53 | if (!BN_nnmod(x, x_, group->field, ctx)) |
54 | goto err; |
55 | if (group->meth->field_decode == 0) { |
56 | /* field_{sqr,mul} work on standard representation */ |
57 | if (!group->meth->field_sqr(group, tmp2, x_, ctx)) |
58 | goto err; |
59 | if (!group->meth->field_mul(group, tmp1, tmp2, x_, ctx)) |
60 | goto err; |
61 | } else { |
62 | if (!BN_mod_sqr(tmp2, x_, group->field, ctx)) |
63 | goto err; |
64 | if (!BN_mod_mul(tmp1, tmp2, x_, group->field, ctx)) |
65 | goto err; |
66 | } |
67 | |
68 | /* tmp1 := tmp1 + a*x */ |
69 | if (group->a_is_minus3) { |
70 | if (!BN_mod_lshift1_quick(tmp2, x, group->field)) |
71 | goto err; |
72 | if (!BN_mod_add_quick(tmp2, tmp2, x, group->field)) |
73 | goto err; |
74 | if (!BN_mod_sub_quick(tmp1, tmp1, tmp2, group->field)) |
75 | goto err; |
76 | } else { |
77 | if (group->meth->field_decode) { |
78 | if (!group->meth->field_decode(group, tmp2, group->a, ctx)) |
79 | goto err; |
80 | if (!BN_mod_mul(tmp2, tmp2, x, group->field, ctx)) |
81 | goto err; |
82 | } else { |
83 | /* field_mul works on standard representation */ |
84 | if (!group->meth->field_mul(group, tmp2, group->a, x, ctx)) |
85 | goto err; |
86 | } |
87 | |
88 | if (!BN_mod_add_quick(tmp1, tmp1, tmp2, group->field)) |
89 | goto err; |
90 | } |
91 | |
92 | /* tmp1 := tmp1 + b */ |
93 | if (group->meth->field_decode) { |
94 | if (!group->meth->field_decode(group, tmp2, group->b, ctx)) |
95 | goto err; |
96 | if (!BN_mod_add_quick(tmp1, tmp1, tmp2, group->field)) |
97 | goto err; |
98 | } else { |
99 | if (!BN_mod_add_quick(tmp1, tmp1, group->b, group->field)) |
100 | goto err; |
101 | } |
102 | |
103 | if (!BN_mod_sqrt(y, tmp1, group->field, ctx)) { |
104 | #ifndef FIPS_MODE |
105 | unsigned long err = ERR_peek_last_error(); |
106 | |
107 | if (ERR_GET_LIB(err) == ERR_LIB_BN |
108 | && ERR_GET_REASON(err) == BN_R_NOT_A_SQUARE) { |
109 | ERR_clear_error(); |
110 | ECerr(EC_F_EC_GFP_SIMPLE_SET_COMPRESSED_COORDINATES, |
111 | EC_R_INVALID_COMPRESSED_POINT); |
112 | } else |
113 | #endif |
114 | { |
115 | ECerr(EC_F_EC_GFP_SIMPLE_SET_COMPRESSED_COORDINATES, |
116 | ERR_R_BN_LIB); |
117 | } |
118 | goto err; |
119 | } |
120 | |
121 | if (y_bit != BN_is_odd(y)) { |
122 | if (BN_is_zero(y)) { |
123 | int kron; |
124 | |
125 | kron = BN_kronecker(x, group->field, ctx); |
126 | if (kron == -2) |
127 | goto err; |
128 | |
129 | if (kron == 1) |
130 | ECerr(EC_F_EC_GFP_SIMPLE_SET_COMPRESSED_COORDINATES, |
131 | EC_R_INVALID_COMPRESSION_BIT); |
132 | else |
133 | /* |
134 | * BN_mod_sqrt() should have caught this error (not a square) |
135 | */ |
136 | ECerr(EC_F_EC_GFP_SIMPLE_SET_COMPRESSED_COORDINATES, |
137 | EC_R_INVALID_COMPRESSED_POINT); |
138 | goto err; |
139 | } |
140 | if (!BN_usub(y, group->field, y)) |
141 | goto err; |
142 | } |
143 | if (y_bit != BN_is_odd(y)) { |
144 | ECerr(EC_F_EC_GFP_SIMPLE_SET_COMPRESSED_COORDINATES, |
145 | ERR_R_INTERNAL_ERROR); |
146 | goto err; |
147 | } |
148 | |
149 | if (!EC_POINT_set_affine_coordinates(group, point, x, y, ctx)) |
150 | goto err; |
151 | |
152 | ret = 1; |
153 | |
154 | err: |
155 | BN_CTX_end(ctx); |
156 | BN_CTX_free(new_ctx); |
157 | return ret; |
158 | } |
159 | |
160 | size_t ec_GFp_simple_point2oct(const EC_GROUP *group, const EC_POINT *point, |
161 | point_conversion_form_t form, |
162 | unsigned char *buf, size_t len, BN_CTX *ctx) |
163 | { |
164 | size_t ret; |
165 | BN_CTX *new_ctx = NULL; |
166 | int used_ctx = 0; |
167 | BIGNUM *x, *y; |
168 | size_t field_len, i, skip; |
169 | |
170 | if ((form != POINT_CONVERSION_COMPRESSED) |
171 | && (form != POINT_CONVERSION_UNCOMPRESSED) |
172 | && (form != POINT_CONVERSION_HYBRID)) { |
173 | ECerr(EC_F_EC_GFP_SIMPLE_POINT2OCT, EC_R_INVALID_FORM); |
174 | goto err; |
175 | } |
176 | |
177 | if (EC_POINT_is_at_infinity(group, point)) { |
178 | /* encodes to a single 0 octet */ |
179 | if (buf != NULL) { |
180 | if (len < 1) { |
181 | ECerr(EC_F_EC_GFP_SIMPLE_POINT2OCT, EC_R_BUFFER_TOO_SMALL); |
182 | return 0; |
183 | } |
184 | buf[0] = 0; |
185 | } |
186 | return 1; |
187 | } |
188 | |
189 | /* ret := required output buffer length */ |
190 | field_len = BN_num_bytes(group->field); |
191 | ret = |
192 | (form == |
193 | POINT_CONVERSION_COMPRESSED) ? 1 + field_len : 1 + 2 * field_len; |
194 | |
195 | /* if 'buf' is NULL, just return required length */ |
196 | if (buf != NULL) { |
197 | if (len < ret) { |
198 | ECerr(EC_F_EC_GFP_SIMPLE_POINT2OCT, EC_R_BUFFER_TOO_SMALL); |
199 | goto err; |
200 | } |
201 | |
202 | if (ctx == NULL) { |
203 | ctx = new_ctx = BN_CTX_new_ex(group->libctx); |
204 | if (ctx == NULL) |
205 | return 0; |
206 | } |
207 | |
208 | BN_CTX_start(ctx); |
209 | used_ctx = 1; |
210 | x = BN_CTX_get(ctx); |
211 | y = BN_CTX_get(ctx); |
212 | if (y == NULL) |
213 | goto err; |
214 | |
215 | if (!EC_POINT_get_affine_coordinates(group, point, x, y, ctx)) |
216 | goto err; |
217 | |
218 | if ((form == POINT_CONVERSION_COMPRESSED |
219 | || form == POINT_CONVERSION_HYBRID) && BN_is_odd(y)) |
220 | buf[0] = form + 1; |
221 | else |
222 | buf[0] = form; |
223 | |
224 | i = 1; |
225 | |
226 | skip = field_len - BN_num_bytes(x); |
227 | if (skip > field_len) { |
228 | ECerr(EC_F_EC_GFP_SIMPLE_POINT2OCT, ERR_R_INTERNAL_ERROR); |
229 | goto err; |
230 | } |
231 | while (skip > 0) { |
232 | buf[i++] = 0; |
233 | skip--; |
234 | } |
235 | skip = BN_bn2bin(x, buf + i); |
236 | i += skip; |
237 | if (i != 1 + field_len) { |
238 | ECerr(EC_F_EC_GFP_SIMPLE_POINT2OCT, ERR_R_INTERNAL_ERROR); |
239 | goto err; |
240 | } |
241 | |
242 | if (form == POINT_CONVERSION_UNCOMPRESSED |
243 | || form == POINT_CONVERSION_HYBRID) { |
244 | skip = field_len - BN_num_bytes(y); |
245 | if (skip > field_len) { |
246 | ECerr(EC_F_EC_GFP_SIMPLE_POINT2OCT, ERR_R_INTERNAL_ERROR); |
247 | goto err; |
248 | } |
249 | while (skip > 0) { |
250 | buf[i++] = 0; |
251 | skip--; |
252 | } |
253 | skip = BN_bn2bin(y, buf + i); |
254 | i += skip; |
255 | } |
256 | |
257 | if (i != ret) { |
258 | ECerr(EC_F_EC_GFP_SIMPLE_POINT2OCT, ERR_R_INTERNAL_ERROR); |
259 | goto err; |
260 | } |
261 | } |
262 | |
263 | if (used_ctx) |
264 | BN_CTX_end(ctx); |
265 | BN_CTX_free(new_ctx); |
266 | return ret; |
267 | |
268 | err: |
269 | if (used_ctx) |
270 | BN_CTX_end(ctx); |
271 | BN_CTX_free(new_ctx); |
272 | return 0; |
273 | } |
274 | |
275 | int ec_GFp_simple_oct2point(const EC_GROUP *group, EC_POINT *point, |
276 | const unsigned char *buf, size_t len, BN_CTX *ctx) |
277 | { |
278 | point_conversion_form_t form; |
279 | int y_bit; |
280 | BN_CTX *new_ctx = NULL; |
281 | BIGNUM *x, *y; |
282 | size_t field_len, enc_len; |
283 | int ret = 0; |
284 | |
285 | if (len == 0) { |
286 | ECerr(EC_F_EC_GFP_SIMPLE_OCT2POINT, EC_R_BUFFER_TOO_SMALL); |
287 | return 0; |
288 | } |
289 | form = buf[0]; |
290 | y_bit = form & 1; |
291 | form = form & ~1U; |
292 | if ((form != 0) && (form != POINT_CONVERSION_COMPRESSED) |
293 | && (form != POINT_CONVERSION_UNCOMPRESSED) |
294 | && (form != POINT_CONVERSION_HYBRID)) { |
295 | ECerr(EC_F_EC_GFP_SIMPLE_OCT2POINT, EC_R_INVALID_ENCODING); |
296 | return 0; |
297 | } |
298 | if ((form == 0 || form == POINT_CONVERSION_UNCOMPRESSED) && y_bit) { |
299 | ECerr(EC_F_EC_GFP_SIMPLE_OCT2POINT, EC_R_INVALID_ENCODING); |
300 | return 0; |
301 | } |
302 | |
303 | if (form == 0) { |
304 | if (len != 1) { |
305 | ECerr(EC_F_EC_GFP_SIMPLE_OCT2POINT, EC_R_INVALID_ENCODING); |
306 | return 0; |
307 | } |
308 | |
309 | return EC_POINT_set_to_infinity(group, point); |
310 | } |
311 | |
312 | field_len = BN_num_bytes(group->field); |
313 | enc_len = |
314 | (form == |
315 | POINT_CONVERSION_COMPRESSED) ? 1 + field_len : 1 + 2 * field_len; |
316 | |
317 | if (len != enc_len) { |
318 | ECerr(EC_F_EC_GFP_SIMPLE_OCT2POINT, EC_R_INVALID_ENCODING); |
319 | return 0; |
320 | } |
321 | |
322 | if (ctx == NULL) { |
323 | ctx = new_ctx = BN_CTX_new_ex(group->libctx); |
324 | if (ctx == NULL) |
325 | return 0; |
326 | } |
327 | |
328 | BN_CTX_start(ctx); |
329 | x = BN_CTX_get(ctx); |
330 | y = BN_CTX_get(ctx); |
331 | if (y == NULL) |
332 | goto err; |
333 | |
334 | if (!BN_bin2bn(buf + 1, field_len, x)) |
335 | goto err; |
336 | if (BN_ucmp(x, group->field) >= 0) { |
337 | ECerr(EC_F_EC_GFP_SIMPLE_OCT2POINT, EC_R_INVALID_ENCODING); |
338 | goto err; |
339 | } |
340 | |
341 | if (form == POINT_CONVERSION_COMPRESSED) { |
342 | if (!EC_POINT_set_compressed_coordinates(group, point, x, y_bit, ctx)) |
343 | goto err; |
344 | } else { |
345 | if (!BN_bin2bn(buf + 1 + field_len, field_len, y)) |
346 | goto err; |
347 | if (BN_ucmp(y, group->field) >= 0) { |
348 | ECerr(EC_F_EC_GFP_SIMPLE_OCT2POINT, EC_R_INVALID_ENCODING); |
349 | goto err; |
350 | } |
351 | if (form == POINT_CONVERSION_HYBRID) { |
352 | if (y_bit != BN_is_odd(y)) { |
353 | ECerr(EC_F_EC_GFP_SIMPLE_OCT2POINT, EC_R_INVALID_ENCODING); |
354 | goto err; |
355 | } |
356 | } |
357 | |
358 | /* |
359 | * EC_POINT_set_affine_coordinates is responsible for checking that |
360 | * the point is on the curve. |
361 | */ |
362 | if (!EC_POINT_set_affine_coordinates(group, point, x, y, ctx)) |
363 | goto err; |
364 | } |
365 | |
366 | ret = 1; |
367 | |
368 | err: |
369 | BN_CTX_end(ctx); |
370 | BN_CTX_free(new_ctx); |
371 | return ret; |
372 | } |
373 | |