Back to index

lightning-sunbird  0.9+nobinonly
ecl-priv.h
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  *   Stephen Fung <fungstep@hotmail.com> and
00024  *   Douglas Stebila <douglas@stebila.ca>, Sun Microsystems Laboratories
00025  *
00026  * Alternatively, the contents of this file may be used under the terms of
00027  * either the GNU General Public License Version 2 or later (the "GPL"), or
00028  * the GNU Lesser General Public License Version 2.1 or later (the "LGPL"),
00029  * in which case the provisions of the GPL or the LGPL are applicable instead
00030  * of those above. If you wish to allow use of your version of this file only
00031  * under the terms of either the GPL or the LGPL, and not to allow others to
00032  * use your version of this file under the terms of the MPL, indicate your
00033  * decision by deleting the provisions above and replace them with the notice
00034  * and other provisions required by the GPL or the LGPL. If you do not delete
00035  * the provisions above, a recipient may use your version of this file under
00036  * the terms of any one of the MPL, the GPL or the LGPL.
00037  *
00038  * ***** END LICENSE BLOCK ***** */
00039 
00040 #ifndef __ecl_priv_h_
00041 #define __ecl_priv_h_
00042 
00043 #include "ecl.h"
00044 #include "mpi.h"
00045 #include "mplogic.h"
00046 
00047 /* MAX_FIELD_SIZE_DIGITS is the maximum size of field element supported */
00048 /* the following needs to go away... */
00049 #if defined(MP_USE_LONG_LONG_DIGIT) || defined(MP_USE_LONG_DIGIT)
00050 #define ECL_SIXTY_FOUR_BIT
00051 #else
00052 #define ECL_THIRTY_TWO_BIT
00053 #endif
00054 
00055 #define ECL_CURVE_DIGITS(curve_size_in_bits) \
00056        (((curve_size_in_bits)+(sizeof(mp_digit)*8-1))/(sizeof(mp_digit)*8))
00057 #define ECL_BITS (sizeof(mp_digit)*8)
00058 #define ECL_MAX_FIELD_SIZE_DIGITS (80/sizeof(mp_digit))
00059 
00060 /* Gets the i'th bit in the binary representation of a. If i >= length(a), 
00061  * then return 0. (The above behaviour differs from mpl_get_bit, which
00062  * causes an error if i >= length(a).) */
00063 #define MP_GET_BIT(a, i) \
00064        ((i) >= mpl_significant_bits((a))) ? 0 : mpl_get_bit((a), (i))
00065 
00066 #if !defined(MP_NO_MP_WORD) && !defined(MP_NO_ADD_WORD)
00067 #define MP_ADD_CARRY(a1, a2, s, cin, cout)   \
00068     { mp_word w; \
00069     w = ((mp_word)(cin)) + (a1) + (a2); \
00070     s = ACCUM(w); \
00071     cout = CARRYOUT(w); }
00072 
00073 #define MP_SUB_BORROW(a1, a2, s, bin, bout)   \
00074     { mp_word w; \
00075     w = ((mp_word)(a1)) - (a2) - (bin); \
00076     s = ACCUM(w); \
00077     bout = (w >> MP_DIGIT_BIT) & 1; }
00078 
00079 #else
00080 /* NOTE, 
00081  * cin and cout could be the same variable.
00082  * bin and bout could be the same variable.
00083  * a1 or a2 and s could be the same variable.
00084  * don't trash those outputs until their respective inputs have
00085  * been read. */
00086 #define MP_ADD_CARRY(a1, a2, s, cin, cout)   \
00087     { mp_digit tmp,sum; \
00088     tmp = (a1); \
00089     sum = tmp + (a2); \
00090     tmp = (sum < tmp);                     /* detect overflow */ \
00091     s = sum += (cin); \
00092     cout = tmp + (sum < (cin)); }
00093 
00094 #define MP_SUB_BORROW(a1, a2, s, bin, bout)   \
00095     { mp_digit tmp; \
00096     tmp = (a1); \
00097     s = tmp - (a2); \
00098     tmp = (s > tmp);                    /* detect borrow */ \
00099     if ((bin) && !s--) tmp++;      \
00100     bout = tmp; }
00101 #endif
00102 
00103 
00104 struct GFMethodStr;
00105 typedef struct GFMethodStr GFMethod;
00106 struct GFMethodStr {
00107        /* Indicates whether the structure was constructed from dynamic memory 
00108         * or statically created. */
00109        int constructed;
00110        /* Irreducible that defines the field. For prime fields, this is the
00111         * prime p. For binary polynomial fields, this is the bitstring
00112         * representation of the irreducible polynomial. */
00113        mp_int irr;
00114        /* For prime fields, the value irr_arr[0] is the number of bits in the 
00115         * field. For binary polynomial fields, the irreducible polynomial
00116         * f(t) is represented as an array of unsigned int[], where f(t) is
00117         * of the form: f(t) = t^p[0] + t^p[1] + ... + t^p[4] where m = p[0]
00118         * > p[1] > ... > p[4] = 0. */
00119        unsigned int irr_arr[5];
00120        /* Field arithmetic methods. All methods (except field_enc and
00121         * field_dec) are assumed to take field-encoded parameters and return
00122         * field-encoded values. All methods (except field_enc and field_dec)
00123         * are required to be implemented. */
00124        mp_err (*field_add) (const mp_int *a, const mp_int *b, mp_int *r,
00125                                            const GFMethod *meth);
00126        mp_err (*field_neg) (const mp_int *a, mp_int *r, const GFMethod *meth);
00127        mp_err (*field_sub) (const mp_int *a, const mp_int *b, mp_int *r,
00128                                            const GFMethod *meth);
00129        mp_err (*field_mod) (const mp_int *a, mp_int *r, const GFMethod *meth);
00130        mp_err (*field_mul) (const mp_int *a, const mp_int *b, mp_int *r,
00131                                            const GFMethod *meth);
00132        mp_err (*field_sqr) (const mp_int *a, mp_int *r, const GFMethod *meth);
00133        mp_err (*field_div) (const mp_int *a, const mp_int *b, mp_int *r,
00134                                            const GFMethod *meth);
00135        mp_err (*field_enc) (const mp_int *a, mp_int *r, const GFMethod *meth);
00136        mp_err (*field_dec) (const mp_int *a, mp_int *r, const GFMethod *meth);
00137        /* Extra storage for implementation-specific data.  Any memory
00138         * allocated to these extra fields will be cleared by extra_free. */
00139        void *extra1;
00140        void *extra2;
00141        void (*extra_free) (GFMethod *meth);
00142 };
00143 
00144 /* Construct generic GFMethods. */
00145 GFMethod *GFMethod_consGFp(const mp_int *irr);
00146 GFMethod *GFMethod_consGFp_mont(const mp_int *irr);
00147 GFMethod *GFMethod_consGF2m(const mp_int *irr,
00148                                                  const unsigned int irr_arr[5]);
00149 /* Free the memory allocated (if any) to a GFMethod object. */
00150 void GFMethod_free(GFMethod *meth);
00151 
00152 struct ECGroupStr {
00153        /* Indicates whether the structure was constructed from dynamic memory 
00154         * or statically created. */
00155        int constructed;
00156        /* Field definition and arithmetic. */
00157        GFMethod *meth;
00158        /* Textual representation of curve name, if any. */
00159        char *text;
00160        /* Curve parameters, field-encoded. */
00161        mp_int curvea, curveb;
00162        /* x and y coordinates of the base point, field-encoded. */
00163        mp_int genx, geny;
00164        /* Order and cofactor of the base point. */
00165        mp_int order;
00166        int cofactor;
00167        /* Point arithmetic methods. All methods are assumed to take
00168         * field-encoded parameters and return field-encoded values. All
00169         * methods (except base_point_mul and points_mul) are required to be
00170         * implemented. */
00171        mp_err (*point_add) (const mp_int *px, const mp_int *py,
00172                                            const mp_int *qx, const mp_int *qy, mp_int *rx,
00173                                            mp_int *ry, const ECGroup *group);
00174        mp_err (*point_sub) (const mp_int *px, const mp_int *py,
00175                                            const mp_int *qx, const mp_int *qy, mp_int *rx,
00176                                            mp_int *ry, const ECGroup *group);
00177        mp_err (*point_dbl) (const mp_int *px, const mp_int *py, mp_int *rx,
00178                                            mp_int *ry, const ECGroup *group);
00179        mp_err (*point_mul) (const mp_int *n, const mp_int *px,
00180                                            const mp_int *py, mp_int *rx, mp_int *ry,
00181                                            const ECGroup *group);
00182        mp_err (*base_point_mul) (const mp_int *n, mp_int *rx, mp_int *ry,
00183                                                    const ECGroup *group);
00184        mp_err (*points_mul) (const mp_int *k1, const mp_int *k2,
00185                                             const mp_int *px, const mp_int *py, mp_int *rx,
00186                                             mp_int *ry, const ECGroup *group);
00187        mp_err (*validate_point) (const mp_int *px, const mp_int *py, const ECGroup *group);
00188        /* Extra storage for implementation-specific data.  Any memory
00189         * allocated to these extra fields will be cleared by extra_free. */
00190        void *extra1;
00191        void *extra2;
00192        void (*extra_free) (ECGroup *group);
00193 };
00194 
00195 /* Wrapper functions for generic prime field arithmetic. */
00196 mp_err ec_GFp_add(const mp_int *a, const mp_int *b, mp_int *r,
00197                               const GFMethod *meth);
00198 mp_err ec_GFp_neg(const mp_int *a, mp_int *r, const GFMethod *meth);
00199 mp_err ec_GFp_sub(const mp_int *a, const mp_int *b, mp_int *r,
00200                               const GFMethod *meth);
00201 
00202 /* fixed length in-line adds. Count is in words */
00203 mp_err ec_GFp_add_3(const mp_int *a, const mp_int *b, mp_int *r,
00204                               const GFMethod *meth);
00205 mp_err ec_GFp_add_4(const mp_int *a, const mp_int *b, mp_int *r,
00206                               const GFMethod *meth);
00207 mp_err ec_GFp_add_5(const mp_int *a, const mp_int *b, mp_int *r,
00208                               const GFMethod *meth);
00209 mp_err ec_GFp_add_6(const mp_int *a, const mp_int *b, mp_int *r,
00210                               const GFMethod *meth);
00211 mp_err ec_GFp_sub_3(const mp_int *a, const mp_int *b, mp_int *r,
00212                               const GFMethod *meth);
00213 mp_err ec_GFp_sub_4(const mp_int *a, const mp_int *b, mp_int *r,
00214                               const GFMethod *meth);
00215 mp_err ec_GFp_sub_5(const mp_int *a, const mp_int *b, mp_int *r,
00216                               const GFMethod *meth);
00217 mp_err ec_GFp_sub_6(const mp_int *a, const mp_int *b, mp_int *r,
00218                               const GFMethod *meth);
00219 
00220 mp_err ec_GFp_mod(const mp_int *a, mp_int *r, const GFMethod *meth);
00221 mp_err ec_GFp_mul(const mp_int *a, const mp_int *b, mp_int *r,
00222                               const GFMethod *meth);
00223 mp_err ec_GFp_sqr(const mp_int *a, mp_int *r, const GFMethod *meth);
00224 mp_err ec_GFp_div(const mp_int *a, const mp_int *b, mp_int *r,
00225                               const GFMethod *meth);
00226 /* Wrapper functions for generic binary polynomial field arithmetic. */
00227 mp_err ec_GF2m_add(const mp_int *a, const mp_int *b, mp_int *r,
00228                                const GFMethod *meth);
00229 mp_err ec_GF2m_neg(const mp_int *a, mp_int *r, const GFMethod *meth);
00230 mp_err ec_GF2m_mod(const mp_int *a, mp_int *r, const GFMethod *meth);
00231 mp_err ec_GF2m_mul(const mp_int *a, const mp_int *b, mp_int *r,
00232                                const GFMethod *meth);
00233 mp_err ec_GF2m_sqr(const mp_int *a, mp_int *r, const GFMethod *meth);
00234 mp_err ec_GF2m_div(const mp_int *a, const mp_int *b, mp_int *r,
00235                                const GFMethod *meth);
00236 
00237 /* Montgomery prime field arithmetic. */
00238 mp_err ec_GFp_mul_mont(const mp_int *a, const mp_int *b, mp_int *r,
00239                                       const GFMethod *meth);
00240 mp_err ec_GFp_sqr_mont(const mp_int *a, mp_int *r, const GFMethod *meth);
00241 mp_err ec_GFp_div_mont(const mp_int *a, const mp_int *b, mp_int *r,
00242                                       const GFMethod *meth);
00243 mp_err ec_GFp_enc_mont(const mp_int *a, mp_int *r, const GFMethod *meth);
00244 mp_err ec_GFp_dec_mont(const mp_int *a, mp_int *r, const GFMethod *meth);
00245 void ec_GFp_extra_free_mont(GFMethod *meth);
00246 
00247 /* point multiplication */
00248 mp_err ec_pts_mul_basic(const mp_int *k1, const mp_int *k2,
00249                                           const mp_int *px, const mp_int *py, mp_int *rx,
00250                                           mp_int *ry, const ECGroup *group);
00251 mp_err ec_pts_mul_simul_w2(const mp_int *k1, const mp_int *k2,
00252                                              const mp_int *px, const mp_int *py, mp_int *rx,
00253                                              mp_int *ry, const ECGroup *group);
00254 
00255 /* Computes the windowed non-adjacent-form (NAF) of a scalar. Out should
00256  * be an array of signed char's to output to, bitsize should be the number 
00257  * of bits of out, in is the original scalar, and w is the window size.
00258  * NAF is discussed in the paper: D. Hankerson, J. Hernandez and A.
00259  * Menezes, "Software implementation of elliptic curve cryptography over
00260  * binary fields", Proc. CHES 2000. */
00261 mp_err ec_compute_wNAF(signed char *out, int bitsize, const mp_int *in,
00262                                       int w);
00263 
00264 /* Optimized field arithmetic */
00265 mp_err ec_group_set_gfp192(ECGroup *group, ECCurveName);
00266 mp_err ec_group_set_gfp224(ECGroup *group, ECCurveName);
00267 mp_err ec_group_set_gfp256(ECGroup *group, ECCurveName);
00268 mp_err ec_group_set_gfp384(ECGroup *group, ECCurveName);
00269 mp_err ec_group_set_gfp521(ECGroup *group, ECCurveName);
00270 mp_err ec_group_set_gf2m163(ECGroup *group, ECCurveName name);
00271 mp_err ec_group_set_gf2m193(ECGroup *group, ECCurveName name);
00272 mp_err ec_group_set_gf2m233(ECGroup *group, ECCurveName name);
00273 
00274 /* Optimized floating-point arithmetic */
00275 #ifdef ECL_USE_FP
00276 mp_err ec_group_set_secp160r1_fp(ECGroup *group);
00277 mp_err ec_group_set_nistp192_fp(ECGroup *group);
00278 mp_err ec_group_set_nistp224_fp(ECGroup *group);
00279 #endif
00280 
00281 #endif                                           /* __ecl_priv_h_ */