Легенда:
 новое сообщение
 закрытая нитка
 новое сообщение
 в закрытой нитке
 старое сообщение
|
- Напоминаю, что масса вопросов по функционированию форума снимается после прочтения его описания.
- Новичкам также крайне полезно ознакомиться с данным документом.
Я имел в виду два "смысла", первый именно этот, второй -... 17.01.05 16:37 Число просмотров: 2826
Автор: leo <Леонид Юрьев> Статус: Elderman
|
> Что такое корреляция? Насколько я понимаю - это зависимость
> текущего сгенеренного значения от 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, тогда ты можешь сделать хуже, т.к.
> результирующая п-ть будет иметь меньший период...
Только в том случае если генератор "собран" на нелинейных функциях 100% коррелирующих с используемой бент-функцией.
Ясно, что по-хорошему нужно анализировать именно генератор (http://leo.yuriev.ru/random), но пока никто ничего толкового не предложил.
|
|
|
подробно о проекте
Анализ криптографических сетевых...
