1/* 2 * Copyright (c) 2007, 2017, Oracle and/or its affiliates. All rights reserved. 3 * Use is subject to license terms. 4 * 5 * This library is free software; you can redistribute it and/or 6 * modify it under the terms of the GNU Lesser General Public 7 * License as published by the Free Software Foundation; either 8 * version 2.1 of the License, or (at your option) any later version. 9 * 10 * This library is distributed in the hope that it will be useful, 11 * but WITHOUT ANY WARRANTY; without even the implied warranty of 12 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 13 * Lesser General Public License for more details. 14 * 15 * You should have received a copy of the GNU Lesser General Public License 16 * along with this library; if not, write to the Free Software Foundation, 17 * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA. 18 * 19 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA 20 * or visit www.oracle.com if you need additional information or have any 21 * questions. 22 */ 23 24/* ********************************************************************* 25 * 26 * The Original Code is the elliptic curve math library for binary polynomial field curves. 27 * 28 * The Initial Developer of the Original Code is 29 * Sun Microsystems, Inc. 30 * Portions created by the Initial Developer are Copyright (C) 2003 31 * the Initial Developer. All Rights Reserved. 32 * 33 * Contributor(s): 34 * Douglas Stebila <douglas@stebila.ca>, Sun Microsystems Laboratories 35 * 36 * Last Modified Date from the Original Code: May 2017 37 *********************************************************************** */ 38 39#include "ec2.h" 40#include "mplogic.h" 41#include "mp_gf2m.h" 42#ifndef _KERNEL 43#include <stdlib.h> 44#endif 45 46/* Checks if point P(px, py) is at infinity. Uses affine coordinates. */ 47mp_err 48ec_GF2m_pt_is_inf_aff(const mp_int *px, const mp_int *py) 49{ 50 51 if ((mp_cmp_z(px) == 0) && (mp_cmp_z(py) == 0)) { 52 return MP_YES; 53 } else { 54 return MP_NO; 55 } 56 57} 58 59/* Sets P(px, py) to be the point at infinity. Uses affine coordinates. */ 60mp_err 61ec_GF2m_pt_set_inf_aff(mp_int *px, mp_int *py) 62{ 63 mp_zero(px); 64 mp_zero(py); 65 return MP_OKAY; 66} 67 68/* Computes R = P + Q based on IEEE P1363 A.10.2. Elliptic curve points P, 69 * Q, and R can all be identical. Uses affine coordinates. */ 70mp_err 71ec_GF2m_pt_add_aff(const mp_int *px, const mp_int *py, const mp_int *qx, 72 const mp_int *qy, mp_int *rx, mp_int *ry, 73 const ECGroup *group) 74{ 75 mp_err res = MP_OKAY; 76 mp_int lambda, tempx, tempy; 77 78 MP_DIGITS(&lambda) = 0; 79 MP_DIGITS(&tempx) = 0; 80 MP_DIGITS(&tempy) = 0; 81 MP_CHECKOK(mp_init(&lambda, FLAG(px))); 82 MP_CHECKOK(mp_init(&tempx, FLAG(px))); 83 MP_CHECKOK(mp_init(&tempy, FLAG(px))); 84 /* if P = inf, then R = Q */ 85 if (ec_GF2m_pt_is_inf_aff(px, py) == 0) { 86 MP_CHECKOK(mp_copy(qx, rx)); 87 MP_CHECKOK(mp_copy(qy, ry)); 88 res = MP_OKAY; 89 goto CLEANUP; 90 } 91 /* if Q = inf, then R = P */ 92 if (ec_GF2m_pt_is_inf_aff(qx, qy) == 0) { 93 MP_CHECKOK(mp_copy(px, rx)); 94 MP_CHECKOK(mp_copy(py, ry)); 95 res = MP_OKAY; 96 goto CLEANUP; 97 } 98 /* if px != qx, then lambda = (py+qy) / (px+qx), tempx = a + lambda^2 99 * + lambda + px + qx */ 100 if (mp_cmp(px, qx) != 0) { 101 MP_CHECKOK(group->meth->field_add(py, qy, &tempy, group->meth)); 102 MP_CHECKOK(group->meth->field_add(px, qx, &tempx, group->meth)); 103 MP_CHECKOK(group->meth-> 104 field_div(&tempy, &tempx, &lambda, group->meth)); 105 MP_CHECKOK(group->meth->field_sqr(&lambda, &tempx, group->meth)); 106 MP_CHECKOK(group->meth-> 107 field_add(&tempx, &lambda, &tempx, group->meth)); 108 MP_CHECKOK(group->meth-> 109 field_add(&tempx, &group->curvea, &tempx, group->meth)); 110 MP_CHECKOK(group->meth-> 111 field_add(&tempx, px, &tempx, group->meth)); 112 MP_CHECKOK(group->meth-> 113 field_add(&tempx, qx, &tempx, group->meth)); 114 } else { 115 /* if py != qy or qx = 0, then R = inf */ 116 if (((mp_cmp(py, qy) != 0)) || (mp_cmp_z(qx) == 0)) { 117 mp_zero(rx); 118 mp_zero(ry); 119 res = MP_OKAY; 120 goto CLEANUP; 121 } 122 /* lambda = qx + qy / qx */ 123 MP_CHECKOK(group->meth->field_div(qy, qx, &lambda, group->meth)); 124 MP_CHECKOK(group->meth-> 125 field_add(&lambda, qx, &lambda, group->meth)); 126 /* tempx = a + lambda^2 + lambda */ 127 MP_CHECKOK(group->meth->field_sqr(&lambda, &tempx, group->meth)); 128 MP_CHECKOK(group->meth-> 129 field_add(&tempx, &lambda, &tempx, group->meth)); 130 MP_CHECKOK(group->meth-> 131 field_add(&tempx, &group->curvea, &tempx, group->meth)); 132 } 133 /* ry = (qx + tempx) * lambda + tempx + qy */ 134 MP_CHECKOK(group->meth->field_add(qx, &tempx, &tempy, group->meth)); 135 MP_CHECKOK(group->meth-> 136 field_mul(&tempy, &lambda, &tempy, group->meth)); 137 MP_CHECKOK(group->meth-> 138 field_add(&tempy, &tempx, &tempy, group->meth)); 139 MP_CHECKOK(group->meth->field_add(&tempy, qy, ry, group->meth)); 140 /* rx = tempx */ 141 MP_CHECKOK(mp_copy(&tempx, rx)); 142 143 CLEANUP: 144 mp_clear(&lambda); 145 mp_clear(&tempx); 146 mp_clear(&tempy); 147 return res; 148} 149 150/* Computes R = P - Q. Elliptic curve points P, Q, and R can all be 151 * identical. Uses affine coordinates. */ 152mp_err 153ec_GF2m_pt_sub_aff(const mp_int *px, const mp_int *py, const mp_int *qx, 154 const mp_int *qy, mp_int *rx, mp_int *ry, 155 const ECGroup *group) 156{ 157 mp_err res = MP_OKAY; 158 mp_int nqy; 159 160 MP_DIGITS(&nqy) = 0; 161 MP_CHECKOK(mp_init(&nqy, FLAG(px))); 162 /* nqy = qx+qy */ 163 MP_CHECKOK(group->meth->field_add(qx, qy, &nqy, group->meth)); 164 MP_CHECKOK(group->point_add(px, py, qx, &nqy, rx, ry, group)); 165 CLEANUP: 166 mp_clear(&nqy); 167 return res; 168} 169 170/* Computes R = 2P. Elliptic curve points P and R can be identical. Uses 171 * affine coordinates. */ 172mp_err 173ec_GF2m_pt_dbl_aff(const mp_int *px, const mp_int *py, mp_int *rx, 174 mp_int *ry, const ECGroup *group) 175{ 176 return group->point_add(px, py, px, py, rx, ry, group); 177} 178 179/* by default, this routine is unused and thus doesn't need to be compiled */ 180#ifdef ECL_ENABLE_GF2M_PT_MUL_AFF 181/* Computes R = nP based on IEEE P1363 A.10.3. Elliptic curve points P and 182 * R can be identical. Uses affine coordinates. */ 183mp_err 184ec_GF2m_pt_mul_aff(const mp_int *n, const mp_int *px, const mp_int *py, 185 mp_int *rx, mp_int *ry, const ECGroup *group) 186{ 187 mp_err res = MP_OKAY; 188 mp_int k, k3, qx, qy, sx, sy; 189 int b1, b3, i, l; 190 191 MP_DIGITS(&k) = 0; 192 MP_DIGITS(&k3) = 0; 193 MP_DIGITS(&qx) = 0; 194 MP_DIGITS(&qy) = 0; 195 MP_DIGITS(&sx) = 0; 196 MP_DIGITS(&sy) = 0; 197 MP_CHECKOK(mp_init(&k)); 198 MP_CHECKOK(mp_init(&k3)); 199 MP_CHECKOK(mp_init(&qx)); 200 MP_CHECKOK(mp_init(&qy)); 201 MP_CHECKOK(mp_init(&sx)); 202 MP_CHECKOK(mp_init(&sy)); 203 204 /* if n = 0 then r = inf */ 205 if (mp_cmp_z(n) == 0) { 206 mp_zero(rx); 207 mp_zero(ry); 208 res = MP_OKAY; 209 goto CLEANUP; 210 } 211 /* Q = P, k = n */ 212 MP_CHECKOK(mp_copy(px, &qx)); 213 MP_CHECKOK(mp_copy(py, &qy)); 214 MP_CHECKOK(mp_copy(n, &k)); 215 /* if n < 0 then Q = -Q, k = -k */ 216 if (mp_cmp_z(n) < 0) { 217 MP_CHECKOK(group->meth->field_add(&qx, &qy, &qy, group->meth)); 218 MP_CHECKOK(mp_neg(&k, &k)); 219 } 220#ifdef ECL_DEBUG /* basic double and add method */ 221 l = mpl_significant_bits(&k) - 1; 222 MP_CHECKOK(mp_copy(&qx, &sx)); 223 MP_CHECKOK(mp_copy(&qy, &sy)); 224 for (i = l - 1; i >= 0; i--) { 225 /* S = 2S */ 226 MP_CHECKOK(group->point_dbl(&sx, &sy, &sx, &sy, group)); 227 /* if k_i = 1, then S = S + Q */ 228 if (mpl_get_bit(&k, i) != 0) { 229 MP_CHECKOK(group-> 230 point_add(&sx, &sy, &qx, &qy, &sx, &sy, group)); 231 } 232 } 233#else /* double and add/subtract method from 234 * standard */ 235 /* k3 = 3 * k */ 236 MP_CHECKOK(mp_set_int(&k3, 3)); 237 MP_CHECKOK(mp_mul(&k, &k3, &k3)); 238 /* S = Q */ 239 MP_CHECKOK(mp_copy(&qx, &sx)); 240 MP_CHECKOK(mp_copy(&qy, &sy)); 241 /* l = index of high order bit in binary representation of 3*k */ 242 l = mpl_significant_bits(&k3) - 1; 243 /* for i = l-1 downto 1 */ 244 for (i = l - 1; i >= 1; i--) { 245 /* S = 2S */ 246 MP_CHECKOK(group->point_dbl(&sx, &sy, &sx, &sy, group)); 247 b3 = MP_GET_BIT(&k3, i); 248 b1 = MP_GET_BIT(&k, i); 249 /* if k3_i = 1 and k_i = 0, then S = S + Q */ 250 if ((b3 == 1) && (b1 == 0)) { 251 MP_CHECKOK(group-> 252 point_add(&sx, &sy, &qx, &qy, &sx, &sy, group)); 253 /* if k3_i = 0 and k_i = 1, then S = S - Q */ 254 } else if ((b3 == 0) && (b1 == 1)) { 255 MP_CHECKOK(group-> 256 point_sub(&sx, &sy, &qx, &qy, &sx, &sy, group)); 257 } 258 } 259#endif 260 /* output S */ 261 MP_CHECKOK(mp_copy(&sx, rx)); 262 MP_CHECKOK(mp_copy(&sy, ry)); 263 264 CLEANUP: 265 mp_clear(&k); 266 mp_clear(&k3); 267 mp_clear(&qx); 268 mp_clear(&qy); 269 mp_clear(&sx); 270 mp_clear(&sy); 271 return res; 272} 273#endif 274 275/* Validates a point on a GF2m curve. */ 276mp_err 277ec_GF2m_validate_point(const mp_int *px, const mp_int *py, const ECGroup *group) 278{ 279 mp_err res = MP_NO; 280 mp_int accl, accr, tmp, pxt, pyt; 281 282 MP_DIGITS(&accl) = 0; 283 MP_DIGITS(&accr) = 0; 284 MP_DIGITS(&tmp) = 0; 285 MP_DIGITS(&pxt) = 0; 286 MP_DIGITS(&pyt) = 0; 287 MP_CHECKOK(mp_init(&accl, FLAG(px))); 288 MP_CHECKOK(mp_init(&accr, FLAG(px))); 289 MP_CHECKOK(mp_init(&tmp, FLAG(px))); 290 MP_CHECKOK(mp_init(&pxt, FLAG(px))); 291 MP_CHECKOK(mp_init(&pyt, FLAG(px))); 292 293 /* 1: Verify that publicValue is not the point at infinity */ 294 if (ec_GF2m_pt_is_inf_aff(px, py) == MP_YES) { 295 res = MP_NO; 296 goto CLEANUP; 297 } 298 /* 2: Verify that the coordinates of publicValue are elements 299 * of the field. 300 */ 301 if ((MP_SIGN(px) == MP_NEG) || (mp_cmp(px, &group->meth->irr) >= 0) || 302 (MP_SIGN(py) == MP_NEG) || (mp_cmp(py, &group->meth->irr) >= 0)) { 303 res = MP_NO; 304 goto CLEANUP; 305 } 306 /* 3: Verify that publicValue is on the curve. */ 307 if (group->meth->field_enc) { 308 group->meth->field_enc(px, &pxt, group->meth); 309 group->meth->field_enc(py, &pyt, group->meth); 310 } else { 311 mp_copy(px, &pxt); 312 mp_copy(py, &pyt); 313 } 314 /* left-hand side: y^2 + x*y */ 315 MP_CHECKOK( group->meth->field_sqr(&pyt, &accl, group->meth) ); 316 MP_CHECKOK( group->meth->field_mul(&pxt, &pyt, &tmp, group->meth) ); 317 MP_CHECKOK( group->meth->field_add(&accl, &tmp, &accl, group->meth) ); 318 /* right-hand side: x^3 + a*x^2 + b */ 319 MP_CHECKOK( group->meth->field_sqr(&pxt, &tmp, group->meth) ); 320 MP_CHECKOK( group->meth->field_mul(&pxt, &tmp, &accr, group->meth) ); 321 MP_CHECKOK( group->meth->field_mul(&group->curvea, &tmp, &tmp, group->meth) ); 322 MP_CHECKOK( group->meth->field_add(&tmp, &accr, &accr, group->meth) ); 323 MP_CHECKOK( group->meth->field_add(&accr, &group->curveb, &accr, group->meth) ); 324 /* check LHS - RHS == 0 */ 325 MP_CHECKOK( group->meth->field_add(&accl, &accr, &accr, group->meth) ); 326 if (mp_cmp_z(&accr) != 0) { 327 res = MP_NO; 328 goto CLEANUP; 329 } 330 /* 4: Verify that the order of the curve times the publicValue 331 * is the point at infinity. 332 */ 333 /* timing mitigation is not supported */ 334 MP_CHECKOK( ECPoint_mul(group, &group->order, px, py, &pxt, &pyt, /*timing*/ 0) ); 335 if (ec_GF2m_pt_is_inf_aff(&pxt, &pyt) != MP_YES) { 336 res = MP_NO; 337 goto CLEANUP; 338 } 339 340 res = MP_YES; 341 342CLEANUP: 343 mp_clear(&accl); 344 mp_clear(&accr); 345 mp_clear(&tmp); 346 mp_clear(&pxt); 347 mp_clear(&pyt); 348 return res; 349} 350