A.F.Ronzhin. Problems of Security in Information Processing
Systems//В сб.: Два подхода к определению
стойкости криптографической системы Рассмотрим условия, которым
должна удовлетворять криптосистема для надежной защиты
информации. Стойкость зашифрованной информации (криптографическая
стойкость, или просто стойкость) зависит от возможности
несанкционированного чтения данных. Существует два типа
стойкости: теортическая (математическая) и практическая. Эти
концепции были предложены в классической работе Шеннона (Shannon,
1949). Термин "практическая стойкость" не означает, что
определение не является математически строгим. Стойкость обоих
типов стойкости в следующем. Теоретическая стойкость основана на
факте, что криптосистема моделируется некоторым формальным
объектом, и для этой модели формулируются определенные условия
невозможности раскола криптосистемы посторонним лицом. Обычно
полагается, что доступная злоумышленнику информация должна быть
недостаточной для определения открытого текста, даже если
информация о криптосистеме несекретна. В качестве меры
практической стойкости мы принимаем работу, т.е. число операций
или временную сложность определения открытой информации
посторонним лицом, либо средние значения этих характеристик над
множеством всех открытых текстов. В этом случае цель состоит в
получении максимальной сложности задачи несанкционированного
дешифрования. Следует отметить, что существует два подхода к
построению практически стойких шифров. В первом случае строится
криптосистема, и затем показывается, что ее раскол является
сложной задачей. Во втором случае выбирается некоторая сложная
математическая задача, и затем строится соответствующая
криптосистема, чей раскол эквивалентен решению этой задачи. В
статье (Diffie and Hellman, 1976) авторы впервые предложили
использовать класс сложных задач для построения криптосистем.
Однако следует отметить, что нет принципиальной разницы между
использованием систем с открытым ключом и, например,
DES-алгоритмов. Проблемы теоретической стойкости исследовались в
основном в работах, посвященных криптологии. Проблемы
практической стойкости исследовались в чисто математических
работах по вычислительной сложности. В заключение отметим, что
теоретическая стойкость определяется при условии, что не
существует временных ограничений на несанкционированное
дешифрование, и, следовательно, это является ответом на вопрос,
что криптосистема не может быть расколота в принципе. такие
совершенно стойкие системы существуют на самом деле (Wilkes,
1972). Их можно построить с помощью случайного равновероятного
ключа шифрования, чья длина не меньше длины открытого текста.
Совершенно стойкие системы чрезвычайно дороги в реализации.
Поэтому на практике используют системы, которые в принципе можно
расколоть, но за неприемлемое время. Отметим, что эксперты АНБ
(см.(Matyas et al., 1980; Unclassified summary, 1978)) не нашли
возможностей раскола ключей DES статистическими методами, а
рабочая группа ICST (Wilkes, 1972) заявила о невозможности
создания до 1990 года специализированного устройства для
исчерпывающего перебора ключей DES с вероятностью успеха 0.1-0.2.
Эксперты АНБ продлили гарантию стойкости алгоритмов DES до 1995
года. Стоимость и время, требуемые для раскола криптосистемы,
также налагают некоторые ограничения на стойкость криптосистем.
Для любой криптосистемы существует соответствие между ее
стоимостью и временем ее раскола. Зашифрованные данные, кроме
того, имеют ценность, обычно убывающую со временем. Это дает
определенное соответствие между ценностью и временем хранения
информации. При разработке и оценке практической стойкости
криптосистем эти соответствия необходимо принимать во внимание.
3.2. Математическая стойкость Пусть источник открытых текстов Х
вырабатывает информационные сообщения в соответствии с некоторым
стохастическим процессом g(t) с областью значений {X}. Пусть ключ
k K выбирается на основе другого стохастического процесса,
возможно, g(t). В результате шифртекст также является
стохастическим процессом, r(t). Основным условием, обеспечивающим
стойкость, является требование, чтобы вероятность восстановления
открытого текста на основе шифртекста Y=r(t), рассчитанная
посторонним лицом, была равна начальной вероятности Х, т.е.
P{g(t)=X}=P{g(t)=X I r(t)=Y}. (2) Разумно рассматривать такие
криптосистемы, в которых существует только единственное сообщение
Y=E(k,X) для любого открытого текста и любого ключа k, и для
различных пар (X,k) соответствующие шифртексты различны. Тогда
I{X}I<=I{Y}I. Ограничимся случаем, когда I{X}I=I{Y}I. В этом
случае E(k) является однозначным соответствием, и существует
D(k)=E (k). Если ключи выбираются с равными вероятностями 1/IKI
из множества K всех ключей, и число открытых текстов, являющихся
прообразами шифртекста, одинаково для любого шифртекста, то (2)
выполняется. Другие достаточные условия для (2) даны в (Shannon,
1949). Если равновероятный выбор ключей естественен, то вопрос о
распределении на множестве открытых текстов не совсем ясен.
Шеннон (см.(Shannon, 1949, 1951)) предложил подход, основанный на
избыточности естественных языков. Множество открытых текстов {X}
на алфавите естественного языка разделяется на следующие два
класса: полная вероятность первого класса близка к нулю, а
вероятность каждого сообщения из второго класса приблизительно
равна p=exp(-NH), где N - это длина сообщения, а H - энтропия
языка. Обычно можно полагать, что H=-p(1)log p(1) -...-p(z)log
p(z), где p(1),...,p(z) - относительные частоты букв
естественного языка. На основе упомянутых условий мы можем
получить следующие формулы для параметров криптосистемы (Meyer,
Matyas, 1982). Вероятность угадывания ключа при заданном
шифртексте равна приблизительно (1-exp(-h))/h, где
h=IKIexp(NH)/I{Y}I. Здесь IKI означает число ключей, а I{Y}I -
число шифртекстов. Если в противоположность упомянутому условию
число ключей, переводящих данный шифртекст в осмысленный открытый
текст, не одно и то же для всех шифртекстов и является случайной
переменной М, то P{M=m}=exp(-h')(h') /(m-1)!, где
h'=h(IKI-1)/IKI. Из этой формулы видно, каким важным параметром
является расстояние единственности (Shannon, 1949), т.е.
минимальная длина N открытого текста, для которой существует
единственный ключ, соотвествующий данному шифртексту. Вероятность
угадывания открытого текста из шифртекста равна
(1-exp(-h)/h)(1+h'/(2exp(NH))). Отметим, что эти формулы
соответствуют естественным языкам и включают число осмысленных
текстов таких, что вероятность множества осмысленных сообщений
равна единице. На втором этапе оценки стойкости шифрование
рассматривается как передача открытого текста по каналу с шумом
(роль шума выполняет криптосистема). При этом задача
восстановления открытого текста из шифртекста совпадает с задачей
восстановления сигнала, передаваемого по каналу с шумом. В теории
связи шум желательно снизить до минимума; в криптографии более
предпочтителен канал с максимальным шумом. По этой причине
очевидно, что сообщения имеют избыточность, измеряемую как 1-H,
где H - энтропия языка. Перечислим некоторые результаты,
полученные с помощью такого подхода (Meyer, Matyas, 1982;
Shannon, 1949). Расстояние единственности является решением
уравнения H(X)+H(K)-H(Y)=0 относительно длины Y. В случае, когда
даны и открытый текст и шифртекст, расстояние единственности для
ключей является решением уравнения H(K)-H(Y I X)=0 отноистельно
длины ключей из К. В этих формулах H( ) - энтропия случайной
переменной и H( )= p log p , где p =P{ =k}, т.е. H(X), H(Y), H(K)
- это меры неопределенности выбора открытого текста, шифртекста и
ключа соответственно, а H(YIX) - условная энтропия Y при условии,
что задано X. В предположении, что ключи в алгоритме DES
выбираются с равными вероятностями, и для данного открытого
текста все 2^56 шифртекстов выбираются с равными вероятностями из
множества 2^8N возможных шифртекстов (N - длина открытого
текста), получаем, что расстояние единственности равно длине
одного блока для ключей и удвоенной длине блока для открытых
текстов. Таким образом, алгоритм DES не является совершенно
стойкой системой. Примеры оценки расстояния единственности для
перестановки, подстановки и других криптосистем даны в (Deavours,
1977; Matyas, 1974; Meyer, Matyas, 1982). 3.3. Алгоритмическая
стойкость и возможности современного аппаратного обеспечения
Алгоритмическая или вычислительная стойкость (Denning, 1983)
определяет требования к вычислительным ресурсам, необходимым для
анализа криптографических алгоритмов, и используется для
исследования сложности раскола шифров. Стойкость криптосистем
измеряется вычислительной сложностью алгоритмов, используемых для
их рас кола. Вычислительная сложность включает временную
сложность Т и емкостную сложность S (объем памяти), используемые
алгоритмом. Параметры T и S являются функциями длины входных
последовательностей N. Обычно оценки функции f(n) можно
представить в виде f(n)=O(g(n)), где g(n) - просто вычислимая
функция. Например, если g(n) - полином степени t, то f(n)=O(n ).
При таком представлении сложность в определенной степени не
зависит от вычислительных средств. Кроме того, действительное
время выполнения алгоритма зависит от характеристик ключей и
открытого текста. Подобное представление возможно для среднего
объема памяти, используемого алгоритмом. Известна следующая
классификация алгоритмов в соответствии с их сложностью.
Полиномиальные алгоритмы - это алгоритмы со сложностью
полиномиального времени T=O(n ), где t - константа. Если t=1,
алгоритм называют линейным. Экспоненциальные алгоритмы - это
алгоритмы со сложностью экспоненциального времени T=O(t ), где
h(n) - полином, а t - константа. Можно предположить, что для
больших n полиномиальные алгоритмы в общем случае реализуемы на
многопроцессорных или специализированных компьютерах.
Экспоненциальные алгоритмы нельзя реализовать эффективно.
Алгоритмическая сложность тесно связана с математической
NP-сложностью. В теории сложности задачи классифицируются в
соответствии с минимальным временем и памятью, необходимыми для
их решения на машине Тьюринга или на другой абстрактной
вычислительной модели (Aho et al., 1974; Garey, Johnson, 1979;
Minsky, 1967). Показано, что в пределах класса задачи
эквивалентны. Все системы с открытым ключом основаны на
алгоритмах с полиномиальной сложностью шифрования и дешифрования
и с экспоненциальной сложностью их раскола (Konheim, 1981).
Многие криптосистемы имеют полиномиальную сложность, и их
практическая стойкость определяется мощностью компьютеров и в
первую очередь скоростью компьютеров и микропроцессоров. Скорость
микропроцессоров определяет мощность как персональных
компьютеров, наиболее доступных злоумышленникам, так и
специализированных многопроцессорных систем, используемых
профессионалами. Рассмотри состояние и тенденции развития
микропроцессоров и высокоскоростных компьютеров. Таблица 4
----------------------------------------------------------------Тип,
производитель Рабочая частота, Скорость, Число операций МГц
млн.опер./с на команду
----------------------------------------------------------------80386,
Intel 24 5,3 6,0 80486, Intel 40 18,0 1,0 68020, Motorola 25 4,0
7,0 68030, Motorola 25 6,8 --68040, Motorola 40 18,0 --VAX 8550,
DEC 22,2 3,0 7,0 VAX 8800, DEC 22 11,0 --R2000, MIPS 16,7 12,0
1,4 R3000, MIPS 25 20,0 1,25 Am2900, AMD 25 12,5 2,0 SPARC, Sun
Micro- 16,7 8,0 2,1 systems
----------------------------------------------------------------
Таблица 5
----------------------------------------------------------------Тип
ЭВМ Количество Скорость, млн. опер./с процессоров
----------------------------------------------------------------Cray
Y-MP/8 8 2000 SX-3 4 22000 TX-3 1024 20000 n-Cube 2 8192 27000
----------------------------------------------------------------В
последние два десятилетия наблюдается тенденция к стабильному
прогрессу в области микропроцессоров. Благодаря развитию
микроэлектроники и других отраслей необходимость в
микропроцессорах постоянно растет. В настоящее время имеются 1-,
4-, 8-, 16-, 32- и даже 64-битные микропроцессоры. Мы не имеем
возможности сделать полный обзор текущего состояния
микропроцессорной и компьютерной промышленности. Приводим только
две таблицы (таблицы 4 и 5), в которых показаны некоторые
характеристики производимых микропроцессоров и высокоскоростных
ЭВМ.
