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
);