security/nss/lib/freebl/ecl/ecl_mult.c

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