Современные симметричные криптосистемы

3. Современные симметричные криптосистемы

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

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

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

         В составных шифрах в качестве простых шифров чаще всего используются простые перестановки и подстановки. При перестановке просто перемешивают символы открытого текста, причем конкретный вид перемешивания определяется секретным ключом. При подстановке каждый символ открытого текста заменяют другим символом из того же алфавита, а конкретный вид подстановки также определяется секретным ключом. Следует заметить, что в современном блочном шифре блоки открытого текста и шифртекста представляют собой двоичные последовательности обычно длиной 64 бита. В принципе каждый блок может принимать 2⁶⁴ значений. Поэтому подстановки выполняются в очень большом алфавите, содержащем до 2⁶⁴  10¹⁹ "символов".

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

3.1 Классическая сеть Фейстеля

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

         Структура классической сети Фейстеля показана на рис. 3.1

Рекомендуемые материалы

.

Рисунок 3.1 – Структура классической сети Фейстеля

         Независимые потоки информации, порожденные из исходного блока, называются ветвями сети. В классической схеме Фейстеля их две. Величины V_i называются параметрами сети, обычно это функции от материала ключа. Функция F называется образующей. Действие, состоящее из однократного вычисления образующей функциии и последующего наложения ее результата на другую ветвь с обменом местами называется циклом или раундом сети Фейстеля. Оптимальное число раундов K − от 8 до 32.

         Увеличение количества раундов значительно повышает криптостойкость любого симметричного блочного шифра. Благодаря этой особенности сети Фейстеля получили широкое распространение – при обнаружении слабого места в алгоритме почти всегда достаточно не переписывая сам алгоритм увеличить количество раундов на 4-8.

         В соответствии с описанной методикой построены блочные симметричные криптоалгоритмы DES, IDEA, ГОСТ 28147-89 и ряд других алгоритмов.

3.2. Американский стандарт шифрования данных DES

            Стандарт шифрования данных DES (Data Encryption Standard) опубликован в 1977 г. Национальным бюро стандартов США. Стандарт DES предназначен  для защиты от несанкционированного доступа к важной, но несекретной информации в государственных и коммерческих организациях США. Алгоритм, положенный в основу стандарта, распространялся достаточно быстро, и уже в 1980 г. был одобрен Национальным институтом стандартов и технологий США (НИСТ). С этого момента DES превращается в стандарт не только по названию (Data Encryption Standard), но и фактически. Появляются программное обеспечение и специализированные микроЭВМ, предназначенные для шифрования и расшифрования информации в сетях передачи данных.

К настоящему времени DES является наиболее распространенным алгоритмом, используемым в системах защиты коммерческой информации. Более того, реализация алгоритма DES в таких системах становится признаком хорошего тона.

Основные достоинства алгоритма DES:

· используется только один ключ длиной 56 бит;

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

· относительная простота алгоритма обеспечивает высокую скорость обработки;

· достаточно высокая стойкость алгоритма.

         Алгоритм DES использует комбинацию подстановок и перестановок. DES осуществляет шифрование 64-битовых блоков данных с помощью 64-битового ключа, в котором значащими являются 56 бит (остальные 8 бит – проверочные биты для контроля на четность). Дешифрование в DES является операцией, обратной шифрованию, и выполняется путем повторения операций шифрования в обратной последовательности. Обобщенная схема процесса шифрования в алгоритме DES показана на 3.2. Процесс шифрования заключается в начальной перестановке битов 64-битового блока, шестнадцати циклах шифрования и, наконец, в конечной перестановке битов.

Рисунок 3.2 – Обобщенная  схема  шифрования  в  алгоритме  DES

            Все приводимые таблицы являются стандартными и должны включаться в реализацию алгоритма DES в неизменном виде.

         Все перестановки и коды в таблицах подобраны разработчиками таким образом, чтобы максимально затруднить процесс расшифровки путем подбора ключа. При описании алгоритма DES (рис. 3.3) применены следующие обозначения:

L и R – последовательности битов (левая (left) и правая (right));

Рисунок 3.3 – Структура  алгоритма DES

LR – конкатенация последовательностей L и R, т.е. такая последовательность битов, длина которой равна сумме длин L и R; в последовательности LR биты последовательности R следуют за битами последовательности L;

 – операция побитового сложения по модулю 2.

            Пусть из файла исходного текста считан очередной 64-битовый (8-байтовый) блок Т. Этот блок Т преобразуется с помощью матрицы начальной перестановки IP (табл. 3.1).

                                                                                               Таблица 3.1

Матрица начальной перестановки IP

            Биты входного блока Т (64 бита) переставляются в соответствии с матрицей IP: бит 58 входного блока Т становится битом 1, бит 50 – битом 2 и т.д. Эту перестановку можно описать выражением  Т₀ = IP(T). Полученная последовательность битов  Т₀  разделяется на две последовательности: L₀ – левые или старшие биты,  R₀ – правые  или  младшие  биты, каждая из которых содер-жит 32 бита.

         Затем выполняется итеративный процесс шифрования, состоящий из 16 шагов (циклов). Пусть Т_i – результат i-й итерации:

Т_i = L_i R_i,

где  L_i = t₁ t₂ ... t₃₂  (первые 32 бита);  R_i = t₃₃ t₃₄ ... t₆₄ (последние 32 бита). Тогда результат i-й итерации описывается следующими формулами:

L_i = R_i–1,   i = 1, 2, ..., 16;

R_i = L_i–1  f (R_i–1, K_i),   i =  1, 2, ..., 16.

Функция f называется функцией шифрования. Ее аргументами являются последовательность R_i–1, получаемая на предыдущем шаге итерации, и 48-битовый ключ  К_i, который является результатом преобразования 64-битового ключа шифра К. (Подробнее функция шифрования  f  и алгоритм получения ключа  К_i  описаны ниже.)

         На последнем шаге итерации получают последовательности R₁₆ и L₁₆ (без перестановки местами), которые конкатенируются в 64-битовую последовательность  R₁₆ L₁₆.

         По окончании шифрования осуществляется восстановление  позиций  битов  с  помощью  матрицы  обратной перестановки IP^–1 (табл.3.2).

                                                                                               Таблица 3.2

Матрица обратной перестановки IP^–1

Пример того, как соотносятся элементы первой строки матрицы IP^–1 с элементами матрицы IP приведен в табл. 3.3.

Таблица 3.3

Связь элементов матриц

            Процесс расшифрования данных является инверсным по отношению к процессу шифрования. Все действия должны быть выполнены в обратном порядке. Это означает, что расшифровываемые данные сначала переставляются в соответствии с матрицей IP^–1, а затем над последовательностью битов  R₁₆L₁₆  выполняются те же действия, что и в процессе шифрования, но в обратном порядке.

         Итеративный процесс расшифрования может быть описан следующими формулами:

R_i–1 = L_i,   i = 1, 2, ..., 16;

L_i–1 = R_i  f (L_i, K_i),   i = 1, 2, ..., 16.         Таким образом, для процесса расшифрования с переставленным входным блоком R₁₆L₁₆ на первой итерации используется ключ  К₁₆, на второй итерации – К₁₅  и т.д. На 16-й итерации используется ключ К₁. На последнем шаге итерации будут получены последовательности L₀ и R₀, которые конкатенируются в 64‑битовую последовательность L₀R₀. Затем в этой последовательности 64 бита переставляются в соответствии с матрицей IP. Результат такого преобразования – исходная последовательность битов (расшифрованное 64-битовое значение).

         Теперь рассмотрим, что скрывается под преобразованием, обозначенным буквой  f. Схема вычисления функции шифрования f (R_i–1,K_i) показана на рис. 3.4.

Рисунок 3.4 – Схема вычисления функции шифрования f

            Для вычисления значения функции  f  используются:

· функция Е (расширение 32 бит до 48);

· функция S₁, S₂, ..., S₈ (преобразование 6-битового числа в 4-битовое);

