Youssef, Amr M. (2011) Cryptanalysis of a quadratic knapsack cryptosystem. Computers & Mathematics with Applications, 61 (4). pp. 1261-1265. ISSN 08981221
Preview |
Text (application/pdf)
132kBamr2011.pdf - Accepted Version |
Official URL: http://dx.doi.org/10.1016/j.camwa.2011.01.006
Abstract
Wang and Hu [B. Wang and Y. Hu, Quadratic compact knapsack public-key cryptosystem, Comput. Math. Appl. 59 (1) (2010) 194–206] proposed a knapsack-type public-key cryptosystem by introducing an easy quadratic compact knapsack problem and then using the Chinese remainder theorem to disguise the easy knapsack instant. In this paper, we present a heuristic stereotyped message attack that allows the cryptanalyst to recover the plaintext message when partial information about the original message is known. In particular, as shown by our experiments, for the proposed system parameter n = 100 which corresponds to a block length of 400 bits, exposing 60% of the plaintext allows the
cryptanalyst to recover the remaining 160 bits of the essage with a success probability of about 90% in about 2 hours.
| Divisions: | Concordia University > Gina Cody School of Engineering and Computer Science > Concordia Institute for Information Systems Engineering |
|---|---|
| Item Type: | Article |
| Refereed: | Yes |
| Authors: | Youssef, Amr M. |
| Journal or Publication: | Computers & Mathematics with Applications |
| Date: | 2011 |
| Digital Object Identifier (DOI): | 10.1016/j.camwa.2011.01.006 |
| Keywords: | Public-key cryptography Cryptanalysis Knapsack cryptosystem Lattice basis reduction Stereotyped message attack |
| ID Code: | 976802 |
| Deposited By: | Danielle Dennie |
| Deposited On: | 28 Jan 2013 13:30 |
| Last Modified: | 18 Jan 2018 17:43 |
References:
[1] R.C. Merkle, M.E. Hellman, Hiding information and signatures in trapdoor knapsacks, IEEE Trans. Inform. Theory 24 (1978) 525–530.[2] A.J. Menezes, P.C. van Oorschot, S.A. Vanstone, Handbook of Applied Cryptographic Research, CRC Press, 1996.
[3] A.M. Odlyzko, The rise and fall of knapsack cryptosystems, in: Cryptology and Computational Number Theory, in: Proc. of Symposia in Applied Mathematics, vol. 42, AMS, 1990, pp. 75–88.
[4] P. Nguyen, J. Stern, Lattice reduction in cryptology: an update, in: Algorithmic Number Theory, Proc. of ANTS-IV, in: LNCS, vol. 1838, Springer-Verlag,
2000, pp. 85–112.
[5] A.K. Lenstra, H.W. Lenstra, L. Lovász, Factoring polynomials with rational coefficients, Math. Ann. 261 (1982) 515–534.
[6] B. Wang, Y. Hu, Quadratic compact knapsack public-key cryptosystem, Comput. Math. Appl. 59 (1) (2010) 194–206.
[7] P. Nguyen, J. Stern, Merkle–Hellman revisited: a cryptanalysis of the Qu–Vanstone cryptosystem based on group factorizations, in: Proc. of Crypto’97, in: LNCS, vol. 1294, Springer-Verlag, Berlin, 1997, pp. 198–212.
[8] S.Y. Yan, Cryptanalytic Attacks on RSA, 1st ed., Springer, 2008.
[9] M.J. Hinek, Cryptanalysis of RSA and its Variants, CRC Press, Taylor & Francis Group, 2009.
[10] D. Boneh, Twenty Years of Attacks on the RSA Cryptosystem, in: Notices of the AMS, vol. 46, 1999, pp. 203–213.
[11] Antoine Joux, Algorithmic Cryptanalysis, Chapman & Hall, CRC Cryptography and Network Security Series, 2009.
[12] T. Nagell, Introduction to Number Theory, Wiley, New York, 1951.
[13] Rainer Dietmann, Small solutions of quadratic diophantine equations, Proc. London Math. Soc. 86 (3) (2003) 545–582.
Repository Staff Only: item control page
Download Statistics
Download Statistics