How do “low exponents” make RSA encrypt faster?
The RSA cryptosystem involves repeated multiplication in the group of numbers modulo p. Thus encryption requires taking a certain element g of the group and computing gk, and then decryption involves taking another element h and computing hn. In order to make encryption faster, sometimes people take the encryption exponent k to be very small. Typical examples of encryption exponents that people use are k=3 or k=17=24+1 or k=216+1=65537. Don Coppersmith has shown that the use of a very small exponent such as k=3 is probably not a good idea, at least for unpadded RSA messages. D. Coppersmith, Small solutions to polynomial equations and low exponent RSA vulnerabilities, Journal of Cryptology 10 (1997), 233-260. C. Coupe, P. Nguyen, J. Stern, The effectiveness of lattice attacks against low-exponent RSA, Public Key Cryptography ’99, Lecture Notes in Computer Science, Springer-Verlag. However, if the message is padded (as is generally the case), then many cryptographers feel that using k=3
