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