Comments 12
Условие независимости источников — на самом деле очень сильное. И если бы вы правильно сформулировали это условие — доказательство вашего тезиса ("при правильном подходе качество имеющегося ГСЧ невозможно ухудшить") было бы тривиальным.
Но на практике, увы, это условие трудно гарантировать "в лоб", поэтому используют хитрые методы накопления энтропии (алгоритм Ярроу, вроде терпимо описан в википедии).
С практической точки зрения X и Y можно считать независимыми, если гипотетический взлом X (когда вероятность gx становится равна 1) не увеличивает злоумышленнику gy. Зависимость между X и Y может быть (кто-то из древних говорил, что все явления в нашем грешном мире взаимосвязаны), но она может быть невычислимой.
Например, некоторая зависимость между буквами, которые ввёл пользователь, и временем, которое он на это затратил, конечно, есть. Но начиная с сотых долей секунды она уже примерно никакая. Работают факторы, которые в самих введённых буквах уже никак не отражены.
Можно… Но это ещё более сильное требование: у вас ведь ГПСЧ, т.е. его выход не истинно случаен. К примеру, если у нас истинно случаен (с какой-то плотностью распределения) seed, можно (но дорого) посчитать плотность распределения первого псевдослучайного числа, потом второго…
Если подмешиваем случайные числа в процессе — всё становится ещё сложнее, но всё ещё не факт, что никто не выявит закономерность, которую можно использовать.
В общем, криптографические хэши, используемые в Ярроу или Fortuna, позволяют с этими закономерностями бороться.
Про подмешивание в процессе данных внешнего источника думал, но даже выкрутив паранойю на максималку, для данного конкретного случая смысла в этом разглядеть не удалось. Нереализуемость обратного расчёта хеш-функции — достаточно сильный аргумент в пользу того, чтобы дальше дурака не валять.
То есть gr может быть больше gx только тогда, когда угадывание основной последовательности хуже монетки. Тогда, когда наш предсказатель занят сознательным саботажем.
Если ваши рассуждения верны (не проверял), то угадывающий их может повторить, и "сознательный саботаж" на глазах превратится в повышающий вероятность угадывания алгоритм.
а). Добыть где-то угадывателя-саботажника, который всё правильно знает, но инвертирует выдачу.
б). Познать предательскую сущность саботажника.
После этого, конечно, взломщик инвертирует выдачу обратно и получает хороший прогноз.
Вообще, ситуация с тем, как при помощи монетки можно повышать качество прогноза, получается забавная. Предположим, есть секта, каждый год прогнозирующая вторжение инопланетян (или конец света, или технологическую сингулярность, или ещё что такое). Мы не знаем, вторгнутся ли инопланетяне. Если мы будем верить, мы обманемся в 100% случаев, а если будем XORить из прогноз с результатом бросания монетки, мы обманемся всего в 50% случаев. Профит :))
А чем этот вариант лучше, чем экстракторы энтропии, в частности универсальные хеш-функции (Leftover Hash Lemma)?
Идея с циклическим хешом (правда, в несколько другом варианте) уже имеет реальное воплощение в методических рекомендациях ТК 26 (Р 1323565.1.006-2017 «Информационная технология. Криптографическая защита информации. Механизмы выработки псевдослучайных последовательностей»). Но там, на мой взгляд, гамма будет вырабатываться побыстрее, не уступая в стойкости.
Вопрос в следующем. При генерировании последовательности случайных чисел часто наблюдается скопления значений. Что то типа «000011011110100001100001100001». Можно ли как то увеличить распределённость значений «01010110010100110101101010011001» не затрачивая много машинного времени на дополнительные проверки.
Вот здесь задают примерно такой же вопрос на практике www.flasher.ru/forum/showthread.php?t=215652
Поможет ли тут программные генераторы псевдослучаных чисел?
Увеличиваем случайность того, что и так [наверно] [почти] случайно