Взлом криптографических алгоритмов: анализ

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

На сегодняшний день работники крупной компании с большими вычислительными мощностями и/или пользователи глобальной сети совместными усилиями могут методом перебора вскрыть ключ максимальной длиной 64–80 бит. По оценкам, взлом шифра со 128-битным ключом займет не менее 1020 лет. Впрочем, оценки такого рода весьма поверхностны. Так, вскрытие 64-битного ключа (симметричного алгоритма RC5-64) потребовало сравнительно меньших временных затрат, чем предполагалось. Распределенное на несколько сотен тысяч машин сложное математическое задание позволило «взломать» ключ за пять лет против предполагавшихся ста лет.

Вспомним удачный отечественный ГОСТ 28147-89 — это симметричная блочная криптосистема, немного напоминающая известный алгоритм DES (только по сходной структуре итераций, шаг шифрования у него совсем другой). Ключ у него «всего» 256 бит. Учтите, что это 256 случайных бит. Так что для прямой атаки на ключ придется перебрать все 2256 ключей, что физически не реализуемо: при минимальном энергопотреблении взламывающего вычислителя (оно определяется исходя из квантовой теории) оказывается, что для обеспечения энергией такого вычислителя необходимо рвануть сверхновую.

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

Здесь уместно отметить один неудачный отечественный опыт, в результате которого был придуман более простой алгоритм вскрытия шифра, чем ожидалось. В 1994 году был принят первый отечественный стандарт в области электронной цифровой подписи (ЭЦП) — ГОСТ Р34.10-94 «Информационная технология. Криптографическая защита информации. Процедуры выработки и проверки электронной цифровой подписи на базе асимметричного криптографического алгоритма». Он определяет процедуры работы с ЭЦП на основе схемы Эль Гамаля. Невозможность подделки подписи основана на сложности решения задачи дискретного логарифмирования в поле из р элементов. Однако математика не стоит на месте, и недавно был изобретен так называемый метод решета числового поля. С его помощью можно «взломать» ЭЦП, сформированную по схеме Эль Гамаля, по крайней мере в случае 512-битного модуля р.

Некоторые разработчики предпочитают использовать, казалось бы, уходящие в прошлое методы симметричного шифрования. Они боятся, что сделают ставку на некоторый надежный, по их мнению, асимметричный алгоритм, а математики через некоторое время придумают новый метод и вскроют его (алгоритм). С этой точки зрения симметричные алгоритмы, вероятно, более прогнозируемы (но отнюдь не более надежны). Надо ли говорить, что классические методы шифрования и изучены гораздо больше, а их надежность обоснована неизмеримо лучше, чем надежность методов «современной криптографии».

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