ltc_ecc_mul2add.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_mul2add.c
00039   ECC Crypto, Shamir's Trick, Tom St Denis
00040 */  
00041 
00042 #ifdef LTC_MECC
00043 
00044 #ifdef LTC_ECC_SHAMIR
00045 
00046 /** Computes kA*A + kB*B = C using Shamir's Trick
00047   @param A        First point to multiply
00048   @param kA       What to multiple A by
00049   @param B        Second point to multiply
00050   @param kB       What to multiple B by
00051   @param C        [out] Destination point (can overlap with A or B
00052   @param modulus  Modulus for curve 
00053   @return CRYPT_OK on success
00054 */ 
00055 int ltc_ecc_mul2add(ecc_point *A, void *kA,
00056                     ecc_point *B, void *kB,
00057                     ecc_point *C,
00058                          void *modulus)
00059 {
00060   ecc_point     precomp[16];
00061   unsigned       bitbufA, bitbufB, lenA, lenB, len, x, y, nA, nB, nibble;
00062   unsigned char tA[ECC_BUF_SIZE];
00063   unsigned char tB[ECC_BUF_SIZE];
00064   int            err, first;
00065   void          *mp, *mu;
00066  
00067   /* argchks */
00068   LTC_ARGCHK(A       != NULL);
00069   LTC_ARGCHK(B       != NULL);
00070   LTC_ARGCHK(C       != NULL);
00071   LTC_ARGCHK(kA      != NULL);
00072   LTC_ARGCHK(kB      != NULL);
00073   LTC_ARGCHK(modulus != NULL);
00074 
00075   /* get sizes */
00076   lenA = mp_unsigned_bin_size(kA);
00077   lenB = mp_unsigned_bin_size(kB);
00078   len  = MAX(lenA, lenB);
00079 
00080   /* sanity check */
00081   if ((lenA > ECC_BUF_SIZE) || (lenB > ECC_BUF_SIZE)) {
00082      err = CRYPT_INVALID_ARG;
00083      goto ERR_T;
00084   }
00085 
00086   /* extract and justify kA */
00087   mp_to_unsigned_bin(kA, (len - lenA) + tA);
00088 
00089   /* extract and justify kB */
00090   mp_to_unsigned_bin(kB, (len - lenB) + tB);
00091 
00092   /* allocate the table */
00093   for (x = 0; x < 16; x++) {
00094      precomp[x] = ltc_ecc_new_point(); //mp_init_multi FIXME
00095      if (precomp[x] == NULL) {
00096          for (y = 0; y < x; ++y) {
00097             ltc_ecc_del_point(precomp[y]);
00098          }
00099          err = CRYPT_MEM;
00100          goto ERR_T;
00101      }
00102   }
00103 
00104    /* init montgomery reduction */
00105    if ((err = mp_montgomery_setup(modulus, &mp)) != CRYPT_OK) {
00106       goto ERR_P;
00107    }
00108    if ((err = mp_init(&mu)) != CRYPT_OK) {
00109       goto ERR_MP;
00110    }
00111    if ((err = mp_montgomery_normalization(mu, modulus)) != CRYPT_OK) {
00112       goto ERR_MU;
00113    }
00114 
00115   /* copy ones ... */
00116   if ((err = mp_mulmod(A->x, mu, modulus, precomp[1]->x)) != CRYPT_OK)                                         { goto ERR_MU; }
00117   if ((err = mp_mulmod(A->y, mu, modulus, precomp[1]->y)) != CRYPT_OK)                                         { goto ERR_MU; }
00118   if ((err = mp_mulmod(A->z, mu, modulus, precomp[1]->z)) != CRYPT_OK)                                         { goto ERR_MU; }
00119 
00120   if ((err = mp_mulmod(B->x, mu, modulus, precomp[1<<2]->x)) != CRYPT_OK)                                      { goto ERR_MU; }
00121   if ((err = mp_mulmod(B->y, mu, modulus, precomp[1<<2]->y)) != CRYPT_OK)                                      { goto ERR_MU; }
00122   if ((err = mp_mulmod(B->z, mu, modulus, precomp[1<<2]->z)) != CRYPT_OK)                                      { goto ERR_MU; }
00123 
00124   /* precomp [i,0](A + B) table */
00125   if ((err = ltc_mp.ecc_ptdbl(precomp[1], precomp[2], modulus, mp)) != CRYPT_OK)                               { goto ERR_MU; }
00126   if ((err = ltc_mp.ecc_ptadd(precomp[1], precomp[2], precomp[3], modulus, mp)) != CRYPT_OK)                   { goto ERR_MU; }
00127 
00128   /* precomp [0,i](A + B) table */
00129   if ((err = ltc_mp.ecc_ptdbl(precomp[1<<2], precomp[2<<2], modulus, mp)) != CRYPT_OK)                         { goto ERR_MU; }
00130   if ((err = ltc_mp.ecc_ptadd(precomp[1<<2], precomp[2<<2], precomp[3<<2], modulus, mp)) != CRYPT_OK)          { goto ERR_MU; }
00131 
00132   /* precomp [i,j](A + B) table (i != 0, j != 0) */
00133   for (x = 1; x < 4; x++) {
00134      for (y = 1; y < 4; y++) {
00135         if ((err = ltc_mp.ecc_ptadd(precomp[x], precomp[(y<<2)], precomp[x+(y<<2)], modulus, mp)) != CRYPT_OK) { goto ERR_MU; }
00136      }
00137   }   
00138 
00139   nibble  = 3;
00140   first   = 1;
00141   bitbufA = tA[0];
00142   bitbufB = tB[0];
00143 
00144   /* for every byte of the multiplicands */
00145   for (x = -1;; ) {
00146      /* grab a nibble */
00147      if (++nibble == 4) {
00148         ++x; if (x == len) break;
00149         bitbufA = tA[x];
00150         bitbufB = tB[x];
00151         nibble  = 0;
00152      }
00153 
00154      /* extract two bits from both, shift/update */
00155      nA = (bitbufA >> 6) & 0x03;
00156      nB = (bitbufB >> 6) & 0x03;
00157      bitbufA = (bitbufA << 2) & 0xFF;   
00158      bitbufB = (bitbufB << 2) & 0xFF;   
00159 
00160      /* if both zero, if first, continue */
00161      if ((nA == 0) && (nB == 0) && (first == 1)) {
00162         continue;
00163      }
00164 
00165      /* double twice, only if this isn't the first */
00166      if (first == 0) {
00167         /* double twice */
00168         if ((err = ltc_mp.ecc_ptdbl(C, C, modulus, mp)) != CRYPT_OK)                  { goto ERR_MU; }
00169         if ((err = ltc_mp.ecc_ptdbl(C, C, modulus, mp)) != CRYPT_OK)                  { goto ERR_MU; }
00170      }
00171 
00172      /* if not both zero */
00173      if ((nA != 0) || (nB != 0)) {
00174         if (first == 1) {
00175            /* if first, copy from table */
00176            first = 0;
00177            if ((err = mp_copy(precomp[nA + (nB<<2)]->x, C->x)) != CRYPT_OK)           { goto ERR_MU; }
00178            if ((err = mp_copy(precomp[nA + (nB<<2)]->y, C->y)) != CRYPT_OK)           { goto ERR_MU; }
00179            if ((err = mp_copy(precomp[nA + (nB<<2)]->z, C->z)) != CRYPT_OK)           { goto ERR_MU; }
00180         } else {
00181            /* if not first, add from table */
00182            if ((err = ltc_mp.ecc_ptadd(C, precomp[nA + (nB<<2)], C, modulus, mp)) != CRYPT_OK) { goto ERR_MU; }
00183         }
00184      }
00185   }
00186 
00187   /* reduce to affine */
00188   err = ltc_ecc_map(C, modulus, mp);
00189 
00190   /* clean up */
00191 ERR_MU:
00192    mp_clear(mu);
00193 ERR_MP:
00194    mp_montgomery_free(mp);
00195 ERR_P:
00196    for (x = 0; x < 16; x++) {
00197        ltc_ecc_del_point(precomp[x]);
00198    }
00199 ERR_T:
00200 #ifdef LTC_CLEAN_STACK
00201    zeromem(tA, ECC_BUF_SIZE);
00202    zeromem(tB, ECC_BUF_SIZE);
00203 #endif
00204    XFREE(tA);
00205    XFREE(tB);
00206 
00207    return err;
00208 }
00209 
00210 #endif
00211 #endif
00212 
00213 /* $Source: /cvs/libtom/libtomcrypt/src/pk/ecc/ltc_ecc_mul2add.c,v $ */
00214 /* $Revision: 1.8 $ */
00215 /* $Date: 2007/05/12 14:32:35 $ */