APPLICATION OF BACKPACK ALGORITHMS TO PREVENT UNAUTHORIZED EXCHANGE OF INFORMATION BETWEEN DIFFERENT LEVELS USERS IN THE HIERARCHICAL SYSTEM OF PROTECTION AGAINST UNAUTHORIZED ACCESS
Abstract
The problem of designing a secure system of protection against unauthorized access is considered. In particular, this article considers hierarchical data protection systems with cryptographic key distribution, namely, the problem of organizing access to file storages is considered. Although cryptographic key distribution can ensure the security of information from users who do not have access to it, the hierarchical access control system was not originally designed to solve the problem of protecting information from the dishonest actions of the user himself. Thus, the overall objective of the study is to prevent unauthorized exchange of information between users of different levels of a hierarchical system of protection against unauthorized access with cryptographic key distribution. To achieve the stated goal, the authors previously proposed to use the problems of Diophantine analysis, in particular the knapsack problem. Previously, the authors formulated the properties of the knapsack vector, applicable for improving the hierarchical system of protection against unauthorized access. In this article, the authors present the conditions for the injectivity of knapsack vectors. A comparative analysis of these conditions with the already established injectivity conditions is carried out. The analysis shows the need to formulate such conditions and the applicability of knapsack vectors that satisfy them for improving the hierarchical model of protection against unauthorized access. Based on the specified conditions, this article develops a recursive algorithm for constructing an injective multiplicative knapsack vector. The authors then analyze the possibility of its application for modeling a hierarchical mandatory model of information protection from unauthorized access. The analysis shows how already known algorithms for constructing knapsack vectors can be used as part of the developed algorithm. The authors also show where exactly in the developed system it is necessary to apply this algorithm to implement the properties required for hierarchical systems of protection against unauthorized access
References
1. Lerner V.D. Kriptograficheskoe raspredelenie klyuchey dlya zashchity informatsii v ierarkhicheskikh sistemakh [Cryptographic key distribution for information protection in hierarchical systems], Infor-matsionno-upravlyayushchie sistemy [Information and Control Systems], 2012, No. 5 (60),
pp. 37-43.
2. Chen M., Mao S., Zhang Y., Leung C.M. Big data. Related technologies, challenges, and future pro-spects. Springer, 2014, 100 p.
3. Akl S.G., Taylor P.D. Cryptographic solution to a problem of access control in hierarchy, ACM Transac-tions on computer systems, 1983, No. 1 (3), pp. 239-248.
4. Lerner V.D., Bezzateev S.V. Osnovnye printsipy raspredeleniya klyuchey dlya dostupa k informatsii v oblachnykh khranilishchakh dannykh [Basic principles of key distribution for access to information in cloud data storage], Informatsionnaya bezopasnost' regionov Rossii (IBRR-2011): VII Sankt-Peterburgskaya mezhregion. konf., Sankt-Peterburg, 26-28 oktyabrya 2011 g.: Mater. konf. [Infor-mation security of Russian regions (ISRR-2011): VII St. Petersburg interregional conference, St. Pe-tersburg, October 26-28, 2011: Conference materials]. SPOISU. Saint Petersburg, 2011, pp. 120.
5. Zhuk A.S., Golovskoy V.A. Sintez ierarkhicheskoy sistemy zashchity informatsii ot nesanktsionirovan-nogo dostupa na osnovanii modeli Bella-LaPaduly [Synthesis of a hierarchical information protection system against unauthorized access based on the Bell-LaPadula model], Tr. Severo-Kavkazskogo filiala Moskovskogo tekhnicheskogo universiteta svyazi i informatiki [Proceedings of the North Caucasus Branch of the Moscow Technical University of Communications and Informatics]. Part II. Rostov-on-Don: PTS «Universitet» SKF MTUSI, 2017, pp. 90-97.
6. Shcheglov A.Yu. Modeli, metody i sredstva kontrolya dostupa k resursam vychislitel'nykh system [Mod-els, methods and means of access control to resources of computing systems]. Saint Petersburg: Univer-sitet ITMO, 2014, 95 p.
7. Bell D.E. Looking Back at the Bell-LaPadula Model, 21st Annual Computer Security Applications Con-ference. Tucson, Arizona, USA, 2005, pp. 337-351.
8. Usov S.V. O svyazi mezhdu ob"ektno-orientirovannoy diskretsionnoy i sub"ektno-ob"ektnoy mandatnoy modelyami bezopasnosti [On the relationship between object-oriented discretionary and subject-object mandatory security models], Matematicheskie struktury i modelirovanie [Mathematical structures and modeling], 2016, No. 4 (40), pp. 151-163.
9. Zhuk A.S., Osipyan V.O. Usloviya in"ektivnosti mul'tiplikativnogo obobshchennogo ryukzachnogo vektora [Injectivity conditions of the multiplicative generalized backpack vector], Spetsial'naya svyaz' i bezopasnost' informatsii (SSBI-2016): Sb. trudov. Mezhdunarodnaya NPK [Special Communications and Information Security (SSBI-2016): Collection of Works. International Scientific and Practical Con-ference]. Krasnodar: Krasnodarskiy tsentr nauchno-tekhnicheskoy informatsii (TSNTI), 2016, pp. 92-97.
10. Zhuk A.C., Golovskoy V.A. Issledovanie vozmozhnosti primeneniya obobshchennykh in"ektivnykh ryukzachnykh vektorov dlya modelirovaniya sistemy zashchity informatsii ot NSD [Study of the possi-bility of using generalized injective backpack vectors for modeling an information security system against unauthorized access], Tr. Severo-Kavkazskogo filiala Moskovskogo tekhnicheskogo universiteta svyazi i informatiki [Proceedings of the North Caucasian branch of the Moscow Technical University of Communications and Informatics], 2018, No. 2, pp. 110-115. EDN WALPYX.
11. Martello S.T.P. Knapsack problems: algorithms and computer implementations. Chichester: JOHN WILEY & SONS, 1990, pp. 137-138.
12. Shamir A. A polynomial-time algorithm for breaking the basic Merkle - Hellman cryptosystem, Infor-mation Theory, IEEE Transactions, 1984, Vol. 30, No. 5, pp. 699-704.
13. 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, No. 4, pp. 594-601.
14. Osipyan V.O. Modelirovanie sistem zashchity informatsii soderzhashchikh diofantovy trudnosti. Raz-rabotka metodov resheniy mnogostepennykh sistem diofantovykh uravneniy. Razrabotka ne-standartnykh ryukzachnykh kriptosistem: monografiya. LAP, 2012, 344 p.
15. Osipyan V.O. O sisteme zashchity informatsii na osnove problemy ryukzaka [On the information securi-ty system based on the backpack problem], Izvestiya TPU [Bulletin of the Tomsk Polytechnic Universi-ty], 2006, No. 2. Available at: https://cyberleninka.ru/article/n/o-sisteme-zaschity-informatsii-na-osnove-problemy-ryukzaka (accessed 28 January 2019).
16. Osipyan V.O., Leĭman A.V., Chesebiev A.A., Zhuk A.S., Arutyunyan A.Kh., Karpenko Yu.A. Matematich-eskoe modelirovanie nestandartnykh mul'tiplikativnykh rantsevykh kriptosistem [Mathematical modeling of non-standard multiplicative knapsack cryptosystems], Ekologicheskiy vestnik nauchnykh tsentrov Chernomorskogo ekonomicheskogo sotrudnichestva [Ecological Bulletin of Scientific Centers of the Black Sea Economic Cooperation], 2017, No. 2, pp. 57-64.
17. Osipyan V.O. Buiding of alphabetic data protection cryptosystems on the base of equal power knapsacks with Diophantine problems, ACM, 2012, pp. 124-129.
18. Zhivotova A.E., Zyulyarkina N.D., Kostygina Yu.O. Modifikatsiya kriptosistemy s otkrytym klyuchom na osnove «zadachi o ryukzake [Modification of a public-key cryptosystem based on the “knapsack problem”], Vestnik UrFO. Bezopasnost' v informatsionnoy sfere [Bulletin of the Ural Federal District. Information Security], 2014, No. 1 (11), pp. 16-20.
19. Shevlyakov T.N. Mul'tiplikativnaya ryukzachnaya kriptosistema [Multiplicative backpack cryptosystem], Vestnik OmGU [Bulletin of Omsk State University], 2011, No. 4. Available at: https://cyberleninka.ru/article/n/multiplikativnaya-ryukzachnaya-kriptosistema (accessed 28 January 2019).
20. Osipyan V.O., Zhuk A.S., Lukashchik E.P. [et al.]. Multiplicative knapsack injectivity as condition of effective unauthorized access protection, Journal of Physics: Conference Series, 2021, Vol. 2131,
No. 2, pp. 022084. DOI: 10.1088/1742-6596/2131/2/022084.
21. Zhuk A.S., Golovskoy V.A. Analiz vychislitel'noy slozhnosti resheniya zadachi o mul'tiplikativnom ryukzake [Analysis of the computational complexity of solving the multiplicative knapsack problem]. Vol. 78, Tr. Severo-Kavkazskogo filiala Moskovskogo tekhnicheskogo universiteta svyazi i informatiki [Proceedings of the North Caucasus Branch of Moscow Technical University of Communications and Informatics]. Part II. Rostov-on-Don: PTS «Universitet» SKF MTUSI, 2017, 441 p., pp. 81-90.
22. Zhuk A.S., Kislenko I.A. Razrabotka matematicheskikh modeley usloviy snizheniya vychislitel'noy slozhnosti algoritmov resheniya zadachi ob obobshchennom mul'tiplikativnom ryukzake [Development of mathematical models of conditions for reducing the computational complexity of algorithms for solv-ing the generalized multiplicative knapsack problem], Sb. statey XVIII voenno-nauchnoy konferentsii kursantov i operatorov nauchnoy roty Krasnodarskogo vysshego voennogo uchilishcha imeni generala armii S.M. Shtemenko [Collection of articles of the XVIII military-scientific conference of cadets and operators of the scientific company of the Krasnodar Higher Military School named after General of the Army S.M. Shtemenko]. Krasnodar: KVVU, 2016, pp. 86-96.
23. Osipyan V.O., Zhuk A.S., Arutyunyan A.Kh., Karpenko Yu.A. Postroenie kriptosistem s otkrytym klyu-chom na osnove zadach o nestandartnom ryukzake [Construction of public-key cryptosystems based on non-standard knapsack problems], MMiITS: Tr. V Vseros. n/p konf.24 iyunya 2011, KU MVD Rossii [MMiITS: Proceedings of the V All-Russian scientific conference. June 24, 2011, KU MVD of Russia], pp. 12-15.
24. Podkolzin V.V., Osipyan V.O. O svoystvakh ryukzachnykh sistem zashchity informatsii s otkrytym klyuchom v Zp [On the properties of backpack information security systems with an open key in Zp], Vestnik SibGU im. M.F. Reshetneva [Bulletin of the Siberian State University named after
M.F. Reshetnev], 2010, No. 3, pp. 51-55.
25. Osipyan V.O., Mirzayan A.V. Sravnitel'nyy analiz kriptostoykosti klassicheskoy i obobshchennoy ryukzachnoy kriptosistem [Comparative analysis of cryptographic resistance of classical and generalized backpack cryptosystems], Matematicheskie metody i informatsionno-tekhnicheskie sredstva: Tr. Vseros. nauch.-praktich. konf. Krasnodar, 24 iyunya 2005 [Mathematical methods and information technology tools: Proceedings of the All-Russian scientific and practical conference. Krasnodar, June 24, 2005], pp. 34-36.
