RSA security
Kaoru Kurosawa, K. Matsu, Hirohumi Kasai · Electronics and Communications in Japan (Part III Fundamental Electronic Science) · 1990
Abstract RSA is a typical public key cryptosystem, but whether or not breaking RSA is as hard as prime factorization is unknown. It is known that if the LSB sequence obtained from iterated cipher texts of RSA is distinguished from the true random sequence in a polynomial time, it is possible to break RSA. Consequently, by testing the quality of this pseudorandom sequence, the security of RSA can be evaluated. It is known also for RSA that guessing the least‐significant bit of the original message from the encrypted message with probability 1/2 + 1/poly(n) is equivalent to finding the whole original message. In this paper, it is shown first that guessing the value of the original message by mod L with probability 1/L + 1/poly(n) is as difficult as finding the entire original message. Based on the result, a multivalued pseudorandom number generator is given. Those based on the hardness of the quadratic residue property also are shown. Statistical testing of those pseudorandom numbers is attempted, leading to the evaluation of the reliability of RSA.