Методы криптоанализа симметричных криптосистем 1 страница

По определению известного американского криптолога У. Фридмана «криптоанализ включает определение используемого языка, типа криптосистемы, ключа и исходного текста; обычно именно в этом порядке». Хотя определение криптоанализа было введено сравнительно недавно, первым известным письменным упоминанием о криптоанализе является «Книга о большом стремлении человека разгадать загадки древней письменности», написанная арабским учёным Абу Вакр бен Али бен Вахшия ал-Набати в средние века. В настоящее время криптоанализ активно развивается, хотя единая математическая теория криптоанализа еще не разработана, и на рынке уже появились пакеты прикладных программ по криптоанализу. В частности, разработкой таких программных продуктов занимается американская фирма Access Data Recovery.

3.1. Задачи и принципы криптоанализа

Следует заметить сразу, что основная цель криптоанализа состоит не столько в получении скрываемой информации, а в оценке стойкости существующих и разрабатываемых криптосистем. Оценка стойкости криптосистем представляется в виде количества операций, необходимых для взлома криптосистемы или в виде времени, которое требуется для взлома.

Приведем основные принципы, которые были «выстраданы» криптологами [5,10]:

1. Принцип Керкхоффа. Только криптоаналитик может судить о криптостойкости системы.

2. Принцип Керкхоффа-Шеннона. Противник знает используемую криптосистему с точностью до ключевой информации.

3. Принцип Жеверже. Поверхностные усложнения криптосистемы могут быть иллюзорны, так как порождают ложные оценки ее криптостойкости.

4. При оценке криптостойкости необходимо учитывать возможные криптографические ошибки и другие нарушения дисциплины безопасности.

Из приведенных выше принципов следует, что основная задача криптоаналитика заключается в оценке ключевой информации, при условии, что сама используемая криптосистема известна. Алгоритм оценки ключевой информации называется криптоатакой. В зависимости от условий взаимодействия криптоаналитика с криптосистемой различают следующие основные типы криптоатак:

- криптоатака с использованием только криптограмм (А1);

- криптоатака с использованием открытых текстов и соответствующих им криптограмм (А2);

- криптоатака с использованием выбираемых криптоаналитиком открытых текстов и соответствующих им криптограмм (А3);

- криптоатака с использованием аппаратного воздействия на криптосистему (криптоатака по сторонним каналом) (А4).

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

В настоящее время разработано множество методов криптоанализа, реализующих криптоатаки типов А1-А3. В настоящей главе рассмотрим несколько этих типов криптоатак.

3.2. Метод полного перебора

Метод полного перебора или метод «грубой силы» (brute force attack) является простейшим методом криптоанализа, и несмотря на свой «солидный возраст» в настоящее время, в связи с интенсивных развитием компьютерной техники, находит достаточно широкое применение. Суть метода заключается в следующем:

1) на основе имеющейся криптограммы и соответствующего ей открытого текста составляется система уравнений относительно :

, , (3.1)

полным перебором всех возможных значений ключевого параметра находится некоторое множество решений ;

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

Если считать проверку одного варианта ключа в выражении (3.1) за одну операцию, то полный перебор ключей потребует операций. Пусть ключ в алгоритме шифрования выбирается случайно и равновероятно из множества . Тогда с вероятностью трудоемкость метода полного перебора равна 1. Это происходит в том случае, когда случайно выбран ключ, расположенный в нашем порядке на первом месте. Поэтому естественно в качестве оценки трудоемкости метода взять математическое ожидание числа шагов в переборе до попадания на использованный ключ. Пусть случайная величина - число опробований включительно до момента обнаружения использованного ключа. При случайные величины 1, если использованный ключ находиться в порядке на месте и 0 в противном случае. Тогда:

. (3.2)

Если считать, что все ключи расположены в установленном порядке, то процедуру равновероятного выбора ключа можно представить как равновероятный выбор числа в последовательности натуральных чисел . Тогда для любого . Подставляя полученное значение в (3.2) имеем:

