Мультипликативная обратная таблица GF(2^4) в массиве Java или C

Я должен написать таблицу поиска мультипликативного обратного в GF(24). Я уже выписал таблицу умножения, и я не собираюсь делать это снова. Вот таблица, которую я написал в качестве примера. Я надеюсь, что никто никогда не будет писать это снова. Я чувствовал себя глупо.

Таблица умножения на GF(24)

// Multiplication table over Galois Field 2^4 
byte mulTable[][] = {
        {0, 0, 0, 0, 0, 0, 0, 0, 0, 0,   0,   0,   0,   0,   0,   0},
        {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 0xa, 0xb, 0xc, 0xd, 0xe, 0xf}, 
        {0, 2, 4, 6, 8, 0xa, 0xc, 0xe, 3, 1, 7, 5, 0xb, 9, 0xf, 0xd},
        {0, 3, 6, 5, 0xc, 0xf, 0xa, 9, 0xb, 8, 0xd, 0xe, 7, 4, 1, 2},
        {0, 4, 8, 0xc, 3, 7, 0xb, 0xf, 6, 2, 0xe, 0xa, 5, 1, 0xd, 9},
        {0, 5, 0xa, 0xf, 7, 2, 0xd, 8, 0xe, 0xb, 4, 1, 9, 0xc, 3, 6},
        {0, 6, 0xc, 0xa, 0xb, 0xd, 7, 1, 5, 3, 9, 0xf, 0xe, 8, 2, 4},
        {0, 7, 0xe, 9, 0xf, 8, 1, 6, 0xd, 0xa, 3, 4, 2, 5, 0xc, 0xb},
        {0, 8, 3, 0xb, 6, 0xe, 5, 0xd, 0xc, 4, 0xf, 7, 0xa, 2, 9, 1},
        {0, 9, 1, 8, 2, 0xb, 3, 0xa, 4, 0xd, 5, 0xc, 6, 0xf, 7, 0xe},
        {0, 0xa, 7, 0xd, 0xe, 4, 9, 3, 0xf, 5, 8, 2, 1, 0xb, 0xc, 6},
        {0, 0xb, 5, 0xe, 0xa, 1, 0xf, 4, 7, 0xc, 2, 9, 0xd, 6, 8, 3},
        {0, 0xc, 0xb, 7, 5, 9, 0xe, 2, 0xa, 6, 1, 0xd, 0xf, 3, 4, 8},
        {0, 0xd, 9, 4, 1, 0xc, 8, 5, 2, 0xf, 0xb, 6, 3, 0x3, 0xa, 7},
        {0, 0xe, 0xf, 1, 0xd, 3, 2, 0xc, 9, 7, 6, 8, 4, 0xa, 0xb, 5},
        {0, 0xf, 0xd, 2, 9, 6, 4, 0xb, 1, 0xe, 0xc, 3, 8, 7, 5, 0xa}
    };   

Я не хочу делать это снова для обратного!
Кто-нибудь знает таблицу (желательно в массиве Java или C 16x16), подходящую для копирования и вставки из нее? Я искал github, пытаясь найти тот, который уже был написан, но без радости.

Мотивация /Rational
Мне не обязательно выполнять поиск по таблице, но я не хочу добавлять сто строк кода, чтобы просто генерировать поле на лету (это всего лишь оценка, но я сомневаюсь, что смогу сделать это в Меньше).

2 ответа

Решение

Таблица умножения представляет двоичную операцию "*": x * y = z тогда и только тогда, когда mulTable[x][y] == z

Инверсией элемента x является другой элемент y такой, что x * y = 1, эквивалентно mulTable[x][y] == 1. Иногда обратного не существует. Для этой двоичной операции не существует обратного 0. На этом фоне следующий код вычисляет таблицу инверсий, используя только ту таблицу умножения, которую вы указали.

public static byte[] computeInverseTable() {
    byte [] inverseTable = new byte[16];
    inverseTable[0] = 0; // the inverse of 0 doesn't exist.

    for (int x = 1; x<16; x++) {
        for (int y = 1; y<16; y++) {
            if (mulTable[x][y] == 1) {
                inverseTable[x] = (byte) y;
                break;
            }
        }
    }
    return inverseTable;
}

Этот вопрос означает, что вы не правильно понимаете проблему. В вашем теге вы упоминаете шифрование.

Но это довольно маленькое поле у ​​вас там...

Есть только один алгоритм шифрования (который я знаю), который использует GF (2 4). Этот алгоритм - алгоритм Simplified-AES, разработанный профессором Эдвардом Шефером из Университета Санта-Клары и несколькими его учениками. Вы должны изучить этот материал и понять алгоритм.

Какого черта вам понадобится стол инверсий в любом случае!?

Возможно, вы заметили, что, потратив время на изучение YouTube, алгоритм никогда не включает деление. Так что вам не нужны инверсии. Единственное место, где алгоритм выполняет умножение, находится в функции mixColums, и у вас уже есть таблица умножения для этого. Инверсия mixColumns не делит и не нуждается в инверсиях, либо просто использует другую матрицу 2x2.

Если бы вам пришлось делить, не могли бы вы использовать таблицу умножения, чтобы найти обратное?
... А как бы выглядела эта таблица инверсий? Будет ли это 16x16?

А теперь выходи ТАК и возвращайся к учебе.

Другие вопросы по тегам