· функция  Р  (перестановка  битов  в 32-битовой последователь-

     ности).

         Приведем определения этих функций.

         Аргументами функции шифрования f являются  R_i–1 (32 бита) и K_i (48 бит). Результат функции  Е (R_i–1)  есть 48-битовое число. Функция расширения Е, выполняющая расширение 32 бит до 48 (принимает блок из 32 бит и порождает блок из 48 бит), определяется табл. 3.4.

В соответствии с табл. 3.4 первые три бита E (R_i–1) – это биты 32, 1 и 2, а последние – 31, 32, 1. Полученный результат (обозначим его E(R_i–1)) складывается по модулю 2 (операция XOR) с текущим значением

                                                                                     Таблица 3.4

Функция расширения E

ключа К_i и затем разбивается на восемь 6-битовых блоков В₁, В₂, ..., В₈:

Е (R_i–1)  К_i = В₁ В₂ ... В₈.

Далее каждый из этих блоков используется как номер элемента в функциях-матрицах S₁, S₂, ..., S₈, содержащих 4-битовые значения (табл. 3.5).

Таблица 3.5

Функции преобразования S₁, S₂, ..., S₈

         Следует отметить, что выбор элемента в матрице S_j осуществляется достаточно оригинальным образом. Пусть на вxод матрицы  S_j  поступает 6-битовый блок  B_j = b₁ b₂ b₃ b₄ b₅ b₆, тогда двухбитовое число  b₁ b₆  указывает номер строки матрицы, а четырехбитовое число  b₂ b₃ b₄ b₅ – номер столбца. Например, если на вход матрицы S₁ поступает 6-битовый блок В₁= b₁ b₂ b₃ b₄ b₅ b₆ = 100110, то 2-битовое число  b₁ b₆ = 10₍₂₎ = 2₍₁₀₎  указывает строку с номером 2 матрицы S₁, а 4‑битовое число  b₂ b₃ b₄ b₅=0011₍₂₎=3₍₁₀₎  указывает столбец с номером  3  матрицы S₁. Это означает, что в матрице S₁ блок В₁ = 100110 выбирает элемент на пересечении строки  с  номером  2  и  столбца  с  номером  3, т.е. элемент 8₍₁₀₎ =

=1000₍₂₎. Совокупность 6-битовых блоков В₁, В₂,..., В₈ обеспечивает выбор четырехбитового элемента в каждой из матриц S₁, S₂, ..., S₈.

         В результате получаем S₁(В₁) S₂(В₂) S₃(В₃) ... S₈(В₈), т.е. 32‑битовый блок (поскольку матрицы S_j содержат 4-битовые элементы). Этот 32-битовый блок преобразуется с помощью функции перестановки битов Р (табл.3.6).

         Таким образом, функция шифрования

f (R_i–1, K_i) = P(S₁(B₁), ..., S₈(B₈)).

         Как нетрудно заметить, на каждой итерации используется новое значение ключа К_i (длиной 48 бит). Новое значение ключа  К_i  вычисляется из начального ключа  К  (рис.3.5). Ключ К представляет собой 64‑битовый блок с 8 битами контроля по четности, расположенными в позициях 8, 16, 24, 32, 40, 48, 56, 64. Для удаления контрольных битов и подготовки ключа к работе используется функция G первоначальной подготовки ключа (табл. 3.7).

Рисунок 3.5 – Схема алгоритма вычисления ключей K_i   Табл. 3.7 разделена на две части. Результат преобразования G(K)  разбивается на две половины С₀ и D₀ по 28 бит каждая. Первые  четыре  строки  матрицы  G  определяют,  как   выбираются биты последовательности С₀  (первым  битом  С₀ будет  бит  57 ключа шифра, затем бит 49 и т.д., а последними битами – биты 44 и 36 ключа).

         Следующие четыре строки матрицы G определяют, как выбираются биты последовательности D₀ (т.е. последовательность D₀ будет состоять из битов 63, 55, 47, ...,12, 4 ключа шифра).

         Как видно из табл. 3.7, для генерации последовательностей С₀ и D₀ не используются биты 8, 16, 24, 32, 40, 48, 56 и 64 ключа шифра. Эти биты не влияют на шифрование и могут служить для других целей (например, для контроля по четности). Таким образом, в действительности ключ шифра является 56-битовым.

         После определения С₀ и  D₀ рекурсивно определяются  С_i и D_i, I = 1, 2, ..., 16. Для этого применяются операции циклического сдвига влево на один или два бита в зависимости от номера шага итерации, как показано в табл. 3.8.

         Операции сдвига выполняются для последовательностей  С_i и  D_i  независимо. Например, последовательность С₃ получается посредством циклического сдвига влево на две позиции последовательности С₂, а последовательность D₃ – посредством сдвига влево на две позиции последовательности D₂, С₁₆ и D₁₆ получаются из С₁₅ и D₁₅ посредством сдвига влево на одну позицию.

Таблица 3.8

Таблица сдвигов  s_i для вычисления ключа

            Ключ К_i, определяемый на каждом шаге итерации, есть результат выбора конкретных битов из 56-битовой последовательности  С_i D_i  и их перестановки. Другими словами, ключ К_i=H(С_i D_i), где функция H определяется матрицей, завершающей обработку ключа (табл. 3.9).

                                                                                             Таблица 3.9

Функция H завершающей обработки ключа

(переставленная выборка 2)

            Как следует из табл.3.9, первым битом ключа  К_i будет 14-й бит последовательности  С_i D_i, вторым – 17-й бит, 47-м битом ключа  К_i  будет 29-й бит  С_i D_i, а 48-м битом – 32-й бит  С_i D_i.

3.2.1. Основные режимы работы алгоритма DES

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

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

· электронная кодовая книга ECB (Electronic Code Book);

· сцепление блоков шифра CBC (Cipher Block Chaining);

· обратная связь по шифртексту CFB (Cipher Feed Back);

· обратная связь по выходу OFB (Output Feed Back).

Режим "Электронная кодовая книга"

         Длинный файл разбивают на 64-битовые отрезки (блоки) по 8 байтов. Каждый из этих блоков шифруют независимо с использованием одного и того же ключа шифрования (рис.3.6).

         Основное достоинство – простота реализации. Недостаток – относительно слабая  устойчивость  против  квалифицированных криптоаналитиков. Из-за фиксированного характера шифрования при ограниченной длине блока 64 бита возможно проведение криптоанализа "со словарем". Блок такого размера может повториться  в  сообщении  вследствие  большой избыточности в тексте на естественном языке.

Рисунок 3.6 – Схема алгоритма DES в режиме электронной кодовой  книги

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

Режим "Сцепление блоков шифра"

         В этом режиме исходный файл М разбивается на 64-битовые блоки: М = М₁М₂...М_n. Первый блок М₁ складывается по модулю 2 с 64‑битовым начальным вектором IV, который меняется ежедневно и держится в секрете (рис.3.7). Полученная сумма затем шифруется с использованием ключа DES, известного и отправителю, и получателю информации. Полученный 64-битовый шифр С₁ складывается по модулю 2 со вторым блоком текста, результат шифруется и получается второй 64‑битовый шифр С₂, и т.д. Процедура повторяется до тех пор, пока не будут обработаны все блоки текста.

         Таким образом, для всех  i = 1…n (n – число блоков) результат шифрования  С_i  определяется  следующим  образом: С_i =

=DES (М_i  C_i–1), где С₀ = IV – начальное значение шифра, равное начальному вектору (вектору инициализации).

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

Рисунок 3.7 – Схема алгоритма DES в режиме сцепления блоков шифра

открытого текста независимо от его длины. Этот блок шифртекста называют кодом аутентификации сообщения (КАС).

            Код КАС может быть легко проверен получателем, владеющим секретным ключом и начальным вектором, путем повторения процедуры, выполненной отправителем. Посторонний, однако, не может осуществить генерацию КАС, который воспринялся бы получателем как подлинный, чтобы добавить его к ложному сообщению, либо отделить КАС от истинного сообщения для использования его с измененным или ложным сообщением.

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

         Блок М_i является функцией только С_i–1 и С_i. Поэтому ошибка  при  передаче  приведет  к потере только двух блоков исходно-го текста.

