/*
- * RSA implementation just sufficient for ssh client-side
- * initialisation step
- *
- * Rewritten for more speed by Joris van Rantwijk, Jun 1999.
+ * RSA implementation for PuTTY.
*/
#include <stdio.h>
freebn(b2);
}
-Bignum rsadecrypt(Bignum input, struct RSAKey *key)
+/*
+ * This function is a wrapper on modpow(). It has the same effect
+ * as modpow(), but employs RSA blinding to protect against timing
+ * attacks.
+ */
+static Bignum rsa_privkey_op(Bignum input, struct RSAKey *key)
{
+ Bignum random, random_encrypted, random_inverse;
+ Bignum input_blinded, ret_blinded;
Bignum ret;
- ret = modpow(input, key->private_exponent, key->modulus);
+
+ /*
+ * 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.)
+ */
+ 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, byte = random_byte();
+ 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;
+ }
+ }
+
+ /*
+ * RSA blinding relies on the fact that (xy)^d mod n is equal
+ * to (x^d mod n) * (y^d mod n) mod n. We invent a random pair
+ * y and y^d; then we multiply x by y, raise to the power d mod
+ * n as usual, and divide by y^d to recover x^d. Thus an
+ * attacker can't correlate the timing of the modpow with the
+ * input, because they don't know anything about the number
+ * that was input to the actual modpow.
+ *
+ * The clever bit is that we don't have to do a huge modpow to
+ * get y and y^d; we will use the number we just invented as
+ * _y^d_, and use the _public_ exponent to compute (y^d)^e = y
+ * from it, which is much faster to do.
+ */
+ random_encrypted = modpow(random, key->exponent, key->modulus);
+ random_inverse = modinv(random, key->modulus);
+ input_blinded = modmul(input, random_encrypted, key->modulus);
+ ret_blinded = modpow(input_blinded, key->private_exponent, key->modulus);
+ ret = modmul(ret_blinded, random_inverse, key->modulus);
+
+ freebn(ret_blinded);
+ freebn(input_blinded);
+ freebn(random_inverse);
+ freebn(random_encrypted);
+ freebn(random);
+
return ret;
}
+Bignum rsadecrypt(Bignum input, struct RSAKey *key)
+{
+ return rsa_privkey_op(input, key);
+}
+
int rsastr_len(struct RSAKey *key)
{
Bignum md, ex;
getstring(data, datalen, &p, &length);
if (!p)
return NULL;
- b = bignum_from_bytes(p, length);
+ b = bignum_from_bytes((unsigned char *)p, length);
return b;
}
int numlen, i;
MD5Init(&md5c);
- MD5Update(&md5c, "\0\0\0\7ssh-rsa", 11);
+ MD5Update(&md5c, (unsigned char *)"\0\0\0\7ssh-rsa", 11);
#define ADD_BIGNUM(bignum) \
numlen = (bignum_bitcount(bignum)+8)/8; \
return ret;
}
-unsigned char *rsa2_sign(void *key, char *data, int datalen, int *siglen)
+static unsigned char *rsa2_sign(void *key, char *data, int datalen,
+ int *siglen)
{
struct RSAKey *rsa = (struct RSAKey *) key;
unsigned char *bytes;
in = bignum_from_bytes(bytes, nbytes);
sfree(bytes);
- out = modpow(in, rsa->private_exponent, rsa->modulus);
+ out = rsa_privkey_op(in, rsa);
freebn(in);
nbytes = (bignum_bitcount(out) + 7) / 8;