Легенда:
 новое сообщение
 закрытая нитка
 новое сообщение
 в закрытой нитке
 старое сообщение
|
- Напоминаю, что масса вопросов по функционированию форума снимается после прочтения его описания.
- Новичкам также крайне полезно ознакомиться с данным документом.
Зачем так извращаться? 15.01.05 03:44 Число просмотров: 3151
Автор: whiletrue <Роман> Статус: Elderman
Отредактировано 15.01.05 04:09 Количество правок: 4
|
> Есть желание улучшить не-коррелируемость ГПСЧ. Идея такая:
> береться 11 32-битных чисел от ГПСЧ, одно отбрасывается, а
> от 10 берется поразрядная бент-функция, результат
> становится выходом "улучшенного" генератора. Причем перед
> вызовом bent аргументы подвергаются циклическому битовому
> сдвигу на 0, 1, 3, 5, 7, 11, 13, 17, 19, 23.
>
> Понятно, что вроде-бы должно быть в ~10 раз лучше, но
> хочется теоретического успокоения. Увы нет "погруженности"
> в теорию до желаемого уровня и возможности сделать это в
> доступное время.
>
> Кто может сказать что-либо толкового?
Что такое корреляция? Насколько я понимаю - это зависимость текущего сгенеренного значения от m предыдущих. То есть злоумышленник набирает какую-то статистику и строит некую цепь Маркова, глубины, которую позволяет его компьютер. Значит если увеличить период повторония генерируемой последовательности, то мы таким образом "уменьшим" коррелируемость. То есть усложним задачу злоумышленнику. Я прав?
Обычно рассматривается рекурентная последовательность, т.е. некий автономный автомат с какими-то начальными значениями. Все значения сдвигаются влево, а очередное значение генерится так Ai = g(Ai-1, ... Ai-m-1), где m - ранг рекурентной последовательности. Все делается над неким конечным полем, например GF(2^8) (т.е. символы от 0-255) или GF(2) (бинарная п-ть). Функция g может быть линенейной или нелинейной. В случае линейной рекурентной последовательности Ai = a1*Ai-1+ ...+ am*Ai-m-1 - это называется характеристическим уравнением ЛРП. Над выбранным полем можно рассматривать поле характеристических функций. ЛРП соответсвует характирестический многочлен f(x) = x^m + SUM(ai * x^i). Так вот чтобы построить ЛРП максимальной длины нужно просто взять неприводимый многочлен выбранного ранга (степени) m, период будет равен T=q^m - 1, где q - порядок конечного поля (2 - для бинарной п-ти). И еще есть теоремка, что если мы перемножим два многочлена с периодами T1 и T2, то период результирующего многочлена будет T=T1*T2. Все! Имея это на руках можно генерить последовательности любого самого злостного периода.
В случае нелинейных РП - там анализируется регулярность автомата, строятся какие-то злостные графы, в них склеиваются циклы... щас навру, а лезть смотреть неохота. Ну смотреть надо в этом направлении.
В твоем случае - надо понять что есть ф-ция g и ее уже анализировать, а для этого надо распотрошить твой ГПСЧ и bent... геморно, имхо. Грубо говоря ты делаешь так, чтобы сгенеренное число зависело от десяти предыдущих, а вдруг твой ГПСЧ генерит ЛРП со значениями, зависящими от i-100, i-31 и i-1, тогда ты можешь сделать хуже, т.к. результирующая п-ть будет иметь меньший период...
|
|
|
подробно о проекте
Анализ криптографических сетевых...
