7.14. The modulus of RSA has been enlarged over the years in order to thwart im proved attacks. As one would assume, public-key algorithms become slower as the modulus length increases. We study the relation between modulus length and perfor- mance 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 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 encryp- tion/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 klog23, is often used for long number multiplication in cryptog- raphy. Assume that this more advanced technique requires e klogz3-.k1.585 clock cycles for multiplication or squaring where c is a constant. What is the Problems 203 ratio between RSA encryption with 1024 bit and RSA with 512 bit if the Karat suba algorithm is used in both cases? Again, assume that full-length exponents are being used
