ecp_oct.c revision 1.6
1/* $OpenBSD: ecp_oct.c,v 1.6 2015/02/08 22:25:03 miod Exp $ */ 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 BN_CTX_free(new_ctx); 194 return ret; 195} 196 197 198size_t 199ec_GFp_simple_point2oct(const EC_GROUP * group, const EC_POINT * point, point_conversion_form_t form, 200 unsigned char *buf, size_t len, BN_CTX * ctx) 201{ 202 size_t ret; 203 BN_CTX *new_ctx = NULL; 204 int used_ctx = 0; 205 BIGNUM *x, *y; 206 size_t field_len, i, skip; 207 208 if ((form != POINT_CONVERSION_COMPRESSED) 209 && (form != POINT_CONVERSION_UNCOMPRESSED) 210 && (form != POINT_CONVERSION_HYBRID)) { 211 ECerr(EC_F_EC_GFP_SIMPLE_POINT2OCT, EC_R_INVALID_FORM); 212 goto err; 213 } 214 if (EC_POINT_is_at_infinity(group, point) > 0) { 215 /* encodes to a single 0 octet */ 216 if (buf != NULL) { 217 if (len < 1) { 218 ECerr(EC_F_EC_GFP_SIMPLE_POINT2OCT, EC_R_BUFFER_TOO_SMALL); 219 return 0; 220 } 221 buf[0] = 0; 222 } 223 return 1; 224 } 225 /* ret := required output buffer length */ 226 field_len = BN_num_bytes(&group->field); 227 ret = (form == POINT_CONVERSION_COMPRESSED) ? 1 + field_len : 1 + 2 * field_len; 228 229 /* if 'buf' is NULL, just return required length */ 230 if (buf != NULL) { 231 if (len < ret) { 232 ECerr(EC_F_EC_GFP_SIMPLE_POINT2OCT, EC_R_BUFFER_TOO_SMALL); 233 goto err; 234 } 235 if (ctx == NULL) { 236 ctx = new_ctx = BN_CTX_new(); 237 if (ctx == NULL) 238 return 0; 239 } 240 BN_CTX_start(ctx); 241 used_ctx = 1; 242 x = BN_CTX_get(ctx); 243 y = BN_CTX_get(ctx); 244 if (y == NULL) 245 goto err; 246 247 if (!EC_POINT_get_affine_coordinates_GFp(group, point, x, y, ctx)) 248 goto err; 249 250 if ((form == POINT_CONVERSION_COMPRESSED || form == POINT_CONVERSION_HYBRID) && BN_is_odd(y)) 251 buf[0] = form + 1; 252 else 253 buf[0] = form; 254 255 i = 1; 256 257 skip = field_len - BN_num_bytes(x); 258 if (skip > field_len) { 259 ECerr(EC_F_EC_GFP_SIMPLE_POINT2OCT, ERR_R_INTERNAL_ERROR); 260 goto err; 261 } 262 while (skip > 0) { 263 buf[i++] = 0; 264 skip--; 265 } 266 skip = BN_bn2bin(x, buf + i); 267 i += skip; 268 if (i != 1 + field_len) { 269 ECerr(EC_F_EC_GFP_SIMPLE_POINT2OCT, ERR_R_INTERNAL_ERROR); 270 goto err; 271 } 272 if (form == POINT_CONVERSION_UNCOMPRESSED || form == POINT_CONVERSION_HYBRID) { 273 skip = field_len - BN_num_bytes(y); 274 if (skip > field_len) { 275 ECerr(EC_F_EC_GFP_SIMPLE_POINT2OCT, ERR_R_INTERNAL_ERROR); 276 goto err; 277 } 278 while (skip > 0) { 279 buf[i++] = 0; 280 skip--; 281 } 282 skip = BN_bn2bin(y, buf + i); 283 i += skip; 284 } 285 if (i != ret) { 286 ECerr(EC_F_EC_GFP_SIMPLE_POINT2OCT, ERR_R_INTERNAL_ERROR); 287 goto err; 288 } 289 } 290 if (used_ctx) 291 BN_CTX_end(ctx); 292 BN_CTX_free(new_ctx); 293 return ret; 294 295err: 296 if (used_ctx) 297 BN_CTX_end(ctx); 298 BN_CTX_free(new_ctx); 299 return 0; 300} 301 302 303int 304ec_GFp_simple_oct2point(const EC_GROUP * group, EC_POINT * point, 305 const unsigned char *buf, size_t len, BN_CTX * ctx) 306{ 307 point_conversion_form_t form; 308 int y_bit; 309 BN_CTX *new_ctx = NULL; 310 BIGNUM *x, *y; 311 size_t field_len, enc_len; 312 int ret = 0; 313 314 if (len == 0) { 315 ECerr(EC_F_EC_GFP_SIMPLE_OCT2POINT, EC_R_BUFFER_TOO_SMALL); 316 return 0; 317 } 318 form = buf[0]; 319 y_bit = form & 1; 320 form = form & ~1U; 321 if ((form != 0) && (form != POINT_CONVERSION_COMPRESSED) 322 && (form != POINT_CONVERSION_UNCOMPRESSED) 323 && (form != POINT_CONVERSION_HYBRID)) { 324 ECerr(EC_F_EC_GFP_SIMPLE_OCT2POINT, EC_R_INVALID_ENCODING); 325 return 0; 326 } 327 if ((form == 0 || form == POINT_CONVERSION_UNCOMPRESSED) && y_bit) { 328 ECerr(EC_F_EC_GFP_SIMPLE_OCT2POINT, EC_R_INVALID_ENCODING); 329 return 0; 330 } 331 if (form == 0) { 332 if (len != 1) { 333 ECerr(EC_F_EC_GFP_SIMPLE_OCT2POINT, EC_R_INVALID_ENCODING); 334 return 0; 335 } 336 return EC_POINT_set_to_infinity(group, point); 337 } 338 field_len = BN_num_bytes(&group->field); 339 enc_len = (form == POINT_CONVERSION_COMPRESSED) ? 1 + field_len : 1 + 2 * field_len; 340 341 if (len != enc_len) { 342 ECerr(EC_F_EC_GFP_SIMPLE_OCT2POINT, EC_R_INVALID_ENCODING); 343 return 0; 344 } 345 if (ctx == NULL) { 346 ctx = new_ctx = BN_CTX_new(); 347 if (ctx == NULL) 348 return 0; 349 } 350 BN_CTX_start(ctx); 351 x = BN_CTX_get(ctx); 352 y = BN_CTX_get(ctx); 353 if (y == NULL) 354 goto err; 355 356 if (!BN_bin2bn(buf + 1, field_len, x)) 357 goto err; 358 if (BN_ucmp(x, &group->field) >= 0) { 359 ECerr(EC_F_EC_GFP_SIMPLE_OCT2POINT, EC_R_INVALID_ENCODING); 360 goto err; 361 } 362 if (form == POINT_CONVERSION_COMPRESSED) { 363 if (!EC_POINT_set_compressed_coordinates_GFp(group, point, x, y_bit, ctx)) 364 goto err; 365 } else { 366 if (!BN_bin2bn(buf + 1 + field_len, field_len, y)) 367 goto err; 368 if (BN_ucmp(y, &group->field) >= 0) { 369 ECerr(EC_F_EC_GFP_SIMPLE_OCT2POINT, EC_R_INVALID_ENCODING); 370 goto err; 371 } 372 if (form == POINT_CONVERSION_HYBRID) { 373 if (y_bit != BN_is_odd(y)) { 374 ECerr(EC_F_EC_GFP_SIMPLE_OCT2POINT, EC_R_INVALID_ENCODING); 375 goto err; 376 } 377 } 378 if (!EC_POINT_set_affine_coordinates_GFp(group, point, x, y, ctx)) 379 goto err; 380 } 381 382 /* test required by X9.62 */ 383 if (EC_POINT_is_on_curve(group, point, ctx) <= 0) { 384 ECerr(EC_F_EC_GFP_SIMPLE_OCT2POINT, EC_R_POINT_IS_NOT_ON_CURVE); 385 goto err; 386 } 387 ret = 1; 388 389err: 390 BN_CTX_end(ctx); 391 BN_CTX_free(new_ctx); 392 return ret; 393} 394