зависящей от числа итераций n=1,...,16 и ключевой
последовательности K. Ключ k, используемый в n-ой итерации,
равен k =Ks(n, K). Дешифрование выполняется по тому же алгоритму
лишь с тем различием, что ключи k ,...,k используются в обратном
порядке. Функцию шифрования f можно представить схемой,
показанной на рис.2. Функция Е на схеме размещает 32-битный блок
R на 48 позициях по предписанному правилу. Каждая из восьми групп
B,...,B из 6 последовательных битов является входом
соответствующей функции выбора Si, i=1,...,8, c 4-битными
выходами. Для каждого i функция Si определяется (16х4)-матрицей
Ai с элементами a , принимающими значения 0,1,...,15. Первый и
последний биты входа рассматриваются как двоичное число,
определяющее число r, а 4 средних бита рассматриваются как
двоичное число6 определяющее s. Тогда выход Si равен a,
представленному в двоичном счислении. Выход Si преобразуется
перестановкой P. Таким образом, если входы функции f равны R и k,
то f(R, k)=P(S (B ),...,S (B )), где B B ...B = k+E(R). Отметим,
что мы рассматриваем g-блоки А и h-блок В записанными вместе как
единый блок АВ длиной g+h. Процесс построения ключа k из
64-битного блока KEY показан на рис.3. Из 64 бит KEY функция PC-1
выбирает 56 бит и делит их на 28-битные блоки C и D. В каждой
итерации i, i=1,...,16, выполняется циклический сдвиг содержимого
регистров Ci и Di на l(i) бит влево, и с помощью функции PC-2 из
полученного блока CiDi выбирается 48-битный блок k. Для
завершения описания алгоритма остается задать значения НП, Е, S
,...,S, PC-1, PC-2 и L=(l(1),...,l(16)). Функции S,...,S и PC-2
можно найти в (DES, 1977). Все они не имеют определенной
структуры, и мы не даем здесь их описание. Таким образом, мы
видим, что DES выполняет 16 итераций и зависит от 16 ключей
длиной 48 бит каждый. Эти ключи, как следует из описания PC-1,
выбираются из одного установленного ключа. Кроме того, содержимое
регистров Ci, Di сдвигается, поэтому С =Со и D =Dо. При
дешифровании функция выбора ключа действует точно так же, только
сдвиг регистров выполняется вправо. Завершим описание алгоритма
DES матрицей для выбора ключей k,...,k k = 28
k = 2 ... 23
.................................. k = 5 ... 39
Среди этих чисел нет битов из разрядов 8,16,...,64, используемых
для управления на начальном этапе построения ключа. Отметим
некоторые черты алгоритма DES. 1. Слабые ключи (Meyer and Matyas,
1982). Существуют ключи, для которых k =...=k, т. е. ключи, для
которых содержимое регистров C и D состоит только из нулей
(толлько из единиц), либо из последовательностей вида 0101...01;
1010...10; 0011...0011; 0110...0110; 1001...1001; 1100...1100.
Хотя число таких ключей очень мало по сравнению с общим числом
ключей, равным 7*10^17, и вероятность того, что такой ключ
появится при случайной генерации ключей, очень мала, необходимо
исключать такие ключи путем специального контроля. 2. Критерии
выбора математических преобразований. Первый этап DES длился 5
лет. В результате были предложены некоторые критерии, часть из
которых строго сформулирована и может использоваться в
криптоанализе. В частности, для выбора перестановок был принят
принцип, что каждый выходной бит должен фактически зависеть от
каждого бита ключа и открытого текста, а преобразование должно
включать минимум итераций (Meyer, 1978). Другим важным принципом
является требование, что функции в DES для своей реализации
используют минимальное число логических операций (Honget al.,
1974).
http://users. /~batmanb/box/1/27.shtml
Проблемы безопасности в системах обработки информации. Стойкость криптографических систем
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 pp(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, 198Алгоритмическая
стойкость и возможности современного аппаратного обеспечения
Алгоритмическая или вычислительная стойкость (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
Тип,
производитель Рабочая частота, Скорость, Число операций МГц
млн. опер./с на команду
386,
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/SX-TX-3 1n-Cube 2 8
В
последние два десятилетия наблюдается тенденция к стабильному
прогрессу в области микропроцессоров. Благодаря развитию
микроэлектроники и других отраслей необходимость в
микропроцессорах постоянно растет. В настоящее время имеются 1-,
4-, 8-, 16-, 32- и даже 64-битные микропроцессоры. Мы не имеем
возможности сделать полный обзор текущего состояния
микропроцессорной и компьютерной промышленности. Приводим только
две таблицы (таблицы 4 и 5), в которых показаны некоторые
характеристики производимых микропроцессоров и высокоскоростных
ЭВМ.
http://users. /~batmanb/box/1/28.shtml
Проблемы безопасности в системах обработки информации. Протоколы криптосистем
A. F.Ronzhin. Problems of Security in Information Processing
Systems//В сб.: Организация безопасной связи должна
удовлетворять определенным строгим правилам, которые регулируются
протоколами. Для различных типов безопасной связи требуются
разные протоколы. Мы не имеем возможности перечислить все типы
безопасной связи и привести хотя бы краткое описание
соответствующих протоколов. Ограничимся некоторыми примерами
протоколов аутентификации и цифровой подписи. 4.1. Задачи
аутентификации Аутентификация - это процесс, используемый для
подтверждения подлинности (аутентичности) кого-либо или
чего-либо. Криптографические методы обеспечивают высший уровень
аутентификации сообщений, данных, ключей и устройств. Все методы
аутентификации имеют общую часть, в которой проверяется
аутентичность одного или нескольких параметров. Федеральный
стандарт США (Federal Standard 1026, 1978) определяет
аутентификацию как процесс, гарантирующий инвариантность данных
частей или позиций, либо подтверждающий аутентичность данного
информационного блока. Необходимо отличать параметры
аутентификации и процесс аутентификации от цифровых подписей. В
процессе аутентификации не требуется доказывать третьей стороне,
что информация была послана этим отправителем и не была создана
получателем. Однако требуется, чтобы получатель был уверен в том,
что информация была послана именно данным отправителем.
Криптографические алгоритмы, используемые для аутентификации,
должны удовлетворять следубщим условиям. 1. Они должны быть
надежными в том смысле, что ключ шифрования не может быть найден
на основе соответствующих открытого и зашифрованного текстов. 2.
Ключи криптосистемы должны быть защищены. Очевидно, что эти
условия выполняются при использовании классических алгоритмов,
алгоритмов с открытыми ключами и процедур, основанных на
односторонних функций (Evans et al., 1974; Purdy, 1974; Westin,
1968). Рассмотрим три случая, когда аутентификация играет важную
роль. В первом случае это подтверждение установления связи между
двумя санкционированными пользователями системы. Процедура
называется рукопожатием. Второй случай - это аутентификация
сообщения, которая должна подтвердить получателю аутентичность
отправителя сообщения, содержимого сообщения, порядка сообщений
(т. е. получатель должен быть уверен, что он принял сообщения в
том порядке, в котором они отправлялись), адреса сообщения (т. е.
пользователь должен быть уверен, что сообщение передано в том
направлении, в котором оно посылалось). В третьем случае
проверяется аутентичность тех системных данных, которые должны
быть постоянными в течение некоторого периода времени (например,
ключи, идентификаторы пользователя и т. п.). В качестве примера
опишем протокол рукопожатия. 4.2. Протокол рукопожатия Рассмотрим
процедуру, позволяющую пользователю А проверить аутентичность
пользователя В. Очевидно, что обратная процедура позволяет
пользователю В проверить аутентичность пользователя А.
Пользователь А вырабатывает псевдослучайное число N, которое
шифруется с помощью сеансового ключа k и посылается пользователю
В. Пользователь В дешифрует его и вычисляет некоторую открытую
(несекретную) функцию y(N). Затем значение y(N) шифруется и
посылается пользователю А. Пользователь А дешифрует принятое
значение и сравнивает его с y(N). Равенство подтверждает
аутентичность пользователя В. Этот метод делает невозможной
"ночную атаку" злоумышленника, поскольку при следующем сеансе
терминал вырабатывает другое псевдослучайное число N, и
злоумышленник не может дать правильный ответ на запрос системы,
так как он знает только значение E(k, N). Иногда в качестве
функции Y используется инверсия некоторых битов в двоичной записи
числа N. Важно, чтобы N генерировалось терминалом A в защищенной
памяти, и, более того, оператор не должен иметь возможности ввода
N. В противном случае злоумышленник может действовать следующим
образом. Он устанавливает на терминале y(N') вместо N', получает
E(k, y(N')), шифрует его и посылает пользователю B вместо E(k
,N'). Таким образом, в памяти пользователя теперь находится E(k
,y(N')) вместо истинной записи E(k, y(N)). Затем злоумышленник
посылает N' пользователю В и успешно проходит проверку на
аутентичность. Для предотвращения таких типов нападений можно
использовать некоторое число R, хранимое в защищенной памяти,
вместо случайно генерируемого N. Для проверки аутентичности связи
А шифрует число R на ключе k, т. е. берет E(k ,R ). Злоумышленник
может ввести N' и получить E(k, N'). Поскольку y - это открытая
функция, можно получить y(E(k, N')). Также можно получить y(E(k
,y(k, N'))). Он может заменить E(k, y(E(k, E(k R )))) на E(k
,y(E(k, N'))), но он не может заменить N на N'. 4.3. Цифровые
(электронные) подписи В соответствии с единым торговым кодексом
(Uniform Commercial Code, 1972) и законами США такими, как Закон
о подписи и Закон об учреждениях (Corley and Robert, 1971),
подпись на документе должна гарантировать то, что документ,
обговаривающий обязательства сторон, действительно подписан
данным лицом в данное время. С этой целью в процесс вовлекается
третья сторона (арбитр, нотариус и т. п.). У (Lipton and Matyas,
1978) юридические положения адаптированы для электронной почты.
Цифровая подпись должна быть такой, чтобы получатель мог доказать
аутентичность сообщения третьей стороне и отправителю. Цифровая
подпись является функцией подписываемого сообщения, протокола или
документа и конфиденциальной информации, известной только
отправителю, а также, возможно, открытой информации. Передача
подписанного сообщения от А к В может осуществляться, если они
имеют соответствующие возможности. А должен иметь информацию для
создания подписи для каждого сообщения, а В должен иметь
информацию для проверки аутентичности сообщения и авторства А.
Отправитель А может потребовать подтверждение факта приема
сообщения. Существует несколько криптосистем, позволяющих
реализовать цифровые подписи на базе симметричных алгоритмов и
алгоритмов с открытым ключом. Цифровые подписи, используемые в
системах, где каждое лицо, допущенное к системной услуге, может
проверить аутентичность отправителя и сообщения, называют
универсальными. Их легко построить, используя алгоритмы с
открытым ключом. Универсальные подписи можно создать и на сонове
симметричных алгоритмов. В этом случае требуется передача
дополнительной конфиденциальной или открытой информации для
каждого сообщения. Также представляют интерес методы построения
цифровых подписей на базе симметричных алгоритмов, обеспечивающие
свойства алгоритмов с открытым ключом. Другим подходом к созданию
цифровых подписей является вовлечение в процесс связи третьей
стороны, играющей роль инспектора. 4.4. Протоколы универсальных
подписей Применение универсальных подписей позволяет получателю
проверить аутентичность подписи и сообщения независимо от других
лиц. Третья сторона может вовлекаться в процесс только для
разрешения спорных моментов. Рассмотрим более подробно некоторые
протоколы. 4.5. Применение алгоритма с открытым ключом Данный
класс алгоритмов описан в (Cryptographic Algorithms, 1973;
Hellman et al., 1976; Shamir, 1978). Пусть К будет ключом для
шифрования сообщений i-ым пользователем, и пусть К будет ключом
для дешифрования сообщений, принимаемых j-ым пользователем. Затем
в зависимости от секретности ключей возможны следующие типы
систем связи: а) К - открытый, К - секретный. В этом случае
система связи обеспечивает секретность передаваемой информации.
Любой пользователь, применяющий открытый ключ, может передать
сообщение, а соответствующий получатель может только дешифровать
его; б) К - секретный, К - открытый. В этом случае аналогичная
система связи не обеспечивает секретность передаваемой
информации. Любой пользователь может дешифровать сообщение, и,
следовательно, проверить, что информация была послана i-ым
пользователем, так как i-ый пользователь может шифровать только
на К ; в) К и К секретные, а К и К открытые. Алгоритм
удовлетворяет условию D(K, E(K, X)) = E(K, D(K, X)) = X (3) для
всех Х или подмножества всех сообщений (Hellman et al., 1976).
Система обеспечивает секретность передаваемых сообщений и
доказательство аутентичности подписи. Общая схема передачи
подписанного сообщения строится на основе файла, доступного
каждому лицу и содержащего идентификаторы пользователей (числа 1,
2,...) и их ключи шифрования К, К,... Каждый пользователь имеет
секретный ключ дешифрования К, К,.. Кроме этого, условие (3)
выполняется для каждой пары ключей К, К и не действует почти для
всех Х, если К =К, К =К. Несмотря на тот факт, что открытый
файл не содержит никакой секретной информации, его необходимо
защищать от разрушения другими системами. Пусть все сообщения
имеют вид М=<идентификатор отправителя><идентификатор получателя>
<последовательность чисел><данные>. Для передачи сообщения
Mn(i, j,n, X) от i к j необходимо выполнить следующие процедуры: 1.
Пользователь i дешифрует сообщение Mn на секретном ключе K. 2.
Пользователь i шифрует его на открытом ключе К и после этого
передает j сообщение вида E(K, D(K, XПользователь j
дешифрует сообщение на секретном ключе K и шифрует его на
открытом ключе К, получая сообщение Mn. Величину D(K, X) после
проверки сообщения Mn можно использовать как доказательство того,
что сообщение Mn было послано пользователем i. Поскольку величина
К известна только пользователю i, никто не мог создать сообщение.
Пусть часть сообщения Mn, включающая Qn=<идентификатор
отправителя><идентификатор получателя> <последовательность
чисел>, содержит r бит. Тогда вероятность правильного
дешифрования D(K , Mn) на произвольном ключе, отличном от К,
равна 2^(-r). Это позволяет выполнить аутентификацию Mn путем
проверки значения Qn. В данном случае D(K, Mn) зависит и от
сообщения и от секретного ключа отправителя и может быть
рассчитано только отправителем. Кроме того, D(K, Mn) можно
рассматривать как подпись, поскольку аутентичность сообщения
определяется по параметрам Qn, которые доступны всем. Несмотря на
тот факт, что симметричные блочные алгоритмы существенно
отличаются от алгоритмов с открытым ключом с точки зрения
шифрующих и дешифрующих преобразований, основанные на них
криптосистемы, включая управление ключами, можно построить таким
образом, что описанный выше протокол не претерпит изменений.
Подробное описание метода взаимодействия двух пользователей, либо
пользователя и системы можно найти в (Zennon et al., 1980, 1982).
Коротко опишем идею. Пусть К - секретный ключ, и пусть определены
следующие ключи: К = E(K, K), K = E(K, K). В данном случае K,
i=1,2, - это варианты главного ключа. Кроме того, имеются два
типа криптографических операций - только шифрование данных (ENCO)
и только дешифрование данных (DECO): ENCO{K, X} -- E(D, K ,X) и
DECO{K, Y} -- D(D, K,Y) соответственно. В этом случае для всех Х
имеем DECO{K ,ENCO{K, X}} = X, и K = K для всех K. Следует
отметить, что знание K не дает возможности восстановить K
благодаря стойкости самого блочного алгоритма. Если положить, что
К открытый, а К секретный, то получим все свойства алгоритмов с
открытым ключом. При обеспечении защиты главного ключа системы и
ключа К обеспечивается стойкость системы. Для выработки ключей К
и К используется операция GENKEY, которая не имеет входных
значений (она берет псевдослучайные числа RN от своего
внутреннего генератора) и имеет два выхода: GENKEY -- (E(K
,RN),E(K, RNМетод Диффи-Лампорта Метод основан на
симметричном блочном алгоритме (Chaum, 1979). Пусть требуется
подтверждение подписей n-битного сообщения. Отправитель заранее
вырабатывает n пар ключей криптоалгоритма: (К, К ), i = 1,...,n,
которые хранятся в тайне, и предоставляет получателю две
последовательности для проверки аутентичности: (U, U ), (V, V
), i = 1,...,n, где V = E(K, U ), l = 1,2, i = 1,...,n.
Отправитель записывает последовательности, а получатель хранит их
в несекретном файле, имеющем дополнительную защиту от разрушения.
По окончании описанного процесса выполняется следующая процедура
передачи подписанного сообщения. Отправитель передает сообщение M
= m(1)...m(n) вместе с ключами К ; сравнение результата с V, i =
1,...,n, позволяет сделать вывод об аутентичности сообщения и
отправителя, так как никто не знает ключей К и К, i = 1,...,n.
Поскольку ключи неизвестны и получателю, тот не может
сформировать фальшивое сообщение. Процедура имеет существенный
недостаток. Требуется передавать и хранить большой объем
информации, пропорциональный длине передаваемого сообщения. Один
из методов смягчения этого недостатка - использование методов
сжатия. Код сжатия (С ) - это функция, которая отображает
двоичные последовательности переменной длины в битовые
последовательности фиксированной длины m. Код сжатия и величина m
выбираются таким образом, чтобы вычисление М и М', для которых
справедливо С (М) = С(М'), было чрезвычайно сложным. Один из
способов построения функции С с помощью симметричного алгоритма
заключается в следующем. Выбираются два несекретных ключа К и К.
Для сообщения Х, состоящего из блоков Х,...,Х, вычисляются два
значения U и U по следующим правилам: Y = E(K, X + Y ), Y = 0, i
= 1,...,n, U = E(K, X +...+ X + Y ), r = 1,2, после чего
полагаем, что C (M) = (U, UМетод Рабина Метод описан в
(Rabin, 1978). Отправитель вырабатывает 2r криптографических
ключей К,..., K, которые хранятся в секрете. Ключи используются
для выработки параметров U,..., U и E(K ,U ),..., E(K , U ),
позволяющих установить аутентичность. Эти параметры посылаются
получателю и хранятся получателем и отправителем в файлах,
имеющих дополнительную защиту от разрушения. Цифровая подпись
сообщения М формируется следующим образом. Находится сжатие
сообщения вида C (M), которое шифруется на всех ключах сообщения.
Итоговая подпись E(K, C (M)),..., E(K, C (M)) (4) передается
получателю. Процедура проверки аутентичности заключается в
следующем. Отправитель раскрывает получателю половину ключей, а
другую половину хранит в тайне, чтобы предотвратить фальсификацию
сообщения получателем. r требуемых ключей выбираются с участием
получателя. Он либо производит случайную выборку объема r без
заемены из множества 2r элементов, либо вырабатывает случайный
двоичный вектор длины 2r, содержащий ровно r единиц. Единица в
i-ой позиции означает выбор ключа К . Выбранные ключи передаются
получателю, который проверяет, совпадают ли значения параметров U
и C (M), зашифрованные на ключах, со значениями E(K, U ) и E(K, C
(M)) соответственно. Если получатель пытается приписать
отправителю фальшивое сообщение, то отправитель показывает все
ключи К,..., К третьей стороне, которая проверяет соответствие
всех параметров. Если совпадает более r элементов подписи (4),
сообщение приписывается отправителю. В противном случае оно
считается поддельным. Для формирования фальшивого сообщения
отправитель должен определить ровно r параметров. Поскольку ключи
запрашиваются получателем, отправитель может правильно угадать
положения параметров с вероятностью (r!)^2/(2r)!. 4.8. Метод
Матиаса и Мейера Данный метод (Matyas and Meyer, 1981a, 1981b)
требует построения исходных таблиц параметров. Первая таблица
размера 31х31 состоит из секретных ключей K(i, j), а вторая
таблица размера 30х31 состоит из кодовых слов U(i, j), являющихся
несекретными параметрами для проверки аутентичности. Эти таблицы
можно, например, построить следующим образом. Предположим имеется
секретный ключ К и открытый параметр U. Тогда для n-ного
сообщения построим первую таблицу с элементами U(i, j) =
E(31^2(n-1) + 31(j-1) + j), K(1,j) = E(K, 31(n-1) + j), K(i +
1,j) = E(K(i, j), U9i, j)), i = 1,...,30, j = 1,...,31. Ключи из 31
строки ключевой таблицы называют конечными; они передаются
получателю заранее. Получатель може потребовать доказательства их
аутентичности путем помещения в общедоступный список. Кроме того,
необходимо иметь 31 несекретный ключ К,...,К, которые
помещаются в общедоступный список. Затем для каждого сообщения М
вычисляется код сжатия C (M) и тридцать одно кодовое слово С =
E(K, C (M)),...,C = E(K, C (M)). Кодовые слова С,...,C
упорядочиваются в возрастающем порядке в строку С,...,C, а
номера ключей цифровой подписи образуются строками как ключис
номерами (i(1),1),...,(i(31),31) соответственно. Ключи,
находящиеся в этих позициях, передаются получателю, который
выполняет за исключением одного шага те же шаги, что и
отправитель. Получатель вычисляет код сжатия сообщения М. Затем
он вычисляет и сортирует кодовые слова, проверяет номера
полученных ключей; затем с помощью этих ключей и таблицы кодовых
слов восстанавливает 31 строку ключевой матрицы. На последнем
шаге он проверяет соответствие восстановленных ключей и матрицы
кодовых слов. Как видно, протоколы, основанные на симметричных
алгоритмах, являются одноразовыми и требуют смены хотя бы одного
параметра для каждого нового сообщения. В то же время алгоритмы с
открытым ключом позволяют использовать один параметр - открытый
ключ отправителя - для всех подписываемых сообщений. В заключение
следует отметить, что обзор в основном посвящен криптографии.
Рамки статьи не позволяют рассмотреть результаты другой части
криптологии - криптоанализа. Надеюсь, что представленная в обзоре
информация дает начальное понятие об этой замечательной области
прикладной математики, выдвигающей целый ряд чисто математических
проблем.
http://users. /~batmanb/box/1/29.shtml
57. Проблемы безопасности программного обеспечения критических систем
1. ПРОБЛЕМЫ БЕЗОПАСНОСТИ ПРОГРАММНОГО ОБЕСПЕЧЕНИЯ Большинство
ученых и специалистов-практиков, работающих в области создания
оружия и военной техники за рубежом, отмечают непрерывное
|
Из за большого объема этот материал размещен на нескольких страницах:
1 2 3 |
