Mercurial > dropbear

comparison libtomcrypt/src/pk/ecc/ltc_ecc_mul2add.c @ 382:0cbe8f6dbf9e

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
propagate from branch 'au.asn.ucc.matt.ltc.dropbear' (head 2af22fb4e878750b88f80f90d439b316d229796f) to branch 'au.asn.ucc.matt.dropbear' (head 02c413252c90e9de8e03d91e9939dde3029f5c0a)
author Matt Johnston <matt@ucc.asn.au>
date Thu, 11 Jan 2007 02:41:05 +0000
parents
children f849a5ca2efc
comparison
equal deleted inserted replaced
379:b66a00272a90 382:0cbe8f6dbf9e
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 $ */