annotate src/jdk.crypto.ec/share/native/libsunec/impl/ecl_mult.c @ 51120:dccdf51b10dd

8207233: Minor improvements of jdk C-coding Reviewed-by: rriggs, prr
author goetz
date Fri, 13 Jul 2018 17:42:24 +0200
parents 71c04702a3d5
children
rev   line source
vinnie@9774 1 /*
goetz@51120 2 * Copyright (c) 2007, 2018, Oracle and/or its affiliates. All rights reserved.
vinnie@9774 3 * Use is subject to license terms.
vinnie@9774 4 *
vinnie@9774 5 * This library is free software; you can redistribute it and/or
vinnie@9774 6 * modify it under the terms of the GNU Lesser General Public
vinnie@9774 7 * License as published by the Free Software Foundation; either
vinnie@9774 8 * version 2.1 of the License, or (at your option) any later version.
vinnie@9774 9 *
vinnie@9774 10 * This library is distributed in the hope that it will be useful,
vinnie@9774 11 * but WITHOUT ANY WARRANTY; without even the implied warranty of
vinnie@9774 12 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
vinnie@9774 13 * Lesser General Public License for more details.
vinnie@9774 14 *
vinnie@9774 15 * You should have received a copy of the GNU Lesser General Public License
vinnie@9774 16 * along with this library; if not, write to the Free Software Foundation,
vinnie@9774 17 * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
vinnie@9774 18 *
vinnie@9774 19 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
vinnie@9774 20 * or visit www.oracle.com if you need additional information or have any
vinnie@9774 21 * questions.
vinnie@9774 22 */
vinnie@9774 23
vinnie@3863 24 /* *********************************************************************
vinnie@3863 25 *
vinnie@3863 26 * The Original Code is the elliptic curve math library.
vinnie@3863 27 *
vinnie@3863 28 * The Initial Developer of the Original Code is
vinnie@3863 29 * Sun Microsystems, Inc.
vinnie@3863 30 * Portions created by the Initial Developer are Copyright (C) 2003
vinnie@3863 31 * the Initial Developer. All Rights Reserved.
vinnie@3863 32 *
vinnie@3863 33 * Contributor(s):
vinnie@3863 34 * Douglas Stebila <douglas@stebila.ca>, Sun Microsystems Laboratories
vinnie@3863 35 *
apetcher@45993 36 * Last Modified Date from the Original Code: May 2017
vinnie@3863 37 *********************************************************************** */
vinnie@3863 38
vinnie@3863 39 #include "mpi.h"
vinnie@3863 40 #include "mplogic.h"
vinnie@3863 41 #include "ecl.h"
vinnie@3863 42 #include "ecl-priv.h"
vinnie@3863 43 #ifndef _KERNEL
vinnie@3863 44 #include <stdlib.h>
vinnie@3863 45 #endif
vinnie@3863 46
vinnie@3863 47 /* Elliptic curve scalar-point multiplication. Computes R(x, y) = k * P(x,
vinnie@3863 48 * y). If x, y = NULL, then P is assumed to be the generator (base point)
vinnie@3863 49 * of the group of points on the elliptic curve. Input and output values
vinnie@3863 50 * are assumed to be NOT field-encoded. */
vinnie@3863 51 mp_err
vinnie@3863 52 ECPoint_mul(const ECGroup *group, const mp_int *k, const mp_int *px,
apetcher@45993 53 const mp_int *py, mp_int *rx, mp_int *ry,
apetcher@45993 54 int timing)
vinnie@3863 55 {
vinnie@3863 56 mp_err res = MP_OKAY;
vinnie@3863 57 mp_int kt;
vinnie@3863 58
vinnie@3863 59 ARGCHK((k != NULL) && (group != NULL), MP_BADARG);
vinnie@3863 60 MP_DIGITS(&kt) = 0;
vinnie@3863 61
vinnie@3863 62 /* want scalar to be less than or equal to group order */
vinnie@3863 63 if (mp_cmp(k, &group->order) > 0) {
vinnie@3863 64 MP_CHECKOK(mp_init(&kt, FLAG(k)));
vinnie@3863 65 MP_CHECKOK(mp_mod(k, &group->order, &kt));
vinnie@3863 66 } else {
vinnie@3863 67 MP_SIGN(&kt) = MP_ZPOS;
vinnie@3863 68 MP_USED(&kt) = MP_USED(k);
vinnie@3863 69 MP_ALLOC(&kt) = MP_ALLOC(k);
vinnie@3863 70 MP_DIGITS(&kt) = MP_DIGITS(k);
vinnie@3863 71 }
vinnie@3863 72
vinnie@3863 73 if ((px == NULL) || (py == NULL)) {
vinnie@3863 74 if (group->base_point_mul) {
vinnie@3863 75 MP_CHECKOK(group->base_point_mul(&kt, rx, ry, group));
vinnie@3863 76 } else {
goetz@42455 77 kt.flag = (mp_sign)0;
vinnie@3863 78 MP_CHECKOK(group->
vinnie@3863 79 point_mul(&kt, &group->genx, &group->geny, rx, ry,
apetcher@45993 80 group, timing));
vinnie@3863 81 }
vinnie@3863 82 } else {
goetz@51120 83 kt.flag = (mp_sign)0;
vinnie@3863 84 if (group->meth->field_enc) {
vinnie@3863 85 MP_CHECKOK(group->meth->field_enc(px, rx, group->meth));
vinnie@3863 86 MP_CHECKOK(group->meth->field_enc(py, ry, group->meth));
apetcher@45993 87 MP_CHECKOK(group->point_mul(&kt, rx, ry, rx, ry, group, timing));
vinnie@3863 88 } else {
apetcher@45993 89 MP_CHECKOK(group->point_mul(&kt, px, py, rx, ry, group, timing));
vinnie@3863 90 }
vinnie@3863 91 }
vinnie@3863 92 if (group->meth->field_dec) {
vinnie@3863 93 MP_CHECKOK(group->meth->field_dec(rx, rx, group->meth));
vinnie@3863 94 MP_CHECKOK(group->meth->field_dec(ry, ry, group->meth));
vinnie@3863 95 }
vinnie@3863 96
vinnie@3863 97 CLEANUP:
vinnie@3863 98 if (MP_DIGITS(&kt) != MP_DIGITS(k)) {
vinnie@3863 99 mp_clear(&kt);
vinnie@3863 100 }
vinnie@3863 101 return res;
vinnie@3863 102 }
vinnie@3863 103
vinnie@3863 104 /* Elliptic curve scalar-point multiplication. Computes R(x, y) = k1 * G +
vinnie@3863 105 * k2 * P(x, y), where G is the generator (base point) of the group of
vinnie@3863 106 * points on the elliptic curve. Allows k1 = NULL or { k2, P } = NULL.
vinnie@3863 107 * Input and output values are assumed to be NOT field-encoded. */
vinnie@3863 108 mp_err
vinnie@3863 109 ec_pts_mul_basic(const mp_int *k1, const mp_int *k2, const mp_int *px,
vinnie@3863 110 const mp_int *py, mp_int *rx, mp_int *ry,
apetcher@45993 111 const ECGroup *group, int timing)
vinnie@3863 112 {
vinnie@3863 113 mp_err res = MP_OKAY;
vinnie@3863 114 mp_int sx, sy;
vinnie@3863 115
vinnie@3863 116 ARGCHK(group != NULL, MP_BADARG);
vinnie@3863 117 ARGCHK(!((k1 == NULL)
vinnie@3863 118 && ((k2 == NULL) || (px == NULL)
vinnie@3863 119 || (py == NULL))), MP_BADARG);
vinnie@3863 120
vinnie@3863 121 /* if some arguments are not defined used ECPoint_mul */
vinnie@3863 122 if (k1 == NULL) {
apetcher@45993 123 return ECPoint_mul(group, k2, px, py, rx, ry, timing);
vinnie@3863 124 } else if ((k2 == NULL) || (px == NULL) || (py == NULL)) {
apetcher@45993 125 return ECPoint_mul(group, k1, NULL, NULL, rx, ry, timing);
vinnie@3863 126 }
vinnie@3863 127
vinnie@3863 128 MP_DIGITS(&sx) = 0;
vinnie@3863 129 MP_DIGITS(&sy) = 0;
vinnie@3863 130 MP_CHECKOK(mp_init(&sx, FLAG(k1)));
vinnie@3863 131 MP_CHECKOK(mp_init(&sy, FLAG(k1)));
vinnie@3863 132
apetcher@45993 133 MP_CHECKOK(ECPoint_mul(group, k1, NULL, NULL, &sx, &sy, timing));
apetcher@45993 134 MP_CHECKOK(ECPoint_mul(group, k2, px, py, rx, ry, timing));
vinnie@3863 135
vinnie@3863 136 if (group->meth->field_enc) {
vinnie@3863 137 MP_CHECKOK(group->meth->field_enc(&sx, &sx, group->meth));
vinnie@3863 138 MP_CHECKOK(group->meth->field_enc(&sy, &sy, group->meth));
vinnie@3863 139 MP_CHECKOK(group->meth->field_enc(rx, rx, group->meth));
vinnie@3863 140 MP_CHECKOK(group->meth->field_enc(ry, ry, group->meth));
vinnie@3863 141 }
vinnie@3863 142
vinnie@3863 143 MP_CHECKOK(group->point_add(&sx, &sy, rx, ry, rx, ry, group));
vinnie@3863 144
vinnie@3863 145 if (group->meth->field_dec) {
vinnie@3863 146 MP_CHECKOK(group->meth->field_dec(rx, rx, group->meth));
vinnie@3863 147 MP_CHECKOK(group->meth->field_dec(ry, ry, group->meth));
vinnie@3863 148 }
vinnie@3863 149
vinnie@3863 150 CLEANUP:
vinnie@3863 151 mp_clear(&sx);
vinnie@3863 152 mp_clear(&sy);
vinnie@3863 153 return res;
vinnie@3863 154 }
vinnie@3863 155
vinnie@3863 156 /* Elliptic curve scalar-point multiplication. Computes R(x, y) = k1 * G +
vinnie@3863 157 * k2 * P(x, y), where G is the generator (base point) of the group of
vinnie@3863 158 * points on the elliptic curve. Allows k1 = NULL or { k2, P } = NULL.
vinnie@3863 159 * Input and output values are assumed to be NOT field-encoded. Uses
vinnie@3863 160 * algorithm 15 (simultaneous multiple point multiplication) from Brown,
vinnie@3863 161 * Hankerson, Lopez, Menezes. Software Implementation of the NIST
vinnie@3863 162 * Elliptic Curves over Prime Fields. */
vinnie@3863 163 mp_err
vinnie@3863 164 ec_pts_mul_simul_w2(const mp_int *k1, const mp_int *k2, const mp_int *px,
vinnie@3863 165 const mp_int *py, mp_int *rx, mp_int *ry,
apetcher@45993 166 const ECGroup *group, int timing)
vinnie@3863 167 {
vinnie@3863 168 mp_err res = MP_OKAY;
vinnie@3863 169 mp_int precomp[4][4][2];
vinnie@3863 170 const mp_int *a, *b;
vinnie@3863 171 int i, j;
vinnie@3863 172 int ai, bi, d;
vinnie@3863 173
vinnie@3863 174 ARGCHK(group != NULL, MP_BADARG);
vinnie@3863 175 ARGCHK(!((k1 == NULL)
vinnie@3863 176 && ((k2 == NULL) || (px == NULL)
vinnie@3863 177 || (py == NULL))), MP_BADARG);
vinnie@3863 178
vinnie@3863 179 /* if some arguments are not defined used ECPoint_mul */
vinnie@3863 180 if (k1 == NULL) {
apetcher@45993 181 return ECPoint_mul(group, k2, px, py, rx, ry, timing);
vinnie@3863 182 } else if ((k2 == NULL) || (px == NULL) || (py == NULL)) {
apetcher@45993 183 return ECPoint_mul(group, k1, NULL, NULL, rx, ry, timing);
vinnie@3863 184 }
vinnie@3863 185
vinnie@3863 186 /* initialize precomputation table */
vinnie@3863 187 for (i = 0; i < 4; i++) {
vinnie@3863 188 for (j = 0; j < 4; j++) {
vinnie@3863 189 MP_DIGITS(&precomp[i][j][0]) = 0;
vinnie@3863 190 MP_DIGITS(&precomp[i][j][1]) = 0;
vinnie@3863 191 }
vinnie@3863 192 }
vinnie@3863 193 for (i = 0; i < 4; i++) {
vinnie@3863 194 for (j = 0; j < 4; j++) {
vinnie@3863 195 MP_CHECKOK( mp_init_size(&precomp[i][j][0],
vinnie@3863 196 ECL_MAX_FIELD_SIZE_DIGITS, FLAG(k1)) );
vinnie@3863 197 MP_CHECKOK( mp_init_size(&precomp[i][j][1],
vinnie@3863 198 ECL_MAX_FIELD_SIZE_DIGITS, FLAG(k1)) );
vinnie@3863 199 }
vinnie@3863 200 }
vinnie@3863 201
vinnie@3863 202 /* fill precomputation table */
vinnie@3863 203 /* assign {k1, k2} = {a, b} such that len(a) >= len(b) */
vinnie@3863 204 if (mpl_significant_bits(k1) < mpl_significant_bits(k2)) {
vinnie@3863 205 a = k2;
vinnie@3863 206 b = k1;
vinnie@3863 207 if (group->meth->field_enc) {
vinnie@3863 208 MP_CHECKOK(group->meth->
vinnie@3863 209 field_enc(px, &precomp[1][0][0], group->meth));
vinnie@3863 210 MP_CHECKOK(group->meth->
vinnie@3863 211 field_enc(py, &precomp[1][0][1], group->meth));
vinnie@3863 212 } else {
vinnie@3863 213 MP_CHECKOK(mp_copy(px, &precomp[1][0][0]));
vinnie@3863 214 MP_CHECKOK(mp_copy(py, &precomp[1][0][1]));
vinnie@3863 215 }
vinnie@3863 216 MP_CHECKOK(mp_copy(&group->genx, &precomp[0][1][0]));
vinnie@3863 217 MP_CHECKOK(mp_copy(&group->geny, &precomp[0][1][1]));
vinnie@3863 218 } else {
vinnie@3863 219 a = k1;
vinnie@3863 220 b = k2;
vinnie@3863 221 MP_CHECKOK(mp_copy(&group->genx, &precomp[1][0][0]));
vinnie@3863 222 MP_CHECKOK(mp_copy(&group->geny, &precomp[1][0][1]));
vinnie@3863 223 if (group->meth->field_enc) {
vinnie@3863 224 MP_CHECKOK(group->meth->
vinnie@3863 225 field_enc(px, &precomp[0][1][0], group->meth));
vinnie@3863 226 MP_CHECKOK(group->meth->
vinnie@3863 227 field_enc(py, &precomp[0][1][1], group->meth));
vinnie@3863 228 } else {
vinnie@3863 229 MP_CHECKOK(mp_copy(px, &precomp[0][1][0]));
vinnie@3863 230 MP_CHECKOK(mp_copy(py, &precomp[0][1][1]));
vinnie@3863 231 }
vinnie@3863 232 }
vinnie@3863 233 /* precompute [*][0][*] */
vinnie@3863 234 mp_zero(&precomp[0][0][0]);
vinnie@3863 235 mp_zero(&precomp[0][0][1]);
vinnie@3863 236 MP_CHECKOK(group->
vinnie@3863 237 point_dbl(&precomp[1][0][0], &precomp[1][0][1],
vinnie@3863 238 &precomp[2][0][0], &precomp[2][0][1], group));
vinnie@3863 239 MP_CHECKOK(group->
vinnie@3863 240 point_add(&precomp[1][0][0], &precomp[1][0][1],
vinnie@3863 241 &precomp[2][0][0], &precomp[2][0][1],
vinnie@3863 242 &precomp[3][0][0], &precomp[3][0][1], group));
vinnie@3863 243 /* precompute [*][1][*] */
vinnie@3863 244 for (i = 1; i < 4; i++) {
vinnie@3863 245 MP_CHECKOK(group->
vinnie@3863 246 point_add(&precomp[0][1][0], &precomp[0][1][1],
vinnie@3863 247 &precomp[i][0][0], &precomp[i][0][1],
vinnie@3863 248 &precomp[i][1][0], &precomp[i][1][1], group));
vinnie@3863 249 }
vinnie@3863 250 /* precompute [*][2][*] */
vinnie@3863 251 MP_CHECKOK(group->
vinnie@3863 252 point_dbl(&precomp[0][1][0], &precomp[0][1][1],
vinnie@3863 253 &precomp[0][2][0], &precomp[0][2][1], group));
vinnie@3863 254 for (i = 1; i < 4; i++) {
vinnie@3863 255 MP_CHECKOK(group->
vinnie@3863 256 point_add(&precomp[0][2][0], &precomp[0][2][1],
vinnie@3863 257 &precomp[i][0][0], &precomp[i][0][1],
vinnie@3863 258 &precomp[i][2][0], &precomp[i][2][1], group));
vinnie@3863 259 }
vinnie@3863 260 /* precompute [*][3][*] */
vinnie@3863 261 MP_CHECKOK(group->
vinnie@3863 262 point_add(&precomp[0][1][0], &precomp[0][1][1],
vinnie@3863 263 &precomp[0][2][0], &precomp[0][2][1],
vinnie@3863 264 &precomp[0][3][0], &precomp[0][3][1], group));
vinnie@3863 265 for (i = 1; i < 4; i++) {
vinnie@3863 266 MP_CHECKOK(group->
vinnie@3863 267 point_add(&precomp[0][3][0], &precomp[0][3][1],
vinnie@3863 268 &precomp[i][0][0], &precomp[i][0][1],
vinnie@3863 269 &precomp[i][3][0], &precomp[i][3][1], group));
vinnie@3863 270 }
vinnie@3863 271
vinnie@3863 272 d = (mpl_significant_bits(a) + 1) / 2;
vinnie@3863 273
vinnie@3863 274 /* R = inf */
vinnie@3863 275 mp_zero(rx);
vinnie@3863 276 mp_zero(ry);
vinnie@3863 277
vinnie@3863 278 for (i = d - 1; i >= 0; i--) {
vinnie@3863 279 ai = MP_GET_BIT(a, 2 * i + 1);
vinnie@3863 280 ai <<= 1;
vinnie@3863 281 ai |= MP_GET_BIT(a, 2 * i);
vinnie@3863 282 bi = MP_GET_BIT(b, 2 * i + 1);
vinnie@3863 283 bi <<= 1;
vinnie@3863 284 bi |= MP_GET_BIT(b, 2 * i);
vinnie@3863 285 /* R = 2^2 * R */
vinnie@3863 286 MP_CHECKOK(group->point_dbl(rx, ry, rx, ry, group));
vinnie@3863 287 MP_CHECKOK(group->point_dbl(rx, ry, rx, ry, group));
vinnie@3863 288 /* R = R + (ai * A + bi * B) */
vinnie@3863 289 MP_CHECKOK(group->
vinnie@3863 290 point_add(rx, ry, &precomp[ai][bi][0],
vinnie@3863 291 &precomp[ai][bi][1], rx, ry, group));
vinnie@3863 292 }
vinnie@3863 293
vinnie@3863 294 if (group->meth->field_dec) {
vinnie@3863 295 MP_CHECKOK(group->meth->field_dec(rx, rx, group->meth));
vinnie@3863 296 MP_CHECKOK(group->meth->field_dec(ry, ry, group->meth));
vinnie@3863 297 }
vinnie@3863 298
vinnie@3863 299 CLEANUP:
vinnie@3863 300 for (i = 0; i < 4; i++) {
vinnie@3863 301 for (j = 0; j < 4; j++) {
vinnie@3863 302 mp_clear(&precomp[i][j][0]);
vinnie@3863 303 mp_clear(&precomp[i][j][1]);
vinnie@3863 304 }
vinnie@3863 305 }
vinnie@3863 306 return res;
vinnie@3863 307 }
vinnie@3863 308
vinnie@3863 309 /* Elliptic curve scalar-point multiplication. Computes R(x, y) = k1 * G +
vinnie@3863 310 * k2 * P(x, y), where G is the generator (base point) of the group of
vinnie@3863 311 * points on the elliptic curve. Allows k1 = NULL or { k2, P } = NULL.
vinnie@3863 312 * Input and output values are assumed to be NOT field-encoded. */
vinnie@3863 313 mp_err
vinnie@3863 314 ECPoints_mul(const ECGroup *group, const mp_int *k1, const mp_int *k2,
apetcher@45993 315 const mp_int *px, const mp_int *py, mp_int *rx, mp_int *ry,
apetcher@45993 316 int timing)
vinnie@3863 317 {
vinnie@3863 318 mp_err res = MP_OKAY;
vinnie@3863 319 mp_int k1t, k2t;
vinnie@3863 320 const mp_int *k1p, *k2p;
vinnie@3863 321
vinnie@3863 322 MP_DIGITS(&k1t) = 0;
vinnie@3863 323 MP_DIGITS(&k2t) = 0;
vinnie@3863 324
vinnie@3863 325 ARGCHK(group != NULL, MP_BADARG);
vinnie@3863 326
vinnie@3863 327 /* want scalar to be less than or equal to group order */
vinnie@3863 328 if (k1 != NULL) {
vinnie@3863 329 if (mp_cmp(k1, &group->order) >= 0) {
vinnie@3863 330 MP_CHECKOK(mp_init(&k1t, FLAG(k1)));
vinnie@3863 331 MP_CHECKOK(mp_mod(k1, &group->order, &k1t));
vinnie@3863 332 k1p = &k1t;
vinnie@3863 333 } else {
vinnie@3863 334 k1p = k1;
vinnie@3863 335 }
vinnie@3863 336 } else {
vinnie@3863 337 k1p = k1;
vinnie@3863 338 }
vinnie@3863 339 if (k2 != NULL) {
vinnie@3863 340 if (mp_cmp(k2, &group->order) >= 0) {
vinnie@3863 341 MP_CHECKOK(mp_init(&k2t, FLAG(k2)));
vinnie@3863 342 MP_CHECKOK(mp_mod(k2, &group->order, &k2t));
vinnie@3863 343 k2p = &k2t;
vinnie@3863 344 } else {
vinnie@3863 345 k2p = k2;
vinnie@3863 346 }
vinnie@3863 347 } else {
vinnie@3863 348 k2p = k2;
vinnie@3863 349 }
vinnie@3863 350
vinnie@3863 351 /* if points_mul is defined, then use it */
vinnie@3863 352 if (group->points_mul) {
apetcher@45993 353 res = group->points_mul(k1p, k2p, px, py, rx, ry, group, timing);
vinnie@3863 354 } else {
apetcher@45993 355 res = ec_pts_mul_simul_w2(k1p, k2p, px, py, rx, ry, group, timing);
vinnie@3863 356 }
vinnie@3863 357
vinnie@3863 358 CLEANUP:
vinnie@3863 359 mp_clear(&k1t);
vinnie@3863 360 mp_clear(&k2t);
vinnie@3863 361 return res;
vinnie@3863 362 }