Псевдослучайные последовательности

Лучшее, что может сделать компьютер - это генератор псевдослучайных последовательностей. Что это такое? Многие пытались дать его формальное определение, но мы уклонимся от этого. Псевдослучайная последовательность – это что-то, выглядящее как случайное. Период последовательности должен быть достаточно велик, поэтому конечная последовательность разумной длины – которая в действительности и используется – не периодична. Если вам нужен миллиард случайных бит, не пользуйтесь генератором последовательности, повторяющейся каждые шестнадцать тысяч бит. Эти относительно короткие непериодические подпоследовательности должны быть, насколько это возможно, неотличимы от случайных последовательностей. Например, в них должно быть примерно одинаковое количество единиц и нулей, около половины серий (последовательностей одинаковых бит) должны быть единичной длины, четверть - состоять из двух бит, восьмая часть - из трех, и т.д. Эти последовательности должны быть несжимаемы. Распределение длин серий для нулей и единиц должно быть одинаковым. Эти свойства могут быть измерены опытным путем и затем сравнены с ожидаемыми статистически с помощью статистики хи-квадрат. Для наших целей генератор последовательности считается псевдослучайным, если он обладает следующим свойством:

1. Он выглядит случайно. Это означает, что он проходит все тесты на случайность, которые нам удалось найти.

Множество усилий было затрачено на создание хороших псевдослучайных последовательностей на компьютере. Обсуждение генераторов в большом количестве можно найти в академической литературе вместе с различными тестами на случайность. Все эти генераторы периодичны (этого невозможно избежать), но, если их период 2²⁵⁶и выше, они могут быть использованы в самых серьезных приложениях.

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