Практическая реализация и исследование криптостойкости. Часть 2.

Страницы:   1   2   3   4   5   6

---

1.2 Сеть Фейштеля как популярный атрибут блочных шифров

 

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

Классическая сеть Фейштеля имеет следующую структуру (рис. 2):

 

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

Сразу же возникает вопрос, – является ли данная схема обратимой? Очевидно, да. Сеть Фейштеля обладает тем свойством, что даже если в качестве образующей функции F будет использовано необратимое преобразование, то и в этом случае вся цепочка будет восстановима. Это происходит вследствие того, что для обратного преобразования сети Фейштеля не нужно вычислять функцию F^-1.

Более того, как нетрудно заметить, сеть Фейштеля симметрична. Использование операции XOR, обратимой своим же повтором, и инверсия последнего обмена ветвей делают возможным раскодирование блока той же сетью Фейштеля, но с инверсным порядком параметров V_i. Заметим, что для обратимости сети Фейштеля не имеет значение является ли число раундов четным или нечетным числом. В большинстве реализаций схемы, в которых оба вышеперечисленные условия (операция XOR и уничтожение последнего обмена) сохранены, прямое и обратное преобразования производятся одной и той же процедурой, которой в качестве параметра передается вектор величин V_i либо в исходном, либо в инверсном порядке.

С незначительными доработками сеть Фейштеля можно сделать и абсолютно симметричной, то есть выполняющей функции шифрования и расшифрования одним и тем же набором операций. Математическим языком это записывается как «Функция EnCrypt тождественно равна функции DeCrypt». Если мы рассмотрим граф состояний криптоалгоритма, на котором точками отмечены блоки входной и выходной информации, то при каком-то фиксированном ключе для классической сети Фейштеля мы будем иметь картину, изображенную на рис. 3а, а во втором случае каждая пара точек получит уникальную связь, как изображено на рис. 3б.

 

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

 

А вот модификацию сети Фейштеля для большего числа ветвей применяют гораздо чаще. Это в первую очередь связано с тем, что при больших размерах кодируемых блоков (128 и более бит) становится неудобно работать с математическими функциями по модулю 64 и выше. Как известно, основные единицы информации обрабатываемые процессорами на сегодняшний день – это байт и двойное машинное слово 32 бита. Поэтому все чаще и чаще в блочных криптоалгоритмах встречается сеть Фейштеля с 4-мя ветвями. Самый простой принцип ее модификации изображен на рис. 5а. Для более быстрого перемешивания информации между ветвями (а это основная проблема сети Фейштеля с большим количеством ветвей) применяются две модифицированные схемы, называемые «type-2» и «type-3». Они изображены на рис. 5б и 5в.

 

Сеть Фейштеля надежно зарекомендовала себя как криптостойкая схема произведения преобразований, и ее можно найти практически в любом современном блочном шифре. Незначительные модификации касаются обычно дополнительных начальных и оконечных преобразований (англоязычный термин – whitening) над шифруемым блоком. Подобные преобразования, выполняемые обычно также либо «исключающим ИЛИ» или сложением имеют целью повысить начальную рандомизацию входного текста. Таким образом, криптостойкость блочного шифра, использующего сеть Фейштеля, определяется на 95% функцией F и правилом вычисления V_i из ключа. Эти функции и являются объектом все новых и новых исследований специалистов в области криптографии.

 

1.3 Стандарт шифрования данных DES и AES

 

Одним из самых распространенных алгоритмов блочного шифрования, рекомендованных Национальным бюро стандартов США в качестве основного средства криптографической защиты информации как в государственных, так и в коммерческих структурах, является DES (Data Encryption Standard), который получил достаточно широкое распространение в свое время. Он был разработан в 1977г., однако уже в 1988г [3. С. 34]. Национальное бюро стандартов рекомендовало использовать DES только в системах электронного перевода. С учетом выявленных недостатков DES в начальный вариант стандарта постоянно вносятся изменения; появляются также и новые алгоритмы, использующие в качестве основы DES – NewDES, TripleDES, LUCIFER, MADRYGA, FEAL, REDOC, LOKI, KHUFU, KHAFRE, IDEA, MMB, CA-1.1, SKIPJACK, CAST, BLOWFISH, SAFER, 3-WAY, CRAB, и другие. Однако на текущий момент стандарт DES полностью неприемлем для использования по двум причинам:

