Back to index

lightning-sunbird  0.9+nobinonly
ec2_proj.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 for binary polynomial field curves.
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  *   Sheueling Chang-Shantz <sheueling.chang@sun.com>,
00024  *   Stephen Fung <fungstep@hotmail.com>, and
00025  *   Douglas Stebila <douglas@stebila.ca>, Sun Microsystems Laboratories.
00026  *
00027  * Alternatively, the contents of this file may be used under the terms of
00028  * either the GNU General Public License Version 2 or later (the "GPL"), or
00029  * the GNU Lesser General Public License Version 2.1 or later (the "LGPL"),
00030  * in which case the provisions of the GPL or the LGPL are applicable instead
00031  * of those above. If you wish to allow use of your version of this file only
00032  * under the terms of either the GPL or the LGPL, and not to allow others to
00033  * use your version of this file under the terms of the MPL, indicate your
00034  * decision by deleting the provisions above and replace them with the notice
00035  * and other provisions required by the GPL or the LGPL. If you do not delete
00036  * the provisions above, a recipient may use your version of this file under
00037  * the terms of any one of the MPL, the GPL or the LGPL.
00038  *
00039  * ***** END LICENSE BLOCK ***** */
00040 
00041 #include "ec2.h"
00042 #include "mplogic.h"
00043 #include "mp_gf2m.h"
00044 #include <stdlib.h>
00045 #ifdef ECL_DEBUG
00046 #include <assert.h>
00047 #endif
00048 
00049 /* by default, these routines are unused and thus don't need to be compiled */
00050 #ifdef ECL_ENABLE_GF2M_PROJ
00051 /* Converts a point P(px, py) from affine coordinates to projective
00052  * coordinates R(rx, ry, rz). Assumes input is already field-encoded using 
00053  * field_enc, and returns output that is still field-encoded. */
00054 mp_err
00055 ec_GF2m_pt_aff2proj(const mp_int *px, const mp_int *py, mp_int *rx,
00056                                    mp_int *ry, mp_int *rz, const ECGroup *group)
00057 {
00058        mp_err res = MP_OKAY;
00059 
00060        MP_CHECKOK(mp_copy(px, rx));
00061        MP_CHECKOK(mp_copy(py, ry));
00062        MP_CHECKOK(mp_set_int(rz, 1));
00063        if (group->meth->field_enc) {
00064               MP_CHECKOK(group->meth->field_enc(rz, rz, group->meth));
00065        }
00066   CLEANUP:
00067        return res;
00068 }
00069 
00070 /* Converts a point P(px, py, pz) from projective coordinates to affine
00071  * coordinates R(rx, ry).  P and R can share x and y coordinates. Assumes
00072  * input is already field-encoded using field_enc, and returns output that
00073  * is still field-encoded. */
00074 mp_err
00075 ec_GF2m_pt_proj2aff(const mp_int *px, const mp_int *py, const mp_int *pz,
00076                                    mp_int *rx, mp_int *ry, const ECGroup *group)
00077 {
00078        mp_err res = MP_OKAY;
00079        mp_int z1, z2;
00080 
00081        MP_DIGITS(&z1) = 0;
00082        MP_DIGITS(&z2) = 0;
00083        MP_CHECKOK(mp_init(&z1));
00084        MP_CHECKOK(mp_init(&z2));
00085 
00086        /* if point at infinity, then set point at infinity and exit */
00087        if (ec_GF2m_pt_is_inf_proj(px, py, pz) == MP_YES) {
00088               MP_CHECKOK(ec_GF2m_pt_set_inf_aff(rx, ry));
00089               goto CLEANUP;
00090        }
00091 
00092        /* transform (px, py, pz) into (px / pz, py / pz^2) */
00093        if (mp_cmp_d(pz, 1) == 0) {
00094               MP_CHECKOK(mp_copy(px, rx));
00095               MP_CHECKOK(mp_copy(py, ry));
00096        } else {
00097               MP_CHECKOK(group->meth->field_div(NULL, pz, &z1, group->meth));
00098               MP_CHECKOK(group->meth->field_sqr(&z1, &z2, group->meth));
00099               MP_CHECKOK(group->meth->field_mul(px, &z1, rx, group->meth));
00100               MP_CHECKOK(group->meth->field_mul(py, &z2, ry, group->meth));
00101        }
00102 
00103   CLEANUP:
00104        mp_clear(&z1);
00105        mp_clear(&z2);
00106        return res;
00107 }
00108 
00109 /* Checks if point P(px, py, pz) is at infinity. Uses projective
00110  * coordinates. */
00111 mp_err
00112 ec_GF2m_pt_is_inf_proj(const mp_int *px, const mp_int *py,
00113                                       const mp_int *pz)
00114 {
00115        return mp_cmp_z(pz);
00116 }
00117 
00118 /* Sets P(px, py, pz) to be the point at infinity.  Uses projective
00119  * coordinates. */
00120 mp_err
00121 ec_GF2m_pt_set_inf_proj(mp_int *px, mp_int *py, mp_int *pz)
00122 {
00123        mp_zero(pz);
00124        return MP_OKAY;
00125 }
00126 
00127 /* Computes R = P + Q where R is (rx, ry, rz), P is (px, py, pz) and Q is
00128  * (qx, qy, 1).  Elliptic curve points P, Q, and R can all be identical.
00129  * Uses mixed projective-affine coordinates. Assumes input is already
00130  * field-encoded using field_enc, and returns output that is still
00131  * field-encoded. Uses equation (3) from Hankerson, Hernandez, Menezes.
00132  * Software Implementation of Elliptic Curve Cryptography Over Binary
00133  * Fields. */
00134 mp_err
00135 ec_GF2m_pt_add_proj(const mp_int *px, const mp_int *py, const mp_int *pz,
00136                                    const mp_int *qx, const mp_int *qy, mp_int *rx,
00137                                    mp_int *ry, mp_int *rz, const ECGroup *group)
00138 {
00139        mp_err res = MP_OKAY;
00140        mp_int A, B, C, D, E, F, G;
00141 
00142        /* If either P or Q is the point at infinity, then return the other
00143         * point */
00144        if (ec_GF2m_pt_is_inf_proj(px, py, pz) == MP_YES) {
00145               return ec_GF2m_pt_aff2proj(qx, qy, rx, ry, rz, group);
00146        }
00147        if (ec_GF2m_pt_is_inf_aff(qx, qy) == MP_YES) {
00148               MP_CHECKOK(mp_copy(px, rx));
00149               MP_CHECKOK(mp_copy(py, ry));
00150               return mp_copy(pz, rz);
00151        }
00152 
00153        MP_DIGITS(&A) = 0;
00154        MP_DIGITS(&B) = 0;
00155        MP_DIGITS(&C) = 0;
00156        MP_DIGITS(&D) = 0;
00157        MP_DIGITS(&E) = 0;
00158        MP_DIGITS(&F) = 0;
00159        MP_DIGITS(&G) = 0;
00160        MP_CHECKOK(mp_init(&A));
00161        MP_CHECKOK(mp_init(&B));
00162        MP_CHECKOK(mp_init(&C));
00163        MP_CHECKOK(mp_init(&D));
00164        MP_CHECKOK(mp_init(&E));
00165        MP_CHECKOK(mp_init(&F));
00166        MP_CHECKOK(mp_init(&G));
00167 
00168        /* D = pz^2 */
00169        MP_CHECKOK(group->meth->field_sqr(pz, &D, group->meth));
00170 
00171        /* A = qy * pz^2 + py */
00172        MP_CHECKOK(group->meth->field_mul(qy, &D, &A, group->meth));
00173        MP_CHECKOK(group->meth->field_add(&A, py, &A, group->meth));
00174 
00175        /* B = qx * pz + px */
00176        MP_CHECKOK(group->meth->field_mul(qx, pz, &B, group->meth));
00177        MP_CHECKOK(group->meth->field_add(&B, px, &B, group->meth));
00178 
00179        /* C = pz * B */
00180        MP_CHECKOK(group->meth->field_mul(pz, &B, &C, group->meth));
00181 
00182        /* D = B^2 * (C + a * pz^2) (using E as a temporary variable) */
00183        MP_CHECKOK(group->meth->
00184                         field_mul(&group->curvea, &D, &D, group->meth));
00185        MP_CHECKOK(group->meth->field_add(&C, &D, &D, group->meth));
00186        MP_CHECKOK(group->meth->field_sqr(&B, &E, group->meth));
00187        MP_CHECKOK(group->meth->field_mul(&E, &D, &D, group->meth));
00188 
00189        /* rz = C^2 */
00190        MP_CHECKOK(group->meth->field_sqr(&C, rz, group->meth));
00191 
00192        /* E = A * C */
00193        MP_CHECKOK(group->meth->field_mul(&A, &C, &E, group->meth));
00194 
00195        /* rx = A^2 + D + E */
00196        MP_CHECKOK(group->meth->field_sqr(&A, rx, group->meth));
00197        MP_CHECKOK(group->meth->field_add(rx, &D, rx, group->meth));
00198        MP_CHECKOK(group->meth->field_add(rx, &E, rx, group->meth));
00199 
00200        /* F = rx + qx * rz */
00201        MP_CHECKOK(group->meth->field_mul(qx, rz, &F, group->meth));
00202        MP_CHECKOK(group->meth->field_add(rx, &F, &F, group->meth));
00203 
00204        /* G = rx + qy * rz */
00205        MP_CHECKOK(group->meth->field_mul(qy, rz, &G, group->meth));
00206        MP_CHECKOK(group->meth->field_add(rx, &G, &G, group->meth));
00207 
00208        /* ry = E * F + rz * G (using G as a temporary variable) */
00209        MP_CHECKOK(group->meth->field_mul(rz, &G, &G, group->meth));
00210        MP_CHECKOK(group->meth->field_mul(&E, &F, ry, group->meth));
00211        MP_CHECKOK(group->meth->field_add(ry, &G, ry, group->meth));
00212 
00213   CLEANUP:
00214        mp_clear(&A);
00215        mp_clear(&B);
00216        mp_clear(&C);
00217        mp_clear(&D);
00218        mp_clear(&E);
00219        mp_clear(&F);
00220        mp_clear(&G);
00221        return res;
00222 }
00223 
00224 /* Computes R = 2P.  Elliptic curve points P and R can be identical.  Uses 
00225  * projective coordinates.
00226  *
00227  * Assumes input is already field-encoded using field_enc, and returns 
00228  * output that is still field-encoded.
00229  *
00230  * Uses equation (3) from Hankerson, Hernandez, Menezes. Software 
00231  * Implementation of Elliptic Curve Cryptography Over Binary Fields.
00232  */
00233 mp_err
00234 ec_GF2m_pt_dbl_proj(const mp_int *px, const mp_int *py, const mp_int *pz,
00235                                    mp_int *rx, mp_int *ry, mp_int *rz,
00236                                    const ECGroup *group)
00237 {
00238        mp_err res = MP_OKAY;
00239        mp_int t0, t1;
00240 
00241        if (ec_GF2m_pt_is_inf_proj(px, py, pz) == MP_YES) {
00242               return ec_GF2m_pt_set_inf_proj(rx, ry, rz);
00243        }
00244 
00245        MP_DIGITS(&t0) = 0;
00246        MP_DIGITS(&t1) = 0;
00247        MP_CHECKOK(mp_init(&t0));
00248        MP_CHECKOK(mp_init(&t1));
00249 
00250        /* t0 = px^2 */
00251        /* t1 = pz^2 */
00252        MP_CHECKOK(group->meth->field_sqr(px, &t0, group->meth));
00253        MP_CHECKOK(group->meth->field_sqr(pz, &t1, group->meth));
00254 
00255        /* rz = px^2 * pz^2 */
00256        MP_CHECKOK(group->meth->field_mul(&t0, &t1, rz, group->meth));
00257 
00258        /* t0 = px^4 */
00259        /* t1 = b * pz^4 */
00260        MP_CHECKOK(group->meth->field_sqr(&t0, &t0, group->meth));
00261        MP_CHECKOK(group->meth->field_sqr(&t1, &t1, group->meth));
00262        MP_CHECKOK(group->meth->
00263                         field_mul(&group->curveb, &t1, &t1, group->meth));
00264 
00265        /* rx = px^4 + b * pz^4 */
00266        MP_CHECKOK(group->meth->field_add(&t0, &t1, rx, group->meth));
00267 
00268        /* ry = b * pz^4 * rz + rx * (a * rz + py^2 + b * pz^4) */
00269        MP_CHECKOK(group->meth->field_sqr(py, ry, group->meth));
00270        MP_CHECKOK(group->meth->field_add(ry, &t1, ry, group->meth));
00271        /* t0 = a * rz */
00272        MP_CHECKOK(group->meth->
00273                         field_mul(&group->curvea, rz, &t0, group->meth));
00274        MP_CHECKOK(group->meth->field_add(&t0, ry, ry, group->meth));
00275        MP_CHECKOK(group->meth->field_mul(rx, ry, ry, group->meth));
00276        /* t1 = b * pz^4 * rz */
00277        MP_CHECKOK(group->meth->field_mul(&t1, rz, &t1, group->meth));
00278        MP_CHECKOK(group->meth->field_add(&t1, ry, ry, group->meth));
00279 
00280   CLEANUP:
00281        mp_clear(&t0);
00282        mp_clear(&t1);
00283        return res;
00284 }
00285 
00286 /* Computes R = nP where R is (rx, ry) and P is (px, py). The parameters
00287  * a, b and p are the elliptic curve coefficients and the prime that
00288  * determines the field GF2m.  Elliptic curve points P and R can be
00289  * identical.  Uses mixed projective-affine coordinates. Assumes input is
00290  * already field-encoded using field_enc, and returns output that is still
00291  * field-encoded. Uses 4-bit window method. */
00292 mp_err
00293 ec_GF2m_pt_mul_proj(const mp_int *n, const mp_int *px, const mp_int *py,
00294                                    mp_int *rx, mp_int *ry, const ECGroup *group)
00295 {
00296        mp_err res = MP_OKAY;
00297        mp_int precomp[16][2], rz;
00298        mp_digit precomp_arr[ECL_MAX_FIELD_SIZE_DIGITS * 16 * 2], *t;
00299        int i, ni, d;
00300 
00301        ARGCHK(group != NULL, MP_BADARG);
00302        ARGCHK((n != NULL) && (px != NULL) && (py != NULL), MP_BADARG);
00303 
00304        /* initialize precomputation table */
00305        t = precomp_arr;
00306        for (i = 0; i < 16; i++) {
00307               /* x co-ord */
00308               MP_SIGN(&precomp[i][0]) = MP_ZPOS;
00309               MP_ALLOC(&precomp[i][0]) = ECL_MAX_FIELD_SIZE_DIGITS;
00310               MP_USED(&precomp[i][0]) = 1;
00311               *t = 0;
00312               MP_DIGITS(&precomp[i][0]) = t;
00313               t += ECL_MAX_FIELD_SIZE_DIGITS;
00314               /* y co-ord */
00315               MP_SIGN(&precomp[i][1]) = MP_ZPOS;
00316               MP_ALLOC(&precomp[i][1]) = ECL_MAX_FIELD_SIZE_DIGITS;
00317               MP_USED(&precomp[i][1]) = 1;
00318               *t = 0;
00319               MP_DIGITS(&precomp[i][1]) = t;
00320               t += ECL_MAX_FIELD_SIZE_DIGITS;
00321        }
00322 
00323        /* fill precomputation table */
00324        mp_zero(&precomp[0][0]);
00325        mp_zero(&precomp[0][1]);
00326        MP_CHECKOK(mp_copy(px, &precomp[1][0]));
00327        MP_CHECKOK(mp_copy(py, &precomp[1][1]));
00328        for (i = 2; i < 16; i++) {
00329               MP_CHECKOK(group->
00330                                point_add(&precomp[1][0], &precomp[1][1],
00331                                                   &precomp[i - 1][0], &precomp[i - 1][1],
00332                                                   &precomp[i][0], &precomp[i][1], group));
00333        }
00334 
00335        d = (mpl_significant_bits(n) + 3) / 4;
00336 
00337        /* R = inf */
00338        MP_DIGITS(&rz) = 0;
00339        MP_CHECKOK(mp_init(&rz));
00340        MP_CHECKOK(ec_GF2m_pt_set_inf_proj(rx, ry, &rz));
00341 
00342        for (i = d - 1; i >= 0; i--) {
00343               /* compute window ni */
00344               ni = MP_GET_BIT(n, 4 * i + 3);
00345               ni <<= 1;
00346               ni |= MP_GET_BIT(n, 4 * i + 2);
00347               ni <<= 1;
00348               ni |= MP_GET_BIT(n, 4 * i + 1);
00349               ni <<= 1;
00350               ni |= MP_GET_BIT(n, 4 * i);
00351               /* R = 2^4 * R */
00352               MP_CHECKOK(ec_GF2m_pt_dbl_proj(rx, ry, &rz, rx, ry, &rz, group));
00353               MP_CHECKOK(ec_GF2m_pt_dbl_proj(rx, ry, &rz, rx, ry, &rz, group));
00354               MP_CHECKOK(ec_GF2m_pt_dbl_proj(rx, ry, &rz, rx, ry, &rz, group));
00355               MP_CHECKOK(ec_GF2m_pt_dbl_proj(rx, ry, &rz, rx, ry, &rz, group));
00356               /* R = R + (ni * P) */
00357               MP_CHECKOK(ec_GF2m_pt_add_proj
00358                                (rx, ry, &rz, &precomp[ni][0], &precomp[ni][1], rx, ry,
00359                                    &rz, group));
00360        }
00361 
00362        /* convert result S to affine coordinates */
00363        MP_CHECKOK(ec_GF2m_pt_proj2aff(rx, ry, &rz, rx, ry, group));
00364 
00365   CLEANUP:
00366        mp_clear(&rz);
00367        return res;
00368 }
00369 #endif