Дослідження статистичних характеристик модифікованого алгоритму BBS із залежністю від поточного та попереднього значення послідовності

Ключові слова: псевдовипадкова послідовність; генератори псевдовипадкових послідовностей; одностороння функція; генератор Блюма-Блюма-Шуба

Анотація

У системах захисту інформації широкого застосування набув генератор Блюма-Блюма-Шуба (BBS), який базується на використанні односторонньої функції факторизації, та належить до криптостійких. У роботі досліджено характеристики запропонованого автором модифікованого алгоритму BBS із залежністю від поточного та попереднього значення послідовності, зокрема, період повторення та статистичні характеристики вихідної послідовності залежно від параметрів генератора. Дослідження проведено з використанням тестів NIST і порівняно із класичним алгоритмом BBS. З'ясовано, що період повторення класичного алгоритму BBS для малих значень ключа, від 5 до 10 бітів, становить не більше ніж 20 % від його значення. Ця тенденція зберігається на ключах більшого розміру, від 15 до 21 бітів, де період повторення для вибраних початкових установок не перевищує 5,56 %. Період повторення модифікованого алгоритму BBS для ключів від 5 до 10 бітів у середньому становить 200 % від значення ключа. Така поведінка зберігається для вибіркових початкових установок для ключів від 15 до 21 бітів, період повторення яких в середньому становить 351 %. Дослідження статистичних характеристик пакетом статистичних тестів NIST проведено на згенерованих послідовностях із 10бітів для ключів завдовжки від 29 до 31 бітів. Встановлено, що статистичні портрети для класичного алгоритму є не задовільними, зокрема, статистичні портрети для 31-бітного ключа мають до 5 незадовільних результатів із 188 тестів. Статистичні портрети для модифікованого алгоритму BBS є задовільними для ключів від 30 до 31 бітів, але не є задовільними для 29-бітного ключа – мають по одному незадовільному результату. Отже, модифікований алгоритм BBS має кращі значення періоду повторення та статистичні портрети порівняно із класичним алгоритмом, що дає змогу використовувати ключі меншої довжини при генеруванні послідовності, які вимагають менше ресурсів системи, оскільки операція піднесення до квадрату за модулем більш ресурсозатратна, ніж операція додавання. Подальші дослідження будуть зосереджені на апаратну реалізацію модифікованого алгоритму BBS та порівняння використаних ресурсів системи із реалізацією класичного алгоритму BBS.

Біографія автора

А. С. Малогловець, Національний університет "Львівська політехніка", м. Львів

аспірант, кафедра безпеки інформаційних технологій

Посилання

Aïssa, B., Khaled, M., & Lakhdar, G. (2014). Implementation of Blum Blum Shub generator for message encryption: proceedings of the International Conference on Control, Engineering and Information Technology (CEIT14). Tunisia, 6, pp. 118–123.

Blum, L., Blum, M., & Shub, M. (1983). Comparison of two pseudo-random number generators: proceedings of the Workshop on the Theory and Application of Cryptographic Techniques CRYPTO82. New York, pp. 61–78.

Blum, L., Blum, M., & Shub, M. (1986). A simple unpredictable pseudorandom number generator: SIAM. Journal on Computing, 15(2), 364–383.

Divyanjali, Ankur, Pareek, V. (2014). An overview of cryptographically secure pseudorandom number generators and BBS: IJCA proceedings of the International Conference on Advances in Computer Engineering and Applications ICACEA. March 2014, 2(3), 19–28.

Gawande, K., & Mundle, M. (2003). Various implementations of Blum Blum Shub pseudo-random sequence generator, Conference Proceedings. Retrieved from: https://pdfs.semanticscholar.org/5ddc/47b658a204ae76d00aec929b1a5b7fbbfaa6.pdf

Gurpreet, S., & Gurjot, G. (2017). DNA and Blum Blum Shub Random Number Generator Based Security Key Generation Algorithm. International Journal of Security and its Applications, 11, 1–10.

Junod, P. (1999). Cryptographic secure pseudo-random bits generation: The Blum-Blum-Shub generator. Retrieved from: http://crypto.junod.info/bbs.pdf

Kapur, V., & Teja, S. (2015). Two level image encryption using pseudo random number generators. International Journal of Computer Applications, 115(12), 1–4.

Lopez, P., & Millan, E. (2010). Cryptographically secure pseudorandom bit generator for RFID tags: proceedings of the International Conference for Internet Technology and Secured Trans. London, 8–11 Nov 2010, pp. 1–6.

Malohlovets, A. C., & Maksymovych, V. M. (2017). Metody pokrashchennia statystychnykh kharakterystyk kryptostiikykh heneratoriv BBS psevdovypadkovykh chysel i bitovykh poslidovnostei. Zakhyst informatsii i bezpeka informatsiinykh system: materialy VI Mizhnarodnii konferentsii (m. Lviv, 1 chervnia 2017), Lviv, 73–74. [In Ukrainian].

NIST SP 800-22. (2019). A Statistical Test Suite for Random and Pseudorandom Number Generators for Cryptographic Applications. Retrieved from: http://csrc.nist.gov/publications/nistpubs/800-22-rev1a/SP800-22rev1a.pdf.

Shrestha, B. (2016). Multiprime Blum-Blum-Shub Pseudorandom Number Generator, PhD thesis. Retrieved from: https://apps.dtic.mil/dtic/tr/fulltext/u2/1030047.pdf

Sidorenko, A., & Schoenmakers, B. (2005). Concrete security of the Blum-Blum-Shub pseudorandom generator: Cryptography and Coding, Lecture Notes on Computer Science, Springer. Nov 2005, 37(96), 355–375.

Опубліковано
2020-06-04
Як цитувати
Малогловець, А. С. (2020). Дослідження статистичних характеристик модифікованого алгоритму BBS із залежністю від поточного та попереднього значення послідовності. Науковий вісник НЛТУ України, 30(2), 122-128. https://doi.org/10.36930/40300222
Розділ
Інформаційні технології