Математика и математическое моделирование. 2020; : 1-51
Четыре клеточно-автоматных алгоритма пермутаций матриц
https://doi.org/10.24108/mathm.0420.0000223Аннотация
С помощью численного расчета описывается работа алгоритмов пермутаций матриц, основанных на циклических сдвигах строк и столбцов. Такой выбор алгоритмов дискретного преобразования обоснован удобством клеточно-автоматных формулировок, которые и приводятся. Получены эмпирические формулы для периода пермутаций; для последнего алгоритма формула периода носит рекуррентный характер. Для базовой и наиболее простой схемы период N(n) имеет асимптотику exp(2n)/n для матрицы nxn с попарно различными элементами. Несмотря на усложнение схемы алгоритма, две другие модификации дают лишь полиномиальный рост степени не выше 3. Четвертая схема имеет нетривиальную зависимость периода, но не выше экспоненциальной. В ряде случаев алгоритмы порождают особые пермутации: поворот, отражение и перестановку блоков для матрицы 2kx2k. Эти формулы тесно связаны с индивидуальными траекториями элементов, а они – с влиянием границ, что дает ветвление порядка матрицы по классу вычета по модулю 3,4 или 12. Визуализации этих траекторий приводятся в расширенном поле КА. В качестве параметра динамики КА анализируются две «метрики перемешанности» на пермутациях матрицы (по сравнению с начальной). Для всех схем и большинства ветвей поведение этих метрик представлено на графиках и гистограммах (условно: плотности распределения), показывающих, как часто встречаются по периоду пермутации с заданным интервалом значений метрик. Практическое значение работы состоит в оценке применения КА в областях генерации псевдослучайных чисел и криптографии.
Список литературы
1. Wolfram S. Random Sequence Generation by Cellular Automata // Advances in Applied Mathematics, 1986, vol. 7, Pp. 429 – 432.
2. Сухинин Б. М. Разработка генераторов псевдослучайных двоичных последовательностей на основе клеточных автоматов // Машиностроение и компьютерные технологии. 2010. №9. Режим доступа: https://cyberleninka.ru/article/n/razrabotka-generatorov-psevdosluchaynyh-dvoichnyh-posledovatelnostey-na-osnove-kletochnyh-avtomatov (дата обращения: 25.08.2020).
3. Ярмолик В.Н., Мурашко И. А. Реализация генератора псевдослучайной последовательности на клеточных автоматах // Автоматика и вычислительная техника. 1993. №3. С. 9-13.
4. Bar dell P. Analysis of cellular automata used as pseudorandom pattern generators // Proceeings., International Test Conference. 1990. Pp. 762-768.
5. Girau B., Vlassopoulos N. Evolution of 2-dimensional cellular automata as pseudo-random number generators // Cellular automata: 10th Intern. conf. on cellular automata for research and industry: ACRI 2012 (Santorini island, Greece, Sept. 24-27, 2012): Proc. B.; Hdbl.: Springer, 2012. Pp. 611-622.
6. Мухамеджанов Д.Д., Левина А.Б. Генератор псевдослучайных чисел на основе клеточных автоматов // Научно-технический вестник информационных технологий, механики и оптики. 2018. №5. С 894–900. DOI: 10.17586/2226-1494-2018-18-5-894-900
7. S. Bilan, M. Bilan, S. Bilan, Novel pseudo-random sequence of numbers generator based cellular automata. // Information Technology and Security. – 2015. – Vol. 3, Iss. 1 (4). – Pp. 38–50. DOI: doi.org/10.20535/2411-1031.2015.3.1.57710
8. Bruno Martin, Patrick Solé. Pseudo-random Sequences Generated by Cellular Automata. International Conference on Relations, Orders and Graphs: Interactions with Computer Science, May 2008, Mahdia, Tunisia, Pp. 401-410.
9. Agrawal V, Bushnell M. Essentials of Electronic Testing for Digital, Memory, and Mixed-Signal VLSI Circuits. Springer, 2000. Pp. 712.
10. Hortensius P.D. Parallel random number generation for VLSI systems using cellular automata // IEEE Transactions on Computers. 1989. Vol. 28 (10). Pp. 1466-1473.
11. Fog A. Pseudo-Random Number Generators for Vector Processors and Multicore Processors. // Journal of modern applied statistical methods. 2015. №14(1) Pp 308 - 334.
12. Ключарёв П.Г. Построение случайных графов, предназначенных для применения в криптографических алгоритмах, основанных на обобщенных клеточных автоматах. // Математика и математическое моделирование. 2017. №3. С. 77-90. DOI: 10.24108/mathm.0317.0000076.
13. Конахович Г.Ф. , Пузыренко А.Ю. Компьютерная стеганография Теория и практика. К "МК-Пресс" 2006. Гл. 5. С. 92-97.
14. Chen Y. L., Lambooij E., Mennink B. How to Build Pseudorandom Functions From Public Random Permutations Cryptology. Cryptology ePrint Archive. Available at https://eprint.iacr.org/2019/554.pdf , accessed 09.07.2020.
15. Trevisan L. U.C. Berkeley — CS276: Cryptography: Notes for Lecture 15. Available at https://people.eecs.berkeley.edu/~luca/cs276/lecture15.pdf , accessed 09.07.2020.
16. Rubio, C. F., L. Encinas, S. H. White, Á. Rey and G. Sánchez. The Use of Linear Hybrid Cellular Automata as Pseudo Random Bit Generators in Cryptography. // Neural Parallel & Scientific Comp. 2004. №12. Pp 175-192.
17. Жуков Д. А. О порядке одной перестановки на элементах квадратной матрицы // Десятая международная научно-технической конференция «Безопасные информационные технологии»: труды. М.: Москва, Изд-во Московский государственный технический университет имени Н.Э. Баумана (национальный исследовательский университет) (Москва), 2019. С. 143-145.
18. Weichuang Guo, Junqin Zhao, Ruisong Ye. A chaos-based pseudorandom permutation and bilateral diffusion scheme for image encryption // Intern. J. of Image, Graphics and Signal Processing. 2014. Vol. 6. №11. Pp. 50–61.
19. Матюшкин И.В., Кожевников В.С Клеточно-автоматные алгоритмы пермутации матриц // ТРУДЫ МФТИ. 2019. Том 11, № 1. С.39-52.
20. Матюшкин И.В., Кожевников В.С. Клеточно-автоматный алгоритм пермутации мат-риц // Математика и математическое моделирование. 2019. №3. С. 1-24.
21. Деза Е.И., Деза М.М. Энциклопедический словарь расстояний: пер. с англ. М.: Наука, 2008. 444 с. [Deza E., Deza M.M. Dictionary of distances. Amst.: Elsevier, 2006. 391 p.].
Mathematics and Mathematical Modeling. 2020; : 1-51
Four Cellular Automata Algorithms for Matrix Permutation
https://doi.org/10.24108/mathm.0420.0000223Abstract
Numerical calculation uses to describe the operation of matrix permutation algorithms based on cyclic shifts of rows and columns. This choice of discrete transformation algorithms justified by the convenience of the cellular automaton (CA) formulation, which is used. Obtained Empirical formulas for the permutation period and for the last algorithm, which period formula is recurrent. For a base scheme period has the asymptotics: for a matrix with pairwise different elements. Despite the complexity of the scheme, the other two modifications only give a polynomial growth of period, no higher than 3. Fourth scheme has a non-trivial period dependence, but no higher than the exponential. In some cases algorithms make special permutations: rotate, reflect, and rearrange blocks for the matrix . These formulas are closely related to individual cells paths. And paths connected with the influence of the boundaries that gives branching the matrix order by subtraction class modulo 3,4 or 12. Visualizations of these paths make in the extended CA-field. Two "mixing metrics" analyze as a parameter of CA dynamics on matrix permutations (compared to the initial). For all schemes and most branches, the behavior of these metrics shows in graphs and histograms (conditional density distribution) showing how often the permutation period occurs with the specified interval of metrics. The practical aim of this work is in the field of pseudorandom number generation and cryptography.
References
1. Wolfram S. Random Sequence Generation by Cellular Automata // Advances in Applied Mathematics, 1986, vol. 7, Pp. 429 – 432.
2. Sukhinin B. M. Razrabotka generatorov psevdosluchainykh dvoichnykh posledovatel'nostei na osnove kletochnykh avtomatov // Mashinostroenie i komp'yuternye tekhnologii. 2010. №9. Rezhim dostupa: https://cyberleninka.ru/article/n/razrabotka-generatorov-psevdosluchaynyh-dvoichnyh-posledovatelnostey-na-osnove-kletochnyh-avtomatov (data obrashcheniya: 25.08.2020).
3. Yarmolik V.N., Murashko I. A. Realizatsiya generatora psevdosluchainoi posledovatel'nosti na kletochnykh avtomatakh // Avtomatika i vychislitel'naya tekhnika. 1993. №3. S. 9-13.
4. Bar dell P. Analysis of cellular automata used as pseudorandom pattern generators // Proceeings., International Test Conference. 1990. Pp. 762-768.
5. Girau B., Vlassopoulos N. Evolution of 2-dimensional cellular automata as pseudo-random number generators // Cellular automata: 10th Intern. conf. on cellular automata for research and industry: ACRI 2012 (Santorini island, Greece, Sept. 24-27, 2012): Proc. B.; Hdbl.: Springer, 2012. Pp. 611-622.
6. Mukhamedzhanov D.D., Levina A.B. Generator psevdosluchainykh chisel na osnove kletochnykh avtomatov // Nauchno-tekhnicheskii vestnik informatsionnykh tekhnologii, mekhaniki i optiki. 2018. №5. S 894–900. DOI: 10.17586/2226-1494-2018-18-5-894-900
7. S. Bilan, M. Bilan, S. Bilan, Novel pseudo-random sequence of numbers generator based cellular automata. // Information Technology and Security. – 2015. – Vol. 3, Iss. 1 (4). – Pp. 38–50. DOI: doi.org/10.20535/2411-1031.2015.3.1.57710
8. Bruno Martin, Patrick Solé. Pseudo-random Sequences Generated by Cellular Automata. International Conference on Relations, Orders and Graphs: Interactions with Computer Science, May 2008, Mahdia, Tunisia, Pp. 401-410.
9. Agrawal V, Bushnell M. Essentials of Electronic Testing for Digital, Memory, and Mixed-Signal VLSI Circuits. Springer, 2000. Pp. 712.
10. Hortensius P.D. Parallel random number generation for VLSI systems using cellular automata // IEEE Transactions on Computers. 1989. Vol. 28 (10). Pp. 1466-1473.
11. Fog A. Pseudo-Random Number Generators for Vector Processors and Multicore Processors. // Journal of modern applied statistical methods. 2015. №14(1) Pp 308 - 334.
12. Klyucharev P.G. Postroenie sluchainykh grafov, prednaznachennykh dlya primeneniya v kriptograficheskikh algoritmakh, osnovannykh na obobshchennykh kletochnykh avtomatakh. // Matematika i matematicheskoe modelirovanie. 2017. №3. S. 77-90. DOI: 10.24108/mathm.0317.0000076.
13. Konakhovich G.F. , Puzyrenko A.Yu. Komp'yuternaya steganografiya Teoriya i praktika. K "MK-Press" 2006. Gl. 5. S. 92-97.
14. Chen Y. L., Lambooij E., Mennink B. How to Build Pseudorandom Functions From Public Random Permutations Cryptology. Cryptology ePrint Archive. Available at https://eprint.iacr.org/2019/554.pdf , accessed 09.07.2020.
15. Trevisan L. U.C. Berkeley — CS276: Cryptography: Notes for Lecture 15. Available at https://people.eecs.berkeley.edu/~luca/cs276/lecture15.pdf , accessed 09.07.2020.
16. Rubio, C. F., L. Encinas, S. H. White, Á. Rey and G. Sánchez. The Use of Linear Hybrid Cellular Automata as Pseudo Random Bit Generators in Cryptography. // Neural Parallel & Scientific Comp. 2004. №12. Pp 175-192.
17. Zhukov D. A. O poryadke odnoi perestanovki na elementakh kvadratnoi matritsy // Desyataya mezhdunarodnaya nauchno-tekhnicheskoi konferentsiya «Bezopasnye informatsionnye tekhnologii»: trudy. M.: Moskva, Izd-vo Moskovskii gosudarstvennyi tekhnicheskii universitet imeni N.E. Baumana (natsional'nyi issledovatel'skii universitet) (Moskva), 2019. S. 143-145.
18. Weichuang Guo, Junqin Zhao, Ruisong Ye. A chaos-based pseudorandom permutation and bilateral diffusion scheme for image encryption // Intern. J. of Image, Graphics and Signal Processing. 2014. Vol. 6. №11. Pp. 50–61.
19. Matyushkin I.V., Kozhevnikov V.S Kletochno-avtomatnye algoritmy permutatsii matrits // TRUDY MFTI. 2019. Tom 11, № 1. S.39-52.
20. Matyushkin I.V., Kozhevnikov V.S. Kletochno-avtomatnyi algoritm permutatsii mat-rits // Matematika i matematicheskoe modelirovanie. 2019. №3. S. 1-24.
21. Deza E.I., Deza M.M. Entsiklopedicheskii slovar' rasstoyanii: per. s angl. M.: Nauka, 2008. 444 s. [Deza E., Deza M.M. Dictionary of distances. Amst.: Elsevier, 2006. 391 p.].
