информационная безопасность
без паники и всерьез
 подробно о проектеRambler's Top100
Страшный баг в WindowsSpanning Tree Protocol: недокументированное применениеВсе любят мед
BugTraq.Ru
Русский BugTraq
 Анализ криптографических сетевых... 
 Модель надежности двухузлового... 
 Специальные марковские модели надежности... 
 Три миллиона электронных замков... 
 Doom на газонокосилках 
 Умер Никлаус Вирт 
главная обзор RSN блог библиотека закон бред форум dnet о проекте
bugtraq.ru / форум / theory
Имя Пароль
ФОРУМ
все доски
FAQ
IRC
новые сообщения
site updates
guestbook
beginners
sysadmin
programming
operating systems
theory
web building
software
hardware
networking
law
hacking
gadgets
job
dnet
humor
miscellaneous
scrap
регистрация





Легенда:
  новое сообщение
  закрытая нитка
  новое сообщение
  в закрытой нитке
  старое сообщение
  • Напоминаю, что масса вопросов по функционированию форума снимается после прочтения его описания.
  • Новичкам также крайне полезно ознакомиться с данным документом.
Зачем так извращаться? 15.01.05 03:44  Число просмотров: 3067
Автор: 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, тогда ты можешь сделать хуже, т.к. результирующая п-ть будет иметь меньший период...
<theory> Поиск 






Rambler's Top100
Рейтинг@Mail.ru


  Copyright © 2001-2024 Dmitry Leonov   Page build time: 0 s   Design: Vadim Derkach