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