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