1. Основной – длина его ключа составляет 56 бит, что чрезвычайно мало на современном этапе развития ЭВМ.
2. Второстепенной – при разработке алгоритм был ориентирован на аппаратную реализацию, то есть содержал операции, выполняемые на микропроцессорах за неприемлемо большое время (например, такие как перестановка бит внутри машинного слова по определенной схеме).

Все это сподвигло Американский институт стандартизации NIST (National Institute of Standards & Technology) в 1996 г на поиски нового стандарта симметричного криптоалгоритма, впоследствии названного AES (Advanced Encryption Standard), который стал де-факто мировым криптостандартом на ближайшие 10-20 лет. На сей раз уже были учтены основные промахи шифра-предшественника, а к разработке были подключены самые крупные центры по криптологии со всего мира.

Требования, предъявленные на AES, были предельно просты [5. С. 51]:

1. Алгоритм должен быть симметричным.
2. Алгоритм должен быть блочным шифром.
3. Алгоритм должен иметь длину блока 128 бит, и поддерживать три длины ключа: 128, 192 и 256 бит.

В течение 2 лет специалисты комитета, исследуя самостоятельно, и изучая публикации других исследователей, выбрали 5 лучших представителей (Табл. 3).

Табл. 3. 5 лучших представителей AES

 

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

2 октября 2000 года NIST объявил, что самым лучшим криптоалгоритмом шифрования данных является алгоритм Rijndael (произносится «Рейн-дал»). Этот алгоритм был разработан Винсентом Райманом и Йоан Даменом и представляет собой алгоритм, не использующий сети Фейштеля. С этого момента с алгоритма-победителя сняты все патентные ограничения – его можно будет использовать в любой криптопрограмме без отчисления каких-либо средств создателю.

 

1.4 Схемы построения широко распространенных алгоритмов шифрования

 

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

 

1.4.1 Обзор симметричных криптосистем

 

Все нижеследующие симметричные блочные криптоалгоритмы содержат следующие обозначения и производятся по определенной схеме (слева даны условные обозначения этих операций на графических схемах алгоритмов) (Табл. 4):

Табл. 4. Обозначения операций преобразования

В качестве параметра V для любого из этих преобразований может использоваться [5. С. 77-98]:

1. Фиксированное число (например, X’=X+125)
2. Число, получаемое из ключа (например, X’=X+F(Key))
3. Число, получаемое из независимой части блока (например, X₂‘=X₂+F(X₁))

 

1.4.1.1 Шифр MARS

 

Шифр состоит из трех видов операций, которые повторяются сначала в прямом, а затем в инверсном порядке. На первом шаге идет классическое входное забеливание: ко всем байтам исходного текста добавляются байты из материала ключа.

Второй этап: прямое перемешивание, однотипная операция, имеющая структуру сети Фейштеля повторяется 8 раз. Однако, на этом этапе не производится добавление материала ключа. Цель данного преобразования – тщательная рандомизация данных и повышение стойкости шифра к некоторым видам атак (рис.6).

 

 

Третий этап: собственно шифрование. В нем используется сеть Фейштеля треьего типа с 4 ветвями, то есть значения трех функций, вычисленных от одной ветви накладываются соответственно на три других, затем идет перестановка машинных слов. Эта операция также повторяется 8 раз (рис.6). Именно на этом этапе происходит смешивание текста с основной (большей) частью материала ключа. Сами функции, накладываемые на ветви, изображены на рис. 7. Как видим, в алгоритме MARS использованы практически все виды операций, применяемых в криптографических преобразованиях: сложение, «исключающее ИЛИ», сдвиг на фиксированное число бит, сдвиг на переменное число бит, умножение и табличные подстановки.

