Integer Factorization Based Cryptography
Song Yuan Yan · 2012
This chapter examines the IFP-based cryptographic systems and protocols, including the famous RSA cryptographic system; the factoring-equivalent Rabin cryptographic system; and the quadratic residuosity based probabilistic encryption. The original version of the RSA cryptosystem is a type of deterministic cryptosystem, in which the same cipher text is obtained for the same plaintext even at a different time. The most straightforward attacks on RSA are the integer factorization attack and discrete logarithm attack. If there are ef?cient algorithms for the integer factorization problem and the discrete logarithm problem, then RSA can be completely broken in polynomial-time. The search for such an ef?cient algorithm is the most important unsolved problem in computational number theory. The chapter introduces some elementary attacks on RSA, based on some elementary number-theoretic properties and the weakness of RSA. The RSA function enjoys a certain kind of self-reducibility, which, on the one hand is good but on the other hand is bad.