1 /* Originally written by Bodo Moeller and Nils Larsch for the OpenSSL project. 2 * ==================================================================== 3 * Copyright (c) 1998-2005 The OpenSSL Project. All rights reserved. 4 * 5 * Redistribution and use in source and binary forms, with or without 6 * modification, are permitted provided that the following conditions 7 * are met: 8 * 9 * 1. Redistributions of source code must retain the above copyright 10 * notice, this list of conditions and the following disclaimer. 11 * 12 * 2. Redistributions in binary form must reproduce the above copyright 13 * notice, this list of conditions and the following disclaimer in 14 * the documentation and/or other materials provided with the 15 * distribution. 16 * 17 * 3. All advertising materials mentioning features or use of this 18 * software must display the following acknowledgment: 19 * "This product includes software developed by the OpenSSL Project 20 * for use in the OpenSSL Toolkit. (http://www.openssl.org/)" 21 * 22 * 4. The names "OpenSSL Toolkit" and "OpenSSL Project" must not be used to 23 * endorse or promote products derived from this software without 24 * prior written permission. For written permission, please contact 25 * openssl-core (at) openssl.org. 26 * 27 * 5. Products derived from this software may not be called "OpenSSL" 28 * nor may "OpenSSL" appear in their names without prior written 29 * permission of the OpenSSL Project. 30 * 31 * 6. Redistributions of any form whatsoever must retain the following 32 * acknowledgment: 33 * "This product includes software developed by the OpenSSL Project 34 * for use in the OpenSSL Toolkit (http://www.openssl.org/)" 35 * 36 * THIS SOFTWARE IS PROVIDED BY THE OpenSSL PROJECT ``AS IS'' AND ANY 37 * EXPRESSED OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 38 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR 39 * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE OpenSSL PROJECT OR 40 * ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 41 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT 42 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; 43 * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 44 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, 45 * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) 46 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED 47 * OF THE POSSIBILITY OF SUCH DAMAGE. 48 * ==================================================================== 49 * 50 * This product includes cryptographic software written by Eric Young 51 * (eay (at) cryptsoft.com). This product includes software written by Tim 52 * Hudson (tjh (at) cryptsoft.com). 53 * 54 */ 55 /* ==================================================================== 56 * Copyright 2002 Sun Microsystems, Inc. ALL RIGHTS RESERVED. 57 * 58 * Portions of the attached software ("Contribution") are developed by 59 * SUN MICROSYSTEMS, INC., and are contributed to the OpenSSL project. 60 * 61 * The Contribution is licensed pursuant to the OpenSSL open source 62 * license provided above. 63 * 64 * The elliptic curve binary polynomial software is originally written by 65 * Sheueling Chang Shantz and Douglas Stebila of Sun Microsystems 66 * Laboratories. */ 67 68 #include <openssl/ec.h> 69 70 #include <openssl/bn.h> 71 #include <openssl/err.h> 72 #include <openssl/mem.h> 73 74 #include "../bn/internal.h" 75 #include "../delocate.h" 76 #include "internal.h" 77 78 79 int ec_GFp_mont_group_init(EC_GROUP *group) { 80 int ok; 81 82 ok = ec_GFp_simple_group_init(group); 83 group->mont = NULL; 84 return ok; 85 } 86 87 void ec_GFp_mont_group_finish(EC_GROUP *group) { 88 BN_MONT_CTX_free(group->mont); 89 group->mont = NULL; 90 ec_GFp_simple_group_finish(group); 91 } 92 93 int ec_GFp_mont_group_copy(EC_GROUP *dest, const EC_GROUP *src) { 94 BN_MONT_CTX_free(dest->mont); 95 dest->mont = NULL; 96 97 if (!ec_GFp_simple_group_copy(dest, src)) { 98 return 0; 99 } 100 101 if (src->mont != NULL) { 102 dest->mont = BN_MONT_CTX_new(); 103 if (dest->mont == NULL) { 104 return 0; 105 } 106 if (!BN_MONT_CTX_copy(dest->mont, src->mont)) { 107 goto err; 108 } 109 } 110 111 return 1; 112 113 err: 114 BN_MONT_CTX_free(dest->mont); 115 dest->mont = NULL; 116 return 0; 117 } 118 119 int ec_GFp_mont_group_set_curve(EC_GROUP *group, const BIGNUM *p, 120 const BIGNUM *a, const BIGNUM *b, BN_CTX *ctx) { 121 BN_CTX *new_ctx = NULL; 122 BN_MONT_CTX *mont = NULL; 123 int ret = 0; 124 125 BN_MONT_CTX_free(group->mont); 126 group->mont = NULL; 127 128 if (ctx == NULL) { 129 ctx = new_ctx = BN_CTX_new(); 130 if (ctx == NULL) { 131 return 0; 132 } 133 } 134 135 mont = BN_MONT_CTX_new(); 136 if (mont == NULL) { 137 goto err; 138 } 139 if (!BN_MONT_CTX_set(mont, p, ctx)) { 140 OPENSSL_PUT_ERROR(EC, ERR_R_BN_LIB); 141 goto err; 142 } 143 144 group->mont = mont; 145 mont = NULL; 146 147 ret = ec_GFp_simple_group_set_curve(group, p, a, b, ctx); 148 149 if (!ret) { 150 BN_MONT_CTX_free(group->mont); 151 group->mont = NULL; 152 } 153 154 err: 155 BN_CTX_free(new_ctx); 156 BN_MONT_CTX_free(mont); 157 return ret; 158 } 159 160 int ec_GFp_mont_field_mul(const EC_GROUP *group, BIGNUM *r, const BIGNUM *a, 161 const BIGNUM *b, BN_CTX *ctx) { 162 if (group->mont == NULL) { 163 OPENSSL_PUT_ERROR(EC, EC_R_NOT_INITIALIZED); 164 return 0; 165 } 166 167 return BN_mod_mul_montgomery(r, a, b, group->mont, ctx); 168 } 169 170 int ec_GFp_mont_field_sqr(const EC_GROUP *group, BIGNUM *r, const BIGNUM *a, 171 BN_CTX *ctx) { 172 if (group->mont == NULL) { 173 OPENSSL_PUT_ERROR(EC, EC_R_NOT_INITIALIZED); 174 return 0; 175 } 176 177 return BN_mod_mul_montgomery(r, a, a, group->mont, ctx); 178 } 179 180 int ec_GFp_mont_field_encode(const EC_GROUP *group, BIGNUM *r, const BIGNUM *a, 181 BN_CTX *ctx) { 182 if (group->mont == NULL) { 183 OPENSSL_PUT_ERROR(EC, EC_R_NOT_INITIALIZED); 184 return 0; 185 } 186 187 return BN_to_montgomery(r, a, group->mont, ctx); 188 } 189 190 int ec_GFp_mont_field_decode(const EC_GROUP *group, BIGNUM *r, const BIGNUM *a, 191 BN_CTX *ctx) { 192 if (group->mont == NULL) { 193 OPENSSL_PUT_ERROR(EC, EC_R_NOT_INITIALIZED); 194 return 0; 195 } 196 197 return BN_from_montgomery(r, a, group->mont, ctx); 198 } 199 200 static int ec_GFp_mont_point_get_affine_coordinates(const EC_GROUP *group, 201 const EC_POINT *point, 202 BIGNUM *x, BIGNUM *y, 203 BN_CTX *ctx) { 204 if (EC_POINT_is_at_infinity(group, point)) { 205 OPENSSL_PUT_ERROR(EC, EC_R_POINT_AT_INFINITY); 206 return 0; 207 } 208 209 BN_CTX *new_ctx = NULL; 210 if (ctx == NULL) { 211 ctx = new_ctx = BN_CTX_new(); 212 if (ctx == NULL) { 213 return 0; 214 } 215 } 216 217 int ret = 0; 218 219 BN_CTX_start(ctx); 220 221 if (BN_cmp(&point->Z, &group->one) == 0) { 222 /* |point| is already affine. */ 223 if (x != NULL && !BN_from_montgomery(x, &point->X, group->mont, ctx)) { 224 goto err; 225 } 226 if (y != NULL && !BN_from_montgomery(y, &point->Y, group->mont, ctx)) { 227 goto err; 228 } 229 } else { 230 /* transform (X, Y, Z) into (x, y) := (X/Z^2, Y/Z^3) */ 231 232 BIGNUM *Z_1 = BN_CTX_get(ctx); 233 BIGNUM *Z_2 = BN_CTX_get(ctx); 234 BIGNUM *Z_3 = BN_CTX_get(ctx); 235 if (Z_1 == NULL || 236 Z_2 == NULL || 237 Z_3 == NULL) { 238 goto err; 239 } 240 241 /* The straightforward way to calculate the inverse of a Montgomery-encoded 242 * value where the result is Montgomery-encoded is: 243 * 244 * |BN_from_montgomery| + invert + |BN_to_montgomery|. 245 * 246 * This is equivalent, but more efficient, because |BN_from_montgomery| 247 * is more efficient (at least in theory) than |BN_to_montgomery|, since it 248 * doesn't have to do the multiplication before the reduction. 249 * 250 * Use Fermat's Little Theorem instead of |BN_mod_inverse_odd| since this 251 * inversion may be done as the final step of private key operations. 252 * Unfortunately, this is suboptimal for ECDSA verification. */ 253 if (!BN_from_montgomery(Z_1, &point->Z, group->mont, ctx) || 254 !BN_from_montgomery(Z_1, Z_1, group->mont, ctx) || 255 !bn_mod_inverse_prime(Z_1, Z_1, &group->field, ctx, group->mont)) { 256 goto err; 257 } 258 259 if (!BN_mod_mul_montgomery(Z_2, Z_1, Z_1, group->mont, ctx)) { 260 goto err; 261 } 262 263 /* Instead of using |BN_from_montgomery| to convert the |x| coordinate 264 * and then calling |BN_from_montgomery| again to convert the |y| 265 * coordinate below, convert the common factor |Z_2| once now, saving one 266 * reduction. */ 267 if (!BN_from_montgomery(Z_2, Z_2, group->mont, ctx)) { 268 goto err; 269 } 270 271 if (x != NULL) { 272 if (!BN_mod_mul_montgomery(x, &point->X, Z_2, group->mont, ctx)) { 273 goto err; 274 } 275 } 276 277 if (y != NULL) { 278 if (!BN_mod_mul_montgomery(Z_3, Z_2, Z_1, group->mont, ctx) || 279 !BN_mod_mul_montgomery(y, &point->Y, Z_3, group->mont, ctx)) { 280 goto err; 281 } 282 } 283 } 284 285 ret = 1; 286 287 err: 288 BN_CTX_end(ctx); 289 BN_CTX_free(new_ctx); 290 return ret; 291 } 292 293 DEFINE_METHOD_FUNCTION(EC_METHOD, EC_GFp_mont_method) { 294 out->group_init = ec_GFp_mont_group_init; 295 out->group_finish = ec_GFp_mont_group_finish; 296 out->group_copy = ec_GFp_mont_group_copy; 297 out->group_set_curve = ec_GFp_mont_group_set_curve; 298 out->point_get_affine_coordinates = ec_GFp_mont_point_get_affine_coordinates; 299 out->mul = ec_wNAF_mul /* XXX: Not constant time. */; 300 out->field_mul = ec_GFp_mont_field_mul; 301 out->field_sqr = ec_GFp_mont_field_sqr; 302 out->field_encode = ec_GFp_mont_field_encode; 303 out->field_decode = ec_GFp_mont_field_decode; 304 } 305
