Лекции по теории передачи информации

Подождите немного. Документ загружается.

можно.

Однако если удается получить некоторое число двоичных символов ис-

ходного текста и соответствующих им двоичных символов криптограммы, то

сообщение нетрудно раскрыть, так как преобразование, осуществляемое при

гаммировании, является линейным. Для полного раскрытия достаточно всего

n, где n – число разрядов регистра, формирующего псевдослучайную последо-

вательность двоичных символов зашифрованного и соответствующего ему ис-

ходного текста.

6.5.4.Стандарт шифрования данных DES (Data Encryption Standart) – госу-

дарственный стандарт США. Cтандарт DES стал одним из первых «открытых»

шифроалгоритмов. Все схемы используемые для его реализации, были опубли-

кованы и тщательно проверены. Секретным был только ключ, с помощью кото-

рого осуществляется кодирование и декодирование информации.

Алгоритм DES базируется на научной работе Шеннона 1949 г., связавшей

криптографию с теорией информации. Шеннон выделил два общих принципа

используемых в практических шифрах рассеивание и перемешивание. Рассеи-

ванием он назвал распространение влияния одного знака открытого текста на

множество знаков шифротекста, что позволяет скрыть статистические свойства

открытого текста. Под перемешиванием Шеннон понимал использование взаи-

мосвязи статистических свойств открытого и шифрованного текста. Однако

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

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

принята идея использовать произведение простых шифров, каждый из которых

вносит небольшой вклад в значительное суммарное рассеивание и перемеши-

вание.

В составных шифрах в качестве элементарных составляющих чаще всего

используются простые подстановки и перестановки. При многократном чере-

довании простых перестановок и подстановок можно получить очень стойкий

шифр (криптоалгоритм) с хорошим рассеиванием и перемешиванием.

Стандарт шифрованных данных DES – один из наиболее удачных приме-

ров криптоалгоритма, разработанного в соответствии с принципами рассеива-

ния и перемешивания. В нем открытый текст, криптограмма и ключ являются

двоичными последовательностями длиной соответственно

М = 64, N = 64,

К = 56 бит. Криптоалгоритм DES представляет собой суперпозицию элемен-

тарных шифров, состоящую из 16 последовательных шифроциклов, в каждом

из которых довольно простые перестановки с подстановками в четырехбитовых

группах

В каждом проходе используются лишь 48 бит ключа, однако они выби-

раются внешне случайным образом из полного 56

-битового ключа.

Операции шифрования и дешифрования осуществляются по схеме, пред-

ставленной на рис. 6.3.

Рис. 6.3. Шифратор (дешифратор) в стандарте DES

Входной регистр

сдвига

Регистр ключа

(56+8) бит

Блок шифровки

(дешифрования)

Генератор

субключей

Регистр сдвига

Вход

64 бит

56 бит

64 бит

16 субключей

по 48 бит

Выход

Перед началом шифрования в специализированный регистр устройства через

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

ется для генерации субключей, а 8 являются проверочными. Ключ из устройст-

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

внутри устройства. При этом ключ, вводимый в устройство, шифруется ранее

использовавшимся ключом и затем через

выходной регистр вводится в специа-

лизированный регистр в качестве нового ключа. Шестнадцать субключей по 48

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

рования блока из 64 символов, поступающих во входной регистр устройства.

Шифрование осуществляется из 16 логически идентичных шагов, на каждом из

которых используется один из субключей.

Процесс дешифрования выполняется по тому

же алгоритму, что и процесс

шифрования, с той лишь разницей, что субключи генерируются в обратном по-

рядке.

Алгоритм DES используется как для шифрования, так и для установления под-

линности (аутентификации) данных.

6.5.5. ГОСТ 28147-89 – стандарт на шифрование данных. В Республике Бе-

ларусь установлен единый алгоритм криптографического преобразования дан-

ных для систем обработки информации в сетях ЭВМ, отдельных вычислитель-

ных комплексах и ЭВМ, который определяется ГОСТ 28147-89.

Алгоритм криптографического преобразования данных предназначен для

аппаратной или программной реализации, удовлетворяет криптографическим

требованиям и не накладывает ограничений на степень секретности защищае-

