Keywords: digital signature, factorization problem, discrete logarithm problem, double hard problem, quadratic residue
Received November 18, 2003; revised July 6 & September 19, 2005; accepted October 31, 2005.
Communicated by Tzong-Chen Wu.
| Previous | [ 1] | [ 2] | [ 3] | [ 4] | [ 5] | [ 6] | [ 7] | [ 8] | [ 9] | [ 10] | [ 11] | [ 12] | [ 13] | [ 14] | [ 15] | [ 16] | [ 17] | [ 18] | [ 19] | [ 20] |
¡@
H. F. Lin, Jenshiuh Liu and C. Y. Chen*
Department of Information Engineering and Computer Science
*Department of Communications
Feng Chia University
Taichung, 407 Taiwan
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.
Received November 18, 2003; revised July 6 & September 19, 2005; accepted October 31, 2005.
Communicated by Tzong-Chen Wu.