informИнформатикаInformatics1816-03012617-6963UIIP NASBinform-107Research ArticleЗАЩИТА ИНФОРМАЦИИ И НАДЕЖНОСТЬ СИСТЕМINFORMATION PROTECTION AND SYSTEM RELIABILITYО ТЕСТИРОВАНИИ ВЫХОДНЫХ ПОСЛЕДОВАТЕЛЬНОСТЕЙ КРИПТОГРАФИЧЕСКИХ ГЕНЕРАТОРОВ НА ОСНОВЕ ЦЕПЕЙ МАРКОВА УСЛОВНОГО ПОРЯДКАON TESTING OF CRYPTOGRAPHYC GENERATORS OUTPUT SEQUENCES USING MARKOV CHAINS OF CONDITIONAL ORDERМальцевМ. В.MaltsevM. V.maltsew@mail.ruХаринЮ. С,.KharinYu. S.kharin@bsu.byНИИ прикладных проблем математики и информатики БГУRussian Federation20130110201604104111Copyright © Мальцев М.В., Харин Ю.С., 20162016Мальцев М.В., Харин Ю.С.Maltsev M.V., Kharin Y.S.Данная работа распространяется под лицензией Creative Commons Attribution 4.0.This work is licensed under a Creative Commons Attribution 4.0 License.https://inf.grid.by/jour/article/view/107

Рассматривается цепь Маркова условного порядка, используемая для статистического тес-тирования криптографических генераторов. Приводятся статистические оценки параметров, доказывается состоятельность оценки порядка цепи Маркова. Показываются результаты компьютерных экспериментов для модельных и реальных данных.

The paper deals with the Markov chain of conditional order, which is used for statisticaltesting of cryptographic generators. Statistical estimations of model parameters are given. Consistency of the order estimator is proved. Results of computer experiments are presented.

