1/* LibTomCrypt, modular cryptographic library -- Tom St Denis
2 *
3 * LibTomCrypt is a library that provides various cryptographic
4 * algorithms in a highly modular and flexible manner.
5 *
6 * The library is free for all purposes without any express
7 * guarantee it works.
8 *
9 * Tom St Denis, tomstdenis@gmail.com, http://libtomcrypt.com
10 */
11
12/* Implements ECC over Z/pZ for curve y^2 = x^3 - 3x + b
13 *
14 * All curves taken from NIST recommendation paper of July 1999
15 * Available at http://csrc.nist.gov/cryptval/dss.htm
16 */
17#include "tomcrypt.h"
18
19/**
20  @file ltc_ecc_mulmod_timing.c
21  ECC Crypto, Tom St Denis
22*/
23
24#ifdef MECC
25
26#ifdef LTC_ECC_TIMING_RESISTANT
27
28/**
29   Perform a point multiplication  (timing resistant)
30   @param k    The scalar to multiply by
31   @param G    The base point
32   @param R    [out] Destination for kG
33   @param modulus  The modulus of the field the ECC curve is in
34   @param map      Boolean whether to map back to affine or not (1==map, 0 == leave in projective)
35   @return CRYPT_OK on success
36*/
37int ltc_ecc_mulmod(void *k, ecc_point *G, ecc_point *R, void *modulus, int map)
38{
39   ecc_point *tG, *M[3];
40   int        i, j, err;
41   void       *mu, *mp;
42   unsigned long buf;
43   int        first, bitbuf, bitcpy, bitcnt, mode, digidx;
44
45   LTC_ARGCHK(k       != NULL);
46   LTC_ARGCHK(G       != NULL);
47   LTC_ARGCHK(R       != NULL);
48   LTC_ARGCHK(modulus != NULL);
49
50   /* init montgomery reduction */
51   if ((err = mp_montgomery_setup(modulus, &mp)) != CRYPT_OK) {
52      return err;
53   }
54   if ((err = mp_init(&mu)) != CRYPT_OK) {
55      mp_montgomery_free(mp);
56      return err;
57   }
58   if ((err = mp_montgomery_normalization(mu, modulus)) != CRYPT_OK) {
59      mp_clear(mu);
60      mp_montgomery_free(mp);
61      return err;
62   }
63
64  /* alloc ram for window temps */
65  for (i = 0; i < 3; i++) {
66      M[i] = ltc_ecc_new_point();
67      if (M[i] == NULL) {
68         for (j = 0; j < i; j++) {
69             ltc_ecc_del_point(M[j]);
70         }
71         mp_clear(mu);
72         mp_montgomery_free(mp);
73         return CRYPT_MEM;
74      }
75  }
76
77   /* make a copy of G incase R==G */
78   tG = ltc_ecc_new_point();
79   if (tG == NULL)                                                                   { err = CRYPT_MEM; goto done; }
80
81   /* tG = G  and convert to montgomery */
82   if ((err = mp_mulmod(G->x, mu, modulus, tG->x)) != CRYPT_OK)                      { goto done; }
83   if ((err = mp_mulmod(G->y, mu, modulus, tG->y)) != CRYPT_OK)                      { goto done; }
84   if ((err = mp_mulmod(G->z, mu, modulus, tG->z)) != CRYPT_OK)                      { goto done; }
85   mp_clear(mu);
86   mu = NULL;
87
88   /* calc the M tab */
89   /* M[0] == G */
90   if ((err = mp_copy(tG->x, M[0]->x)) != CRYPT_OK)                                  { goto done; }
91   if ((err = mp_copy(tG->y, M[0]->y)) != CRYPT_OK)                                  { goto done; }
92   if ((err = mp_copy(tG->z, M[0]->z)) != CRYPT_OK)                                  { goto done; }
93   /* M[1] == 2G */
94   if ((err = ltc_mp.ecc_ptdbl(tG, M[1], modulus, mp)) != CRYPT_OK)                  { goto done; }
95
96   /* setup sliding window */
97   mode   = 0;
98   bitcnt = 1;
99   buf    = 0;
100   digidx = mp_get_digit_count(k) - 1;
101   bitcpy = bitbuf = 0;
102   first  = 1;
103
104   /* perform ops */
105   for (;;) {
106     /* grab next digit as required */
107      if (--bitcnt == 0) {
108         if (digidx == -1) {
109            break;
110         }
111         buf    = mp_get_digit(k, digidx);
112         bitcnt = (int) MP_DIGIT_BIT;
113         --digidx;
114      }
115
116      /* grab the next msb from the ltiplicand */
117      i = (buf >> (MP_DIGIT_BIT - 1)) & 1;
118      buf <<= 1;
119
120      if (mode == 0 && i == 0) {
121         /* dummy operations */
122         if ((err = ltc_mp.ecc_ptadd(M[0], M[1], M[2], modulus, mp)) != CRYPT_OK)    { goto done; }
123         if ((err = ltc_mp.ecc_ptdbl(M[1], M[2], modulus, mp)) != CRYPT_OK)          { goto done; }
124         continue;
125      }
126
127      if (mode == 0 && i == 1) {
128         mode = 1;
129         /* dummy operations */
130         if ((err = ltc_mp.ecc_ptadd(M[0], M[1], M[2], modulus, mp)) != CRYPT_OK)    { goto done; }
131         if ((err = ltc_mp.ecc_ptdbl(M[1], M[2], modulus, mp)) != CRYPT_OK)          { goto done; }
132         continue;
133      }
134
135      if ((err = ltc_mp.ecc_ptadd(M[0], M[1], M[i^1], modulus, mp)) != CRYPT_OK)     { goto done; }
136      if ((err = ltc_mp.ecc_ptdbl(M[i], M[i], modulus, mp)) != CRYPT_OK)             { goto done; }
137   }
138
139   /* copy result out */
140   if ((err = mp_copy(M[0]->x, R->x)) != CRYPT_OK)                                   { goto done; }
141   if ((err = mp_copy(M[0]->y, R->y)) != CRYPT_OK)                                   { goto done; }
142   if ((err = mp_copy(M[0]->z, R->z)) != CRYPT_OK)                                   { goto done; }
143
144   /* map R back from projective space */
145   if (map) {
146      err = ltc_ecc_map(R, modulus, mp);
147   } else {
148      err = CRYPT_OK;
149   }
150done:
151   if (mu != NULL) {
152      mp_clear(mu);
153   }
154   mp_montgomery_free(mp);
155   ltc_ecc_del_point(tG);
156   for (i = 0; i < 3; i++) {
157       ltc_ecc_del_point(M[i]);
158   }
159   return err;
160}
161
162#endif
163#endif
164/* $Source: /cvs/libtom/libtomcrypt/src/pk/ecc/ltc_ecc_mulmod_timing.c,v $ */
165/* $Revision: 1.11 $ */
166/* $Date: 2006/12/04 22:17:46 $ */
167
168