Доброе GMT+n всем на борту. Давайте я не буду писать начало хакерских статей про то, как я сидел вечером и скучая пил апельсиновый сок, а тут вдруг бац и постучался ко мне друг, вследствии чего я решил написать статью subj вызывает много непонятных мыслей в головах начинающих хакеров и просто студентов, ну и вотъ. Автор по возможности старается избегать хакерского и прочих сленгов, в статье используется русский язык, так что некоторым возможно будет сложно её понять. Начинаем. Для начала короткий брифинг - AES, aka Rijndael, симметричный алгоритм блочного шифрования. (Блок - 128 бит, ключ - 128, 192, 256 бит). Изобретён... кому какая разница кем и в каком году Мы с вами рассмотрим только случай с 128 битным ключом. Для начала взгляд на AES с высоты птичьего полёта - О обозначениях - x - исходное сообщение, y - зашифрованное сообщение, x - ключ. Слеш-чёрточка - показывает сколько бит вошло/вышло. Из схемы понятно, что мы имеем 128 бит на входе, 128 бит ключа и 128 бит на выходе. Это общий взгляд на то, как оно всё работает. Теперь смотрим глубже. Для генерации y в случае использования 128 битного ключа алгоритм проходит в 10 кругов. (Порой автор применяет вероятно не общепринятые обозначения из русского языка, так как изучал сей предмет на английском языке, но сути это не меняет, если же меняет, то не стесняйтесь, оставляйте ваши комментарии.) Шифрование происходит в три этапа: 1. Подстановка. 2. Рассеивание. 3. Добавление ключа. Рассеивание состоит в свою очередь из 2х операций: 1. сдвиг рядов, 2. Смешивание столбцов (далее будет подробнее про ряды и столбцы) |||||||Теперь немного математики. Чуть-чуть Был такой математик, которого звали Галуа, родом он был из страны родины революций и круассанов, тобишь Франции. Сама его судьба очень интересна, но статья не об этом, поэтому кому интесно - википедируйте и обрящете. Так вот, он придумал такую штуку, как поля, которые были названы... сюрприз-сюрприз - поля Галуа . Ну если в кратце, то это такие поля на которых растёт картошка и кукуруза. Шутка-шутка. Вы не поверите, но можно сказать, что имеете дело с этими полями постоянно. Наверное не совсем корректный пример, но так вам быстрее станет понятно, что это такое. Например время. 90 минут это 1 час 30 минут. Т.е. 90 = 30 mod 60 Такие вот дела. Говоря проще, поля Галуа это некая ограниченная область чисел, внутри которых можно проводить арифметические операции. Пример 1. Возьмём поле GF (Galua Field)(5) - GF(5) = {0,1,2,3,4} Т.е. X mod5 Таблица ниже описывает сложение и умножение в таком поле. сложение умножение т.е. например 4mod5 * 3mod5 = 12mod5 == 2mod5 Думаю понятно. Для нас наиболее важно самое маленькое из таких полей, GF(2) Самые догадливые наверное уже думают про XOR. Да, да, так и есть сложение умножение Теперь все остальные тоже видят - сложение в таких полях эквивалентно операции XOR. Ну а умножение соответствует лог. операции AND. Сейчас наверное будет немного не понятно, но не пугайтесь, Чип и Дейл всегда спешат на помощь, всё будет рассказано и показано. В AES поле содержит 256 элементов и выглядит вот так GF(2^8) (Два в восьмой степени). Так было сделано, потому что таким образом каждый элемент этого поля может быть представлен как один байт. Вспоминаем из школьного курса информатики - 1 байт - 8 бит. Каждый элемент A в поле GF(2^8) может быть представлен в виде полинома (кажется по-русски это называется многочлен, но давайте дадим автору немного свободы Заметьте, что это будет 256 = 2^8 таких полиномов. ||||||||||||||||Сложение и вычитание в GF(2^n) На уровне добавления ключа в AES (вспомните начало статьи) используется сложение. Заметьте, что как мы ранее уже поняли, сложение и вычитание mod2 это одна и таже операция и эквивалентна XOR. Давайте на примере посмотрим на сложение в GF(2^8) которое используется в AES: C(x)=A(x)+B(x) Снова обратите внимание, что если бы считали не сумму, а разность, то результат был бы такой же. ||||||||||||||Умножение в GF(2^n) Умножение в таких полях очень важно для понимания того, как происходит смешивание столбцов. Кстати, если кому не ясно, что за многочлены мы тут используем и для чего, то поясню - во многих книгах я видел не очень понятные объяснения какого-то мудрёного умножения в двоичной системе, что весьма затрудняет понимание общей ситуации. Мы же с вами представляем это дело таким образом, что например байт 0000 0111 это на самом деле полином вида x^2+x+1. мм... Так начём я остановился - ах да, умножение: C(x)=A(x)*B(x)mod P(x) Что за P(x)? Это такой полином, по модулю которого скоращается результат умножения A и B. В спецификации AES это полином вида P(x) = x^8+x^4+x^3+x+1 Рассмотрим на примере: Нам требуется умножить A(x)= x^3+x^2+1 на B(x)=x^2+x в поле GF(x^4), как P(x) мы возьмём полином P(x) = x^4+x+1 Сначала мы просто перемножаем A и B так, как нас учили в школе, результат сохраняем в промежуточном C'(x). C'(x) = A(x)*B(x) = x^5+x^3+x^2+x Теперь сократим полином, опять же используя либо полученные знания в школе, либо схему Горнера, либо таким образом: x^4 = 1*P(x)+(x+1) x^4 = x+1 mod P(x) x^5 = x^2+x mod P(x) (кто не понял: x*(x+1) = x^2+x ) Теперь осталось только подставить результат для x^5 в наш полином: C(x) = x^5+x^3+x^2+x mod P(x) C(x) = (x^2+x)+(x^3+x^2+x) = x^3 A(x)*B(x) = x^3 Что на битовом уровне соотвествует: 1101 * 0110 = 1000 Теперь о инверсии, она нам потребуется для понимания того, как происходит подстановка. A^(-1) * A(x) = 1 mod P(x) Т.е. это такой полином, умножение А на который даст нам 1. Думаю не стоит излишне заострять на этом внимания вникая в математическую составляющую этого процесса, для начала будет достаточно таблицы: Пример: например нам нужно узнать инверсмию для x^7+x^6+x, что в двоичной будет 11000010, или в hex - C2. Смотрим в таблице строку C, столбец 2: 0x2F = 00101111 bin, = x^5 + x^3 + x^2 + x + 1 Проверям: (x^7+x^6+x)*(x^5+x^3+x^2+x+1) = 1 mod P(x) Так, с математикой закончили. Внутренняя структура. Итак, 16 байт (128 бит) данных A от 0 до 15 попадают в S-Box. Что это такое, спросит читатель со смайликом оО... Это сокращение от Substitution-box, что в переводе на великий и могучий значит коробку подстановок (конечно тут может быть много вариантов перевода, не стоит сразу набрасываться) Вообщем это ящик, в котором происходят подстановки. Всего их, этих ящиков 16, по количеству байтов. Представте, как 16 байтов, на которые разбивается блок входящих данных, проходят через эти коробки и образуют 16 байтовые B. Т.е. 16 байт, 16 байт выход. Потом происходят операции сдвига рядов и смешивания столбцов, после чего раундовый ключ ксорится с тем что получилось. Теперь подробнее Для начала представим блок входящих данных в виде матрицы 4х4, в которой каждый элемент А соотвествует байту. .Уровень подстановок. Этот уровень можно представить как 16 одинаковых, расположенных параллельно S-box'ов, каждый с 8-ю байтами на входе и выходе. На этом уровне каждый из полиномов А заменяется на полином B, (прикруте к форуму Latex уже! ) Т.е., если представить S-box как некую функцию S, то мы имеет что-то вроде такого: S(A)= B. При программной реализации AES S-box как правило реализуют в виде таблицы: Code: unsigned long int SBOX[256] = { 0x63, 0x7C, 0x77, 0x7B, 0xF2, 0x6B, 0x6F, 0xC5, 0x30, 0x01, 0x67, 0x2B, 0xFE, 0xD7, 0xAB, 0x76, 0xCA, 0x82, 0xC9, 0x7D, 0xFA, 0x59, 0x47, 0xF0, 0xAD, 0xD4, 0xA2, 0xAF, 0x9C, 0xA4, 0x72, 0xC0, 0xB7, 0xFD, 0x93, 0x26, 0x36, 0x3F, 0xF7, 0xCC, 0x34, 0xA5, 0xE5, 0xF1, 0x71, 0xD8, 0x31, 0x15, 0x04, 0xC7, 0x23, 0xC3, 0x18, 0x96, 0x05, 0x9A, 0x07, 0x12, 0x80, 0xE2, 0xEB, 0x27, 0xB2, 0x75, 0x09, 0x83, 0x2C, 0x1A, 0x1B, 0x6E, 0x5A, 0xA0, 0x52, 0x3B, 0xD6, 0xB3, 0x29, 0xE3, 0x2F, 0x84, 0x53, 0xD1, 0x00, 0xED, 0x20, 0xFC, 0xB1, 0x5B, 0x6A, 0xCB, 0xBE, 0x39, 0x4A, 0x4C, 0x58, 0xCF, 0xD0, 0xEF, 0xAA, 0xFB, 0x43, 0x4D, 0x33, 0x85, 0x45, 0xF9, 0x02, 0x7F, 0x50, 0x3C, 0x9F, 0xA8, 0x51, 0xA3, 0x40, 0x8F, 0x92, 0x9D, 0x38, 0xF5, 0xBC, 0xB6, 0xDA, 0x21, 0x10, 0xFF, 0xF3, 0xD2, 0xCD, 0x0C, 0x13, 0xEC, 0x5F, 0x97, 0x44, 0x17, 0xC4, 0xA7, 0x7E, 0x3D, 0x64, 0x5D, 0x19, 0x73, 0x60, 0x81, 0x4F, 0xDC, 0x22, 0x2A, 0x90, 0x88, 0x46, 0xEE, 0xB8, 0x14, 0xDE, 0x5E, 0x0B, 0xDB, 0xE0, 0x32, 0x3A, 0x0A, 0x49, 0x06, 0x24, 0x5C, 0xC2, 0xD3, 0xAC, 0x62, 0x91, 0x95, 0xE4, 0x79, 0xE7, 0xC8, 0x37, 0x6D, 0x8D, 0xD5, 0x4E, 0xA9, 0x6C, 0x56, 0xF4, 0xEA, 0x65, 0x7A, 0xAE, 0x08, 0xBA, 0x78, 0x25, 0x2E, 0x1C, 0xA6, 0xB4, 0xC6, 0xE8, 0xDD, 0x74, 0x1F, 0x4B, 0xBD, 0x8B, 0x8A, 0x70, 0x3E, 0xB5, 0x66, 0x48, 0x03, 0xF6, 0x0E, 0x61, 0x35, 0x57, 0xB9, 0x86, 0xC1, 0x1D, 0x9E, 0xE1, 0xF8, 0x98, 0x11, 0x69, 0xD9, 0x8E, 0x94, 0x9B, 0x1E, 0x87, 0xE9, 0xCE, 0x55, 0x28, 0xDF, 0x8C, 0xA1, 0x89, 0x0D, 0xBF, 0xE6, 0x42, 0x68, 0x41, 0x99, 0x2D, 0x0F, 0xB0, 0x54, 0xBB, 0x16 }; Представте, что в массиве выше слева x, сверху y, тогда S(A=C2)=25. На битовом уровне это выглядит как S(11000010) = (00100101) .Растворение. Этот уровень, как упоминалось выше состоит из двух подуровней. Сначала происходит сдвиг рядов. Нулевой ряд сверху не сдвигается, 1вый сдвигается влево на один бит, второй на два, третий на три. Здесь всё просто. Следующий уровень немного сложнее: Для начала представим как ф-цию, MixColumns(B) = C B здесь то, что получилось после сдвига рядов. Теперь каждый из столбцов B нужно представить как вектор, который будет умножен на фиксированную матрицу. 01 - 00000001, 02 - 00000010, 03 - 00000011, что сооветствует в случае 3 - x+1 Точно таким же макаром считаются все следующие C. Рассмотрим далее на примере, У нас есть B (25,25,...,25) В таком случае нам нужно 02*25, 03*25 02*25 = x(x^5+x^2+1) = x^6+x^3+x 03*25 = (x+1)*(x^5+x^2+1) = (x^6+x^3+x)+(x^5+x^2+1) = x^6+x^5+x^3+x^2+x+1 Так как степень полинома не выше 8ми, то сокращать по модулю ничего не нужно (Умножение матрицы на вектор, элементы ксорятся) .Добавление ключа. На этом уровне подключ XORится с C. Сейчас рассмотрим как вычисляется подключ. Количество подключей считается по принципу количество раундов + 1, в нашем случае - 11, каждый по 128 бит. 11 ключей хранятся в массиве от W[0] до W[43], получаются они след. образом: Первый подключ k0 это наш настоящий ключ, этот ключ разбивается на слова по 2 байта и заполняет первые 4 элемента массива W. Следующие эдементы массива получаются так: каждый ключ это 4 слова из массива W[...] и считается по формуле W[4i] = W[4(i-1)]+g(W[4i-1]) где i от 1 до 10, а g() нелинейная ф-ция с 4мя байтами вход/выход... Примерно вот как-то так, дополнения приветствуются