мых сообщений (информации

). Из-за сложности этого алгоритма здесь будут

приведены только основные его концепции. Чтобы подробно изучить алгоритм

криптографического преобразования, следует обратиться к ГОСТ 28147-89 .

Приведенный ниже материал должен использоваться лишь как ознакомитель-

ный.

При описании алгоритма приняты следующие обозначения. Если

L и

R – это последовательности бит, то LR будет обозначать конкатенацию после-

довательностей

L и R. Под конкатенацией последовательностей L и R понима-

ется последовательность бит, размерность которой равна сумме размерностей

R. В этой последовательности биты последовательности R следуют за битами

последовательности

L. Конкатенация битовых строк является ассоциативной,

т.е. запись

ABCDE обозначает, что за битами последовательности А следуют

биты последовательности

В, затем С и т.д.

Символом (+) обозначается операция побитового сложения по модулю 2,

символом [+] – операция сложения по модулю 2

двух 32-разрядных чисел.

Числа суммируются по следующему правилу:

.2если,2][

;2если,][

3232

≥+−+=+

<++=+

BABABA

Символом {+} обозначается операция сложения по модулю 2

– 1 двух

32-разрядных чисел. Правила суммирования чисел следующие:

.12если),12(}{

;12если,}{

3232

−≥+−−+=+

−<++=+

BABABA

Алгоритм криптографического преобразования предусматривает несколь-

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

ключ, который имеет размерность 256 бит и представляется в виде восьми 32-

разрядных чисел

X(i). Если обозначить ключ через W, то

W = Х(7)Х(6)Х(5)Х(4)Х(3)Х(2)Х(1)Х(0).

Расшифрование выполняется по тому же ключу, что и зашифрование, но

этот процесс является инверсией процесса зашифрования данных.

Первый и самый простой режим –замена. Открытые данные, подлежащие

зашифрованию, разбивают на блоки по 64 бит в каждом, которые можно обо-

значить

T(j). Очередная последовательность бит T(j) разделяется на две после-

довательности

В(0) (левые или старшие биты) и A(0) (правые или младшие би-

ты), каждая из которых содержит 32 бита. Затем выполняется итеративный

процесс шифрования, который описывается следующими формулами:

)),31())(0(])[31(()32(

);31()32(

32при

);1()(

));1())((])[1(()(

32;31,...,26,25при

);1()(

));1())((])[1(()(

)8)(mod1(;24,...,2,1при

BXAfB

iAiB

iBjXiAfiA

iAiB

iBjXiAfiA

iji

++=

−=

−++−=

−==

−=

−++−=

−

где

i обозначает номер итерации (i = 1, 2,…, 32).

Функция

f называется функцией шифрования. Ее аргументом является

сумма по модулю 2

числа А(i), полученного на предыдущем шаге итерации, и

числа

X(j) ключа (размерность каждого из этих чисел равна 32 знакам).

Функция шифрования включает две операции над полученной 32-

разрядной суммой. Первая операция называется подстановкой

К. Блок подста-

новки

K состоит из восьми узлов замены K(1)...K(8) с памятью 64 бит каждый.

Поступающий на блок подстановки 32-разрядный вектор разбивается на восемь

последовательно идущих 4-разрядных векторов, каждый из которых преобразу-

ется в 4-разрядный вектор соответствующим узлом замены, представляющим

собой таблицу из шестнадцати целых чисел в диапазоне 0...15.

Входной вектор определяет адрес строки в таблице, число из которой яв-

ляется выходным

вектором. Затем 4-разрядные выходные векторы последова-

тельно объединяются в 32-разрядный вектор. Таблицы блока подстановки

К со-

держат ключевые элементы, общие для сети ЭВМ и редко изменяемые.

Вторая операция – циклический сдвиг влево 32-разрядного вектора, полу-

ченного в результате подстановки

К 64-разрядный блок зашифрованных дан-

ных

представляется в виде:

= A(32)B(32).

Остальные блоки открытых данных в режиме простой замены зашифровы-

ваются аналогично.

Следует иметь в виду, что режим простой замены допустимо использовать

для шифрования данных только в ограниченных случаях.

К этим случаям относится выработка ключа и зашифрование его с обеспе-

чением имитозащиты для передачи по каналам связи или хранения в памяти

ЭВМ.

Следующий режим шифрования называется режимом гаммирования. От-

крытые данные, разбитые на 64-разрядные блоки

Т(i) (i =1, 2,..., m, где m опре-

деляется объемом шифруемых данных), зашифровываются в режиме гаммиро-

вания путем поразрядного сложения по модулю 2 с гаммой шифра Г

, которая

вырабатывается блоками по 64 бит, т.е.

)).(),...,(),...,2(),1(( mÃiÃÃÃÃ

Число двоичных разрядов в блоке

Т(т) может быть меньше 64, при этом

неиспользованная для шифрования часть гаммы шифра из блока

Г(m) отбрасы-

вается.

Уравнение зашифрования данных в режиме гаммирования может быть

представлено в следующем виде:

).())(())()(}){1(,])[1(()(

iTiÃiTCiZCiYAiØ +

−

+−=

В этом уравнении

Ш(i) обозначает 64-разрядный блок зашифрованного

текста;

А(-) – функцию шифрования в режиме простой замены (аргументами

этой функции являются два 32-разрядных числа);

и С

– константы, задан-

ные в обязательном приложении 2 к ГОСТ 28147-89. Величины

У(-) и Z(•) опре-

деляются итерационно по мере формирования гаммы следующим образом

(

Y(0), Z(0)) = A(S), где S – 64-разярдная двоичная последовательность (синхро-

посылка)

,}){1(,])[1())(),((

CiZCiYiZiY

−

где

i = 1, 2,…, m.

Расшифрование данных возможно только при наличии синхропосылки, ко-

торая не является секретным элементом шифра и может храниться в памяти

ЭВМ или передаваться по каналам связи вместе с зашифрованными данными.

Режим гаммирования с обратной связью очень похож на режим гаммиро-

вания Как и в режиме гаммирования, открытые данные, разбитые на 64-

разрядные

блоки T(i) (i = 1, 2,..., m, где m определяется объемом шифруемых

данных), зашифровываются путем поразрядного

)).(),...,(),...,2(),1(( mÃiÃÃÃÃ

сложения по модулю 2 с гаммой шифра Г

, которая вырабатывается блоками

по 64 бит.

Число двоичных разрядов в блоке

Т(т) может быть меньше 64, при этом

неиспользованная для шифрования часть гаммы шифра из блока

Г(m) отбрасы-

вается.

Уравнение зашифрования данных в режиме гаммирования с обратной свя-

зью для

г = 2,3,..., то может быть представлено в следующем виде:

),())(())())(1(()(

);1())(1()1())(()1(

iTiÃiÒiØAiØ

+=+−=

где Ш(i) обозначает 64-разрядный блок зашифрованного текста; A(-) – функ-

цию шифрования в режиме простой замены.

Аргументом функции на первом шаге итеративного алгоритма является 64-

разрядная синхропосылка, а на всех последующих – предыдущий блок зашиф-

рованных данных

Ш(i – 1).

В ГОСТ 28147-89 определяется процесс выработки имитовставки, который

единообразен для любого из режимов шифрования данных. Имитовстав-

ка – это блок из

р бит (имитоставка И

), который вырабатывается либо перед

шифрованием всего сообщения, либо параллельно с шифрованием по блокам.

Первые блоки открытых данных, которые участвуют в выработке имитовстав-

ки, могут содержать служебную информацию (например адресную часть, вре-

мя, синхропосылку) и не зашифровываться. Значение параметра

р (число дво-

ичных разрядов в имитовставке) определяется криптографическими требова-

ниями с учетом того, что вероятность навязывания ложных помех равна 1/2

Для получения имитовставки открытые данные представляются в виде 64-

разрядных блоков

T(i) (i = 1, 2 m, где m определяется объемом шифруемых

данных). Первый блок открытых данных

Т(1) подвергается преобразованию,

соответствующему первым 16 циклам алгоритма зашифрования в режиме про-

стой замены, причем в качестве ключа для выработки имитовставки использу-

ется ключ, по которому шифруются данные

Полученное после 16 циклов работы 64-разрядное число суммируется по

модулю 2 с вторым блоком открытых данных

Т(2). Результат суммирования

снова подвергается преобразованию, соответствующему первым 16 циклам ал-

горитма зашифрования в режиме простой замены.

Полученное 64-разрядное число суммируется по модулю 2 с третьим бло-

ком открытых данных

Т(3) и т д. Последний блок Т(m), при необходимости до-

полненный до полного 64-разрядного блока нулями, суммируется по модулю 2

с результатом работы на шаге

m-1, после него зашифровывается в режиме про-

стой замены по первым 16 циклам работы алгоритма. Из полученного 64-

разрядного числа выбирается отрезок

длиной р бит.

Имитовставка

передается по каналу связи или в память ЭВМ после за-

шифрованных данных. Поступившие зашифрованные данные расшифровыва-

ются и из полученных блоков открытых данных

Т(i) вырабатывается имитов-

ставка

, которая затем сравнивается с имитовставкой И

, полученной из ка-

нала связи или из памяти ЭВМ В случае несовпадения имитовставок все рас-

шифрованные данные считают ложными.

6.5.6 Криптографические системы с открытым ключом. Наиболее перспек-

тивными системами криптографической защиты данных являются системы с

открытым ключом. В таких системах для зашифрования данных используется

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

и может быть опубликован для использования всеми пользователями системы,

которые зашифровывают данные. Расшифрование данных с помощью извест-

ного ключа невозможно. Для

расшифрования данных получатель зашифрован-

ной информации использует второй ключ, который является секретным. Разу-

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

[12].

В настоящее время наиболее развитым методом криптографической защи-

ты информации с известным ключом является RSA (назван так по начальным

буквам фамилий ее изобретателей Rivest, Shamir и Adleman). При рассмотрении

метода RSA необходимо вспомнить некоторые школьные термины.

Под простым числом понимают такое число, которое делится только на 1 и

на само себя. Взаимно простыми числами называют такие числа, которые не

имеют ни одного общего делителя, кроме 1. Под результатом операции

zmod

понимают остаток от целочисленного деления

i на j.

Чтобы использовать алгоритм RSA, надо сначала сгенерировать открытый

и секретный ключи, выполнив следующие шаги.

1. Выбрать два очень больших простых числа

р и q.

2. Определить

п как результат умножения р на q(n = pq).

3. Выбрать большое случайное число d. Оно должно быть взаимно про-

стым с результатом умножения (

р - 1)(q - 1)

4. Определить такое число е, для которого является истинным следующее

соотношение:

edmod((p - 1)(q - 1)) = 1.

5. Назвать открытым ключом числа

е и n, а секретным ключом – числа

d и n.

Далее, чтобы зашифровать данные по известному ключу {

е, n}, необходи-

мо разбить шифруемый текст на блоки, каждый из которых может быть пред-

ставлен в виде числа

М(i) = 0, 1 n – 1, зашифровать текст, рассматриваемый как

последовательность чисел M(i) по формуле ).mod()()( niMiC

Чтобы расшифровать эти данные, используя секретный ключ {d, n}, необ-

ходимо выполнить следующие вычисления.

В результате

будет получено множество чисел

М(i), которое представляет собой исходный

текст.

).mod()()( niCiM

Приведем простой пример использования метода RSA для шифрования со-

общения «ЕДА» Для простоты будем использовать очень маленькие числа (на

практике используются намного большие числа):

1. Выберем

р = 3 и q = 11.

2. Определим

п = 3·11 = 33.

3. Найдем (

р–1)(q–1) = 20. Следовательно, в качестве d выберем любое

число, которое является взаимно простым с 20, например

d = 3.

4. Выберем число

е. В качестве такого числа может быть взято любое чис-

ло, для которого удовлетворяется соотношение

е·3mod(20) = 1, например е = 7.

5. Представим шифруемое сообщение как последовательность целых чисел

в диапазоне 0...32. Пусть буква

Е изображается числом 6, буква Д – числом 5, а

буква

А – числом 1. Тогда сообщение можно представить в виде последова-

тельности чисел 651. Зашифруем сообщение, используя ключ {7,33}:

= 6

mod(33) = 279936 mod(33) = 30; С

= 5

mod(33)

78125

mod(33)= 14;

= 1

mod(33) = 1 mod(33) = 1.

Попытаемся расшифровать сообщение (30, 14, 1), полученное в результате

зашифрования по известному ключу, на основе секретного ключа {3,33} –

= 30

mod(33) = 27000 mod(33) = 6; М

= 14

mod(33) = 2744mod(33) = 5;

= 1

mod(33) = 1 mod(33) = 1.

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

ное сообщение «ЕДА».

Криптостойкость алгоритма RSA основывается на предположении, что ис-

ключительно трудно определить секретный ключ по известному, поскольку для

этого необходимо решить задачу о существовании делителей целого числа.

Данная задача не имеет до настоящего времени эффективного (полиномиально-

го) решения. Более того, вопрос

существования эффективных алгоритмов ре-

шения таких задач является открытым. В связи с этим для чисел, состоящих из

200 цифр (а именно такие числа рекомендуется использовать), традиционные

методы требуют выполнения огромного числа операций (около 10

6.5.7. Некоторая сравнительная оценка криптографических методов. Ре-

зультаты сравнительных оценок криптографических методов приведены в [12].

Метод шифрования с использованием датчика ПСЧ наиболее часто ис-

пользуется в программной реализации системы криптографической защиты

данных. Это объясняется тем, что, с одной стороны, он достаточно прост для

программирования, а с другой стороны, позволяет создавать алгоритмы с очень

высокой криптостойкостью. Кроме того, эффективность

данного метода шиф-

рования достаточна высока. Системы, основанные на методе шифрования с ис-

пользованием датчика ПСЧ, позволяют зашифровать в секунду от нескольких

десятков до сотен килобайт данных (здесь оценочные характеристики приведе-

ны для персональных компьютеров).

Основным преимуществом метода DES является то, что он является стан-

дартом. Как утверждает Национальное Бюро Стандартов

США, алгоритм обла-

дает следующими свойствами:

–

высоким уровнем защиты данных против дешифрования и возможной

модификации данных;

–

простотой в понимании;

–

высокой степенью сложности, которая делает его раскрытие дороже по-

лучаемой при этом прибыли;

–

метод защиты основывается на ключе и не зависит ни от какой «секрет-

ности» алгоритма;

экономичен в реализации и эффективен в быстродействии.

Важной характеристикой этого алгоритма является его гибкость при реа-

лизации и использовании в различных приложениях обработки данных. Каж-

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

вывать отдельный

блок в зашифрованном сообщении и структуре данных. По-

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

ный доступ к зашифрованным данным. Ни временная, ни позиционная синхро-

низация для операция шифрования не нужны.

Алгоритм вырабатывает зашифрованные данные, в которых каждый бит

является функцией от всех битов открытых данных и всех битов ключа. Разли-

чие лишь в одном бите данных дает в результате равные вероятности измене-

ния для каждого

бита зашифрованных данных.

Конечно, эти свойства DES выгодно отличают его от метода шифрования с

использованием датчика ПСЧ, поскольку большинство алгоритмов шифрова-

ния, построенных на основе датчиков ПСЧ, не характеризуются всеми преиму-

ществами DES. Однако и DES обладает рядом недостатков

Самым существенным недостатком DES специалисты признают размер

ключа, который считается слишком малым. Стандарт не является

неуязвимым,

хотя и очень труден для раскрытия. Для дешифрования сообщения методом

подбора ключей достаточно выполнить 2

операций расшифрования (т.е. всего

около 7,6·10

операций). Хотя в настоящее время нет аппаратуры, которая мог-

ла бы выполнить в обозримый период времени подобные вычисления, никто не

гарантирует, что она не появится в будущем. Некоторые специалисты предла-

гают простую модификацию для устранения этого недостатка исходный текст

зашифровывается сначала по ключу

, а затем по ключу K

и, наконец по клю-

чу

. В результате время, требующееся для дешифрования, возрастает до 2

168

операций (приблизительно, до 10

операций).

Еще один недостаток метода DES заключается в том, что отдельные блоки,

содержащие одинаковые данные (например пробелы), будут одинаково выгля-

деть в зашифрованном тексте, что с точки зрения криптоанализа неправильно.

Метод DES может быть реализован и программно. В зависимости от быстро-

действия и типа процессора персонального компьютера программная система,

шифрующая данные с

использованием метода DES, может обрабатывать от не-

скольких килобайт до десятков килобайт данных в секунду. В то же время не-

обходимо отметить, что базовый алгоритм все же рассчитан на реализацию в

электронных устройствах специального назначения.

Алгоритм криптографического преобразования, определяемый ГОСТ

28147-89, свободен от недостатков стандарта DES и в то же время обладает

всеми

его преимуществами. Кроме того, в стандарт уже заложен метод, с по-

мощью которого можно зафиксировать необнаруженную случайную или

умышленную модификацию зашифрованной информации.

Однако у алгоритма есть очень существенный недостаток, который заклю-

чается в том, что его программная реализация очень сложна и практически ли-

шена всякого смысла из-за крайне низкого быстродействия

. По оценкам авто-

ров, за 1 с на персональном компьютере может быть обработано всего лишь не-

сколько десятков (максимально сотен) байт данных, а подобная производитель-

ность вряд ли удовлетворит кого-либо из пользователей. Хотя сейчас уже раз-

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

ского преобразования данных, которые демонстрируют приемлемую произво-

дительность (около 70 Кбайт/с для IBM PC с тактовой частотой 12 МГц).

Теперь о методе RSA. Он является очень перспективным, поскольку для

зашифрования информации не требуется передачи ключа другим пользовате-

лям. Это выгодно отличает его от всех вышеописанных методов криптографи-

ческой защиты данных. Но в настоящее время к этому методу относятся веро-

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

найден эффективный алгоритм

определения делителей целых чисел, в резуль-

тате чего метод шифрования станет абсолютно незащищенным.

В остальном метод RSA обладает только достоинствами. К числу этих дос-

тоинств следует отнести очень высокую криптостойкость, довольно простую

программную и аппаратную реализации. Правда, использование этого метода

для криптографической защиты данных неразрывно связано с высоким уровнем

развития вычислительной

техники.

Кроме метода RSA есть еще несколько криптосистем с открытым ключом,

в той или иной мере распространенных в теоретическом или практическом пла-

не, например система Эль-Гамаля, основанная на трудности вычисления дис-

кретных логарифмов в конечных полях. Мак-Элис предложил криптосистему,

основанную на кодах, исправляющих ошибки. Вычисления в этой системе реа-

лизуются

в несколько раз быстрее, чем в системе RSA.

6.6. Электронная цифровая подпись

6.6.1. Аутентификация электронных документов. Безбумажная информати-

ка дает ряд преимуществ при обмене документами (приказами, распоряжения-

ми, письмами, постановлениями и т.д.) по сети связи или на машинных носите-

лях. В этом случае временные затраты (распечатка, пересылка, ввод полученно-

го документа с клавиатуры) существенно снижаются, убыстряется поиск доку-

ментов, снижаются затраты на их хранение и т.д. Но при этом возникает про-

блема аутентификации автора документа и самого документа (т.е. установление

подлинности подписи и отсутствия изменений в полученном документе). Эти

проблемы в обычной (бумажной) информатике решаются за счет того, что ин-

формация в документе жестко связана с физическим носителем (бумагой). На

машинных носителях такой связи нет.

Проблема аутентификации является актуальной в вычислительных сетях,

электронных системах управления и вообще там, где необходимо удостове-

риться в подлинности полученного по каналам связи или на машинных носите-

лях сообщения (документа) [16].

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

кация абонента, аутентификация принадлежности абонента к заданной группе,

аутентификация хранящихся на машинных носителях документов.

Остановимся на аутентификации документов (или файлов) как на более

важной. Если рассматривается случай обмена секретными документами (воен-

ная или дипломатическая связь), то с большой степенью уверенности можно

предположить, что обмен осуществляют доверяющие и достойные доверия сто-

роны. Однако возможно, что обмен находится под наблюдением и управлением