Back to index

lightning-sunbird  0.9+nobinonly
ecl_mult.c
Go to the documentation of this file.
00001 /* 
00002  * ***** BEGIN LICENSE BLOCK *****
00003  * Version: MPL 1.1/GPL 2.0/LGPL 2.1
00004  *
00005  * The contents of this file are subject to the Mozilla Public License Version
00006  * 1.1 (the "License"); you may not use this file except in compliance with
00007  * the License. You may obtain a copy of the License at
00008  * http://www.mozilla.org/MPL/
00009  *
00010  * Software distributed under the License is distributed on an "AS IS" basis,
00011  * WITHOUT WARRANTY OF ANY KIND, either express or implied. See the License
00012  * for the specific language governing rights and limitations under the
00013  * License.
00014  *
00015  * The Original Code is the elliptic curve math library.
00016  *
00017  * The Initial Developer of the Original Code is
00018  * Sun Microsystems, Inc.
00019  * Portions created by the Initial Developer are Copyright (C) 2003
00020  * the Initial Developer. All Rights Reserved.
00021  *
00022  * Contributor(s):
00023  *   Douglas Stebila <douglas@stebila.ca>, Sun Microsystems Laboratories
00024  *
00025  * Alternatively, the contents of this file may be used under the terms of
00026  * either the GNU General Public License Version 2 or later (the "GPL"), or
00027  * the GNU Lesser General Public License Version 2.1 or later (the "LGPL"),
00028  * in which case the provisions of the GPL or the LGPL are applicable instead
00029  * of those above. If you wish to allow use of your version of this file only
00030  * under the terms of either the GPL or the LGPL, and not to allow others to
00031  * use your version of this file under the terms of the MPL, indicate your
00032  * decision by deleting the provisions above and replace them with the notice
00033  * and other provisions required by the GPL or the LGPL. If you do not delete
00034  * the provisions above, a recipient may use your version of this file under
00035  * the terms of any one of the MPL, the GPL or the LGPL.
00036  *
00037  * ***** END LICENSE BLOCK ***** */
00038 
00039 #include "mpi.h"
00040 #include "mplogic.h"
00041 #include "ecl.h"
00042 #include "ecl-priv.h"
00043 #include <stdlib.h>
00044 
00045 /* Elliptic curve scalar-point multiplication. Computes R(x, y) = k * P(x, 
00046  * y).  If x, y = NULL, then P is assumed to be the generator (base point) 
00047  * of the group of points on the elliptic curve. Input and output values
00048  * are assumed to be NOT field-encoded. */
00049 mp_err
00050 ECPoint_mul(const ECGroup *group, const mp_int *k, const mp_int *px,
00051                      const mp_int *py, mp_int *rx, mp_int *ry)
00052 {
00053        mp_err res = MP_OKAY;
00054        mp_int kt;
00055 
00056        ARGCHK((k != NULL) && (group != NULL), MP_BADARG);
00057        MP_DIGITS(&kt) = 0;
00058 
00059        /* want scalar to be less than or equal to group order */
00060        if (mp_cmp(k, &group->order) > 0) {
00061               MP_CHECKOK(mp_init(&kt));
00062               MP_CHECKOK(mp_mod(k, &group->order, &kt));
00063        } else {
00064               MP_SIGN(&kt) = MP_ZPOS;
00065               MP_USED(&kt) = MP_USED(k);
00066               MP_ALLOC(&kt) = MP_ALLOC(k);
00067               MP_DIGITS(&kt) = MP_DIGITS(k);
00068        }
00069 
00070        if ((px == NULL) || (py == NULL)) {
00071               if (group->base_point_mul) {
00072                      MP_CHECKOK(group->base_point_mul(&kt, rx, ry, group));
00073               } else {
00074                      MP_CHECKOK(group->
00075                                       point_mul(&kt, &group->genx, &group->geny, rx, ry,
00076                                                          group));
00077               }
00078        } else {
00079               if (group->meth->field_enc) {
00080                      MP_CHECKOK(group->meth->field_enc(px, rx, group->meth));
00081                      MP_CHECKOK(group->meth->field_enc(py, ry, group->meth));
00082                      MP_CHECKOK(group->point_mul(&kt, rx, ry, rx, ry, group));
00083               } else {
00084                      MP_CHECKOK(group->point_mul(&kt, px, py, rx, ry, group));
00085               }
00086        }
00087        if (group->meth->field_dec) {
00088               MP_CHECKOK(group->meth->field_dec(rx, rx, group->meth));
00089               MP_CHECKOK(group->meth->field_dec(ry, ry, group->meth));
00090        }
00091 
00092   CLEANUP:
00093        if (MP_DIGITS(&kt) != MP_DIGITS(k)) {
00094               mp_clear(&kt);
00095        }
00096        return res;
00097 }
00098 
00099 /* Elliptic curve scalar-point multiplication. Computes R(x, y) = k1 * G + 
00100  * k2 * P(x, y), where G is the generator (base point) of the group of
00101  * points on the elliptic curve. Allows k1 = NULL or { k2, P } = NULL.
00102  * Input and output values are assumed to be NOT field-encoded. */
00103 mp_err
00104 ec_pts_mul_basic(const mp_int *k1, const mp_int *k2, const mp_int *px,
00105                              const mp_int *py, mp_int *rx, mp_int *ry,
00106                              const ECGroup *group)
00107 {
00108        mp_err res = MP_OKAY;
00109        mp_int sx, sy;
00110 
00111        ARGCHK(group != NULL, MP_BADARG);
00112        ARGCHK(!((k1 == NULL)
00113                       && ((k2 == NULL) || (px == NULL)
00114                              || (py == NULL))), MP_BADARG);
00115 
00116        /* if some arguments are not defined used ECPoint_mul */
00117        if (k1 == NULL) {
00118               return ECPoint_mul(group, k2, px, py, rx, ry);
00119        } else if ((k2 == NULL) || (px == NULL) || (py == NULL)) {
00120               return ECPoint_mul(group, k1, NULL, NULL, rx, ry);
00121        }
00122 
00123        MP_DIGITS(&sx) = 0;
00124        MP_DIGITS(&sy) = 0;
00125        MP_CHECKOK(mp_init(&sx));
00126        MP_CHECKOK(mp_init(&sy));
00127 
00128        MP_CHECKOK(ECPoint_mul(group, k1, NULL, NULL, &sx, &sy));
00129        MP_CHECKOK(ECPoint_mul(group, k2, px, py, rx, ry));
00130 
00131        if (group->meth->field_enc) {
00132               MP_CHECKOK(group->meth->field_enc(&sx, &sx, group->meth));
00133               MP_CHECKOK(group->meth->field_enc(&sy, &sy, group->meth));
00134               MP_CHECKOK(group->meth->field_enc(rx, rx, group->meth));
00135               MP_CHECKOK(group->meth->field_enc(ry, ry, group->meth));
00136        }
00137 
00138        MP_CHECKOK(group->point_add(&sx, &sy, rx, ry, rx, ry, group));
00139 
00140        if (group->meth->field_dec) {
00141               MP_CHECKOK(group->meth->field_dec(rx, rx, group->meth));
00142               MP_CHECKOK(group->meth->field_dec(ry, ry, group->meth));
00143        }
00144 
00145   CLEANUP:
00146        mp_clear(&sx);
00147        mp_clear(&sy);
00148        return res;
00149 }
00150 
00151 /* Elliptic curve scalar-point multiplication. Computes R(x, y) = k1 * G + 
00152  * k2 * P(x, y), where G is the generator (base point) of the group of
00153  * points on the elliptic curve. Allows k1 = NULL or { k2, P } = NULL.
00154  * Input and output values are assumed to be NOT field-encoded. Uses
00155  * algorithm 15 (simultaneous multiple point multiplication) from Brown,
00156  * Hankerson, Lopez, Menezes. Software Implementation of the NIST
00157  * Elliptic Curves over Prime Fields. */
00158 mp_err
00159 ec_pts_mul_simul_w2(const mp_int *k1, const mp_int *k2, const mp_int *px,
00160                                    const mp_int *py, mp_int *rx, mp_int *ry,
00161                                    const ECGroup *group)
00162 {
00163        mp_err res = MP_OKAY;
00164        mp_int precomp[4][4][2];
00165        const mp_int *a, *b;
00166        int i, j;
00167        int ai, bi, d;
00168 
00169        ARGCHK(group != NULL, MP_BADARG);
00170        ARGCHK(!((k1 == NULL)
00171                       && ((k2 == NULL) || (px == NULL)
00172                              || (py == NULL))), MP_BADARG);
00173 
00174        /* if some arguments are not defined used ECPoint_mul */
00175        if (k1 == NULL) {
00176               return ECPoint_mul(group, k2, px, py, rx, ry);
00177        } else if ((k2 == NULL) || (px == NULL) || (py == NULL)) {
00178               return ECPoint_mul(group, k1, NULL, NULL, rx, ry);
00179        }
00180 
00181        /* initialize precomputation table */
00182        for (i = 0; i < 4; i++) {
00183               for (j = 0; j < 4; j++) {
00184                      MP_DIGITS(&precomp[i][j][0]) = 0;
00185                      MP_DIGITS(&precomp[i][j][1]) = 0;
00186               }
00187        }
00188        for (i = 0; i < 4; i++) {
00189               for (j = 0; j < 4; j++) {
00190                       MP_CHECKOK( mp_init_size(&precomp[i][j][0],
00191                                            ECL_MAX_FIELD_SIZE_DIGITS) );
00192                       MP_CHECKOK( mp_init_size(&precomp[i][j][1],
00193                                            ECL_MAX_FIELD_SIZE_DIGITS) );
00194               }
00195        }
00196 
00197        /* fill precomputation table */
00198        /* assign {k1, k2} = {a, b} such that len(a) >= len(b) */
00199        if (mpl_significant_bits(k1) < mpl_significant_bits(k2)) {
00200               a = k2;
00201               b = k1;
00202               if (group->meth->field_enc) {
00203                      MP_CHECKOK(group->meth->
00204                                       field_enc(px, &precomp[1][0][0], group->meth));
00205                      MP_CHECKOK(group->meth->
00206                                       field_enc(py, &precomp[1][0][1], group->meth));
00207               } else {
00208                      MP_CHECKOK(mp_copy(px, &precomp[1][0][0]));
00209                      MP_CHECKOK(mp_copy(py, &precomp[1][0][1]));
00210               }
00211               MP_CHECKOK(mp_copy(&group->genx, &precomp[0][1][0]));
00212               MP_CHECKOK(mp_copy(&group->geny, &precomp[0][1][1]));
00213        } else {
00214               a = k1;
00215               b = k2;
00216               MP_CHECKOK(mp_copy(&group->genx, &precomp[1][0][0]));
00217               MP_CHECKOK(mp_copy(&group->geny, &precomp[1][0][1]));
00218               if (group->meth->field_enc) {
00219                      MP_CHECKOK(group->meth->
00220                                       field_enc(px, &precomp[0][1][0], group->meth));
00221                      MP_CHECKOK(group->meth->
00222                                       field_enc(py, &precomp[0][1][1], group->meth));
00223               } else {
00224                      MP_CHECKOK(mp_copy(px, &precomp[0][1][0]));
00225                      MP_CHECKOK(mp_copy(py, &precomp[0][1][1]));
00226               }
00227        }
00228        /* precompute [*][0][*] */
00229        mp_zero(&precomp[0][0][0]);
00230        mp_zero(&precomp[0][0][1]);
00231        MP_CHECKOK(group->
00232                         point_dbl(&precomp[1][0][0], &precomp[1][0][1],
00233                                            &precomp[2][0][0], &precomp[2][0][1], group));
00234        MP_CHECKOK(group->
00235                         point_add(&precomp[1][0][0], &precomp[1][0][1],
00236                                            &precomp[2][0][0], &precomp[2][0][1],
00237                                            &precomp[3][0][0], &precomp[3][0][1], group));
00238        /* precompute [*][1][*] */
00239        for (i = 1; i < 4; i++) {
00240               MP_CHECKOK(group->
00241                                point_add(&precomp[0][1][0], &precomp[0][1][1],
00242                                                   &precomp[i][0][0], &precomp[i][0][1],
00243                                                   &precomp[i][1][0], &precomp[i][1][1], group));
00244        }
00245        /* precompute [*][2][*] */
00246        MP_CHECKOK(group->
00247                         point_dbl(&precomp[0][1][0], &precomp[0][1][1],
00248                                            &precomp[0][2][0], &precomp[0][2][1], group));
00249        for (i = 1; i < 4; i++) {
00250               MP_CHECKOK(group->
00251                                point_add(&precomp[0][2][0], &precomp[0][2][1],
00252                                                   &precomp[i][0][0], &precomp[i][0][1],
00253                                                   &precomp[i][2][0], &precomp[i][2][1], group));
00254        }
00255        /* precompute [*][3][*] */
00256        MP_CHECKOK(group->
00257                         point_add(&precomp[0][1][0], &precomp[0][1][1],
00258                                            &precomp[0][2][0], &precomp[0][2][1],
00259                                            &precomp[0][3][0], &precomp[0][3][1], group));
00260        for (i = 1; i < 4; i++) {
00261               MP_CHECKOK(group->
00262                                point_add(&precomp[0][3][0], &precomp[0][3][1],
00263                                                   &precomp[i][0][0], &precomp[i][0][1],
00264                                                   &precomp[i][3][0], &precomp[i][3][1], group));
00265        }
00266 
00267        d = (mpl_significant_bits(a) + 1) / 2;
00268 
00269        /* R = inf */
00270        mp_zero(rx);
00271        mp_zero(ry);
00272 
00273        for (i = d - 1; i >= 0; i--) {
00274               ai = MP_GET_BIT(a, 2 * i + 1);
00275               ai <<= 1;
00276               ai |= MP_GET_BIT(a, 2 * i);
00277               bi = MP_GET_BIT(b, 2 * i + 1);
00278               bi <<= 1;
00279               bi |= MP_GET_BIT(b, 2 * i);
00280               /* R = 2^2 * R */
00281               MP_CHECKOK(group->point_dbl(rx, ry, rx, ry, group));
00282               MP_CHECKOK(group->point_dbl(rx, ry, rx, ry, group));
00283               /* R = R + (ai * A + bi * B) */
00284               MP_CHECKOK(group->
00285                                point_add(rx, ry, &precomp[ai][bi][0],
00286                                                   &precomp[ai][bi][1], rx, ry, group));
00287        }
00288 
00289        if (group->meth->field_dec) {
00290               MP_CHECKOK(group->meth->field_dec(rx, rx, group->meth));
00291               MP_CHECKOK(group->meth->field_dec(ry, ry, group->meth));
00292        }
00293 
00294   CLEANUP:
00295        for (i = 0; i < 4; i++) {
00296               for (j = 0; j < 4; j++) {
00297                      mp_clear(&precomp[i][j][0]);
00298                      mp_clear(&precomp[i][j][1]);
00299               }
00300        }
00301        return res;
00302 }
00303 
00304 /* Elliptic curve scalar-point multiplication. Computes R(x, y) = k1 * G + 
00305  * k2 * P(x, y), where G is the generator (base point) of the group of
00306  * points on the elliptic curve. Allows k1 = NULL or { k2, P } = NULL.
00307  * Input and output values are assumed to be NOT field-encoded. */
00308 mp_err
00309 ECPoints_mul(const ECGroup *group, const mp_int *k1, const mp_int *k2,
00310                       const mp_int *px, const mp_int *py, mp_int *rx, mp_int *ry)
00311 {
00312        mp_err res = MP_OKAY;
00313        mp_int k1t, k2t;
00314        const mp_int *k1p, *k2p;
00315 
00316        MP_DIGITS(&k1t) = 0;
00317        MP_DIGITS(&k2t) = 0;
00318 
00319        ARGCHK(group != NULL, MP_BADARG);
00320 
00321        /* want scalar to be less than or equal to group order */
00322        if (k1 != NULL) {
00323               if (mp_cmp(k1, &group->order) >= 0) {
00324                      MP_CHECKOK(mp_init(&k1t));
00325                      MP_CHECKOK(mp_mod(k1, &group->order, &k1t));
00326                      k1p = &k1t;
00327               } else {
00328                      k1p = k1;
00329               }
00330        } else {
00331               k1p = k1;
00332        }
00333        if (k2 != NULL) {
00334               if (mp_cmp(k2, &group->order) >= 0) {
00335                      MP_CHECKOK(mp_init(&k2t));
00336                      MP_CHECKOK(mp_mod(k2, &group->order, &k2t));
00337                      k2p = &k2t;
00338               } else {
00339                      k2p = k2;
00340               }
00341        } else {
00342               k2p = k2;
00343        }
00344 
00345        /* if points_mul is defined, then use it */
00346        if (group->points_mul) {
00347               res = group->points_mul(k1p, k2p, px, py, rx, ry, group);
00348        } else {
00349               res = ec_pts_mul_simul_w2(k1p, k2p, px, py, rx, ry, group);
00350        }
00351 
00352   CLEANUP:
00353        mp_clear(&k1t);
00354        mp_clear(&k2t);
00355        return res;
00356 }