Во второй части операции шифрования повторяются те же операции, но в обратном порядке: сначала шифрование, затем перемешивание, и, наконец, забеливание. При этом во вторые варианты всех операций внесены некоторые изменения таким образом, чтобы криптоалгоритм в целом стал абсолютно симметричным. То есть, в алгоритме MARS для любого X выполняется выражение EnCrypt(EnCrypt(X))=X.

 

1.4.1.2 Шифр Serpent

 

Алгоритм разработан группой ученых из нескольких исследовательских центров мира. Алгоритм представляет собой сетей Фейштеля для четырех ветвей смешанного типа (рис 8) [3. С. 45]: 2 четные ветви изменяют совместно значения нечетных, затем меняются местами. В качестве криптопреобразований используются только «исключающее ИЛИ», табличные подстановки и битовые сдвиги. Алгоритм состоит из 32 раундов. Сами раунды составлены таким образом, что добавление к ветвями материала ключа на первом и последнем раундах образует входное и выходное забеливание.

 

1.4.1.3 Шифр TwoFish

 

Алгоритм разработан команией Counterpain Security Systems, возглавляемой Брюсом Шнайером (англ. Bruce Schneier). Предыдущая программная разработка этой фирмы, называвшаяся BlowFish, являлась и до сих пор является признанным криптостойким алгоритмом [4. С. 78].

В алгоритме TwoFish разработчики оставили некоторые удачные решения из проекта-предшественника, кроме этого произвели тщательные исследования по перемешиванию данных в сети Фейштеля. Алгоритм представляет собой сеть Фейштеля смешанного типа: первая и вторая ветвь на нечетных раундах производят модификацию третьей и четвертой, на четных раундах ситуация меняется на противоположную. В алгоритме используется криптопреобразование Адамара (англ. Pseudo-Hadamar Transform) – обратимое арифметическое сложение первого потока со вторым, а затем второго с первым.

Единственным нарицанием, поступившим в адрес TwoFish от независимых исследователей, является тот факт, что при расширении материала ключа в алгоритме используется сам же алгоритм. Двойное применение блочного шифра довольно сильно усложняет его анализ на предмет наличия слабых ключей или недокументированных замаскированных связей между входными и выходными данными (рис. 9).

 

1.4.1.4 Шифр Rijndael

 

Данный алгоритм разработан двумя специалистами по криптографии из Бельгии. Он является нетрадиционным блочным шифром, поскольку не использует сеть Фейштеля для криптопреобразований. Алгоритм представляет каждый блок кодируемых данных в виде двумерного массива байт размером 4х4, 4х6 или 4х8 в зависимости от установленной длины блока. Далее на соответствующих этапах преобразования производятся либо над независимыми столбцами, либо над независимыми строками, либо вообще над отдельными байтами в таблице [11. С. 66-77].

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

Алгоритм состоит из некоторого количества раундов (от 10 до 14 – это зависит от размера блока и длины ключа), в которых последовательно выполняются следующие операции :

ByteSub – табличная подстановка 8х8 бит (рис. 10),

 

MixColumn – математическое преобразование, перемешивающее данные внутри столбца (рис.12),

 

AddRoundKey – добавление материала ключа операцией XOR (рис.13).

 

В последнем раунде операция перемешивания столбцов отсутствует, что делает всю последовательность операций симметричной.

 

1.4.1.5 Стандарт шифрования данных ГОСТ 28147-89

 

Также следует указать российский стандарт криптографического преобразования текста для информационных систем. Он носит обязательный характер для государственных органов, организаций, предприятий, банковских и иных учреждений, чья деятельность связана с обеспечением информационной безопасности государства. Для других организаций и частных лиц, ГОСТ имеет рекомендательный характер [8].

Данный стандарт формировался с учетом мирового опыты и, в частности, были приняты во внимание недостатки и нереализованные возможности алгоритма DES, поэтому использование стандарта ГОСТ предпочтительнее. Алгоритм шифрования построен с использованием сети Фейштеля. Алгоритм достаточно сложен и ниже будет описана в основном его концепция.

