1 /* 2 * ***** BEGIN LICENSE BLOCK ***** 3 * Version: MPL 1.1/GPL 2.0/LGPL 2.1 4 * 5 * The contents of this file are subject to the Mozilla Public License Version 6 * 1.1 (the "License"); you may not use this file except in compliance with 7 * the License. You may obtain a copy of the License at 8 * http://www.mozilla.org/MPL/ 9 * 10 * Software distributed under the License is distributed on an "AS IS" basis, 11 * WITHOUT WARRANTY OF ANY KIND, either express or implied. See the License 12 * for the specific language governing rights and limitations under the 13 * License. 14 * 15 * The Original Code is the elliptic curve math library for prime field curves. 16 * 17 * The Initial Developer of the Original Code is 18 * Sun Microsystems, Inc. 19 * Portions created by the Initial Developer are Copyright (C) 2003 20 * the Initial Developer. All Rights Reserved. 21 * 22 * Contributor(s): 23 * Sheueling Chang-Shantz <sheueling.chang@sun.com>, 24 * Stephen Fung <fungstep@hotmail.com>, and 25 * Douglas Stebila <douglas@stebila.ca>, Sun Microsystems Laboratories. 26 * Bodo Moeller <moeller@cdc.informatik.tu-darmstadt.de>, 27 * Nils Larsch <nla@trustcenter.de>, and 28 * Lenka Fibikova <fibikova@exp-math.uni-essen.de>, the OpenSSL Project 29 * 30 * Alternatively, the contents of this file may be used under the terms of 31 * either the GNU General Public License Version 2 or later (the "GPL"), or 32 * the GNU Lesser General Public License Version 2.1 or later (the "LGPL"), 33 * in which case the provisions of the GPL or the LGPL are applicable instead 34 * of those above. If you wish to allow use of your version of this file only 35 * under the terms of either the GPL or the LGPL, and not to allow others to 36 * use your version of this file under the terms of the MPL, indicate your 37 * decision by deleting the provisions above and replace them with the notice 38 * and other provisions required by the GPL or the LGPL. If you do not delete 39 * the provisions above, a recipient may use your version of this file under 40 * the terms of any one of the MPL, the GPL or the LGPL. 41 * 42 * ***** END LICENSE BLOCK ***** */ 43 /* 44 * Copyright 2007 Sun Microsystems, Inc. All rights reserved. 45 * Use is subject to license terms. 46 * 47 * Sun elects to use this software under the MPL license. 48 */ 49 50 #pragma ident "%Z%%M% %I% %E% SMI" 51 52 #include "ecp.h" 53 #include "mplogic.h" 54 #ifndef _KERNEL 55 #include <stdlib.h> 56 #endif 57 58 /* Checks if point P(px, py) is at infinity. Uses affine coordinates. */ 59 mp_err 60 ec_GFp_pt_is_inf_aff(const mp_int *px, const mp_int *py) 61 { 62 63 if ((mp_cmp_z(px) == 0) && (mp_cmp_z(py) == 0)) { 64 return MP_YES; 65 } else { 66 return MP_NO; 67 } 68 69 } 70 71 /* Sets P(px, py) to be the point at infinity. Uses affine coordinates. */ 72 mp_err 73 ec_GFp_pt_set_inf_aff(mp_int *px, mp_int *py) 74 { 75 mp_zero(px); 76 mp_zero(py); 77 return MP_OKAY; 78 } 79 80 /* Computes R = P + Q based on IEEE P1363 A.10.1. Elliptic curve points P, 81 * Q, and R can all be identical. Uses affine coordinates. Assumes input 82 * is already field-encoded using field_enc, and returns output that is 83 * still field-encoded. */ 84 mp_err 85 ec_GFp_pt_add_aff(const mp_int *px, const mp_int *py, const mp_int *qx, 86 const mp_int *qy, mp_int *rx, mp_int *ry, 87 const ECGroup *group) 88 { 89 mp_err res = MP_OKAY; 90 mp_int lambda, temp, tempx, tempy; 91 92 MP_DIGITS(&lambda) = 0; 93 MP_DIGITS(&temp) = 0; 94 MP_DIGITS(&tempx) = 0; 95 MP_DIGITS(&tempy) = 0; 96 MP_CHECKOK(mp_init(&lambda, FLAG(px))); 97 MP_CHECKOK(mp_init(&temp, FLAG(px))); 98 MP_CHECKOK(mp_init(&tempx, FLAG(px))); 99 MP_CHECKOK(mp_init(&tempy, FLAG(px))); 100 /* if P = inf, then R = Q */ 101 if (ec_GFp_pt_is_inf_aff(px, py) == 0) { 102 MP_CHECKOK(mp_copy(qx, rx)); 103 MP_CHECKOK(mp_copy(qy, ry)); 104 res = MP_OKAY; 105 goto CLEANUP; 106 } 107 /* if Q = inf, then R = P */ 108 if (ec_GFp_pt_is_inf_aff(qx, qy) == 0) { 109 MP_CHECKOK(mp_copy(px, rx)); 110 MP_CHECKOK(mp_copy(py, ry)); 111 res = MP_OKAY; 112 goto CLEANUP; 113 } 114 /* if px != qx, then lambda = (py-qy) / (px-qx) */ 115 if (mp_cmp(px, qx) != 0) { 116 MP_CHECKOK(group->meth->field_sub(py, qy, &tempy, group->meth)); 117 MP_CHECKOK(group->meth->field_sub(px, qx, &tempx, group->meth)); 118 MP_CHECKOK(group->meth-> 119 field_div(&tempy, &tempx, &lambda, group->meth)); 120 } else { 121 /* if py != qy or qy = 0, then R = inf */ 122 if (((mp_cmp(py, qy) != 0)) || (mp_cmp_z(qy) == 0)) { 123 mp_zero(rx); 124 mp_zero(ry); 125 res = MP_OKAY; 126 goto CLEANUP; 127 } 128 /* lambda = (3qx^2+a) / (2qy) */ 129 MP_CHECKOK(group->meth->field_sqr(qx, &tempx, group->meth)); 130 MP_CHECKOK(mp_set_int(&temp, 3)); 131 if (group->meth->field_enc) { 132 MP_CHECKOK(group->meth->field_enc(&temp, &temp, group->meth)); 133 } 134 MP_CHECKOK(group->meth-> 135 field_mul(&tempx, &temp, &tempx, group->meth)); 136 MP_CHECKOK(group->meth-> 137 field_add(&tempx, &group->curvea, &tempx, group->meth)); 138 MP_CHECKOK(mp_set_int(&temp, 2)); 139 if (group->meth->field_enc) { 140 MP_CHECKOK(group->meth->field_enc(&temp, &temp, group->meth)); 141 } 142 MP_CHECKOK(group->meth->field_mul(qy, &temp, &tempy, group->meth)); 143 MP_CHECKOK(group->meth-> 144 field_div(&tempx, &tempy, &lambda, group->meth)); 145 } 146 /* rx = lambda^2 - px - qx */ 147 MP_CHECKOK(group->meth->field_sqr(&lambda, &tempx, group->meth)); 148 MP_CHECKOK(group->meth->field_sub(&tempx, px, &tempx, group->meth)); 149 MP_CHECKOK(group->meth->field_sub(&tempx, qx, &tempx, group->meth)); 150 /* ry = (x1-x2) * lambda - y1 */ 151 MP_CHECKOK(group->meth->field_sub(qx, &tempx, &tempy, group->meth)); 152 MP_CHECKOK(group->meth-> 153 field_mul(&tempy, &lambda, &tempy, group->meth)); 154 MP_CHECKOK(group->meth->field_sub(&tempy, qy, &tempy, group->meth)); 155 MP_CHECKOK(mp_copy(&tempx, rx)); 156 MP_CHECKOK(mp_copy(&tempy, ry)); 157 158 CLEANUP: 159 mp_clear(&lambda); 160 mp_clear(&temp); 161 mp_clear(&tempx); 162 mp_clear(&tempy); 163 return res; 164 } 165 166 /* Computes R = P - Q. Elliptic curve points P, Q, and R can all be 167 * identical. Uses affine coordinates. Assumes input is already 168 * field-encoded using field_enc, and returns output that is still 169 * field-encoded. */ 170 mp_err 171 ec_GFp_pt_sub_aff(const mp_int *px, const mp_int *py, const mp_int *qx, 172 const mp_int *qy, mp_int *rx, mp_int *ry, 173 const ECGroup *group) 174 { 175 mp_err res = MP_OKAY; 176 mp_int nqy; 177 178 MP_DIGITS(&nqy) = 0; 179 MP_CHECKOK(mp_init(&nqy, FLAG(px))); 180 /* nqy = -qy */ 181 MP_CHECKOK(group->meth->field_neg(qy, &nqy, group->meth)); 182 res = group->point_add(px, py, qx, &nqy, rx, ry, group); 183 CLEANUP: 184 mp_clear(&nqy); 185 return res; 186 } 187 188 /* Computes R = 2P. Elliptic curve points P and R can be identical. Uses 189 * affine coordinates. Assumes input is already field-encoded using 190 * field_enc, and returns output that is still field-encoded. */ 191 mp_err 192 ec_GFp_pt_dbl_aff(const mp_int *px, const mp_int *py, mp_int *rx, 193 mp_int *ry, const ECGroup *group) 194 { 195 return ec_GFp_pt_add_aff(px, py, px, py, rx, ry, group); 196 } 197 198 /* by default, this routine is unused and thus doesn't need to be compiled */ 199 #ifdef ECL_ENABLE_GFP_PT_MUL_AFF 200 /* Computes R = nP based on IEEE P1363 A.10.3. Elliptic curve points P and 201 * R can be identical. Uses affine coordinates. Assumes input is already 202 * field-encoded using field_enc, and returns output that is still 203 * field-encoded. */ 204 mp_err 205 ec_GFp_pt_mul_aff(const mp_int *n, const mp_int *px, const mp_int *py, 206 mp_int *rx, mp_int *ry, const ECGroup *group) 207 { 208 mp_err res = MP_OKAY; 209 mp_int k, k3, qx, qy, sx, sy; 210 int b1, b3, i, l; 211 212 MP_DIGITS(&k) = 0; 213 MP_DIGITS(&k3) = 0; 214 MP_DIGITS(&qx) = 0; 215 MP_DIGITS(&qy) = 0; 216 MP_DIGITS(&sx) = 0; 217 MP_DIGITS(&sy) = 0; 218 MP_CHECKOK(mp_init(&k)); 219 MP_CHECKOK(mp_init(&k3)); 220 MP_CHECKOK(mp_init(&qx)); 221 MP_CHECKOK(mp_init(&qy)); 222 MP_CHECKOK(mp_init(&sx)); 223 MP_CHECKOK(mp_init(&sy)); 224 225 /* if n = 0 then r = inf */ 226 if (mp_cmp_z(n) == 0) { 227 mp_zero(rx); 228 mp_zero(ry); 229 res = MP_OKAY; 230 goto CLEANUP; 231 } 232 /* Q = P, k = n */ 233 MP_CHECKOK(mp_copy(px, &qx)); 234 MP_CHECKOK(mp_copy(py, &qy)); 235 MP_CHECKOK(mp_copy(n, &k)); 236 /* if n < 0 then Q = -Q, k = -k */ 237 if (mp_cmp_z(n) < 0) { 238 MP_CHECKOK(group->meth->field_neg(&qy, &qy, group->meth)); 239 MP_CHECKOK(mp_neg(&k, &k)); 240 } 241 #ifdef ECL_DEBUG /* basic double and add method */ 242 l = mpl_significant_bits(&k) - 1; 243 MP_CHECKOK(mp_copy(&qx, &sx)); 244 MP_CHECKOK(mp_copy(&qy, &sy)); 245 for (i = l - 1; i >= 0; i--) { 246 /* S = 2S */ 247 MP_CHECKOK(group->point_dbl(&sx, &sy, &sx, &sy, group)); 248 /* if k_i = 1, then S = S + Q */ 249 if (mpl_get_bit(&k, i) != 0) { 250 MP_CHECKOK(group-> 251 point_add(&sx, &sy, &qx, &qy, &sx, &sy, group)); 252 } 253 } 254 #else /* double and add/subtract method from 255 * standard */ 256 /* k3 = 3 * k */ 257 MP_CHECKOK(mp_set_int(&k3, 3)); 258 MP_CHECKOK(mp_mul(&k, &k3, &k3)); 259 /* S = Q */ 260 MP_CHECKOK(mp_copy(&qx, &sx)); 261 MP_CHECKOK(mp_copy(&qy, &sy)); 262 /* l = index of high order bit in binary representation of 3*k */ 263 l = mpl_significant_bits(&k3) - 1; 264 /* for i = l-1 downto 1 */ 265 for (i = l - 1; i >= 1; i--) { 266 /* S = 2S */ 267 MP_CHECKOK(group->point_dbl(&sx, &sy, &sx, &sy, group)); 268 b3 = MP_GET_BIT(&k3, i); 269 b1 = MP_GET_BIT(&k, i); 270 /* if k3_i = 1 and k_i = 0, then S = S + Q */ 271 if ((b3 == 1) && (b1 == 0)) { 272 MP_CHECKOK(group-> 273 point_add(&sx, &sy, &qx, &qy, &sx, &sy, group)); 274 /* if k3_i = 0 and k_i = 1, then S = S - Q */ 275 } else if ((b3 == 0) && (b1 == 1)) { 276 MP_CHECKOK(group-> 277 point_sub(&sx, &sy, &qx, &qy, &sx, &sy, group)); 278 } 279 } 280 #endif 281 /* output S */ 282 MP_CHECKOK(mp_copy(&sx, rx)); 283 MP_CHECKOK(mp_copy(&sy, ry)); 284 285 CLEANUP: 286 mp_clear(&k); 287 mp_clear(&k3); 288 mp_clear(&qx); 289 mp_clear(&qy); 290 mp_clear(&sx); 291 mp_clear(&sy); 292 return res; 293 } 294 #endif 295 296 /* Validates a point on a GFp curve. */ 297 mp_err 298 ec_GFp_validate_point(const mp_int *px, const mp_int *py, const ECGroup *group) 299 { 300 mp_err res = MP_NO; 301 mp_int accl, accr, tmp, pxt, pyt; 302 303 MP_DIGITS(&accl) = 0; 304 MP_DIGITS(&accr) = 0; 305 MP_DIGITS(&tmp) = 0; 306 MP_DIGITS(&pxt) = 0; 307 MP_DIGITS(&pyt) = 0; 308 MP_CHECKOK(mp_init(&accl, FLAG(px))); 309 MP_CHECKOK(mp_init(&accr, FLAG(px))); 310 MP_CHECKOK(mp_init(&tmp, FLAG(px))); 311 MP_CHECKOK(mp_init(&pxt, FLAG(px))); 312 MP_CHECKOK(mp_init(&pyt, FLAG(px))); 313 314 /* 1: Verify that publicValue is not the point at infinity */ 315 if (ec_GFp_pt_is_inf_aff(px, py) == MP_YES) { 316 res = MP_NO; 317 goto CLEANUP; 318 } 319 /* 2: Verify that the coordinates of publicValue are elements 320 * of the field. 321 */ 322 if ((MP_SIGN(px) == MP_NEG) || (mp_cmp(px, &group->meth->irr) >= 0) || 323 (MP_SIGN(py) == MP_NEG) || (mp_cmp(py, &group->meth->irr) >= 0)) { 324 res = MP_NO; 325 goto CLEANUP; 326 } 327 /* 3: Verify that publicValue is on the curve. */ 328 if (group->meth->field_enc) { 329 group->meth->field_enc(px, &pxt, group->meth); 330 group->meth->field_enc(py, &pyt, group->meth); 331 } else { 332 mp_copy(px, &pxt); 333 mp_copy(py, &pyt); 334 } 335 /* left-hand side: y^2 */ 336 MP_CHECKOK( group->meth->field_sqr(&pyt, &accl, group->meth) ); 337 /* right-hand side: x^3 + a*x + b */ 338 MP_CHECKOK( group->meth->field_sqr(&pxt, &tmp, group->meth) ); 339 MP_CHECKOK( group->meth->field_mul(&pxt, &tmp, &accr, group->meth) ); 340 MP_CHECKOK( group->meth->field_mul(&group->curvea, &pxt, &tmp, group->meth) ); 341 MP_CHECKOK( group->meth->field_add(&tmp, &accr, &accr, group->meth) ); 342 MP_CHECKOK( group->meth->field_add(&accr, &group->curveb, &accr, group->meth) ); 343 /* check LHS - RHS == 0 */ 344 MP_CHECKOK( group->meth->field_sub(&accl, &accr, &accr, group->meth) ); 345 if (mp_cmp_z(&accr) != 0) { 346 res = MP_NO; 347 goto CLEANUP; 348 } 349 /* 4: Verify that the order of the curve times the publicValue 350 * is the point at infinity. 351 */ 352 MP_CHECKOK( ECPoint_mul(group, &group->order, px, py, &pxt, &pyt) ); 353 if (ec_GFp_pt_is_inf_aff(&pxt, &pyt) != MP_YES) { 354 res = MP_NO; 355 goto CLEANUP; 356 } 357 358 res = MP_YES; 359 360 CLEANUP: 361 mp_clear(&accl); 362 mp_clear(&accr); 363 mp_clear(&tmp); 364 mp_clear(&pxt); 365 mp_clear(&pyt); 366 return res; 367 } 368