Другие журналы

научное издание МГТУ им. Н.Э. Баумана

НАУКА и ОБРАЗОВАНИЕ

Издатель ФГБОУ ВПО "МГТУ им. Н.Э. Баумана". Эл № ФС 77 - 48211.  ISSN 1994-0408

Исследование характеристик лавинного эффекта обобщенных клеточных автоматов на основе графов малого диаметра

# 04, апрель 2016
DOI: 10.7463/0416.0837506
Файл статьи: SE-BMSTU...o105.pdf (1308.97Кб)
авторы: Балк Е. А.1, доцент, к.т.н. Ключарёв П. Г.1,*

УДК 519.713+004.056.55

1 МГТУ им. Н.Э. Баумана, Москва, Россия


Данная статья является продолжением цикла статей, посвященных исследованию обобщенных клеточных автоматов и их криптографических свойств. Основное внимание уделено рассмотрению применимости обобщенных клеточных автоматов в качестве базовых криптографических примитивов в соответствии с требованиями, предъявлемыми к алгоритмам так называемой легковесной криптографии (lightweight cryptography). Одним из основных требований является минимизация затрачиваемых аппаратных ресурсов. В соответствии с ним, в случае использования для аппаратной реализации алгортма программируемых логических интегральных схем (ПЛИС), было предложено рассматривать только обобщенные клеточные автоматы на основе регулярных графов степени k=4 и k=6, т.к. они имеют эффективные аппаратные реализации на получивших наиболее широкое распространение ПЛИС с 4- и 6-входовой таблицей поиска. В связи с тем, что хорошими характеристиками лавинного эффекта обладают обобщенные клеточные автоматы на основе регулярных графов малого диаметра и граница Мура накладывает ограничение на максимальный порядок графа при заданном значении степени графа и диаметра, для построения обобщенных клеточных автоматов использовались графы с диаметром D=3 и D=4.Полученные в ходе исследования результаты для клеточных автоматов на основе графов максимального порядка с диаметром D=3 и D=4 и степенью вершин k=4 в целом соответствуют предыдущим результатам для обобщенных  автоматов с окрестностью 4. Они характеризуются достаточно большим, относительно диаметра их графа, значением количества тактов от начала работы автомата до достижения им максимальных значений характеристик интегрального лавинного эффекта.Выбранные клеточные автоматы на основе графов с диаметром D=3 и D=4 и степенью вершин k=6 по результатам исследования показали хорошие значения характеристик лавинного эффекта и обладают хорошими рассеивающими свойствами.Таким образом, все рассмотренные обобщенные клеточные автоматы обладают хорошими характеристиками лавинного эффекта и могут быть использованы в качестве базовых криптографических примитивов. Перспективным направлением изучения является создание неоднородных клеточных автоматов, у которых локальные функции связи различны для всех ячеек.


