In 1998, Shao proposed two digital signature schemes and claimed that the security of which is based on the difficulties of computing both integer factorization and discrete logarithm. However, in 1999, Lee demonstrated that Shao’s signature schemes can be broken if the factorization problem can be solved. This paper presents an improvement of Shao’s signature schemes and shows that it can resist Lee’s attack. This makes our proposed scheme based on two hard problems. Some possible common attacks are considered. We show that the problem of recovering the signer’s secret key from his/her public key is equivalent to solve both the discrete logarithm problem and the factorization problem; the problem of forging a valid signature for a message is at least equivalent to solve the discrete logarithm problem or the factorization problem. In addition, our proposed scheme is immune from substitution and homomorphism attacks.