Будем использовать следующие операции сложения:

• AÅB — побитовое сложение по модулю 2;
• A[+]B — сложение по модулю 2³²;
• A{+}B — сложение по модулю 2³²-1;

Алгоритм криптографического преобразования предусматривает несколько режимов работы: 1) простая замена; 2) гаммирование; 3) гаммирование с обратной связью. Во всех режимах используется ключ W длиной 256 бит, представляемый в виде восьми 32-разрядных чисел x(i).

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

Для расшифрования используется тот же ключ, но процесс расшифрования является инверсным по отношению к исходному. Самый простой из возможных режимов – простая замена.

Простая замена. Пусть открытые блоки разбиты на блоки по 64 бит в каждом, которые обозначим как T(j). Очередная последовательность бит T(j) разделяется на две последовательности B(0) и A(0) по 32 бита (правый и левый блоки). Далее выполняется итеративный процесс шифрования описываемый следующими формулами, вид который зависит от i:

Для i=1, 2, …, 24, j=(i-1) mod 8;

A(i) = f(A(i-1) [+] x(j)) Å B(i-1)

B(i) = A(i-1)

Для i=25, 26, …, 31, j=32-i;

A(i) = f(A(i-1) [+] x(j)) Å B(i-1)

B(i) = A(i-1)

Для i=32

A(32) = A(31)

B(32) = f(A(31) [+] x(0)) Å B(31).

Здесь i обозначает номер итерации. Функция f – функция шифрования.

Функция шифрования включает две операции над 32-разрядным аргументом.

Первая операция является подстановкой K. Блок подстановки К состоит из 8 узлов замены К(1)…К(8) с памятью 64 бита каждый. Поступающий на блок подстановки 32-разрядный вектор разбивается на 8 последовательно идущих 4-разрядных вектора, каждый из который преобразуется в 4-разрядный вектор соответствующим узлом замены, представляющим из себя таблицу из 16 целых чисел в диапазоне 0…15. Входной вектор определяет адрес строки в таблице, число из которой является выходным вектором. Затем 4-разрядные векторы последовательно объединяются в 32-разрядный выходной.

Вторая операция – циклический сдвиг влево 32-разрядного вектора, полученного в результате подстановки К. 64-разрядный блок зашифрованных данных Т представляется в виде Т=А(32)В(32).

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

Гаммирование. Открытые данные, разбитые на 64-разрядные блоки T(i) (i=1,2,…,m) (m определяется объемом шифруемых данных), зашифровываются в режиме гаммирования путем поразрядного сложения по модулю 2 с гаммой шифра Г_ш, которая вырабатывается блоками по 64 бит, т.е.

Г_ш=(Г(1),Г(2),….,Г(m)).

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

Ш(i)=A(Y(i-1) Å C2, Z(i-1)) {+} C(1) Å T(i)=Г(i) Å T(i)

В этом уравнении Ш(i) обозначает 64-разрядный блок зашифрованного текста, А — функцию шифрования в режиме простой замены (аргументами этой функции являются два 32-разрядных числа). С1 и С2 — константы, заданные в ГОСТ 28147-89. Величины y(i) и Z(i) определяются итерационно по мере формирования гаммы следующим образом:

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

(Y(i),Z(i))=(Y(i-1) [+] C2, Z(i-1) {+} C(1)), i=1, 2, …, m.

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

Гаммирование с обратной связбю очень похож на режим гаммирования. Как и в режиме гаммирования открытые данные, разбитые на 64-разрядные блоки T(i), зашифровываются путем поразрядного сложения по модулю 2 с гаммой шифра Г_ш, которая вырабатывается блоками по 64 бит:

Г_ш=(Г(1), Г(2), …, Г(m)).

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

Ш(1)=A(S)ÅT(1)=Г(1)ÅT(1),

