ГСЧ разные статьи :: Форумы техгруппы TEGIR

Международная объединенная техническая группа
исследований и разработок
ТЕГИР

Дружественные исследовательские группы:

Форумы TEGIR.RU: Форум Программа PSI-ГСЧ. Энтропия. :

Тема: ГСЧ разные статьи

Генерация случайных чисел (и ляпы “Компьютерры”)

9. December 2007, 10:21 Безопасность, Избранное, Компьютеры и ПО, Математика

Всё-таки довольно забавно начинает звучать текст, если автор называет псевдослучайные числа - случайными. Вот в “Компьютерре” статья, где как раз речь о псевдослучайных числах, но автор предпочитает уверенно называть их “случайные”. В статье пишут, например:

”
Скажем, генератор случайных чисел, встроенный в ОС Windows, автоматически используется во всех приложениях системы, связанных с защитой информации. И при этом конкретные алгоритмы генерации, используемые в Microsoft для данной цели, никогда открыто не публиковались[...]

…аналитики нашли уязвимость, позволяющую организовать атаку, эффективно отыскивающую предыдущие состояния генератора, а значит, и вычислять будущие числа на выходе.”

Вот такие случайные числа, генерируемые, тем не менее, “алгоритмом” и, тем не менее, вычисляемые на будущее аналитиками. По-моему, кошмар.

Как обстоит дело в реальности: в большинстве компьютерных приложений, о которых идёт речь, используются последовательности псевдослучайных чисел. Псевдослучайными они называются потому, что каждый следующий член последовательности вычисляется некоторым заранее известным способом. При этом хороший алгоритм генерации устроен таким образом, что последовательность (точнее, некоторый её фрагмент) обладает важными статистическими свойствами последовательностей случайных чисел. Вообще говоря, некоторый “участок” хорошей псевдослучайной последовательности может быть не отличим от действительно случайной.

Но при этом псевдослучайные числа очевидно не являются случайными, так как они зависят друг от друга, а впечатление случайности (ложное) возникает лишь от того, что аналитику не “виден” механизм генерации. Тем не менее, криптоанализ псевдослучайных последовательностей может принести полезные результаты, а в самих алгоритмах генерации известны уязвимости.

Таким образом, если криптосистема существенным образом использует тот или иной алгоритм генерации псевдослучайных чисел, то стойкость этой криптосистемы оказывается завязана на стойкость “псевдослучайного” алгоритма. Например, сам шифр может быть очень стойким, но если для генерации ключей шифра использован нестойкий алгоритм, то стойкость самого шифра, понятно, уже не имеет значения.

Эта особенность, конечно, давно известна, поэтому для получения более стойких “случайных” последовательностей используются другие методы. На практике они привязаны к некоторым физическим процессам, происходящим в окружающем мире. Например, в качестве источника для получения последовательности чисел используется тепловой шум в электронных устройствах. Этот тепловой шум, несомненно, более близок к случайному процессу. Тем не менее, только близок, а в строгом смысле этот процесс тоже не является случайным.

Дело в том, что зная в подробностях физическое состояние “шумящего” устройства на момент начала генерации последовательности, аналитик, построив математическую модель устройства генерации (физические законы, определяющие тепловой шум, хорошо известны, и всё сводится к мощности вычислителя), может либо определить все члены последовательности в точности, либо сильно сузить область перебора. При этом, если в устройстве генератора допущена ошибка, задача аналитика резко упрощается (почему это так, мы в другой раз обсудим). По этой причине источники “случайности”, подобные только что описанному, называют детерминированными, то есть, по большому счёту, генерируемые ими числа тоже являются псевдослучайными.

С генерацией же действительно случайных чисел, совершенно непредсказуемых (по современным представлениям), имеются большие проблемы. Однако и такие генераторы сейчас существуют, они основаны на квантовых физических процессах. Например, генератор действительно случайных чисел может быть построен на основе регистрации радиоактивного распада - этот процесс совершенно непредсказуем.

Ссылка по теме: моя колонка про случайные числа на “Информационном буме” http://ezhe.ru/ib/issue586.html

источник: http://dxdt.ru/2007/12/09/891/
      1 Старлинг (2008-09-12, 13:08:32) 0

ссылка из конца предыдущего текста:

Неопределенный текст
Если игральные кости не перемешивать тщательно, не бросать решительным жестом, а, скажем, потихоньку переворачивать мизинцем, перекатывая по столу, то выпадающее число сможет предугадать даже попугай какаду. При условии, конечно, что попугая хорошо обучили, а специально посаженный рядом с клеткой человек дернет в нужный момент птицу за хвост, с помощью специального шнурка. Фокус фокусом, но выпадающие числа перестанут казаться неожиданностью.

Говорят, что группа хорошо подготовленных специалистов обыгрывала казино, используя технические и компьютерные средства для ликвидации непредсказуемости в рулетке. Будто, подсадной засланец за игровым столом с помощью замаскированного и довольно хитрого лазерного устройства измерял скорость движения шарика по желобку (вы же знаете, там такой желобок, по которому пускают шарик, чтобы тот в итоге залетел в нужную ячейку). Далее процесс одурачивания казино требовал привлечения современн
      2 Старлинг (2008-09-12, 13:09:30) 0

Статья http://leo.yuriev.ru/114
с картинками и схемами, поэтмоу только ссылка:
http://leo.yuriev.ru/114
      3 Старлинг (2008-09-12, 13:11:36) 0

Блин еле нашел!
а адрес оказался просто : )))

http://random.org/integers/
заходим сюда - и делаем выборку.
      4 Старлинг (2008-09-12, 13:47:00) 0

