We discuss some attacks that are possible if we choose an excessively small exponent such as 3. We have already observed that implementations of RSA use small encryption exponents (typically ) to improve the performance of encryption function. This implies that n should never be reused for different key pairs: any time we generate a key pair we need to generate a new modulus n. Notice also that once we leak a private key the modulus is no more secure. This proves that if an exponent is leaked then n is compromised, thus breaking a private key is as difficult as factoring.
(See for more detail).Īs for Monte Carlo algorithms, we can iterate a Las Vegas algorithm as needed. Given an algorithm that computes exponent a we can write a probabilistic “Las Vegas” algorithm that factorises n with probability at least. It can be proved that this would allow to factor n: It could be possible, in principle, to compute the private exponent without necessarily computing. Given an algorithm that computes Φ(n) it is enough to solve the system of equations: It is however trivial to see that computing Φ(n) is at least as difficult as factoring n. Computing Φ(n)Īs already discussed, security of RSA is based on the secrecy of Φ(n)=(p-1)(q-1). We now discuss the main results about security of RSA cipher.
0 kommentar(er)