. (3.3)

При больших можно приблизительно считать, что . Например, для криптосистемы DES , тогда средняя трудоемкость полного перебора . При использовании современных вычислительных систем, среднее время взлома шифра Цезаря составляет секунды, а шифра Вернама - лет.

Метод полного перебора допускает распараллеливание. Один из способов распараллеливания заключается в том, что множество натуральных чисел разбивается на непересекающиеся подмножества . Система из вычислительных машин перебирает ключи так, что -ая машина осуществляет перебор ключей из множества , . Система прекращает работу, если одна из вычислительных машин определила ключ. Например, если одна вычислительная машина опробует ключ за секунд, то для того чтобы найти ключ криптосистемы DES полным перебором за 24 часа требуется вычислительных машин.

3.3. Методы бесключевого чтения

При рассмотрении поточных криптосистем гаммирования были определены требования к гамме. Нарушение этих требований дает противнику возможность реализовать криптоатаку на криптосистему. Рассмотрим некоторые методы криптоанализа криптосистем гаммирования не требующие определения ключа [11].

Метод чтения в колонках реализует способ восстановления текста, зашифрованного неравновероятной гаммой. Суть метода состоит в следующем. Пусть есть вероятность использования знака в гамме, причем полагаем, что не все вероятности равны , где - длина гаммы. Без ущерба для общности положим , , . В -м такте шифрованию подверглась одна из следующих букв открытого текста, :

, , …, . (3.4)

Открытый текст может быть получен подбором -го знака в -й колонке табл. 3.1 (элементы таблицы рассматриваются по mod , где - мощность алфавита).

Таблица 3.1. Таблица дешифрования

		…		…
		…		…
	-1	…	-1	…	-1
…	…	…	…	…	…
		…		…

Знаки в каждой колонке упорядочены по вероятности их использования в открытом тексте. Это облегчает чтение в колонках, т.к. «читаемый текст» с повышенной вероятностью расположен в верхних строках таблицы. В случае, когда все >0, но при этом имеют разные значения при составлении таблицы необходимо исключить из рассмотрения наименее вероятных знаков гаммы. В этом случае существует ненулевая вероятность потери истинного решения, т.е. исходного открытого текста.

Применение данного метода тем успешнее, чем меньше высота колонок , характеризующая многозначность решения задачи. При близких к , чтение в колонках теряет смысл, т. к. табл. 3.1 может содержать большое количество осмысленных, но и взаимно противоречивых открытых текстов. Данный метод может быть использован и в случае, когда текст зашифрован периодической гаммой. Пусть дана криптограмма . Известен период ключевой последовательности . Сформируем две подпоследовательности исходной криптограммы:

Будем полагать, что открытыми текстами, подлежащими шифрованию, являются содержательные тексты с известными вероятностями букв алфавита , , где - номер буквы алфавита. Также будем считать, что на множестве задано равномерное распределение, т.е. ключом является реализация выборки объемом из равномерного распределения . Тогда вероятность того, что -я и ()-я буквы открытого текста были равны соответственно, и , при условии, что -я и ()-я буквы криптограммы равны соответственно, и определяется выражением:

. (3.5)

Так как в рассматриваемой криптосистеме множество ключей задано латинским квадратом, следовательно, используемый ключ однозначно определен любым переходом в этой замене. Если числитель (3.5) не равен нулю, то справедливо равенство:

. (3.6)

Для каждой пары и букв исходной криптограммы упорядочим в соответствии с убыванием полученных значения условных вероятностей (3.6) пары букв открытого текста и .

Построив такие колонки для каждого , в результате получаем таблицу (см. табл. 3.2), в которой верхние пары имеют большую условную вероятность, чем нижние.

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

Таблица 3.2. Таблица дешифрования

	…		…
	…		…
….	…		…	…

