АНАЛІЗ ЕФЕКТИВНОСТІ АТАКИ ТИПУ «ВГАДАЙ ТА ВИЗНАЧ» НА ГЕНЕРАТОР ПСЕВДОВИПАДКОВИХ ПОСЛІДОВНОСТЕЙ ГОЛЬДРАЙХА З МОДИФІКОВАНИМ ПРЕДИКАТОМ P5

Анотація

У даній статті досліджено стійкість генератора псевдовипадкових послідовностей Гольдрайха класу
складності NC0 з різними предикатами локальності 5 до атаки типу “вгадай та визнач” (guess-and-determine).
Генератор належить до локальних, у яких кожен вихідний біт залежить лише від фіксованої кількості вхідних
бітів, що забезпечує високу швидкодію та паралельність обчислень. Розглянуто п’ять варіантів предиката P5
, що
відрізняються позицією нелінійного елемента (AND): на початку, всередині та в кінці булевої функції, а також,
для порівняння, лінійний предикат. Метою роботи є визначення впливу розташування елемента AND та інших
параметрів генератора на ефективність атаки, зокрема на відсоток успішності, час її проведення, кількість
необхідних вгадувань та кількість колізій. Проведено експериментальні дослідження для розмірів початкових
значень n = 16, 32, 48, 64 та різних коефіцієнтів розтягу s = 1,15; 1,20; 1,25; 1,30; 1,35. Встановлено, що позиція
операції AND та параметри n і s суттєво впливають на стійкість генератора. Методом Гаусса можна відновити
початкове значення з ймовірністю понад 90%, що підтверджує необхідність використання нелінійних елементів
для забезпечення криптографічної стійкості. Предикати з AND на початку або в кінці забезпечують найвищу
успішність атаки для малих значень n та s, однак характеризуються більшою тривалістю виконання. Натомість
запропоновані предикати з AND всередині виявилися стійкішими при малих s, особливо зі збільшенням розміру
n. Виявлено, що збільшення коефіцієнта розтягу s спрощує атаку через зростання кількості колізій, тоді як
збільшення розміру насіння n, навпаки, знижує її ефективність внаслідок експоненційного зростання простору
станів. Отримані результати уточнюють вплив структури предиката та параметрів генератора Гольдрайха на його
стійкість і можуть слугувати теоретичною основою для прогнозування їхньої поведінки при збільшенні n та
проєктування безпечніших криптографічних генераторів.
Ключові слова: генератор псевдовипадкових послідовностей, генератор Гольдрайха, криптоаналіз, атака
типу “guess-and-determine”, низька локальність, нелінійність, колізії.

