Python/Django разработчик
0,0
рейтинг
11 февраля 2014 в 19:30

Разработка → AES-128. Детали и реализация на python из песочницы

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

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

Немного введения


Advanced Encryption Standard является общеизвестным названием алгоритма Rijndael ([rɛindaːl]), который был разработан двумя бельгийскими криптографами Йоаном Дайменом и Винсентом Рэйменом. Алгоритм является блочным и симметричным. Принят в качестве стандарта шифрования данных для гос учреждений в США. Нашумевшее в последнее время Агенство Национальной Безопасности использует его для хранения документов: вплоть до уровня SECRET применяется шифрование с ключом длиной в 128 бит, информация TOP SECRET требует ключа в 192 или 256 бит. В дополнение к высокой криптостойкости алгоритм базируется на не самой сложной математике.

Много шифрования


Для работы нам необходим набор байтов в качестве объекта шифрования и секретный ключ, который потребуется при расшифровке. Длинные ключи хранить в голове неудобно, да и считается, что длины ключа в 128 бит, с лихвой хватает для неприступности, поэтому на варианты 192/256 я не смотрел. К тому же, как сказано здесь, при некоторых условиях более длинный ключ может отставать в устойчивости.

Введем некоторые обозначения:
  • State — промежуточный результат шифрования, который может быть представлен как прямоугольный массив байтов имеющий 4 строки и Nb колонок. Каждая ячейка State содержит значение размером в 1 байт
  • Nb — число столбцов (32-х битных слов), составляющих State. Для стандарта регламентировано Nb = 4
  • Nk — длина ключа в 32-х битных словах. Для AES, Nk = 4, 6, 8. Мы уже определились, что будем использовать Nk = 4
  • Nr — количество раундов шифрования. В зависимости от длины ключа, Nr = 10, 12 или 14

Алгоритм имеет четыре трансформации, каждая из которых своим образом влияет на состояние State и в конечном итоге приводит к результату: SubBytes(), ShiftRows(), MixColumns() и AddRoundKey(). Общую схему шифрования можно представить как:
image
В начале заполняется массив State входными значениями по формуле State[r][c] = input[r + 4c], r = 0,1...4; c = 0,1..Nb. То есть по колонкам. За раз шифруется блок размером 16 байт.
image

Алгоритм оперирует байтами, считая их элементами конечного поля или поля Галуа 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. То, что мы работаем с элементами поля, очень важно потому, что это меняет правила операций сложения и умножения. Этого мы коснемся немного позже.

Далее рассмотрим подробно каждую из трансформаций.

SybButes()

Преобразование представляет собой замену каждого байта из State на соответствующий ему из константной таблицы Sbox. Значения элементов Sbox представлены в шестнадцатеричной системе счисления. Сама же таблица получена посредством преобразований уже известного нам поля GF(28)
image
Каждый байт из State можно представить как {xy} в шестнадцатеричной системе счисления. Тогда следует заменять его на элемент, стоящий на пересечении строки x и столбца y. Например, {6е} заменится на {9f}, а {15} на {59}.

ShiftRows()

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


MixColumns()

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

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

Здесь нужно вспомнить о неработоспособности обычных правил сложения и умножения.
Новые правила:
  • Сложение в поле 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. Первый раундовый ключ заполняется на основе секретного ключа, который вы придумаете, по формуле
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) уже предварительно заполнены значениями из секретного слова. Начинаем с колонки под номером Nk (в нашем случае с четвертой)
  • Если номер Wi колонки кратен Nk (в нашем случае каждая четвертая), то берем колонку Wi-1, выполняем над ней циклический сдвиг влево на один элемент, затем все байты колонки заменяем соответствующими из таблицы Sbox, как делали это в SubBytes(). Далее выполняем операцию XOR между колонкой Wi-Nk, измененной Wi-1 и колонкой Rconi/Nk-1. Результат записывается в колонку Wi. Чтобы было немного понагляднее, иллюстрация для i = 4.
  • Для остальных колонок выполняем XOR между Wi-Nk и Wi-1. Результат записываем в Wi

Эта вспомогательная трансформация является самой объемной по написанию и, наверное, самой сложной, после осознания математики в MixColumns(), в алгоритме. Шифроключ обязан состоять из 4*Nk элементов (в нашем случае 16). Но так как мы делаем все это для домашнего применения, то вполне вероятно, что придумывать ключ в 16 символов и запоминать его не каждый будет. Поэтому, если на вход поступила строка длиной менее 16, я в KeySchedule дозаношу значения {01} до нормы.
Код KeyExpansion()
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(), на самом деле не важно, потому что одна из них работает со значениями байтов, а вторая переставляет байты, этих самых значений не меняя, но я придерживался последовательности преобразований в псевдокоде стандарта.

