ltc_ecc_mulmod_timing.c

00001 /*
00002 MiniTLS - A super trimmed down TLS/SSL Library for embedded devices
00003 Author: Donatien Garnier
00004 Copyright (C) 2013-2014 AppNearMe Ltd
00005 
00006 This program is free software; you can redistribute it and/or
00007 modify it under the terms of the GNU General Public License
00008 as published by the Free Software Foundation; either version 2
00009 of the License, or (at your option) any later version.
00010 
00011 This program is distributed in the hope that it will be useful,
00012 but WITHOUT ANY WARRANTY; without even the implied warranty of
00013 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
00014 GNU General Public License for more details.
00015 
00016 You should have received a copy of the GNU General Public License
00017 along with this program; if not, write to the Free Software
00018 Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301, USA.
00019 *//* LibTomCrypt, modular cryptographic library -- Tom St Denis
00020  *
00021  * LibTomCrypt is a library that provides various cryptographic
00022  * algorithms in a highly modular and flexible manner.
00023  *
00024  * The library is free for all purposes without any express
00025  * guarantee it works.
00026  *
00027  * Tom St Denis, tomstdenis@gmail.com, http://libtom.org
00028  */
00029 
00030 /* Implements ECC over Z/pZ for curve y^2 = x^3 - 3x + b
00031  *
00032  * All curves taken from NIST recommendation paper of July 1999
00033  * Available at http://csrc.nist.gov/cryptval/dss.htm
00034  */
00035 #include "ltc.h"
00036 
00037 /**
00038   @file ltc_ecc_mulmod_timing.c
00039   ECC Crypto, Tom St Denis
00040 */  
00041 
00042 #ifdef LTC_MECC
00043 
00044 #ifdef LTC_ECC_TIMING_RESISTANT
00045 
00046 /**
00047    Perform a point multiplication  (timing resistant)
00048    @param k    The scalar to multiply by
00049    @param G    The base point
00050    @param R    [out] Destination for kG
00051    @param modulus  The modulus of the field the ECC curve is in
00052    @param map      Boolean whether to map back to affine or not (1==map, 0 == leave in projective)
00053    @return MINITLS_OK on success
00054 */
00055 int ltc_ecc_mulmod(void *k, ecc_point *G, ecc_point *R, void *modulus, int map)
00056 {
00057    ecc_point tG, M[3];
00058    int        i, j, err;
00059    fp_int     mu;
00060    fp_digit   mp;
00061    unsigned long buf;
00062    int        first, bitbuf, bitcpy, bitcnt, mode, digidx;
00063 
00064    LTC_ARGCHK(k       != NULL);
00065    LTC_ARGCHK(G       != NULL);
00066    LTC_ARGCHK(R       != NULL);
00067    LTC_ARGCHK(modulus != NULL);
00068 
00069    /* init montgomery reduction */
00070    if ((err = mp_montgomery_setup(modulus, &mp)) != MINITLS_OK) {
00071       return err;
00072    }
00073    /*if ((err =*/ mp_init(&mu);/*) != MINITLS_OK) {
00074       mp_montgomery_free(&mp);
00075       return err;
00076    }*/
00077    /*if ((err =*/ mp_montgomery_normalization(&mu, modulus);/*) != MINITLS_OK) {
00078       mp_clear(&mu);
00079       mp_montgomery_free(&mp);
00080       return err;
00081    }*/
00082 
00083   /* alloc ram for window temps */
00084   for (i = 0; i < 3; i++) {
00085     if (mp_init_multi(&M[i].x, &M[i].y, &M[i].z, NULL) != MINITLS_OK)
00086     {
00087          for (j = 0; j < i; j++) {
00088            mp_clear_multi(&M[j].x, &M[j].y, &M[j].z, NULL);
00089          }
00090          mp_clear(&mu);
00091          mp_montgomery_free(&mp);
00092          return MINITLS_ERR_MEMORY;
00093       }
00094   }
00095 
00096    /* make a copy of G incase R==G */
00097    if (mp_init_multi(&tG.x, &tG.y, &tG.z, NULL) != MINITLS_OK)                      { err = MINITLS_ERR_MEMORY; goto done; }
00098 
00099    /* tG = G  and convert to montgomery */
00100    if ((err = mp_mulmod(&G->x, &mu, modulus, &tG.x)) != MINITLS_OK)                      { goto done; }
00101    if ((err = mp_mulmod(&G->y, &mu, modulus, &tG.y)) != MINITLS_OK)                      { goto done; }
00102    if ((err = mp_mulmod(&G->z, &mu, modulus, &tG.z)) != MINITLS_OK)                      { goto done; }
00103    mp_clear(&mu);
00104    //mu = NULL;
00105    
00106    /* calc the M tab */
00107    /* M[0] == G */
00108    /*if ((err =*/ mp_copy(&tG.x, &M[0].x); /*) != MINITLS_OK)                                  { goto done; }*/
00109    /*if ((err =*/ mp_copy(&tG.y, &M[0].y); /*) != MINITLS_OK)                                  { goto done; }*/
00110    /*if ((err =*/ mp_copy(&tG.z, &M[0].z); /*) != MINITLS_OK)                                  { goto done; }*/
00111    /* M[1] == 2G */
00112    if ((err = ltc_ecc_projective_dbl_point(&tG, &M[1], modulus, &mp)) != MINITLS_OK)                  { goto done; }
00113 
00114    /* setup sliding window */
00115    mode   = 0;
00116    bitcnt = 1;
00117    buf    = 0;
00118    digidx = mp_get_digit_count(k) - 1;
00119    bitcpy = bitbuf = 0;
00120    first  = 1;
00121 
00122    /* perform ops */
00123    for (;;) {
00124      /* grab next digit as required */
00125       if (--bitcnt == 0) {
00126          if (digidx == -1) {
00127             break;
00128          }
00129          buf    = mp_get_digit(k, digidx);
00130          bitcnt = (int) MP_DIGIT_BIT;
00131          --digidx;
00132       }
00133 
00134       /* grab the next msb from the ltiplicand */
00135       i = (buf >> (MP_DIGIT_BIT - 1)) & 1;
00136       buf <<= 1;
00137 
00138       if (mode == 0 && i == 0) {
00139          /* dummy operations */
00140          if ((err = ltc_ecc_projective_add_point(&M[0], &M[1], &M[2], modulus, &mp)) != MINITLS_OK)    { goto done; }
00141          if ((err = ltc_ecc_projective_dbl_point(&M[1], &M[2], modulus, &mp)) != MINITLS_OK)          { goto done; }
00142          continue;
00143       }
00144 
00145       if (mode == 0 && i == 1) {
00146          mode = 1;
00147          /* dummy operations */
00148          if ((err = ltc_ecc_projective_add_point(&M[0], &M[1], &M[2], modulus, &mp)) != MINITLS_OK)    { goto done; }
00149          if ((err = ltc_ecc_projective_dbl_point(&M[1], &M[2], modulus, &mp)) != MINITLS_OK)          { goto done; }
00150          continue;
00151       }
00152 
00153       if ((err = ltc_ecc_projective_add_point(&M[0], &M[1], &M[i^1], modulus, &mp)) != MINITLS_OK)     { goto done; }
00154       if ((err = ltc_ecc_projective_dbl_point(&M[i], &M[i], modulus, &mp)) != MINITLS_OK)             { goto done; }
00155    }
00156 
00157    /* copy result out */
00158    /*if ((err =*/ mp_copy(&M[0].x, &R->x);/*) != MINITLS_OK)                                   { goto done; }*/
00159    /*if ((err =*/ mp_copy(&M[0].y, &R->y);/*) != MINITLS_OK)                                   { goto done; }*/
00160    /*if ((err =*/ mp_copy(&M[0].z, &R->z);/*) != MINITLS_OK)                                   { goto done; }*/
00161 
00162    /* map R back from projective space */
00163    if (map) {
00164       err = ltc_ecc_map(R, modulus, &mp);
00165    } else {
00166       err = MINITLS_OK;
00167    }
00168 done:
00169    //if (mu != NULL) {
00170       mp_clear(&mu);
00171    //}
00172    mp_montgomery_free(&mp);
00173    mp_clear_multi(&tG.x, &tG.y, &tG.z, NULL);
00174    for (i = 0; i < 3; i++) {
00175      mp_clear_multi(&M[i].x, &M[i].y, &M[i].z, NULL);
00176    }
00177    return err;
00178 }
00179 
00180 #endif
00181 #endif
00182 /* $Source: /cvs/libtom/libtomcrypt/src/pk/ecc/ltc_ecc_mulmod_timing.c,v $ */
00183 /* $Revision: 1.13 $ */
00184 /* $Date: 2007/05/12 14:32:35 $ */
00185