Как работает AES (Advanced Encryption Standard). Объяснение для гуманитариев

Однажды я проверял за переводчиком проект по СХД, и там было такое предложение: 

Data can be automatically encrypted inside disk storage systems using high-security 128-bit AES technology… 

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

… при помощи 128-разрядной технологии AES … 

Я, конечно, уверенно такое исправил на 128-битное шифрование AES, но потом задумался: «А вдруг там все-таки разряды, а не биты? Да и вообще, как этот алгоритм работает?». Полез как водится на хабр, потом в википедии и прочие справочники — описаний либо нет, либо они написаны таким языком, что гуманитарии типа меня год буду разбираться. 

Удалось найти достойное видео на английском, где работа алгоритма разложена по полкам — некоторые вещи опущены, но по крайней мере после его изучения, переводчик уже не будет задумываться о том, разряды там или биты. 

Мы его транскрибировали и перевели, оно ниже, с незначительными купюрами. Желаю приятного чтения. 

 

1. Предисловие

— … ты слышал название Rijndael? 

— Рэйндал? Нет.

— Нет? Возможно, такая подача материала может кого-то раздражать, но мне удалось в предыдущем видео про историю AES ни слова не сказать о том, как этот алгоритм работает. 

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

Это значит, что AES берет 128 бит исходного сообщения и превращает их с помощью некоего ключа в 128-битный шифротекст. Размер ключа может быть 128, 192 или 256 бит. 

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

Если вы обнаружите, что ваш браузер использует 128 бит, это нормально. Ключ такого размера был указан как часть AES, поэтому алгоритму Rjjndael этого должно быть достаточно. Просто представьте: у нас есть 16 байтов, или 128 бит, мы что-то с ними делаем и получаем шифротекст. И поскольку все происходит в SP-сети, то есть подстановочно-перестановочной, мы что-нибудь подставим, или применим метод конфузии, и что-нибудь переставим, переместим элементы, чтобы также использовать метод диффузии. Вы же не хотите, чтобы у вас было как в Энигме — один байт на входе и один на выходе, ибо это очень легко поддается криптоанализу, и история это подтверждала неоднократно.

 

2. Деление на блоки.

Итак, вместо длинных рядов бит или байтов, как в большинстве алгоритмов шифрования, в AES элементы организованы в матрицы 4 на 4 по 128 бит. Получается, нас есть сообщение размером 128 бит или 16 байтов в виде матрицы 4 на 4. 

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

В первой ячейке будет байт 0, здесь байт 1, байт 2, байт 3, затем 4, 5, 6, 7, то есть байты размещаются по столбцам сверху вниз. 

Иными словами, мы берем 128 бит нашего сообщения и расписываем его в таком порядке. 

Затем мы начнем применять к ним функции SP-сети: переставлять элементы и подставлять байты на место других, то есть мы собираемся трансформировать исходное сообщение таким образом, чтобы взломщики не могли его прочитать.

В алгоритме AES происходит несколько разных операций, но запомните, что все они совершаются в матрице 4 на 4.

Так что же мы будем делать? Мы работаем с SP-сетью, поэтому мы совершим подстановки и перестановки элементов с помощью разных команд и потом в определенный момент добавим наш ключ.

 

3. Наложение фрагмента ключа через XOR

Итак, это наш открытый текст и, в первую очередь, мы берем часть нашего ключа и совершаем сложение по модулю 2, или функцию XOR.

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

• Сначала функция SubBytes подставляет на место одних байтов другие из таблицы замены (S-блока). 
• Затем ShiftRows сдвигает элементы в каждом ряду матрицы. 
• После этого MixColumns перемешивает элементы в каждом столбце. Первый шаг – это подстановка, второй и третий – перестановка. 
• В конце каждого раунда мы добавляем раундовый ключ (Round Key). 

Всё это и есть один раунд. 

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

