Різноманіття псевдовипадкових блукань шахового коня для скремблювання багатовимірних даних
DOI:
https://doi.org/10.31558/2786-9482.2024.1.1Ключові слова:
скремблювання даних, псевдовипадкове блукання шахового коня, ймовірність зламу, рівень подібностіАнотація
Задача відкритого циклу шахового коня полягає у побудові послідовності ходів шахового коня, яка
повністю покриває шахову дошку без повторів, де початкове та кінцеве положення є завжди різними.
Розв’язок задачі відкритого циклу шахового коня подібний до послідовності псевдовипадкових чисел, за
якими можна відобразити дані у корисну інформацію без можливості її читання. Задача відкритого циклу
шахового коня для певного стартового положення має різноманіття розв’язків, кількість яких залежить від
розміру шахової дошки. Розв’язки задачі відкритого циклу шахового коня виглядають як його
псевдовипадкове блукання або як випадкова послідовність його положень. Ці розв’язки використовуються
для подальшого покращення балансу простоти скремблювання та продуктивності, де головними
показниками є ймовірність зламу та індекс подібності. Ймовірність зламу суттєво зменшується завдяки
різноманіттю псевдовипадкових блукань шахового коня для певного стартового положення на даній
шаховій дошці. Песимістична оцінка ймовірності зламу для шахової дошки розміром 8×8 є меншою за
10-16 . Аналогічна оцінка для шахової дошки розміром 8×8×8 є меншою за 10-26 . Конкретна реалізація
псевдовипадкового блукання шахового коня будується в режимі онлайн за заданого початкового цілого
для генератора псевдовипадкових чисел. Вектор даних після скремблювання також будується в режимі
онлайн за лінійної часової складності. Індекс подібності є прийнятним. Він стрімко падає зі зростанням
розміру шахової дошки (для більших масивів багатовимірних даних). Конкретне псевдовипадкове
блукання шахового коня визначається розміром шахової дошки, початковим положенням, методом
векторизації псевдовипадкового блукання шахового коня, а також початковим цілим для генератора
псевдовипадкових чисел. Ці параметри визначають специфічний рух коня у ситуаціях, коли постають
множинні варіанти подальшого руху. Скремблер на основі відкритого циклу шахового коня має від 1016
до 1021 разів меншу ймовірність зламу, порівняно зі звичайним псевдовипадковим генератором, залежно
від розміру шахової дошки та початкового положення шахового коня.
Посилання
Pandya, P. (2013). Advanced data encryption. In Cyber Security and IT Infrastructure
Protection (pp. 325–345). Elsevier. https://doi.org/10.1016/B978-0-12-416681-3.00015-X
Pandya, P. (2013). Advanced data encryption. In Computer and Information Security
Handbook (pp. 1127–1138). Elsevier Inc. https://doi.org/10.1016/B978-0-12-394397-
00070-2
Li, N., Zhang, N., Das, S. K., & Thuraisingham, B. (2009). Privacy preservation in wireless
sensor networks: A state-of-the-art survey. Ad Hoc Networks, 7(8), 1501–1514.
https://doi.org/10.1016/j.adhoc.2009.04.009
De Capitani di Vimercati, S., Foresti, S., Livraga, G., & Samarati, P. (2022). Digital
infrastructure policies for data security and privacy in smart cities. In Smart Cities Policies
and Financing: Approaches and Solutions (pp. 249–261). Elsevier.
https://doi.org/10.1016/B978-0-12-819130-9.00007-3
Waheed, A., Subhan, F., Suud, M. M., Alam, M. M., & Haider, S. (2023). Design and
optimization of nonlinear component of block cipher: Applications to multimedia security.
Ain Shams Engineering Journal, 102507. https://doi.org/10.1016/j.asej.2023.102507
Fair, T., Nordfelt, M., Ring, S., & Cole, E. (2005). Spying Basics. In Cyber Spying (pp. 45–
. Elsevier. https://doi.org/10.1016/b978-193183641-8/50005-8
Stapko, T. (2008). Choosing and optimizing cryptographic algorithms for resourceconstrained systems. In Practical Embedded Security (p. 149–171). Elsevier.
https://doi.org/10.1016/b978-075068215-2.50009-4
Sun, P. (2020). Security and privacy protection in cloud computing: Discussions and
challenges. Journal of Network and Computer Applications, 160, 102642.
https://doi.org/10.1016/j.jnca.2020.102642
Bakiri, M., Guyeux, C., Couchot, J.-F., & Oudjida, A. K. (2018). Survey on hardware
implementation of random number generators on FPGA: Theory and experimental analyses.
Computer Science Review, 27, 135–153. https://doi.org/10.1016/j.cosrev.2018.01.002
L’Ecuyer, P. (2006). Chapter 3. Uniform random number generation. In Handbooks in
Operations Research and Management Science. Vol. 13 (p. 55–81). Elsevier.
https://doi.org/10.1016/S0927-0507(06)13003-0
Plesser, H. E., & Jahnsen, A. G. (2010). Re-seeding invalidates tests of random number
generators. Applied Mathematics and Computation, 217(1), 339–346.
https://doi.org/10.1016/j.amc.2010.05.066
Dunn, W. L., & Shultis, J. K. (2012). Pseudorandom number generators. In Exploring Monte
Carlo Methods (pp. 47–68). Elsevier. https://doi.org/10.1016/b978-0-444-51575-9.00003-8
Bowman, K. P. (2005). Statistics and pseudorandom numbers. In An Introduction to
Programming with IDL (pp. 227–235). Elsevier. https://doi.org/10.1016/b978-012088559-
/50024-8
Ross, S. M. (2023). Random numbers. In Simulation (p. 39–45). Elsevier.
https://doi.org/10.1016/b978-0-32-385738-3.00008-0
Parberry, I. (1997). An efficient algorithm for the Knight’s tour problem. Discrete Applied
Mathematics, 73(3), 251–260. https://doi.org/10.1016/S0166-218X(96)00010-8
Lin, S.-S., & Wei, C.-L. (2005). Optimal algorithms for constructing knight’s tours on
arbitrary n m chessboards. Discrete Applied Mathematics, 146(3), 219–232.
https://doi.org/10.1016/j.dam.2004.11.002
Weisstein, E. W. Knight Graph. URL: https://mathworld.wolfram.com/KnightGraph.html
Bai, S., Yang, X.-F., Zhu, G.-B., Jiang, D.-L., & Huang, J. (2010). Generalized knight’s tour
on 3D chessboards. Discrete Applied Mathematics, 158, 1727–1731.
https://doi.org/10.1016/j.dam.2010.07.009
Kyek, O., Parberry, I., Wegener, I. (1997). Bounds on the number of knight’s tours. Discrete
Applied Mathematics, 74(2), 171–181. https://doi.org/10.1016/S0166-218X(96)00031-5
Romanuke, V. V. (2022). Finite uniform approximation of two-person games defined on a
product of staircase-function infinite spaces. International Journal of Approximate
Reasoning, 145, 139–162. https://doi.org/10.1016/j.ijar.2022.03.005
