Корреляционный анализ

Материал из Национальной библиотеки им. Н. Э. Баумана
Последнее изменение этой страницы: 14:12, 12 июня 2016.

Общие сведения

Корреляционный анализ - метод, позволяющий обнаружить зависимость между несколькими случайными величинами.

Допустим, проводится независимое измерение различных параметров у одного типа объектов. Из этих данных можно получить качественно новую информацию - о взаимосвязи этих параметров.

Статистическая ошибка

При корреляционном анализе могут возникать ошибки первого и второго рода.

TemplateDifinitionIcon.svg Определение «Определение - oшибка первого рода»
Ошибка первого рода возникает при пропуске истинного ключа. При возникновении ошибки первого рода задача дешифрования становится невыполнимой
TemplateDifinitionIcon.svg Определение «Определение - ошибка второго рода»
Ошибка второго рода возникает при принятии ложного ключа. При возникновении ошибки второго рода необходимо продолжить перебор

Корреляционный анализ на примере генератора Геффе

Как работает метод корреляционного анализа комбинирующих генераторов можно наиболее наглядно продемонстрировать на примере анализа генератора Геффе. Этот довольно простой пример позволяет понять основные идеи и принципы корреляционного криптоанализа, которые, будучи модифицированными должным образом, могут быть применены для анализа значительно более сложных поточных криптосистем. Главной целью криптоанализа генератора Геффе, как и любого другого генератора ключевого потока, является нахождение секретного ключа при условии, что известен отрезок ключевой последовательности, вырабатываемой этим генератором. Прежде всего отметим, что нахождение ключа генератора Геффе методом полного опробования всех ключей, требует перебора порядка вариантов, где – длины соответствующих регистров. Как указывалось выше, комбинирующей функцией генератора Геффе является функция Рассмотрим следующую вероятностную модель работы генератора Геффе. Будем считать, что в каждый момент времени на входы функции подаются независимые случайные величины каждая из которых принимает значения 0 и 1 с равной вероятностью. Тогда величина является случайной величиной, причем В то же время для всех при условии, что величина меньше длины периода выходной последовательности LFSR-1 и, соответственно, LFSR-3. Сделанные предположения весьма точно отражают свойство псевдослучайности, которым обладают выходные последовательности линейных регистров сдвига с обратной связью.

В этих предположениях можно попытаться определять начальные заполнения каждого из регистров по отдельности, независимо друг от друга. На первом этапе опробуем все варианты начального заполнения первого регистра. Для каждого из этих вариантов подсчитываем относительную частоту совпадения -го знака выходной последовательности, вырабатываемой этим регистром при данном начальном заполнении, со знаком известной выходной последовательности генератора. Если частота совпадения меньше не-которой величины то соответствующее начальное заполнение отбраковывается, если больше – заносится в список возможных вариантов. Выбор границы осуществляется известными статистическими методами и определяется указанными выше значениями вероятностей совпадения знаков последовательностей, длиной известной выходной последовательности и выбранными значениями ошибок первого и второго рода. Детали могут быть найдены в любой книге по методам математической статистики. Начальное заполнение третьего регистра сдвига определяется аналогичным образом. Начальное заполнение второго регистра определяется из следующих соображений. Если и – истинные выходные последовательности первого и третьего регистров, выходной знак второго регистра определен однозначно для каждого момента времени для которого соответствующие знаки и – не совпадают. Тогда отбраковка ложных вариантов начального заполнения второго регистра происходит одновременно с отбраковкой ложных вариантов начальных заполнений первого и третьего регистров, не отбракованных на первом этапе.

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

Оценка сложности атаки

Для атаки на регистр необходимо перебрать заполнений, для атаки на регистр необходимо перебрать заполнений.

Функция

Таким образом, если определился.

Общая сложность атаки

Корреляционная иммуность

Функция называется корреляционно-иммунной, если при всех .

Другими словами, значение функции совпадает со значением аргумента функции с вероятностью 1/2.