Ш(i)=A(Ш(i-1)ÅT(i)=Г(i)ÅT(i), i=2, 3, …, m.

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

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

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

 

1.4.2 Обзор ассиметричных криптосистем

 

Рассматриваются асимметричные алгоритмы: система с открытым ключом RSA, криптосистема Эль-Гамаля и криптосистемы на основе эллиптических уравнений.

 

1.4.2.1 Система с открытым ключом RSA

 

Наиболее популярная система с открытым ключом – криптосистема RSA, была разработана в 1977 году и получила название в честь ее создателей: Рона Ривеста (Rivest), Ади Шамира (Shamir) и Леонарда Адлемана (Adleman). Алгоритм RSA стал первым полноценным алгоритмом с открытым ключом, который может работать как в режиме шифрования данных, так и в режиме электронно-цифровой подписи [3. С. 60-69].

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

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

В настоящее время алгоритм RSA используется во многих стандартах, среди которых SSL, S-HHTP, S-MIME, S/WAN, STT и PCT.

Первым этапом любого асимметричного алгоритма является создание пары ключей: открытого и закрытого и распространение открытого ключа «по всему миру». Для алгоритма RSA этап создания ключей состоит из следующих операций:

1. Выбираются два простых (!) числа p и q.
2. Вычисляется их произведение n(=p*q).
3. Выбирается произвольное число e (e<n), такое, что НОД(e,(p-1)(q-1))=1, то есть e должно быть взаимно простым с числом (p-1)(q-1).
4. Методом Евклида решается в целых числах (!) уравнение e*d+(p-1)(q-1)*y=1. Здесь неизвестными являются переменные d и y – метод Евклида как раз и находит множество пар (d, y), каждая из которых является решением уравнения в целых числах.
5. Два числа (e, n) – публикуются как открытый ключ.
6. Число d хранится в строжайшем секрете – это и есть закрытый ключ, который позволит читать все послания, зашифрованные с помощью пары чисел (e, n).

Как же производится собственно шифрование с помощью этих чисел:

1. Отправитель разбивает свое сообщение на блоки, равные k=[log₂(n)] бит, где квадратные скобки обозначают взятие целой части от дробного числа.
2. Подобный блок может быть интерпретирован как число из диапазона (0;2^k-1). Для каждого такого числа (назовем его m_i) вычисляется выражение c_i=((m_i)^e)mod n. Блоки c_i и есть зашифрованное сообщение Их можно спокойно передавать по открытому каналу, поскольку.операция возведения в степень по модулю простого числа, является необратимой математической задачей. Обратная ей задача носит название «логарифмирование в конечном поле» и является на несколько порядков более сложной задачей. То есть даже если злоумышленник знает числа e и n, то по c_i прочесть исходные сообщения m_i он не может никак, кроме как полным перебором m_i.

А вот на приемной стороне процесс расшифрования все же возможен, и поможет нам в этом хранимое в секрете число d. Достаточно давно была доказана теорема Эйлера, частный случай которой утверждает, что если число n представимо в виде двух простых чисел p и q, то для любого x имеет место равенство (x^(p-1)(q-1))mod n=1. Для расшифрования RSA-сообщений воспользуемся этой формулой. Возведем обе ее части в степень (-y) : (x^{(-y)(p-1)(q-1)})mod n = 1^(-y) = 1. Теперь умножим обе ее части на x: (x^{(-y)(p-1)(q-1)+1})mod n = 1*x = x.

А теперь вспомним каким образом создавались открытый и закрытый ключи. С помощью алгоритма Евклида подбиралась d такое, что e*d+(p-1)(q-1)*y=1, то есть e*d=(-y)(p-1)(q-1)+1. А следовательно в последнем выражении предыдущего абзаца можно заменить показатель степени на число (e*d). Получаем (x^e*d)mod n=x. То есть для того чтобы прочесть сообщение c_i=((m_i)^e)mod n достаточно возвести его в степень d по модулю m: ((c_i)^d)mod n = ((m_i)^e*d)mod n = m_i.

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

---

Страницы:   1   2   3   4   5   6