Line data Source code
1 : /* crypto/ec/ecp_oct.c */
2 : /*
3 : * Includes code written by Lenka Fibikova <fibikova@exp-math.uni-essen.de>
4 : * for the OpenSSL project. Includes code written by Bodo Moeller for the
5 : * OpenSSL project.
6 : */
7 : /* ====================================================================
8 : * Copyright (c) 1998-2002 The OpenSSL Project. All rights reserved.
9 : *
10 : * Redistribution and use in source and binary forms, with or without
11 : * modification, are permitted provided that the following conditions
12 : * are met:
13 : *
14 : * 1. Redistributions of source code must retain the above copyright
15 : * notice, this list of conditions and the following disclaimer.
16 : *
17 : * 2. Redistributions in binary form must reproduce the above copyright
18 : * notice, this list of conditions and the following disclaimer in
19 : * the documentation and/or other materials provided with the
20 : * distribution.
21 : *
22 : * 3. All advertising materials mentioning features or use of this
23 : * software must display the following acknowledgment:
24 : * "This product includes software developed by the OpenSSL Project
25 : * for use in the OpenSSL Toolkit. (http://www.openssl.org/)"
26 : *
27 : * 4. The names "OpenSSL Toolkit" and "OpenSSL Project" must not be used to
28 : * endorse or promote products derived from this software without
29 : * prior written permission. For written permission, please contact
30 : * openssl-core@openssl.org.
31 : *
32 : * 5. Products derived from this software may not be called "OpenSSL"
33 : * nor may "OpenSSL" appear in their names without prior written
34 : * permission of the OpenSSL Project.
35 : *
36 : * 6. Redistributions of any form whatsoever must retain the following
37 : * acknowledgment:
38 : * "This product includes software developed by the OpenSSL Project
39 : * for use in the OpenSSL Toolkit (http://www.openssl.org/)"
40 : *
41 : * THIS SOFTWARE IS PROVIDED BY THE OpenSSL PROJECT ``AS IS'' AND ANY
42 : * EXPRESSED OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
43 : * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
44 : * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE OpenSSL PROJECT OR
45 : * ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
46 : * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
47 : * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
48 : * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
49 : * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
50 : * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
51 : * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED
52 : * OF THE POSSIBILITY OF SUCH DAMAGE.
53 : * ====================================================================
54 : *
55 : * This product includes cryptographic software written by Eric Young
56 : * (eay@cryptsoft.com). This product includes software written by Tim
57 : * Hudson (tjh@cryptsoft.com).
58 : *
59 : */
60 : /* ====================================================================
61 : * Copyright 2002 Sun Microsystems, Inc. ALL RIGHTS RESERVED.
62 : * Portions of this software developed by SUN MICROSYSTEMS, INC.,
63 : * and contributed to the OpenSSL project.
64 : */
65 :
66 : #include <openssl/err.h>
67 : #include <openssl/symhacks.h>
68 :
69 : #include "ec_lcl.h"
70 :
71 0 : int ec_GFp_simple_set_compressed_coordinates(const EC_GROUP *group,
72 : EC_POINT *point,
73 : const BIGNUM *x_, int y_bit,
74 : BN_CTX *ctx)
75 : {
76 : BN_CTX *new_ctx = NULL;
77 : BIGNUM *tmp1, *tmp2, *x, *y;
78 : int ret = 0;
79 :
80 : /* clear error queue */
81 0 : ERR_clear_error();
82 :
83 0 : if (ctx == NULL) {
84 0 : ctx = new_ctx = BN_CTX_new();
85 0 : if (ctx == NULL)
86 : return 0;
87 : }
88 :
89 0 : y_bit = (y_bit != 0);
90 :
91 0 : BN_CTX_start(ctx);
92 0 : tmp1 = BN_CTX_get(ctx);
93 0 : tmp2 = BN_CTX_get(ctx);
94 0 : x = BN_CTX_get(ctx);
95 0 : y = BN_CTX_get(ctx);
96 0 : if (y == NULL)
97 : goto err;
98 :
99 : /*-
100 : * Recover y. We have a Weierstrass equation
101 : * y^2 = x^3 + a*x + b,
102 : * so y is one of the square roots of x^3 + a*x + b.
103 : */
104 :
105 : /* tmp1 := x^3 */
106 0 : if (!BN_nnmod(x, x_, &group->field, ctx))
107 : goto err;
108 0 : if (group->meth->field_decode == 0) {
109 : /* field_{sqr,mul} work on standard representation */
110 0 : if (!group->meth->field_sqr(group, tmp2, x_, ctx))
111 : goto err;
112 0 : if (!group->meth->field_mul(group, tmp1, tmp2, x_, ctx))
113 : goto err;
114 : } else {
115 0 : if (!BN_mod_sqr(tmp2, x_, &group->field, ctx))
116 : goto err;
117 0 : if (!BN_mod_mul(tmp1, tmp2, x_, &group->field, ctx))
118 : goto err;
119 : }
120 :
121 : /* tmp1 := tmp1 + a*x */
122 0 : if (group->a_is_minus3) {
123 0 : if (!BN_mod_lshift1_quick(tmp2, x, &group->field))
124 : goto err;
125 0 : if (!BN_mod_add_quick(tmp2, tmp2, x, &group->field))
126 : goto err;
127 0 : if (!BN_mod_sub_quick(tmp1, tmp1, tmp2, &group->field))
128 : goto err;
129 : } else {
130 0 : if (group->meth->field_decode) {
131 0 : if (!group->meth->field_decode(group, tmp2, &group->a, ctx))
132 : goto err;
133 0 : if (!BN_mod_mul(tmp2, tmp2, x, &group->field, ctx))
134 : goto err;
135 : } else {
136 : /* field_mul works on standard representation */
137 0 : if (!group->meth->field_mul(group, tmp2, &group->a, x, ctx))
138 : goto err;
139 : }
140 :
141 0 : if (!BN_mod_add_quick(tmp1, tmp1, tmp2, &group->field))
142 : goto err;
143 : }
144 :
145 : /* tmp1 := tmp1 + b */
146 0 : if (group->meth->field_decode) {
147 0 : if (!group->meth->field_decode(group, tmp2, &group->b, ctx))
148 : goto err;
149 0 : if (!BN_mod_add_quick(tmp1, tmp1, tmp2, &group->field))
150 : goto err;
151 : } else {
152 0 : if (!BN_mod_add_quick(tmp1, tmp1, &group->b, &group->field))
153 : goto err;
154 : }
155 :
156 0 : if (!BN_mod_sqrt(y, tmp1, &group->field, ctx)) {
157 0 : unsigned long err = ERR_peek_last_error();
158 :
159 0 : if (ERR_GET_LIB(err) == ERR_LIB_BN
160 0 : && ERR_GET_REASON(err) == BN_R_NOT_A_SQUARE) {
161 0 : ERR_clear_error();
162 0 : ECerr(EC_F_EC_GFP_SIMPLE_SET_COMPRESSED_COORDINATES,
163 : EC_R_INVALID_COMPRESSED_POINT);
164 : } else
165 0 : ECerr(EC_F_EC_GFP_SIMPLE_SET_COMPRESSED_COORDINATES,
166 : ERR_R_BN_LIB);
167 : goto err;
168 : }
169 :
170 0 : if (y_bit != BN_is_odd(y)) {
171 0 : if (BN_is_zero(y)) {
172 : int kron;
173 :
174 0 : kron = BN_kronecker(x, &group->field, ctx);
175 0 : if (kron == -2)
176 : goto err;
177 :
178 0 : if (kron == 1)
179 0 : ECerr(EC_F_EC_GFP_SIMPLE_SET_COMPRESSED_COORDINATES,
180 : EC_R_INVALID_COMPRESSION_BIT);
181 : else
182 : /*
183 : * BN_mod_sqrt() should have cought this error (not a square)
184 : */
185 0 : ECerr(EC_F_EC_GFP_SIMPLE_SET_COMPRESSED_COORDINATES,
186 : EC_R_INVALID_COMPRESSED_POINT);
187 : goto err;
188 : }
189 0 : if (!BN_usub(y, &group->field, y))
190 : goto err;
191 : }
192 0 : if (y_bit != BN_is_odd(y)) {
193 0 : ECerr(EC_F_EC_GFP_SIMPLE_SET_COMPRESSED_COORDINATES,
194 : ERR_R_INTERNAL_ERROR);
195 0 : goto err;
196 : }
197 :
198 0 : if (!EC_POINT_set_affine_coordinates_GFp(group, point, x, y, ctx))
199 : goto err;
200 :
201 : ret = 1;
202 :
203 : err:
204 0 : BN_CTX_end(ctx);
205 0 : if (new_ctx != NULL)
206 0 : BN_CTX_free(new_ctx);
207 0 : return ret;
208 : }
209 :
210 1486 : size_t ec_GFp_simple_point2oct(const EC_GROUP *group, const EC_POINT *point,
211 : point_conversion_form_t form,
212 : unsigned char *buf, size_t len, BN_CTX *ctx)
213 : {
214 : size_t ret;
215 : BN_CTX *new_ctx = NULL;
216 : int used_ctx = 0;
217 : BIGNUM *x, *y;
218 : size_t field_len, i, skip;
219 :
220 2972 : if ((form != POINT_CONVERSION_COMPRESSED)
221 1486 : && (form != POINT_CONVERSION_UNCOMPRESSED)
222 0 : && (form != POINT_CONVERSION_HYBRID)) {
223 0 : ECerr(EC_F_EC_GFP_SIMPLE_POINT2OCT, EC_R_INVALID_FORM);
224 0 : goto err;
225 : }
226 :
227 1486 : if (EC_POINT_is_at_infinity(group, point)) {
228 : /* encodes to a single 0 octet */
229 0 : if (buf != NULL) {
230 0 : if (len < 1) {
231 0 : ECerr(EC_F_EC_GFP_SIMPLE_POINT2OCT, EC_R_BUFFER_TOO_SMALL);
232 0 : return 0;
233 : }
234 0 : buf[0] = 0;
235 : }
236 : return 1;
237 : }
238 :
239 : /* ret := required output buffer length */
240 1486 : field_len = BN_num_bytes(&group->field);
241 : ret =
242 : (form ==
243 1486 : POINT_CONVERSION_COMPRESSED) ? 1 + field_len : 1 + 2 * field_len;
244 :
245 : /* if 'buf' is NULL, just return required length */
246 1486 : if (buf != NULL) {
247 743 : if (len < ret) {
248 0 : ECerr(EC_F_EC_GFP_SIMPLE_POINT2OCT, EC_R_BUFFER_TOO_SMALL);
249 0 : goto err;
250 : }
251 :
252 743 : if (ctx == NULL) {
253 0 : ctx = new_ctx = BN_CTX_new();
254 0 : if (ctx == NULL)
255 : return 0;
256 : }
257 :
258 743 : BN_CTX_start(ctx);
259 : used_ctx = 1;
260 743 : x = BN_CTX_get(ctx);
261 743 : y = BN_CTX_get(ctx);
262 743 : if (y == NULL)
263 : goto err;
264 :
265 743 : if (!EC_POINT_get_affine_coordinates_GFp(group, point, x, y, ctx))
266 : goto err;
267 :
268 1486 : if ((form == POINT_CONVERSION_COMPRESSED
269 743 : || form == POINT_CONVERSION_HYBRID) && BN_is_odd(y))
270 0 : buf[0] = form + 1;
271 : else
272 743 : buf[0] = form;
273 :
274 : i = 1;
275 :
276 743 : skip = field_len - BN_num_bytes(x);
277 743 : if (skip > field_len) {
278 0 : ECerr(EC_F_EC_GFP_SIMPLE_POINT2OCT, ERR_R_INTERNAL_ERROR);
279 0 : goto err;
280 : }
281 744 : while (skip > 0) {
282 1 : buf[i++] = 0;
283 1 : skip--;
284 : }
285 743 : skip = BN_bn2bin(x, buf + i);
286 743 : i += skip;
287 743 : if (i != 1 + field_len) {
288 0 : ECerr(EC_F_EC_GFP_SIMPLE_POINT2OCT, ERR_R_INTERNAL_ERROR);
289 0 : goto err;
290 : }
291 :
292 1486 : if (form == POINT_CONVERSION_UNCOMPRESSED
293 743 : || form == POINT_CONVERSION_HYBRID) {
294 743 : skip = field_len - BN_num_bytes(y);
295 743 : if (skip > field_len) {
296 0 : ECerr(EC_F_EC_GFP_SIMPLE_POINT2OCT, ERR_R_INTERNAL_ERROR);
297 0 : goto err;
298 : }
299 747 : while (skip > 0) {
300 4 : buf[i++] = 0;
301 4 : skip--;
302 : }
303 743 : skip = BN_bn2bin(y, buf + i);
304 743 : i += skip;
305 : }
306 :
307 743 : if (i != ret) {
308 0 : ECerr(EC_F_EC_GFP_SIMPLE_POINT2OCT, ERR_R_INTERNAL_ERROR);
309 0 : goto err;
310 : }
311 : }
312 :
313 1486 : if (used_ctx)
314 743 : BN_CTX_end(ctx);
315 1486 : if (new_ctx != NULL)
316 0 : BN_CTX_free(new_ctx);
317 1486 : return ret;
318 :
319 : err:
320 0 : if (used_ctx)
321 0 : BN_CTX_end(ctx);
322 0 : if (new_ctx != NULL)
323 0 : BN_CTX_free(new_ctx);
324 : return 0;
325 : }
326 :
327 737 : int ec_GFp_simple_oct2point(const EC_GROUP *group, EC_POINT *point,
328 : const unsigned char *buf, size_t len, BN_CTX *ctx)
329 : {
330 : point_conversion_form_t form;
331 : int y_bit;
332 : BN_CTX *new_ctx = NULL;
333 : BIGNUM *x, *y;
334 : size_t field_len, enc_len;
335 : int ret = 0;
336 :
337 737 : if (len == 0) {
338 0 : ECerr(EC_F_EC_GFP_SIMPLE_OCT2POINT, EC_R_BUFFER_TOO_SMALL);
339 0 : return 0;
340 : }
341 737 : form = buf[0];
342 737 : y_bit = form & 1;
343 737 : form = form & ~1U;
344 737 : if ((form != 0) && (form != POINT_CONVERSION_COMPRESSED)
345 737 : && (form != POINT_CONVERSION_UNCOMPRESSED)
346 737 : && (form != POINT_CONVERSION_HYBRID)) {
347 0 : ECerr(EC_F_EC_GFP_SIMPLE_OCT2POINT, EC_R_INVALID_ENCODING);
348 0 : return 0;
349 : }
350 737 : if ((form == 0 || form == POINT_CONVERSION_UNCOMPRESSED) && y_bit) {
351 0 : ECerr(EC_F_EC_GFP_SIMPLE_OCT2POINT, EC_R_INVALID_ENCODING);
352 0 : return 0;
353 : }
354 :
355 737 : if (form == 0) {
356 0 : if (len != 1) {
357 0 : ECerr(EC_F_EC_GFP_SIMPLE_OCT2POINT, EC_R_INVALID_ENCODING);
358 0 : return 0;
359 : }
360 :
361 0 : return EC_POINT_set_to_infinity(group, point);
362 : }
363 :
364 737 : field_len = BN_num_bytes(&group->field);
365 : enc_len =
366 : (form ==
367 737 : POINT_CONVERSION_COMPRESSED) ? 1 + field_len : 1 + 2 * field_len;
368 :
369 737 : if (len != enc_len) {
370 0 : ECerr(EC_F_EC_GFP_SIMPLE_OCT2POINT, EC_R_INVALID_ENCODING);
371 0 : return 0;
372 : }
373 :
374 737 : if (ctx == NULL) {
375 0 : ctx = new_ctx = BN_CTX_new();
376 0 : if (ctx == NULL)
377 : return 0;
378 : }
379 :
380 737 : BN_CTX_start(ctx);
381 737 : x = BN_CTX_get(ctx);
382 737 : y = BN_CTX_get(ctx);
383 737 : if (y == NULL)
384 : goto err;
385 :
386 737 : if (!BN_bin2bn(buf + 1, field_len, x))
387 : goto err;
388 737 : if (BN_ucmp(x, &group->field) >= 0) {
389 0 : ECerr(EC_F_EC_GFP_SIMPLE_OCT2POINT, EC_R_INVALID_ENCODING);
390 0 : goto err;
391 : }
392 :
393 737 : if (form == POINT_CONVERSION_COMPRESSED) {
394 0 : if (!EC_POINT_set_compressed_coordinates_GFp
395 0 : (group, point, x, y_bit, ctx))
396 : goto err;
397 : } else {
398 737 : if (!BN_bin2bn(buf + 1 + field_len, field_len, y))
399 : goto err;
400 737 : if (BN_ucmp(y, &group->field) >= 0) {
401 0 : ECerr(EC_F_EC_GFP_SIMPLE_OCT2POINT, EC_R_INVALID_ENCODING);
402 0 : goto err;
403 : }
404 737 : if (form == POINT_CONVERSION_HYBRID) {
405 0 : if (y_bit != BN_is_odd(y)) {
406 0 : ECerr(EC_F_EC_GFP_SIMPLE_OCT2POINT, EC_R_INVALID_ENCODING);
407 0 : goto err;
408 : }
409 : }
410 :
411 737 : if (!EC_POINT_set_affine_coordinates_GFp(group, point, x, y, ctx))
412 : goto err;
413 : }
414 :
415 : /* test required by X9.62 */
416 737 : if (EC_POINT_is_on_curve(group, point, ctx) <= 0) {
417 0 : ECerr(EC_F_EC_GFP_SIMPLE_OCT2POINT, EC_R_POINT_IS_NOT_ON_CURVE);
418 0 : goto err;
419 : }
420 :
421 : ret = 1;
422 :
423 : err:
424 737 : BN_CTX_end(ctx);
425 737 : if (new_ctx != NULL)
426 0 : BN_CTX_free(new_ctx);
427 737 : return ret;
428 : }
|
