1 /* ====================================================================
2 * Copyright 2002 Sun Microsystems, Inc. ALL RIGHTS RESERVED.
4 * The Elliptic Curve Public-Key Crypto Library (ECC Code) included
5 * herein is developed by SUN MICROSYSTEMS, INC., and is contributed
6 * to the OpenSSL project.
8 * The ECC Code is licensed pursuant to the OpenSSL open source
9 * license provided below.
11 * The software is originally written by Sheueling Chang Shantz and
12 * Douglas Stebila of Sun Microsystems Laboratories.
15 /* ====================================================================
16 * Copyright (c) 1998-2005 The OpenSSL Project. All rights reserved.
18 * Redistribution and use in source and binary forms, with or without
19 * modification, are permitted provided that the following conditions
22 * 1. Redistributions of source code must retain the above copyright
23 * notice, this list of conditions and the following disclaimer.
25 * 2. Redistributions in binary form must reproduce the above copyright
26 * notice, this list of conditions and the following disclaimer in
27 * the documentation and/or other materials provided with the
30 * 3. All advertising materials mentioning features or use of this
31 * software must display the following acknowledgment:
32 * "This product includes software developed by the OpenSSL Project
33 * for use in the OpenSSL Toolkit. (http://www.openssl.org/)"
35 * 4. The names "OpenSSL Toolkit" and "OpenSSL Project" must not be used to
36 * endorse or promote products derived from this software without
37 * prior written permission. For written permission, please contact
38 * openssl-core@openssl.org.
40 * 5. Products derived from this software may not be called "OpenSSL"
41 * nor may "OpenSSL" appear in their names without prior written
42 * permission of the OpenSSL Project.
44 * 6. Redistributions of any form whatsoever must retain the following
46 * "This product includes software developed by the OpenSSL Project
47 * for use in the OpenSSL Toolkit (http://www.openssl.org/)"
49 * THIS SOFTWARE IS PROVIDED BY THE OpenSSL PROJECT ``AS IS'' AND ANY
50 * EXPRESSED OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
51 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
52 * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE OpenSSL PROJECT OR
53 * ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
54 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
55 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
56 * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
57 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
58 * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
59 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED
60 * OF THE POSSIBILITY OF SUCH DAMAGE.
61 * ====================================================================
63 * This product includes cryptographic software written by Eric Young
64 * (eay@cryptsoft.com). This product includes software written by Tim
65 * Hudson (tjh@cryptsoft.com).
69 #include <openssl/err.h>
73 #ifndef OPENSSL_NO_EC2M
76 * Calculates and sets the affine coordinates of an EC_POINT from the given
77 * compressed coordinates. Uses algorithm 2.3.4 of SEC 1.
78 * Note that the simple implementation only uses affine coordinates.
80 * The method is from the following publication:
82 * Harper, Menezes, Vanstone:
83 * "Public-Key Cryptosystems with Very Small Key Lengths",
84 * EUROCRYPT '92, Springer-Verlag LNCS 658,
85 * published February 1993
87 * US Patents 6,141,420 and 6,618,483 (Vanstone, Mullin, Agnew) describe
88 * the same method, but claim no priority date earlier than July 29, 1994
89 * (and additionally fail to cite the EUROCRYPT '92 publication as prior art).
91 int ec_GF2m_simple_set_compressed_coordinates(const EC_GROUP *group,
93 const BIGNUM *x_, int y_bit,
96 BN_CTX *new_ctx = NULL;
97 BIGNUM *tmp, *x, *y, *z;
100 /* clear error queue */
104 ctx = new_ctx = BN_CTX_new();
109 y_bit = (y_bit != 0) ? 1 : 0;
112 tmp = BN_CTX_get(ctx);
119 if (!BN_GF2m_mod_arr(x, x_, group->poly))
122 if (!BN_GF2m_mod_sqrt_arr(y, group->b, group->poly, ctx))
125 if (!group->meth->field_sqr(group, tmp, x, ctx))
127 if (!group->meth->field_div(group, tmp, group->b, tmp, ctx))
129 if (!BN_GF2m_add(tmp, group->a, tmp))
131 if (!BN_GF2m_add(tmp, x, tmp))
133 if (!BN_GF2m_mod_solve_quad_arr(z, tmp, group->poly, ctx)) {
134 unsigned long err = ERR_peek_last_error();
136 if (ERR_GET_LIB(err) == ERR_LIB_BN
137 && ERR_GET_REASON(err) == BN_R_NO_SOLUTION) {
139 ECerr(EC_F_EC_GF2M_SIMPLE_SET_COMPRESSED_COORDINATES,
140 EC_R_INVALID_COMPRESSED_POINT);
142 ECerr(EC_F_EC_GF2M_SIMPLE_SET_COMPRESSED_COORDINATES,
146 z0 = (BN_is_odd(z)) ? 1 : 0;
147 if (!group->meth->field_mul(group, y, x, z, ctx))
150 if (!BN_GF2m_add(y, y, x))
155 if (!EC_POINT_set_affine_coordinates_GF2m(group, point, x, y, ctx))
162 BN_CTX_free(new_ctx);
167 * Converts an EC_POINT to an octet string. If buf is NULL, the encoded
168 * length will be returned. If the length len of buf is smaller than required
169 * an error will be returned.
171 size_t ec_GF2m_simple_point2oct(const EC_GROUP *group, const EC_POINT *point,
172 point_conversion_form_t form,
173 unsigned char *buf, size_t len, BN_CTX *ctx)
176 BN_CTX *new_ctx = NULL;
179 size_t field_len, i, skip;
181 if ((form != POINT_CONVERSION_COMPRESSED)
182 && (form != POINT_CONVERSION_UNCOMPRESSED)
183 && (form != POINT_CONVERSION_HYBRID)) {
184 ECerr(EC_F_EC_GF2M_SIMPLE_POINT2OCT, EC_R_INVALID_FORM);
188 if (EC_POINT_is_at_infinity(group, point)) {
189 /* encodes to a single 0 octet */
192 ECerr(EC_F_EC_GF2M_SIMPLE_POINT2OCT, EC_R_BUFFER_TOO_SMALL);
200 /* ret := required output buffer length */
201 field_len = (EC_GROUP_get_degree(group) + 7) / 8;
204 POINT_CONVERSION_COMPRESSED) ? 1 + field_len : 1 + 2 * field_len;
206 /* if 'buf' is NULL, just return required length */
209 ECerr(EC_F_EC_GF2M_SIMPLE_POINT2OCT, EC_R_BUFFER_TOO_SMALL);
214 ctx = new_ctx = BN_CTX_new();
223 yxi = BN_CTX_get(ctx);
227 if (!EC_POINT_get_affine_coordinates_GF2m(group, point, x, y, ctx))
231 if ((form != POINT_CONVERSION_UNCOMPRESSED) && !BN_is_zero(x)) {
232 if (!group->meth->field_div(group, yxi, y, x, ctx))
240 skip = field_len - BN_num_bytes(x);
241 if (skip > field_len) {
242 ECerr(EC_F_EC_GF2M_SIMPLE_POINT2OCT, ERR_R_INTERNAL_ERROR);
249 skip = BN_bn2bin(x, buf + i);
251 if (i != 1 + field_len) {
252 ECerr(EC_F_EC_GF2M_SIMPLE_POINT2OCT, ERR_R_INTERNAL_ERROR);
256 if (form == POINT_CONVERSION_UNCOMPRESSED
257 || form == POINT_CONVERSION_HYBRID) {
258 skip = field_len - BN_num_bytes(y);
259 if (skip > field_len) {
260 ECerr(EC_F_EC_GF2M_SIMPLE_POINT2OCT, ERR_R_INTERNAL_ERROR);
267 skip = BN_bn2bin(y, buf + i);
272 ECerr(EC_F_EC_GF2M_SIMPLE_POINT2OCT, ERR_R_INTERNAL_ERROR);
279 BN_CTX_free(new_ctx);
285 BN_CTX_free(new_ctx);
290 * Converts an octet string representation to an EC_POINT. Note that the
291 * simple implementation only uses affine coordinates.
293 int ec_GF2m_simple_oct2point(const EC_GROUP *group, EC_POINT *point,
294 const unsigned char *buf, size_t len,
297 point_conversion_form_t form;
299 BN_CTX *new_ctx = NULL;
301 size_t field_len, enc_len;
305 ECerr(EC_F_EC_GF2M_SIMPLE_OCT2POINT, EC_R_BUFFER_TOO_SMALL);
311 if ((form != 0) && (form != POINT_CONVERSION_COMPRESSED)
312 && (form != POINT_CONVERSION_UNCOMPRESSED)
313 && (form != POINT_CONVERSION_HYBRID)) {
314 ECerr(EC_F_EC_GF2M_SIMPLE_OCT2POINT, EC_R_INVALID_ENCODING);
317 if ((form == 0 || form == POINT_CONVERSION_UNCOMPRESSED) && y_bit) {
318 ECerr(EC_F_EC_GF2M_SIMPLE_OCT2POINT, EC_R_INVALID_ENCODING);
324 ECerr(EC_F_EC_GF2M_SIMPLE_OCT2POINT, EC_R_INVALID_ENCODING);
328 return EC_POINT_set_to_infinity(group, point);
331 field_len = (EC_GROUP_get_degree(group) + 7) / 8;
334 POINT_CONVERSION_COMPRESSED) ? 1 + field_len : 1 + 2 * field_len;
336 if (len != enc_len) {
337 ECerr(EC_F_EC_GF2M_SIMPLE_OCT2POINT, EC_R_INVALID_ENCODING);
342 ctx = new_ctx = BN_CTX_new();
350 yxi = BN_CTX_get(ctx);
354 if (!BN_bin2bn(buf + 1, field_len, x))
356 if (BN_ucmp(x, group->field) >= 0) {
357 ECerr(EC_F_EC_GF2M_SIMPLE_OCT2POINT, EC_R_INVALID_ENCODING);
361 if (form == POINT_CONVERSION_COMPRESSED) {
362 if (!EC_POINT_set_compressed_coordinates_GF2m
363 (group, point, x, y_bit, ctx))
366 if (!BN_bin2bn(buf + 1 + field_len, field_len, y))
368 if (BN_ucmp(y, group->field) >= 0) {
369 ECerr(EC_F_EC_GF2M_SIMPLE_OCT2POINT, EC_R_INVALID_ENCODING);
372 if (form == POINT_CONVERSION_HYBRID) {
373 if (!group->meth->field_div(group, yxi, y, x, ctx))
375 if (y_bit != BN_is_odd(yxi)) {
376 ECerr(EC_F_EC_GF2M_SIMPLE_OCT2POINT, EC_R_INVALID_ENCODING);
381 if (!EC_POINT_set_affine_coordinates_GF2m(group, point, x, y, ctx))
385 /* test required by X9.62 */
386 if (EC_POINT_is_on_curve(group, point, ctx) <= 0) {
387 ECerr(EC_F_EC_GF2M_SIMPLE_OCT2POINT, EC_R_POINT_IS_NOT_ON_CURVE);
395 BN_CTX_free(new_ctx);