Mercurial > dropbear

comparison gf.c @ 16:09ab3354aa21 libtomcrypt

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
propagate of e8bea23df30f9f46c647d06db3b223427b4e3604 and b0b6b4a8843b94d9f049cb5ffe0b1ae91ec1bf8b from branch 'au.asn.ucc.matt.ltc-orig' to 'au.asn.ucc.matt.ltc-db'
author Matt Johnston <matt@ucc.asn.au>
date Tue, 15 Jun 2004 14:27:14 +0000
parents d7da3b1e1540
children
comparison
equal deleted inserted replaced
15:6362d3854bb4 16:09ab3354aa21
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