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
assert(modulus[modulus[0]] != 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]--;
* Step 1. w <- s^-1 mod q.
*/
w = modinv(s, dss->q);
+ if (!w) {
+ freebn(r);
+ freebn(s);
+ return 0;
+ }
/*
* Step 2. u1 <- SHA(message) * w mod q.
SHA512_Init(&ss);
SHA512_Bytes(&ss, digest512, sizeof(digest512));
SHA512_Bytes(&ss, digest, sizeof(digest));
- SHA512_Final(&ss, digest512);
- smemclr(&ss, sizeof(ss));
+ while (1) {
+ SHA512_State ss2 = ss; /* structure copy */
+ SHA512_Final(&ss2, digest512);
+
+ smemclr(&ss2, sizeof(ss2));
+
+ /*
+ * Now convert the result into a bignum, and reduce it mod q.
+ */
+ proto_k = bignum_from_bytes(digest512, 64);
+ k = bigmod(proto_k, dss->q);
+ freebn(proto_k);
+ kinv = modinv(k, dss->q); /* k^-1 mod q */
+ if (!kinv) { /* very unlikely */
+ freebn(k);
+ /* Perturb the hash to think of a different k. */
+ SHA512_Bytes(&ss, "x", 1);
+ /* Go round and try again. */
+ continue;
+ }
+
+ break;
+ }
- /*
- * Now convert the result into a bignum, and reduce it mod q.
- */
- proto_k = bignum_from_bytes(digest512, 64);
- k = bigmod(proto_k, dss->q);
- freebn(proto_k);
+ smemclr(&ss, sizeof(ss));
smemclr(digest512, sizeof(digest512));
freebn(gkp);
hash = bignum_from_bytes(digest, 20);
- kinv = modinv(k, dss->q); /* k^-1 mod q */
hxr = bigmuladd(dss->x, r, hash); /* hash + x*r */
s = modmul(kinv, hxr, dss->q); /* s = k^-1 * (hash + x*r) mod q */
freebn(hxr);
bignum_cmp(random, key->modulus) >= 0) {
freebn(random);
continue;
- } else {
- break;
}
+
+ /*
+ * Also, make sure it has an inverse mod modulus.
+ */
+ random_inverse = modinv(random, key->modulus);
+ if (!random_inverse) {
+ freebn(random);
+ continue;
+ }
+
+ break;
}
/*
*/
random_encrypted = crt_modpow(random, key->exponent,
key->modulus, key->p, key->q, key->iqmp);
- random_inverse = modinv(random, key->modulus);
input_blinded = modmul(input, random_encrypted, key->modulus);
ret_blinded = crt_modpow(input_blinded, key->private_exponent,
key->modulus, key->p, key->q, key->iqmp);
freebn(key->iqmp);
key->iqmp = modinv(key->q, key->p);
+ if (!key->iqmp)
+ return 0;
}
/*
* RSA key generation.
*/
+#include <assert.h>
+
#include "ssh.h"
#define RSA_EXPONENT 37 /* we like this prime */
freebn(pm1);
freebn(qm1);
key->private_exponent = modinv(key->exponent, phi_n);
+ assert(key->private_exponent);
pfn(pfnparam, PROGFN_PROGRESS, 3, 4);
key->iqmp = modinv(key->q, key->p);
+ assert(key->iqmp);
pfn(pfnparam, PROGFN_PROGRESS, 3, 5);
/*