Efficient CRT-RSA Decryption for Small Encryption Exponents

Consider CRT-RSA with the parameters p,q,e, d(p), d(q), where p,g are secret primes, e is the public encryption exponent and d(p), d(q) are the private decryption exponents. We present an efficient method to select CRT-RSA parameters in such a manner so that the decryption becomes faster for small encryption exponents. This is the most frequently used situation for application of RSA in commercial domain. Our idea is to choose e and the factors (with low Hamming weight) of d(p), d(q) first and then applying the extended Euclidean algorithm, we obtain p, q of same bit size. For small e, we get an asymptotic reduction of the order of 1/3 in the decryption time compared to standard CRT-RSA parameters for large N = pq. In case of practical parameters, with 1024 bits N and e = 2(16) + 1, we achieve a reduction of more than 27%. Extensive security analysis is presented for our selected parameters and benchmark examples are also provided.