© The Institution of Engineering and Technology
Baocang and Yupu proposed a relatively fast public key cryptosystem. The authors claim that the security of their system is based on two number-theoretic hard problems, namely the simultaneous Diophantine approximation problem and the integer factorisation problem. In this article we present a polynomial time heuristic attack that enables us to recover the private key from the public key. In particular, we show that breaking the system can be reduced to finding a short vector in a lattice which can be achieved using the L3-lattice reduction algorithm.
References
-
-
1)
-
Youssef, A.M., Gong, G.: `Cryptanalysis of a public key cryptosystem proposed at ACISP 2000', Proc. ACISP01, July 2001, Sydney, Australia, p. 15–20, Lect. Notes Comput. Sci., 2119.
-
2)
-
Boneh, D., Venkatesan, R.: `Hardness of computing the most significant bits of secret keys in Diffie-Hellman and related schemes', Proc. of CRYPTO '96, Aug. 1996, Santa Barbara, CA, USA, p. 129–142, Lect. Notes Comput. Sci., 1109.
-
3)
-
Nguyen, P., Stern, J.: `Cryptanalysis of the Ajtai-Dwork Cryptosystem', Advances in Cryptology, Proc. CRYPTO' 98, Aug. 1998, Santa Barbara, CA, USA, p. 223–242, Lect. Notes Comput. Sci., 1462.
-
4)
-
Nguyen, P., Stern, J.: `Cryptanalysis of a fast public key cryptosystem presented at SAC '97', Proc. Workshop on Selected Areas in Cryptography, Aug. 1998, Kingston, Canada, p. 213–218, Lect. Notes Comput. Sci., 1556.
-
5)
-
Nguyen, P., Stern, J.: `Lattice reduction in cryptology: An update Algorithmic Number Theory', Proc. of ANTS-IV, July 2000, p. 85–112, Lect. Notes Comput. Sci., 1838.
-
6)
-
I. Niven ,
H.S. Zuckerman
.
(1966)
An introduction to the theory of numbers.
-
7)
-
W. Baocang ,
H. Yupu
.
Public key cryptosystem based on two cryptographic assumptions.
IEE Proc. Commun.
,
6 ,
861 -
865
-
8)
-
A.J. Menezes ,
P.C. van Oorschot ,
S.A. Vanstone
.
(1996)
Handbook of applied cryptographic research.
-
9)
-
A.K. Lenstra ,
H.W. Lenstra ,
L. Lovász
.
Factoring polynomials with rational coefficients.
Math. Ann.
,
515 -
534
http://iet.metastore.ingenta.com/content/journals/10.1049/ip-ifs_20060075
Related content
content/journals/10.1049/ip-ifs_20060075
pub_keyword,iet_inspecKeyword,pub_concept
6
6