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