Перелік посилань
1. Röck A. Pseudorandom number generators for cryptographic applications [Electronic resource]: Master’s
thesis / A. Röck, Paris-Lodron-Universität Salzburg, 2005. 131 p. Mode of access: https://wwwroc.inria.fr/secret/Andrea.Roeck/pdfs/dipl.pdf.
2. Кіх М. Комплексне криптографічне оцінювання гібридного генератора псевдовипадкових
послідовностей на основі аудіоентропії та нелінійних булевих функцій / М. Кіх, О. Нємкова // Кібербезпека:
освіта, наука, техніка. 2025. Том 31, № 3. P. 270–282. https://doi.org/10.28925/2663-4023.2025.31.1020.
3. Мандрона М. Атаки на генератори псевдовипадкових чисел / М. Мандрона, О. Гарасимчук // Вісник
Національного університету “Львівська політехніка”. Серія: Автоматика, вимірювання та керування. 2012.
№ 741. P. 251–256. Mode of access: https://ena.lpnu.ua/items/f0830f09-b7b1-4750-b462-6d9c0006e9f1.
4. Цебак О. Методи оцінки якості та криптостійкості послідовностей, згенерованих генераторами
псевдовипадкових чисел / О. Цебак, С. Войтусік // Сучасний захист інформації. 2025. Том 64, № 4. P. 164–171.
https://doi.org/10.31673/2409-7292.2025.041218.
5. Горячий О. Дослідження множини початкових значень генераторів псевдовипадкових чисел на основі
арифметики з рухомою комою / О. Горячий, В. Максимович, М. Шабатура // Сучасний захист інформації. 2024.
Том 58, № 2. P. 91–102. https://doi.org/10.31673/2409-7292.2024.020011.
6. Kelsey J. Cryptanalytic attacks on pseudorandom number generators / J. Kelsey, B. Schneier, D. Wagner, С.
Hall // Fast Software Encryption Workshop (FSE 1998). Lecture Notes in Computer Science, Springer, Vol. 1372, 1998.
P. 168–188. https://doi.org/10.1007/3-540-69710-1_12.
7. Горячий О. Розроблення генераторів псевдовипадкових чисел на основі покращених методів обчислення
елементарних функцій для задач кібербезпеки [Електронний ресурс] : Дисертація доктора філософії / О. Горячий
Національний університет “Львівська політехніка”, Львів, 2025. 288 p. Режим доступу:
https://lpnu.ua/sites/default/files/2025/radaphd/32585/disertaciya-goryachogo-o-ya.pdf.
8. Almaraz Luengo E. Cryptographically secured pseudo-random number generators: analysis and testing with
NIST statistical test suite / E. Almaraz Luengo, J. Román Villaizán // Mathematics. 2023. Vol. 11, no. 23. 4812.
https://doi.org/10.3390/math11234812.
9. Ruhault S. Security analysis for pseudo-random number generators [Electronic resource] : Doctoral thesis / S.
Ruhault, Ecole normale supérieure, 2015. 156 p. Mode of access: https://theses.hal.science/tel-01236602v2.
10. Goldreich O. Candidate one-way functions based on expander graphs / O. Goldreich // IACR Cryptology ePrint
Archive. 2000. Report 2000/063. Mode of access: https://www.wisdom.weizmann.ac.il/~oded/COL/ow-cand.pdf.
11. Mossel E. On ε-biased generators in NC⁰ / E. Mossel, A. Shpilka, L. Trevisan // 44th Annual IEEE Symposium
on Foundations of Computer Science (FOCS 2003). IEEE, 2003. P. 136–145. Mode of access: https://faculty.
wharton.upenn.edu/wp-content/uploads/2014/07/On_Biased_Generators_in_NC0_1.pdf.
12. Applebaum B. Cryptography in NC⁰ / B. Applebaum, Y. Ishai, E. Kushilevitz // SIAM Journal on Computing.
2006. Vol. 36, no. 4. P. 845–888. Mode of access: https://www.wisdom.weizmann.ac.il/~bennyap/pubs/nc0.pdf.
13. Applebaum B. Pseudorandom generators with long stretch and low locality from random local one-way
functions / B. Applebaum // SIAM Journal on Computing. 2013. Vol. 42, no. 5. P. 2008–2037. Mode of access:
https://eccc.weizmann.ac.il/report/2011/007/download/.
14. O'Donnell R. Goldreich's PRG: Evidence for near-optimal polynomial stretch / R. O'Donnell, D. Witmer //
IEEE 29th Conference on Computational Complexity (CCC 2014). IEEE, 2014. P. 1–12. Mode of access:
https://www.cs.cmu.edu/~dwitmer/papers/csp-prg.pdf.
15. Applebaum B. Algebraic attacks against random local functions and their countermeasures / B. Applebaum, S.
Lovett // 48th Annual ACM Symposium on Theory of Computing (STOC 2016). ACM, 2016. P. 1087–1100. Mode of
access: https://dl.acm.org/doi/epdf/10.1145/2897518.2897554.
16. Couteau G. On the concrete security of Goldreich's pseudorandom generator / G. Couteau, A. Dupin, P. Méaux,
M. Rossi, Y. Rotella // International Conference on the Theory and Application of Cryptology and Information Security
(ASIACRYPT 2018). – Springer, 2018. P. 96–124. Mode of access: https://eprint.iacr.org/2018/1162.pdf.
17. Couteau G. On the concrete security of Goldreich's pseudorandom generator [Electronic resource] / G. Couteau,
A. Dupin, P. Méaux, M. Rossi, Y. Rotella // ASIACRYPT 2018. 2018. Mode of access: https://asiacrypt.
iacr.org/2018/files/SLIDES/TUESDAY/421/slides_PRG.pdf.
18. Yang J. Revisiting the concrete security of Goldreich's pseudorandom generator / J. Yang, Q. Guo, T.
Johansson, M. Lentmaier // IEEE Transactions on Information Theory. 2020. Mode of access: https://ieeexplore.
ieee.org/document/9615074.
19. Applebaum B. Structured-seed local pseudorandom generators and their applications / B. Applebaum, D. Bui,
G. Couteau, N. Melissaris // IACR Cryptology ePrint Archive. 2024. Report 2024/1027. Mode of access: https://eprint.
iacr.org/2024/1027.pdf.
20. Fu X. Attacks on Goldreich's pseudorandom generators by grouping and solving / X. Fu, M. Li, S. Lyu, C. Liu
// IACR Cryptology ePrint Archive. 2024. Report 2024/1594. Mode of access: https://eprint.iacr.org/2024/1594.pdf.