Что-то вводит в заблуждение в статье Википедии. Они написали:
$s = b \oplus (b \lll 1) \oplus (b \lll 2) \oplus (b \lll 3) \oplus (b \lll 4)$
Равно:
$s = b \times 31 \mod 257$
куда $\раз$ является полиномиальным умножением $b$ и $31$ воспринимаются как битовые массивы. Но $\мод 257$ не является стандартной операцией по модулю, это мод в $GF(2^8)$ и $257$ на самом деле является полиномом вида $х^{9}+1$.
Легко видеть, что умножение без переноса $b \раз 31$ равно:
$s = b \oplus (b \ll 1) \oplus (b \ll 2) \oplus (b \ll 3) \oplus (b \ll 4)$
в битах $7,6,5,4$, куда $\ll$ это побитовый сдвиг, а не круговой сдвиг. Но в примере с Википедией и в AES есть круговой сдвиг. Так откуда берется циркуляр? Это происходит из редукции полиномом $х^9+1$. Вот как работает умножение с полиномиальной редукцией в $GF(2^8)$:
#include <cstdint>
#include <cstdio>
#include <битсет>
#include<iostream>
uint8_t умножить (uint a, uint b)
{
uint8_t р = 1;
uint16_t L = 1;
uint16_t с = 0;
for (целое без знака i = 0; i < 8; ++i)
{
с ^ = а & (L << я) ? (uint16_t)b << i : 0;
}
for (целое без знака i = 8; i-- > 0; )
{
если (с & (L << (i + 8)))
{
с ^= L << (i + 8);
с ^= (uint16_t)p << i;
}
}
возврат (uint8_t)с;
}
основной ()
{
результат = 0;
результат = умножить (131,31);
std::cout << результат;
вернуть 0;
}
Нам нужен многочлен степени $9$, но мы можем определить уменьшающий многочлен в практической реализации, взяв только его первый $8$ младшие биты, поэтому в нашем случае $р=1$. Теперь, если мы посмотрим, как работает умножение без переноса (первый цикл), мы увидим, что в $7,6,5,4$ бит мы бы получили тот же результат, что и со сдвигами:
$s = b \oplus (b \ll 1) \oplus (b \ll 2) \oplus (b \ll 3) \oplus (b \ll 4)$
Но вместо бит $11,10,9,8$ будут ровно биты сдвинуты (отменены) в процессе побитового сдвига. Это связано с тем, что умножение без переноса перемещает их влево на $1,2,3...$ позиции, а затем все xored. Как здесь:
Так как мы умножаем на $31$ мы всегда получали $4$ дополнительные биты в старшей значащей половине нашего 16-битного результата. И они будут подвергнуты xoring, потому что именно так работает умножение без переноса. Итак, теперь у нас есть биты $7,6,5,4$ равно результату:
$s = b \oplus (b \ll 1) \oplus (b \ll 2) \oplus (b \ll 3) \oplus (b \ll 4)$
И биты $11,10,9,8$, который может быть вместо бит $3,2,1,0$. Чтобы сделать циклический сдвиг, нам нужно только выполнить операцию xor назад для этих битов. Это делается:
for (целое без знака i = 8; i-- > 0; )
{
если (с & (L << (i + 8)))
{
с ^= L << (i + 8);
с ^= (uint16_t)p << i;
}
}
Если $р=1$. Мы видим, что этот код действительно проверяет, равен ли бит $1$ слева на позиции $я$ нашей верхней половины, и если это так, то это xor тот бит с битом $я$ на нашей низкой половине. И весь этот алгоритм равен xoring с круговым сдвигом $\lll$:
$s = b \oplus (b \lll 1) \oplus (b \lll 2) \oplus (b \lll 3) \oplus (b \lll 4)$
Зная это, становится ясно, что такого рода эквивалентность имеет место для любого $GF(2^k)$, если мы выбираем $р=1$ (по соглашению размещенного кода), так как наш многочлен и множитель равны $ 2 ^ {\ гидроразрыва {к} {2} +1} + 1 $.
