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

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

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

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

Построение алгоритмов выработки имитовставок на основе обобщённых клеточных автоматов

# 11, ноябрь 2016
DOI: 10.7463/1116.0849590
Файл статьи: SE-BMSTU...o152.pdf (333.25Кб)
автор: доцент, к.т.н. Ключарёв П. Г.1,*

УДК 519.713+004.056.55

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

Важным классом криптографических алгоритмов являются алгоритмы выработки имитовставок (англ. Message Authentication Code). Такие алгоритмы предназначены для обеспечения целостности сообщений и аутентификации их источника
Основной задачей статьи является разработка метода синтеза алгоритмов выработки имитовставок, основанных на обобщенных клеточных автоматах.
Предлагаемый в статье метод построения алгоритмов выработки имитовставок состоит в использовании следующей схемы. Пусть вычисляется имитовставка от сообщения на некотором ключе. Работа алгоритма состоит из двух этапов: этапа абсорбции и этапа вычисления результата.
На этапе абсорбции используется обобщенный клеточный автомат, к внутреннему состоянию которого раз в несколько шагов подмешивается очередной блок сообщения. Для обеспечения зависимости выхода от всех разрядов ключа используется задающая последовательность, вырабатываемая линейным регистром сдвига с обратной связью. Начальное заполнение клеточного автомата и начальное заполнение регистра сдвига основаны на ключе. После того, как все сообщение будет обработано клеточным автоматом, этап абсорбирования завершается. Далее начинается этап вычисления результата, на котором клеточный автомат продолжает работать, при этом раз в определенное число шагов с некоторых разрядов его внутреннего состояния снимается необходимое количество разрядов имитовставки. После того, как будет получен необходимое количество разрядов, работа алгоритма завершается.
В качестве графа клеточного автомата используются графы Рамануджана, а именно графы Любоцкого-Филипса-Сарнака. Локальная функция связи выбирается специальным образом.
В статье приводятся требования к локальной функции связи, уделяется внимание вопросам конструкции графа клеточного автомата и вопросам криптостойкости.
Было проведено статистическое тестирование алгоритмов при различных наборах параметров с помощью комплекса статистических тестов NIST Statistical Test Suite. Все тесты были успешно пройдены.
Таким образом, в статье разработан новый метод построения алгоритмов выработки имитовставок, основанных на обобщённых клеточных автоматах.
Работа выполнена при финансовой поддержке РФФИ в рамках научного проекта № 16-07-00542  а.

Список литературы
  1. Bellare M., Canetti R., Krawczyk H., Bellare M., Canetti R., Krawczyk H. Advances in Cryptology - CRYPTO '96, 16th Annual International Cryptology Conference, Santa Barbara, California, USA, August 18-22, 1996, Proceedings. Springer. 1996. P. 1–15. DOI: 10.1007/3-540-68697-5_1, дата обращения 11.11.2016.
  2. Ключарёв П. Г. NP-трудность задачи о восстановлении предыдущего состояния обобщенного клеточного автомата // Наука и образование. Электронное научно-техническое издание. 2012. № 1. Режим доступа: http://technomag.neicon.ru/file/505104.html, дата обращения 11.11.2016.
  3. Ключарёв П. Г. О периоде обобщённых клеточных автоматов // Наука и образование. Электронное научно-техническое издание. 2012. № 2. Режим доступа: http://technomag.neicon.ru/doc/340943.html, дата обращения 11.11.2016.
  4. Ключарёв П. Г. Обеспечение криптографических свойств обобщённых клеточных автоматов // Наука и образование. Электронное научно-техническое издание. 2012. № 3. Режим доступа: http://technomag.neicon.ru/doc/358973.html, дата обращения 11.11.2016.
  5. Ключарёв П. Г. Клеточные автоматы, основанные на графах Рамануджана, в задачах генерации псевдослучайных последовательностей // Наука и образование. Электронное научно-техническое издание. 2011. № 10. Режим доступа: http://technomag.neicon.ru/file/504895.html, дата обращения 11.11.2016.
  6. Ключарёв П. Г. Построение псевдослучайных функций на основе обобщённых клеточных автоматов // Наука и образование. Электронное научно-техническое издание. 2012. № 10. Режим доступа: DOI: 10.7463/1112.0496381, дата обращения 11.11.2016.
  7. Davidoff G., Sarnak P., Valette A. Elementary number theory, group theory and Ramanujan graphs. Cambridge University Press, 2003. Vol. 55.
  8. Hoory S., Linial N., Wigderson A. Expander graphs and their applications. Bulletin of the American Mathematical Society. 2006. Vol. 43, No. 4. P. 439–562.
  9. Lubotzky A., Phillips R., Sarnak P. Ramanujan graphs. Combinatorica. 1988. Vol. 8, No. 3. P. 261–277.
  10. Lubotzky A., Phillips R., Sarnak P. Explicit expanders and the ramanujan conjectures. Proceedings of the eighteenth annual ACM symposium on Theory of computing. ACM. 1986. P. 240–246.
  11. Sarnak P. Some applications of modular forms. Cambridge University Press, 1990. Vol. 99.
  12. Ключарёв П. Г. Об устойчивости обобщенных клеточных автоматов к некоторым типам коллизий // Наука и образование. Электронное научно-техническое издание. 2014. № 9. С. 194–202. Режим доступа: DOI: 10.7463/0914.0727086, дата обращения 11.11.2016.
  13. Основы криптографии / А. П. Алферов, А. Ю. Зубов, A. C. Кузьмин, А. В. Черемушкин. М.: Гелиос, 2001.
  14. Bassham III L.E., Rukhin A. L., Soto J., Nechvatal J. R., Smid M. E., Barker E. B., Leigh S. D., Levenson M., Vangel M., Banks D. L., Heckert N. A., Dray J. F., Vo S. A Statistical Test Suite for Random and Pseudorandom Number Generators for Cryptographic Applications. National Institute of Standards & Technology Gaithersburg, MD, 2001
  15. Soto J. Statistical testing of random number generators. Proceedings of the 22nd National Information Systems Security Conference. National Institute of Standards & Technology Gaithersburg, MD. Vol. 10. 1999. P. 12.
  16. Zivkovic M. A table of primitive binary polynomials. Mathematics of Computation. 1994. Vol. 62, No. 205. P. 385–386.
  17. Ключарёв П. Г. Блочные шифры, основанные на обобщённых клеточных автоматах // Наука и образование. Электронное научно-техническое издание. 2012. № 12. Режим доступа: DOI: 10.7463/0113.0517543, дата обращения 11.11.2016.
  18. Ключарёв П. Г. Криптографические хэш-функции, основанные на обобщённых клеточных автоматах // Наука и образование. Электронное научно-техническое издание. 2013. № 1. Режим доступа: DOI: 10.7463/0113.0534640.
Поделиться:
 
ПОИСК
 
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)