Главная
Блог разработчиков phpBB
 
+ 17 предустановленных модов
+ SEO-оптимизация форума
+ авторизация через соц. сети
+ защита от спама

AES-128. Детали и реализация на python

Anna | 15.06.2014 | нет комментариев

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

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

Немножко вступления

Advanced Encryption Standard является общеизвестным наименованием алгорифма Rijndael ([r91439b60b48d5dfee225ceec.jpg" alt="image"/>
Всякий байт из State дозволено представить как {xy} в шестнадцатеричной системе счисления. Тогда следует заменять его на элемент, стоящий на пересечении строки x и столбца y. Скажем, {6е} заменится на {9f}, а {15} на {59}.

ShiftRows()

Простая трансформация. Она исполняет циклический сдвиг налево на 1 элемент для первой строки, на 2 для 2-й и на 3 для третьей. Нулевая строка не сдвигается.

MixColumns()

В рамках этой трансформации всякая колонка в State представляется в виде многочлена и перемножается в поле GF(28) по модулю x4 1 с фиксированным многочленом 3x3 x2 x 2. Звучит как бы легко, но малопонятно, как это сделать. Картина становится проще, если посмотреть на равнозначную матричную запись, предоставленную в официальном документе эталона:

При умножении матриц, значение аij получается как сумма произведений соответствующих элементов i-ой строки первой матрицы и j-ого столбца 2-й, т. е.

Тут необходимо припомнить о неработоспособности обыкновенных правил сложения и умножения.
Новые правила:

  • Сложение в поле GF(28) равнозначно операции XOR
  • Умножение на {01} не меняет умножаемое
  • Умножение на {02} производится по правилу: если умножаемое значение поменьше {80}, оно сдвигается налево на 1 бит. Если же умножаемое значение огромнее либо равно {80}, оно вначале сдвигается налево на 1 бит, а после этого к итогу сдвига используется операция XOR со значением {1b}. Итог может перескочить за значение {ff}, то есть за границы одного байта. В этом случае необходимо воротить остаток от деления итога на {100}.
  • Умножение на другие константы дозволено выразить через предыдущие

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

AddRoundKey()

Трансформация изготавливает побитовый XOR всякого элемента из State с соответствующим элементом из RoundKey. RoundKey — массив такого же размера, как и State, тот, что строится для всякого раунда на основе тайного ключа функцией KeyExpansion(), которую и разглядим дальше.

KeyExpansion()

Эта вспомогательная трансформация формирует комплект раундовых ключей — KeySchedule. KeySchedule представляет собой длинную таблицу, состоящую из Nb*(Nr 1) столбцов либо (Nr 1) блоков, всякий из которых равен по размеру State. 1-й раундовый ключ заполняется на основе тайного ключа, тот, что вы придумаете, по формуле
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:

  • На всякой итерации трудимся с колонкой таблицы. Колонки 0,..,(Nk — 1) теснее заранее заполнены значениями из тайного слова. Начинаем с колонки поmk!code>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
    
    InvShiftRows()

    Трансформация изготавливает циклический сдвиг вправо на 1 элемент для первой строки State, на 2 для 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
    
    InvMixColumns()

    Операции те же, но всякая колонка State перемножается с иным многочленом {0b}x3 {0d}x2 {09}x {0e}. В матричной форме это выглядит так:

    Либо готовые формулы. Все значения, безусловно же, в шестнадцатеричной системе счисления.

    Тут необходимо сделать отхождение в сторону математики и пояснить как получить функции умножения на константы крупные, чем {02}. Как я теснее говорил, они получаются путем разложения их через {01} и {02}, а именно:

    Реформирования

    n*{03} = n*({02} {01}) = n*{02} n*{01}
    n*{09} = n*({08} {01}) = n*{02}*{02}*{02} n*{01}
    n*{0b} = n*({08} {02} {01}) = b*{02}*{02}*{02} n*{02} n*{01}
    n*{0d} = n*({08} {04} {01}) = n*{08} n*{04} n*{01} = n*{02}*{02}*{02} n*{02}*{02} n*{01}
    n*{0е} = n*({08} {04} {02} = n*{08} n*{04} n*{02} = n*{02}*{02}*{02} n*{02}*{02} b*{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
    
    AddRoundKey()

    Эта трансформация обратна сама себе в силу свойства операции 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(), а только на словах пояснил, что они где-то есть. Не сочтите, что я пиарюсь, но полный, склеенный совместно код дозволено взять в репозитории. Там же лежит скромный CLI интерфейс, тот, что разрешает легко указать путь до файла, ввести тайный ключ и получить зашифрованный файл в той же директории, что и начальный (расшифрованный файл дозволено получить таким же методом). Шифруйте на здоровье!

    И в конце нужно сказать об одном немаловажном нюансе — padding либо дополнение до блока. AES — алгорифм блочного шифрования, функции encrypt()/decrypt() берут на вход ровно один блок входных байтов (для нашего варианта с ключом в 128 бит это 16 байт). В конце файла могут остаться от 1 до 15 байт, которые не формируют цельный блок. Их дозволено легко, не шифруя, отдать на запись в финальный файл, но в некоторых случаях, в конце файла может содержаться что-то значимое, и такой вариант не подходит. 2-й вариант мне подсказала статья на Википедии про блочные шифры

    Примитивное дополнение нулевыми битами не решает задачи, так как получатель не сумеет обнаружить конец пригодных данных. К тому же, такой вариант приводит к атакам Оракула дополнения. Следственно на практике применимо решение, стандартизованное как «Способ дополнения 2» в ISO/IEC 9797-1, добавляющее единичный бит в конец сообщения и заполняющее оставшееся место нулями. В этом случае была подтверждена стойкость к сходственным атакам.

    Так я и сделал (правда 1-й вариант остался, легко закомментированный. Внезапно и сгодится).

    Подборка источников:
    Официальная документация
    Дюже наглядная визуальная истолковывание шифрующей части алгорифма. Да не засудит меня автор, сделал оттуда пару скриншотов.
    Никуда без Википедии
    Отдельная статья про MixColumns(). В ней есть таблицы с итогами умножения списка чисел 0…255 на константы, используемые в шифре, в поле GF(28)
    Комичный комикс про историю AES и сам алгорифм. Ничтожно, что обнаружил его только тогда, когда теснее писал статью.

Источник: programmingmaster.ru

Оставить комментарий
Форум phpBB, русская поддержка форума phpBB
Рейтинг@Mail.ru 2008 - 2017 © BB3x.ru - русская поддержка форума phpBB