Mercurial > dropbear

comparison libtomcrypt/src/pk/ecc/ltc_ecc_mulmod.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_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 $ */