Режим "Обратная связь по шифру"

         В этом режиме размер блока может отличаться от 64 бит (рис.3.8). Файл, подлежащий шифрованию (расшифрованию), считывается последовательными блоками длиной k битов (k =1…64).

            Входной блок (64-битовый регистр сдвига) вначале содержит вектор инициализации, выровненный по правому краю.

         Предположим, что в результате разбиения на блоки мы получили n блоков длиной k битов каждый (остаток дописывается нулями  или  пробелами).  Тогда  для  любого  i =1…n  блок шифр-текста

С _i = M_i  P_i–1,

где Р_i–1 обозначает k старших битов предыдущего зашифрованного блока.

         Обновление сдвигового регистра осуществляется путем удаления его старших k битов и записи  С_i  в регистр. Восстановление зашифрованных данных также выполняется относительно просто:  Р_i–1  и  С_i  вычисляются аналогичным образом и

М _i = С _i  Р_i–1.

Рисунок 3.8 – Схема алгоритма DES в режиме обратной связи по шифртексту

Режим "Обратная связь по выходу"

         Этот режим тоже использует переменный размер блока и сдвиговый регистр, инициализируемый так же, как в режиме СFB, а именно – входной блок вначале содержит вектор инициализации IV, выровненный по правому краю (рис.3.9). При этом для  каждого сеанса шифрования данных необходимо использовать новое начальное состояние регистра, которое должно пересылаться по каналу открытым текстом.

         Положим

М = М ₁ М ₂ ... M_n.

         Для всех  i = 1… n

С _i = M _i  P_i,

где Р_i – старшие k битов операции DES (С_i–1).

         Отличие от режима обратной связи по шифртексту состоит в методе обновления сдвигового регистра.

            Это осуществляется путем отбрасывания старших k битов и дописывания справа Р_i.

Рисунок 3.9 – Схема алгоритма DES в режиме обратной связи по выходу

3.3. Области применения алгоритма DES

            Каждому из рассмотренных режимов (ЕСВ, СВС, CFB, OFB) свойственны свои достоинства и недостатки, что обусловливает области их применения.

         Режим ЕСВ хорошо подходит для шифрования ключей: режим CFB, как правило, предназначается для шифрования отдельных символов, а режим OFB нередко применяется для шифрования в спутниковых системах связи.

         Режимы СВС и CFB пригодны для аутентификации данных. Эти режимы позволяют использовать алгоритм DES для:

· интерактивного шифрования при обмене данными между терминалом и главной ЭВМ;

· шифрования криптографического ключа в практике автоматизированного распространения ключей;

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

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

         В системах автоматической обработки данных человек не в состоянии просмотреть данные, чтобы установить, не внесены ли в них какие-либо изменения. При огромных объемах данных, проходящих в современных системах обработки, просмотр занял бы слишком много времени. К тому же избыточность данных может оказаться недостаточной для обнаружения ошибок. Даже в тех случаях, когда просмотр человеком возможен, данные могут быть изменены таким образом, что обнаружить эти изменения человеку очень трудно. Например, "do" может быть заменено на "do not", "$1900" – на "$9100". Без дополнительной информации человек при просмотре может легко принять измененные данные за подлинные. Такие опасности могут существовать даже при использовании шифрования данных. Поэтому желательно иметь автоматическое средство обнаружения преднамеренных и непреднамеренных изменений данных.

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

         Этот процесс описывает стандарт для аутентификации данных ЭВМ (FIPS 113). Суть стандарта состоит в том, что данные зашифровываются в режиме обратной связи по шифртексту (режим CFB) или в режиме сцепления блоков шифра (режим СВС), в результате чего получается окончательный блок шифра, представляющий собой функцию всех разрядов открытого текста. После этого сообщение, которое содержит открытый текст, может быть передано с использованием вычисленного окончательного блока шифра, служащего в качестве криптографической контрольной суммы.

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

му тексту.

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

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

         С помощью алгоритма DES можно также зашифровать файлы ЭВМ для их хранения.

         Одним из наиболее важных применений алгоритма DES является защита сообщений электронной системы платежей (ЭСП) при операциях с широкой клиентурой и между банками.

         Алгоритм DES реализуется в банковских автоматах, терминалах в торговых точках, автоматизированных рабочих местах и главных ЭВМ. Диапазон защищаемых им данных весьма широк – от оплат $50 до переводов на многие миллионы долларов. Гибкость основного алгоритма DES позволяет использовать его в самых разнообразных областях применения электронной системы платежей.

3.4. Комбинирование блочных алгоритмов

            В настоящее время блочный алгоритм DES считается относительно безопасным алгоритмом шифрования. Он подвергался тщательному криптоанализу в течение 20 лет, и самым практичным способом его взламывания является метод перебора всех возможных вариантов ключа. Ключ DES имеет длину 56 бит, поэтому существует 2⁵⁶ возможных вариантов такого ключа. Если предположить, что суперкомпьютер может испытать миллион вариантов ключа за секунду, то потребуется 2285 лет для нахождения правильного ключа. Если бы ключ имел длину 128 бит, то потребовалось бы 10²⁵ лет (для сравнения: возраст Вселенной около 10¹⁰ лет).

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

         Возникает естественный вопрос: нельзя ли использовать DES в качестве строительного блока для создания другого алгоритма с более длинным ключом?

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

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

         Рассмотрим эффективность двухкратного шифрования блока открытого текста с помощью двух разных ключей. Сначала шифруют блок Р ключом К₁, а затем получившийся шифртекст Е_К1(Р) шифруют ключом К₂. В результате двухкратного шифрования получают криптограмму

С = Е_К2(Е_К1(Р)).

         Расшифрование является обратным процессом:

Р = D_К1(D_К2(C)).

         Если блочный алгоритм обладает свойствами группы, то всегда найдется такой ключ К₃, что

С = Е_К2(Е_К1(Р)) = Е_К3(Р).

            Если же блочный алгоритм не является группой, то результирующий двухкратно шифрованный блок текста окажется намного сложнее для взламывания методом полного перебора вариантов. Вместо 2ⁿ попыток, где n – длина ключа в битах, потребуется  2²ⁿ попыток. В частности, если n=64, то двухкратно зашифрованный  блок  текста  потребует  2¹²⁸ попыток  для нахожде-ния ключа.

         Однако Р.Меркль и М.Хеллман показали на примере DES, что, используя метод "обмена времени на память" и криптоаналитическую атаку "встреча посредине", можно взломать такую схему двухкратного шифрования за 2ⁿ⁺¹ попыток [34]. Хотя эта атака потребует очень большого объема памяти (для алгоритма с 56-битовым ключом потребуется 2⁵⁶ 64-битовых блоков или 10¹⁷ бит памяти).

         Более привлекательную идею предложил У.Тачмен [125]. Суть этой идеи состоит в том, чтобы шифровать блок открытого текста Р три раза с помощью двух ключей К₁ и К₂ (рис.3.10). Процедура шифрования:

С = Е_К1(D_К2 (E_К1(Р))),

т.е. блок открытого текста Р сначала шифруется ключом К₁, затем расшифровывается ключом К₂ и окончательно зашифровывается ключом К₁.

         Этот режим иногда называют режимом EDE (encrypt-decrypt-encrypt). Введение в данную схему операции расшифрования D_К2 позволяет обеспечить совместимость этой схемы со схемой однократного использования алгоритма DES. Если в схеме трехкратного использования DES выбрать все ключи одинаковыми, то эта схема превращается в схему однократного использования DES.

Рисунок 3.10 – Схемы трехкратного применения алгоритма DES

с двумя разными ключами

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

Р = D_К1(Е_К2(D_К1(C))),

