|
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_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 */ |
|
|
37 int 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 */ |
|
|
183 ERR_MU: |
|
|
184 mp_clear(mu); |
|
|
185 ERR_MP: |
|
|
186 mp_montgomery_free(mp); |
|
|
187 ERR_P: |
|
|
188 for (x = 0; x < 16; x++) { |
|
|
189 ltc_ecc_del_point(precomp[x]); |
|
|
190 } |
|
|
191 ERR_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 $ */ |