Список литературы
  1. Быков А.Ю., Панфилов Ф.А., Ховрина А.В. Алгоритм выбора классов защищенности для объектов распределенной информационной системы и размещения данных по объектам на основе приведения оптимизационной задачи к задаче теории игр с непротивоположными интересами // Наука и образование. МГТУ им. Н.Э. Баумана. Электрон. журн. 2016. № 1. C. 90-107. DOI:10.7463/0116.0830972
  2. Быков А.Ю., Шматова Е.С. Алгоритмы распределения ресурсов для защиты информации между объектами информационной системы на основе игровой модели и принципа равной защищенности объектов // Наука и образование. МГТУ им. Н.Э. Баумана. Электрон. журн. 2015. № 9. C. 160-187. DOI:10.7463/0915.0812283
  3. Ключарев П.Г. Клеточные автоматы, основанные на графах Рамануджана, в задачах генерации псевдослучайных последовательностей // Наука и образование. МГТУ им. Н.Э. Баумана. Электрон. журн. 2011. № 10. Режим доступа: http://technomag.bmstu.ru/file/504895.html?__s=1 (дата обращения 01.03.2016).
  4. Ключарев П.Г. Обеспечение криптографических свойств обобщенных клеточных автоматов // Наука и образование. МГТУ им. Н.Э. Баумана. Электрон. журн. 2012. № 3. Режим доступа: http://technomag.bmstu.ru/file/505222.html?__s=1 (дата обращения 01.03.2016).
  5. Ключарев П.Г. О вычислительной сложности некоторых задач на обобщенных клеточных автоматах // Безопасность информационных технологий. 2012. № 1. С. 30-32. Режим доступа: http://pvti.ru/data/file/bit/2012_1/part_4.pdf (дата обращения 01.03.2016).
  6. Ключарев П.Г. О периоде обобщённых клеточных автоматов // Наука и образование. МГТУ им. Н.Э. Баумана. Электрон. журн. 2012. № 02. Режим доступа: http://technomag.bmstu.ru/file/505165.html?__s=1 (дата обращения 01.03.2016).
  7. Ключарев П.Г. Криптографические хэш-функции, основанные на обобщённых клеточных автоматах // Наука и образование. МГТУ им. Н.Э. Баумана. Электрон. журн. 2013. № 01. С. 161-172. DOI: 10.7463/0113.0534640
  8. Ключарев П.Г. Производительность и эффективность аппаратной реализации поточных шифров, основанных на обобщенных клеточных автоматах // Наука и образование. МГТУ им. Н.Э. Баумана. Электрон. журн. 2013. № 10. С. 299-314. DOI:1013.0624722
  9. Ключарев П.Г. Реализация криптографических хэш-функций, основанных на обобщенных клеточных автоматах, на базе ПЛИС: производительность и эффективность // Наука и образование. МГТУ им. Н.Э. Баумана. Электрон. журн. 2014. № 01. С. 214-223. DOI:10.7463/0114.0675812
  10. Сухинин Б.М. Исследование характеристик лавинного эффекта в двоичных клеточных автоматах с равновесными функциями переходов // Наука и образование. МГТУ им. Н.Э. Баумана. Электрон. журн. 2010. № 08. Режим доступа: http://technomag.bmstu.ru/file/504603.html?__s=1 (дата обращения 01.03.2016).
  11. Сухинин Б.М. Разработка генераторов псевдослучайных двоичных последовательностей на основе клеточных автоматов // Наука и образование. МГТУ им. Н.Э. Баумана. Электрон. журн. 2010. № 9. Режим доступа: http://technomag.edu.ru/file/504604.html?__s=1 (дата обращения 01.03.2016).
  12. Comellas F., Delorme C. The (degree, diameter) problem for graphs // Государственный университет Каталонии : сайт . Режим доступа:http://www-ma4.upc.es/~comellas/delta-d/taula_delta_d.html (дата обращения 15.02.2016).
  13. Miller M., Širan J. Moore graphs and beyond: A survey of the degree / diameter problem // The Electronic Journal of Combinatorics. 2005. No . DS 14. Режим доступа: http://www.emis.ams.org/journals/EJC/Surveys/ds14.pdf (дата обращения 01.03.2016).
  14. Балк Е.А., Ключарев П.Г. Исследование характеристик лавинного эффекта неориентированных обобщенных клеточных автоматов малого размера // XI Международная научно-практическая конференция «Перспективы развития информационных технологий»: сб. матер. Новосибирск, 2013.
  15. Allwright J. New graphs discovered by heuristic search // Discrete Applied Mathematics. 1992. Vol. 37-38. P. 3-8. DOI : 10.1016/0166-218X(92)90120-Y
  16. Lin S., Kernighan B.W. An efficient heuristic procedure for partitioning graphs // The Bell System Technical Journal. 1970. Vol. 49, no. 2. P. 291-307. DOI: 10.1002/j.1538-7305.1970.tb01770.x
  17. Lin S., Kernighan B.W. An Effective Heuristic Algorithm for the Traveling-Salesman Problem // Operations Research. 1973. Vol. 21, no. 2. P. 498-516. DOI: 10.1287/opre.21.2.498
  18. Loz E., Širan J. New record graphs in the degree-diameter problem // Australasian Journal of Combinatorics. 2008. Vol . 41. P . 63-80. Режим доступа: http://ajc.maths.uq.edu.au/pdf/41/ajc_v41_p063.pdf (дата обращения 01.03.2016).
  19. D McKay B., Miller M., Širan J. A Note on Large Graphs of Diameter Two and Given Maximum Degree // Journal of Combinatorial Theory, Series B. 1998. Vol. 74, no. 1. P. 110-118. DOI: 10.1006/jctb.1998.1828
  20. Dinneen M.J., Hafner P.R. New results for degree/diameter problem // Networks. 1994. Vol. 24, no. 7. P. 359-367. DOI: 10.1002/net.3230240702
  21. Brankovic L., Miller M., Plesnik J., Ryan J., Širan J. Large graphs with small degree and diameter: A voltage assignment approach // Australasian Journal of Combinatorics. 1998. No . 18. P . 65-76. Режим доступа: http://ajc.maths.uq.edu.au/pdf/18/ajc-v18-p65.pdf (дата обращения 01.03.2016).

Поделиться:
 
ПОИСК
 
elibrary crossref ulrichsweb neicon rusycon
 
ЮБИЛЕИ
ФОТОРЕПОРТАЖИ
 
СОБЫТИЯ
 
НОВОСТНАЯ ЛЕНТА



Авторы
Пресс-релизы
Библиотека
Конференции
Выставки
О проекте
Rambler's Top100
Телефон: +7 (915) 336-07-65 (строго: среда; пятница c 11-00 до 17-00)
  RSS
© 2003-2017 «Наука и образование»
Перепечатка материалов журнала без согласования с редакцией запрещена
 Тел.: +7 (915) 336-07-65 (строго: среда; пятница c 11-00 до 17-00)