A widely used method for speeding up RSA encryption and RSA

A widely used method for speeding up RSA encryption and RSA signatures is the use of so called short exponents. These are numbers, which are only a few bits in length, i.e. e = 3, 17 and 2^16 + 1. Most short exponents are of the form ce = 2^n +1. Would it be advantageous to use exponents of the form 2^n - 1? Justify your answer! Compute the exponentiation m^e mod 29 of m = 5 with both variants of c for n = 4. Use the square-and-multiply algorithm and show each step of your computation. Justify your answer from part (a). Why can\'t we use short exponents d for the decryption/signature generation? Suggest a minimum bit length for the exponent d and explain your answer.

Solution

(a) No it would not advantageious to use exponents of the form 2^n-1 because it will be inefficient to compute the encryption operation.

(b) Let us take e as 9(2^3+1) and 7(2^3-1).

5 mod 29 = 5
5^2 mod 29 = 25
5^4 mod 29 = 25^2 mod 29 = 16
5^8 mod 29 = 16^2 mod 29 = 24

if e = 9, 5^9 mod 29 = 5^8 x 5 mod 29 = 24 x 5 mod 29 = 4
if e = 7, 5^7 mod 29 = 5^4 x 5^2 x 5 mod 29 = 16 x 25 x 5 mod 29 = 2000 mod 29 = 28

Here we can see 3 multiplcations need to be performed for 7 compare to 2 multiplcations for 9. The multiplcations will always be 2 for e = 2^k + 1, but it will be k-1 for e = 2^k-1

(c) We cannot use short exponents because it will vulnerable to key recovery attacks. The adversary can guess the key encryptions multiple messages using our public key. The minimum bit length should be atleast 1024, this will make sure it will be difficult for the adversary to guess the private key.