# Pick faster private exponent

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?

-
Are you already using CRT decryption? $\;$ –  Ricky Demer Jun 5 at 20:24
@RickyDemer yes I think so, since my private key file also include those parameters in CRT. Thank you for pointing it out. That should make modular exponentiation operate on half size of the modulus. However, I'm curious anyway if it have solution to the problem or not. In practical aspect my question may change to there is a way to pick smaller dP and dQ in CRT? (I'm also interested in the original question though.) –  Curious Sam Jun 5 at 20:44
A perhaps relevant answer to a different question. –  fgrieu Jun 5 at 22:00
You could consider multi-prime RSA if your implementation supports it. –  CodesInChaos Jun 6 at 11:39

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.

-
Thank you for the clarification. Practical server authentication that can be used today is only RSA. (probably due to patent issues.) so I'm just looking into RSA optimization. –  Curious Sam Jun 5 at 21:18