Материалы что дал Мухачев / Материалы что дал Мухачев / Білети_коротки_відповіді / Білети_відпові_УБДМ / Sp_Otvet16

№ 16. Криптографічні генератори ПВЧ на основі теоретико-числових методів. Генератор BBS

Стійкість криптографічних генераторів ПВЧ на основі теоретико-числових методів основана на складності теоретико-числових проблем. Стійкість генератора BBS основана на складності задачі факторизації натуральних чисел.

Процедура генерування ПВЧ за допомогою генератора BBS наступна.

1. Вибираються два секретних надвеликих простих числа , і обчислюється .

2. Вибирається секретне випадкове значення : і обчислюється початкове значення генератора: .

3. Для генерування послідовності псевдовипадкових бітів необхідно обчислити для обчислити і . Таким чином, на кожній ітерації створюється один біт послідовності.

Доведено, що цей генератор задовільняє т. зв. критерій наступного біта, тобто для довільного не існує ефективного алгоритму, що дозволяє за першими бітами передбачити -ший біт з ймовірністю, що суттево відрізняється від .