информационная безопасность
без паники и всерьез
 подробно о проектеRambler's Top100
Где водятся OGRыSpanning Tree Protocol: недокументированное применениеСтрашный баг в Windows
BugTraq.Ru
Русский BugTraq
 Анализ криптографических сетевых... 
 Модель надежности двухузлового... 
 Специальные марковские модели надежности... 
 Google закрывает безлимитные Photos 
 Имя компании как средство XSS-атаки 
 Утекший код XP и Windows Server... 
главная обзор 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
регистрация





Легенда:
  новое сообщение
  закрытая нитка
  новое сообщение
  в закрытой нитке
  старое сообщение
  • Напоминаю, что масса вопросов по функционированию форума снимается после прочтения его описания.
  • Новичкам также крайне полезно ознакомиться с данным документом.
Я имел в виду два "смысла", первый именно этот, второй -... 17.01.05 16:37  Число просмотров: 2411
Автор: 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> Поиск 








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


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