Неправильное умножение / деление в поле Галуа (2^8)

Question

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

Однако я провалил несколько тривиальных тестовых случаев.

пример:

//passes  
assert((GF256elm(4) / GF256elm(1)) == GF256elm(4));  
assert((GF256elm(32) / GF256elm(16)) == GF256elm(2));  
assert((GF256elm(15) / GF256elm(5)) == GF256elm(3));  
assert((GF256elm(88) / GF256elm(8)) == GF256elm(11));  
//fails, but should pass
assert((GF256elm(77) / GF256elm(11)) == GF256elm(7));
assert((GF256elm(77) / GF256elm(7)) == GF256elm(11));  

Первые четыре строки проходят, однако они терпят неудачу как на 5-й, так и на 6-й линии.
После дальнейшего изучения я обнаружил, что эти ошибки возникают, когда происходит "перезапись", т.е. log3(a) + log3(b) > 255 (случай умножения) или log3(a) - log3(b) < 0, Однако значение "модифицируется" таким образом, что они остаются в 0~255, используя истинный модуль.

GF256elm& GF256elm::operator/=(const GF256elm& other) { //C++ operator override for division
    int t = _logTable[val] - _logTable[other.val]; //log3(a) - log3(b)
    int temp =  ((t % 255) + 255) % 255; //this wraps the value to between 0~254 inclusive.
    val = _expTable[temp];
    return *this;
}

/ Оператор реализован с использованием /= переопределите выше, так что ничего особенного там не происходит.

Я проверил, что сгенерированные таблицы log/exp верны.

Что мне здесь не хватает? Спасибо!

Answer 1

Сначала внимательно прочитайте этот вопрос и все его ответы и комментарии:

Сложение и умножение в поле Галуа

Я думаю, что ваш код в порядке, но у вас есть две проблемы.

Во-первых, комментарии неверны; Вы держите показатель в диапазоне 0-254, а не 0-255.

Во-вторых, ваши "тривиальные" тестовые примеры неверны.

В этом поле представьте числа как многочлены, коэффициенты которых вы получите из двоичного представления числа. Например, так как 5 = 2^2 + 1, в этом поле "5" означает x ^ 2 + 1.

Итак, "5" * "3" = (x^2 + 1) * (x + 1) = x^3 + x^2 + x + 1 или "15". Вот почему ваш тестовый пример assert((GF256elm(15) / GF256elm(5)) == GF256elm(3)); работает. Это не имеет ничего общего с вашим обычным представлением, что пять раз три равно пятнадцати. Точно так же и для других ваших рабочих тестовых случаев, которые вы заметите, в основном включают степени два.

Однако "7" * "11" = (x^2 + x + 1) * (x^3 + x + 1) = x^5 + x^4 + 2x^3 + 2x^2 +2x + 1

Но все коэффициенты по модулю 2, так что на самом деле это x^5 + x^4 + 1 = "49". Вот почему ваши последние два теста провалились.

Если вы попытаетесь assert(GF256elm(49) / GF256elm(7) == GF256elm(11)); Вы должны найти это проверить.

Answer 2

В коде нет ничего плохого. Умножение / деление конечных полей отличается от обычной арифметики. Пожалуйста, обратитесь к этому вопросу в cryptostackxchange.

Answer 3

x % n оценивается как целое число от 0 до (n - 1) включительно.

Это означает, что x % 255 оценивается как целое число от 0 до 254, а не от 0 до 255.

Вы должны заменить 255 на 256 или, альтернативно, выполнить побитовое И с 0xff за тот же результат. Последний работает быстрее, хотя вполне вероятно, что компиляторы достаточно умны, чтобы оптимизировать их под один и тот же байт-код.