Операция умножение в поле Галуа GF(256)
Поясню суть вопроса: пытаюсь разобраться как производить операцию умнжения в конечных полях (finite fields). Точнее как умножать я понимаю:
For the AES algorithm, this irreducible polynomial is
m(x) = x8 + x 4 + x3 + x +1, or {01}{1b} in hexadecimal notation.
Не могу понять пример, прилагавшийся к мануалу(умножение в полиномиальном виде):
For example, {57} · {83} = {c1}, because
(x6 + x4 + x2 + x +1) (x7 + x +1)
= x13 + x11 + x9 + x8 + x7 + x7 + x5 + x3 + x 2 + x + x6 + x 4 + x 2 + x +1 = x13 + x11 + x9 + x8 + x6 + x5 + x 4 + x3 +1
and
x13 + x11 + x9 + x8 + x6 + x5 + x 4 + x3 +1 modulo ( x8 + x 4 + x3 + x +1)
= x7 + x 6 +1.
Если производить оперцию "·" как обычное умножение, то:
57*83=2С85
Но, судя по всему, там еще происхожит сложение одинаковых членов между собой по mod2 т.о. получается x7 XOR x7 = 0
если это так, то получаем ответ:
57*83=2B79 (10101101111001 в двоичном)
НО 2B79 mod 11B = 5C а не С1 !???:confused:
Помогите, пожалуйста, найти ошибку!
з.ы. пример из FIPS 197 - AES standard - ошибок быть не может
corresponding powers in the polynomials for the two elements. The addition is performed with
the XOR operation - i.e., modulo 2
...
Consequently, subtraction of polynomials is identical to addition of polynomials.
т.о. операция умножения, действительно, производится по след. правилу:
1) умножение 2х полиномов друг на друга - правилами обычной математики
2) суммирование полученных x^i по модулю 2 (XOR)
операция Mod(x) поризводится следующим образом:
1) x5*(x8 + x 4 + x3 + x +1) = x13 + x9 + x8 + x6 + x5
2) [x13 + x11 + x9 + x8 + x6 + x5 + x 4 + x3 +1] XOR [x13 + x9 + x8 + x6 + x5] = x11 + x4 + x3 + 1
3) x3*(x8 + x 4 + x3 + x +1) = x11 + x7 + x6 + x4 + x3
4) [x11 + x7 + x6 + x4 + x3] XOR [x11 + x7 + x6 + x4 + x3] = x7 + x 6 +1
получили такой же ответ как в примере:
x13 + x11 + x9 + x8 + x6 + x5 + x 4 + x3 +1 modulo ( x8 + x 4 + x3 + x +1)
= x7 + x 6 +1.
Соответственно пявился еще один интересный вопрос: как реализовать такую логику умножения в коде??? Посоветуйте что-нть, пжалста!!!
http://www.av5.com/journals-magazines-online/1/34/296
а вообще мне этот пост напоминает разговор с самим собой)
Peasant algorithm:
/* Multiply two numbers in the GF(2^8) finite field defined
* by the polynomial x^8 + x^4 + x^3 + x + 1 */
uint8_t gmul(uint8_t a,uint8_t b)
{
uint8_t p = 0;
uint8_t counter;
uint8_t hi_bit_set;
for(counter = 0; counter < 8; counter++) {
if((b & 1) == 1)
p ^= a;
hi_bit_set = (a & 0x80);
a <<= 1;
if(hi_bit_set == 0x80)
a ^= 0x11b; /* x^8 + x^4 + x^3 + x + 1 */
b >>= 1;
}
return p;
}
Спасибо всем, кто помог, я без вас бы не справился, тема закрыта xD
Посмотри документ "Rijndael: AES Proposal". Там в конце указано, как сделать совсем быстрый алгоритм. Правда, разобраться в этом будет посложнее, чем в умножении в GF(256). Вообще, этот документ полезно почитать, так как он дает более полное описание алгоритма. В стандарте он слегка урезан.
на счет таблицы умножения GF(256) - спасибо, идея действительно хорошая. я как раз сеня када ехал из универа прикинул сколько потребуется примерно операций для формирования S-box, 1 перемешивания строки и задумался о необходимости оптимизации.
Вообще-то все элементы поля можно представить в виде степеней примитивного элемента (в любом поле Галуа существует такой элемент, все степени которого образуют поле) тогда умножение элементов сводится к сложению их степеней в данном примере по модулю 256.
Приведение результата умножения двух полиномов по модулю образующего полинома поля - есть не что иное как остаток от деления результата на образующий полином.
Табличный метод умножения самый быстрый, но можно и сложением степеней обойтись, понадобится только одномерный масив (256), где по адресу значения элемента будет записана его степень:)
Читал.
Статья может быть и хорошая, но авторский стиль изложения мне не нравится. К тому же способ табличного умножения, предложенный автором ("берем это, умножем на то, ищем здесь") малого того что не понятен (я бы даже сказал неинформативен), но и неправилен! Поробовал считать этой табличкой - ответы получаются неверные. Конечно, может я не так понял способ (что собственно и неудивительно, т.к. автор говорить как делать, но не приводить ни одного аргумента почему надо делать именно так)...
Короче говоря, статья ацтой. Хотя можно ознакомится - поверхностно проясняет тему вопроса в целом (не более) :(
p.s. Gigahard, перед тем как постить ответ мог бы по ссылке сходить....и не постить :)[QUOTE=Аццкий программер]нашел статейку, правда пока нет времени читать
http://www.av5.com/journals-magazines-online/1/34/296[/QUOTE]
В некоторых примерах там ошибки, я бы даже сказал не ошибки, а опечатки, которые подлежат исправлению.
Конечно если понимать что исправлять.
По поводу заявления о том, что табличный метод не правильный... Хм... Ну Вам видимо лучше видно.
Только табличный метод в большинстве случаев позволяет ускорить вычисления, при минимуме ресурсов.
Кстати, что Вы подразумеваете под "неверными ответами"?
"автор говорить как делать, но не приводить ни одного аргумента почему надо делать именно так"
Это нужно делать так, потому что стандарт.
Таблица может иметь произвольный вид. И это никоим образом не вытекает из арифметики Галуа. Таблица, это договоренность.
Странно, а мне показалось, что автор все достаточно досканально разжевывает...
В частности есть стандарт ECMA 130 которому придерживается автор. Что самое интересное - стандарт тоже повествует о том КАК нужно делать, но не рассказывает ПОЧЕМУ. На то он и стандарт.
P.S. И вообще, я постил для viat1
Тогда как прикажите строить табличку для неприводимого многочлена: x8+x4+x3+x+1 ?
"Поробовал считать этой табличкой - ответы получаются неверные."
Вероятно, вы попросту построили просто несколько подгруп порядка = делителю порядка поля, поскольку полином у вас дан не примитивный.
P.S. При малом порядке поля я сам пользуюсь табличным методом (методом Зеча), но только когда есть право выбора полинома. А вот когда даётся не примитивный полином....пока ещё не решил что делать.