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

УДК 519.713; 004.056.55

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

pk.iu8@yandex.ru

В работе представлена методика построения псевдослучайных функций, основанная на использовании обобщённых клеточных автоматов. При этом, в качестве графов таких автоматов используется явная конструкция графов Рамануджана - графы Любоцкого-Филипса-Сарнака. Проведено эмпирическое исследование статистических свойств полученных псевдослучайных  функций, посредством применения набора статистических тестов NIST. Предложенная методика может быть использована для построения S-блоков, предназначенных для применения в составе блочных шифров, хеш-функций, а также других криптографических алгоритмов и протоколов.

Список литературы

1. ГОСТ 28147-89. Системы обработки информации. Защита криптографическая. Алгоритм криптографического преобразования. Введ. 1990-07-01. М.: Изд-во стандартов, 1996. 28 с.

2. Ключарёв П.Г. Клеточные автоматы, основанные на графах Рамануджана, в задачах генерации псевдослучайных последовательностей // Наука и образование. МГТУ им. Н.Э. Баумана. Электрон. журн. 2011. № 10. Режим доступа:   http://technomag.edu.ru/doc/241308.html (дата обращения 22.11.2012).

3. Ключарёв П.Г. О вычислительной сложности некоторых задач на обобщенных клеточных автоматах // Безопасность информационных технологий. 2012. № 1. Режим доступа:   http://www.pvti.ru/data/file/bit/2012_1/part_4.pdf (дата обращения 22.11.2012).

4. Ключарёв П.Г. О периоде обобщённых клеточных автоматов // Наука и образование. МГТУ им. Н.Э. Баумана. Электрон. журн. 2012. № 2. Режим доступа:   http://technomag.edu.ru/doc/340943.html (дата обращения 22.11.2012).

5. Ключарёв П.Г. Обеспечение криптографических свойств обобщённых клеточных автоматов // Наука и образование. МГТУ им. Н.Э. Баумана. Электрон. журн. 2012. № 3. Режим доступа:  http://technomag.edu.ru/doc/358973.html  (дата обращения 22.11.2012).

6. Ключарёв П.Г. NP-трудность задачи о восстановлении предыдущего состояния обобщенного клеточного автомата // Наука и образование. МГТУ им. Н.Э. Баумана. Электрон. журн. 2012. № 1. Режим доступа:   http://technomag.edu.ru/doc/312834.html (дата обращения 22.11.2012).

7. Сухинин Б.М. Высокоскоростные генераторы псевдослучайных последовательностей на основе клеточных автоматов // Прикладная дискретная математика. 2010. № 2. С. 34-41.

8. Сухинин Б.М. О некоторых свойствах клеточных автоматов и их применении в структуре генераторов псевдослучайных последовательностей // Вестник МГТУ им. Н.Э. Баумана. Сер. Приборостроение. 2011. № 2. С. 68-76.

9. ChungF. Spectralgraphtheory. American Mathematical Society, 1997. (CBMS Regional Conference Series in Mathematics, No.  92).

10. Cusick T., Stanica P. Cryptographic Boolean functions and applications. Academic Press, 2009. 232 p.

11. Daemen J., Rijmen V. The design of Rijndael: AES-the advanced encryption standard. Springer, 2002.

12. Davidoff G., Sarnak P., Valette A. Elementary number theory, group theory and Ramanujan graphs. Cambridge University Press, 2003. 144 p. (London Mathematical Society Student Texts, vol. 55.).

13. Federal Information Processing Standard (FIPS) Pub. 197. Advanced Encryption Standard (AES). Department of Commerce, National Institute of Standards and Technology, Information Technology Laboratory (ITL). 2001. 47 p. Available at:   http://csrc.nist.gov/publications/fips/fips197/fips-197.pdf  , accessed 22.11.2012.

14. 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.

15. Knudsen L., Robshaw M. The block cipher companion. Springer, 2011.

16. Lubotzky A., Phillips R., Sarnak P. Explicit expanders and the ramanujan conjectures // STOC '86 Proceedings of the eighteenth annual ACM symposium on Theory of computing. New York, NY: ACM, 1986. P. 240–246. DOI: 10.1145/12130.12154

17. Lubotzky A., Phillips R., Sarnak P. Ramanujan graphs // Combinatorica. 1988. Vol. 8, no. 3. P. 261-277.

18. Luby M., Rackoff C. How to construct pseudorandom permutations from pseudorandom functions // SIAM Journal on Computing. 1988. Vol. 17, no. 2. P. 373-386.