В последнее время мы часто слышим о реальном применении криптографии в компьютерных системах и не только (даже стандарт сотовой связи GSM предусматривает защиту разговора абонентов при помощи методов симметричной криптографии). Криптография здорово продвинулась за последнее столетие. Придумано много алгоритмов: RSA, DES, алгоритмы на основе схемы Эль Гамаля, эллиптических кривых… Но!

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

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

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

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

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

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

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

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

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