1 /* Bignum routines adapted from PUTTY sources. PuTTY copyright notice follows.
3 * PuTTY is copyright 1997-2007 Simon Tatham.
5 * Portions copyright Robert de Bath, Joris van Rantwijk, Delian
6 * Delchev, Andreas Schultz, Jeroen Massar, Wez Furlong, Nicolas Barry,
7 * Justin Bradford, Ben Harris, Malcolm Smith, Ahmad Khalifa, Markus
8 * Kuhn, and CORE SDI S.A.
10 * Permission is hereby granted, free of charge, to any person
11 * obtaining a copy of this software and associated documentation files
12 * (the "Software"), to deal in the Software without restriction,
13 * including without limitation the rights to use, copy, modify, merge,
14 * publish, distribute, sublicense, and/or sell copies of the Software,
15 * and to permit persons to whom the Software is furnished to do so,
16 * subject to the following conditions:
18 * The above copyright notice and this permission notice shall be
19 * included in all copies or substantial portions of the Software.
21 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
22 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
23 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
24 * NONINFRINGEMENT. IN NO EVENT SHALL THE COPYRIGHT HOLDERS BE LIABLE
25 * FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF
26 * CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
27 * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
32 #ifndef CONFIG_MACH_IPMATE
34 #include "dwc_modpow.h"
36 #define BIGNUM_INT_MASK 0xFFFFFFFFUL
37 #define BIGNUM_TOP_BIT 0x80000000UL
38 #define BIGNUM_INT_BITS 32
41 static void *snmalloc(void *mem_ctx, size_t n, size_t size)
45 if (size == 0) size = 1;
46 p = dwc_alloc(mem_ctx, size);
50 #define snewn(ctx, n, type) ((type *)snmalloc((ctx), (n), sizeof(type)))
51 #define sfree dwc_free
55 * * Do not call the DIVMOD_WORD macro with expressions such as array
56 * subscripts, as some implementations object to this (see below).
57 * * Note that none of the division methods below will cope if the
58 * quotient won't fit into BIGNUM_INT_BITS. Callers should be careful
60 * If this condition occurs, in the case of the x86 DIV instruction,
61 * an overflow exception will occur, which (according to a correspondent)
62 * will manifest on Windows as something like
63 * 0xC0000095: Integer overflow
64 * The C variant won't give the right answer, either.
67 #define MUL_WORD(w1, w2) ((BignumDblInt)w1 * w2)
69 #if defined __GNUC__ && defined __i386__
70 #define DIVMOD_WORD(q, r, hi, lo, w) \
72 "=d" (r), "=a" (q) : \
73 "r" (w), "d" (hi), "a" (lo))
75 #define DIVMOD_WORD(q, r, hi, lo, w) do { \
76 BignumDblInt n = (((BignumDblInt)hi) << BIGNUM_INT_BITS) | lo; \
85 #define BIGNUM_INT_BYTES (BIGNUM_INT_BITS / 8)
87 #define BIGNUM_INTERNAL
89 static Bignum newbn(void *mem_ctx, int length)
91 Bignum b = snewn(mem_ctx, length + 1, BignumInt);
93 //abort(); /* FIXME */
94 DWC_MEMSET(b, 0, (length + 1) * sizeof(*b));
99 void freebn(void *mem_ctx, Bignum b)
102 * Burn the evidence, just in case.
104 DWC_MEMSET(b, 0, sizeof(b[0]) * (b[0] + 1));
110 * Input is in the first len words of a and b.
111 * Result is returned in the first 2*len words of c.
113 static void internal_mul(BignumInt *a, BignumInt *b,
114 BignumInt *c, int len)
119 for (j = 0; j < 2 * len; j++)
122 for (i = len - 1; i >= 0; i--) {
124 for (j = len - 1; j >= 0; j--) {
125 t += MUL_WORD(a[i], (BignumDblInt) b[j]);
126 t += (BignumDblInt) c[i + j + 1];
127 c[i + j + 1] = (BignumInt) t;
128 t = t >> BIGNUM_INT_BITS;
130 c[i] = (BignumInt) t;
134 static void internal_add_shifted(BignumInt *number,
135 unsigned n, int shift)
137 int word = 1 + (shift / BIGNUM_INT_BITS);
138 int bshift = shift % BIGNUM_INT_BITS;
141 addend = (BignumDblInt)n << bshift;
144 addend += number[word];
145 number[word] = (BignumInt) addend & BIGNUM_INT_MASK;
146 addend >>= BIGNUM_INT_BITS;
153 * Input in first alen words of a and first mlen words of m.
154 * Output in first alen words of a
155 * (of which first alen-mlen words will be zero).
156 * The MSW of m MUST have its high bit set.
157 * Quotient is accumulated in the `quotient' array, which is a Bignum
158 * rather than the internal bigendian format. Quotient parts are shifted
159 * left by `qshift' before adding into quot.
161 static void internal_mod(BignumInt *a, int alen,
162 BignumInt *m, int mlen,
163 BignumInt *quot, int qshift)
175 for (i = 0; i <= alen - mlen; i++) {
177 unsigned int q, r, c, ai1;
191 /* Find q = h:a[i] / m0 */
196 * To illustrate it, suppose a BignumInt is 8 bits, and
197 * we are dividing (say) A1:23:45:67 by A1:B2:C3. Then
198 * our initial division will be 0xA123 / 0xA1, which
199 * will give a quotient of 0x100 and a divide overflow.
200 * However, the invariants in this division algorithm
201 * are not violated, since the full number A1:23:... is
202 * _less_ than the quotient prefix A1:B2:... and so the
203 * following correction loop would have sorted it out.
205 * In this situation we set q to be the largest
206 * quotient we _can_ stomach (0xFF, of course).
210 /* Macro doesn't want an array subscript expression passed
211 * into it (see definition), so use a temporary. */
212 BignumInt tmplo = a[i];
213 DIVMOD_WORD(q, r, h, tmplo, m0);
215 /* Refine our estimate of q by looking at
216 h:a[i]:a[i+1] / m0:m1 */
218 if (t > ((BignumDblInt) r << BIGNUM_INT_BITS) + ai1) {
221 r = (r + m0) & BIGNUM_INT_MASK; /* overflow? */
222 if (r >= (BignumDblInt) m0 &&
223 t > ((BignumDblInt) r << BIGNUM_INT_BITS) + ai1) q--;
227 /* Subtract q * m from a[i...] */
229 for (k = mlen - 1; k >= 0; k--) {
230 t = MUL_WORD(q, m[k]);
232 c = (unsigned)(t >> BIGNUM_INT_BITS);
233 if ((BignumInt) t > a[i + k])
235 a[i + k] -= (BignumInt) t;
238 /* Add back m in case of borrow */
241 for (k = mlen - 1; k >= 0; k--) {
244 a[i + k] = (BignumInt) t;
245 t = t >> BIGNUM_INT_BITS;
250 internal_add_shifted(quot, q, qshift + BIGNUM_INT_BITS * (alen - mlen - i));
256 * The most significant word of mod MUST be non-zero.
257 * We assume that the result array is the same size as the mod array.
258 * We optionally write out a quotient if `quotient' is non-NULL.
259 * We can avoid writing out the result if `result' is NULL.
261 void bigdivmod(void *mem_ctx, Bignum p, Bignum mod, Bignum result, Bignum quotient)
265 int plen, mlen, i, j;
267 /* Allocate m of size mlen, copy mod to m */
268 /* We use big endian internally */
270 m = snewn(mem_ctx, mlen, BignumInt);
272 //abort(); /* FIXME */
273 for (j = 0; j < mlen; j++)
274 m[j] = mod[mod[0] - j];
276 /* Shift m left to make msb bit set */
277 for (mshift = 0; mshift < BIGNUM_INT_BITS-1; mshift++)
278 if ((m[0] << mshift) & BIGNUM_TOP_BIT)
281 for (i = 0; i < mlen - 1; i++)
282 m[i] = (m[i] << mshift) | (m[i + 1] >> (BIGNUM_INT_BITS - mshift));
283 m[mlen - 1] = m[mlen - 1] << mshift;
287 /* Ensure plen > mlen */
291 /* Allocate n of size plen, copy p to n */
292 n = snewn(mem_ctx, plen, BignumInt);
294 //abort(); /* FIXME */
295 for (j = 0; j < plen; j++)
297 for (j = 1; j <= (int)p[0]; j++)
300 /* Main computation */
301 internal_mod(n, plen, m, mlen, quotient, mshift);
303 /* Fixup result in case the modulus was shifted */
305 for (i = plen - mlen - 1; i < plen - 1; i++)
306 n[i] = (n[i] << mshift) | (n[i + 1] >> (BIGNUM_INT_BITS - mshift));
307 n[plen - 1] = n[plen - 1] << mshift;
308 internal_mod(n, plen, m, mlen, quotient, 0);
309 for (i = plen - 1; i >= plen - mlen; i--)
310 n[i] = (n[i] >> mshift) | (n[i - 1] << (BIGNUM_INT_BITS - mshift));
313 /* Copy result to buffer */
315 for (i = 1; i <= (int)result[0]; i++) {
317 result[i] = j >= 0 ? n[j] : 0;
321 /* Free temporary arrays */
322 for (i = 0; i < mlen; i++)
325 for (i = 0; i < plen; i++)
333 Bignum bigmod(void *mem_ctx, Bignum a, Bignum b)
335 Bignum r = newbn(mem_ctx, b[0]);
336 bigdivmod(mem_ctx, a, b, r, NULL);
341 * Compute (base ^ exp) % mod.
343 Bignum dwc_modpow(void *mem_ctx, Bignum base_in, Bignum exp, Bignum mod)
345 BignumInt *a, *b, *n, *m;
351 * The most significant word of mod needs to be non-zero. It
352 * should already be, but let's make sure.
354 //assert(mod[mod[0]] != 0);
357 * Make sure the base is smaller than the modulus, by reducing
358 * it modulo the modulus if not.
360 base = bigmod(mem_ctx, base_in, mod);
362 /* Allocate m of size mlen, copy mod to m */
363 /* We use big endian internally */
365 m = snewn(mem_ctx, mlen, BignumInt);
367 //abort(); /* FIXME */
368 for (j = 0; j < mlen; j++)
369 m[j] = mod[mod[0] - j];
371 /* Shift m left to make msb bit set */
372 for (mshift = 0; mshift < BIGNUM_INT_BITS - 1; mshift++)
373 if ((m[0] << mshift) & BIGNUM_TOP_BIT)
376 for (i = 0; i < mlen - 1; i++)
378 (m[i] << mshift) | (m[i + 1] >>
379 (BIGNUM_INT_BITS - mshift));
380 m[mlen - 1] = m[mlen - 1] << mshift;
383 /* Allocate n of size mlen, copy base to n */
384 n = snewn(mem_ctx, mlen, BignumInt);
386 //abort(); /* FIXME */
388 for (j = 0; j < i; j++)
390 for (j = 0; j < base[0]; j++)
391 n[i + j] = base[base[0] - j];
393 /* Allocate a and b of size 2*mlen. Set a = 1 */
394 a = snewn(mem_ctx, 2 * mlen, BignumInt);
396 //abort(); /* FIXME */
397 b = snewn(mem_ctx, 2 * mlen, BignumInt);
399 //abort(); /* FIXME */
400 for (i = 0; i < 2 * mlen; i++)
404 /* Skip leading zero bits of exp. */
406 j = BIGNUM_INT_BITS - 1;
407 while (i < exp[0] && (exp[exp[0] - i] & (1 << j)) == 0) {
411 j = BIGNUM_INT_BITS - 1;
415 /* Main computation */
418 internal_mul(a + mlen, a + mlen, b, mlen);
419 internal_mod(b, mlen * 2, m, mlen, NULL, 0);
420 if ((exp[exp[0] - i] & (1 << j)) != 0) {
421 internal_mul(b + mlen, n, a, mlen);
422 internal_mod(a, mlen * 2, m, mlen, NULL, 0);
432 j = BIGNUM_INT_BITS - 1;
435 /* Fixup result in case the modulus was shifted */
437 for (i = mlen - 1; i < 2 * mlen - 1; i++)
439 (a[i] << mshift) | (a[i + 1] >>
440 (BIGNUM_INT_BITS - mshift));
441 a[2 * mlen - 1] = a[2 * mlen - 1] << mshift;
442 internal_mod(a, mlen * 2, m, mlen, NULL, 0);
443 for (i = 2 * mlen - 1; i >= mlen; i--)
445 (a[i] >> mshift) | (a[i - 1] <<
446 (BIGNUM_INT_BITS - mshift));
449 /* Copy result to buffer */
450 result = newbn(mem_ctx, mod[0]);
451 for (i = 0; i < mlen; i++)
452 result[result[0] - i] = a[i + mlen];
453 while (result[0] > 1 && result[result[0]] == 0)
456 /* Free temporary arrays */
457 for (i = 0; i < 2 * mlen; i++)
460 for (i = 0; i < 2 * mlen; i++)
463 for (i = 0; i < mlen; i++)
466 for (i = 0; i < mlen; i++)
470 freebn(mem_ctx, base);
478 static __u32 dh_p[] = {
578 static __u32 dh_a[] = {
590 static __u32 dh_b[] = {
602 static __u32 dh_g[] = {
611 k = dwc_modpow(NULL, dh_g, dh_a, dh_p);
614 for (i=0; i<k[0]; i++) {
615 __u32 word32 = k[k[0] - i];
616 __u16 l = word32 & 0xffff;
617 __u16 m = (word32 & 0xffff0000) >> 16;
618 printf("%04x %04x ", m, l);
619 if (!((i + 1)%13)) printf("\n");
623 if ((k[0] == 0x60) && (k[1] == 0x28e490e5) && (k[0x60] == 0x5a0d3d4e)) {
632 #endif /* UNITTEST */
634 #endif /* CONFIG_MACH_IPMATE */
636 #endif /*DWC_CRYPTOLIB */