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