'''Diehard''' — это название «тестовой батареи» (также: «набор тестов» или «диапазон тестов») для проверки случайности заданной строки символов, например цифр и/или букв. из байтов.
Английское слово «diehard» имеет несколько значений, и в качестве прилагательного его, возможно, лучше всего перевести как «неутомимый».Entry [https://de.pons.com/%C3%BCberstellung?q = diehard&l=deen&in=&lf=de diehard] в словаре Pons-Verlag|PONS, по состоянию на 8 марта 2024 г.
== Генерация случайных последовательностей ==
В течение нескольких десятилетий, начиная с 1960-х годов, американский математик и ученый-компьютерщик Джордж Марсалья (1924–2011) очень интересовался феноменом «случайности», в частности генерацией максимально случайных чисел («случайные числа»). ) или случайные последовательности букв («случайные тексты»). ), поскольку они нужны, например, в криптологии, и задал себе вопрос, как можно измерить «случайность».
Уже было известно, что генерировать «хорошие» случайные последовательности с помощью алгоритмов далеко не тривиально. «Хорошие» здесь относятся к строкам, которые невозможно отличить от «реальных» случайных последовательностей, т. е. которые не обнаруживают никаких закономерностей и чьи статистические параметры, такие как среднее значение или дисперсия (стохастичность), не показывают никаких отклонений. Это называется псевдослучайным.
Существует ряд генераторов случайных чисел, которые могут генерировать более или менее «хорошие» случайные последовательности, например псевдослучайные последовательности для тестовых сигналов, которые могут быть «достаточно» случайными для специальных целей. Однако в конечном итоге это обычно детерминизм (алгоритм) | детерминированные строки символов, поскольку они вычисляются с использованием определенных математических правил. Поэтому их называют генераторами случайных чисел#детерминированными генераторами случайных чисел|генераторами псевдослучайных чисел.
Для криптографически безопасных генераторов случайных чисел, которые предназначены для генерации «настолько реальной» случайности, то обычно используются генераторы непредсказуемых случайных чисел, недетерминированные генераторы случайных чисел, недетерминированные генераторы случайных чисел, физические генераторы случайных чисел, например шума. генераторы. Иногда также используются человеческие действия или реакции, например, движения компьютерной мыши или время в секундах#Единицы измерения, связанные с секундами|Миллисекунды между нажатиями клавиш, чтобы получить случайные значения. Однако оказывается, что эти события на самом деле не случайны, а лишь квазислучайны. Следовательно, генерируемые таким образом случайные числа также имеют более или менее хорошее качество, например, они обычно распределяются неравномерно. С помощью своей батареи тестов Марсалья смог показать, что даже случайные числа, генерируемые с помощью, например, генераторов физического шума, не проходят все тесты, наоборот: «Они проваливают многие тесты в DIEHARD» (
Поэтому Марсалья дал недвусмысленную рекомендацию о том, что для генерации «хороших» случайных последовательностей лучше всего использовать несколько методов — как можно более разных — а затем объединять их результаты друг с другом с помощью микшеров (криптологии). Он исходит из принципа, что результат комбинации двух или более случайных последовательностей никогда не бывает менее случайным, чем каждая из них, что ему удалось доказать эмпирически.Джордж Марсалья: «Инструкция по использованию DIEHARD – батареи тесты на случайность». Diehard.doc, 7 января 1997 г., стр. 3 (на английском языке).
== Измерение случайности ==
Интересно, что, как и генерирование случайности, проверка на случайность далеко не тривиальна. Никто не знает простого метода, позволяющего надежно определить, является ли данная строка действительно случайной или нет. Однако существуют различные статистические параметры, которые можно проверить и которые служат мерой «качества случайности».
=== Пример означает ===
Очень простой и весьма полезный тест на случайность — вычисление среднего значения. Например, вы можете использовать его для проверки качества игральных костей. Идеальная игральная кость должна выдавать все числа от 1 до 6 одинаково часто. Если бросить тысячу раз и сложить все результаты, то в сумме должно получиться около 3500, так как в среднем за шесть бросков 1+2+3+4+5+6 = 21, то есть в среднем 21 за бросок /6  Генерируется ;= 3,5. Большая разница в результате, например 4000, сделает кости подозрительными. И наоборот, идеальное среднее не будет гарантией идеального кубика. Например, на сломанной игральной кости очень часто могут выпадать числа 1 и 6, и эти два числа могут выпадать одинаковое количество раз, но редко или никогда — другие числа. Даже тогда среднее значение будет 3,5. Это значит, что тест на среднее не выявит такой дефектный куб.
=== Пример равномерного распределения ===
Альтернативным и столь же простым тестом может быть проверка равномерного распределения. Это позволит немедленно обнаружить вышеописанный дефектный куб. Другой «фиктивный куб», реализованный здесь с помощью алгоритма, который всегда генерирует последовательность 1, 2, 3, 4, 5, 6 одну за другой, блестяще прошел бы тест на равномерное распределение, а также тест на среднее значение. Тем не менее такая последовательность, конечно, была бы отнюдь не случайной, а весьма детерминированной, т. е. совершенно бесполезной.
== Тестовая батарея ==
Как оказывается, ни одного теста недостаточно, чтобы проверить «настоящую» случайность строки. Подобно батарее (военной) в армии, в которой для достижения максимально возможного эффекта используется несколько пушек, у Марсальи возникла идея использовать «набор тестов», то есть набор тестов для измерения или оценить случайность. Для этой цели он ввел термин «тестовая батарея». Впервые в 1995 году он опубликовал свою «Непреклонную батарею тестов случайности».
Ниже кратко описаны несгибаемые тесты, первоначально предложенные Джорджем Марсальей в 1990-х годах. Подробности можно найти в его текстовом файле (см. также: «test.txt» в «Diehard.zip» в разделе #Weblinks|Weblinks).
=== Интервалы между днями рождения ===
Название основано на парадоксе дня рождения. В зависимости от проверяемой последовательности тест выбирает случайные точки в большом интервале (математика)|интервале, аналогичном дням рождения в течение года. Для этого из последовательности систематически выбираются разные конкретные биты и интерпретируются как времена. Интервалы между моментами времени (днями рождения) должны асимптотически соответствовать распределению Пуассона.
=== Перекрывающиеся перестановки ===
=== Ранги матриц 31×31 («Тест двоичного ранга») ===
Для этого из проверяемой последовательности систематически берутся отдельные биты и заполняется матрица (математика)|матрица размером 31×31 дуальная система|двоичная. Затем определяется ранг (математический) матрицы, который теоретически может находиться в диапазоне от 0 до 31, хотя ранги ниже 28 должны встречаться сравнительно редко. Результаты 40 000 испытаний сравниваются с ожидаемым значением с помощью теста хи-квадрат.
=== Ранги матриц 32×32 ===
Этот тест аналогичен предыдущему, но здесь с матрицами размера 32х32.
=== Ранги матриц 6×8 ===
Здесь шесть байтов, то есть 6×8 бит, берутся из последовательности и записываются в матрицу. Здесь также определяются ранги матриц, при этом ранги меньше 4 должны встречаться очень редко.
=== Битовая последовательность («Тест битового потока») ===
Случайная последовательность рассматривается как перекрывающиеся биты, а «слово» (состоящее из нулей и единиц) формируется из 20 последовательных битов. Проверяется появление всех мыслимых 220, т.е. 1 048 576 возможных «слов», и подсчитывается невхождение именно слов. В идеале они должны быть нормально распределены.
=== Тесты на обезьянах ===
В основе лежит теорема о бесконечной обезьяне, которая гласит, что обезьяна, которая беспорядочно печатает на пишущей машинке бесконечное количество времени, в конечном итоге напишет любую книгу.
=== Перекрывающиеся пары ===
Здесь десять бит берутся из последовательности и интерпретируются как «буква» из «алфавита (криптологии)|алфавита» с 210, т.е. 1024 возможными буквами. Две такие буквы в паре образуют «слово». Таким образом, в общей сложности одно за другим систематически формируется 221, что равно 2 097 152 словам. Затем проверяется, сколько слов не встретилось ни разу.
=== Перекрывающиеся четверки ===
Вместо использования пар букв, то есть слов длиной два, то же самое делается со словами длиной четыре, то есть кортежей|четверок букв.
=== Перекрывающиеся ДНК ===
В-третьих, два бита берутся из последовательности и интерпретируются как дезоксирибонуклеиновая кислота | строительный блок ДНК — аденин (А), гуанин (G), тимин (Т) или цитозин (С). Вы также можете произнести букву алфавита, состоящего всего из четырех букв. Каждый из двадцати битов теперь можно понимать как слово, состоящее из десяти таких букв. Всего возможно 410 различных слов, статистическое распределение которых проверяется тестом.
=== Подсчитайте единицы для последовательности байтов («Count-The-1s») ===
Каждый байт последовательности проверяется один за другим. В каждом байте может встречаться от нуля до восьми двоичных единиц, причем эти девять случаев имеют разную частоту (1, 8, 28, 56, 70, 56, 28, 8, 1). Для крайних случаев (ноль и восемь единиц) существует только одна возможность; однако для четырех есть 70 возможностей. Критерий хи-квадрат используется для проверки того, соответствует ли ожидаемое значение.
=== Подсчитайте единицы для специальных байтов ===
В 32-битном слове данных выбираются восемь битов и подсчитывается их количество. Отдельные результаты подсчета затем преобразуются в буквы: от нуля до двух единиц составляют букву A, три — B, четыре — C, пять — D и шесть-восемь единиц — E. В результате получаются слова, состоящие из пять букв с разной вероятностью появления букв: 37, 56, 70, 56 и 37 из 256 случаев. Частота появления всех слов проверяется по сравнению с отдельными ожидаемыми значениями.
=== Тест на парковке («Тест на парковке») ===
Круглый объект («автомобиль») размещается в любой точке квадратного поля («стоянки») размером 100х100, местоположение которого (координатная плоскость|координата x-y) определяется значениями последовательности. Если место еще свободно и можно сделать это без перекрытия («столкновения») с уже размещенными объектами, то количество уже успешно припаркованных автомобилей увеличивается на единицу. Здесь проверяется количество успехов по сравнению с количеством попыток, которое можно точно предсказать для совершенно случайных размещений. О качестве случайной последовательности можно судить по отклонению числа в эксперименте.
=== Тест минимального расстояния («Тест минимального расстояния») ===
В зависимости от последовательности внутри квадрата с длиной стороны 10 000 выбирается множество точек со случайными координатами x-y, всего 8 000 точек. Теперь вычисляются расстояния между всеми парами точек и считается минимальное расстояние. Этот эксперимент повторяется сто раз и отклонения от ожидаемого значения рассчитываются как критерий качества случайной последовательности.
=== Тест сферы («Тест 3D сфер») ===
Внутри куба (геометрии) с длиной ребра 1000 на основе последовательности выбираются 4000 местоположений (координаты x-y-z). Вокруг каждой локации в качестве центра размещается сфера, радиус которой выбран настолько большим, что он едва касается ближайшей точки. Радиус наименьшего из всех шаров должен быть 120·\pi/3, если последовательность совершенно случайна. Отклонения указывают на несовершенство последовательности.
=== Тест на сжатие («Тест на сжатие») ===
Это предполагает использование специальной функции программирования, которая округляет любое действительное число до следующего большего целого числа. 32-битная последовательность считается действительным числом от нуля до единицы, т.е. от 0 до 0,999... («плавающее»). Это число умножается на 231 и получается 2 147 483 648. Если произведение не является целым числом, оно округляется до ближайшего по величине целого числа («потолок»). Если это не единица, то результат еще раз умножается на исходное действительное число. Этот процесс повторяется до тех пор, пока не будет получен один. Критерием этого теста на сжатие является количество необходимых повторений.[https://mumble.net/~campbell/2014/04/28 ... ndom-float ''Равномерные случайные числа с плавающей запятой''], с апреля 28 г. 2014 г., по состоянию на 8 марта 2024 г. (на английском языке).
Краш-тест проводится 100 000 раз. Это должно привести к определенному распределению чисел критериев.
=== Перекрывающиеся суммы («Тест перекрывающихся сумм») ===
Здесь также битовые последовательности интерпретируются как действительные числа, лежащие в интервале (математика)|интервале между нулем и меньше единицы, т.е. [0,1). Сотни полученных таким образом действительных чисел суммируются. Затем первое сложение удаляется и добавляется сотое сложение. И т.д. Для суммовых последовательностей должны получиться характерные средние значения и дисперсии.
=== Запускает тест ===
Опять же, битовые последовательности рассматриваются как действительные числа от нуля до единицы. Проверяются длины встречающихся возрастающих или убывающих числовых значений, которые соответствуют определенному статистическому распределению в случае идеальных случайных чисел.
=== Тест на кости ===
Используя проверяемую последовательность чисел, разыгрывается 200 000 игр Craps|Craps. Подсчитывается количество бросков за игру и количество побед. Для идеальных случайных чисел оба должны соответствовать определенному распределению.
== Примечание ==
Марсалья сделал важное примечание: «Так что имейте в виду, что «p случается».Джордж Марсалья: сноска «ПРИМЕЧАНИЕ» в конце его вспомогательного файла «test.txt» для «DIEHARD ». ; – батарея тестов случайности». 9 декабря 1995 г. (на английском языке). Здесь, возможно, просто переводится как: «Помните, что «случайность случается».» Он указывает, что тест — это один Даже индивидуальный результат Последовательность действительно превосходного генератора случайных чисел может иногда давать результат, далеко отклоняющийся от ожидаемого значения. Однако это не доказательство его якобы плохого качества, а просто совпадение. Даже в рулетке один и тот же цвет может появляться несколько раз подряд (см. также: Ошибка обратного игрока). Это не невозможно, а основано на том, что французский математик Жозеф Бертран (1822-1900) однажды лаконично сформулировал: «Случайность не имеет памяти».
* * [https://webhome.phy.duke.edu/~rgb/General/dieharder.php «Страница общих инструментов Роберта Г. Брауна»] содержит «программу Dieharder» (на английском языке).
* [https://csrc.nist.gov/projects/random-bit-generation ''Генерация случайных битов.''] Руководства и рекомендации по генерации случайных чисел от Национального института стандартов и технологий|NIST (на английском языке).< бр />
Категория:случайная величина
Категория:Генератор псевдослучайных чисел
Категория: Криптологический метод
Подробнее: https://de.wikipedia.org/wiki/Diehard