A.F.Ronzhin.  Problems  of  Security  in  Information  Processing
Systems//В  сб.:  АННОТАЦИЯ.
До настоящего времени в нашей стране проблемы защиты информации в
ЭВМ  практически  не  обсуждались  в печати. Цель данного доклада
познакомить    участников    конференции    с    рядом   примеров
математических  и практических проблем, которые необходимо решить
для  реализации надежной секретной системы связи. В данном обзоре
рассмотрены   методы   защиты   данных   в   ЭВМ,  основные  идеи
организации,   построения   и   использования   криптографических
средств.   В   данный   обзор  также  включено  краткое  описание
криптографических возможностей по аутентификации данных, проверке
подписи  и  аутентификации  пользователей.  1.  ВВЕДЕНИЕ  Широкое
распространение  ЭВМ  и  расширение  диапазона  их  использования
приводят  к  крайней  необходимости  защиты  информации  в  ЭВМ и
вызывают  значительный  интерес  во  всем мире к методам защиты и
проблемам  стандартизации,  особенно в наши дни, когда информация
приобретает  статус товара с определенной ценностью.Необходимость
защиты  данных  исходит  из  требований  обеспечения сохранности,
надежности   и   секретности  хранимой  информации  нессмотря  на
действия   неопытных   пользователей,   сбои   или  неисправности
аппаратуры,  либо  вмешательство  нарушителей.  Здесь и далее под
нарушителями  понимаются  как  лица, желающие незаконно получить,
разрушить    или    изменить    хранимую    информацию,   так   и
непрофессионалы, создающие компьютерные вирусы, чье вмешательство
в   ЭВМ  приводит  к  частичной  или  полной  потере  информации.
Безопасность  данных  достигается  сочетанием  ряда  мер, которые
условно можно разбить на четыре группы, а именно организационные,
технические,  программные  и криптологические методы. Программные
методы    защиты    информации    направлены    на    обеспечение
дифференцированного  доступа  к  ЭВМ,  т.е. это такие системы ПО,
которые  гарантируют, что каждый пользователь имеет доступ только
к   разрешенным  для  него  данным.  Методы  защиты,  реализуемые
программно,  хорошо  известны  всем пользователям; это пароли для
ограничения   доступа   и   системы   привилегий  для  доступа  к
определенным   ресурсам  и  устройствам  ЭВМ.  Парольная  система
выполняет    функции   аутентификации   с   целью   идентификации
пользователя  или  элемента  оборудования,  а также определения и
контроля   (с   помощью  функции  контроля  доступа)  ресурсов  и
устройств  ЭВМ,  которые  могут  быть предоставлены пользователю.
Обычно  для  регистрации  и  анализа  событий  в ЭВМ используется
аудиторский  контроль,  который  может  быть  полезен  для защиты
системы.   Аудиторский   контроль  предназначен  для  обнаружения
попыток  несанкционированных действий и выявления ситуаций, когда
совокупные   действия   многих  пользователей  могут  привести  к
нежелательным  последствиям. Защита вычислительных сетей является
сложной задачей ввиду противоречия между требованием к открытости
системы для несложного общего пользования и ограниченным доступом
для   защиты.  К  сожалению,  программные  методы  защиты  весьма
уязвимы,  так  как незначительная ошибка может вызвать изменения,
сводящие  на  нет  эффективность  защиты. Кроме того, принимая во
внимание    организационные    принципы    хранения   информации,
высококвалифицированные  специалисты могут получить любые данные,
не    защищенные    специальными    аппаратными    способами    и
организационными  мерами.  По  этой причине необходимо обеспечить
нечитаемость   данных,   которые   могут  быть  случайно  вызваны
несанкционированным     пользователем.     Это     обеспечивается
криптографическими  средствами, обеспечивающими нечитаемость; они
используются  практически  во всех методах защиты - от шифрования
самой   информации  до  организации  парольных  систем,  контроля
доступа   и   др.   По  мнению  специалистов  национального  бюро
стандартов  США  шифрование  -  это  единственный  надежный метод
защиты  данных  при их передаче и хранении на различных носителях
данных  (Data  Encryption,  1978; Konheim et al., 1980; With data
encryption,  1980). Этим объясняется большой интерес к шифрованию
информации.  Крипттографические  методы  не  исключают  полностью
технические  и  организационные  меры, но сводят их к минимуму. В
последние   годы   меры  технической  защиты  часто  основаны  на
криптографических  идеях.  Для  шифрования  и дешифрования данных
требуются  соответствующие  методы  и устройства. Более того, они
должны зависеть от времени, т.е. метод шифрования должен зависеть
от  некоторой  переменной,  называемой  криптографическим ключом.
Необходимо  вырабатывать,  распределять  и управлять ключами. Все
это образует систему шифрования, или криптосистему. Криптосистема
не  изолирована  от ЭВМ, а существует и работает в вычислительной
среде,  и,  следовательно,  требуются  протоколы,  описывающие  и
управляющие   использованием  криптографических  средств.  Однако
следует отметить, что не существует мер криптографической защиты,
которые  решают  такие  проблемы,  как  первоначальная  установка
ключей в терминал и центральные устройства информационной сети, а
также защита от непосредственного считывания ключей. Эти проблемы
необходимо  решать  аппаратными  и  организационными  мерами.  До
настоящего  времени  проблемы защиты информации в ЭВМ практически
не   обсуждались  в  печати.  Цель  данного  доклада  познакомить
участников   конференции   с   рядом  примеров  математических  и
практических  проблем,  которые  необходимо решить для реализации
надежной  секретной  системы  связи.  В данном обзоре рассмотрены
методы защиты данных в ЭВМ, основные идеи организации, построения
и использования криптографических средств, а также их зависимость
от  имеющихся у нарушителей технических устройств. В данный обзор
также   включено   описание   криптографических  возможностей  по
аутентификации   данных,   проверке   подписи   и  аутентификации
пользователей.  Более  подробное  обсуждение  защиты компьютерной
информации  можно  найти  в (Denning, 1983; Gasser, 1987; Special
issue  on  security  technology).  2. КРИПТОГРАФИЧЕСКИЕ АЛГОРИТМЫ
2.1.  Области  применения  и  основные типы алгоритмов ЭВМ широко
используются в современной криптологии и их развитие идет вровень
с    развитием    технологии    обработки   информации.   Широкое
распространение   криптографической   защиты   информации   стало
возможным  благодаря  разработке  алгоритмов  шифрования, которые
можно   реализовать  в  современных  компьютерных  системах.  При
обработке  информации в ЭВМ криптографическая защита используется
в  трех  областях: при передаче данных, при хранении информации и
для  аутентификации  пользователей  и информации. Наиболее широко
используется  шифрование при передаче данных по сетям связи и при
обработке   компьютерных   данных  в  распределенных  системах  и
вычислительных   сетях.   Другой   важной   областью   применения
криптографической защиты является шифрование хранимой информации;
в   этом   случае   должна   сохранятся   возможность   обработки
зашифрованных   данных.   Совместимость  шифрования  и  принципов
аутентификации   и   контроля  доступа  выдвигают  дополнительные
требования   к   криптографическим  преобразованиям.  Возможность
аутентификации   особенно   важна,  если  используются  удаленные
терминалы.  Процедуры  аутенификации  с помощью криптографических
средств  приобретают  дополнительную  важность  в связи с широким
распространением   электронной   почты   (передача   сообщений  и
документов  от  одного  компьютера  к другому по каналам связи) и
заключения  контрактов  с  помощью  компьютеров.  Знание  свойств
криптосистем,   приспособленных   для  компьютерного  применения,
является  необходимым  условием  использования  криптографических
методов   защиты   информации   в  ЭВМ  и  вычислительных  сетях.
Криптографические    методы    используются    для    обеспечения
безопасности информации путем преобразования данных (шифрования),
такого,   что   преобразованные   данные   (шифртекст)   не  дают
возможности несанкционированного восстановления открытого текста.
Криптосистема    состоит    из    обратимого   криптографического
преобразования   и   множества   ключей,  являющихся  параметрами
преобразования.   Знание  используемых  ключей  дает  возможность
дешифровать   шифртекст.  Схему  криптографической  защиты  можно
описать   следующим  образом.  Пусть  открытый  текст  написан  в
некотором  алфавите А={А ,...,А }, где m - это мощность алфавита.
Множество  открытых  текстов  Х - это множество слов Х ,...,Х над
алфавитом  А:  Х  =  {X ,...,X }, а множество шифртекстов Y - это
множество  слов Y ,...,Y над тем же алфавитом: Y = {Y ,...,Y }. В
качестве алфавита можно принять символы ASCII, буквы национальных
алфавитов,  двоичные  символы.  Шифрование  как криптографическое
преобразование  - это функция Е, которая каждому открытому тексту
Хi Х приписывает единственный элемент Yi Y, Yi= E(Xi), i=1,...,n.
Дешифрование - это функция D, обратная Е. Каждому шифртексту Yj Y
функция  D  функция  D  приписывает  единственный  элемент  Хj Х,
Хj=D(Yj), j=1,...,l. Таким образом, функция Е, называемая шифром,
с  множеством открытых текстов Х в качестве области определения и
множеством  шифртекстов Y в качестве области значений для каждого
элемента  Х  определяет единственный элемент Y. Общее число таких
функций равно l!/(l-n)!. пометим эти функции произвольным образом
элементами  множества  К.  Элементы  k K называют ключами и могут
рассматриваться   как   значения   криптографической  переменной.
Процесс  шифрования состоит из выбора k K и отображения открытого
текста при помощи функции Е в элемент множества Y. Выбранный ключ
k является секретным, но множество функций и соответствие между К
и  этим  множеством  несекретно.  Для  выбора множества функций и
множества  ключей К имеются определенные требования (Introduction
to  FFT  security,  1976; Шеннон, 1951), которые гарантируют, что
нарушители   не   смогут  восстановить  открытый  текст  и  найти
используемый  ключ  k  на  основе  шифртекста,  однако  здесь эти
условия     не    обсуждаются.    Рассмотрим    более    подробно
криптографические   функции   и   их  сильные  и  слабые  стороны
применительно  к  защите  информации в ЭВМ. Все криптографические
функции  можно  разделить  на  два  класса - блочное шифрование и
последовательное  шифрование.  2.2. Алгоритмы блочного шифрования
или  шифры  Блочные  шифры  преобразуют  входные двоичные векторы
длины    n    в    выходные    блоки   длины   m   (зашифрованные
последовательности) таким образом, что каждый бит выходного блока
зависит от каждого бита входного блока (Don, 1985). Для упрощения
предположим,  что  n=m.  Схему  блочного шифрования можно описать
следующим образом. Пусть выбран ключ k, тогда каждый входной блок
длины  n  преобразуется  в  блок  Y длины n шифртекста при помощи
функции  Е , Y = Ek(X), X = Dk(Y), где Dk - это функция, обратная
Еk.  Пусть {Ek, k K}={Dk, k K}, что обычно выполняется, тогда Dk=
Ek  и  Y  =  E(k,X),  X  =  E(k',E(k,X)).  Возможны две следующие
ситуации:  для  данного  k  легко вычисляются ключ k' и Еk , либо
вычисление  k' так же сложно, как восстановление соответствующего
открытого  текста  на  основе  данного  шифртекста Y. В последнем
случае  ключ  k  совместно  с  шифртекстом  Y  можно  передать по
несекретному   каналу.   Это   не   разрушает   криптосистему.  В
соответствии  с  этим  свойством  все  блочные  шифрсистемы можно
разделить  на  класс обычных процедур шифрования и класс процедур
шифрования  с  открытым  ключом.  Типичным  представителем класса
обычных  алгоритмов  является  алгоритм  DES,  обсуждаемый  ниже.
Обратимся ко второму классу алгоритмов. 2.3. Алгоритмы с открытым
ключом  Основная черта этих алгоритмов (Diffie and Hellman, 1976)
- использование несекретного ключа Еk для шифрования и секретного
ключа  Dk  для  дешифрования.  Такие  алгоритмы  имеют  следующие
свойства:  *  пользователи  могут эффективно вычислить ключи Ek и
Dk;  *  знание  Ek не дает возможности эффективно вычислить Dk; *
дешифрование,   последующее   шифрованию,   дает   первоначальную
информацию  X  = Dk(Ek(X)). Алгоритмы с открытым ключом построены
на   основе  известных  трудных  математических  проблем  высокой
сложности,    а   обычные   алгоритмы   реализуют   специфические
преобразования, трудные для анализа. При использовании алгоритмов
с  открытым ключом не требуется передача ключа Ek в зашифрованном
виде. Несмотря на существенные различия между классами алгоритмов
обычные  алгоритмы  можно  адаптировать  таким  образом,  что они
обеспечат  многие  полезные  свойства  процедур с открытым ключом
(Ehrsam  et  al.,  1978;  Zennon and Matyas, 1979; Zennon et al.,
1980,  1981,  1982). Рассмотрим два примера алгоритмов с открытым
ключом. 2.4. RSA-алгоритмы Алгоритмы шифрования с открытым ключом
Ривеста,  Шамира  и  Адельмана  (RSA)  основаны на том факте, что
разложение  большого  числа  на  множители является очень сложной
вычислительной задачей (Ore, 1948). Для определения RSA-алгоритма
необходимо  тщательно  выбрать  два  больших простых числа p и q,
которые  секретны.  Их  произведение  r=pq  несекретно,  но число
f(r0=(p-1)(q-1)  также  секретно.  По формуле Эйлера a = 1 mod r,
(1)  где  a  относительно  простое  с r, а f(r) - функция Эйлера.
Пусть  Ek*Dk=1  mod  f(r),  тогда,  как следует из (1), для любой
численной  записи  открытого текста Х X = X mod r. Следовательно,
информацию  можно шифровать и дешифровать по формулам Y = E(Ek,X)
=  X  mod  r,  X  =  D(Dk,Y)  = Y mod r. Таким образом, процедура
построения  и использования RSA-алгоритма следующая. 1. Случайным
образом  выбираются  два  секретных  простых  числа  p  и  q.  2.
Вычисляются    открытое    число    r=pq    и   секретное   число
f(r)=(p-1)(q-1).  3.  Выбирается число Ek, относительно простое с
f(r),  и вычисляется секретное Dk такое, что Ek*Dk=1 mod f(r). 4.
Открытый  текст  Х и шифртекст Y - это числа (возможно в двоичном
представлении)   из   множества   {0,1,...,r-1},  Y  =  X  mod  r
{0,1,...,r-1},   X  =  Y  mod  r  {0,1,...,r-1}.  Рассмотрим  ряд
математических  задач,  связанных  с  построением  RSA-алгоритма.
Первая  задача связана с выбором Ek и Dk, удовлетворяющих условию
3.  По  теореме  из теории чисел (Ore, 1948) соотношение Dk*x = 1
mod  f(r)  имеет  решение  тогда  и только тогда, когда Dk и f(r)
относительно  просты.  Следовательно,  для  выбора  Dk и Ek можно
применить  алгоритм  Евклида  для  нахождения  наибольшего общего
делителя.  Вторая  проблема  касается  количества  простых чисел.
Хорошо известно, что (x)log(x)/x - 1 при x , где (х) - количество
простых  чисел,  не больших x. таким образом, если p - 200-битное
двоичное  число, то количество таких простых чисел приблизительно
равно  10^58.  Нахождение  больших простых чисел является третьей
проблемой.  Такой  выбор требует проверки на простоту. В качестве
тестов  на  простоту можно использовать теорему Вильсона (Wilson)
(Ore,  1948), в которой говорится, что если p - простое число, то
(p-1)!  =  -1 mod p, а также простой факт, что p является простым
числом, если оно не делится на все целые числа, не превышающие p.
Существует  ряд  легко вычислимых методов, с высокой вероятностью
подтверждающих  простоту  (Solovay  and  Strassen,  1977). Другие
эффективно  вычислимые тесты на простоту описаны в (Miller, 1976;
Polland, 1974; Rabin, 1976). В последние годы проблемы, связанные
с  процедурами  с  открытым ключом, стали предметом значительного
интереса  у  математиков  и  криптологов  (Blackely and Blackely,
1978, 1979; DES, 1977; Davies et al., 1979; Hellman et al., 1976;
Herlestam,  1978; Meyer, 1978; Rivest, 1978a, 1978 b; Simmons and
Norris,  1977; Williams and Schmid, 1978). Из результатов (Rivest
et  al.,  1978) следует, что для системы RSA с блоками длиной 338
бит  требуется  такое же время для разложения на множители r, как
для  исчерпывающего перебора всех 2^56 ключей алгоритма DES. 2.5.
Ранцевые  алгоритмы Эти алгоритмы основаны на классической задаче
теории  чисел  (Merkle,  Hellman,  1978). Пусть X=(x(1),...,x(n))
будет  секретным  двоичным  вектором,  который  является открытым
текстом,  а A=(a(1),...,a(n)) будет несекретным вектором с целыми
компонентами.   Тогда   зашифрованная   информация  -  это  число
Y=(A,X)=a(1)x(1)  +...+  a(n)x(n).  Простота шифрования очевидна.
Возможность  восстановления  X  с  помощью  Y может быть получена
благодаря   соответствующему  выбору  A.  Единственной  проблемой
является   введение   секретного   значения,  позволяющего  легко
дешифровать   принятую  скрытую  информацию.  Это  можно  сделать
следующим      образом.      Выбирается      секретный     вектор
A'=(a'(1),...,a'(n))    такой,    что    a'(l+1)>a'(1)+...+a'(l),
l=1,...,n-1. Для такого вектора легко решается задача определения
X  из  Y'=(A',X)=a'(1)x(1)+...+a'(n)x(n),  поскольку x(n)=1, если
Y'>=a'(1)+...+a'(n-1), x(n-1)=1, если Y'-a'(n)>=a'(1)+...+a'(n-2)
и  т.д.  Ведем  секретные  взаимно простые числа r и t и найдем s
такое,  что  st=1  mod  r.  Теперь  шифрование можно организовать
следующим   образом.   Определим  несекретное  A  с  координатами
a(i)=a'(i)t  mod  r  и  выберем  Y=(A,X)  в  качестве шифртекста,
оставляя  все  сложности  дешифрования  на  A.  Для  дешифрования
преобразуем  Y  в Y'=Ys mod r и учитывая, что Y'=(A',X), уменьшим
сложность  восстановления  X.  Оценки  соответствующих сложностей
можно  найти  у  (Shamir, 1982). 2.6. Последовательное шифрование
Пусть   открытый  текст  будет  двоичной  последовательностью,  и
существуют  автономные  автоматы  A(k), k K, с выходным алфавитом
{0,1}.  Тогда  для  открытого текста X=(x(1),...,x(n)) и выходной
последовательности    R(k)=(r(1,k),...,r(n,k))    автомата   A(k)
шифртекст  Y=(y(1),...,y(n)) определяется как y(i)=x(i) + r(i,k),
i=1,...,n.   Обычно,  хотя  и  не  необходимо,  ключ  k  является
начальным  состоянием  автомата.  Поскольку  x(i)=y(i)  - r(i,k),
i=1,...,n,  шифрование  и дешифрование реализуются одной и той же
схемой.   Такая  схема  шифрования-дешифрования  имеет  следующие
важные  черты: если ключ k используется для шифрования нескольких
открытых  текстов (например, если открытый текст разбит на блоки,
и    каждый    блок    шифруется    отдельно    той    же   самой
последовательностью),  и один из этих открытых текстов становится
известным    нарушителю,    то    он    может    легко   получить
последовательность   R(k)=X+Y   и   затем   без  знания  ключа  k
дешифровать   все   остальные  записи,  добавляя  соответствующие
шифртексты  и  R(k).  Это происходит потому, что автомат A(k) для
одинаковых  начальных  состояний  каждый  раз выдает тот же самый
выход.  Этого  недостатка  можно  избежать, если каждый раз перед
шифрованием  изменять  начальное  состояние  автомата.  Начальным
состоянием  можно  управлять  с  помощью  некоторого параметра Z.
Параметр  вводится  только  для  перевода  автомата  с ключом k в
различные    начальные   состояния,   но   не   для   обеспечения
криптографической  надежности.  По этой причине требования к Z не
так  сильны,  как  к ключам K. 2.7. Алгоритм DES Опишем алгоритм,
известный  как  Data  Encryption  Standard  (Стандарт  шифрования
данных).   Перед   обсуждением   технической   стороны  процедуры
обратимся  к  законодательству  США  по  вопросам секретности и к
истории  разработки  DES.  Ясно,  что такая информация может быть
полезной   для   осуществления   организационных  мер  по  защите
информации.  Для сохранения тайны в системах обработки информации
необходимо   следовать   ряду  правил,  регулирующих  возможности
пользователей  по  выбору,  хранению  и  изменению  информации по
своему  желанию.  Кроме того, пользователи должны иметь авторское
право  на  свою  информацию.  В настоящее время в США эти правила
регулируются  актом  1974  года  (Privacy  Act, 1974). Касательно
криптографических  мер  защиты данных, их применение регулируется
актом  1997  года  (Public  Law 95-213). Более подробное описание
законодательства  США по защите вычислительных систем можно найти
в  (Hoffman,  1977). В 1973 году Национальное бюро стандартов США
опубликовало  статью  (Cryptographic Algorithms, 1973), в которой
предлагалось   разработать   унифицированный  криптоалгоритм  для
обработки   компьютерных   данных   в  коммерческой  и  оборонной
областях.  Были  сформулированы следующие требования к алгоритму:
1.   Алгоритм   должен   быть  полностью  описан  без  какой-либо
неопределенности. 2. Он должен обеспечить соответствующий уровень
безопасности,  который  можно  естественным  образом  оценить  по
времени  или  количеству операций, требуемых для раскола системы.
3.  Его стойкость должна быть основана только на стойкости ключа.
4.    Он    может    без   каких-либо   ограничений   применяться
пользователями.  6  августа  1974  года  IBM предложила алгоритм,
разработанный   научной   группой  под  руководством  W.L.Tuchman
(Ehrsan  et  al.,  1976),  как  удовлетворяющий этим требованиям.
Алгоритм  основывался  на  криптосистеме  Lucifer  (IBM  Research
Report,   1971),   разработанной   Файстелем   (Feistel,   1974).
Американским   экспертом   в  криптологии  и  безопасности  связи
является  Агентство национальной безопасности (АНБ). Национальное
бюро  стандартов  совместно с АНБ оценило стойкость предложенного
алгоритма  (Report  Workshop  on  Cryptography,  1977), который и
составил  основу  DES, опубликованного АНБ 17 марта 1975 года; 15
июля   1975  года  алгоритм  был  официально  принят  в  качестве
федерального   стандарта.  DES  позволено  применять  федеральным
агентствам и Государственному департаменту для шифрования данных,
не  попадающих под классификацию Акта о национальной безопасности
(1974)  и  Акта  о  ядерной  энергии  (1954).  Более того, он был
рекомендован  для  применения  промышленным  корпорациям. DES был
адаптирован  Американским  национальным  институтом по стандартам
(АНИС)  к  требованиям  CCIP(X3) и принят в качестве стандартного
промышленного  алгоритма  DEC  X3.92 (American National Standard,
1981).  Требования  к  стойкости, физической и электронной защите
DES-оборудования были одобрены в (Proposed Federal Standard 1026,
1980;  Proposed  Federal Standard 1027, 1980). Там же можно найти
более  подробную  информацию  о  разработке  DES. В (Unclassified
Summary,  1978) даны следующие официальные характеристики DES: 1.
DES  более,  чем  приемлем  в своих областях применения. 2. IBM -
изобретатель  и  создатель  DES.  3.  АНБ  не принимало участия в
разработке.  4.  АНБ  проверило  стойкость  DES против атак всеми
известными  статистическими  методами.  5.  АНБ рекомендовало ФБР
использоватиь  DES  для  передачи  данных  с  помощью электронных
средств. Алгоритм DES - это типичный представитель класса блочных
шифров.   Дадим   его  описание,  следуя  (DES,  1977).  Алгоритм
используется  для  шифрования и дешифрования блоков данных длиной
64  бита и управляется ключом длиной 64 бита. Как видно из рис.1,
шифрование  выполняется следующим образом. 64 бита входного блока
преставляются  в соответствии с начальной перестановкой (НП). Эта
перстановка ставит на первую позицию 58-ой бит, на вторую позицию
-  50-ый  бит  и  т.д.  Выход  этой  перестановки  идет  на  вход
процессора,  который  зависит от ключа. Выход процессора называют
предварительным  выходом;  он  переставляется  в  соответствии  с
подстановкой,  обратной  НП.  Процессор  выполняет  16 итераций с
функцией  f,  которая зависит от двух 32-битных блоков предыдущей
итерации и 48 бит ключа. Функция f называется функцией шифрования
и  принимает  значения  на множестве 32-битных блоков. Для каждой
итерации  64 бита входного блока разбиваются на 32-битные блоки L
и  R.  Пусть  k  будет 48-битным блоком, выбираемым из 64-битного
блока  ключа, тогда выход итерации состоит из 32-битного блока L'
и  32-битного  блока  R'  таких,  что L'=R, R'=L+f(R,k). В каждой
итерации  ключ  k  выбирается  из  ключевой последовательности K,
которая является 64-битным блоком. Выбор выполняется функцией Ks,
зависящей    от    числа    итераций    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 = 10 51 ... 41 22 28
...    31    k    =    2    43    ...    33    14   20   ...   23
..................................  k  = 18 59 ... 49 30 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).
 

Оставит комментарий