2 * Bignum routines for RSA and DH and stuff.
11 static unsigned short Zero[1] = { 0 };
13 #if defined TESTMODE || defined RSADEBUG
17 #define debug(x) bndebug(#x,x)
19 static void bndebug(char *name, Bignum b) {
21 int w = 50-level-strlen(name)-5*b[0];
25 dprintf("%*s%s%*s", level, "", name, w, "");
26 for (i=b[0]; i>0; i--)
27 dprintf(" %04x", b[i]);
30 #define dmsg(x) do {if(level<DLVL){dprintf("%*s",level,"");printf x;}} while(0)
31 #define enter(x) do { dmsg(x); level += 4; } while(0)
32 #define leave(x) do { level -= 4; dmsg(x); } while(0)
40 Bignum newbn(int length) {
41 Bignum b = malloc((length+1)*sizeof(unsigned short));
44 memset(b, 0, (length+1)*sizeof(*b));
49 void freebn(Bignum b) {
51 * Burn the evidence, just in case.
53 memset(b, 0, sizeof(b[0]) * (b[0] + 1));
59 * Input is in the first len words of a and b.
60 * Result is returned in the first 2*len words of c.
62 static void bigmul(unsigned short *a, unsigned short *b, unsigned short *c,
68 for (j = len - 1; j >= 0; j--)
71 for (i = len - 1; i >= 0; i--) {
74 for (j = len - 1; j >= 0; j--) {
75 t += ai * (unsigned long) b[j];
76 t += (unsigned long) c[i+j+1];
77 c[i+j+1] = (unsigned short)t;
80 c[i] = (unsigned short)t;
86 * Input in first 2*len words of a and first len words of m.
87 * Output in first 2*len words of a (of which first len words will be zero).
88 * The MSW of m MUST have its high bit set.
90 static void bigmod(unsigned short *a, unsigned short *m, int len)
92 unsigned short m0, m1;
96 /* Special case for len == 1 */
98 a[1] = (((long) a[0] << 16) + a[1]) % m[0];
106 for (i = 0; i <= len; i++) {
108 unsigned int q, r, c;
117 /* Find q = h:a[i] / m0 */
118 t = ((unsigned long) h << 16) + a[i];
122 /* Refine our estimate of q by looking at
123 h:a[i]:a[i+1] / m0:m1 */
124 t = (long) m1 * (long) q;
125 if (t > ((unsigned long) r << 16) + a[i+1]) {
128 r = (r + m0) & 0xffff; /* overflow? */
129 if (r >= (unsigned long)m0 &&
130 t > ((unsigned long) r << 16) + a[i+1])
134 /* Substract q * m from a[i...] */
136 for (k = len - 1; k >= 0; k--) {
137 t = (long) q * (long) m[k];
140 if ((unsigned short) t > a[i+k]) c++;
141 a[i+k] -= (unsigned short) t;
144 /* Add back m in case of borrow */
147 for (k = len - 1; k >= 0; k--) {
150 a[i+k] = (unsigned short)t;
158 * Compute (base ^ exp) % mod.
159 * The base MUST be smaller than the modulus.
160 * The most significant word of mod MUST be non-zero.
161 * We assume that the result array is the same size as the mod array.
163 void modpow(Bignum base, Bignum exp, Bignum mod, Bignum result)
165 unsigned short *a, *b, *n, *m;
169 /* Allocate m of size mlen, copy mod to m */
170 /* We use big endian internally */
172 m = malloc(mlen * sizeof(unsigned short));
173 for (j = 0; j < mlen; j++) m[j] = mod[mod[0] - j];
175 /* Shift m left to make msb bit set */
176 for (mshift = 0; mshift < 15; mshift++)
177 if ((m[0] << mshift) & 0x8000) break;
179 for (i = 0; i < mlen - 1; i++)
180 m[i] = (m[i] << mshift) | (m[i+1] >> (16-mshift));
181 m[mlen-1] = m[mlen-1] << mshift;
184 /* Allocate n of size mlen, copy base to n */
185 n = malloc(mlen * sizeof(unsigned short));
187 for (j = 0; j < i; j++) n[j] = 0;
188 for (j = 0; j < base[0]; j++) n[i+j] = base[base[0] - j];
190 /* Allocate a and b of size 2*mlen. Set a = 1 */
191 a = malloc(2 * mlen * sizeof(unsigned short));
192 b = malloc(2 * mlen * sizeof(unsigned short));
193 for (i = 0; i < 2*mlen; i++) a[i] = 0;
196 /* Skip leading zero bits of exp. */
198 while (i < exp[0] && (exp[exp[0] - i] & (1 << j)) == 0) {
200 if (j < 0) { i++; j = 15; }
203 /* Main computation */
206 bigmul(a + mlen, a + mlen, b, mlen);
208 if ((exp[exp[0] - i] & (1 << j)) != 0) {
209 bigmul(b + mlen, n, a, mlen);
220 /* Fixup result in case the modulus was shifted */
222 for (i = mlen - 1; i < 2*mlen - 1; i++)
223 a[i] = (a[i] << mshift) | (a[i+1] >> (16-mshift));
224 a[2*mlen-1] = a[2*mlen-1] << mshift;
226 for (i = 2*mlen - 1; i >= mlen; i--)
227 a[i] = (a[i] >> mshift) | (a[i-1] << (16-mshift));
230 /* Copy result to buffer */
231 for (i = 0; i < mlen; i++)
232 result[result[0] - i] = a[i+mlen];
234 /* Free temporary arrays */
235 for (i = 0; i < 2*mlen; i++) a[i] = 0; free(a);
236 for (i = 0; i < 2*mlen; i++) b[i] = 0; free(b);
237 for (i = 0; i < mlen; i++) m[i] = 0; free(m);
238 for (i = 0; i < mlen; i++) n[i] = 0; free(n);