Back to index

lightning-sunbird  0.9+nobinonly
ecp_fp224.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 prime field curves using floating point operations.
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  *   Stephen Fung <fungstep@hotmail.com>, 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 "ecp_fp.h"
00040 #include <stdlib.h>
00041 
00042 #define ECFP_BSIZE 224
00043 #define ECFP_NUMDOUBLES 10
00044 
00045 #include "ecp_fpinc.c"
00046 
00047 /* Performs a single step of reduction, just on the uppermost float
00048  * (assumes already tidied), and then retidies. Note, this does not
00049  * guarantee that the result will be less than p. */
00050 void
00051 ecfp224_singleReduce(double *r, const EC_group_fp * group)
00052 {
00053        double q;
00054 
00055        ECFP_ASSERT(group->doubleBitSize == 24);
00056        ECFP_ASSERT(group->primeBitSize == 224);
00057        ECFP_ASSERT(group->numDoubles == 10);
00058 
00059        q = r[ECFP_NUMDOUBLES - 1] - ecfp_beta_224;
00060        q += group->bitSize_alpha;
00061        q -= group->bitSize_alpha;
00062 
00063        r[ECFP_NUMDOUBLES - 1] -= q;
00064        r[0] -= q * ecfp_twom224;
00065        r[4] += q * ecfp_twom128;
00066 
00067        ecfp_positiveTidy(r, group);
00068 }
00069 
00070 /* 
00071  * Performs imperfect reduction.  This might leave some negative terms,
00072  * and one more reduction might be required for the result to be between 0 
00073  * and p-1. x should be be an array of at least 20, and r at least 10 x
00074  * and r can be the same, but then the upper parts of r are not zeroed */
00075 void
00076 ecfp224_reduce(double *r, double *x, const EC_group_fp * group)
00077 {
00078 
00079        double x10, x11, x12, x13, x14, q;
00080 
00081        ECFP_ASSERT(group->doubleBitSize == 24);
00082        ECFP_ASSERT(group->primeBitSize == 224);
00083        ECFP_ASSERT(group->numDoubles == 10);
00084 
00085        /* Tidy just the upper bits of x.  Don't need to tidy the lower ones
00086         * yet. */
00087        ecfp_tidyUpper(x, group);
00088 
00089        x10 = x[10] + x[16] * ecfp_twom128;
00090        x11 = x[11] + x[17] * ecfp_twom128;
00091        x12 = x[12] + x[18] * ecfp_twom128;
00092        x13 = x[13] + x[19] * ecfp_twom128;
00093 
00094        /* Tidy up, or we won't have enough bits later to add it in */
00095        q = x10 + group->alpha[11];
00096        q -= group->alpha[11];
00097        x10 -= q;
00098        x11 = x11 + q;
00099 
00100        q = x11 + group->alpha[12];
00101        q -= group->alpha[12];
00102        x11 -= q;
00103        x12 = x12 + q;
00104 
00105        q = x12 + group->alpha[13];
00106        q -= group->alpha[13];
00107        x12 -= q;
00108        x13 = x13 + q;
00109 
00110        q = x13 + group->alpha[14];
00111        q -= group->alpha[14];
00112        x13 -= q;
00113        x14 = x[14] + q;
00114 
00115        r[9] = x[9] + x[15] * ecfp_twom128 - x[19] * ecfp_twom224;
00116        r[8] = x[8] + x14 * ecfp_twom128 - x[18] * ecfp_twom224;
00117        r[7] = x[7] + x13 * ecfp_twom128 - x[17] * ecfp_twom224;
00118        r[6] = x[6] + x12 * ecfp_twom128 - x[16] * ecfp_twom224;
00119        r[5] = x[5] + x11 * ecfp_twom128 - x[15] * ecfp_twom224;
00120        r[4] = x[4] + x10 * ecfp_twom128 - x14 * ecfp_twom224;
00121        r[3] = x[3] - x13 * ecfp_twom224;
00122        r[2] = x[2] - x12 * ecfp_twom224;
00123        r[1] = x[1] - x11 * ecfp_twom224;
00124        r[0] = x[0] - x10 * ecfp_twom224;
00125 
00126        /* 
00127         * Tidy up just r[ECFP_NUMDOUBLES-2] so that the number of reductions
00128         * is accurate plus or minus one.  (Rather than tidy all to make it
00129         * totally accurate) */
00130        q = r[ECFP_NUMDOUBLES - 2] + group->alpha[ECFP_NUMDOUBLES - 1];
00131        q -= group->alpha[ECFP_NUMDOUBLES - 1];
00132        r[ECFP_NUMDOUBLES - 2] -= q;
00133        r[ECFP_NUMDOUBLES - 1] += q;
00134 
00135        /* Tidy up the excess bits on r[ECFP_NUMDOUBLES-1] using reduction */
00136        /* Use ecfp_beta so we get a positive res */
00137        q = r[ECFP_NUMDOUBLES - 1] - ecfp_beta_224;
00138        q += group->bitSize_alpha;
00139        q -= group->bitSize_alpha;
00140 
00141        r[ECFP_NUMDOUBLES - 1] -= q;
00142        r[0] -= q * ecfp_twom224;
00143        r[4] += q * ecfp_twom128;
00144 
00145        ecfp_tidyShort(r, group);
00146 }
00147 
00148 /* Sets group to use optimized calculations in this file */
00149 mp_err
00150 ec_group_set_nistp224_fp(ECGroup *group)
00151 {
00152 
00153        EC_group_fp *fpg;
00154 
00155        /* Allocate memory for floating point group data */
00156        fpg = (EC_group_fp *) malloc(sizeof(EC_group_fp));
00157        if (fpg == NULL) {
00158               return MP_MEM;
00159        }
00160 
00161        fpg->numDoubles = ECFP_NUMDOUBLES;
00162        fpg->primeBitSize = ECFP_BSIZE;
00163        fpg->orderBitSize = 224;
00164        fpg->doubleBitSize = 24;
00165        fpg->numInts = (ECFP_BSIZE + ECL_BITS - 1) / ECL_BITS;
00166        fpg->aIsM3 = 1;
00167        fpg->ecfp_singleReduce = &ecfp224_singleReduce;
00168        fpg->ecfp_reduce = &ecfp224_reduce;
00169        fpg->ecfp_tidy = &ecfp_tidy;
00170 
00171        fpg->pt_add_jac_aff = &ecfp224_pt_add_jac_aff;
00172        fpg->pt_add_jac = &ecfp224_pt_add_jac;
00173        fpg->pt_add_jm_chud = &ecfp224_pt_add_jm_chud;
00174        fpg->pt_add_chud = &ecfp224_pt_add_chud;
00175        fpg->pt_dbl_jac = &ecfp224_pt_dbl_jac;
00176        fpg->pt_dbl_jm = &ecfp224_pt_dbl_jm;
00177        fpg->pt_dbl_aff2chud = &ecfp224_pt_dbl_aff2chud;
00178        fpg->precompute_chud = &ecfp224_precompute_chud;
00179        fpg->precompute_jac = &ecfp224_precompute_jac;
00180 
00181        group->point_mul = &ec_GFp_point_mul_wNAF_fp;
00182        group->points_mul = &ec_pts_mul_basic;
00183        group->extra1 = fpg;
00184        group->extra_free = &ec_GFp_extra_free_fp;
00185 
00186        ec_set_fp_precision(fpg);
00187        fpg->bitSize_alpha = ECFP_TWO224 * fpg->alpha[0];
00188 
00189        return MP_OKAY;
00190 }