т.е. блок шифртекста С сначала расшифровывается ключом К₁, затем зашифровывается ключом К₂ и окончательно расшифровывается ключом К₁.

         Если исходный блочный алгоритм имеет n-битовый ключ, то схема трехкратного шифрования имеет 2n-битовый ключ. Чередование ключей К₁ и К₂ позволяет предотвратить криптоаналитическую атаку "встреча посредине". Данная схема приводится в стандартах Х9.17 и ISO 8732 в качестве средства улучшения характеристик алгоритма DES.

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

С = Е_К3(D_К2(E_К1(P))),

Р = D_К1(Е_К2(D_К3(C))).

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

3.5. Алгоритм шифрования данных IDEA

            Алгоритм IDEA (International Data Encryption Algorithm) является блочным шифром. Он оперирует 64-битовыми блоками открытого текста. Несомненным достоинством алгоритма IDEA является то, что его ключ имеет длину 128 бит. Один и тот же алгоритм используется и для шифрования, и для расшифрования.

            Первая версия алгоритма IDEA была предложена в 1990 г., ее авторы – Х.Лей и Дж.Мэсси. Первоначальное название алгоритма PES (Proposed Encryption Standard). Улучшенный вариант этого алгоритма, разработанный в 1991 г., получил название IPES (Improved Proposed Encryption Standard). В 1992 г. IPES изменил свое имя на IDEA. Как и большинство других блочных шифров, алгоритм IDEA использует при шифровании процессы смешивания и рассеивания, причем все процессы легко реализуются аппаратными и программными средствами.

         В алгоритме IDEA используются следующие математические операции:

· поразрядное сложение по модулю 2 (операция "исключающее ИЛИ"); операция обозначается как ;

· сложение беззнаковых целых по модулю 2¹⁶ (модуль 65536); операция обозначается как ⊞ ;

· умножение целых по модулю (2¹⁶+1) (модуль 65537), рассматриваемых как беззнаковые целые, за исключением того, что блок из 16 нулей рассматривается как 2¹⁶; операция обозначается  как ⊙.

Все операции выполняются над 16-битовыми субблоками.

Эти три операции несовместимы в том смысле, что:

· никакая пара из этих трех операций не удовлетворяет ассоциативному закону,

например  a ⊞ (b  c)  (a ⊞ b)  c;

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

например  a ⊞ (b⊙ c)  (a ⊞ b)⊙ (a ⊞ c).

         Комбинирование этих трех операций обеспечивает комплексное  преобразование  входа, существенно  затрудняя крипто-анализ IDEA по сравнению с DES, который базируется исключительно на операции "исключающее ИЛИ".

         Общая схема алгоритма IDEA приведена на рис.3.11. 64-битовый блок данных делится на четыре 16-битовых субблока. Эти четыре субблока становятся входом в первый цикл алгоритма. Всего выполняется восемь циклов. Между циклами второй и третий субблоки меняются местами. В каждом цикле имеет место следующая последовательность операций:

         Выходом цикла являются четыре субблока, которые получают как результаты выполнения шагов (11), (12), (13) и (14). В завершение цикла переставляют местами два внутренних субблока (за исключением последнего цикла), и в результате формируется вход для следующего цикла.

                Обозначения:

            X_i – 16-битовый субблок открытого текста, i = 1…4

            Y_i – 16-битовый субблок шифртекста, i = 1…4

            Z_j^(r) – 16-битовый подключ (субблок ключа), j = 1…6, r = 1…8

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

                  – сложение по модулю 2¹⁶ 16-битовых целых

                  – умножение по модулю 2¹⁶ 16-битовых целых (с нулевым субблоком,

                    соответствующим 2¹⁶)

Рисунок 3.11 – Схема алгоритма IDEA (режим шифрования)

            После восьмого цикла осуществляют заключительное преобразование выхода:

Наконец, эти результирующие четыре субблока  Y₁…Y₄  вновь объединяют для получения блока шифртекста.

            Создание подключей Z_j также относительно несложно. Алгоритм использует всего 52 подключа (по шесть для каждого из восьми циклов и еще четыре для преобразования выхода). Сначала 128-битовый ключ делят на восемь 16-битовых подключей. Это – первые восемь подключей для алгоритма (шесть подключей – для первого цикла и первые два подключа – для второго цикла). Затем 128-битовый ключ циклически сдвигается влево на 25 бит и снова делится на восемь подключей. Первые четыре из них используют во втором цикле; последние четыре – в третьем цикле. Ключ снова циклически сдвигается влево еще на 25 бит для получения следующих восьми подключей и т.д., пока выполнение алгоритма не завершится.

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

         Для реализации алгоритма IDEA было принято предположение, что нулевой субблок равен 2¹⁶= –1; при этом мультипликативная обратная величина от 0 равна 0 [121]. Вычисление значений мультипликативных обратных величин требует некоторых затрат, но это приходится делать только один раз для каждого ключа расшифрования.

         Алгоритм IDEA может работать в любом режиме блочного шифра, предусмотренном для алгоритма DES. Алгоритм IDEA обладает рядом преимуществ перед алгоритмом DES. Он значительно безопаснее алгоритма DES, поскольку 128-битовый ключ алгоритма IDEA вдвое больше ключа DES. Внутренняя структура алгоритма IDEA обеспечивает лучшую устойчивость к криптоанализу. Существующие программные реализации алгоритма IDEA примерно вдвое быстрее реализаций алгоритма DES. Алгоритм IDEA  шифрует данные

Таблица 3.10

Подключи шифрования и расшифрования алгоритма IDEA

на IBM PC/486 со скоростью 2,4 Мбит/с. Реализация IDEA на СБИС  шифрует данные со скоростью 177 Мбит/с при частоте 25 Мгц. Алгоритм IDEA запатентован в Европе и США.

3.6. Отечественный  стандарт  шифрования данных

            В нашей стране установлен единый алгоритм криптографического преобразования данных для систем обработки информации в сетях ЭВМ, отдельных вычислительных комплексах и ЭВМ, который определяется ГОСТ 28147-89. Стандарт обязателен для организаций, предприятий и учреждений, применяющих криптографическую защиту данных, хранимых и передаваемых в сетях ЭВМ, в отдельных вычислительных комплексах и ЭВМ.

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

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

L и R – последовательности битов;

LR – конкатенация последовательностей L и R, в которой биты последовательности R следуют за битами последовательности L;

 – операция побитового сложения по модулю 2;

⊞ – операция сложения по модулю 2³² двух 32-разрядных двоичных чисел;

⊞´– операция сложения двух 32-разрядных чисел по модулю 2³² –1.

            Два целых числа  a, b,  где  0  a, b  2³² –1,

a= (a₃₂a₃₁ ... a₂a₁),   b = (b₃₂, b₃₁, ..., b₂, b₁),

представленные в двоичном виде, т.е.

a= a₃₂2³¹ + a₃₁2³⁰ +...+ a₂2¹ + a₁,

b = b₃₂2³¹ + b₃₁2³⁰ +...+ b₂2¹ + b₁,

суммируются   по   модулю   2³²  (операция ⊞) по следующему правилу:

a ⊞ b = a + b,  если  a + b < 2³²,

a ⊞ b = a + b – 2³²,  если  a + b  2³².

         Правила суммирования чисел по модулю  2³² – 1:

a ⊞´ b = a + b,  если  a + b < 2³²– 1,

a ⊞´ b = a + b – (2³² – 1),  если  a + b  2³² – 1.

            Алгоритм предусматривает четыре режима работы:

· шифрование данных в режиме простой замены;

· шифрование данных в режиме гаммирования;

· шифрование данных в режиме гаммирования с обратной связью;

· выработка имитовставки.

Режим простой замены

         Для реализации алгоритма шифрования данных в режиме простой замены используется только часть блоков общей криптосистемы (рис.3.12). Обозначения на схеме:

N₁, N₂ – 32-разрядные накопители;

СМ₁ – 32-разрядный сумматор по модулю 2³² (⊞);

СМ₂ – 32-разрядный сумматор по модулю 2 ();

