Критерии оценки криптографических алгоритмов
В криптографии понятие криптографическая стойкость (криптостойкость) традиционно определяется как устойчивость к попыткам дешифрования сообщений, т.е. количественная мера того, насколько легко криптоаналитик может вскрыть шифр, измеряемая минимальным количеством операций шифрования/расшифрования, необходимых для определения ключа (или открытого текста), при наилучшей из атак. Основное правило криптографии применительно к вопросу криптостойкости состоит в следующем: вскрытие шифра с целью прочесть закрытую информацию должно обойтись гораздо дороже (стоимость выражается в некоторых ресурсах – число микросхем для реализации атаки, объем памяти и т.д.), чем реальная стоимость информации.
Понятие криптостойкости тесно связано со сложностью криптоаналитической атаки на алгоритм шифрования и характеризуется с помощью трех величин [1, 2]:
- сложность по данным - количество перехваченных данных, необходимых для успешной криптоаналитической атаки на алгоритм шифрования.
- вычислительная сложность – количество операций, необходимое для успешной атаки на алгоритм шифрования.
- сложность по памяти - объем памяти, необходимый для успешной атаки.
Для оценки стойкости можно взять максимальную из этих величин или использовать оценку на основе обобщенного критерия.
Все шифры по криптографической стойкости делятся на совершенные (не имеющие более эффективных алгоритмов вскрытия, кроме метода полного перебора) и несовершенные (не обладающие абсолютной стойкостью), стойкость которых основывается на вычислительной сложности решения некоторой математической задачи. Для оценки вычислительной стойкости используется количество операций (w) некоторого типа, необходимых для дешифрования сообщения или определения ключа. Наиболее удобной операцией для получения оценок стойкости является цикл проверки одного ключа. Трудоемкость дешифрования зависит от характера и количества информации, имеющийся в распоряжении аналитика:
|
|
|
1. Анализ на основе только шифртекста - аналитик знает механизм шифрования и ему доступен только шифртекст размером n, что соответствует модели внешнего нарушителя, который имеет физический доступ к линии связи;
2. Анализ на основе заданного открытого текста - криптоаналитику известен шифртекст и та или иная доля исходной информации, а в частных случаях и соответствие между шифртекстом и исходным текстом, т.е. аналитик располагает зашифрованным сообщением размером n и соответствующим ему открытым текстом. Такая атака возможна пришифровании стандартных документов, подготавливаемых по стандартным формам, когда определенные блоки данных повторяются и известны;
|
|
|
3. Анализ на основе произвольно выбранного открытого текста - криптоаналитик может ввести специально подобранный им текст в шифрующее устройство и получить криптограмму, образованную под управлением секретного ключа, т.е. в распоряжении аналитика есть возможность получить результат зашифрования для произвольно выбранного им массива открытых данных размером n, что соответствует модели внутреннего нарушителя, когда в атаку на шифр вовлекаются лица, которые не знают секретного ключа, но в соответствии со своими служебными полномочиями имеют доступ к устройству шифрования;
4. Анализ на основе произвольно выбранного шифртекста - противник имеет возможность подставлять для дешифрования фиктивные шифртексты, которые выбираются специальным образом, чтобы по полученным на выходе дешифратора текстам он мог с минимальной трудоемкостью вычислить ключ шифрования, т.е. в распоряжении аналитика есть возможность получить результат расшифрования для произвольно выбранного им зашифрованного сообщения размером n, что соответствует доступу к устройству дешифрования;
5. Атака на основе адаптивных текстов – атакующий многократно подставляет тексты для шифрования (или дешифрования), причем каждую новую порцию данных выбирают в зависимости от полученного результата преобразования предыдущей порции.
|
|
|
Средний объем работы W(N), необходимый для определения ключа по криптограмме, состоящей из N букв, измеренный в элементарных операциях называется рабочей характеристикой шифра. Это значение берется как среднее по всем ключам и всем сообщениям с соответствующими им вероятностями [3, 4].
Нижние границы трудоемкости достигаются при некоторых конечных значениях параметра N, потому что при его неограниченном увеличении трудоемкость анализа будет стремиться к некоторому пределу, называемому достигнутой оценкой рабочей характеристики. Как отмечено в [4], для несовершенных шифров не существует способа получить точное значение трудоемкости анализа, все оценки базируются на проверках устойчивости шифров к известным на текущий момент видам криптоанализа, и нет гарантии, что в ближайшем или более отдаленном будущем не будут разработаны новые методы анализа, существенно ее снижающие. Поэтому стойкость несовершенных шифров обосновывается эмпирически как устойчивость к известным на сегодняшний день видам криптоанализа.
|
|
|
В настоящее время в криптоанализе выделяют следующие основные методы:
1. Полный перебор возможных ключей;
2. Частотный анализ;
3. Дифференциальный метод;
4. Линейный метод.
Полный перебор возможных ключей
При криптоанализе с известным исходным текстом, который является наиболее актуальным, единственным опубликованным применяемым методом остается полный перебор ключей. Основным недостатком данного метода является экспоненциальная зависимость времени криптоанализа от длины ключа, поэтому, из-за большой трудоемкости этот метод выбран в качестве верхней границы при оценке криптостойкости шифра - если задачу взлома шифра можно решить только методом полного перебора, реализация которого будет неприемлема по финансовым или временным соображением, то данный шифр считается стойким. Также этот метод используется для оценки эффективности других алгоритмов криптоанализа - все остальные методы должны обеспечивать значительно меньшую трудоемкость.
Существуют оптимизации этого метода, связанные с использованием словарных атак [1, 2]. Идея базируется на том, что отправитель сообщения предпочтет использовать легко запоминаемую ключевую последовательность в отличие от полностью случайной. Поэтому в первую очередь необходимо опробовать наиболее вероятные ключи (и их комбинации) из словаря, что может существенно сократить трудоемкость вскрытия шифра. Практические исследования показали высокую эффективность такого подхода.
Частотный анализ
Частотный анализ учитывает частотные характеристики текстов на реальных языках, обладающих большой избыточностью и наличием устойчивых частот сочетаний символов (k-грамм и словоформ языка). Принцип метода состоит в подсчете частот символов в криптограмме и сравнение с вычисленными частотами для модели открытого текста. Достоинством метода является возможность использования для шифров с различающимися алфавитами для открытого текста и криптограммы. Для построения математической модели открытого текста используется построение частотных характеристик открытых текстов, вычисленных с необходимой точностью при исследовании текстов достаточной длины.
Открытый текст рассматривается как реализация стационарного эргодического случайного процесса с дискретным временем и конечным числом состояний и модель представляет собой однородную цепь Маркова [3]. Более высокий порядок приближения соответствует более связному тексту, получаемому на выходе модели. Критерии распознавания строятся либо на основе стандартных методов различения статистических гипотез, либо на основе запретных k-грамм (некоторые редко встречающиеся k-граммы объявляются запретными и их присутствие в получаемом тексте означает получение "бессмысленной" последовательности знаков). При использовании специальных алфавитов (для нетекстовой информации) требуется построение новых формализованных критериев на открытый текст, учитывающих специфику формирования входной последовательности, что само по себе является сложной задачей, связанной с дополнительными исследованиями. Построение критериев для языка, характеризующегося отсутствием статистических зависимостей (равномерным распределением вероятностей появления символов), является практически неразрешимой задачей.
Дифференциальный метод криптоанализа
Дифференциальный криптоанализ (ДКА) - это попытка вскрытия секретного ключа блочных шифров, которые основаны на повторном применении криптографически слабой цифровой операции шифрования (раундовой функции) r раз. При анализе предполагается, что на каждом цикле используется свой подключ шифрования. ДКА может использовать как выбранные, так и известные открытые тексты. Успех таких попыток вскрытия r-циклического шифра зависит от существования дифференциалов (r-1)-го цикла, которые имеют большую вероятность. Идея метода состоит в поиске дифференциалов для последнего цикла, на основании которых можно определить цикловой подключ, после чего процедура повторяется. Отличительной чертой дифференциального анализа является то, что он практически не использует алгебраические свойства шифра (линейность, аффинность, транзитивность, замкнутость и т.п.), а основан лишь на неравномерности распределения вероятности дифференциалов.
Линейный метод криптоанализа
Метод предполагает, что криптоаналитик знает открытые и соответствующие зашифрованные тексты. Обычно при шифровании используется сложение по модулю 2 текста с ключом и операции рассеивания и перемешивания. Метод основан на поиске наилучшей линейной аппроксимации (после всех циклов шифрования) для выражения, описывающего выход шифра, после чего для нахождения каждого бита собственно ключа необходимо решить систему линейных уравнений для известных линейных комбинаций этих бит, но эта процедура не представляет сложности, так как сложность решения системы линейных уравнений описывается полиномом не более третьей степени от длины ключа.
Автоматизация методов криптоанализа для перебора ключей при помощи ЭВМ требует создания адекватной математической модели открытого текста для оценки получаемых результатов. Во многом успех криптоанализа основывается на избыточности открытых текстов на реальных языках [1, 2, 4]. Поэтому перед шифрованием данные целесообразно подвергать преобразованию, уменьшающему избыточность, в качестве которого может выступать сжатие информации. Преимущества использования сжатия перед шифрованием, помимо уменьшения избыточности, позволяет ускорить процесс шифрования, занимающий много времени, за счет сокращения объема открытых данных.
Дата добавления: 2018-02-15; просмотров: 1597; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!