Pick faster private exponent

Question

I recently tried to send 1536-bit modulus CSR to COMODO. They refused to sign the certificate.
I later found out that it's because NIST mandated 2048-bit modulus on the SSL certificate. I think it's overkill so maybe I can use smaller private exponent. (which I hope will lessen server load with reduced security margin as a trade off)

I inspected the keys generated by OpenSSL and found that private exponent is about the same size (slightly smaller) as the modulus (256 bytes). Just 96 bytes private exponent should suffice (with some margin) from Wiener's attack.

The problem is I can't think of a way to generate such key. Since public exponent is fixed (I'm not sure but it's supposed to. I never see other value than 65537 used.) IMHO to make such key possible it should begin at picking 2 primes. At my level of mathematics that's out of the question.

I gave up on trying to generate special certificate but I just curious is it possible and practical to accomplish what I can't?
And if the answer is yes how?

Answer 1

Well, it is certainly possible to generate an RSA public/private key pair like what you're asking about -- I don't know what the OpenSSL API allows you can do, but if you don't restrict yourself to that, well, it is certainly possible to craft such a keypair. You'll come up with a public key with an enormous exponent (and I wouldn't be shocked if not everyone would accept it), but it'd be possible.

On the other hand, I would argue that it's not a good idea. For one, you're looking at only a 25% speed up. You may be thinking "96 bytes is roughly a third of 256 bytes; given that modular exponentiation is linear in the log of the exponent (keeping everything else constant), shouldn't I see a not-quite 3 times improvement?

Well, no, you won't (or, if you do, you're doing it wrong). The key is the Chinese Remainder Theorem optimization (already referenced by Ricky Demer); here, you do the private operation both "mod p" and "mod q", and then recombine the two halves. That is, you compute:

$M_p = (C \bmod p) ^ {d\ \bmod\ p-1} \bmod p$

$M_q = (C \bmod q) ^ {d\ \bmod\ q-1} \bmod q$

Look at the exponents; you're not using the full $d$ (roughly 256 bytes); you're using $d\ \bmod\ p-1$ and $d\ \bmod\ q-1$; those are 128 bytes each. So, if you replace $d$ with a 96 byte number, what you're doing is replacing those 128 byte numbers with a 96 byte number; that gives you a far smaller speedup than what you were thinking of.

We're not sure whether Weiner's attack can be extended to a private exponent of size 0.375 times the modulus size; however given the relatively small speedup this gives, it wouldn't appear to be worth the risk.

Instead, if you are concerned with performance, you might want to investigate Elliptic Curve certificates.