Современные алгоритмы шифрования

Алгоритм Rijndael не похож на большинство известных алгоритмов симметричного шифрования, структура которых носит название "сеть Фейстеля" и аналогична российскому ГОСТ 28147-89. Особенность сети Фейстеля состоит в том, что входное значение разбивается на два и более субблоков, часть из которых в каждом раунде обрабатывается по определенному закону, после чего накладывается на необрабатываемые субблоки (см. рис. 1).

В отличие от отечественного стандарта  шифрования, алгоритм Rijndael представляет блок данных в виде двухмерного байтового массива размером 4X4, 4X6 или 4X8 (допускается использование нескольких фиксированных размеров шифруемого блока информации). Все операции выполняются с отдельными байтами массива, а также с независимыми столбцами и строками.

Алгоритм Rijndael выполняет четыре преобразования: BS (ByteSub) - табличная замена каждого байта массива (рис. 3); SR (ShiftRow) - сдвиг строк массива (рис. 4). При этой операции первая строка остается без изменений, а остальные циклически побайтно сдвигаются влево на фиксированное число байт, зависящее от размера массива. Например, для массива размером 4X4 строки 2, 3 и 4 сдвигаются соответственно на 1, 2 и 3 байта. Далее идет MC (MixColumn) - операция над независимыми столбцами массива (рис. 5), когда каждый столбец по определенному правилу умножается на фиксированную матрицу c(x). И, наконец, AK (AddRoundKey) - добавление ключа. Каждый бит массива складывается по модулю 2 с соответствующим битом ключа раунда, который, в свою очередь, определенным образом вычисляется из ключа шифрования (рис. 6).

Рис. 3. Операция BS.

Рис. 4. Операция SR.

Рис. 5. Операция MC.

Рис. 6. Операция AK.

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

AK, {BS, SR, MC, AK} (повторяется R-1 раз), BS, SR, AK.

Рис. 7. Раунд алгоритма  Rijndael.

Количество раундов шифрования (R) в алгоритме Rijndael переменное (10, 12 или 14 раундов) и зависит от размеров блока и ключа шифрования (для ключа также предусмотрено несколько фиксированных размеров).

Расшифрование выполняется с помощью следующих обратных операций. Выполняется обращение таблицы и табличная замена на инверсной таблице (относительно применяемой при зашифровании). Обратная операция к SR - это циклический сдвиг строк вправо, а не влево. Обратная операция для MC - умножение по тем же правилам на другую матрицу d(x), удовлетворяющую условию: c(x) * d(x) = 1. Добавление ключа AK является обратным самому себе, поскольку в нем используется только операция XOR. Эти обратные операции применяются при расшифровании в последовательности, обратной той, что использовалась при зашифровании.

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

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

Асимметричное шифрование

Алгоритмы асимметричного шифрования, как уже отмечалось, используют два  ключа: k1 - ключ зашифрования, или открытый, и k2 - ключ расшифрования, или секретный. Открытый ключ вычисляется из секретного: k1 = f(k2).

Асимметричные алгоритмы шифрования основаны на применении однонаправленных функций. Согласно определению, функция y = f(x) является однонаправленной, если: ее легко вычислить для всех возможных  вариантов x и для большинства  возможных значений y достаточно сложно вычислить такое значение x, при  котором y = f(x).

Примером однонаправленной функции  может служить умножение двух больших чисел: N = P*Q. Само по себе такое  умножение - простая операция. Однако обратная функция (разложение N на два  больших множителя), называемая факторизацией, по современным временным оценкам  представляет собой достаточно сложную  математическую задачу. Например, разложение на множители N размерностью 664 бит при P ? Q потребует выполнения примерно 1023 операций, а для обратного вычисления х для модульной экспоненты y = ax mod p при известных a, p и y (при такой же размерности a и p) нужно выполнить примерно 1026 операций. Последний из приведенных примеров носит название - "Проблема дискретного логарифма" (DLP - Discrete Logarithm Problem), и такого рода функции часто используются в алгоритмах асимметричного шифрования, а также в алгоритмах, используемых для создания электронной цифровой подписи.

Еще один важный класс функций, используемых в асимметричном шифровании, - однонаправленные функции с потайным ходом. Их определение  гласит, что функция является однонаправленной с потайным ходом, если она является однонаправленной и существует возможность  эффективного вычисления обратной функции x = f-1(y), т. е. если известен "потайной ход" (некое секретное число, в  применении к алгоритмам асимметричного шифрования - значение секретного ключа).

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

Алгоритм RSA

Разработанный в 1978 г. тремя авторами (Rivest, Shamir, Adleman), он получил свое название по первым буквам фамилий разработчиков. Надежность алгоритма основывается на сложности факторизации больших чисел и вычисления дискретных логарифмов. Основной параметр алгоритма RSA - модуль системы N, по которому проводятся все вычисления в системе, а N = P*Q (P и Q - секретные случайные простые большие числа, обычно одинаковой размерности).

Секретный ключ k2 выбирается случайным  образом и должен соответствовать  следующим условиям:

1<k2<F(N)

НОД(k2, F(N)) = 1,

где НОД - наибольший общий делитель, т. е. k1 должен быть взаимно простым  со значением функции Эйлера F(N), причем последнее равно количеству положительных целых чисел в  диапазоне от 1 до N, взаимно простых  с N, и вычисляется как F(N) = (P - 1)*(Q - 1).

Открытый ключ k1 вычисляется из соотношения (k2*k1 ) = 1 mod F(N), и для этого используется обобщенный алгоритм Евклида (алгоритм вычисления наибольшего общего делителя). Зашифрование блока данных M по алгоритму RSA выполняется следующим образом: C = M[в степени k1] mod N. Заметим, что, поскольку в реальной криптосистеме с использованием RSA число k1 весьма велико (в настоящее время его размерность может доходить до 2048 бит), прямое вычисление M[в степени k1] нереально. Для его получения применяется комбинация многократного возведения M в квадрат с перемножением результатов.

Обращение данной функции при больших  размерностях неосуществимо; иными  словами, невозможно найти M по известным C, N и k1. Однако, имея секретный ключ k2, при помощи несложных преобразований можно вычислить M = Ck2 mod N. Очевидно, что, помимо собственно секретного ключа, необходимо обеспечивать секретность параметров P и Q. Если злоумышленник добудет их значения, то сможет вычислить и секретный ключ k2.

Какое шифрование лучше?

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

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

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