Article

Article title DIOPHANTINE DIFFICULTIES OF ATTACKS ON NON-STANDARD KNAPSACKS INFORMATION SECURITY SYSTEMS
Authors V.O. Osipyan, Yu.A. Karpenko, A.S. Zhuck, A.H. Arutyunyan
Section SECTION IV. METHODS AND TOOLS CRYPTOGRAPHY AND STEGANOGRAPHY
Month, Year 12, 2013 @en
Index UDC 519.72
DOI
Abstract Development of the asymmetric cryptography started with the appearance of the first knapsack information protection system, when, in 1976, Ralph Merkel and Martin Hellman proposed to use different keys for forward and reverse mapping data for encryption. Now this model, like many based on are considered to be insecure. As a result the authority of knapsack systems was low. However, some of these systems are still considered persistent, for example, the model proposed in 1988 by Ben Shore and Ronald Rivest. In the article stated and solved the problem of argumentation of cryptographic strength of the non-standard knapsack information security systems. Justified diophantine difficulties that arise in the study of vulnerabilities of the investigated information security systems. Revealed the qualitative features of non-standard knapsack systems that increase their resistance to known attacks.

Download PDF

Keywords Knapsack information security system; resistance of algorithm; cryptographic attack; diophantine difficulties; knapsack algorithm; knapsack vector; original message; plain text; key; ciphertext.
References 1. Саломаа А. Криптография с открытым ключом. – М.: Мир, 1995.
2. Шеннон К. Работы по теории информации и кибернетики. – М. 1963. – 832 с.
3. Осипян В.О. О системе защиты информации на основе проблемы рюкзака // Известия Томского политехнического университета. – 2006. – Т. 309, № 2.
4. Осипян В.О. Моделирование систем защиты информации содержащих диофантовы трудности. LAP LAMBERT Academic Publishing, 2012.
5. Diffie W., Hellman M. New directions in cryptography // IEEE Transactions on Information Theory. – 1976. – Vol. 22. – P. 644-654.
6. Rivest R.L., Chor B. A knapsack-type public key cryptosystem based on arithmetic in finite fields // IEEE Transactions on Information Theory. – 1988. – Vol. 34, № 5. – P. 901-909.
7. Martello S. T.P. Knapsack problems : algorithms and computer implementations // Chichester: JOHN WILEY & SONS. – 1990. – P. 137-138.
8. Merkle R.C., Hellman M.E. Hiding Information and Signatures in Trapdook Knapsacks. – 1978. – № 24. – P. 525-530.
9. Shamir A. A polynomial-time algorithm for breaking the basic Merkle - Hellman cryptosystem // Information Theory, IEEE Transactions. – 1984. – Vol. 30, № 5. – P. 699-704.
10. Lenstra, Jr. H.W. Integer Programming with a Fixed Number of Variables // Mathematics of Operations Research. – 1983. – Vol. 8, № 4. – P. 538-548.
11. Vaudenay S. Cryptanalysis of the Chor-Rivest cryptosystem // CRYPTO. – 1998. – P. 243-256.
12. Izu T., Kogure J., Koshiba T., and Shimoyama T. Low-density attack revisited // Design, Codes and Cryptography. – 2007. – Vol. 43, № 1. – P. 47-59.
13. Осипян В.О., Спирина С.Г., Арутюнян А.С., Подколзин В.В. Труды VII Международной конференции "Алгебра и теория чисел: современные проблемы и приложения",
посвященной памяти профессора А.А. Карацубы // Моделирование ранцевых криптосистем, содержащих диофантову трудность. – 2010. – Т. 11. – С. 209-216.
14. Odlyzhko A.O. Cryptanalytic attacks on the multiplicative knapsack cryptosystem and on Shamir's fast signature scheme // IEEE Transactions on Information Theory. – Jul 1984. – Vol. IT-30, № 4. – P. 594-601.

Comments are closed.