Cryptanalysis of Server-Aided RSA Key Generation Protocols at MADNES 2005

摘要

At MADNES 2005, Y. Chen et al. proposed two improved server-aided RSA key generation protocols, which are claimed to be secure against collusion attack. However, at ISPEC 2006, T. Cao et al. presented a collusion attack on Chen's standard server-aided RSA key generation protocol and can get the plaintext from a ciphertext. In this paper, we propose a full cryptanalysis of Chen's two server-aided RSA key generation protocols. Firstly, we give a further analysis of Chen's standard protocol and can recover the factorization of the RSA modulus N with the complexity O(log~3 (N)). Secondly, we propose two collusion attacks on Chen's unbalanced RSA key generation protocol. It is proved that we can decrypt any ciphertext with the complexity O(log~3 (N)) and find the secret prime p with the complexity O(log~4(N)). Therefore, neither of Chen's two server-aided RSA key generation protocols can resist collusion attack.