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