Криптография > Псевдослучайные последовательности > Предсказуемость гаммы
 
 

Предсказуемость гаммы

Вторая проблема состоит в следующем: на основании чего можно сделать заключение, что гамма конкретного генератора является непредсказуемой? Пока в мире нет еще универсальных и практически проверяемых критериев, позволяющих утверждать это. Неизвестна и общая теория криптоанализа, которая могла бы быть применена для такого доказательства, за исключением все возрастающего количества конкретных способов анализа, выработанных для различных практических целей. Интуитивно случайность воспринимается как непредсказуемость. Чтобы гамма считалось случайной, как минимум необходимо, чтобы ее период был очень большим, а различные комбинации бит определенной длины равномерно распределялись по всей ее длине. Итак, второе требование к ряду заключается в подтверждаемом статистически подобии его свойств настоящей случайной выборки. Каждый порядок элементов гаммы должен быть так же случаен, как и любой другой. Это требование статистики можно толковать и как сложность закона формирования ряда псевдослучайных чисел. Практически, если по достаточно длинной реализации этот закон вскрыть не удается ни на статистическом уровне, ни аналитически, то этим нужно удовлетвориться. Чем длиннее требуемая длина ряда, тем жестче к нему требования. Теперь подробнее расскажем, как вскрывались скрытые закономерности в последовательностях чисел. С древнейших времен люди наблюдали и изучали периодически повторяющиеся процессы, как фазы Луны, движения планет, чередования времен года, но не все такие цикличности выражены явно. Например, солнечные пятна, наблюдаемые невооруженным глазом с начала нашей эры и в телескопы с начала XVII века, дают пример скрытой периодичности в II лет, впервые обнаруженной Генрихом Швабе лишь в 1843 году. А вот среднегодовые температуры и изменение климата Земли связаны с циклами в 19 лет. Работы Винера и Хинчина поставили анализ периодичностей с головы на ноги. Ими предложено оценивать спектр случайных колебаний значений элементов гаммы как преобразование Фурье функции автокорреляции. При этом шумоподобному равномерному спектру гаммы без скрытых периодичностей соответствует автокорреляционная функция в виде одиночного выброса в нуле, то есть так называемая дельта-функция. Этот результат можно интерпретировать как непохожесть последовательности на себя при любом ее сдвиге.