Купить статью

Генераторы случайных чисел порождают равномерное распределение чисел, причем между этими числами нет какой-либо зависимости, позволяющей предсказывать порождаемое число лучше, чем случайное угадывание. Такие генераторы применяются в различных задачах, например моделирование или обеспечение информационной безопасности. В качестве генераторов используются аппаратные устройства, преобразующие случайный физический процесс в поток данных. Другим типом генераторов являются программные, которые используют формулу или алгоритм для получения нового числа. Считается, что программные хоть и быстрее работают, но не обладают доказанным свойством случайности. Известен ряд случаев, когда в таких генераторах обнаруживались закономерности, что приводило к отказу от их использования. Для проверки генератора существуют наборы тестов. При успешном прохождении всех тестов генератор рекомендуют к использованию. Целью данной статьи является разработка алгоритма проверки битовых последовательностей на случайность. В настоящей работе предложен новый тест для генераторов случайных чисел, который может быть включен в общий набор статистических тестов, необходимых для проверки. В отличие от известных ранее тестов, базирующихся на энтропийном подходе, новый выявляет автокорреляцию сгенерированных данных. Показано, что предложенный алгоритм позволяет обнаружить отклонения от случайности у генераторов, которые ранее проходили известные статистические тесты. В ходе экспериментов тестировались выходные последовательности шифра, хэш-функции и некоторых генераторов псевдослучайных чисел. Как показал анализ результатов тестирования, некоторые генераторы имеют автокорреляцию в порождаемых данных. В данной работе не делается заявлений относительно уязвимостей шифров, а только ранжируются генераторы относительно друг друга. Идея теста заключается в том, что у любого генератора существует период, когда в последовательности порождены все числа из генерируемого множества (алфавита). В идеальном случае период будет приближаться к размеру алфавита или будет незначительно больше. Однако если некоторые символы повторяются чаще, то период станет значимо возрастать. Другими словами, удлинение периода может свидетельствовать либо об отклонении от равномерного распределения, либо о наличии автокорреляции в порождаемых данных. Последнее является областью интереса авторов статьи. В ходе исследования использовались элементы теории вероятностей и математической статистики. Эксперименты проведены на большом объеме сгенерированной последовательности чисел.