R – 32-разрядный регистр циклического сдвига;

КЗУ – ключевое запоминающее устройство на 256 бит, состоящее из восьми 32-разрядных накопителей Х₀, Х₁, Х₂, ..., Х₇;

S – блок подстановки, состоящий из восьми узлов замены (S-блоков замены) S₁, S₂, S₃, ..., S₇, S₈.

Зашифрование открытых данных в режиме простой замены. Открытые данные, подлежащие зашифрованию, разбивают на 64‑разрядные блоки Т₀. Процедура зашифрования 64-разрядного блока Т₀ в режиме простой замены включает 32 цикла (j = 1…32). В ключевое запоминающее устройство вводят 256 бит ключа К в виде восьми 32-разрядных подключей (чисел) К_i:

К=К₇К₆К₅К₄К₃К₂К₁К₀.

Последовательность битов блока

Т₀=(a₁(0), a₂(0), ..., a₃₁(0), a₃₂(0), b₁(0), b₂(0),..., b₃₁(0), b₃₂(0))

разбивают на две последовательности по 32 бита: b(0) a(0), где b(0) – левые или старшие биты, a(0) – правые или младшие биты.Эти последовательности вводят в накопители N₁ и N₂ перед началом первого цикла зашифрования. В результате начальное заполнение накопителя N₁

a (0) = (a₃₂(0), a₃₁(0), ..., a₂(0), a₁(0)),

     32,         31,       ...      2,         1         номер разряда N₁

начальное заполнение накопителя N₂

b(0) = (b₃₂(0), b₃₁(0), ..., b₂(0), b₁(0)).

              32,         31,       ...      2,         1        номер разряда N₂

Рисунок 3.12 – Схема реализации режима простой замены

Первый цикл (j=1) процедуры зашифрования 64-разрядного блока открытых данных можно описать уравнениями:

           

Здесь a (1) – заполнение N₁ после 1-го цикла зашифровaния; b (1) – заполнение N₂ после 1-го цикла зашифрования; f – функция шифрования.

         Аргументом функции f является сумма по модулю 2³² числа a(0) (начального заполнения накопителя N₁) и числа К₀ – подключа, считываемого из накопителя Х₀ КЗУ. Каждое из этих чисел равно 32 битам.

         Функция f включает две операции над полученной 32-разрядной суммой  (a (0) ⊞ К₀).

         Первая операция называется подстановкой (заменой) и выполняется блоком подстановки S. Блок подстановки S состоит из восьми узлов замены (S-блоков замены) S₁,S₂,...,S₈ с памятью 64 бит каждый. Поступающий из СМ₁ на блок подстановки S 32-разрядный вектор разбивают на восемь последовательно идущих 4-разрядных векторов, каждый из которых преобразуется в четырехразрядный вектор соответствующим узлом замены. Каждый узел замены можно представить в виде таблицы-перестановки шестнадцати четырехразрядных двоичных чисел в диапазоне 0000…1111. Входной вектор указывает адрес строки в таблице, а число в этой строке является выходным вектором. Затем четырехразрядные выходные векторы последовательно объединяют в 32‑разрядный вектор. Узлы замены (таблицы-перестановки) представляют собой ключевые элементы, которые являются общими для сети ЭВМ и редко изменяются. Эти узлы замены должны сохраняться в секрете.

         Вторая операция – циклический сдвиг влево (на 11 разрядов) 32‑разрядного вектора, полученного с выхода блока подстановки S. Циклический сдвиг выполняется регистром сдвига R.

            Далее результат работы функции шифрования f суммируют поразрядно по модулю 2 в сумматоре СМ₂ с 32-разрядным начальным заполнением b(0) накопителя N₂. Затем полученный на выходе СМ₂ результат (значение a(1)) записывают в накопитель N₁, а старое значение N₁ (значение a(0)) переписывают в накопитель N₂ (значение b(1) = a(0)). Первый цикл завершен.

         Последующие циклы осуществляются аналогично, при этом во втором цикле из КЗУ считывают заполнение Х₁ – подключ К₁, в третьем цикле – подключ К₂ и т.д., в восьмом цикле – подключ К₇. В циклах с 9-го по 16-й, а также в циклах с 17-го по 24-й подключи из КЗУ считываются в том же порядке: К₀, К₁, К₂,...,К₆, К₇. В последних восьми циклах с 25-го по 32-й порядок считывания подключей из КЗУ обратный: К₇, К₆, ..., К₂, К₁, К₀. Таким образом, при зашифровании в 32 циклах осуществляется следующий порядок выборки из КЗУ подключей:

К₀, К₁, К₂, К₃, К₄, К₅, К₆, К₇, К₀, К₁, К₂, К₃, К₄, К₅, К₆, К₇,

К₀, К₁, К₂, К₃, К₄, К₅, К₆, К₇, К₇, К₆, К₅, К₄, К₃, К₂, К₁, К₀.

            В 32-м цикле результат из сумматора СМ₂ вводится в накопитель N₂, а в накопителе N₁ сохраняется прежнее заполнение. Полученные после 32-го цикла зашифрования заполнения накопителей N₁ и N₂ являются блоком зашифрованных данных Т_ш, соответствующим блоку открытых данных Т₀.

         Уравнения   зашифрования   в   режиме   простой    замены имеют  вид:

               при  j=1…24,

                  при  j=25…31,

                      при  j=32

где  a (j) = (a₃₂(j), a₃₁(j), ..., a₁(j)) – заполнение N₁ после j-го цикла зашифрования;

        b (j) = (b₃₂(j), b₃₁(j), ..., b₁(j)) – заполнение N₂ после j-го цикла зашифрования,  j=1…32.

Блок зашифрованных данных Т_ш (64 разряда) выводится из накопителей N₁, N₂ в следующем порядке: из разрядов 1…32 накопителя N₁, затем из разрядов 1…32 накопителя N₂, т.е. начиная с младших разрядов:

Т_ш = (a₁(32), a₂(32), ..., a₃₂(32), b₁(32), b₂(32), ..., b₃₂(32)).

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

Расшифрование в режиме простой замены. Криптосхема, реализующая алгоритм расшифрования в режиме простой замены, имеет тот же вид, что и при зашифровании (см. рис. 3.12).

         В КЗУ вводят 256 бит ключа, на котором осуществлялось зашифрование. Зашифрованные данные, подлежащие расшифрованию, разбиты  на  блоки  Т_ш  по  64 бита  в  каждом.  Ввод  любо-го блока

Т_ш = (a₁(32), a₂(32), ..., a₃₂(32), b₁(32), b₂(32), ..., b₃₂(32))

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

(a₃₂(32), a₃₁(32), ..., a₂(32), a₁(32)),

      32,         31,        ...,     2,              1           номер разряда N₁

а начальное заполнение накопителя N₂ – вид

(b₃₂(32), b₃₁(32), ..., b₂(32), b₁(32)).

    32,           31,       ...,            2,           1            номер разряда N₂

            Расшифрование осуществляется по тому же алгоритму, что и зашифрование, с тем изменением, что заполнения накопителей X₀, Х₁, ..., Х₇ считываются из КЗУ в циклах расшифрования в следующем порядке:

К₀, К₁, К₂, К₃, К₄, К₅, К₆, К₇, К₇, К₆, К₅, К₄, К₃, К₂, К₁, К₀,

К₇, К₆, К₅, К₄, К₃, К₂, К₁, К₀, К₇, К₆, К₅, К₄, К₃, К₂, К₁, К₀.

         Уравнения расшифрования имеют вид:

     при  j=1…8;

       при  j=9…31;

                                         при  j=32.

         Полученные после 32 циклов работы заполнения накопителей N₁ и N₂ образуют блок открытых данных

Т₀ = (a₁(0), a₂(0), ..., a₃₂(0), b₁(0), b₂(0),..., b₃₂(0)),

соответствующий блоку зашифрованных данных Т_ш. При этом состояние накопителя N₁