InvSubBytes()

Работает точно так же, как и 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


InvShiftRows()

Трансформация производит циклический сдвиг вправо на 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


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}
и вызов соответствующих функций будут давать неверный результат (эталонные таблицы с результатами есть в одной из ссылок в списке источников). Специально оставил альтернативные (закомменченные) варианты вычислений, ибо они понятнее, изящнее, но почему-то работают неправильно.
Вспомогательные функции умножения
def mul_by_02(num):
   
    if num < 0x80:
        res =  (num << 1)
    else:
        res =  (num << 1)^0x1b

    return res % 0x100

def mul_by_03(num):
    return mul_by_02(num)^num

def mul_by_09(num):
    #return mul_by_03(num)^mul_by_03(num)^mul_by_03(num) - works wrong, I don't know why
    return mul_by_02(mul_by_02(mul_by_02(num)))^num
 
def mul_by_0b(num):
    #return mul_by_09(num)^mul_by_02(num)
    return mul_by_02(mul_by_02(mul_by_02(num)))^mul_by_02(num)^num

def mul_by_0d(num):
    #return mul_by_0b(num)^mul_by_02(num)
    return mul_by_02(mul_by_02(mul_by_02(num)))^mul_by_02(mul_by_02(num))^num

def mul_by_0e(num):
    #return mul_by_0d(num)^num
    return mul_by_02(mul_by_02(mul_by_02(num)))^mul_by_02(mul_by_02(num))^mul_by_02(num)

Пояснения к коду: функции mul_by_<константа> выполняют умножение на соответствующую константу в GF(28) по правилам, что описывались в разделе про MixColumns().
Код
 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» в ISO/IEC 9797-1, добавляющее единичный бит в конец сообщения и заполняющее оставшееся место нулями. В этом случае была доказана стойкость к подобным атакам.

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

Подборка источников:
Кирилл Костюхин @Skycker
карма
8,0
рейтинг 0,0
Python/Django разработчик
Реклама помогает поддерживать и развивать наши сервисы

Подробнее
Реклама

Самое читаемое Разработка

