Алгоритмические аспекты создания и использования ключевых пространств беспроводных сенсорных сетей на основе комбинаторных блок-схем
Аннотация
На основе анализа особенностей управления ключами в беспроводных сенсорных сетях (БСС) сформулирован ряд отвечающих определенным требованиям к ключевым пространствам БСС положений алгоритмического подхода к их созданию и использованию в предположении, что их структура соответствует одной из разновидностей комбинаторных блок-схем — циклической или ациклической проективной плоскости, линейной или квадратичной трансверсальной блок-схеме. Распределенный характер БСС позволяет избежать построения комбинаторной блок-схемы в полном объеме и вычислять необходимые блоки по мере необходимости при масштабировании сети (добавлении новых узлов) или нецентрализованном определении параметров коммутации конкретных узлов. Для этого необходимы алгоритмы вычисления блоков комбинаторной блок-схемы (как множеств номеров ключей, распределяемых данному узлу) и дуальных блоков (как множеств номеров узлов, которым распределены ключи с номерами, совпадающими с номерами дуальных блоков), а также алгоритмы решения производных задач: вычисления номеров общих ключей двух узлов и номера узла, имеющего общий ключ с одним из двух узлов и, возможно, другой ключ с другим узлом. Указанные задачи решены на основе использования нумерации элементов, блоков и дуальных блоков в соответствии с предложенным правилом двойственности: множества элементов и дуальных блоков находятся во взаимно-однозначном соответствии по нумерации, дуальный блок с заданным номером содержит номера блоков, содержащих элементы с его же номером. Распределенное (независимое) вычисление блоков осуществляется на основе алгебраических идентификаторов, вычисляемых по номерам блоков. Помимо возможного отсутствия физической связи между узлами учтены недопустимость использования отдельных (скомпрометированных) ключей, а также возможная неполнота комплектования узлов сети ключами, как и неполнота реализации системы в целом. Приведены алгоритмы вычисления параметров коммутации двух узлов при проектировании БСС и алгоритм компьютерного моделирования вычисления таких параметров при функционировании БСС при указанных ограничениях и использовании любого из перечисленных выше типов комбинаторных блок-схем.
Литература
2. Mitchell C.J. Combinatorial Techniques for Key Storage Reduction in Secure Networks // Technical Memo. Bristol: Hewlett-Packard Laboratories, 1988.
3. Dyer M., Fenner T., Frieze A., Thomason A. On Key Storage in Secure Networks // J. Cryptology. 1995. V. 8(4). Pp. 189—200.
4. Erdösh P., Frankl P., Füredi Z. Families of Finite Sets in Which no Set is Covered by the Union of Two Others // J. Combinatorial Theory. 1982. V. A33. Pp. 158—166.
5. Erdösh P., Frankl P., Füredi Z. Families of Finite Sets in Which no Set is Covered by the Union of r Others // Israel J. Math. 1985. V. 51. Pp. 75—89.
6. Lee J., Stinson D.R. On the Construction of Practical Key Predistribution Schemes for Distributed Sensor Networks Using Combinatorial Designs // ACM Trans. Information and Syst. Security. 2008. V. 11. No. 2. Pp. 1—35.
7. Stinson D.R., Van Trung T. Some New Results on Key Distribution Patterns and Broadcast Encryption // Designs, Codes and Cryptography. 1998. V. 14. Pp. 261—279
8. Stinson D.R., Van Trung T., Wei R. Secure Frameproof Codes, Key Distribution Patterns, Group Testing Algorithms and Related Structures // J. Statist. Plan. Infer. 2000. V. 86. No. 2. Pp. 595—617
9. Stinson D.R., Wei R., Zhu L. New Constructions for Perfect Hash Families and Related Structures Using Combinatorial Designs and Codes // J. Combinatorial Designs. 2000. V. 8. No. 3. Pp. 189—200.
10. Camtepe S., Yener B. Combinatorial Design of Key Distribution Mechanisms for Wireless Sensor Networks // Lecture Notes in Computer Sci. 2004. V. 3193. Pp. 293—308.
11. Lee J., Stinson D.R. Deterministic Key Predistribution Schemes for Distributed Sensor Networks // Lecture Notes in Computer Sci. 2005. V. 3357. Pp. 294—307.
12. Paterson M.B., Stinson D.R. A Unified Approach to Combinatorial Key Predistribution Schemes for Sensor Networks // Designs Codes and Cryptography.·2014. V. 71. Pp. 433—457.
13. Chan H., Perrig A., Song D. Random Key Predistribution Schemes for Sensor Networks // Proc. Symp. Security and Privacy. 2003. Pp. 197—213.
14. Eschenauer L., Gligor V. A Key-management Scheme for Distributed Sensor Networks // Proc. IX ACM Conf. Computer and Communications Security. ACM Press, 2002. Pp. 41—47.
15. Холл М. Комбинаторика. М: Мир, 1970.
16. Stinson D. Combinatorial Designs: Constructions and Analysis. Berlin: Springer, 2003.
17. Фролов А.Б., Клягин А О., Кочетова Н.П. Темников Д.Ю. Распределенное вычисление комбинаторных блок-схем // Проблемы теоретической кибернетики: Материалы заочного семинара XIX Междунар. конф. Казань, 2020. С. 126—129.
18. Gashkov S.B. Frolov A.B. The Complexity of Solving Low Degree Equations over Ring of Integers and Residue Rings // Moscow University Mathematics Bull. 2019. V. 74. No. 1. Pp. 5—13.
19. Гашков С.Б., Гашков И.Б. Быстрый алгоритм извлечения квадратных корней в некоторых конечных полях нечетной характеристики // Вестник Московского университета. Серия 1: «Математика. Механика». 2018. Т. 73(5). C. 8—14.
20. Волокитин М.В. Алгебраические возможности пакета Mathematica и их расширение // Вестник МЭИ. 2010. № 2. С. 114—120.
21. Гашков С.Б., Фролов А.Б., Попова Е.П. Об оценках сложности алгоритмов извлечения квадратных корней в конечных полях и в кольцах вычетов // Вестник МЭИ. 2018. № 5. С. 79—88.
22. Sage Web Site [Офиц. сайт] www.sagemath.org (дата обращения 25.09.2020).
23. Frolov A.B., Vinnikov A.M. Modeling Cryptographic Protocols Using Computer Algebra Systems // Proc. V Intern. Conf. Information Technol. Engineering Education. Moscow, 2020. Pp. 1—4.
---
Для цитирования: Фролов А.Б., Кочетова Н.П., Клягин А.О., Темников Д.Ю. Алгоритмические аспекты создания и использования ключевых пространств беспроводных сенсорных сетей на основе комбинаторных блок-схем // Вестник МЭИ. 2021. № 2. С. 108—118. DOI: 10.24160/1993-6982-2021-2-108-118.
---
Работа выполнена при поддержке: РФФИ (проект № 19-01-00294а)
#
1. Mitchell C.J., Piper C. Key Storage in Secure Networks. Discrete and Appl. Math. 1988;21:215—228.
2. Mitchell C.J. Combinatorial Techniques for Key Storage Reduction in Secure Networks. Technical Memo. Bristol: Hewlett-Packard Laboratories, 1988.
3. Dyer M., Fenner T., Frieze A., Thomason A. On Key Storage in Secure Networks. J. Cryptology. 1995;8(4):189—200.
4. Erdösh P., Frankl P., Füredi Z. Families of Finite Sets in Which no Set is Covered by the Union of Two Others. J. Combinatorial Theory. 1982;A33:158—166.
5. Erdösh P., Frankl P., Füredi Z. Families of Finite Sets in Which no Set is Covered by the Union of r Others. Israel J. Math. 1985;51:75—89.
6. Lee J., Stinson D.R. On the Construction of Practical Key Predistribution Schemes for Distributed Sensor Networks Using Combinatorial Designs. ACM Trans. Information and Syst. Security. 2008;11;2:1—35.
7. Stinson D.R., Van Trung T. Some New Results on Key Distribution Patterns and Broadcast Encryption. Designs, Codes and Cryptography. 1998;14:261—279
8. Stinson D.R., Van Trung T., Wei R. Secure Frameproof Codes, Key Distribution Patterns, Group Testing Algorithms and Related Structures. J. Statist. Plan. Infer. 2000;86;2:595—617
9. Stinson D.R., Wei R., Zhu L. New Constructions for Perfect Hash Families and Related Structures Using Combinatorial Designs and Codes. J. Combinatorial Designs. 2000;8;3:189—200.
10. Camtepe S., Yener B. Combinatorial Design of Key Distribution Mechanisms for Wireless Sensor Networks. Lecture Notes in Computer Sci. 2004;3193:293—308.
11. Lee J., Stinson D.R. Deterministic Key Predistribution Schemes for Distributed Sensor Networks. Lecture Notes in Computer Sci. 2005;3357:294—307.
12. Paterson M.B., Stinson D.R. A Unified Approach to Combinatorial Key Predistribution Schemes for Sensor Networks. Designs Codes and Cryptography.·2014;71:433—457.
13. Chan H., Perrig A., Song D. Random Key Predistribution Schemes for Sensor Networks. Proc. Symp. Security and Privacy. 2003:197—213.
14. Eschenauer L., Gligor V. A Key-management Scheme for Distributed Sensor Networks. Proc. IX ACM Conf. Computer and Communications Security. ACM Press, 2002:41—47.
15. Kholl M. Kombinatorika. M: Mir, 1970. (in Russian).
16. Stinson D. Combinatorial Designs: Constructions and Analysis. Berlin: Springer, 2003.
17. Frolov A.B., Klyagin A O., Kochetova N.P. Temnikov D.Yu. Raspredelennoe Vychislenie Kombinatornykh Blok-skhem. Problemy Teoreticheskoy Kibernetiki: Materialy Zaochnogo Seminara XIX Mezhdunar. Konf. Kazan', 2020:126—129. (in Russian).
18. Gashkov S.B. Frolov A.B. The Complexity of Solving Low Degree Equations over Ring of Integers and Residue Rings. Moscow University Mathematics Bull. 2019;74;1:5—13.
19. Gashkov S.B., Gashkov I.B. Bystryy Algoritm Izvlecheniya Kvadratnykh Korney v Nekotorykh Konechnykh Polyakh Nechetnoy Kharakteristiki. Vestnik Moskovskogo Universiteta. Seriya 1: «Matematika. Mekhanika». 2018;73(5):8—14. (in Russian).
20. Volokitin M.V. Algebraicheskie Vozmozhnosti Paketa Mathematica i Ikh Rasshirenie. Vestnik MEI. 2010;2:114—120. (in Russian).
21. Gashkov S.B., Frolov A.B., Popova E.P. Ob Otsenkakh Slozhnosti Algoritmov Izvlecheniya Kvadratnykh Korney v Konechnykh Polyakh i v Kol'tsakh Vychetov. Vestnik MEI. 2018;5:79—88. (in Russian).
22. Sage Web Site [Ofits. Sayt] www.sagemath.org (Data Obrashcheniya 25.09.2020).
23. Frolov A.B., Vinnikov A.M. Modeling Cryptographic Protocols Using Computer Algebra Systems. Proc. V Intern. Conf. Information Technol. Engineering Education. Moscow, 2020:1—4.
---
For citation: Frolov A.B., Kochetova N.P., Klyagin A.O., Temnikov D.Yu. The Algorithmic Aspects of Creating and Using Wireless Sensor Network Key Spaces Based on Combinatorial Block Diagrams. Bulletin of MPEI. 2021;2:108—118. (in Russian). DOI: 10.24160/1993-6982-2021-2-108-118.
---
The work is executed at support: RFBR (Project No. 19-01-00294а)