ReferencesМатематические и компьютерные основы криптологии / Ю.С. Харин [и. др.]. – Минск : Новое знание, 2003. – 382 c.Математические и компьютерные основы криптологии / Ю.С. Харин [и. др.]. – Минск : Новое знание, 2003. – 382 c.Максимов, Ю.И. О цепях Маркова, связанных с двоичными регистрами сдвига со случайными элементами / Ю.И. Максимов // Труды по дискретной математике. – 1997. – Т. 1. – С. 203–220.Максимов, Ю.И. О цепях Маркова, связанных с двоичными регистрами сдвига со случайными элементами / Ю.И. Максимов // Труды по дискретной математике. – 1997. – Т. 1. – С. 203–220.Sepehrdad, P. Discovery and Exploitation of New Biases in RC4 / P. Sepehrdad, S. Vaudenay, M. Vuagnoux // Lecture Notes in Computer Science. – 2011. – Vol. 6544. – P. 74–91.Sepehrdad, P. Discovery and Exploitation of New Biases in RC4 / P. Sepehrdad, S. Vaudenay, M. Vuagnoux // Lecture Notes in Computer Science. – 2011. – Vol. 6544. – P. 74–91.A statistical test suite for random and pseudorandom number generators for cryptographic applications / A. Rukhin [et al.] // National Institute of Standards and Technology [Electronic resource]. – USA, 2010. – Mode of access : http://csrc.nist.gov/groups/ST/toolkit/rng/documents/SP800-22rev1a.pdf. – Date of access : 17.04.2013.A statistical test suite for random and pseudorandom number generators for cryptographic applications / A. Rukhin [et al.] // National Institute of Standards and Technology [Electronic resource]. – USA, 2010. – Mode of access : http://csrc.nist.gov/groups/ST/toolkit/rng/documents/SP800-22rev1a.pdf. – Date of access : 17.04.2013.Marsaglia, G. The Marsaglia Random Number CDROM including the Diehard Battery of Tests of Randomness / G. Marsaglia [Electronic resource]. – Florida State University, 1995. – Mode of access : http://www.stat.fsu.edu/pub/diehard/. – Date of access : 01.06.2013.Marsaglia, G. The Marsaglia Random Number CDROM including the Diehard Battery of Tests of Randomness / G. Marsaglia [Electronic resource]. – Florida State University, 1995. – Mode of access : http://www.stat.fsu.edu/pub/diehard/. – Date of access : 01.06.2013.Кнут, Д.Э. Искусство программирования: в 3 т. Т. 1: Получисленные методы /Д. Э. Кнут. – М. : Вильямc, 2007. – 832 с.Кнут, Д.Э. Искусство программирования: в 3 т. Т. 1: Получисленные методы /Д. Э. Кнут. – М. : Вильямc, 2007. – 832 с.Doob, J.L. Stochastic processes / J.L. Doob. – N. Y. : Wiley, 1953. – 6Doob, J.L. Stochastic processes / J.L. Doob. – N. Y. : Wiley, 1953. – 6Харин, Ю.С. Цепь Маркова с частичными связями ЦМ(s, r) и статистические выводы о ее параметрах / Ю.С. Харин, А.И. Петлицкий // Дискретная математика. – 2007. – Т. 19, № 2. – C. 109–130.Харин, Ю.С. Цепь Маркова с частичными связями ЦМ(s, r) и статистические выводы о ее параметрах / Ю.С. Харин, А.И. Петлицкий // Дискретная математика. – 2007. – Т. 19, № 2. – C. 109–130.Raftery, A.E. A model for high-order Markov chains / A.E. Raftery // J. Royal Statistical Society. – 1985. – Vol. B-47, № 3. – P. 528–539.Raftery, A.E. A model for high-order Markov chains / A.E. Raftery // J. Royal Statistical Society. – 1985. – Vol. B-47, № 3. – P. 528–539.Харин, Ю.С. Статистическая проверка гипотез о параметрах цепи Маркова условного порядка / Ю.С. Харин, М.В. Мальцев // Весцi НАН Беларуси. Сер. фiз.-мат. навук. – 2012. – № 3. – С. 5–12.Харин, Ю.С. Статистическая проверка гипотез о параметрах цепи Маркова условного порядка / Ю.С. Харин, М.В. Мальцев // Весцi НАН Беларуси. Сер. фiз.-мат. навук. – 2012. – № 3. – С. 5–12.Мальцев, М.В. Об асимптотических свойствах статистических оценок параметров цепи Маркова условного порядка / М.В. Мальцев, Ю.С. Харин // Весцi НАН Беларуси. Сер. фiз.- мат. навук. – 2013. – №1. – С. 5–12.Мальцев, М.В. Об асимптотических свойствах статистических оценок параметров цепи Маркова условного порядка / М.В. Мальцев, Ю.С. Харин // Весцi НАН Беларуси. Сер. фiз.- мат. навук. – 2013. – №1. – С. 5–12.Csiszar, I. Consistency of the BIC order estimator / I. Csiszar, P. Shields // Electronic research announcments of the American mathematical society. – 1999. – Vol. 5. – P. 123–127.Csiszar, I. Consistency of the BIC order estimator / I. Csiszar, P. Shields // Electronic research announcments of the American mathematical society. – 1999. – Vol. 5. – P. 123–127.Meier, W. The self-shrinking generator / W. Meier, O. Staffelbach // Advances in Cryptology – EUROCRYPT 94. – Springer-Verlag, 1995. – P. 205–214.Meier, W. The self-shrinking generator / W. Meier, O. Staffelbach // Advances in Cryptology – EUROCRYPT 94. – Springer-Verlag, 1995. – P. 205–214.Основы криптографии / А.П. Алферов [и др.]. – М. : Гелиос АРВ, 2001. – 480 с.54 p.Основы криптографии / А.П. Алферов [и др.]. – М. : Гелиос АРВ, 2001. – 480 с.54 p.

The authors declare that there are no conflicts of interest present.