Практическая стойкость шифров

Шифр должен быть криптостойким, то есть устойчивым к попыткам дешифрования сообщений. Отправленное сообщение до поступления к получателю является для него и, естественно, для злоумышленника неопределенным. Пусть возможна отправка сообщений T1,T2,...,Tn с вероятностью p1, p2,..., pn соответственно. Тогда мерой неопределенности сообщения для всех, кто обладает этой априорной информацией, может служить величина математического ожидания логарифма вероятности одного сообщения, взятая со знаком "минус"; по некоторым соображениям в качестве основания логарифма удобно выбрать 2:

Эта величина имеет вполне понятный физический смысл: количество битов информации, которое необходимо в среднем передать, чтобы полностью устранить неопределенность. Если никакой априорной информации о сообщении нет кроме его размера в N бит, то все возможные из 2^N вариантов считаются равновероятными и тогда неопределенность сообщения равна его размеру:

H(T) = -2^N·2^-N·log₂(2^-N) = N = | T |,

где через | X | обозначен размер блока данных X в битах. А если об исходном тексте неизвестно вообще ничего, даже его размер? В этом случае все равно необходимо принять за основу какую-либо модель распределения. Как правило, в реальности подобных трудностей не возникает, поскольку многие весьма стойкие шифры не считают нужным скрывать размер шифруемого сообщения, так как в этом действительно почти никогда нет особой необходимости, и эта характеристика априорно считается известной злоумышленнику. Там же, где этот размер все же реально необходимо скрыть, все сообщения перед шифрованием преобразуются в массивы данных одной и той же длины, и мы опять получаем рассмотренную выше ситуацию.

После перехвата шифротекста эта величина, естественно, может измениться, теперь она становится апостериорной ("после-опытной") условной неопределенностью - условием здесь является перехваченное шифрованное сообщение T'. Теперь она задается следующей формулой:

,

где через p (T_i | T') обозначена вероятность того, что исходное сообщение есть T_i при условии, что результат его зашифрования есть T'.

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

I = H(T) - H(T | T').

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

В наилучшем для разработчиков шифра случае обе эти неопределенности равны:

H(T | T') = H(T),

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

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

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

Поясним сказанное на примере: пусть перехвачена короткая 12-битовая шифровка, имеющая следующее содержание:

1 0 0 1 0 1 1 1 0 1 0 1

Для простоты предположим, что исходное сообщение имеет ту же длину. Если у злоумышленника нет никаких априорных сведений о зашифрованном сообщении, для него каждый из 2¹² исходных вариантов равновероятен, и, таким образом, вероятность правильно определить исходное сообщение простым угадыванием равна 2^-12. Предположим теперь, что злоумышленнику априорно известно, что зашифрование является наложением одной и той же 4-битовой маски на каждую 4-битовую группу сообщения с помощью операции побитового исключающего или. Очевидно, возможно 16 = 2⁴ различных вариантов битовой маски, соответственно, возможно 16 различных значений исходного текста:

маска исходный текст0000 1001011101010001 1000011001000010 101101010110.....1111 011010001010

Таким образом, теперь вероятность правильно угадать исходный текст равна 1/16 - знание особенности использованного способа шифрования повысило ее в 256 раз. Отсюда следует интересный вывод: чем больше неопределенность в шифрующем преобразовании для постороннего лица, тем дальше оно стоит от разгадки шифра, тем шифр надежнее. Шифр, полностью неопределенный для злоумышленника

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

Однако на практике бывает сложно сохранить полную неопределенность относительно шифра у злоумышленника - он может получить информацию о шифре следующими способами:

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

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

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

1. Анализ зашифрованных данных не должен давать злоумышленнику никаких сведений о внутреннем устройстве шифра. В шифротексте не должно прослеживаться никаких статистических закономерностей - например, статистические тесты не должны выявлять в зашифрованных данных никаких зависимостей и отклонений от равновероятного распределения битов (символов) шифротекста.

2. Алгоритм должен быть перенастраиваемым. В распоряжении злоумышленника рано или поздно может оказаться описание алгоритма, его программная или аппаратная реализация. Для того чтобы в этом случае не пришлось заменять алгоритм полностью на всех узлах шифрования, где он используется, он должен содержать легко сменяемую часть.

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