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