projects
/
u
/
mdw
/
putty
/ blobdiff
commit
grep
author
committer
pickaxe
?
search:
re
summary
|
shortlog
|
log
|
commit
|
commitdiff
|
tree
raw
|
inline
| side by side
Make modinv able to return NULL if its inputs are not coprime, and
[u/mdw/putty]
/
sshbn.c
diff --git
a/sshbn.c
b/sshbn.c
index
ecdb90e
..
a206783
100644
(file)
--- a/
sshbn.c
+++ b/
sshbn.c
@@
-624,6
+624,7
@@
static void internal_mod(BignumInt *a, int alen,
int i, k;
m0 = m[0];
int i, k;
m0 = m[0];
+ assert(m0 >> (BIGNUM_INT_BITS-1) == 1);
if (mlen > 1)
m1 = m[1];
else
if (mlen > 1)
m1 = m[1];
else
@@
-868,6
+869,7
@@
Bignum modpow(Bignum base_in, Bignum exp, Bignum mod)
len = mod[0];
r = bn_power_2(BIGNUM_INT_BITS * len);
inv = modinv(mod, r);
len = mod[0];
r = bn_power_2(BIGNUM_INT_BITS * len);
inv = modinv(mod, r);
+ assert(inv); /* cannot fail, since mod is odd and r is a power of 2 */
/*
* Multiply the base by r mod n, to get it into Montgomery
/*
* Multiply the base by r mod n, to get it into Montgomery
@@
-988,6
+990,12
@@
Bignum modmul(Bignum p, Bignum q, Bignum mod)
int pqlen, mlen, rlen, i, j;
Bignum result;
int pqlen, mlen, rlen, i, j;
Bignum result;
+ /*
+ * The most significant word of mod needs to be non-zero. It
+ * should already be, but let's make sure.
+ */
+ assert(mod[mod[0]] != 0);
+
/* Allocate m of size mlen, copy mod to m */
/* We use big endian internally */
mlen = mod[0];
/* Allocate m of size mlen, copy mod to m */
/* We use big endian internally */
mlen = mod[0];
@@
-1087,6
+1095,12
@@
static void bigdivmod(Bignum p, Bignum mod, Bignum result, Bignum quotient)
int mshift;
int plen, mlen, i, j;
int mshift;
int plen, mlen, i, j;
+ /*
+ * The most significant word of mod needs to be non-zero. It
+ * should already be, but let's make sure.
+ */
+ assert(mod[mod[0]] != 0);
+
/* Allocate m of size mlen, copy mod to m */
/* We use big endian internally */
mlen = mod[0];
/* Allocate m of size mlen, copy mod to m */
/* We use big endian internally */
mlen = mod[0];
@@
-1617,9
+1631,22
@@
Bignum modinv(Bignum number, Bignum modulus)
Bignum x = copybn(One);
int sign = +1;
Bignum x = copybn(One);
int sign = +1;
+ assert(number[number[0]] != 0);
+ assert(modulus[modulus[0]] != 0);
+
while (bignum_cmp(b, One) != 0) {
while (bignum_cmp(b, One) != 0) {
- Bignum t = newbn(b[0]);
- Bignum q = newbn(a[0]);
+ Bignum t, q;
+
+ if (bignum_cmp(b, Zero) == 0) {
+ /*
+ * Found a common factor between the inputs, so we cannot
+ * return a modular inverse at all.
+ */
+ return NULL;
+ }
+
+ t = newbn(b[0]);
+ q = newbn(a[0]);
bigdivmod(a, b, t, q);
while (t[0] > 1 && t[t[0]] == 0)
t[0]--;
bigdivmod(a, b, t, q);
while (t[0] > 1 && t[t[0]] == 0)
t[0]--;