The modulus of RSA has been enlarged over the years in order to thwart improved attacks. As one would assume, public-key algorithms become slower as the modulus length increases. We study the relation between modulus length and performance in this problem. The performance of RSA, and of almost any other public-key algorithm, is dependent on how fast modulo exponentiation with large numbers can be performed.1. Assume that one modulo multiplication or squaring with k-bit numbers takes c · k2 clock cycles, where c is a constant. How much slower is RSA encryption/decryption with 1024 bits compared to RSA with 512 bits on average? Only consider the encryption/decryption itself with an exponent of full length and the square-and-multiply algorithm.

2. In practice, the Karatsuba algorithm, which has an asymptotical complexity that is proportional to klog2 3, is often used for long number multiplication in cryptography. Assume that this more advanced technique requires clock cycles for multiplication or squaring where c’ is a constant. What is the ratio between RSA encryption with 1024 bit and RSA with 512 bit if the Karatsuba algorithm is used in both cases? Again, assume that full-length exponents are being used.