#include <stdlib.h>
#include <string.h>
-#if 0 // use PuTTY main debugging for diagbn()
-#include <windows.h>
-#include "putty.h"
-#define debugprint debug
-#else
-#define debugprint(x) printf x
-#endif
+#include "misc.h"
#define BIGNUM_INTERNAL
typedef unsigned short *Bignum;
* Compute p % mod.
* The most significant word of mod MUST be non-zero.
* We assume that the result array is the same size as the mod array.
- * We optionally write out a quotient.
+ * We optionally write out a quotient if `quotient' is non-NULL.
+ * We can avoid writing out the result if `result' is NULL.
*/
-void bigmod(Bignum p, Bignum mod, Bignum result, Bignum quotient)
+void bigdivmod(Bignum p, Bignum mod, Bignum result, Bignum quotient)
{
unsigned short *n, *m;
int mshift;
}
/* Copy result to buffer */
- for (i = 1; i <= result[0]; i++) {
- int j = plen - i;
- result[i] = j >= 0 ? n[j] : 0;
+ if (result) {
+ for (i = 1; i <= result[0]; i++) {
+ int j = plen - i;
+ result[i] = j >= 0 ? n[j] : 0;
+ }
}
/* Free temporary arrays */
bn[i]--;
}
-Bignum bignum_from_bytes(unsigned char *data, int nbytes)
+Bignum bignum_from_bytes(const unsigned char *data, int nbytes)
{
Bignum result;
int w, i;
* Read an ssh1-format bignum from a data buffer. Return the number
* of bytes consumed.
*/
-int ssh1_read_bignum(unsigned char *data, Bignum * result)
+int ssh1_read_bignum(const unsigned char *data, Bignum * result)
{
- unsigned char *p = data;
+ const unsigned char *p = data;
int i;
int w, b;
}
/*
- * Convert a (max 16-bit) short into a bignum.
+ * Convert a (max 32-bit) long into a bignum.
*/
-Bignum bignum_from_short(unsigned short n)
+Bignum bignum_from_long(unsigned long n)
{
Bignum ret;
- ret = newbn(2);
- ret[1] = n & 0xFFFF;
- ret[2] = (n >> 16) & 0xFFFF;
- ret[0] = (ret[2] ? 2 : 1);
+ ret = newbn(3);
+ ret[1] = (unsigned short)(n & 0xFFFF);
+ ret[2] = (unsigned short)((n >> 16) & 0xFFFF);
+ ret[3] = 0;
+ ret[0] = (ret[2] ? 2 : 1);
return ret;
}
void diagbn(char *prefix, Bignum md)
{
+#ifdef DEBUG
int i, nibbles, morenibbles;
static const char hex[] = "0123456789ABCDEF";
- debugprint(("%s0x", prefix ? prefix : ""));
+ debug(("%s0x", prefix ? prefix : ""));
nibbles = (3 + bignum_bitcount(md)) / 4;
if (nibbles < 1)
nibbles = 1;
morenibbles = 4 * md[0] - nibbles;
for (i = 0; i < morenibbles; i++)
- debugprint(("-"));
+ debug(("-"));
for (i = nibbles; i--;)
- debugprint(
- ("%c",
- hex[(bignum_byte(md, i / 2) >> (4 * (i % 2))) & 0xF]));
+ debug(("%c",
+ hex[(bignum_byte(md, i / 2) >> (4 * (i % 2))) & 0xF]));
if (prefix)
- debugprint(("\n"));
+ debug(("\n"));
+#endif
+}
+
+/*
+ * Simple division.
+ */
+Bignum bigdiv(Bignum a, Bignum b)
+{
+ Bignum q = newbn(a[0]);
+ bigdivmod(a, b, NULL, q);
+ return q;
+}
+
+/*
+ * Simple remainder.
+ */
+Bignum bigmod(Bignum a, Bignum b)
+{
+ Bignum r = newbn(b[0]);
+ bigdivmod(a, b, r, NULL);
+ return r;
}
/*
Bignum a = copybn(av);
Bignum b = copybn(bv);
- diagbn("a = ", a);
- diagbn("b = ", b);
while (bignum_cmp(b, Zero) != 0) {
Bignum t = newbn(b[0]);
- bigmod(a, b, t, NULL);
- diagbn("t = ", t);
+ bigdivmod(a, b, t, NULL);
while (t[0] > 1 && t[t[0]] == 0)
t[0]--;
freebn(a);
while (bignum_cmp(b, One) != 0) {
Bignum t = newbn(b[0]);
Bignum q = newbn(a[0]);
- bigmod(a, b, t, q);
+ bigdivmod(a, b, t, q);
while (t[0] > 1 && t[t[0]] == 0)
t[0]--;
freebn(a);