Период ключевой последовательности может быть определен с помощью методов Фридмана [1]. Рассмотрим эти методы. Основаны методы на введенном У. Фридманом понятии индекса совпадения. Индексом совпадения последовательности называется величина

, (3.7)

где , - некоторая последовательность; - частота встречаемости (число мест в тексте) - буквы в последовательности .

Индекс совпадения последовательности равен вероятности совпадения символов данной последовательности на случайно и равновероятно выбранных местах и , причем и , .

При

,

где - вероятность го символа из алфавита в содержательных текстах.

При случайном выборе последовательности индекс совпадения является случайной величиной, и представляет интерес подсчет его математического ожидания. Математическое ожидание индекса совпадения для открытых текстов определяется выражением:

. (3.8)

Если реализация представляет собой выборку из равномерного вероятностного распределения, то справедливо выражение:

. (3.9)

Для любой последовательности вероятность совпадения двух случайно и равновероятно выбранных букв последовательности приблизительно равна:

. (3.10)

Пусть - криптограмма, полученная в результате шифрования случайного текста при случайном и равновероятно выбранном ключе. Тогда математическое ожидание индекса совпадения для криптограммы равно:

. (3.11)

Для криптосистемы гаммирования с периодической гаммой, получаемого шифрованием открытого текста с помощью равновероятного выбора ключа из множества всех локально-периодических последовательностей периода d и справедливо:

(3.12)

При (т.е. ):

(3.13)

Первый метод Фридмана состоит в том, что вычисляется индекс совпадения для имеющейся криптограммы в соответствии с выражением (3.7) и затем его значение сравнивается с (3.13) при . При достаточной близости индекса совпадения к одному из значений (3.13), при некотором , предполагают, что период равен этому значению .

Первый метод Фридмана эффективен для , т.к. значение для фиксированного периода совпадает со значениями целого ряда различных периодов ключевой последовательности.

Второй метод Фридмана также основан на вычислении индекса совпадения. Суть второго метода Фридмана состоит в опробовании возможных периодов по следующей схеме. Из исходной криптограммы для предполагаемого периода ключевой последовательности выписывается подпоследовательностей:

(3.14)

Для каждой подпоследовательности подсчитывается ее индекс совпадения . Если все индексы совпадения в среднем близки к значению (среднее значение индекса совпадения случайных криптограмм, полученных с помощью гамм периода 1), то принимают величину за истинный период, в противном случае опробуется следующая величина периода. Второй метод Фридмана позволяет эффективно определять периоды .

Метод восстановления текстов, основанный на атаке с помощью вставки символа (insertion attack). Рассмотрим существо метода. Пусть открытый текст с помощью гаммы преобразуется в соответствии с уравнением шифрования:

, (3.15)

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

По двум криптограммам, начиная с момента вставки, можно определить и гамму и открытый текст:

, ;

, ;

, , ….

Все вычисления выполняются по mod . Момент вставки символа можно определить, сравнивая видоизмененную и оригинальную криптограммы. Если значение вставленного символа неизвестны, то можно реализовать подбор вариантов его значения. Для защиты от такого рода атак достаточно никогда не использовать одинаковые отрезки гаммы для повторного шифрования.

3.4. Методы криптоанализа с использованием теории статистических решений

Рассмотрим симметричную криптосистему, криптоаналитику априорно известно:

1) криптографическое преобразование с точностью до ключа ;

2) криптограмма длинной n.

Задача криптоаналитика состоит в оценке неизвестного параметра криптографического преобразования .

Допущения (предположения) [10]:

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

2) - является детерминированной неизвестной величиной.

Метод частотного криптоанализа базируется на реализации методов теории статистических решений, а именно, на методе максимального правдоподобия [10]. В соответствии с этим методом формируется функция правдоподобия:

, (3.16)

где - дискретное распределение крипто граммы Y в ситуации, когда значение ключа фиксировано:

Дата добавления: 2014-12-26