Безусловная и теоретическая стойкость
Существует два принципиально разных метода обеспечения стойкости криптографических систем против криптоаналитического нападения.
В некоторых системах объем доступной криптоаналитику информации фактически недостаточен для того, чтобы найти преобразования и дешифрирования, причем данная ситуация не зависит от того, какие вычислительные мощности имеет криптоаналитик.
Система такого рода называется безусловно стойкой.
В том случае, когда перехваченный материал содержит достаточно информации для однозначного решения криптоаналитической задачи, нет никакой гарантии, что это решение будет найдено криптоаналитиком, имеющим определенные вычислительные ресурсы. Следовательно, цель разработчика криптографической системы состоит в том, чтобы уменьшить затраты на операции шифрования и дешифрирования, но чтобы в тоже время любая криптоаналитическая операция была слишком сложной и поэтому экономически невыгодной. Иными словами, необходимо, чтобы задача криптоанализа, о которой известно, что она разрешима при конечном объеме вычислений, была бы столь громоздкой, что для ее решения не хватило бы физических вычислительных ресурсов всего мира. Задачу такого объема называют вычислительно нереализуемой, а связанную с ней криптографическую систему — вычислительно стойкой.
В случае безусловно стойких систем их стойкость может быть доказана, но что касается теории вычислительной сложности, то при нынешнем уровне ее развития она не в состоянии продемонстрировать вычислительную нереализуемость любой криптографической задачи. Поэтому в криптографии возникло и развивается направление, посвященное разработке формальных процессов проверки стойкости. Такие процессы сводятся к криптоаналитическому нападению на предлагаемые для проверки криптографические системы при условиях, благоприятных для криптоаналитика.
Единственной безусловно стойкой системой, находящейся в широком пользовании, является лента однократного использования, в которой открытый текст объединяется со случайным ключом такой же длины.
Обычно открытый текст представляет собой строку из n бит, которая объединяются со случайным ключом такой же длины с помощью сложения по модулю 2. Как видно из самого названия, этот ключ никогда больше не используется.
Даже если бы криптоаналитик попытался осуществить дешифрирование, используя все 2n
возможных ключей, он просто увидел бы все 2n возможных открытых текстов одинаковой длины. Поскольку перехват криптограммы не позволяет криптоаналитику вывести какое-либо сообщение в виде открытого текста, то он не узнает ничего, кроме длины сообщения. Клод Шеннон анализировал абсолютную стойкость более подробно. Если криптоаналитик располагает неограниченным временем для вычислений, то он не связан рамками вычислительной эффективности и может провести полный криптоанализ, испытывая все возможные ключи и сохраняя в качестве результата все осмысленные тексты. В случае ленты однократного использования необходимо сохранить все осмысленные тексты, имеющие одинаковую с криптограммой длину, но в других безусловно стойких системах может быть меньшее количество осмысленных решений. Например, криптограмма XMDA, полученная в результате простой подстановки годится для любого четырехбуквенного слова с неповторяющимися буквами.
По мере того как количество перехваченных текстов возрастает, может быть достигнута точка, в которой оказывается возможным получение однозначного решения. Шеннон назвал это интервалом однозначности N0. В случае ленты однократного использования этого никогда не случиться, и N0 = ¥, тогда как в случае простого подстановочного шифра значение N0 конечно. Шеннон предложил модель для предсказания интервала однозначности шифра. Полученные с помощью этой модели результаты согласуются с практикой. В соответствии с этой моделью “случайного шифра”
N0 = (18.7)
где H(K) — энтропия ключа (обычно это просто длина ключа, измеренная в битах, или log2 от количества ключей), D — избыточность языка, измеренная в битах на 1 знак. (Например, в английском языке за буквой Q всегда следует буква U, которая является избыточной.) Качественно модель можно показать, переписав (18.7) в виде требования для однозначности решения
H(K) £ N0D (18.8)
где H(K) характеризует количество неизвестных в двоичном представлении ключа, а N0D в широком смысле определяет количество уравнений, которые необходимо решить для нахождения ключа. Когда количество уравнений меньше количества неизвестных, однозначное решение невозможно и система является безусловно стойкой. Когда количество уравнений больше количества неизвестных, т.е. как в (18.8), однозначное решение возможно и система не является безусловно стойкой, хотя она все еще может быть вычислительно стойкой.
Несмотря на то, что в теории кодирования Шеннона (т.е. в предположении, что криптоаналитик располагает неограниченными ресурсами) обычно рассматривается нападение при наличии только шифрованного текста, но иногда используются и комбинации шифрованного и открытого текста, что повышает избыточность.
Уравнение (18.7) показывает ценность снятия данных, производимого перед шифрованием.
Согласно Фридмэну, почти любая криптограмма из 25 букв и более, полученная подстановкой, может быть раскрыта. Поскольку криптоаналитик располагает ограниченными вычислительными возможностями, он не может перепробовать все 26! » 4.1026 ключей и должен полагаться на субоптимальные методы, такие как частотный анализ. Таким образом, можно сказать, что N0 = 25 знаков.
В случае ленты однократного использования H(K) = ¥, откуда, согласно (7), N0 = ¥. После простой подстановки получаем H(K) = log2(26!) = 88,4 бит, поэтому для вычисления N0
принято находить D. Каждый знак мог бы переносить максимум log2(26) = 4,7 бит информации, если бы все комбинации были возможны. Но поскольку правила правописания и грамматики запрещают использование большинства комбинаций, то в среднем каждый знак переносит всего лишь 1,5 бит информации. Оставшиеся 3,2 бит оказываются избыточными, откуда D = 3,2 бит/знак. Таким образом, уравнение (18.7) представляет величину N0 = 28 знаков, что хорошо согласуется с практикой.
Например, если перехвачено сообщение длиной в 1000 знаков и известна некоторая последовательность из 100 знаков открытого текста, то общая избыточность составит не 3200 бит, а (900 знаков) ´ (3,2 бит/знак) + (100 знаков) ´ (4,7 бит/знак) = 3350 бит.
Сжатие данных устраняет избыточность, увеличивая тем самым интервал однозначности. Избыточная информация может быть добавлена после дешифрирования. Совершенное сжатие данных устранило бы всю избыточность и привело бы к N0 = ¥ при любой длине ключа, но это довольно дорогое мероприятие.
Важным подготовительным этапом для проверки стойкости шифра является продумывание различных предполагаемых возможностей, с помощью которых противник может вскрыть шифр. Появление таких возможностей у противника обычно не зависит от собственно используемого криптографического метода, а является следствием некоторой внешней подсказки, наличие которой существенно влияет на стойкость шифра. Поэтому оценки стойкости шифра всегда содержат те предположения о противнике, в условиях которых эти оценки получены.
Прежде всего, обычно считается, что противник знает сам шифр и имеет возможность его предварительного изучения. Противник также знает некоторые характеристики открытых текстов (защищаемой информации), например, общую тематику сообщений, их стиль, некоторые стандарты, форматы и т.д.
Приведем три примера специфических возможностей противника:
- противник может перехватывать все шифрованные сообщения, но не имеет соответствующих им открытых текстов;
- противник может перехватывать все шифрованные сообщения и добывать соответствующие им открытые тексты;
- противник имеет доступ к шифру (но не к ключам!) и поэтому может зашифровать любую информацию.
На протяжении многих веков среди специалистов не утихали споры о стойкости шифров и о возможности построения абсолютно стойкого шифра.
“Отец кибернетики” Норберт Винер отмечал: “Любой шифр может быть вскрыт, если только в этом есть настоятельная необходимость и информация, которую предполагается получить, стоит затраченных средств, усилий и времени…”
Поэтому у пользователя остается единственный путь — получение практических оценок стойкости. Этот путь состоит из следующих этапов.
1. Понять и четко сформулировать, от какого противника необходимо защищать информацию. Следует уяснить, что именно противник знает или может узнать о системе шифра, какие силы и средства он сможет применить для его вскрытия.
2. Мысленно стать в положение противника и попытаться с его позиций вскрыть шифр, т.е. разработать различные алгоритмы вскрытия шифра, обеспечивая при этом в максимальной мере моделирование сил, средств и возможностей противника.
3. Наилучший из разработанных алгоритмов использовать для практической оценки стойкости шифра.
Следует упомянуть о двух простейших методах вскрытия шифра: случайного угадывания ключа (он срабатывает с малой вероятностью, но является самую низкую вычислительную сложность) и перебора всех подряд ключей вплоть до нахождения истинного (он срабатывает всегда, но имеет самую высокую вычислительную сложность).