Комментарии (21)

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

    Сразу захотелось разобраться и реализовать алгоритм самому, не прибегая к дополнительным модулям.
    Надеюсь, это только в образовательных целях? Обычно самодельные реализации криптоалгоритмов для практического применения не очень рекомендуется :)
    • +4
      Нашел это по одной из ссылок из статьи :)
      • 0
        Хах, отличное :)
    • 0
      Ну, внедрять это куда-то я и не планировал. Зато радость, когда все корректно заработало, была себе доставлена) ибо мат часть заработала не сразу. И конечно же самообразование, без него никуда)
      • 0
        Все правильно сделали :)
      • +3
        Посмотрите на www.matasano.com/articles/crypto-challenges/, там дают задания, постепенно выполняя которые вы научитесь реализовывать различные алгоритмы, и их же ломать. Задания не особо сложные, там есть небольшие подсказки, время выполнения/язык не ограничен. Если для самообразования — самое то.
        • 0
          Спасибо, интересный проект) Очень порадовала фраза
          We probably won't run your code (we'll definitely read it though). You can ask us for help; we'll try our best.

  • НЛО прилетело и опубликовало эту надпись здесь
    • 0
      Когда делал этот курс — невнимательно прочитал дополнительную задачу второй недели. В итоге, медленно вкуривая документации и стандарты, реализовал AES enc/dec для этой домашней работы на Ruby. Какой же кайф был, когда всё и правда заработало!
      • НЛО прилетело и опубликовало эту надпись здесь
        • +1
          В том то и соль:
          невнимательно прочитал дополнительную задачу второй недели


          А потом на этой реализации допилил уже и CBC, CTR.

          Курс очень интересный, рекомендую всем.
  • 0
    В общем, пакуем все это дело наглухо в пластик, остекловываем и закапываем на глубине 20метров
    © DiHalt
  • +1
    Тож в свое время реализовывал AES128: ваял драйвер hdd диска под винду с шифрованием. Но тоже дальше образовательных целей не пошло.
    Вообще, делать что-то этакое, как по мне, — хорошая разминка для мозга :)
  • +4
    Не увидел кода для умножения полиномов, хотя это самое интересное в реализации данного примитива шифрования. Сам еще год назад реализовывал AES на C# для лабораторной, а потом переписывал на С и на Python для курсеровской криптографии (естественно, ECB, тогда еще была только первая или вторая неделя). Сначала использовал gmul отсюда, потом вообще перешел на precomputed tables, как это сделано в OpenSSL.
    Да, это хорошая разминка для мозга, но можно довести это и дальше, до authenticated encryption. Или попробовать реализовать теперь уже поточный шифр, например, Salsa20. И так, как у вас есть примитив AES, то написать еще и имитовставку (MAC) Poly1305-AES — и получится криптокоробочка из NaCl.
    • 0
      Пожалуй, это действительно нужно приложить к статье. Универсального умножения я не писал, только на константы из алгоритма. Специально оставил закомменченные варианты вычислений, ибо они понятнее, изящнее, но почему-то работают неправильно. Может кто подскажет почему?

      Умножение в поле Галуа
      def mul_by_02(num):
         
          if num < 0x80:
              res =  (num << 1)
          else:
              res =  (num << 1)^0x1b
      
          return res % 0x100
      
      def mul_by_03(num):
          return mul_by_02(num)^num
      
      def mul_by_09(num):
          #return mul_by_03(num)^mul_by_03(num)^mul_by_03(num) - works wrong, I don't know why
          return mul_by_02(mul_by_02(mul_by_02(num)))^num
       
      def mul_by_0b(num):
          #return mul_by_09(num)^mul_by_02(num)
          return mul_by_02(mul_by_02(mul_by_02(num)))^mul_by_02(num)^num
      
      def mul_by_0d(num):
          #return mul_by_0b(num)^mul_by_02(num)
          return mul_by_02(mul_by_02(mul_by_02(num)))^mul_by_02(mul_by_02(num))^num
      
      def mul_by_0e(num):
          #return mul_by_0d(num)^num
          return mul_by_02(mul_by_02(mul_by_02(num)))^mul_by_02(mul_by_02(num))^mul_by_02(num)
      
      • 0
        Почему умножение на {02} выполняется так странно? Умножение на 2 — это умножение на полином 1*x**1+0*x**0 (2_dec=10_bin), то есть это циклический сдвиг влево и всё:
        (b7*x**7+b6*x**6+b5*x**5+b4*x**4+b3*x**3+b2*x**2+b1*x**1+b0*x**0)*x = (b6*x**7+b5*x**6+b4*x**5+b3*x**4+b2*x**3+b1*x**2+b0*x**1+b7*x**0).
        Откуда там взялось XOR с 1b?..
        Умножение на {03} (попросту на тройку) — это умножение на полином (x+1), что даст
        ((b6+b7)*x**7+(b5+b6)*x**6+(b4+b5)*x**5+(b3+b4)*x**4+(b2+b3)*x**3+(b1+b2)*x**2+(b0+b1)*x**1+(b7+b0)*x**0).
        Коэффициенты — биты, поэтому 1+1=0, 0+1=1+0=1, 0+0=0.
        Всё просто.
        Если они используют модуль x**4+1 с допустимыми коэффициентами {0,1}, то это означает, что x**4 можно заменить на 1, x**5 — на x и так далее x**n на x**(n-4m).
        • 0
          Опровергать вашу теорию не буду, может я и допустил где-то ошибки. Дело было давно, но точно помню, что критерием правильности функций умножения для меня было совпадение их результатов с таблицами в конце этой статьи. В качестве исходных данных брался массив чисел [0..255]. Точно помню, что этот тест мои функции прошли, иначе бы статью здесь я не опубликовал
          • 0
            Так тогда понятно про 0x1b… Кто бы знал про полином
            x^8 + x^4 + x^3 + x + 1
            из Вашей ссылки… Просто происходит замена x^8 на x^4+x^3+x+1, а это и есть 00011011=0x1b.
            Тогда я был частично неправ. Но матрицу 4x4 я проверил — она совпала, но там при умножении полиномов x^4 заменялась на 1, так как там модуль x^4+1 = 0.
      • 0
        Мне кажется, что сработает вариант
        def mul2(num):
            return ((num<<1)^(num>>7))
        


        если num — один байт.
      • 0
        Не работает, потому что нельзя раскладывать 9 на сумму 3+3+3, так как в двоичном коде число 9=00001001, а число 3=00000011.
        Сумма трёх троек даст опять тройку, так как 11+11+11 = 00+11=11. Ну, или полиномами: x+1+x+1+x+1=x+1 (коэффициенты складываются по модулю два, то есть 3x=(3-2)x=x).
        Девятка — это полином x^3+1, а x^3 — это три раза умножить на x, то есть на 2=00000010=>1*x^1+0*x^0, поэтому
        n*9=mul2(mul2(mul2(n))) XOR n. Число n — это полином степени 7 с коэффициентами {0,1} (один байт).
  • 0
    А вот есть реализация даже на ассемблере Z80:

    zx.pk.ru/showthread.php?t=20955

Только зарегистрированные пользователи могут оставлять комментарии. Войдите, пожалуйста.