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. 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 "mpi.h" 58 #include "mplogic.h" 59 #include "ecl.h" 60 #include "ecl-priv.h" 61 #ifndef _KERNEL 62 #include <stdlib.h> 63 #endif 64 65 /* Elliptic curve scalar-point multiplication. Computes R(x, y) = k * P(x, 66 * y). If x, y = NULL, then P is assumed to be the generator (base point) 67 * of the group of points on the elliptic curve. Input and output values 68 * are assumed to be NOT field-encoded. */ 69 mp_err 70 ECPoint_mul(const ECGroup *group, const mp_int *k, const mp_int *px, 71 const mp_int *py, mp_int *rx, mp_int *ry) 72 { 73 mp_err res = MP_OKAY; 74 mp_int kt; 75 76 ARGCHK((k != NULL) && (group != NULL), MP_BADARG); 77 MP_DIGITS(&kt) = 0; 78 79 /* want scalar to be less than or equal to group order */ 80 if (mp_cmp(k, &group->order) > 0) { 81 MP_CHECKOK(mp_init(&kt, FLAG(k))); 82 MP_CHECKOK(mp_mod(k, &group->order, &kt)); 83 } else { 84 MP_SIGN(&kt) = MP_ZPOS; 85 MP_USED(&kt) = MP_USED(k); 86 MP_ALLOC(&kt) = MP_ALLOC(k); 87 MP_DIGITS(&kt) = MP_DIGITS(k); 88 } 89 90 if ((px == NULL) || (py == NULL)) { 91 if (group->base_point_mul) { 92 MP_CHECKOK(group->base_point_mul(&kt, rx, ry, group)); 93 } else { 94 MP_CHECKOK(group-> 95 point_mul(&kt, &group->genx, &group->geny, rx, ry, 96 group)); 97 } 98 } else { 99 if (group->meth->field_enc) { 100 MP_CHECKOK(group->meth->field_enc(px, rx, group->meth)); 101 MP_CHECKOK(group->meth->field_enc(py, ry, group->meth)); 102 MP_CHECKOK(group->point_mul(&kt, rx, ry, rx, ry, group)); 103 } else { 104 MP_CHECKOK(group->point_mul(&kt, px, py, rx, ry, group)); 105 } 106 } 107 if (group->meth->field_dec) { 108 MP_CHECKOK(group->meth->field_dec(rx, rx, group->meth)); 109 MP_CHECKOK(group->meth->field_dec(ry, ry, group->meth)); 110 } 111 112 CLEANUP: 113 if (MP_DIGITS(&kt) != MP_DIGITS(k)) { 114 mp_clear(&kt); 115 } 116 return res; 117 } 118 119 /* Elliptic curve scalar-point multiplication. Computes R(x, y) = k1 * G + 120 * k2 * P(x, y), where G is the generator (base point) of the group of 121 * points on the elliptic curve. Allows k1 = NULL or { k2, P } = NULL. 122 * Input and output values are assumed to be NOT field-encoded. */ 123 mp_err 124 ec_pts_mul_basic(const mp_int *k1, const mp_int *k2, const mp_int *px, 125 const mp_int *py, mp_int *rx, mp_int *ry, 126 const ECGroup *group) 127 { 128 mp_err res = MP_OKAY; 129 mp_int sx, sy; 130 131 ARGCHK(group != NULL, MP_BADARG); 132 ARGCHK(!((k1 == NULL) 133 && ((k2 == NULL) || (px == NULL) 134 || (py == NULL))), MP_BADARG); 135 136 /* if some arguments are not defined used ECPoint_mul */ 137 if (k1 == NULL) { 138 return ECPoint_mul(group, k2, px, py, rx, ry); 139 } else if ((k2 == NULL) || (px == NULL) || (py == NULL)) { 140 return ECPoint_mul(group, k1, NULL, NULL, rx, ry); 141 } 142 143 MP_DIGITS(&sx) = 0; 144 MP_DIGITS(&sy) = 0; 145 MP_CHECKOK(mp_init(&sx, FLAG(k1))); 146 MP_CHECKOK(mp_init(&sy, FLAG(k1))); 147 148 MP_CHECKOK(ECPoint_mul(group, k1, NULL, NULL, &sx, &sy)); 149 MP_CHECKOK(ECPoint_mul(group, k2, px, py, rx, ry)); 150 151 if (group->meth->field_enc) { 152 MP_CHECKOK(group->meth->field_enc(&sx, &sx, group->meth)); 153 MP_CHECKOK(group->meth->field_enc(&sy, &sy, group->meth)); 154 MP_CHECKOK(group->meth->field_enc(rx, rx, group->meth)); 155 MP_CHECKOK(group->meth->field_enc(ry, ry, group->meth)); 156 } 157 158 MP_CHECKOK(group->point_add(&sx, &sy, rx, ry, rx, ry, group)); 159 160 if (group->meth->field_dec) { 161 MP_CHECKOK(group->meth->field_dec(rx, rx, group->meth)); 162 MP_CHECKOK(group->meth->field_dec(ry, ry, group->meth)); 163 } 164 165 CLEANUP: 166 mp_clear(&sx); 167 mp_clear(&sy); 168 return res; 169 } 170 171 /* Elliptic curve scalar-point multiplication. Computes R(x, y) = k1 * G + 172 * k2 * P(x, y), where G is the generator (base point) of the group of 173 * points on the elliptic curve. Allows k1 = NULL or { k2, P } = NULL. 174 * Input and output values are assumed to be NOT field-encoded. Uses 175 * algorithm 15 (simultaneous multiple point multiplication) from Brown, 176 * Hankerson, Lopez, Menezes. Software Implementation of the NIST 177 * Elliptic Curves over Prime Fields. */ 178 mp_err 179 ec_pts_mul_simul_w2(const mp_int *k1, const mp_int *k2, const mp_int *px, 180 const mp_int *py, mp_int *rx, mp_int *ry, 181 const ECGroup *group) 182 { 183 mp_err res = MP_OKAY; 184 mp_int precomp[4][4][2]; 185 const mp_int *a, *b; 186 int i, j; 187 int ai, bi, d; 188 189 ARGCHK(group != NULL, MP_BADARG); 190 ARGCHK(!((k1 == NULL) 191 && ((k2 == NULL) || (px == NULL) 192 || (py == NULL))), MP_BADARG); 193 194 /* if some arguments are not defined used ECPoint_mul */ 195 if (k1 == NULL) { 196 return ECPoint_mul(group, k2, px, py, rx, ry); 197 } else if ((k2 == NULL) || (px == NULL) || (py == NULL)) { 198 return ECPoint_mul(group, k1, NULL, NULL, rx, ry); 199 } 200 201 /* initialize precomputation table */ 202 for (i = 0; i < 4; i++) { 203 for (j = 0; j < 4; j++) { 204 MP_DIGITS(&precomp[i][j][0]) = 0; 205 MP_DIGITS(&precomp[i][j][1]) = 0; 206 } 207 } 208 for (i = 0; i < 4; i++) { 209 for (j = 0; j < 4; j++) { 210 MP_CHECKOK( mp_init_size(&precomp[i][j][0], 211 ECL_MAX_FIELD_SIZE_DIGITS, FLAG(k1)) ); 212 MP_CHECKOK( mp_init_size(&precomp[i][j][1], 213 ECL_MAX_FIELD_SIZE_DIGITS, FLAG(k1)) ); 214 } 215 } 216 217 /* fill precomputation table */ 218 /* assign {k1, k2} = {a, b} such that len(a) >= len(b) */ 219 if (mpl_significant_bits(k1) < mpl_significant_bits(k2)) { 220 a = k2; 221 b = k1; 222 if (group->meth->field_enc) { 223 MP_CHECKOK(group->meth-> 224 field_enc(px, &precomp[1][0][0], group->meth)); 225 MP_CHECKOK(group->meth-> 226 field_enc(py, &precomp[1][0][1], group->meth)); 227 } else { 228 MP_CHECKOK(mp_copy(px, &precomp[1][0][0])); 229 MP_CHECKOK(mp_copy(py, &precomp[1][0][1])); 230 } 231 MP_CHECKOK(mp_copy(&group->genx, &precomp[0][1][0])); 232 MP_CHECKOK(mp_copy(&group->geny, &precomp[0][1][1])); 233 } else { 234 a = k1; 235 b = k2; 236 MP_CHECKOK(mp_copy(&group->genx, &precomp[1][0][0])); 237 MP_CHECKOK(mp_copy(&group->geny, &precomp[1][0][1])); 238 if (group->meth->field_enc) { 239 MP_CHECKOK(group->meth-> 240 field_enc(px, &precomp[0][1][0], group->meth)); 241 MP_CHECKOK(group->meth-> 242 field_enc(py, &precomp[0][1][1], group->meth)); 243 } else { 244 MP_CHECKOK(mp_copy(px, &precomp[0][1][0])); 245 MP_CHECKOK(mp_copy(py, &precomp[0][1][1])); 246 } 247 } 248 /* precompute [*][0][*] */ 249 mp_zero(&precomp[0][0][0]); 250 mp_zero(&precomp[0][0][1]); 251 MP_CHECKOK(group-> 252 point_dbl(&precomp[1][0][0], &precomp[1][0][1], 253 &precomp[2][0][0], &precomp[2][0][1], group)); 254 MP_CHECKOK(group-> 255 point_add(&precomp[1][0][0], &precomp[1][0][1], 256 &precomp[2][0][0], &precomp[2][0][1], 257 &precomp[3][0][0], &precomp[3][0][1], group)); 258 /* precompute [*][1][*] */ 259 for (i = 1; i < 4; i++) { 260 MP_CHECKOK(group-> 261 point_add(&precomp[0][1][0], &precomp[0][1][1], 262 &precomp[i][0][0], &precomp[i][0][1], 263 &precomp[i][1][0], &precomp[i][1][1], group)); 264 } 265 /* precompute [*][2][*] */ 266 MP_CHECKOK(group-> 267 point_dbl(&precomp[0][1][0], &precomp[0][1][1], 268 &precomp[0][2][0], &precomp[0][2][1], group)); 269 for (i = 1; i < 4; i++) { 270 MP_CHECKOK(group-> 271 point_add(&precomp[0][2][0], &precomp[0][2][1], 272 &precomp[i][0][0], &precomp[i][0][1], 273 &precomp[i][2][0], &precomp[i][2][1], group)); 274 } 275 /* precompute [*][3][*] */ 276 MP_CHECKOK(group-> 277 point_add(&precomp[0][1][0], &precomp[0][1][1], 278 &precomp[0][2][0], &precomp[0][2][1], 279 &precomp[0][3][0], &precomp[0][3][1], group)); 280 for (i = 1; i < 4; i++) { 281 MP_CHECKOK(group-> 282 point_add(&precomp[0][3][0], &precomp[0][3][1], 283 &precomp[i][0][0], &precomp[i][0][1], 284 &precomp[i][3][0], &precomp[i][3][1], group)); 285 } 286 287 d = (mpl_significant_bits(a) + 1) / 2; 288 289 /* R = inf */ 290 mp_zero(rx); 291 mp_zero(ry); 292 293 for (i = d - 1; i >= 0; i--) { 294 ai = MP_GET_BIT(a, 2 * i + 1); 295 ai <<= 1; 296 ai |= MP_GET_BIT(a, 2 * i); 297 bi = MP_GET_BIT(b, 2 * i + 1); 298 bi <<= 1; 299 bi |= MP_GET_BIT(b, 2 * i); 300 /* R = 2^2 * R */ 301 MP_CHECKOK(group->point_dbl(rx, ry, rx, ry, group)); 302 MP_CHECKOK(group->point_dbl(rx, ry, rx, ry, group)); 303 /* R = R + (ai * A + bi * B) */ 304 MP_CHECKOK(group-> 305 point_add(rx, ry, &precomp[ai][bi][0], 306 &precomp[ai][bi][1], rx, ry, group)); 307 } 308 309 if (group->meth->field_dec) { 310 MP_CHECKOK(group->meth->field_dec(rx, rx, group->meth)); 311 MP_CHECKOK(group->meth->field_dec(ry, ry, group->meth)); 312 } 313 314 CLEANUP: 315 for (i = 0; i < 4; i++) { 316 for (j = 0; j < 4; j++) { 317 mp_clear(&precomp[i][j][0]); 318 mp_clear(&precomp[i][j][1]); 319 } 320 } 321 return res; 322 } 323 324 /* Elliptic curve scalar-point multiplication. Computes R(x, y) = k1 * G + 325 * k2 * P(x, y), where G is the generator (base point) of the group of 326 * points on the elliptic curve. Allows k1 = NULL or { k2, P } = NULL. 327 * Input and output values are assumed to be NOT field-encoded. */ 328 mp_err 329 ECPoints_mul(const ECGroup *group, const mp_int *k1, const mp_int *k2, 330 const mp_int *px, const mp_int *py, mp_int *rx, mp_int *ry) 331 { 332 mp_err res = MP_OKAY; 333 mp_int k1t, k2t; 334 const mp_int *k1p, *k2p; 335 336 MP_DIGITS(&k1t) = 0; 337 MP_DIGITS(&k2t) = 0; 338 339 ARGCHK(group != NULL, MP_BADARG); 340 341 /* want scalar to be less than or equal to group order */ 342 if (k1 != NULL) { 343 if (mp_cmp(k1, &group->order) >= 0) { 344 MP_CHECKOK(mp_init(&k1t, FLAG(k1))); 345 MP_CHECKOK(mp_mod(k1, &group->order, &k1t)); 346 k1p = &k1t; 347 } else { 348 k1p = k1; 349 } 350 } else { 351 k1p = k1; 352 } 353 if (k2 != NULL) { 354 if (mp_cmp(k2, &group->order) >= 0) { 355 MP_CHECKOK(mp_init(&k2t, FLAG(k2))); 356 MP_CHECKOK(mp_mod(k2, &group->order, &k2t)); 357 k2p = &k2t; 358 } else { 359 k2p = k2; 360 } 361 } else { 362 k2p = k2; 363 } 364 365 /* if points_mul is defined, then use it */ 366 if (group->points_mul) { 367 res = group->points_mul(k1p, k2p, px, py, rx, ry, group); 368 } else { 369 res = ec_pts_mul_simul_w2(k1p, k2p, px, py, rx, ry, group); 370 } 371 372 CLEANUP: 373 mp_clear(&k1t); 374 mp_clear(&k2t); 375 return res; 376 }