Как стать автором
Обновить

Комментарии 12

Условие независимости источников — на самом деле очень сильное. И если бы вы правильно сформулировали это условие — доказательство вашего тезиса ("при правильном подходе качество имеющегося ГСЧ невозможно ухудшить") было бы тривиальным.


Но на практике, увы, это условие трудно гарантировать "в лоб", поэтому используют хитрые методы накопления энтропии (алгоритм Ярроу, вроде терпимо описан в википедии).

В принципе, вполне можно пользоваться имеющимся в теории вероятностей понятием «независимые случайные величины».
С практической точки зрения X и Y можно считать независимыми, если гипотетический взлом X (когда вероятность gx становится равна 1) не увеличивает злоумышленнику gy. Зависимость между X и Y может быть (кто-то из древних говорил, что все явления в нашем грешном мире взаимосвязаны), но она может быть невычислимой.

Например, некоторая зависимость между буквами, которые ввёл пользователь, и временем, которое он на это затратил, конечно, есть. Но начиная с сотых долей секунды она уже примерно никакая. Работают факторы, которые в самих введённых буквах уже никак не отражены.

Можно… Но это ещё более сильное требование: у вас ведь ГПСЧ, т.е. его выход не истинно случаен. К примеру, если у нас истинно случаен (с какой-то плотностью распределения) seed, можно (но дорого) посчитать плотность распределения первого псевдослучайного числа, потом второго…
Если подмешиваем случайные числа в процессе — всё становится ещё сложнее, но всё ещё не факт, что никто не выявит закономерность, которую можно использовать.


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

Подсчёт плотностей распределения выдаваемой моим ГПСЧ последовательности ничего интересного не показывает. Ну то есть картинка в целом соответствует тому, что даёт SystemRandom. Специально поэкспериментировал. Есть программка, которая оценивает рандомность рандома по нескольким критериям.

Про подмешивание в процессе данных внешнего источника думал, но даже выкрутив паранойю на максималку, для данного конкретного случая смысла в этом разглядеть не удалось. Нереализуемость обратного расчёта хеш-функции — достаточно сильный аргумент в пользу того, чтобы дальше дурака не валять.
То есть gr может быть больше gx только тогда, когда угадывание основной последовательности хуже монетки. Тогда, когда наш предсказатель занят сознательным саботажем.

Если ваши рассуждения верны (не проверял), то угадывающий их может повторить, и "сознательный саботаж" на глазах превратится в повышающий вероятность угадывания алгоритм.

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

Вообще, ситуация с тем, как при помощи монетки можно повышать качество прогноза, получается забавная. Предположим, есть секта, каждый год прогнозирующая вторжение инопланетян (или конец света, или технологическую сингулярность, или ещё что такое). Мы не знаем, вторгнутся ли инопланетяне. Если мы будем верить, мы обманемся в 100% случаев, а если будем XORить из прогноз с результатом бросания монетки, мы обманемся всего в 50% случаев. Профит :))
Описываемое Вами свойство при суммировании доказано в книге Харина «Математические методы криптологии» (Свойство 6.1.5, воспроизводимость при суммировании). Но там накладывается требование на одну из последовательностей — она должна быть равномерно распределенной случайной последовательностью. Я так понимаю, в данной статье предполагается, что системный ГСЧ таковым и является.

А чем этот вариант лучше, чем экстракторы энтропии, в частности универсальные хеш-функции (Leftover Hash Lemma)?

Идея с циклическим хешом (правда, в несколько другом варианте) уже имеет реальное воплощение в методических рекомендациях ТК 26 (Р 1323565.1.006-2017 «Информационная технология. Криптографическая защита информации. Механизмы выработки псевдослучайных последовательностей»). Но там, на мой взгляд, гамма будет вырабатываться побыстрее, не уступая в стойкости.
Спасибо за наводки. Я, собственно и не претендовал на супер-пупер новизну. Для технических решений, слава богу, нет требований новизны.
Не уверен сильно ли в тему будет тут такой вопрос, так как не сильно владею темой.
Вопрос в следующем. При генерировании последовательности случайных чисел часто наблюдается скопления значений. Что то типа «000011011110100001100001100001». Можно ли как то увеличить распределённость значений «01010110010100110101101010011001» не затрачивая много машинного времени на дополнительные проверки.
Вот здесь задают примерно такой же вопрос на практике www.flasher.ru/forum/showthread.php?t=215652
Поможет ли тут программные генераторы псевдослучаных чисел?

Можно, но ценой ухудшения рандомности. Я бы предложил составить словарик из байт, в которых нет, например, пяти нулей или единиц подряд, и из этого ограниченного набора рандомно выбирать.

Зарегистрируйтесь на Хабре , чтобы оставить комментарий

Публикации

Истории