Assume that one modulo multiplication with k-bit numbers takes "c . k2" clock cycles, where c is a constant. How much slower is RSA encryption/decryption with k=1024 bits compared to RSA with k=512 bits on average if the number of multiplications needed is "1.5k"?

RSA with 1024 bits is eight times as slow as RSA with 512 bits

Explanation:

For simplicity it is assumed that in this problem.

Number of multiplications (and squarings) for one exponentiation with k{bit exponent:

complexity of one multiplication is given as

Complexity for the total exponentiation is given as

Now assuming k1=512,k2=1024 and taking the ratios which are given as

So RSA with 1024 bits is eight times as slow as RSA with 512 bits