- PVSM.RU - https://www.pvsm.ru -
Идея написать для себя что-то шифрующее родилась довольно тривиально — пришлось завести еще одну дебетовую карту и, следовательно, хранить в голове еще один пин-код. Хранить такую информацию в открытом виде паранойя не позволяет, использовать сторонние сервисы тоже, поэтому после некоторых поисков остановился на стандарте AES. Сразу захотелось разобраться и реализовать алгоритм самому, не прибегая к дополнительным модулям.
В статье я расскажу подробно о составляющих алгоритма, немного окунемся в мат часть и приведу пример реализации на python. В разработке я ограничивался только тем, что входит в состав стандартной библиотеки.
Advanced Encryption Standard является общеизвестным названием алгоритма Rijndael ([rɛindaːl]), который был разработан двумя бельгийскими криптографами Йоаном Дайменом и Винсентом Рэйменом. Алгоритм является блочным и симметричным. Принят в качестве стандарта шифрования данных для гос учреждений в США. Нашумевшее в последнее время Агенство Национальной Безопасности использует его для хранения документов: вплоть до уровня SECRET применяется шифрование с ключом длиной в 128 бит, информация TOP SECRET требует ключа в 192 или 256 бит. В дополнение к высокой криптостойкости алгоритм базируется на не самой сложной математике.
Для работы нам необходим набор байтов в качестве объекта шифрования и секретный ключ, который потребуется при расшифровке. Длинные ключи хранить в голове неудобно, да и считается, что длины ключа в 128 бит, с лихвой хватает для неприступности, поэтому на варианты 192/256 я не смотрел. К тому же, как сказано здесь [1], при некоторых условиях более длинный ключ может отставать в устойчивости.
Введем некоторые обозначения:
Алгоритм имеет четыре трансформациями, каждая из которых своим образом влияет на состояние State и в конечном итоге приводит к результату: SubBytes(), ShiftRows(), MixColumns() и AddRoundKey(). Общую схему шифрования можно представить как:
В начале заполняется массив State входными значениями по формуле State[r][c] = input[r + 4c], r = 0,1...4; c = 0,1..Nb. То есть по колонкам. За раз шифруется блок размером 16 байт.
Алгоритм оперирует байтами, считая их элементами конечного поля или поля Галуа [2] GF(28). Число в скобках — это количество элементов поля или его мощность. Элементами поля GF(28) являются многочлены степени не более 7, которые могут быть заданы строкой своих коэффициентов. Байт очень легко представить в виде многочлена. Например, байту {1,1,1,0,0,0,1,1} соответствует элемент поля 1x7 + 1x6 + 1x5 + 0x4 + 0x3 + 0x2 + 1x1 + 1x0 = 1x7 + 1x6 + 1x5 + x +1. То, что мы работаем с элементами поля, очень важно потому, что это меняет правила операций сложения и умножения. Этого мы коснемся немного позже.
Далее рассмотрим подробно каждую из трансформаций.
Преобразование представляет собой замену каждого байта из State на соответствующий ему из константной таблицы Sbox. Значения элементов Sbox представлены в шестнадцатеричной системе счисления. Сама же таблица получена посредством преобразований уже известного нам поля GF(28)
Каждый байт из State можно представить как {xy} в шестнадцатеричной системе счисления. Тогда следует заменять его на элемент, стоящий на пересечении строки x и столбца y. Например, {6е} заменится на {9f}, а {15} на {59}.
Простая трансформация. Она выполняет циклический сдвиг влево на 1 элемент для первой строки, на 2 для второй и на 3 для третьей. Нулевая строка не сдвигается.
В рамках этой трансформации каждая колонка в State представляется в виде многочлена и перемножается в поле GF(28) по модулю x4 + 1 с фиксированным многочленом 3x3 + x2 + x + 2. Звучит вроде просто, но малопонятно, как это сделать. Картина становится проще, если посмотреть на эквивалентную матричную запись, предоставленную в официальном документе стандарта:
При умножении матриц, значение аij получается как сумма произведений соответствующих элементов i-ой строки первой матрицы и j-ого столбца второй, т. е.
Здесь нужно вспомнить о неработоспособности обычных правил сложения и умножения.
Новые правила:
Естественно, это не общие правила арифметики в конечном поле, но в рамках алгоритма придется умножать на три константы при шифровании и на четыре при дешифровке, так что таких локальных лайфхаков вполне хватит.
MixColumns() вместе с ShiftRows() добавляют диффузию в шифр.
Трансформация производит побитовый XOR каждого элемента из State с соответствующим элементом из RoundKey. RoundKey — массив такого же размера, как и State, который строится для каждого раунда на основе секретного ключа функцией KeyExpansion(), которую и рассмотрим далее.
Эта вспомогательная трансформация формирует набор раундовых ключей — KeySchedule. KeySchedule представляет собой длинную таблицу, состоящую из Nb*(Nr + 1) столбцов или (Nr + 1) блоков, каждый из которых равен по размеру State. Первый раундовый ключ заполняется на основе секретного ключа, который вы придумаете, по формуле
KeySchedule[r][c] = SecretKey[r + 4c], r = 0,1...4; c = 0,1..Nk.
Понятно, что в KeySchedule мы должны заносить байты, чтобы были возможны дальнейшие операции. Если использовать этот алгоритм для домашнего шифрования, то хранить в голове последовательность чисел совсем не уютно, так что в нашей реализации KeyExpansion() будет на вход брать plaintext строку и применяя ord()
для каждого из символов, записывать результат в ячейки KeySchedule. Отсюда вытекают ограничения: не более 16 символов длиной и, так как мы работаем с байтами, ord()
символа не должен возвращать значения большие чем 255 или 11111111 в двоичной, иначе получим на выходе неверное шифрование. Получается, что с помощью ключа на русском языке зашифровать не получится.
На рисунке изображен макет KeySchedule для AES-128: 11 блоков по 4 колонки. Для других вариаций алгоритма будет соответственно (Nr + 1) блоков по Nb колонок. Теперь нам предстоит заполнить пустые места. Для преобразований опять определена константная таблица — Rcon — значения которой в шестнадцатеричной системе счисления.
Алгоритм дозаполнения KeySchedule:
Эта вспомогательная трансформация является самой объемной по написанию и, наверное, самой сложной, после осознания математики в MixColumns(), в алгоритме. Шифроключ обязан состоять из 4*Nk элементов (в нашем случае 16). Но так как мы делаем все это для домашнего применения, то вполне вероятно, что придумывать ключ в 16 символов и запоминать его не каждый будет. Поэтому, если на вход поступила строка длиной менее 16, я в KeySchedule дозаношу значения {01} до нормы.
def key_expansion(key):
key_symbols = [ord(symbol) for symbol in key]
# ChipherKey shoul contain 16 symbols to fill 4*Nk table. If it's less
# complement the key with "0x01"
if len(key_symbols) < 4*nk:
for i in range(4*nk - len(key_symbols)):
key_symbols.append(0x01)
# make ChipherKey(which is base of KeySchedule)
key_schedule = [[] for i in range(4)]
for r in range(4):
for c in range(nk):
key_schedule[r].append(key_symbols[r + 4*c])
# Comtinue to fill KeySchedule
for col in range(nk, nb*(nr + 1)): # col - column number
if col % nk == 0:
# take shifted (col - 1)th column...
tmp = [key_schedule[row][col-1] for row in range(1, 4)]
tmp.append(key_schedule[0][col-1])
# change its elements using Sbox-table like in SubBytes...
for j in range(len(tmp)):
sbox_row = tmp[j] // 0x10
sbox_col = tmp[j] % 0x10
sbox_elem = sbox[16*sbox_row + sbox_col]
tmp[j] = sbox_elem
# and finally make XOR of 3 columns
for row in range(4):
s = key_schedule[row][col - 4]^tmp[row]^rcon[row][col/nk - 1]
key_schedule[row].append(s)
else:
# just make XOR of 2 columns
for row in range(4):
s = key_schedule[row][col - 4]^key_schedule[row][col - 1]
key_schedule[row].append(s)
return key_schedule
Как было сказано ранее, KeySchedule используется в трансформации AddRoundKey(). В раунде инициализации раундовым ключом будут колонки с номерами 0,..,3, в первом — с номерами 4,..,7 и тд. Вся суть AddRoundKey() — произвести XOR State и раундового ключа.
Это, собственно, все, что касается процесса шифрования. Выходной массив зашифрованных байтов составляется из State по формуле output[r + 4c] = State[r][c], r = 0,1...4; c = 0,1..Nb. А тем временем статья затягивается, так что мы сейчас быстро пробежимся по процедуре дешифровки.
Идея здесь проста: если с тем же ключевым словом выполнить последовательность трансформаций, инверсных трансформациям шифрования, то получится исходное сообщение. Такими инверсными трансформациями являются InvSubBytes(), InvShiftRows(), InvMixColumns() и AddRoundKey(). Общая схема алгоритма расшифровки:
Стоит отметить, что последовательность добавления раундовых ключей в AddRoundKey() должна быть обратной: от Nr + 1 до 0. Изначально, как и при шифровании, из массива входных байтов формируется таблица State. Затем над ней в каждом раунде производятся преобразования, в конце которых должно получиться расшифрованный файл. Порядок трансформаций немного изменился. Что будет первым, InvSubBytes() или InvShiftRows(), на самом деле не важно, потому что одна из них работает со значениями байтов, а вторая переставляет байты, этих самых значений не меняя, но я придерживался последовательности преобразований в псевдокоде стандарта.
Работает точно так же, как и SubBytes(), за исключением того, что замены делаются из константной таблицы InvSbox.
Оставшиеся обратные трансформации тоже будут очень похожи на свои прямые аналоги, поэтому в коде не выделяем под них отдельных функций. Каждая функция, описывающая трансформацию, будет иметь входную переменную inv
. Если она равна False
, то функция будет работать в обычном или прямом режиме(шифрование), если True
— в инверсном(дешифровка).
def sub_bytes(state, inv=False):
if inv == False: # encrypt
box = sbox
else: # decrypt
box = inv_sbox
for i in range(len(state)):
for j in range(len(state[i])):
row = state[i][j] // 0x10
col = state[i][j] % 0x10
# Our Sbox is a flat array, not a bable. So, we use this trich to find elem:
box_elem = box[16*row + col]
state[i][j] = box_elem
return state
Трансформация производит циклический сдвиг вправо на 1 элемент для первой строки State, на 2 для второй и на 3 для третьей. Нулевая строка не поворачивается.
Пояснения к коду: left_shift/right_shift(array, count)
поворачивают входной array
в соответствующую сторону count
раз
def shift_rows(state, inv=False):
count = 1
if inv == False: # encrypting
for i in range(1, nb):
state[i] = left_shift(state[i], count)
count += 1
else: # decryption
for i in range(1, nb):
state[i] = right_shift(state[i], count)
count += 1
return state
Операции те же, но каждая колонка State перемножается с другим многочленом {0b}x3 + {0d}x2 + {09}x + {0e}. В матричной форме это выглядит так:
Или готовые формулы. Все значения, конечно же, в шестнадцатеричной системе счисления.
Здесь нужно сделать отступление в сторону математики и пояснить как получить функции умножения на константы большие, чем {02}. Как я уже говорил, они получаются путем разложения их через {01} и {02}, а именно:
Разумеется, можно разложить числа и по-другому, но лично проверено, что разложение
n * {09} = n * {03} + n * {03} + n * {03}
и вызов соответствующих функций будут давать неверный результат (эталонные таблицы с результатами есть в одной из ссылок в списке источников).
Пояснения к коду: функции mul_by_<константа>
выполняют умножение на соответствующую константу в GF(28) по правилам, что описывались выше.
def mix_columns(state, inv=False):
for i in range(nb):
if inv == False: # encryption
s0 = mul_by_02(state[0][i])^mul_by_03(state[1][i])^state[2][i]^state[3][i]
s1 = state[0][i]^mul_by_02(state[1][i])^mul_by_03(state[2][i])^state[3][i]
s2 = state[0][i]^state[1][i]^mul_by_02(state[2][i])^mul_by_03(state[3][i])
s3 = mul_by_03(state[0][i])^state[1][i]^state[2][i]^mul_by_02(state[3][i])
else: # decryption
s0 = mul_by_0e(state[0][i])^mul_by_0b(state[1][i])^mul_by_0d(state[2][i])^mul_by_09(state[3][i])
s1 = mul_by_09(state[0][i])^mul_by_0e(state[1][i])^mul_by_0b(state[2][i])^mul_by_0d(state[3][i])
s2 = mul_by_0d(state[0][i])^mul_by_09(state[1][i])^mul_by_0e(state[2][i])^mul_by_0b(state[3][i])
s3 = mul_by_0b(state[0][i])^mul_by_0d(state[1][i])^mul_by_09(state[2][i])^mul_by_0e(state[3][i])
state[0][i] = s0
state[1][i] = s1
state[2][i] = s2
state[3][i] = s3
return state
Эта трансформация обратна сама себе в силу свойства операции XOR:
(a XOR b) XOR b = a
Поэтому никаких изменений в нее вносить не нужно. Набор раундовых ключей формируется таким же образом, как и для шифрования с помощью функции KeyExpansion(), но раундовые ключи необходимо подставлять в обратном порядке.
def add_round_key(state, key_schedule, round=0):
for col in range(nk):
# nb*round is a shift which indicates start of a part of the KeySchedule
s0 = state[0][col]^key_schedule[0][nb*round + col]
s1 = state[1][col]^key_schedule[1][nb*round + col]
s2 = state[2][col]^key_schedule[2][nb*round + col]
s3 = state[3][col]^key_schedule[3][nb*round + col]
state[0][col] = s0
state[1][col] = s1
state[2][col] = s2
state[3][col] = s3
return state
Теперь мы обладаем исчерпывающим набором вспомогательных функций-трансформаций, чтобы написать
def encrypt(input_bytes, key):
# let's prepare our input data: State array and KeySchedule
state = [[] for j in range(4)]
for r in range(4):
for c in range(nb):
state[r].append(input_bytes[r + 4*c])
key_schedule = key_expansion(key)
state = add_round_key(state, key_schedule)
for rnd in range(1, nr):
state = sub_bytes(state)
state = shift_rows(state)
state = mix_columns(state)
state = add_round_key(state, key_schedule, rnd)
state = sub_bytes(state)
state = shift_rows(state)
state = add_round_key(state, key_schedule, rnd + 1)
output = [None for i in range(4*nb)]
for r in range(4):
for c in range(nb):
output[r + 4*c] = state[r][c]
return output
def decrypt(cipher, key):
# let's prepare our algorithm enter data: State array and KeySchedule
state = [[] for i in range(nb)]
for r in range(4):
for c in range(nb):
state[r].append(cipher[r + 4*c])
key_schedule = key_expansion(key)
state = add_round_key(state, key_schedule, nr)
rnd = nr - 1
while rnd >= 1:
state = shift_rows(state, inv=True)
state = sub_bytes(state, inv=True)
state = add_round_key(state, key_schedule, rnd)
state = mix_columns(state, inv=True)
rnd -= 1
state = shift_rows(state, inv=True)
state = sub_bytes(state, inv=True)
state = add_round_key(state, key_schedule, rnd)
output = [None for i in range(4*nb)]
for r in range(4):
for c in range(nb):
output[r + 4*c] = state[r][c]
return output
Эти две функции на вход берут список байтов, не шифрованных или шифрованных, и plaintext строку с секретным ключевым словом.
Статья получилась довольно длинной. Я старался разбавлять текст картинками и, надеюсь, вам было интересно и никто не заскучал. Код, представленный в статье, не совсем исчерпывающий. Я не вставлял глобальное объявление константных таблиц, мелких функций для MixColumns(), а только на словах пояснил, что они где-то есть. Не сочтите, что я пиарюсь, но полный, склеенный вместе код можно взять в репозитории [3]. Там же лежит скромный CLI интерфейс, который позволяет просто указать путь до файла, ввести секретный ключ и получить зашифрованный файл в той же директории, что и исходный (расшифрованный файл можно получить таким же способом). Шифруйте на здоровье!
И в конце необходимо сказать об одном немаловажном нюансе — padding или дополнение до блока. AES — алгоритм блочного шифрования, функции encrypt()/decrypt()
берут на вход ровно один блок входных байтов (для нашего варианта с ключом в 128 бит это 16 байт). В конце файла могут остаться от 1 до 15 байт, которые не формируют цельный блок. Их можно просто, не шифруя, отдать на запись в конечный файл, но в некоторых случаях, в конце файла может содержаться что-то важное, и такой вариант не подходит. Второй вариант мне подсказала статья [4] на Википедии про блочные шифры
Простое дополнение нулевыми битами не решает проблемы, так как получатель не сможет найти конец полезных данных. К тому же, такой вариант приводит к атакам Оракула дополнения. Поэтому на практике применимо решение, стандартизованное как «Метод дополнения 2» в ISO/IEC 9797-1, добавляющее единичный бит в конец сообщения и заполняющее оставшееся место нулями. В этом случае была доказана стойкость к подобным атакам.
Так я и сделал (хотя первый вариант остался, просто закомментированный. Вдруг и пригодится).
Подборка источников:
Официальная документация [5]
Очень наглядная визуальная интерпретация шифрующей части алгоритма [6]. Да не засудит меня автор, сделал оттуда пару скриншотов.
Никуда без Википедии [7]
Отдельная статья про MixColumns() [8]. В ней есть таблицы с результатами умножения списка чисел 0...255 на константы, используемые в шифре, в поле GF(28)
Забавный комикс про историю AES и сам алгоритм [9]. Жалко, что нашел его только тогда, когда уже писал статью.
Автор: Skycker
Источник [10]
Сайт-источник PVSM.RU: https://www.pvsm.ru
Путь до страницы источника: https://www.pvsm.ru/python/54773
Ссылки в тексте:
[1] здесь: http://habrahabr.ru/post/68328/
[2] Галуа: http://ru.wikipedia.org/wiki/%D0%9F%D0%BE%D0%BB%D0%B5_%D0%93%D0%B0%D0%BB%D1%83%D0%B0
[3] репозитории: https://github.com/Skycker/AES
[4] статья: http://ru.wikipedia.org/wiki/%D0%91%D0%BB%D0%BE%D1%87%D0%BD%D1%8B%D0%B9_%D1%88%D0%B8%D1%84%D1%80#.D0.94.D0.BE.D0.BF.D0.BE.D0.BB.D0.BD.D0.B5.D0.BD.D0.B8.D0.B5_.D0.B4.D0.BE_.D1.86.D0.B5.D0.BB.D0.BE.D0.B3.D0.BE_.D0.B1.D0.BB.D0.BE.D0.BA.D0.B0
[5] Официальная документация: http://csrc.nist.gov/publications/fips/fips197/fips-197.pdf
[6] Очень наглядная визуальная интерпретация шифрующей части алгоритма: http://www.cs.bc.edu/~straubin/cs381-05/blockciphers/rijndael_ingles2004.swf
[7] Никуда без Википедии: http://ru.wikipedia.org/wiki/Advanced_Encryption_Standard
[8] Отдельная статья про MixColumns(): http://en.wikipedia.org/wiki/Rijndael_mix_columns
[9] Забавный комикс про историю AES и сам алгоритм: http://www.moserware.com/2009/09/stick-figure-guide-to-advanced.html
[10] Источник: http://habrahabr.ru/post/212235/
Нажмите здесь для печати.