Abstract
RSA is a widely used public key cryptosystem. However, it is possible for a RSA key generator to be embedded a backdoor such that the generated public key contains the information about the private key. Young and Yung have presented some methods to embed backdoors for RSA key generation since 1996. Most of their backdoors satisfy the properties of Strong-SETUP. That is, even though the device is reverse-engineered, anyone except the backdoor manufacturer can not distinguish whether a casually given key is generated by the backdoor device or not. However, the two MSBs of the modulus n generated by their methods have different distribution compared with those of the normal RSA modulus, and the running time of their schemes can not match the normal RSA key-generation time. Hence, anyone may detect the existence of the backdoor by observing these differences. In 2003, Crepéau and Slakmon suggested four simple RSA backdoors. Although three of their schemes have roughly the same running time as the normal RSA, they are all not Strong-SETUPs. Besides, only the last scheme, RSA-HP□, embeds the backdoor in n and the other three schemes embed the backdoor in e. When the backdoor is embedded in e, the size of e is restricted. This is impractical since e = 2^16 +1 is often used to speed RSA encryption. Based on the previous research, we propose three new backdoor mechanisms for RSA key generation, and one backdoor mechanism for rebalanced RSA-CRT. All of the methods embed the backdoor in n so the size of e is not limited. In the first method, RSA-SBLT, the technique of lattice attack is used and in the second method, RSA-SBES, the technique of exhaustive search attack is employed. Both of them roughly have the same running time as the normal RSA key generation so anyone can hardly detect the backdoor by observing the time imparity. As for our third method, RSA-BDH, we utilize the relationship between p and q to devise a backdoor mechanism which solves the problem that the two MSBs of n have abnormal distribution, as it occurs in Young and Yong's method. Moreover, we prove that RSA-BDH is a Strong-SETUP based on DH assumption. Besides the backdoor for RSA, we also devise a backdoor mechanism for Sun et al.’s rebalanced RSA-CRT. Up to now, there is no method proposed to embed the backdoor for rebalanced RSA-CRT. Hence, this is the first backdoor mechanism for rebalanced RSA-CRT.