Mercurial > dropbear

comparison gf.c @ 0:d7da3b1e1540 libtomcrypt

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
put back the 0.95 makefile which was inadvertently merged over
author Matt Johnston <matt@ucc.asn.au>
date Mon, 31 May 2004 18:21:40 +0000
parents
children
comparison
equal deleted inserted replaced
-1:000000000000 0:d7da3b1e1540
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.org
10 */
11 /* polynomial basis GF(2^w) routines */
12 #include "mycrypt.h"
13
14 #ifdef GF
15
16 #define FORLOOP for (i = 0; i < LSIZE; i++)
17
18 /* c = a + b */
19 void gf_add(gf_intp a, gf_intp b, gf_intp c)
20 {
21 int i;
22 FORLOOP c[i] = a[i]^b[i];
23 }
24
25 /* b = a */
26 void gf_copy(gf_intp a, gf_intp b)
27 {
28 int i;
29 FORLOOP b[i] = a[i];
30 }
31
32 /* a = 0 */
33 void gf_zero(gf_intp a)
34 {
35 int i;
36 FORLOOP a[i] = 0;
37 }
38
39 /* is a zero? */
40 int gf_iszero(gf_intp a)
41 {
42 int i;
43 FORLOOP if (a[i]) {
44 return 0;
45 }
46 return 1;
47 }
48
49 /* is a one? */
50 int gf_isone(gf_intp a)
51 {
52 int i;
53 for (i = 1; i < LSIZE; i++) {
54 if (a[i]) {
55 return 0;
56 }
57 }
58 return a[0] == 1;
59 }
60
61 /* b = a << 1*/
62 void gf_shl(gf_intp a, gf_intp b)
63 {
64 int i;
65 gf_int tmp;
66
67 gf_copy(a, tmp);
68 for (i = LSIZE-1; i > 0; i--)
69 b[i] = ((tmp[i]<<1)|((tmp[i-1]&0xFFFFFFFFUL)>>31))&0xFFFFFFFFUL;
70 b[0] = (tmp[0] << 1)&0xFFFFFFFFUL;
71 gf_zero(tmp);
72 }
73
74 /* b = a >> 1 */
75 void gf_shr(gf_intp a, gf_intp b)
76 {
77 int i;
78 gf_int tmp;
79
80 gf_copy(a, tmp);
81 for (i = 0; i < LSIZE-1; i++)
82 b[i] = (((tmp[i]&0xFFFFFFFFUL)>>1)|(tmp[i+1]<<31))&0xFFFFFFFFUL;
83 b[LSIZE-1] = (tmp[LSIZE-1]&0xFFFFFFFFUL)>>1;
84 gf_zero(tmp);
85 }
86
87 /* returns -1 if its zero, otherwise degree of a */
88 int gf_deg(gf_intp a)
89 {
90 int i, ii;
91 unsigned long t;
92
93 ii = -1;
94 for (i = LSIZE-1; i >= 0; i--)
95 if (a[i]) {
96 for (t = a[i], ii = 0; t; t >>= 1, ++ii);
97 break;
98 }
99 if (i == -1) i = 0;
100 return (i<<5)+ii;
101 }
102
103 /* c = ab */
104 void gf_mul(gf_intp a, gf_intp b, gf_intp c)
105 {
106 gf_int ta, tb;
107 int i, n;
108
109 gf_copy(a, ta);
110 gf_copy(b, tb);
111 gf_zero(c);
112 n = gf_deg(ta)+1;
113 for (i = 0; i < n; i++) {
114 if (ta[i>>5]&(1<<(i&31)))
115 gf_add(c, tb, c);
116 gf_shl(tb, tb);
117 }
118 gf_zero(ta);
119 gf_zero(tb);
120 }
121
122 /* q = a/b, r = a%b */
123 void gf_div(gf_intp a, gf_intp b, gf_intp q, gf_intp r)
124 {
125 gf_int ta, tb, shifts[LSIZE*32];
126 int i, magb, mag;
127
128 mag = gf_deg(a);
129 magb = gf_deg(b);
130
131 /* special cases */
132 if (magb > mag) {
133 gf_copy(a, r);
134 gf_zero(q);
135 return;
136 }
137 if (magb == -1) {
138 return;
139 }
140
141 /* copy locally */
142 gf_copy(a, ta);
143 gf_copy(b, tb);
144 gf_zero(q);
145
146 /* make shifted versions of "b" */
147 gf_copy(tb, shifts[0]);
148 for (i = 1; i <= (mag-magb); i++)
149 gf_shl(shifts[i-1], shifts[i]);
150
151 while (mag >= magb) {
152 i = (mag - magb);
153 q[i>>5] |= (1<<(i&31));
154 gf_add(ta, shifts[i], ta);
155 mag = gf_deg(ta);
156 }
157 gf_copy(ta, r);
158 gf_zero(ta);
159 gf_zero(tb);
160 zeromem(shifts, sizeof(shifts));
161 }
162
163 /* b = a mod m */
164 void gf_mod(gf_intp a, gf_intp m, gf_intp b)
165 {
166 gf_int tmp;
167 gf_div(a,m,tmp,b);
168 gf_zero(tmp);
169 }
170
171 /* c = ab (mod m) */
172 void gf_mulmod(gf_intp a, gf_intp b, gf_intp m, gf_intp c)
173 {
174 gf_int tmp;
175 gf_mul(a, b, tmp);
176 gf_mod(tmp, m, c);
177 gf_zero(tmp);
178 }
179
180 /* B = 1/A mod M */
181 void gf_invmod(gf_intp A, gf_intp M, gf_intp B)
182 {
183 gf_int m, n, p0, p1, p2, r, q, tmp;
184
185 /* put all variables in known setup state */
186 gf_zero(p0);
187 gf_zero(p2);
188 gf_copy(M, m);
189 gf_copy(A, n);
190 p0[0] = 1;
191 gf_div(m, n, p1, r);
192 gf_copy(p1, q);
193
194 /* loop until r == 0 */
195 while (!gf_iszero(r)) {
196 gf_copy(n, m);
197 gf_copy(r, n);
198 gf_div(m, n, q, r);
199 gf_mul(q, p1, tmp);
200 gf_add(tmp, p0, p2);
201 gf_copy(p1, p0);
202 gf_copy(p2, p1);
203 }
204 gf_copy(p0, B);
205 gf_zero(p0);
206 }
207
208 /* find a square root modulo a prime. Note the number of
209 * elements is 2^k - 1, so we must square k-2 times to get the
210 * square root..
211 */
212 void gf_sqrt(gf_intp a, gf_intp M, gf_intp b)
213 {
214 int k;
215 k = gf_deg(M)-2;
216 gf_copy(a, b);
217 while (k--)
218 gf_mulmod(b, b, M, b);
219 }
220
221 /* c = gcd(A,B) */
222 void gf_gcd(gf_intp A, gf_intp B, gf_intp c)
223 {
224 gf_int a, b, r;
225 int n;
226
227 gf_add(A, B, r);
228 n = gf_deg(r);
229 if (gf_deg(A) > n) {
230 gf_copy(A, a);
231 gf_copy(B, b);
232 } else {
233 gf_copy(A, b);
234 gf_copy(B, a);
235 }
236
237 do {
238 gf_mod(a, b, r);
239 gf_copy(b, a);
240 gf_copy(r, b);
241 } while (!gf_iszero(r));
242 gf_copy(a, c);
243 gf_zero(a);
244 gf_zero(b);
245 }
246
247 /* returns non-zero if 'a' is irreducible */
248 int gf_is_prime(gf_intp a)
249 {
250 gf_int u, tmp;
251 int m, n;
252
253 gf_zero(u);
254 u[0] = 2; /* u(x) = x */
255 m = gf_deg(a);
256 for (n = 0; n < (m/2); n++) {
257 gf_mulmod(u, u, a, u); /* u(x) = u(x)^2 mod a(x) */
258 gf_copy(u, tmp);
259 tmp[0] ^= 2; /* tmp(x) = u(x) - x */
260 gf_gcd(tmp, a, tmp); /* tmp(x) = gcd(a(x), u(x) - x) */
261 if (!gf_isone(tmp)) {
262 return 0;
263 }
264 }
265 return 1;
266 }
267
268 /* returns bytes required to store a gf_int */
269 int gf_size(gf_intp a)
270 {
271 int n;
272
273 n = gf_deg(a);
274 if (n == -1) {
275 return 4;
276 }
277 n = n + (32 - (n&31));
278 return n/8;
279 }
280
281 /* store a gf_int */
282 void gf_toraw(gf_intp a, unsigned char *dst)
283 {
284 int x, n;
285 n = gf_size(a)/4;
286 for (x = 0; x < n; x++) {
287 STORE32L(a[x], dst);
288 dst += 4;
289 }
290 }
291
292 /* read a gf_int (len == in bytes) */
293 void gf_readraw(gf_intp a, unsigned char *str, int len)
294 {
295 int x;
296 gf_zero(a);
297 for (x = 0; x < len/4; x++) {
298 LOAD32L(a[x], str);
299 str += 4;
300 }
301 }
302
303 #endif
304
305