1 /*

     2  * Copyright (c) 2007, 2011, Oracle and/or its affiliates. All rights reserved.

     3  * Use is subject to license terms.

     4  *

     5  * This library is free software; you can redistribute it and/or

     6  * modify it under the terms of the GNU Lesser General Public

     7  * License as published by the Free Software Foundation; either

     8  * version 2.1 of the License, or (at your option) any later version.

     9  *

    10  * This library is distributed in the hope that it will be useful,

    11  * but WITHOUT ANY WARRANTY; without even the implied warranty of

    12  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU

    13  * Lesser General Public License for more details.

    14  *

    15  * You should have received a copy of the GNU Lesser General Public License

    16  * along with this library; if not, write to the Free Software Foundation,

    17  * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.

    18  *

    19  * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA

    20  * or visit www.oracle.com if you need additional information or have any

    21  * questions.

    22  */

    23 

    24 /* *********************************************************************

    25  *

    26  * The Original Code is the elliptic curve math library.

    27  *

    28  * The Initial Developer of the Original Code is

    29  * Sun Microsystems, Inc.

    30  * Portions created by the Initial Developer are Copyright (C) 2003

    31  * the Initial Developer. All Rights Reserved.

    32  *

    33  * Contributor(s):

    34  *   Stephen Fung <fungstep@hotmail.com> and

    35  *   Douglas Stebila <douglas@stebila.ca>, Sun Microsystems Laboratories

    36  *

    37  *********************************************************************** */

    38 

    39 #ifndef _ECL_PRIV_H

    40 #define _ECL_PRIV_H

    41 

    42 #include "ecl.h"

    43 #include "mpi.h"

    44 #include "mplogic.h"

    45 

    46 /* MAX_FIELD_SIZE_DIGITS is the maximum size of field element supported */

    47 /* the following needs to go away... */

    48 #if defined(MP_USE_LONG_LONG_DIGIT) || defined(MP_USE_LONG_DIGIT)

    49 #define ECL_SIXTY_FOUR_BIT

    50 #else

    51 #define ECL_THIRTY_TWO_BIT

    52 #endif

    53 

    54 #define ECL_CURVE_DIGITS(curve_size_in_bits) \

    55         (((curve_size_in_bits)+(sizeof(mp_digit)*8-1))/(sizeof(mp_digit)*8))

    56 #define ECL_BITS (sizeof(mp_digit)*8)

    57 #define ECL_MAX_FIELD_SIZE_DIGITS (80/sizeof(mp_digit))

    58 

    59 /* Gets the i'th bit in the binary representation of a. If i >= length(a),

    60  * then return 0. (The above behaviour differs from mpl_get_bit, which

    61  * causes an error if i >= length(a).) */

    62 #define MP_GET_BIT(a, i) \

    63         ((i) >= mpl_significant_bits((a))) ? 0 : mpl_get_bit((a), (i))

    64 

    65 #if !defined(MP_NO_MP_WORD) && !defined(MP_NO_ADD_WORD)

    66 #define MP_ADD_CARRY(a1, a2, s, cin, cout)   \

    67     { mp_word w; \

    68     w = ((mp_word)(cin)) + (a1) + (a2); \

    69     s = ACCUM(w); \

    70     cout = CARRYOUT(w); }

    71 

    72 /* Handle case when carry-in value is zero */

    73 #define MP_ADD_CARRY_ZERO(a1, a2, s, cout)   \

    74     MP_ADD_CARRY(a1, a2, s, 0, cout);

    75 

    76 #define MP_SUB_BORROW(a1, a2, s, bin, bout)   \

    77     { mp_word w; \

    78     w = ((mp_word)(a1)) - (a2) - (bin); \

    79     s = ACCUM(w); \

    80     bout = (w >> MP_DIGIT_BIT) & 1; }

    81 

    82 #else

    83 /* NOTE,

    84  * cin and cout could be the same variable.

    85  * bin and bout could be the same variable.

    86  * a1 or a2 and s could be the same variable.

    87  * don't trash those outputs until their respective inputs have

    88  * been read. */

    89 #define MP_ADD_CARRY(a1, a2, s, cin, cout)   \

    90     { mp_digit tmp,sum; \

    91     tmp = (a1); \

    92     sum = tmp + (a2); \

    93     tmp = (sum < tmp);                     /* detect overflow */ \

    94     s = sum += (cin); \

    95     cout = tmp + (sum < (cin)); }

    96 

    97 /* Handle case when carry-in value is zero */

    98 #define MP_ADD_CARRY_ZERO(a1, a2, s, cout)   \

    99     { mp_digit tmp,sum; \

   100     tmp = (a1); \

   101     sum = tmp + (a2); \

   102     tmp = (sum < tmp);                     /* detect overflow */ \

   103     s = sum; \

   104     cout = tmp; }

   105 

   106 #define MP_SUB_BORROW(a1, a2, s, bin, bout)   \

   107     { mp_digit tmp; \

   108     tmp = (a1); \

   109     s = tmp - (a2); \

   110     tmp = (s > tmp);                    /* detect borrow */ \

   111     if ((bin) && !s--) tmp++;   \

   112     bout = tmp; }

   113 #endif

   114 

   115 

   116 struct GFMethodStr;

   117 typedef struct GFMethodStr GFMethod;

   118 struct GFMethodStr {

   119         /* Indicates whether the structure was constructed from dynamic memory

   120          * or statically created. */

   121         int constructed;

   122         /* Irreducible that defines the field. For prime fields, this is the

   123          * prime p. For binary polynomial fields, this is the bitstring

   124          * representation of the irreducible polynomial. */

   125         mp_int irr;

   126         /* For prime fields, the value irr_arr[0] is the number of bits in the

   127          * field. For binary polynomial fields, the irreducible polynomial

   128          * f(t) is represented as an array of unsigned int[], where f(t) is

   129          * of the form: f(t) = t^p[0] + t^p[1] + ... + t^p[4] where m = p[0]

   130          * > p[1] > ... > p[4] = 0. */

   131         unsigned int irr_arr[5];

   132         /* Field arithmetic methods. All methods (except field_enc and

   133          * field_dec) are assumed to take field-encoded parameters and return

   134          * field-encoded values. All methods (except field_enc and field_dec)

   135          * are required to be implemented. */

   136         mp_err (*field_add) (const mp_int *a, const mp_int *b, mp_int *r,

   137                                                  const GFMethod *meth);

   138         mp_err (*field_neg) (const mp_int *a, mp_int *r, const GFMethod *meth);

   139         mp_err (*field_sub) (const mp_int *a, const mp_int *b, mp_int *r,

   140                                                  const GFMethod *meth);

   141         mp_err (*field_mod) (const mp_int *a, mp_int *r, const GFMethod *meth);

   142         mp_err (*field_mul) (const mp_int *a, const mp_int *b, mp_int *r,

   143                                                  const GFMethod *meth);

   144         mp_err (*field_sqr) (const mp_int *a, mp_int *r, const GFMethod *meth);

   145         mp_err (*field_div) (const mp_int *a, const mp_int *b, mp_int *r,

   146                                                  const GFMethod *meth);

   147         mp_err (*field_enc) (const mp_int *a, mp_int *r, const GFMethod *meth);

   148         mp_err (*field_dec) (const mp_int *a, mp_int *r, const GFMethod *meth);

   149         /* Extra storage for implementation-specific data.  Any memory

   150          * allocated to these extra fields will be cleared by extra_free. */

   151         void *extra1;

   152         void *extra2;

   153         void (*extra_free) (GFMethod *meth);

   154 };

   155 

   156 /* Construct generic GFMethods. */

   157 GFMethod *GFMethod_consGFp(const mp_int *irr);

   158 GFMethod *GFMethod_consGFp_mont(const mp_int *irr);

   159 GFMethod *GFMethod_consGF2m(const mp_int *irr,

   160                                                         const unsigned int irr_arr[5]);

   161 /* Free the memory allocated (if any) to a GFMethod object. */

   162 void GFMethod_free(GFMethod *meth);

   163 

   164 struct ECGroupStr {

   165         /* Indicates whether the structure was constructed from dynamic memory

   166          * or statically created. */

   167         int constructed;

   168         /* Field definition and arithmetic. */

   169         GFMethod *meth;

   170         /* Textual representation of curve name, if any. */

   171         char *text;

   172 #ifdef _KERNEL

   173         int text_len;

   174 #endif

   175         /* Curve parameters, field-encoded. */

   176         mp_int curvea, curveb;

   177         /* x and y coordinates of the base point, field-encoded. */

   178         mp_int genx, geny;

   179         /* Order and cofactor of the base point. */

   180         mp_int order;

   181         int cofactor;

   182         /* Point arithmetic methods. All methods are assumed to take

   183          * field-encoded parameters and return field-encoded values. All

   184          * methods (except base_point_mul and points_mul) are required to be

   185          * implemented. */

   186         mp_err (*point_add) (const mp_int *px, const mp_int *py,

   187                                                  const mp_int *qx, const mp_int *qy, mp_int *rx,

   188                                                  mp_int *ry, const ECGroup *group);

   189         mp_err (*point_sub) (const mp_int *px, const mp_int *py,

   190                                                  const mp_int *qx, const mp_int *qy, mp_int *rx,

   191                                                  mp_int *ry, const ECGroup *group);

   192         mp_err (*point_dbl) (const mp_int *px, const mp_int *py, mp_int *rx,

   193                                                  mp_int *ry, const ECGroup *group);

   194         mp_err (*point_mul) (const mp_int *n, const mp_int *px,

   195                                                  const mp_int *py, mp_int *rx, mp_int *ry,

   196                                                  const ECGroup *group);

   197         mp_err (*base_point_mul) (const mp_int *n, mp_int *rx, mp_int *ry,

   198                                                           const ECGroup *group);

   199         mp_err (*points_mul) (const mp_int *k1, const mp_int *k2,

   200                                                   const mp_int *px, const mp_int *py, mp_int *rx,

   201                                                   mp_int *ry, const ECGroup *group);

   202         mp_err (*validate_point) (const mp_int *px, const mp_int *py, const ECGroup *group);

   203         /* Extra storage for implementation-specific data.  Any memory

   204          * allocated to these extra fields will be cleared by extra_free. */

   205         void *extra1;

   206         void *extra2;

   207         void (*extra_free) (ECGroup *group);

   208 };

   209 

   210 /* Wrapper functions for generic prime field arithmetic. */

   211 mp_err ec_GFp_add(const mp_int *a, const mp_int *b, mp_int *r,

   212                                   const GFMethod *meth);

   213 mp_err ec_GFp_neg(const mp_int *a, mp_int *r, const GFMethod *meth);

   214 mp_err ec_GFp_sub(const mp_int *a, const mp_int *b, mp_int *r,

   215                                   const GFMethod *meth);

   216 

   217 /* fixed length in-line adds. Count is in words */

   218 mp_err ec_GFp_add_3(const mp_int *a, const mp_int *b, mp_int *r,

   219                                   const GFMethod *meth);

   220 mp_err ec_GFp_add_4(const mp_int *a, const mp_int *b, mp_int *r,

   221                                   const GFMethod *meth);

   222 mp_err ec_GFp_add_5(const mp_int *a, const mp_int *b, mp_int *r,

   223                                   const GFMethod *meth);

   224 mp_err ec_GFp_add_6(const mp_int *a, const mp_int *b, mp_int *r,

   225                                   const GFMethod *meth);

   226 mp_err ec_GFp_sub_3(const mp_int *a, const mp_int *b, mp_int *r,

   227                                   const GFMethod *meth);

   228 mp_err ec_GFp_sub_4(const mp_int *a, const mp_int *b, mp_int *r,

   229                                   const GFMethod *meth);

   230 mp_err ec_GFp_sub_5(const mp_int *a, const mp_int *b, mp_int *r,

   231                                   const GFMethod *meth);

   232 mp_err ec_GFp_sub_6(const mp_int *a, const mp_int *b, mp_int *r,

   233                                   const GFMethod *meth);

   234 

   235 mp_err ec_GFp_mod(const mp_int *a, mp_int *r, const GFMethod *meth);

   236 mp_err ec_GFp_mul(const mp_int *a, const mp_int *b, mp_int *r,

   237                                   const GFMethod *meth);

   238 mp_err ec_GFp_sqr(const mp_int *a, mp_int *r, const GFMethod *meth);

   239 mp_err ec_GFp_div(const mp_int *a, const mp_int *b, mp_int *r,

   240                                   const GFMethod *meth);

   241 /* Wrapper functions for generic binary polynomial field arithmetic. */

   242 mp_err ec_GF2m_add(const mp_int *a, const mp_int *b, mp_int *r,

   243                                    const GFMethod *meth);

   244 mp_err ec_GF2m_neg(const mp_int *a, mp_int *r, const GFMethod *meth);

   245 mp_err ec_GF2m_mod(const mp_int *a, mp_int *r, const GFMethod *meth);

   246 mp_err ec_GF2m_mul(const mp_int *a, const mp_int *b, mp_int *r,

   247                                    const GFMethod *meth);

   248 mp_err ec_GF2m_sqr(const mp_int *a, mp_int *r, const GFMethod *meth);

   249 mp_err ec_GF2m_div(const mp_int *a, const mp_int *b, mp_int *r,

   250                                    const GFMethod *meth);

   251 

   252 /* Montgomery prime field arithmetic. */

   253 mp_err ec_GFp_mul_mont(const mp_int *a, const mp_int *b, mp_int *r,

   254                                            const GFMethod *meth);

   255 mp_err ec_GFp_sqr_mont(const mp_int *a, mp_int *r, const GFMethod *meth);

   256 mp_err ec_GFp_div_mont(const mp_int *a, const mp_int *b, mp_int *r,

   257                                            const GFMethod *meth);

   258 mp_err ec_GFp_enc_mont(const mp_int *a, mp_int *r, const GFMethod *meth);

   259 mp_err ec_GFp_dec_mont(const mp_int *a, mp_int *r, const GFMethod *meth);

   260 void ec_GFp_extra_free_mont(GFMethod *meth);

   261 

   262 /* point multiplication */

   263 mp_err ec_pts_mul_basic(const mp_int *k1, const mp_int *k2,

   264                                                 const mp_int *px, const mp_int *py, mp_int *rx,

   265                                                 mp_int *ry, const ECGroup *group);

   266 mp_err ec_pts_mul_simul_w2(const mp_int *k1, const mp_int *k2,

   267                                                    const mp_int *px, const mp_int *py, mp_int *rx,

   268                                                    mp_int *ry, const ECGroup *group);

   269 

   270 /* Computes the windowed non-adjacent-form (NAF) of a scalar. Out should

   271  * be an array of signed char's to output to, bitsize should be the number

   272  * of bits of out, in is the original scalar, and w is the window size.

   273  * NAF is discussed in the paper: D. Hankerson, J. Hernandez and A.

   274  * Menezes, "Software implementation of elliptic curve cryptography over

   275  * binary fields", Proc. CHES 2000. */

   276 mp_err ec_compute_wNAF(signed char *out, int bitsize, const mp_int *in,

   277                                            int w);

   278 

   279 /* Optimized field arithmetic */

   280 mp_err ec_group_set_gfp192(ECGroup *group, ECCurveName);

   281 mp_err ec_group_set_gfp224(ECGroup *group, ECCurveName);

   282 mp_err ec_group_set_gfp256(ECGroup *group, ECCurveName);

   283 mp_err ec_group_set_gfp384(ECGroup *group, ECCurveName);

   284 mp_err ec_group_set_gfp521(ECGroup *group, ECCurveName);

   285 mp_err ec_group_set_gf2m163(ECGroup *group, ECCurveName name);

   286 mp_err ec_group_set_gf2m193(ECGroup *group, ECCurveName name);

   287 mp_err ec_group_set_gf2m233(ECGroup *group, ECCurveName name);

   288 

   289 /* Optimized floating-point arithmetic */

   290 #ifdef ECL_USE_FP

   291 mp_err ec_group_set_secp160r1_fp(ECGroup *group);

   292 mp_err ec_group_set_nistp192_fp(ECGroup *group);

   293 mp_err ec_group_set_nistp224_fp(ECGroup *group);

   294 #endif

   295 

   296 #endif /* _ECL_PRIV_H */