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

Я пытаюсь реализовать умножение и деление в 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.

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


c++ cryptography galois-field
person Jacob Wang    schedule 25.08.2013    source источник
comment
Мои извинения. да, я реализовал это и должен был упомянуть об этом. По сути, он просто использует /= в терминах LHS и RHS и возвращает результат, так что ничего особенного. отредактировал мой ответ.   -  person Jacob Wang    schedule 25.08.2013

Ответы (3)


arrow_upward
4
arrow_downward

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

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

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

Во-первых, комментарии неверны; вы держите показатель степени в диапазоне 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));, вы обнаружите, что это работает.

person Nemo    schedule 26.08.2013
comment
Я знаю (и намеренно) поместил его в диапазон от 0 до 254, как объяснено в моем комментарии. Спасибо за объяснение концепции умножения в конечном поле. Я действительно поставил плохие тестовые примеры из-за моего непонимания конечных полей. - person Jacob Wang; 26.08.2013
comment
@jtcwang, но комментарий в вашем коде говорит //this wraps the value to between 0~255 - person gx_; 26.08.2013
comment
починю. Спасибо, что заметили - person Jacob Wang; 06.09.2013

arrow_upward
0
arrow_downward

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

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

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

person ntoskrnl    schedule 25.08.2013
comment
Кстати, это верно не только для C++ %, но и для остатка от целочисленного деления (по модулю) вообще. Точность: когда x подписано (например, int x), x % 255 может оцениваться как целое число от -254 до 254 (включительно) (поэтому код OP - ((t % 255) + 255) % 255, а не просто t % 255). - person gx_; 25.08.2013
comment
Я пробовал это раньше, но это не работает. С моим ограниченным пониманием GF (2 ^ 8) шаблон таблицы exp/log повторяется на 255-м элементе. т. е. элемент [1] такой же, как [255], поэтому модуль равен 255. - person Jacob Wang; 25.08.2013

arrow_upward
0
arrow_downward

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

person Jacob Wang    schedule 26.08.2013