Если размер вашего ключа 128 бит, у вас 10 таких раундов, если 192 бита – 12 раундов, если 256 бит – 14 раундов. 

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

Таким образом, у нас получится ключ 0, затем ключ 1, ключ 2 и так далее, в зависимости от того, какой раунд мы рассматриваем, то есть в каждом раунде используется часть расширенного ключа.

Мы не будем подробно говорить о расписании ключей, это довольно простой процесс и, подразумевается, что, прежде всего, он должен быть быстрым. KeyExpansion берет ваш исходный ключ и расширяет его настолько, чтобы его можно было использовать в разных раундах. Итак, это был очень коротенький обзор алгоритма AES. 

 

4. О сложении: XOR и поля Галуа

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

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

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

Мы уже немного рассказывали о конечных полях или полях Галуа в своем видео про кодирование с помощью кода Рида – Соломона (Reed Solomon encoding).

Смысл заключается в использовании теории поля Галуа для конечных полей и выполнении множества длинных делений и сложений чисел в пределах этого поля. 

Например, у вас есть некоторое количество элементов, скажем, все числа от 0 до 10, например, и у вас есть различные операции, которые можно выполнять в пределах этого поля. Таким образом, в Rjjndael у нас поле Галуа из 2’8 элементов.

А затем в этом поле можно производить сложение, вычитание, умножение и деление или вычисление мультипликативного обратного X’-1.

Важно помнить о конечном поле, если мы не будем углубляться в математику, что 2’8 элементов – это 16 байтов, так что каждый из элементов в этом поле Галуа – это байт. Так что мы начинаем с 00000000 и движемся к 11111111. Таким образом, в этом конкретном конечном поле 256 таких элементов. 

Если мы берем наше изначальное сообщение, нужно знать, даже если вы не взглянете на него снова, что какую бы операцию мы с ним не проводили, мы получим другой элемент их этого поля. Мы никогда не выходим за пределы поля, ни за верхнюю, ни за нижнюю границу, знаете ли, и не уходим в отрицательные числа или что-то в этом роде, здесь нет чисел с плавающей запятой и ничего подобного. Если мы берем одно из чисел и добавляем его к другому, то находим третье в пределах поля. Точно также, если мы умножаем или наоборот вычисляем мультипликативный обратный, или делим, мы переходим к другому числу. Поле Галуа довольно удобно для построения шифра на его основе, потому что большинство действий имеют свою противоположность, например, сложение и вычитание отменяют друг друга, так же как умножение и вычисление мультипликативного обратного или деление, и мы можем перемещаться по этому полю. Но мы всегда остаемся в пределах наших байтов. Если мы представляем путь данных в AES в виде матрицы 4 на 4, это наш 128-битный блок, и мы можем совершать операции в пределах этого конечного поля, и после всех действий мы всё еще будем в нем.

Количество бит не увеличится до 130 или 140, и никакой подобной катастрофы не произойдет.

Так вот, вернемся к схеме, и, держа ее в голове, поговорим о том, что делает каждая функция. 

 

5. Внутри раунда. Операция 1: SubBytes

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

Итак, у нас есть наша матрица, давайте пока отложим нашу схему… у нас есть наша матрица (нам нужно было бы нарисовать ее много раз). Пишем байт 0, байт 1, и так до байта 15. 

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

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

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

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

 

6. Внутри раунда. Операция 2: ShiftRows

Мы взяли наш открытый текст, применили часть нашего раундового ключа, то есть наш первоначальный ключ, и затем в начале раунда мы сделали подстановку, используя S-блок. После этого мы собираемся сдвинуть строки с помощью функции ShiftRows.

На самом деле это просто. С первым рядом мы ничего не делаем.

Второй ряд мы передвинем на один шаг влево. Тогда байт 1 пройдет весь путь в конец строки, потому что элементы движутся по кругу. Этот байт движется сюда, этот – сюда, а этот – сюда. А первый, очевидно, движется в конец строки.