(a₃₂(0), a₃₁(0), ..., a₂(0), a₁(0)),

    32,        31,     ...,        2,        1          номер разряда N₁

состояние накопителя N₂

(b₃₂(0), b₃₁(0), ..., b₂(0), b₁(0)).

     32,       31,      ...,        2,        1          номер разряда N₂

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

            Если алгоритм зашифрования в режиме простой замены 64‑битового блока Т₀ обозначить через А, то

А(Т₀) = А(a (0), b(0)) = (a (32), b(32))=Т_ш.

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

Режим гаммирования

Зашифрование открытых данных в режиме гаммирования. Криптосхема, реализующая алгоритм зашифрования в режиме гаммирования, показана на рис.3.13. Открытые данные разбивают на 64‑разрядные блоки

Т₀⁽¹⁾, Т₀⁽²⁾, ..., Т₀⁽ⁱ⁾, ..., Т₀^(m),

где Т₀⁽ⁱ⁾ – i-й 64-разрядный блок открытых данных, i = 1…m, m определяется объемом шифруемых данных.

Эти блоки поочередно зашифровываются в режиме гаммирования путем поразрядного сложения по модулю 2 в сумматоре СМ₅ с гаммой шифра Г_ш, которая вырабатывается блоками по 64 бита, т.е.

Г_ш=(Г_ш⁽¹⁾, Г_ш⁽²⁾, ..., Г_ш⁽ⁱ⁾, Г_ш^(m)),

где Г_ш⁽ⁱ⁾ – i-й  64-разрядный блок, i = 1…m.

Рисунок 3.13 – Схема реализации режима гаммирования

            Число двоичных разрядов в блоке Т₀^(m) может быть меньше 64, при этом неиспользованная для зашифрования часть гаммы шифра из блока Г_ш^(m) отбрасывается.

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

Т_ш⁽ⁱ⁾ = Т₀⁽ⁱ⁾  Г_ш⁽ⁱ⁾,

где Г_ш⁽ⁱ⁾=А(Y_i–1 ⊞ C₂, Z_i–1 ⊞´C₁), i=1…m; Т_ш⁽ⁱ⁾ – i-й блок 64-разрядного блока зашифрованного текста; А(·) – функция зашифрования в режиме простой замены; С₁, С₂ – 32-разрядные двоичные константы; Y_i, Z_i – 32‑разрядные двоичные последовательности.

         Величины Y_i, Z_i определяются итерационно по мере формирования гаммы Г_ш следующим образом:

(Y₀, Z₀) = А (),

где      –  синхропосылка   (64-разрядная   двоичная   последова-тельность),

(Y_i, Z_i) = (Y_i–1 ⊞ С₂,  Z_i–1 ⊞ C₁),  i = 1…m.

            Рассмотрим реализацию процедуры зашифрования в режиме гаммирования. В накопители N₆ и N₅ заранее записаны 32-разрядные двоичные константы С₁ и С₂, имеющие следующие значения (в шестнадцатеричной форме):

С₁ = 01010104₍₁₆₎,   С₂ = 01010101₍₁₆₎.

         В КЗУ вводится 256 бит ключа; в накопители N₁ и N₂ – 64-разрядная двоичная последовательность (синхропосылка)

 = (S₁, S₂, ..., S₆₄).

Синхропосылка  является исходным заполнением накопителей N₁ и N₂ для последовательной выработки m блоков гаммы шифра.

            Исходное заполнение накопителя N₁:

(S₃₂, S₃₁, ...,S₂, S₁);

    32,    31,  ...,   2,   1   номер разряда N₁

исходное заполнение накопителя N₂:

(S₆₄, S₆₃, ..., S₃₄, S₃₃).

    64,    63,  ...,   34,    33    номер разряда N₂

         Исходное заполнение N₁ и N₂ (синхропосылка ) зашифровывается в режиме простой замены. Результат зашифрования

A() = (Y₀, Z₀)

переписывается в 32-разрядные накопители N₃ и N₄ так, что заполнение N₁ переписывается в N₃, а заполнение N₂ – в N₄.

         Заполнение накопителя N₄ суммируют по модулю (2³² –1) в сумматоре СМ₄ с 32-разрядной константой С₁ из накопителя N₆. Результат записывается в N₄. Заполнение накопителя N₃ суммируется по модулю 2³² в сумматоре СМ₃ с 32-разрядной константой С₂ из накопителя N₅. Результат записывается в N₃. Заполнение N₃ переписывают в N₁, а заполнение N₄ – в N₂, при этом заполнения N₃, N₄ сохраняются. Заполнение накопителей N₁ и N₂ зашифровывается в режиме простой замены.

         Полученное в результате зашифрования заполнение накопителей N₁, N₂ образует первый 64-разрядный блок гаммы шифра Г_ш⁽¹⁾=(₁⁽¹⁾, ₂⁽¹⁾, ..., ₆₃⁽¹⁾, ₆₄⁽¹⁾), который суммируют поразрядно по модулю 2 в сумматоре СМ₅ с первым 64-разрядным блоком открытых данных

Т₀⁽¹⁾ = (t₁⁽¹⁾, t₂⁽¹⁾, ..., t₆₃⁽¹⁾, t₆₄⁽¹⁾).

В результате суммирования по модулю 2 значений Г_ш⁽¹⁾ и Т₀⁽¹⁾  получают первый 64-разрядный блок зашифрованнных данных:

Т_ш⁽¹⁾ = Г_ш⁽¹⁾  Т₀⁽¹⁾ = (₁⁽¹⁾, ₂⁽¹⁾, ..., ₆₃⁽¹⁾, ₆₄⁽¹⁾),

где  _i⁽¹⁾ = t_i⁽¹⁾  _i⁽¹⁾,   i = 1…64.

         Для получения следующего 64-разрядного блока гаммы шифра Г_ш⁽²⁾ заполнение N₄ суммируется по модулю (2³² –1) в сумматоре СМ₄ с константой С₁ из N₆. Результат записывается в N₄. Заполнение N₃ суммируется по модулю 2³² в сумматоре СМ₃ с константой С₂ из N₅. Результат записывается в N₃. Новое заполнение N₃ переписывают в N₁, а новое заполнение N₄ – в N₂ , при этом заполнения N₃ и N₄ сохраняют. Заполнения N₁, N₂ зашифровывают в режиме простой замены.

         Полученное в результате зашифрования заполнение накопителей N₁ и N₂ образует второй 64-разрядный блок гаммы шифра Г_ш⁽²⁾, который суммируется поразрядно по модулю 2 в сумматоре СМ₅ со вторым блоком открытых данных Т₀⁽²⁾:

Т_ш⁽²⁾ = Г_ш⁽²⁾  Т₀⁽²⁾.

Аналогично вырабатываются блоки гаммы шифра Г_ш⁽³⁾, Г_ш⁽⁴⁾, ..., Г_ш^(m) и зашифровываются блоки открытых данных Т₀⁽³⁾, Т₀⁽⁴⁾, ..., Т₀^(m).

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

Т_ш⁽¹⁾, Т_ш⁽²⁾, ..., Т_ш^(m).

Расшифрование в режиме гаммирования. При расшифровании криптосхема имеет тот же вид, что и при зашифровании (см. рис.3.13).

         Уравнение расшифрования:

Т₀⁽ⁱ⁾ = Т_ш⁽ⁱ⁾  Г_ш⁽ⁱ⁾ = T_ш⁽ⁱ⁾  A (Y_i–1 ⊞ C₂, Z_i–1 ⊞´ C₁),  i = 1…m.

         Следует отметить, что расшифрование данных возможно только при наличии синхропосылки, которая не является секретным  элементом  шифра  и  может  храниться  в  памяти  ЭВМ  или передаваться   по  каналам   связи    вместе   с   зашифрованными данными.

         Рассмотрим реализацию процедуры расшифрования. В КЗУ вводят 256 бит ключа, с помощью которого осуществляется зашифрование данных Т₀⁽¹⁾, Т₀⁽²⁾, ..., Т₀^(m). В накопители N₁ и N₂ вводится синхропосылка, и осуществляется процесс выработки m блоков гаммы шифра Г_ш⁽¹⁾, Г_ш⁽²⁾, ..., Г_ш^(m). Блоки зашифрованных данных Т_ш⁽¹⁾, Т_ш⁽²⁾, ..., Т_ш^(m) суммируются поразрядно по модулю 2 в сумматоре СМ₅ с блоками гаммы шифра Г_ш⁽¹⁾, ..., Г_ш^(m). В результате получаются блоки открытых данных

