Методы анализа криптографических алгоритмов, основанные на принципе многократного использования блочных шифров

Р. Меркль и М. Хеллман на примере DES показали, как, используя метод встречи посередине, можно вскрыть схему двукратного шифрования.

Рассмотрим метод вскрытия блочного шифра при использовании двойного шифрования в общем случае.

Предположим, что известны блок М открытого текста и соответствующий ему блок С шифрованного текста. Алгоритм вскрытия неизвестных ключей k ₁ и k ₂ состоит из двух этапов.

На первом этапе перебираются все возможные варианты ключа k ₁. Для каждого варианта k ключа k ₁ вычисляются значения ADR(k) = E _k (М), после чего значения k помещаются в память по адресу ADR(k).

На втором этапе опробуются возможные варианты ключа k ₂. Для опробуемого варианта k ' ключа k ₂ вычисляются значения и производится обращение в память по адресу ADR(k '). Если по этому адресу памяти записи отсутствуют, то происходит переход к опробованию следующего варианта k ' ключа k ₂. Если же по адресу ADR(k ') в памяти хранится ключ k, то образуется допустимая пара ключей (k, k '), удовлетворяющая равенству .

Заметим, что в ячейку памяти с номером ADR(k ') могут попасть несколько вариантов ключа k (для этого память необходимо соответствующим образом организовать). Для каждого из них пара (k, k ') является допустимым ключом.

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

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

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

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

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

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

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