Этот ряд тоже движется, но уже на два шага влево. Так что этот байт движется сюда, этот – сюда, этот – в конец ряда и так далее, а четвертый ряд сдвигается на три шага влево, результат такой же, как если бы этот ряд сдвигался вправо на один шаг.

Так что этот байт движется вот сюда, этот – сюда и так далее.

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

Итак, мы просто берем байты и переставляем их в другое место в пределах матрицы. Теперь мы подходим к функции MixColumns, которая следует за SubBytes. 

 

7. Внутри раунда. Операция 3: MixColumns

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

Мы возьмем первый столбец и смешаем байты в нем, а потом отдельно второй, третий и так далее. Так что это операция производится в пределах столбца. Этот байт переместился сюда, а затем перемешался с другими элементами в этом столбце. Этот передвинулся сюда и перемешался с другими элементами в этом столбце. Таким образом, эти две операции в тандеме хорошенько всё перемешивают, если представить это с технической точки зрения. Здесь используется матричное умножение. 

Давай просто оторвем еще один листочек. Нам сегодня нужно много бумаги. Возьмем один столбец с элементами, например, С0, С1, С2, С3 и умножим его как вектор на матрицу. 

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

Эти числа достаточно велики и настолько перемешаны, что здесь происходят довольно интересные процессы, но одновременно эти числа и достаточно малы, чтобы процессы происходили быстро, как в более сложных реализациях и тому подобное. Если бы в матрице вместо 2 было бы 50, все происходило бы медленнее.

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

(2 x С0) 

(3 x С1) 

(1 x С2) 

(1 x C3)

Мы повторяем этот процесс, чтобы получить все остальные значения. 

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

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

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

 

8. Заключение

А сейчас, давайте еще раз проговорим весь алгоритм сначала: 

1. мы берем наш открытый текст, 
2. производим операцию XOR с помощью первой части нашего расширенного ключа, 
3. затем повторяем все шаги снова и снова. 

Мы подставим некоторые байты на место других, используя хорошо продуманный S-блок. Затем мы сдвинем элементы в строке и после этого смешаем элементы в столбцах. 

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

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

 

9. Post Scriptum

— Скажи, а этот алгоритм когда-нибудь дает сбои?

— В каком смысле? 

— Просто кажется, что в нем так много этапов и так много составляющих. 

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

Одна из главных особенностей AES как стандарта заключается в эффективности использования ЦП. Существуют расширенные инструкции AES по выполнению одного раунда, последнего раунда и т. д. для микропроцессоров Intel и других производителей. Эти процессоры невосприимчивы к такого рода атакам, и они невероятно быстрые. Если использовать AES на процессоре, который оптимизирован под такие задачи, с помощью правильных инструкций, то можно рассчитывать на шифрование со скоростью гигабит в секунду, что весьма быстро. Поэтому в BitLocker или в каком-нибудь шифровании диска вы даже глазом не успеете моргнуть. Вы кликнули файл, и процессор тут же расшифровал его и показал вам, прежде чем вы смогли осознать, что произошло. Это всё благодаря скорости процессов. 

Может быть, мы еще немного поговорим о полях Галуа, потому что, мне нравится, когда говорят… Прежде всего, пожалуйста, поищите Галуа, Эвариста Галуа в Википедии, потому что он очарователен. 

— Разве он не погиб на дуэли? 

Да, в 20 лет он погиб на дуэли. Он опубликовал три знаковые работы по конечным полям, многочленам и прочим вещам. Я не математик и не знаю всей истории. Но дело в том, что этот парень…

 

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

Полагаем, из этих объяснений стало понятно, что ни о каких разрядах там речь не идет, а речь исключительно о перемешивании битов в несколько раундов. 

Надеемся, было познавательно. 

 

Публикацию подготовили: 

Ирина Мирошникова (транскрибация), Светлана Дугинова (перевод), Евгений Бартов (выбор сюжета, вступление, редактура), Галина Таранова (оформление)