Стар скажи как идея :)
берем веб-камеру, и загоняем её в темный ящик, смотрим на шумы, коих на веб-камерах будет много..чем не АГСЧ? аппаратно - да, шум - да
и сразу уж на юсб
      5 Marconi (2009-03-14, 10:13:50) 0

да. но зачем такой гемор излишний?
и - будет много шумов матрицы, а они содержать много не-случайных компонент.
      6 Старлинг (2009-03-16, 11:39:37) 0

Теория случайных процессов

Булинский А.В., Ширяев А.Н.

ISBN: 5-9221-0335-0
Оформление: твердый пер., 400 стр.
Стандарт упаковки: 10
Физматлит, 2003 г.

Цена по прайс-листу: 352 руб.
      7 Rusa (2009-03-19, 17:38:49) 0

Кто в продаже увидит - скажите, я как раз собираюсь в выходные в какой-нть книжный заехать.
сомневаюсь, что в озоне она будет...
      8 Старлинг (2009-03-19, 21:23:16) 0

гм.
есть.
только стоит 571 руб и издание 2005 года.

http://www.ozon.ru/?context=search&text=%C1%F3%EB%E8%ED%F1%EA%E8%E9&go=%CD%E0%E9%F2%E8

Руслан, это она?
Стоит брать?
Дороговата, зараза, данег жалко. Вдруг опять лажа какая-нть, новодел очередной..
      9 Старлинг (2009-03-19, 21:26:25) 0

Могу предложить электронный вариант в формате DjVU

Ю.Д.Максимов
Теория вероятностей. Спаравочник по одномерным непрерывным распределениям. СПгПУ 2002.
      10 Влад (2009-03-20, 12:31:18) 0

А что это даст? оно нужно?
Руся-то знает, что рекомендовать чайникам...
      11 Старлинг (2009-03-20, 21:12:25) 0

Вот нашел статью: <a href=“http://www.mir-koda.ru/full_leson.php?id=8“>Генератор случайных чисел</a>
      12 ertyuo (2009-08-27, 12:11:33) 0

Случайно нашел одно интересное упоминание. Насчет достоверности- хз пока что. По ссылке ниже смотрим событие за номером 4: http://www.rusrep.ru/2008/48/glavnye_nauchnye_sobytiya/
      13 Crowbar (2009-09-30, 02:13:44) 0

Да.
вот и Соленый с этим как раз возится.
Только как-бы “вид сбоку“.
и Козырева туда же:
не столько флуктуации, сколько “направление некоторой гравитационной постояной“, эфира коточе.
меняющегося под влиянием местынх факторов.
      14 Starling (2009-09-30, 16:51:34) 0

нагажу тут :)
а так ли плохи ПГСЧ а? вот только не надо тухлых помидоров кидать раньше времени. Современный алгоритм “Вихрь Мерсенна“ обладает просто колоссальным периодом (2^19937)-1

Вот мне чего-то подсказывает что это намного перекрывает запросы в генерации даже нас. Угенироваться можно в смерть, прежде чем пойдет зацикливание.
      15 Marconi (2009-10-07, 12:44:21) 0

тем, что у них следующий символ жестко определен, и не может изменятся под влиянием внешних условий.
      16 Starling (2009-10-07, 13:20:54) 0

он будет определен только после (2^19937)-1
      17 Marconi (2009-10-07, 13:52:07) 0

не, я имею в виду не “повторен“, а то, что сам ряд жестко определяется алгоритмом.
есть начальные условия, есть алгоритм - все, ряд заранее определен.
нельзя повлиять на его формирование в процессе генерации.
      18 Starling (2009-10-07, 14:34:30) 0

если ряд заранее определен то его можно спрогнозировать :) давай я по генерирую, а ты попробуй :)

так же за уши можно притянуть и ГСЧ..что в неком горизонте событий ряд который выдаст ГСЧ определен и ничто уже не сможет повлиять :)
      19 Marconi (2009-10-07, 19:37:47) 0

мих, лучшие ПГСЧ - работают по таблицам.
в память загнана достаточно длинная таблица случайных чисел.
И она или является опорной, или прямо она и выдается.
речь не о том, что можно или нет ее прогнозировать.

а о том, что в ячейках по адресу 1, 2, 3 и так далее размещены совершенно конкретные, заранее определеныне значения.

кои берет какой-то определнынй алгоритм.
и все.

при повторении начальных условий - ряд будет даже не “похожим“, а именно тем же самым.

ну пусти каокй-нть прогарммный генератор, и инициализируй его одним и тем же значением.

потом открути время на компе назад - и повтори операцию.
и поищи разницу между рядами.
      20 Starling (2009-10-07, 20:28:33) 0

Я хочу сказать, что для того, чтоыб получить истинно случайные последовательности, тебе придется встроенынй ПГСЧ для каждого числа - перезапускать.
По какому-то событию.
Например, по нажатию клавиши или еще чему-то.

А это и будет ввод в него данных.
Смысл?

---
А если егоп ерезапускать, скажем, по таймеру, то, открутив время на девайсе назад и начав запускать по тем же временынм меткам - ты получишь точно тот же самый ряд.

Ну, в “обычных“ алгоритмах.
В усложненных - на него будет наложена еще какая-то функция..
Но - Функция! Жестко определенный алгоритм!
      21 Starling (2009-10-13, 12:18:15) 0

Ответить:

Подпись:

Если вы Гость, то введите данный код подтверждения:

открыть новую тему

--Техническая Группа Исследований и Разработок ТЕГИР