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 "internal.h" 76 77 78 int ec_GFp_mont_group_init(EC_GROUP *group) { 79 int ok; 80 81 ok = ec_GFp_simple_group_init(group); 82 group->mont = NULL; 83 return ok; 84 } 85 86 void ec_GFp_mont_group_finish(EC_GROUP *group) { 87 BN_MONT_CTX_free(group->mont); 88 group->mont = NULL; 89 ec_GFp_simple_group_finish(group); 90 } 91 92 int ec_GFp_mont_group_copy(EC_GROUP *dest, const EC_GROUP *src) { 93 BN_MONT_CTX_free(dest->mont); 94 dest->mont = NULL; 95 96 if (!ec_GFp_simple_group_copy(dest, src)) { 97 return 0; 98 } 99 100 if (src->mont != NULL) { 101 dest->mont = BN_MONT_CTX_new(); 102 if (dest->mont == NULL) { 103 return 0; 104 } 105 if (!BN_MONT_CTX_copy(dest->mont, src->mont)) { 106 goto err; 107 } 108 } 109 110 return 1; 111 112 err: 113 BN_MONT_CTX_free(dest->mont); 114 dest->mont = NULL; 115 return 0; 116 } 117 118 int ec_GFp_mont_group_set_curve(EC_GROUP *group, const BIGNUM *p, 119 const BIGNUM *a, const BIGNUM *b, BN_CTX *ctx) { 120 BN_CTX *new_ctx = NULL; 121 BN_MONT_CTX *mont = NULL; 122 int ret = 0; 123 124 BN_MONT_CTX_free(group->mont); 125 group->mont = NULL; 126 127 if (ctx == NULL) { 128 ctx = new_ctx = BN_CTX_new(); 129 if (ctx == NULL) { 130 return 0; 131 } 132 } 133 134 mont = BN_MONT_CTX_new(); 135 if (mont == NULL) { 136 goto err; 137 } 138 if (!BN_MONT_CTX_set(mont, p, ctx)) { 139 OPENSSL_PUT_ERROR(EC, ERR_R_BN_LIB); 140 goto err; 141 } 142 143 group->mont = mont; 144 mont = NULL; 145 146 ret = ec_GFp_simple_group_set_curve(group, p, a, b, ctx); 147 148 if (!ret) { 149 BN_MONT_CTX_free(group->mont); 150 group->mont = NULL; 151 } 152 153 err: 154 BN_CTX_free(new_ctx); 155 BN_MONT_CTX_free(mont); 156 return ret; 157 } 158 159 int ec_GFp_mont_field_mul(const EC_GROUP *group, BIGNUM *r, const BIGNUM *a, 160 const BIGNUM *b, BN_CTX *ctx) { 161 if (group->mont == NULL) { 162 OPENSSL_PUT_ERROR(EC, EC_R_NOT_INITIALIZED); 163 return 0; 164 } 165 166 return BN_mod_mul_montgomery(r, a, b, group->mont, ctx); 167 } 168 169 int ec_GFp_mont_field_sqr(const EC_GROUP *group, BIGNUM *r, const BIGNUM *a, 170 BN_CTX *ctx) { 171 if (group->mont == NULL) { 172 OPENSSL_PUT_ERROR(EC, EC_R_NOT_INITIALIZED); 173 return 0; 174 } 175 176 return BN_mod_mul_montgomery(r, a, a, group->mont, ctx); 177 } 178 179 int ec_GFp_mont_field_encode(const EC_GROUP *group, BIGNUM *r, const BIGNUM *a, 180 BN_CTX *ctx) { 181 if (group->mont == NULL) { 182 OPENSSL_PUT_ERROR(EC, EC_R_NOT_INITIALIZED); 183 return 0; 184 } 185 186 return BN_to_montgomery(r, a, group->mont, ctx); 187 } 188 189 int ec_GFp_mont_field_decode(const EC_GROUP *group, BIGNUM *r, const BIGNUM *a, 190 BN_CTX *ctx) { 191 if (group->mont == NULL) { 192 OPENSSL_PUT_ERROR(EC, EC_R_NOT_INITIALIZED); 193 return 0; 194 } 195 196 return BN_from_montgomery(r, a, group->mont, ctx); 197 } 198 199 static int ec_GFp_mont_point_get_affine_coordinates(const EC_GROUP *group, 200 const EC_POINT *point, 201 BIGNUM *x, BIGNUM *y, 202 BN_CTX *ctx) { 203 if (EC_POINT_is_at_infinity(group, point)) { 204 OPENSSL_PUT_ERROR(EC, EC_R_POINT_AT_INFINITY); 205 return 0; 206 } 207 208 BN_CTX *new_ctx = NULL; 209 if (ctx == NULL) { 210 ctx = new_ctx = BN_CTX_new(); 211 if (ctx == NULL) { 212 return 0; 213 } 214 } 215 216 int ret = 0; 217 218 BN_CTX_start(ctx); 219 220 if (BN_cmp(&point->Z, &group->one) == 0) { 221 /* |point| is already affine. */ 222 if (x != NULL && !BN_from_montgomery(x, &point->X, group->mont, ctx)) { 223 goto err; 224 } 225 if (y != NULL && !BN_from_montgomery(y, &point->Y, group->mont, ctx)) { 226 goto err; 227 } 228 } else { 229 /* transform (X, Y, Z) into (x, y) := (X/Z^2, Y/Z^3) */ 230 231 BIGNUM *Z_1 = BN_CTX_get(ctx); 232 BIGNUM *Z_2 = BN_CTX_get(ctx); 233 BIGNUM *Z_3 = BN_CTX_get(ctx); 234 if (Z_1 == NULL || 235 Z_2 == NULL || 236 Z_3 == NULL) { 237 goto err; 238 } 239 240 /* The straightforward way to calculate the inverse of a Montgomery-encoded 241 * value where the result is Montgomery-encoded is: 242 * 243 * |BN_from_montgomery| + invert + |BN_to_montgomery|. 244 * 245 * This is equivalent, but more efficient, because |BN_from_montgomery| 246 * is more efficient (at least in theory) than |BN_to_montgomery|, since it 247 * doesn't have to do the multiplication before the reduction. 248 * 249 * Use Fermat's Little Theorem instead of |BN_mod_inverse_odd| since this 250 * inversion may be done as the final step of private key operations. 251 * Unfortunately, this is suboptimal for ECDSA verification. */ 252 if (!BN_from_montgomery(Z_1, &point->Z, group->mont, ctx) || 253 !BN_from_montgomery(Z_1, Z_1, group->mont, ctx) || 254 !bn_mod_inverse_prime(Z_1, Z_1, &group->field, ctx, group->mont)) { 255 goto err; 256 } 257 258 if (!BN_mod_mul_montgomery(Z_2, Z_1, Z_1, group->mont, ctx)) { 259 goto err; 260 } 261 262 /* Instead of using |BN_from_montgomery| to convert the |x| coordinate 263 * and then calling |BN_from_montgomery| again to convert the |y| 264 * coordinate below, convert the common factor |Z_2| once now, saving one 265 * reduction. */ 266 if (!BN_from_montgomery(Z_2, Z_2, group->mont, ctx)) { 267 goto err; 268 } 269 270 if (x != NULL) { 271 if (!BN_mod_mul_montgomery(x, &point->X, Z_2, group->mont, ctx)) { 272 goto err; 273 } 274 } 275 276 if (y != NULL) { 277 if (!BN_mod_mul_montgomery(Z_3, Z_2, Z_1, group->mont, ctx) || 278 !BN_mod_mul_montgomery(y, &point->Y, Z_3, group->mont, ctx)) { 279 goto err; 280 } 281 } 282 } 283 284 ret = 1; 285 286 err: 287 BN_CTX_end(ctx); 288 BN_CTX_free(new_ctx); 289 return ret; 290 } 291 292 const EC_METHOD EC_GFp_mont_method = { 293 ec_GFp_mont_group_init, 294 ec_GFp_mont_group_finish, 295 ec_GFp_mont_group_copy, 296 ec_GFp_mont_group_set_curve, 297 ec_GFp_mont_point_get_affine_coordinates, 298 ec_wNAF_mul /* XXX: Not constant time. */, 299 ec_GFp_mont_field_mul, 300 ec_GFp_mont_field_sqr, 301 ec_GFp_mont_field_encode, 302 ec_GFp_mont_field_decode, 303 }; 304
