Легенда:
 новое сообщение
 закрытая нитка
 новое сообщение
 в закрытой нитке
 старое сообщение
|
- Напоминаю, что масса вопросов по функционированию форума снимается после прочтения его описания.
- Новичкам также крайне полезно ознакомиться с данным документом.
| |
Я имел в виду два "смысла", первый именно этот, второй -... 17.01.05 16:37 Число просмотров: 2821
Автор: 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), но пока никто ничего толкового не предложил.
|
|
<theory>
|
бент: влияние лунного света на рост телеграфных столбов :) 14.01.05 14:04
Автор: leo <Леонид Юрьев> Статус: Elderman
|
Есть желание улучшить не-коррелируемость ГПСЧ. Идея такая: береться 11 32-битных чисел от ГПСЧ, одно отбрасывается, а от 10 берется поразрядная бент-функция, результат становится выходом "улучшенного" генератора. Причем перед вызовом bent аргументы подвергаются циклическому битовому сдвигу на 0, 1, 3, 5, 7, 11, 13, 17, 19, 23.
Понятно, что вроде-бы должно быть в ~10 раз лучше, но хочется теоретического успокоения. Увы нет "погруженности" в теорию до желаемого уровня и возможности сделать это в доступное время.
Кто может сказать что-либо толкового?
|
|
Если нужен улучшеный ГПСЧ по сравнению с 32, может просто... 17.01.05 11:54
Автор: DPP <Dmitry P. Pimenov> Статус: The Elderman
Отредактировано 17.01.05 12:01 Количество правок: 1
|
> Есть желание улучшить не-коррелируемость ГПСЧ. Идея такая:
> береться 11 32-битных чисел от ГПСЧ, одно отбрасывается, а
> от 10 берется поразрядная бент-функция, результат
> становится выходом "улучшенного" генератора. Причем перед
> вызовом bent аргументы подвергаются циклическому битовому
> сдвигу на 0, 1, 3, 5, 7, 11, 13, 17, 19, 23.
Если нужен улучшеный ГПСЧ по сравнению с 32, может просто воспользоваться 64 разрядным, построеным по аналогичному алгоритму. Он должен быть лучше не на десятичный порядок, а на десяток десятичных порядков. Скорость генерации нзначительно упадет, по сравнению с предложенным.
> Понятно, что вроде-бы должно быть в ~10 раз лучше, но
> хочется теоретического успокоения. Увы нет "погруженности"
> в теорию до желаемого уровня и возможности сделать это в
> доступное время.
>
> Кто может сказать что-либо толкового?
Рискну предложить что-то толковое.
Зачем нужны ГПСЧ? В основном для генерации ключа.
Для чего нужны "улучшеные" ГПСЧ? Чтоб сложнее было поломать атакой на генерацию ключа.
Какой самый лучший ГПСЧ? ГСЧ.
Почему народ пользуется именно ГПСЧ? Удобнее и быстрее - не надо дополнительного оборудования или "набирания случайного текста на клавиатуре".
Так почему бы не организовать ГСЧ на базе существующих устройств без использования клавиатуры? В компе почти нет подходящих устройств. Хотя почему нет, кто-то предлагал сделать что-то подобное на основе звуковой платы, точнее на основе ее "шума". Можно воспользоваться датчиками температуры, вращением кулеров, напряжения, временем перемещения головок дисковода.
|
| |
Представьте embedded-устройство, в которое пока не хочеться... 17.01.05 16:51
Автор: leo <Леонид Юрьев> Статус: Elderman
|
> Если нужен улучшеный ГПСЧ по сравнению с 32, может просто
> воспользоваться 64 разрядным, построеным по аналогичному
> алгоритму. Он должен быть лучше не на десятичный порядок, а
> на десяток десятичных порядков. Скорость генерации
> нзначительно упадет, по сравнению с предложенным.
>
> Рискну предложить что-то толковое.
> Зачем нужны ГПСЧ? В основном для генерации ключа.
> Для чего нужны "улучшеные" ГПСЧ? Чтоб сложнее было поломать
> атакой на генерацию ключа.
> Какой самый лучший ГПСЧ? ГСЧ.
> Почему народ пользуется именно ГПСЧ? Удобнее и быстрее - не
> надо дополнительного оборудования или "набирания случайного
> текста на клавиатуре".
> Так почему бы не организовать ГСЧ на базе существующих
> устройств без использования клавиатуры? В компе почти нет
> подходящих устройств. Хотя почему нет, кто-то предлагал
> сделать что-то подобное на основе звуковой платы, точнее на
> основе ее "шума". Можно воспользоваться датчиками
> температуры, вращением кулеров, напряжения, временем
> перемещения головок дисковода.
Представьте embedded-устройство, в которое пока не хочеться встраивать шумящий диод. Точнее говоря, дело не в самом диоде, а в том что если "доверять" всетолькоему, то нужно принять целый рад мер для его защиты и надежной работы.
Удваиваивание "ширины" генератора съест очень много ресурсов (больше чем в два раза), но при этом на смом деле априорно ничего не гарантирует.
|
| | |
Все правильно. Тогда, если учесть дополнительные условия,... 17.01.05 17:25
Автор: DPP <Dmitry P. Pimenov> Статус: The Elderman
|
> Представьте embedded-устройство, в которое пока не хочеться
> встраивать шумящий диод. Точнее говоря, дело не в самом
> диоде, а в том что если "доверять" всетолькоему, то
> нужно принять целый рад мер для его защиты и надежной
> работы.
Все правильно. Тогда, если учесть дополнительные условия, некоррелируемую последовательность ПСЧ можно попытаться получить последовательным шифрованием (DESом, например). Т.е. берем "немножко" начальных случайных 56-64 разрядных чисел, одно - исходный текст, другое ключ шифруем, шифруем. Можно для получения нового ПСЧ сложить текущее и предыдущее зашифрованное значение и то, что получится шифрануть. Что касается быстродействия, то я слышал что даже есть соответствующие чипы, маленькие, быстрые для встраиваемых устройств. Доказать некоррелируемость дложно быть не сложно.
> Удваиваивание "ширины" генератора съест очень много
> ресурсов (больше чем в два раза), но при этом на смом деле
> априорно ничего не гарантирует.
Ну, да, все зависит от алгоритма. Для тупого разрядность вообще не будет играть роли.
|
|
Зачем так извращаться? 15.01.05 03:44
Автор: 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, тогда ты можешь сделать хуже, т.к. результирующая п-ть будет иметь меньший период...
|
| |
Я имел в виду два "смысла", первый именно этот, второй -... 17.01.05 16:37
Автор: 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), но пока никто ничего толкового не предложил.
|
| | |
Чем же она тебя успокаивает? :) 05.02.05 19:28
Автор: Serge3leo Статус: Незарегистрированный пользователь
|
> > Что такое корреляция? Насколько я понимаю - это
> зависимость
> > текущего сгенеренного значения от m предыдущих. То
> есть
> Я имел в виду два "смысла", первый именно этот, второй -
> корреляция сгенерированных чисел с некими внешними
> процессами (т.е. качество генератора). Бент-функция пока
> "успокаивает" меня в обоих случаях.
Чем же она тебя успокаивает? :)
На мой, не просвещённый взгляд. Этот "алгоритм" имеет хоть какой-то смысл, если точно известно, что период ГПСЧ не кратен 11. Всё остальное "вода", т.к. в описаном довеске нет внутреннего состояния. Например, возмите две модельки ГПСЧ типа, скажем x = ( x + 1 ) % 11 и x = ( x + 1 ) % 13 и посмотрите на "улучшение".
|
| | | |
По-поводу самого ГПСЧ 06.02.05 13:55
Автор: leo <Леонид Юрьев> Статус: Elderman
Отредактировано 06.02.05 14:08 Количество правок: 1
|
Я не нашел способа как его толком проанализировать.
Алгоритм простой - 32-а LSFR по X64+X4+X3+X, выходы этих регистров формируют 32 разряда выхода генератора. Если состояние генератора представить в виде таблицы 64x32, то 32 LSFR образуют 32 строки по 64 бита.
Самое главное - feedback для сдвиговых регистров, он нелинейный. "Обычный" feedback (он в GF(2), но просто вычисляется параллельно для всех 32-х LSFR) складывается по модулю 232 с нелинейной функцией от трех "вертикалей" внутри 32-х LSFR, добавление константы не дает LSFR уйти "в нули".
Проще просмотреть С-код, чем объяснить :)
Дак вот, я не знаю (не нашел) как описать "поворот на 90" (и соответственно весь генератор), при формировании feedback для LSFR, кроме как булевой алгеброй. Но "булево представление" не дает мне возможность проанализировать генератор. У меня нет соответствующего образования и опыта в таких делах, и увы нет времени чтобы "доучиваться". Вполне возможно, что есть "общеизвестный" подход, который позволяет все это легко решить...
|
| | | |
IMHO сложнее алгебраическая атака с... 06.02.05 10:59
Автор: leo <Леонид Юрьев> Статус: Elderman
Отредактировано 06.02.05 11:01 Количество правок: 1
|
|
IMHO сложнее алгебраическая атака с целью предсказания внутреннего состояния ГПСЧ.
|
|
|
подробно о проекте
Анализ криптографических сетевых...
