|
380
|
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, [email protected], 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 */ |
|
|
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 $ */ |
