2 * Bignum routines for RSA and DH and stuff.
11 unsigned short bnZero[1] = { 0 };
12 unsigned short bnOne[2] = { 1, 1 };
14 Bignum Zero = bnZero, One = bnOne;
16 Bignum newbn(int length) {
17 Bignum b = malloc((length+1)*sizeof(unsigned short));
20 memset(b, 0, (length+1)*sizeof(*b));
25 Bignum copybn(Bignum orig) {
26 Bignum b = malloc((orig[0]+1)*sizeof(unsigned short));
29 memcpy(b, orig, (orig[0]+1)*sizeof(*b));
33 void freebn(Bignum b) {
35 * Burn the evidence, just in case.
37 memset(b, 0, sizeof(b[0]) * (b[0] + 1));
43 * Input is in the first len words of a and b.
44 * Result is returned in the first 2*len words of c.
46 static void bigmul(unsigned short *a, unsigned short *b, unsigned short *c,
52 for (j = len - 1; j >= 0; j--)
55 for (i = len - 1; i >= 0; i--) {
58 for (j = len - 1; j >= 0; j--) {
59 t += ai * (unsigned long) b[j];
60 t += (unsigned long) c[i+j+1];
61 c[i+j+1] = (unsigned short)t;
64 c[i] = (unsigned short)t;
70 * Input in first len2 words of a and first len words of m.
71 * Output in first len2 words of a
72 * (of which first len2-len words will be zero).
73 * The MSW of m MUST have its high bit set.
75 static void bigmod(unsigned short *a, unsigned short *m,
78 unsigned short m0, m1;
82 /* Special case for len == 1 */
84 a[1] = (((long) a[0] << 16) + a[1]) % m[0];
92 for (i = 0; i <= len2-len; i++) {
103 /* Find q = h:a[i] / m0 */
104 t = ((unsigned long) h << 16) + a[i];
108 /* Refine our estimate of q by looking at
109 h:a[i]:a[i+1] / m0:m1 */
110 t = (long) m1 * (long) q;
111 if (t > ((unsigned long) r << 16) + a[i+1]) {
114 r = (r + m0) & 0xffff; /* overflow? */
115 if (r >= (unsigned long)m0 &&
116 t > ((unsigned long) r << 16) + a[i+1])
120 /* Substract q * m from a[i...] */
122 for (k = len - 1; k >= 0; k--) {
123 t = (long) q * (long) m[k];
126 if ((unsigned short) t > a[i+k]) c++;
127 a[i+k] -= (unsigned short) t;
130 /* Add back m in case of borrow */
133 for (k = len - 1; k >= 0; k--) {
136 a[i+k] = (unsigned short)t;
144 * Compute (base ^ exp) % mod.
145 * The base MUST be smaller than the modulus.
146 * The most significant word of mod MUST be non-zero.
147 * We assume that the result array is the same size as the mod array.
149 void modpow(Bignum base, Bignum exp, Bignum mod, Bignum result)
151 unsigned short *a, *b, *n, *m;
155 /* Allocate m of size mlen, copy mod to m */
156 /* We use big endian internally */
158 m = malloc(mlen * sizeof(unsigned short));
159 for (j = 0; j < mlen; j++) m[j] = mod[mod[0] - j];
161 /* Shift m left to make msb bit set */
162 for (mshift = 0; mshift < 15; mshift++)
163 if ((m[0] << mshift) & 0x8000) break;
165 for (i = 0; i < mlen - 1; i++)
166 m[i] = (m[i] << mshift) | (m[i+1] >> (16-mshift));
167 m[mlen-1] = m[mlen-1] << mshift;
170 /* Allocate n of size mlen, copy base to n */
171 n = malloc(mlen * sizeof(unsigned short));
173 for (j = 0; j < i; j++) n[j] = 0;
174 for (j = 0; j < base[0]; j++) n[i+j] = base[base[0] - j];
176 /* Allocate a and b of size 2*mlen. Set a = 1 */
177 a = malloc(2 * mlen * sizeof(unsigned short));
178 b = malloc(2 * mlen * sizeof(unsigned short));
179 for (i = 0; i < 2*mlen; i++) a[i] = 0;
182 /* Skip leading zero bits of exp. */
184 while (i < exp[0] && (exp[exp[0] - i] & (1 << j)) == 0) {
186 if (j < 0) { i++; j = 15; }
189 /* Main computation */
192 bigmul(a + mlen, a + mlen, b, mlen);
193 bigmod(b, m, mlen, mlen*2);
194 if ((exp[exp[0] - i] & (1 << j)) != 0) {
195 bigmul(b + mlen, n, a, mlen);
196 bigmod(a, m, mlen, mlen*2);
206 /* Fixup result in case the modulus was shifted */
208 for (i = mlen - 1; i < 2*mlen - 1; i++)
209 a[i] = (a[i] << mshift) | (a[i+1] >> (16-mshift));
210 a[2*mlen-1] = a[2*mlen-1] << mshift;
211 bigmod(a, m, mlen, mlen*2);
212 for (i = 2*mlen - 1; i >= mlen; i--)
213 a[i] = (a[i] >> mshift) | (a[i-1] << (16-mshift));
216 /* Copy result to buffer */
217 for (i = 0; i < mlen; i++)
218 result[result[0] - i] = a[i+mlen];
220 /* Free temporary arrays */
221 for (i = 0; i < 2*mlen; i++) a[i] = 0; free(a);
222 for (i = 0; i < 2*mlen; i++) b[i] = 0; free(b);
223 for (i = 0; i < mlen; i++) m[i] = 0; free(m);
224 for (i = 0; i < mlen; i++) n[i] = 0; free(n);
228 * Compute (p * q) % mod.
229 * The most significant word of mod MUST be non-zero.
230 * We assume that the result array is the same size as the mod array.
232 void modmul(Bignum p, Bignum q, Bignum mod, Bignum result)
234 unsigned short *a, *n, *m, *o;
236 int pqlen, mlen, i, j;
238 /* Allocate m of size mlen, copy mod to m */
239 /* We use big endian internally */
241 m = malloc(mlen * sizeof(unsigned short));
242 for (j = 0; j < mlen; j++) m[j] = mod[mod[0] - j];
244 /* Shift m left to make msb bit set */
245 for (mshift = 0; mshift < 15; mshift++)
246 if ((m[0] << mshift) & 0x8000) break;
248 for (i = 0; i < mlen - 1; i++)
249 m[i] = (m[i] << mshift) | (m[i+1] >> (16-mshift));
250 m[mlen-1] = m[mlen-1] << mshift;
253 pqlen = (p[0] > q[0] ? p[0] : q[0]);
255 /* Allocate n of size pqlen, copy p to n */
256 n = malloc(pqlen * sizeof(unsigned short));
258 for (j = 0; j < i; j++) n[j] = 0;
259 for (j = 0; j < p[0]; j++) n[i+j] = p[p[0] - j];
261 /* Allocate o of size pqlen, copy q to o */
262 o = malloc(pqlen * sizeof(unsigned short));
264 for (j = 0; j < i; j++) o[j] = 0;
265 for (j = 0; j < q[0]; j++) o[i+j] = q[q[0] - j];
267 /* Allocate a of size 2*pqlen for result */
268 a = malloc(2 * pqlen * sizeof(unsigned short));
270 /* Main computation */
271 bigmul(n, o, a, pqlen);
272 bigmod(a, m, mlen, 2*pqlen);
274 /* Fixup result in case the modulus was shifted */
276 for (i = 2*pqlen - mlen - 1; i < 2*pqlen - 1; i++)
277 a[i] = (a[i] << mshift) | (a[i+1] >> (16-mshift));
278 a[2*pqlen-1] = a[2*pqlen-1] << mshift;
279 bigmod(a, m, mlen, pqlen*2);
280 for (i = 2*pqlen - 1; i >= 2*pqlen - mlen; i--)
281 a[i] = (a[i] >> mshift) | (a[i-1] << (16-mshift));
284 /* Copy result to buffer */
285 for (i = 0; i < mlen; i++)
286 result[result[0] - i] = a[i+2*pqlen-mlen];
288 /* Free temporary arrays */
289 for (i = 0; i < 2*pqlen; i++) a[i] = 0; free(a);
290 for (i = 0; i < mlen; i++) m[i] = 0; free(m);
291 for (i = 0; i < pqlen; i++) n[i] = 0; free(n);
292 for (i = 0; i < pqlen; i++) o[i] = 0; free(o);
296 * Decrement a number.
298 void decbn(Bignum bn) {
300 while (i < bn[0] && bn[i] == 0)
306 * Read an ssh1-format bignum from a data buffer. Return the number
309 int ssh1_read_bignum(unsigned char *data, Bignum *result) {
310 unsigned char *p = data;
319 b = (w+7)/8; /* bits -> bytes */
320 w = (w+15)/16; /* bits -> words */
322 if (!result) /* just return length */
330 unsigned char byte = *p++;
332 bn[1+i/2] |= byte<<8;
343 * Return the bit count of a bignum, for ssh1 encoding.
345 int ssh1_bignum_bitcount(Bignum bn) {
346 int bitcount = bn[0] * 16 - 1;
348 while (bitcount >= 0 && (bn[bitcount/16+1] >> (bitcount % 16)) == 0)
354 * Return the byte length of a bignum when ssh1 encoded.
356 int ssh1_bignum_length(Bignum bn) {
357 return 2 + (ssh1_bignum_bitcount(bn)+7)/8;
361 * Return a byte from a bignum; 0 is least significant, etc.
363 int bignum_byte(Bignum bn, int i) {
365 return 0; /* beyond the end */
367 return (bn[i/2+1] >> 8) & 0xFF;
369 return (bn[i/2+1] ) & 0xFF;
373 * Write a ssh1-format bignum into a buffer. It is assumed the
374 * buffer is big enough. Returns the number of bytes used.
376 int ssh1_write_bignum(void *data, Bignum bn) {
377 unsigned char *p = data;
378 int len = ssh1_bignum_length(bn);
380 int bitc = ssh1_bignum_bitcount(bn);
382 *p++ = (bitc >> 8) & 0xFF;
383 *p++ = (bitc ) & 0xFF;
384 for (i = len-2; i-- ;)
385 *p++ = bignum_byte(bn, i);