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.c
21 ECC Crypto, Tom St Denis
22 */
23
24 #ifdef MECC
25 #ifndef LTC_ECC_TIMING_RESISTANT
26
27 /* size of sliding window, don't change this! */
28 #define WINSIZE 4
29
30 /**
31 Perform a point multiplication
32 @param k The scalar to multiply by
33 @param G The base point
34 @param R [out] Destination for kG
35 @param modulus The modulus of the field the ECC curve is in
36 @param map Boolean whether to map back to affine or not (1==map, 0 == leave in projective)
37 @return CRYPT_OK on success
38 */
ltc_ecc_mulmod(void * k,ecc_point * G,ecc_point * R,void * modulus,int map)39 int ltc_ecc_mulmod(void *k, ecc_point *G, ecc_point *R, void *modulus, int map)
40 {
41 ecc_point *tG, *M[8];
42 int i, j, err;
43 void *mu, *mp;
44 unsigned long buf;
45 int first, bitbuf, bitcpy, bitcnt, mode, digidx;
46
47 LTC_ARGCHK(k != NULL);
48 LTC_ARGCHK(G != NULL);
49 LTC_ARGCHK(R != NULL);
50 LTC_ARGCHK(modulus != NULL);
51
52 /* init montgomery reduction */
53 if ((err = mp_montgomery_setup(modulus, &mp)) != CRYPT_OK) {
54 return err;
55 }
56 if ((err = mp_init(&mu)) != CRYPT_OK) {
57 mp_montgomery_free(mp);
58 return err;
59 }
60 if ((err = mp_montgomery_normalization(mu, modulus)) != CRYPT_OK) {
61 mp_montgomery_free(mp);
62 mp_clear(mu);
63 return err;
64 }
65
66 /* alloc ram for window temps */
67 for (i = 0; i < 8; i++) {
68 M[i] = ltc_ecc_new_point();
69 if (M[i] == NULL) {
70 for (j = 0; j < i; j++) {
71 ltc_ecc_del_point(M[j]);
72 }
73 mp_montgomery_free(mp);
74 mp_clear(mu);
75 return CRYPT_MEM;
76 }
77 }
78
79 /* make a copy of G incase R==G */
80 tG = ltc_ecc_new_point();
81 if (tG == NULL) { err = CRYPT_MEM; goto done; }
82
83 /* tG = G and convert to montgomery */
84 if (mp_cmp_d(mu, 1) == LTC_MP_EQ) {
85 if ((err = mp_copy(G->x, tG->x)) != CRYPT_OK) { goto done; }
86 if ((err = mp_copy(G->y, tG->y)) != CRYPT_OK) { goto done; }
87 if ((err = mp_copy(G->z, tG->z)) != CRYPT_OK) { goto done; }
88 } else {
89 if ((err = mp_mulmod(G->x, mu, modulus, tG->x)) != CRYPT_OK) { goto done; }
90 if ((err = mp_mulmod(G->y, mu, modulus, tG->y)) != CRYPT_OK) { goto done; }
91 if ((err = mp_mulmod(G->z, mu, modulus, tG->z)) != CRYPT_OK) { goto done; }
92 }
93 mp_clear(mu);
94 mu = NULL;
95
96 /* calc the M tab, which holds kG for k==8..15 */
97 /* M[0] == 8G */
98 if ((err = ltc_mp.ecc_ptdbl(tG, M[0], modulus, mp)) != CRYPT_OK) { goto done; }
99 if ((err = ltc_mp.ecc_ptdbl(M[0], M[0], modulus, mp)) != CRYPT_OK) { goto done; }
100 if ((err = ltc_mp.ecc_ptdbl(M[0], M[0], modulus, mp)) != CRYPT_OK) { goto done; }
101
102 /* now find (8+k)G for k=1..7 */
103 for (j = 9; j < 16; j++) {
104 if ((err = ltc_mp.ecc_ptadd(M[j-9], tG, M[j-8], modulus, mp)) != CRYPT_OK) { goto done; }
105 }
106
107 /* setup sliding window */
108 mode = 0;
109 bitcnt = 1;
110 buf = 0;
111 digidx = mp_get_digit_count(k) - 1;
112 bitcpy = bitbuf = 0;
113 first = 1;
114
115 /* perform ops */
116 for (;;) {
117 /* grab next digit as required */
118 if (--bitcnt == 0) {
119 if (digidx == -1) {
120 break;
121 }
122 buf = mp_get_digit(k, digidx);
123 bitcnt = (int) ltc_mp.bits_per_digit;
124 --digidx;
125 }
126
127 /* grab the next msb from the ltiplicand */
128 i = (buf >> (ltc_mp.bits_per_digit - 1)) & 1;
129 buf <<= 1;
130
131 /* skip leading zero bits */
132 if (mode == 0 && i == 0) {
133 continue;
134 }
135
136 /* if the bit is zero and mode == 1 then we double */
137 if (mode == 1 && i == 0) {
138 if ((err = ltc_mp.ecc_ptdbl(R, R, modulus, mp)) != CRYPT_OK) { goto done; }
139 continue;
140 }
141
142 /* else we add it to the window */
143 bitbuf |= (i << (WINSIZE - ++bitcpy));
144 mode = 2;
145
146 if (bitcpy == WINSIZE) {
147 /* if this is the first window we do a simple copy */
148 if (first == 1) {
149 /* R = kG [k = first window] */
150 if ((err = mp_copy(M[bitbuf-8]->x, R->x)) != CRYPT_OK) { goto done; }
151 if ((err = mp_copy(M[bitbuf-8]->y, R->y)) != CRYPT_OK) { goto done; }
152 if ((err = mp_copy(M[bitbuf-8]->z, R->z)) != CRYPT_OK) { goto done; }
153 first = 0;
154 } else {
155 /* normal window */
156 /* ok window is filled so double as required and add */
157 /* double first */
158 for (j = 0; j < WINSIZE; j++) {
159 if ((err = ltc_mp.ecc_ptdbl(R, R, modulus, mp)) != CRYPT_OK) { goto done; }
160 }
161
162 /* then add, bitbuf will be 8..15 [8..2^WINSIZE] guaranteed */
163 if ((err = ltc_mp.ecc_ptadd(R, M[bitbuf-8], R, modulus, mp)) != CRYPT_OK) { goto done; }
164 }
165 /* empty window and reset */
166 bitcpy = bitbuf = 0;
167 mode = 1;
168 }
169 }
170
171 /* if bits remain then double/add */
172 if (mode == 2 && bitcpy > 0) {
173 /* double then add */
174 for (j = 0; j < bitcpy; j++) {
175 /* only double if we have had at least one add first */
176 if (first == 0) {
177 if ((err = ltc_mp.ecc_ptdbl(R, R, modulus, mp)) != CRYPT_OK) { goto done; }
178 }
179
180 bitbuf <<= 1;
181 if ((bitbuf & (1 << WINSIZE)) != 0) {
182 if (first == 1){
183 /* first add, so copy */
184 if ((err = mp_copy(tG->x, R->x)) != CRYPT_OK) { goto done; }
185 if ((err = mp_copy(tG->y, R->y)) != CRYPT_OK) { goto done; }
186 if ((err = mp_copy(tG->z, R->z)) != CRYPT_OK) { goto done; }
187 first = 0;
188 } else {
189 /* then add */
190 if ((err = ltc_mp.ecc_ptadd(R, tG, R, modulus, mp)) != CRYPT_OK) { goto done; }
191 }
192 }
193 }
194 }
195
196 /* map R back from projective space */
197 if (map) {
198 err = ltc_ecc_map(R, modulus, mp);
199 } else {
200 err = CRYPT_OK;
201 }
202 done:
203 if (mu != NULL) {
204 mp_clear(mu);
205 }
206 mp_montgomery_free(mp);
207 ltc_ecc_del_point(tG);
208 for (i = 0; i < 8; i++) {
209 ltc_ecc_del_point(M[i]);
210 }
211 return err;
212 }
213
214 #endif
215
216 #undef WINSIZE
217
218 #endif
219
220 /* $Source: /cvs/libtom/libtomcrypt/src/pk/ecc/ltc_ecc_mulmod.c,v $ */
221 /* $Revision: 1.24 $ */
222 /* $Date: 2006/12/04 05:07:59 $ */
223