Комментарии 25
Берем современный быстрый потоковый шифр (xchacha20), инициализируем его чем нам нравится и получаем околобесконечный ГПСЧ. Не надо изобретать велосипеды с хэшами
Не случайно в статье употреблена приставка псевдослучайных чисел. Если назову число 10, кто скажет, что оно не случайное? Но если предложу последовательность 10,20,30,40 — мне скажут, что прослеживается закономерность. Вспоминаются методы возить мышкой по квадратику или ответить на вопрос, где миллисекунды скорости ответа будут считаться случайным числом. Алгоритмы криптографии требуют случайных чисел, но в реальности их не получить. С этим приходится мириться.
в реальности их не получить
Это почему? https://en.wikipedia.org/wiki/Hardware_random_number_generator
Потому, что по указанной ссылке (для простоты переключил на.ру) :
Эти процессы в теории абсолютно непредсказуемы, на практике же получаемые из них случайные числа проверяются с помощью специальных статистических тестов.
Читаем про тесты:
Зная вероятностные свойства истинно случайной последовательности, можно на их основе проверять гипотезу о том, насколько сгенерированная последовательность похожа на случайную. Для этого для каждого теста подбирается подходящая статистика, вычисляется её значения для идеальной и сгенерированной последовательности. Если разность этих значений превышает некоторое критическое значение, установленное заранее, то последовательность считается неслучайной. Для «хороших» последовательностей вероятность такого события крайне мала (допустим ~0,001 и обозначим её α). Однако, существует вероятность того, что «плохая» последовательность удовлетворит критерию и будет сделан вывод о её случайности (обозначим вероятность такого события β). На практике значения длины последовательности n, α и β связаны, задаётся α и подбирается n такое, чтобы минимизировать β.
Речь про гипотезу! Но для практики нет ничего лучше — поэтому используем это.
для простоты переключил на.ру
Очень зря.
Речь про гипотезу! Но для практики нет ничего лучше — поэтому используем это.
А это вообще не про то.
Очень зря.
Почему зря? Где важные расхождения? Мы на каком языке здесь говорим?
А это вообще не про то.
Как не про то? А про что?
Потому что тексты не эквиваленты, и русский вариант запутывает, на что Вы и наступили. Случайность некоторых хардварных генераторов гарантируется принципиальной стохастичностью нижележащих процессов (ну, по крайней мере, насколько мы сейчас это знаем), то есть это не гипотеза, которая подтверждается статтестами, а прямое следствие теории. Но для ряда (или всех, я не сильно глубоко копал) необходимо каким-либо способом убеждаться, что они всё ещё работают, а не отвечают всегда "42", т.к. датчики имеют свойство деградировать со временем (или, например, какой-нибудь условный белый шум на какой-то частоте не оказался ВНЕЗАПНО радио Маяк 8)) ). Плюс есть ещё ряд проблем, но, тем не менее, получить случайные числа можно, чем и пользуются, в общем-то.
ИМХО по-сути совпадают. В заключении en-статьи читаем:
Correlation of bias in the inputs to a generator design with other parameters (e.g., internal temperature, bus voltage) might be additionally useful as a further check. Unfortunately, with currently available (and foreseen) tests, passing such tests is not enough to be sure the output sequences are random.
Я выделил в цитате. Известны теор проблемы P ?= NP и т.д. Но на практике работаем, как можем. ИМХО это нужно отметить в статье.
Это другой момент, который я упомянул (в части, что характеристики хардварных генераторов могут требовать той или иной проверки, что они всё ещё ожидаемо работают, грубо говоря, что гномик внутри всё ещё живой и подкидывает монетку 8))). Это не значит, что нет возможности получить истинно случайную последовательность или что существование такой последовательности только гипотеза. То, что Вы выделили, говорит лишь о том, что нет абсолютно достоверного теста, случайная ли последовательность или нет.
Если назову число 10, кто скажет, что оно не случайное?
"Почему на иллюстрациях к генерации через хеш, которые якобы не имеют паттерна, четко видно квадратную сетку без углов, как и на прочих иллюстрациях к хешам?"
Маленький апдейт. Сначала хотел убрать вопрос, ведь сетка четко видна только в статье, где иллюстрации уменьшены. Но нет. Это всегда там было, просто масштабирование сделало это видимым.
Тут скорее всего проблема сжатия в процессе загрузки. Сейчас полез проверить в оригинал. Прикрепляю полноразмерное изображение результата работы MD5. На случай, если и тут сожмётся - прикрепляю ссылку на диск, где уж точно должно быть всё нормально https://disk.yandex.ru/i/p6E4kK46Ih6z2w
А что теоретически лучше: один 64-битный хеш/генератор или два перемешивающихся 32-битных?
Отвечу вопросом на вопрос: "Лучше для какой задачи?"
Дело в том, что тут многое зависит от контекста, в котором ты будешь использовать этот генератор. Если бы разработчики нашли алгоритм, который удовлетворяет всем потребностям программиста, то был бы только он один. А так для разных задач используют различные алгоритмы. Самым лучшим способом ответить на этот вопрос как раз будет взять интересующие тебя алгоритмы и прогнать на некоей синтетической задаче с целью вычисления показателей работоспособности в рамках одинаковой задачи. И уже там, опираясь на полученные результаты принять решение.
Спасибо, порадовали, обстоятельно! Пожалуй, стоит проверить некоррелированность последовательностей в пространствах высших порядков, т.к. ЛКГ стремится распологать точки на гиперплоскостях (см. теорема Марсальи) - https://www.pnas.org/content/61/1/25
В .NET кроме Random (в котором в .NET 6 изменился алгоритм) есть еще и более стойкий RandomNumberGenerator и (теперь устаревший) RNGCryptoServiceProvider.
Разбор алгоритмов генерации псевдослучайных чисел