Т₀⁽¹⁾, Т₀⁽²⁾, ..., Т₀^(m);

при этом Т₀^(m) может содержать меньше 64 разрядов.

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

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

         Открытые данные, разбитые на 64-разрядные блоки Т₀⁽¹⁾, Т₀⁽²⁾, ..., Т₀^(m), зашифровываются в режиме гаммирования с обратной связью путем поразрядного сложения по модулю 2 с гаммой шифра Г_ш, которая вырабатывается блоками по 64 бита:

Г_ш = (Г_ш⁽¹⁾, Г_ш⁽²⁾, ..., Г_ш^(m)).

Число двоичных разрядов в блоке Т₀^(m) может быть меньше 64, при этом неиспользованная для шифрования часть гаммы шифра из блока Г_ш^(m) отбрасывается.

         Уравнения зашифрования в режиме гаммирования с обратной связью имеют вид:

Т_ш⁽¹⁾ = А ()  Т₀⁽¹⁾ = Г_ш⁽¹⁾  Т₀⁽¹⁾,

Т_ш⁽ⁱ⁾ = A (Т_ш^(i–1))  Т₀⁽ⁱ⁾ = Г_ш⁽ⁱ⁾  Т₀⁽ⁱ⁾,  i = 2…m.

 

Рисунок 3.14 – Схема реализации режима гаммирования с обратной связью

Здесь Т_ш⁽ⁱ⁾ – i-й 64-разрядный блок зашифрованного текста; А(·) – функция зашифрования в режиме простой замены; m – определяется объемом открытых данных.

            Аргументом функции А (·) на первом шаге итеративного алгоритма является 64-разрядная синхропосылка , а на всех последующих   шагах – предыдущий   блок   зашифрованных  дан-ных  Т_ш^(i–1).

Процедура зашифрования данных в режиме гаммирования с обратной связью реализуется следующим образом. В КЗУ вводятся 256 бит ключа. В накопители N₁ и N₂ вводится синхро-посылка = (S₁, S₂, ..., S₆₄) из 64 бит. Исходное заполнение накопителей N₁ и N₂ зашифровывается в режиме простой замены. Полученное в результате зашифрования заполнение накопителей N₁ и N₂ образует первый 64‑разрядный блок гаммы шифра Г_ш⁽¹⁾=A(), который  суммируется поразрядно по модулю 2 в сумматоре СМ₅ с первым 64-разрядным блоком открытых данных

Т₀⁽¹⁾ = (t₁⁽¹⁾, t₂⁽¹⁾,..., t₆₄⁽¹⁾).

В результате получают первый 64-разрядный блок зашифрованных данных

Т_Ш⁽¹⁾ = Г_Ш⁽¹⁾  Т₀⁽¹⁾,

где  Т_Ш⁽¹⁾ = (₁⁽¹⁾, ₂⁽¹⁾, ..., ₆₄⁽¹⁾).

         Блок зашифрованных данных Т_Ш⁽¹⁾ одновременно является также исходным состоянием накопителей N₁, N₂ для выработки второго блока гаммы шифра Г_Ш⁽²⁾, и поэтому по обратной связи Т_Ш⁽¹⁾ записывается в указанные накопители N₁ и N₂.

Заполнение накопителя N₁

(₃₂⁽¹⁾, ₃₁⁽¹⁾, ..., ₂⁽¹⁾, ₁⁽¹⁾).

    32,      31,     ...,   2,       1       номер разряда N₁

Заполнение накопителя N₂

(₆₄⁽¹⁾, ₆₃⁽¹⁾, ..., ₃₄⁽¹⁾, ₃₃⁽¹⁾).

   32,      31,     ...,     2,        1         номер разряда N₂

Заполнение накопителей N₁ и N₂ зашифровывается в режиме простой замены. Полученное в результате зашифрования заполнение накопителей N₁ и N₂ образует второй 64-разрядный блок гаммы шифра Г_Ш⁽²⁾, который суммируется поразрядно по модулю 2 в сумматоре СМ₅ со вторым блоком открытых данных Т₀⁽²⁾:

Г_Ш⁽²⁾  Т₀⁽²⁾ = Т_Ш⁽²⁾.

Выработка последующих блоков гаммы шифра Г_Ш⁽ⁱ⁾ и зашифрование соответствующих блоков открытых данных Т₀⁽ⁱ⁾ (i=3…m) производится аналогично.

         Если длина последнего m-го блока открытых данных Т₀^(m) меньше 64 разрядов, то из Г_Ш^(m) используется только соответствующее число разрядов гаммы шифра, остальные разряды отбрасываются.

         В канал связи или память ЭВМ передаются синхропосылка  и блоки зашифрованных данных  Т_Ш⁽¹⁾, Т_Ш⁽²⁾, ..., Т_Ш^(m).

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

         Уравнения расшифрования:

Т₀⁽¹⁾ = А()  Т_ш⁽¹⁾ = Г_ш⁽¹⁾  Т_ш⁽¹⁾,

Т₀⁽ⁱ⁾ = Г_ш⁽ⁱ⁾  Т_ш⁽ⁱ⁾ = A (Т_ш^(i–1) )  Т_ш⁽ⁱ⁾,  i = 2…m.

         Реализация процедуры расшифрования зашифрованных данных  в  режиме  гаммирования с  обратной  связью  происходит следующим образом. В КЗУ вводят 256 бит того же ключа, на котором осуществлялось зашифрование открытых блоков Т₀⁽¹⁾, Т₀⁽²⁾, ..., Т₀^(m). В накопители N₁ и N₂ вводится синхропосылка . Исходное заполнение накопителей N₁ и N₂ (синхропосылка ) зашифровывается в режиме простой замены. Полученное в результате зашифрования заполнение N₁ и N₂ образует первый блок гаммы шифра

Г_Ш⁽¹⁾ = А(),

который суммируется поразрядно по модулю 2 в сумматоре СМ₅ с блоком зашифрованных данных Т_Ш⁽¹⁾.

         В результате получается первый блок открытых данных

Т₀⁽¹⁾ = Г_ш⁽¹⁾  Т_ш⁽¹⁾.

Блок зашифрованных данных Т_ш⁽¹⁾ является исходным заполнением накопителей N₁ и N₂ для выработки второго блока гаммы шифра Г_Ш⁽²⁾: Г_Ш⁽²⁾ = А(Т_Ш⁽¹⁾). Полученное заполнение накопителей N₁ и N₂ зашифровывается в режиме простой замены. Образованный в результате зашифрования блок Г_Ш⁽²⁾ суммируется поразрядно по модулю 2 в сумматоре СМ₅ со вторым блоком зашифрованных данных Т_Ш⁽²⁾. В результате получают второй блок открытых данных. Аналогично в N₁, N₂ последовательно записывают блоки зашифрованных данных Т_Ш⁽²⁾, Т_Ш⁽³⁾, ..., Т_Ш^(m), из которых в режиме простой замены вырабатываются блоки гаммы шифра Г_Ш⁽³⁾, Г_Ш⁽⁴⁾, ..., Г_Ш^(m).

         Блоки гаммы шифра суммируются поразрядно по модулю 2 в сумматоре СМ₅ с блоками зашифрованных данных Т_Ш⁽³⁾,Т_Ш⁽⁴⁾, ..., Т_Ш^(m).

         В результате получают блоки открытых данных

Т₀⁽³⁾, Т₀⁽⁴⁾, ..., Т₀^(m),

