2 * Bignum routines for RSA and DH and stuff.
9 #include <stdio.h> /* FIXME */
10 #include <stdarg.h> /* FIXME */
11 #include <windows.h> /* FIXME */
12 #include "putty.h" /* FIXME */
16 unsigned short bnZero
[1] = { 0 };
17 unsigned short bnOne
[2] = { 1, 1 };
19 Bignum Zero
= bnZero
, One
= bnOne
;
21 Bignum
newbn(int length
) {
22 Bignum b
= malloc((length
+1)*sizeof(unsigned short));
25 memset(b
, 0, (length
+1)*sizeof(*b
));
30 Bignum
copybn(Bignum orig
) {
31 Bignum b
= malloc((orig
[0]+1)*sizeof(unsigned short));
34 memcpy(b
, orig
, (orig
[0]+1)*sizeof(*b
));
38 void freebn(Bignum b
) {
40 * Burn the evidence, just in case.
42 memset(b
, 0, sizeof(b
[0]) * (b
[0] + 1));
48 * Input is in the first len words of a and b.
49 * Result is returned in the first 2*len words of c.
51 static void bigmul(unsigned short *a
, unsigned short *b
, unsigned short *c
,
57 for (j
= len
- 1; j
>= 0; j
--)
60 for (i
= len
- 1; i
>= 0; i
--) {
63 for (j
= len
- 1; j
>= 0; j
--) {
64 t
+= ai
* (unsigned long) b
[j
];
65 t
+= (unsigned long) c
[i
+j
+1];
66 c
[i
+j
+1] = (unsigned short)t
;
69 c
[i
] = (unsigned short)t
;
75 * Input in first len2 words of a and first len words of m.
76 * Output in first len2 words of a
77 * (of which first len2-len words will be zero).
78 * The MSW of m MUST have its high bit set.
80 static void bigmod(unsigned short *a
, unsigned short *m
,
83 unsigned short m0
, m1
;
87 /* Special case for len == 1 */
89 a
[1] = (((long) a
[0] << 16) + a
[1]) % m
[0];
97 for (i
= 0; i
<= len2
-len
; i
++) {
108 /* Find q = h:a[i] / m0 */
109 t
= ((unsigned long) h
<< 16) + a
[i
];
113 /* Refine our estimate of q by looking at
114 h:a[i]:a[i+1] / m0:m1 */
115 t
= (long) m1
* (long) q
;
116 if (t
> ((unsigned long) r
<< 16) + a
[i
+1]) {
119 r
= (r
+ m0
) & 0xffff; /* overflow? */
120 if (r
>= (unsigned long)m0
&&
121 t
> ((unsigned long) r
<< 16) + a
[i
+1])
125 /* Substract q * m from a[i...] */
127 for (k
= len
- 1; k
>= 0; k
--) {
128 t
= (long) q
* (long) m
[k
];
131 if ((unsigned short) t
> a
[i
+k
]) c
++;
132 a
[i
+k
] -= (unsigned short) t
;
135 /* Add back m in case of borrow */
138 for (k
= len
- 1; k
>= 0; k
--) {
141 a
[i
+k
] = (unsigned short)t
;
149 * Compute (base ^ exp) % mod.
150 * The base MUST be smaller than the modulus.
151 * The most significant word of mod MUST be non-zero.
152 * We assume that the result array is the same size as the mod array.
154 void modpow(Bignum base
, Bignum exp
, Bignum mod
, Bignum result
)
156 unsigned short *a
, *b
, *n
, *m
;
160 /* Allocate m of size mlen, copy mod to m */
161 /* We use big endian internally */
163 m
= malloc(mlen
* sizeof(unsigned short));
164 for (j
= 0; j
< mlen
; j
++) m
[j
] = mod
[mod
[0] - j
];
166 /* Shift m left to make msb bit set */
167 for (mshift
= 0; mshift
< 15; mshift
++)
168 if ((m
[0] << mshift
) & 0x8000) break;
170 for (i
= 0; i
< mlen
- 1; i
++)
171 m
[i
] = (m
[i
] << mshift
) | (m
[i
+1] >> (16-mshift
));
172 m
[mlen
-1] = m
[mlen
-1] << mshift
;
175 /* Allocate n of size mlen, copy base to n */
176 n
= malloc(mlen
* sizeof(unsigned short));
178 for (j
= 0; j
< i
; j
++) n
[j
] = 0;
179 for (j
= 0; j
< base
[0]; j
++) n
[i
+j
] = base
[base
[0] - j
];
181 /* Allocate a and b of size 2*mlen. Set a = 1 */
182 a
= malloc(2 * mlen
* sizeof(unsigned short));
183 b
= malloc(2 * mlen
* sizeof(unsigned short));
184 for (i
= 0; i
< 2*mlen
; i
++) a
[i
] = 0;
187 /* Skip leading zero bits of exp. */
189 while (i
< exp
[0] && (exp
[exp
[0] - i
] & (1 << j
)) == 0) {
191 if (j
< 0) { i
++; j
= 15; }
194 /* Main computation */
197 bigmul(a
+ mlen
, a
+ mlen
, b
, mlen
);
198 bigmod(b
, m
, mlen
, mlen
*2);
199 if ((exp
[exp
[0] - i
] & (1 << j
)) != 0) {
200 bigmul(b
+ mlen
, n
, a
, mlen
);
201 bigmod(a
, m
, mlen
, mlen
*2);
211 /* Fixup result in case the modulus was shifted */
213 for (i
= mlen
- 1; i
< 2*mlen
- 1; i
++)
214 a
[i
] = (a
[i
] << mshift
) | (a
[i
+1] >> (16-mshift
));
215 a
[2*mlen
-1] = a
[2*mlen
-1] << mshift
;
216 bigmod(a
, m
, mlen
, mlen
*2);
217 for (i
= 2*mlen
- 1; i
>= mlen
; i
--)
218 a
[i
] = (a
[i
] >> mshift
) | (a
[i
-1] << (16-mshift
));
221 /* Copy result to buffer */
222 for (i
= 0; i
< mlen
; i
++)
223 result
[result
[0] - i
] = a
[i
+mlen
];
225 /* Free temporary arrays */
226 for (i
= 0; i
< 2*mlen
; i
++) a
[i
] = 0; free(a
);
227 for (i
= 0; i
< 2*mlen
; i
++) b
[i
] = 0; free(b
);
228 for (i
= 0; i
< mlen
; i
++) m
[i
] = 0; free(m
);
229 for (i
= 0; i
< mlen
; i
++) n
[i
] = 0; free(n
);
233 * Compute (p * q) % mod.
234 * The most significant word of mod MUST be non-zero.
235 * We assume that the result array is the same size as the mod array.
237 void modmul(Bignum p
, Bignum q
, Bignum mod
, Bignum result
)
239 unsigned short *a
, *n
, *m
, *o
;
241 int pqlen
, mlen
, i
, j
;
243 /* Allocate m of size mlen, copy mod to m */
244 /* We use big endian internally */
246 m
= malloc(mlen
* sizeof(unsigned short));
247 for (j
= 0; j
< mlen
; j
++) m
[j
] = mod
[mod
[0] - j
];
249 /* Shift m left to make msb bit set */
250 for (mshift
= 0; mshift
< 15; mshift
++)
251 if ((m
[0] << mshift
) & 0x8000) break;
253 for (i
= 0; i
< mlen
- 1; i
++)
254 m
[i
] = (m
[i
] << mshift
) | (m
[i
+1] >> (16-mshift
));
255 m
[mlen
-1] = m
[mlen
-1] << mshift
;
258 pqlen
= (p
[0] > q
[0] ? p
[0] : q
[0]);
260 /* Allocate n of size pqlen, copy p to n */
261 n
= malloc(pqlen
* sizeof(unsigned short));
263 for (j
= 0; j
< i
; j
++) n
[j
] = 0;
264 for (j
= 0; j
< p
[0]; j
++) n
[i
+j
] = p
[p
[0] - j
];
266 /* Allocate o of size pqlen, copy q to o */
267 o
= malloc(pqlen
* sizeof(unsigned short));
269 for (j
= 0; j
< i
; j
++) o
[j
] = 0;
270 for (j
= 0; j
< q
[0]; j
++) o
[i
+j
] = q
[q
[0] - j
];
272 /* Allocate a of size 2*pqlen for result */
273 a
= malloc(2 * pqlen
* sizeof(unsigned short));
275 /* Main computation */
276 bigmul(n
, o
, a
, pqlen
);
277 bigmod(a
, m
, mlen
, 2*pqlen
);
279 /* Fixup result in case the modulus was shifted */
281 for (i
= 2*pqlen
- mlen
- 1; i
< 2*pqlen
- 1; i
++)
282 a
[i
] = (a
[i
] << mshift
) | (a
[i
+1] >> (16-mshift
));
283 a
[2*pqlen
-1] = a
[2*pqlen
-1] << mshift
;
284 bigmod(a
, m
, mlen
, pqlen
*2);
285 for (i
= 2*pqlen
- 1; i
>= 2*pqlen
- mlen
; i
--)
286 a
[i
] = (a
[i
] >> mshift
) | (a
[i
-1] << (16-mshift
));
289 /* Copy result to buffer */
290 for (i
= 0; i
< mlen
; i
++)
291 result
[result
[0] - i
] = a
[i
+2*pqlen
-mlen
];
293 /* Free temporary arrays */
294 for (i
= 0; i
< 2*pqlen
; i
++) a
[i
] = 0; free(a
);
295 for (i
= 0; i
< mlen
; i
++) m
[i
] = 0; free(m
);
296 for (i
= 0; i
< pqlen
; i
++) n
[i
] = 0; free(n
);
297 for (i
= 0; i
< pqlen
; i
++) o
[i
] = 0; free(o
);
301 * Decrement a number.
303 void decbn(Bignum bn
) {
305 while (i
< bn
[0] && bn
[i
] == 0)
311 * Read an ssh1-format bignum from a data buffer. Return the number
314 int ssh1_read_bignum(unsigned char *data
, Bignum
*result
) {
315 unsigned char *p
= data
;
324 b
= (w
+7)/8; /* bits -> bytes */
325 w
= (w
+15)/16; /* bits -> words */
332 unsigned char byte
= *p
++;
334 bn
[1+i
/2] |= byte
<<8;
345 * Return the bit count of a bignum, for ssh1 encoding.
347 int ssh1_bignum_bitcount(Bignum bn
) {
348 int bitcount
= bn
[0] * 16 - 1;
350 while (bitcount
>= 0 && (bn
[bitcount
/16+1] >> (bitcount
% 16)) == 0)
356 * Return the byte length of a bignum when ssh1 encoded.
358 int ssh1_bignum_length(Bignum bn
) {
359 return 2 + (ssh1_bignum_bitcount(bn
)+7)/8;
363 * Return a byte from a bignum; 0 is least significant, etc.
365 int bignum_byte(Bignum bn
, int i
) {
367 return 0; /* beyond the end */
369 return (bn
[i
/2+1] >> 8) & 0xFF;
371 return (bn
[i
/2+1] ) & 0xFF;
375 * Write a ssh1-format bignum into a buffer. It is assumed the
376 * buffer is big enough. Returns the number of bytes used.
378 int ssh1_write_bignum(void *data
, Bignum bn
) {
379 unsigned char *p
= data
;
380 int len
= ssh1_bignum_length(bn
);
382 int bitc
= ssh1_bignum_bitcount(bn
);
384 *p
++ = (bitc
>> 8) & 0xFF;
385 *p
++ = (bitc
) & 0xFF;
386 for (i
= len
-2; i
-- ;)
387 *p
++ = bignum_byte(bn
, i
);