- unsigned short *a, *b, *n, *m;
- int mshift;
- int mlen, i, j;
-
- /* Allocate m of size mlen, copy mod to m */
- /* We use big endian internally */
- mlen = mod[0];
- m = malloc(mlen * sizeof(unsigned short));
- for (j = 0; j < mlen; j++) m[j] = mod[mod[0] - j];
-
- /* Shift m left to make msb bit set */
- for (mshift = 0; mshift < 15; mshift++)
- if ((m[0] << mshift) & 0x8000) break;
- if (mshift) {
- for (i = 0; i < mlen - 1; i++)
- m[i] = (m[i] << mshift) | (m[i+1] >> (16-mshift));
- m[mlen-1] = m[mlen-1] << mshift;
- }
-
- /* Allocate n of size mlen, copy base to n */
- n = malloc(mlen * sizeof(unsigned short));
- i = mlen - base[0];
- for (j = 0; j < i; j++) n[j] = 0;
- for (j = 0; j < base[0]; j++) n[i+j] = base[base[0] - j];
-
- /* Allocate a and b of size 2*mlen. Set a = 1 */
- a = malloc(2 * mlen * sizeof(unsigned short));
- b = malloc(2 * mlen * sizeof(unsigned short));
- for (i = 0; i < 2*mlen; i++) a[i] = 0;
- a[2*mlen-1] = 1;
-
- /* Skip leading zero bits of exp. */
- i = 0; j = 15;
- while (i < exp[0] && (exp[exp[0] - i] & (1 << j)) == 0) {
- j--;
- if (j < 0) { i++; j = 15; }
- }
-
- /* Main computation */
- while (i < exp[0]) {
- while (j >= 0) {
- bigmul(a + mlen, a + mlen, b, mlen);
- bigmod(b, m, mlen);
- if ((exp[exp[0] - i] & (1 << j)) != 0) {
- bigmul(b + mlen, n, a, mlen);
- bigmod(a, m, mlen);
- } else {
- unsigned short *t;
- t = a; a = b; b = t;
- }
- j--;
+ Bignum random, random_encrypted, random_inverse;
+ Bignum input_blinded, ret_blinded;
+ Bignum ret;
+
+ SHA512_State ss;
+ unsigned char digest512[64];
+ int digestused = lenof(digest512);
+ int hashseq = 0;
+
+ /*
+ * Start by inventing a random number chosen uniformly from the
+ * range 2..modulus-1. (We do this by preparing a random number
+ * of the right length and retrying if it's greater than the
+ * modulus, to prevent any potential Bleichenbacher-like
+ * attacks making use of the uneven distribution within the
+ * range that would arise from just reducing our number mod n.
+ * There are timing implications to the potential retries, of
+ * course, but all they tell you is the modulus, which you
+ * already knew.)
+ *
+ * To preserve determinism and avoid Pageant needing to share
+ * the random number pool, we actually generate this `random'
+ * number by hashing stuff with the private key.
+ */
+ while (1) {
+ int bits, byte, bitsleft, v;
+ random = copybn(key->modulus);
+ /*
+ * Find the topmost set bit. (This function will return its
+ * index plus one.) Then we'll set all bits from that one
+ * downwards randomly.
+ */
+ bits = bignum_bitcount(random);
+ byte = 0;
+ bitsleft = 0;
+ while (bits--) {
+ if (bitsleft <= 0) {
+ bitsleft = 8;
+ /*
+ * Conceptually the following few lines are equivalent to
+ * byte = random_byte();
+ */
+ if (digestused >= lenof(digest512)) {
+ unsigned char seqbuf[4];
+ PUT_32BIT(seqbuf, hashseq);
+ SHA512_Init(&ss);
+ SHA512_Bytes(&ss, "RSA deterministic blinding", 26);
+ SHA512_Bytes(&ss, seqbuf, sizeof(seqbuf));
+ sha512_mpint(&ss, key->private_exponent);
+ SHA512_Final(&ss, digest512);
+ hashseq++;
+
+ /*
+ * Now hash that digest plus the signature
+ * input.
+ */
+ SHA512_Init(&ss);
+ SHA512_Bytes(&ss, digest512, sizeof(digest512));
+ sha512_mpint(&ss, input);
+ SHA512_Final(&ss, digest512);
+
+ digestused = 0;