+ 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;
+ }
+ byte = digest512[digestused++];
+ }
+ v = byte & 1;
+ byte >>= 1;
+ bitsleft--;
+ bignum_set_bit(random, bits, v);
+ }
+
+ /*
+ * Now check that this number is strictly greater than
+ * zero, and strictly less than modulus.
+ */
+ if (bignum_cmp(random, Zero) <= 0 ||
+ bignum_cmp(random, key->modulus) >= 0) {
+ freebn(random);
+ continue;
+ } else {
+ break;