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_mul2add.c
21  ECC Crypto, Shamir's Trick, Tom St Denis
22*/
23
24#ifdef MECC
25
26#ifdef LTC_ECC_SHAMIR
27
28/** Computes kA*A + kB*B = C using Shamir's Trick
29  @param A        First point to multiply
30  @param kA       What to multiple A by
31  @param B        Second point to multiply
32  @param kB       What to multiple B by
33  @param C        [out] Destination point (can overlap with A or B
34  @param modulus  Modulus for curve
35  @return CRYPT_OK on success
36*/
37int ltc_ecc_mul2add(ecc_point *A, void *kA,
38                    ecc_point *B, void *kB,
39                    ecc_point *C,
40                         void *modulus)
41{
42  ecc_point     *precomp[16];
43  unsigned       bitbufA, bitbufB, lenA, lenB, len, x, y, nA, nB, nibble;
44  unsigned char *tA, *tB;
45  int            err, first;
46  void          *mp, *mu;
47
48  /* argchks */
49  LTC_ARGCHK(A       != NULL);
50  LTC_ARGCHK(B       != NULL);
51  LTC_ARGCHK(C       != NULL);
52  LTC_ARGCHK(kA      != NULL);
53  LTC_ARGCHK(kB      != NULL);
54  LTC_ARGCHK(modulus != NULL);
55
56  /* allocate memory */
57  tA = XCALLOC(1, ECC_BUF_SIZE);
58  if (tA == NULL) {
59     return CRYPT_MEM;
60  }
61  tB = XCALLOC(1, ECC_BUF_SIZE);
62  if (tB == NULL) {
63     XFREE(tA);
64     return CRYPT_MEM;
65  }
66
67  /* get sizes */
68  lenA = mp_unsigned_bin_size(kA);
69  lenB = mp_unsigned_bin_size(kB);
70  len  = MAX(lenA, lenB);
71
72  /* sanity check */
73  if ((lenA > ECC_BUF_SIZE) || (lenB > ECC_BUF_SIZE)) {
74     err = CRYPT_INVALID_ARG;
75     goto ERR_T;
76  }
77
78  /* extract and justify kA */
79  mp_to_unsigned_bin(kA, (len - lenA) + tA);
80
81  /* extract and justify kB */
82  mp_to_unsigned_bin(kB, (len - lenB) + tB);
83
84  /* allocate the table */
85  for (x = 0; x < 16; x++) {
86     precomp[x] = ltc_ecc_new_point();
87     if (precomp[x] == NULL) {
88         for (y = 0; y < x; ++y) {
89            ltc_ecc_del_point(precomp[y]);
90         }
91         err = CRYPT_MEM;
92         goto ERR_T;
93     }
94  }
95
96   /* init montgomery reduction */
97   if ((err = mp_montgomery_setup(modulus, &mp)) != CRYPT_OK) {
98      goto ERR_P;
99   }
100   if ((err = mp_init(&mu)) != CRYPT_OK) {
101      goto ERR_MP;
102   }
103   if ((err = mp_montgomery_normalization(mu, modulus)) != CRYPT_OK) {
104      goto ERR_MU;
105   }
106
107  /* copy ones ... */
108  if ((err = mp_mulmod(A->x, mu, modulus, precomp[1]->x)) != CRYPT_OK)                                         { goto ERR_MU; }
109  if ((err = mp_mulmod(A->y, mu, modulus, precomp[1]->y)) != CRYPT_OK)                                         { goto ERR_MU; }
110  if ((err = mp_mulmod(A->z, mu, modulus, precomp[1]->z)) != CRYPT_OK)                                         { goto ERR_MU; }
111
112  if ((err = mp_mulmod(B->x, mu, modulus, precomp[1<<2]->x)) != CRYPT_OK)                                      { goto ERR_MU; }
113  if ((err = mp_mulmod(B->y, mu, modulus, precomp[1<<2]->y)) != CRYPT_OK)                                      { goto ERR_MU; }
114  if ((err = mp_mulmod(B->z, mu, modulus, precomp[1<<2]->z)) != CRYPT_OK)                                      { goto ERR_MU; }
115
116  /* precomp [i,0](A + B) table */
117  if ((err = ltc_mp.ecc_ptdbl(precomp[1], precomp[2], modulus, mp)) != CRYPT_OK)                               { goto ERR_MU; }
118  if ((err = ltc_mp.ecc_ptadd(precomp[1], precomp[2], precomp[3], modulus, mp)) != CRYPT_OK)                   { goto ERR_MU; }
119
120  /* precomp [0,i](A + B) table */
121  if ((err = ltc_mp.ecc_ptdbl(precomp[1<<2], precomp[2<<2], modulus, mp)) != CRYPT_OK)                         { goto ERR_MU; }
122  if ((err = ltc_mp.ecc_ptadd(precomp[1<<2], precomp[2<<2], precomp[3<<2], modulus, mp)) != CRYPT_OK)          { goto ERR_MU; }
123
124  /* precomp [i,j](A + B) table (i != 0, j != 0) */
125  for (x = 1; x < 4; x++) {
126     for (y = 1; y < 4; y++) {
127        if ((err = ltc_mp.ecc_ptadd(precomp[x], precomp[(y<<2)], precomp[x+(y<<2)], modulus, mp)) != CRYPT_OK) { goto ERR_MU; }
128     }
129  }
130
131  nibble  = 3;
132  first   = 1;
133  bitbufA = tA[0];
134  bitbufB = tB[0];
135
136  /* for every byte of the multiplicands */
137  for (x = -1;; ) {
138     /* grab a nibble */
139     if (++nibble == 4) {
140        ++x; if (x == len) break;
141        bitbufA = tA[x];
142        bitbufB = tB[x];
143        nibble  = 0;
144     }
145
146     /* extract two bits from both, shift/update */
147     nA = (bitbufA >> 6) & 0x03;
148     nB = (bitbufB >> 6) & 0x03;
149     bitbufA = (bitbufA << 2) & 0xFF;
150     bitbufB = (bitbufB << 2) & 0xFF;
151
152     /* if both zero, if first, continue */
153     if ((nA == 0) && (nB == 0) && (first == 1)) {
154        continue;
155     }
156
157     /* double twice, only if this isn't the first */
158     if (first == 0) {
159        /* double twice */
160        if ((err = ltc_mp.ecc_ptdbl(C, C, modulus, mp)) != CRYPT_OK)                  { goto ERR_MU; }
161        if ((err = ltc_mp.ecc_ptdbl(C, C, modulus, mp)) != CRYPT_OK)                  { goto ERR_MU; }
162     }
163
164     /* if not both zero */
165     if ((nA != 0) || (nB != 0)) {
166        if (first == 1) {
167           /* if first, copy from table */
168           first = 0;
169           if ((err = mp_copy(precomp[nA + (nB<<2)]->x, C->x)) != CRYPT_OK)           { goto ERR_MU; }
170           if ((err = mp_copy(precomp[nA + (nB<<2)]->y, C->y)) != CRYPT_OK)           { goto ERR_MU; }
171           if ((err = mp_copy(precomp[nA + (nB<<2)]->z, C->z)) != CRYPT_OK)           { goto ERR_MU; }
172        } else {
173           /* if not first, add from table */
174           if ((err = ltc_mp.ecc_ptadd(C, precomp[nA + (nB<<2)], C, modulus, mp)) != CRYPT_OK) { goto ERR_MU; }
175        }
176     }
177  }
178
179  /* reduce to affine */
180  err = ltc_ecc_map(C, modulus, mp);
181
182  /* clean up */
183ERR_MU:
184   mp_clear(mu);
185ERR_MP:
186   mp_montgomery_free(mp);
187ERR_P:
188   for (x = 0; x < 16; x++) {
189       ltc_ecc_del_point(precomp[x]);
190   }
191ERR_T:
192#ifdef LTC_CLEAN_STACK
193   zeromem(tA, ECC_BUF_SIZE);
194   zeromem(tB, ECC_BUF_SIZE);
195#endif
196   XFREE(tA);
197   XFREE(tB);
198
199   return err;
200}
201
202#endif
203#endif
204
205/* $Source: /cvs/libtom/libtomcrypt/src/pk/ecc/ltc_ecc_mul2add.c,v $ */
206/* $Revision: 1.6 $ */
207/* $Date: 2006/12/04 05:07:59 $ */
208