при этом последний блок открытых данных Т₀^(m) может содержать меньше 64 разрядов.

Режим выработки имитовставки

            Имитовставка – это блок из Р бит, который вырабатывают по определенному правилу из открытых данных с использованием ключа и затем добавляют к зашифрованным данным для обеспечения их имитозащиты.

         Имитозащита – это защита системы шифрованной связи от навязывания ложных данных.

         В стандарте ГОСТ 28147-89 определяется процесс выработки имитовставки, который единообразен для любого из режимов шифрования данных. Имитовставка И_р вырабатывается из блоков открытых данных либо перед шифрованием всего сообщения, либо параллельно с шифрованием по блокам. Первые блоки открытых данных, которые участвуют в выработке имитовставки, могут содержать служебную информацию (например, адресную часть, время, синхропосылку) и не зашифровываются.

         Значение параметра Р (число двоичных разрядов в имитовставке)     определяется    криптографическими    требованиями с   учетом   того,  что   вероятность   навязывания   ложных   помех равна  1/2^р.

            Для выработки имитовставки открытые данные  представляют   в   виде   последовательности   64-разрядных   блоков   Т₀⁽ⁱ⁾, i = 1…m.

         Первый блок открытых данных Т₀⁽¹⁾ подвергают преобразованию (·), соответствующему первым 16 циклам алгоритма зашифрования в режиме простой замены. В качестве ключа для выработки имитовставки используют ключ длиной 256 бит, по которому шифруют данные.

         Полученное после 16 циклов 64-разрядное число (Т₀⁽¹⁾) суммируют по модулю 2 со вторым блоком открытых данных Т₀⁽²⁾. Результат суммирования ((Т₀⁽¹⁾)  Т₀⁽²⁾) снова подвергают преобразованию (·).

         Полученное 64-разрядное число ((Т₀⁽¹⁾)  Т₀⁽²⁾) суммируют по модулю 2 с третьим блоком Т₀⁽³⁾ и снова подвергают преобразованию (·), получая 64-разрядное число

(((Т₀⁽¹⁾)  Т₀⁽²⁾)  Т₀⁽³⁾),   и т.д.

            Последний блок Т₀^(m) (при необходимости дополненный нулями до полного 64-разрядного блока) суммируют по модулю 2 с результатом вычислений на шаге (m–1), после чего зашифровывают в режиме простой замены, используя преобразование (·).

         Из полученного 64-разрядного числа выбирают отрезок И_р (имитовставку) длиной Р бит:

И_р = [a^(m)_32–p+1(16), a^(m)_32–p+2(16), ..., a^(m)₃₂(16)],

где  a_i^(m) – i-й бит 64-разрядного числа, полученного после 16-го цикла последнего преобразования (·), 32 – р + 1  i  32.

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

Т_ш⁽¹⁾, Т_ш⁽²⁾, ..., Т_ш^(m), И_р.

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

Т_ш⁽¹⁾, Т_ш⁽²⁾, ..., Т_ш^(m)

расшифровываются, и из полученных блоков открытых данных Т₀⁽¹⁾, Т₀⁽²⁾, ..., Т₀^(m) аналогичным образом вырабатывается имитовставка И_р^. Эта имитовставка И_р^ сравнивается с имитовставкой И_р, полученной вместе с зашифрованными данными из канала связи или из памяти ЭВМ. В случае несовпадения имитовставок полученные при расшифровании блоки открытых данных Т₀⁽¹⁾, Т₀⁽²⁾, ..., Т₀^(m) считают ложными.

3.7. Блочные и поточные шифры

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

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

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

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

2) Зависимость или независимость функции шифрования от результатов шифрования предыдущих частей сообщения.

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

4) Симметрия или асимметрия функции шифрования. Эта важная характеристика определяет существенное различие между обычными симметричными (одноключевыми) криптосистемами и асимметричными (двухключевыми) криптосистемами с открытым ключом. Основное различие между ними состоит в том, что в асимметричной криптосистеме знания ключа шифрования (или расшифрования) недостаточно для раскрытия соответствующего ключа расшифрования (или шифрования).

         В табл. 3.11 приведены типы криптосистем и их основные характеристики.

Таблица 3.11

Основные характеристики криптосистем

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

         Поточные шифры широко применяются для шифрования преобразованных в цифровую форму речевых сигналов и цифровых данных, требующих оперативной доставки потребителю информации. До недавнего времени такие применения были преобладающими для данного метода шифрования. Это обусловлено, в частности, относительной простотой проектирования и реализации генераторов хороших шифрующих последовательностей. Но самым важным фактором, конечно, является отсутствие размножения ошибок в поточном шифре. Стандартным методом генерирования последовательностей для поточного шифрования является метод, применяемый в стандарте шифрования DES в режиме обратной связи по выходу (режим OFB).

         При блочном шифровании открытый текст сначала разбивается на равные по длине блоки, затем применяется зависящая от ключа функция шифрования для преобразования блока открытого текста длиной  m  бит в блок шифртекста такой же длины. Достоинством блочного шифрования является то, что каждый бит блока шифртекста зависит от значений всех битов соответствующего блока открытого текста, и никакие два блока открытого текста не могут быть представлены одним и тем же блоком шифртекста. Алгоритм блочного шифрования может использоваться в различных режимах. Четыре режима шифрования алгоритма DES фактически применимы к любому блочному шифру: режим прямого шифрования или шифрования с использованием электронной книги кодов ЕСВ (Electronic code Book), шифрование со сцеплением блоков шифртекста СВС (Cipher block chaining), шифрование с обратной связью по шифртексту CFB (Cipher feedback) и шифрование с обратной связью по выходу OFB (Output feedback).

         Основным достоинством прямого блочного шифрования ECB является то, что в хорошо спроектированной системе блочного шифрования небольшие изменения в шифртексте вызывают большие и непредсказуемые изменения в соответствующем открытом тексте, и наоборот. Вместе с тем применение блочного шифра в данном режиме имеет серьезные недостатки. Первый из них заключается в том, что вследствие детерминированного характера шифрования при фиксированной длине блока 64 бита можно осуществить криптоанализ шифртекста "со словарем" в ограниченной форме. Это обусловлено тем, что идентичные блоки открытого текста длиной 64 бита в исходном сообщении представляются идентичными блоками шифртекста, что позволяет криптоаналитику сделать определенные выводы о содержании сообщения. Другой потенциальный недостаток этого шифра связан с размножением ошибок. Результатом изменения только одного бита в принятом блоке шифртекста будет неправильное расшифрование всего блока. Это, в свою очередь, приведет к появлению искаженных битов (от 1 до 64) в восстановленном блоке исходно-го текста.

Если Вам понравилась эта лекция, то понравится и эта - 1 Вопросы к экзамену.

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

         Криптосистема с открытым ключом также является системой блочного шифрования и должна оперировать блоками довольно большой длины. Это обусловлено тем, что криптоаналитик знает открытый ключ шифрования и мог бы заранее вычислить и составить таблицу соответствия блоков открытого текста и шифртекста. Если длина блоков мала, например 30 бит, то число возможных блоков не слишком большое (при длине 30 бит это 2³⁰ = 10⁹), и может быть составлена полная таблица, позволяющая моментально расшифровать любое сообщение с использованием известного открытого ключа. Асимметричные криптосистемы с открытым ключом подробно разбираются в следующей главе.

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

         Практически важным шифром с обратной связью является шифр со сцеплением блоков шифртекста СВС. В этом случае m бит предыдущего шифртекста суммируются по модулю 2 со следующими m битами открытого текста, а затем применяется алгоритм блочного шифрования под управлением ключа для получения следующего блока шифртекста. Еще один вариант шифра с обратной связью получается из стандартного режима CFB алгоритма DES, т.е. режима с обратной связью по шифртексту.

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

         На практике для шифрования длинных сообщений применяют поточные шифры или шифры с обратной связью. Выбор конкретного типа шифра зависит от назначения системы и предъявляемых к ней требований.