Există ceva înșelător în articolul Wikipedia. Ei au scris:
$s = b \oplus (b \lll 1) \oplus (b \lll 2) \oplus (b \lll 3) \oplus (b \lll 4)$
Este egal cu:
$s = b \times 31 \mod 257$
Unde $\ori$ este înmulțirea polinomială a $b$ și $31$ luate ca matrice de biți. Dar $\mod 257$ nu este o operație modulo standard, este mod în $GF(2^8)$ și $257$ este de fapt polinom de forma $x^{9}+1$.
Putem vedea cu ușurință acea multiplicare fără transport a $b \times 31$ este egal cu:
$s = b \oplus (b \ll 1) \oplus (b \ll 2) \oplus (b \ll 3) \oplus (b \ll 4)$
în biți $7,6,5,4$, Unde $\ll$ este deplasare pe biți, nu sfift circular. Dar în exemplul Wikipedia și în AES există o schimbare circulară. Deci de unde vine circulara? Ea provine din reducerea prin polinom $x^9+1$. Acesta este modul în care funcționează înmulțirea cu reducerea polinomială $GF(2^8)$:
#include <cstdint>
#include <cstdio>
#include <set de biți>
#include<iostream>
uint8_t multiplica (uint a, uint b)
{
uint8_t p = 1;
uint16_t L = 1;
uint16_t c = 0;
pentru (unsigned int i = 0; i < 8; ++i)
{
c ^= a & (L << i) ? (uint16_t)b << i : 0;
}
pentru (unsigned int i = 8; i-- > 0; )
{
dacă (c & (L << (i + 8)))
{
c ^= L << (i + 8);
c ^= (uint16_t)p << i;
}
}
return (uint8_t)c;
}
int main()
{
uint rezultat = 0;
rezultat = multiplicare(131,31);
std::cout << rezultat;
întoarce 0;
}
Avem nevoie de polinom de grad $9$, dar putem defini polinomul reducător în implementare practică luând doar primul său $8$ biți cei mai puțin semnificativi, deci în cazul nostru $p=1$. Acum, dacă ne uităm cum funcționează multiplicarea fără transport (prima buclă), putem vedea asta în $7,6,5,4$ biți am obține același rezultat, ca și în cazul deplasărilor:
$s = b \oplus (b \ll 1) \oplus (b \ll 2) \oplus (b \ll 3) \oplus (b \ll 4)$
Dar în loc de biți $11,10,9,8$ vor fi exact biți deplasați (anulați) în procesul de deplasare pe biți. Acest lucru se datorează faptului că înmulțirea fără transport le mută spre stânga $1,2,3...$ poziții și apoi totul este xored. Ca aici:
Din moment ce înmulțim cu $31$ am primi mereu $4$ biți suplimentari în jumătatea semnificativă mai mare a rezultatului nostru pe 16 biți. Și ar fi deranjați, pentru că așa funcționează înmulțirea fără transport. Deci acum avem bucăți $7,6,5,4$ egal cu rezultatul:
$s = b \oplus (b \ll 1) \oplus (b \ll 2) \oplus (b \ll 3) \oplus (b \ll 4)$
Și biți $11,10,9,8$, care ar putea fi în loc de biți $3,2,1,0$. Pentru a face o schimbare circulară, trebuie să facem doar xor înapoi acești biți. Aceasta se realizează prin:
pentru (unsigned int i = 8; i-- > 0; )
{
dacă (c & (L << (i + 8)))
{
c ^= L << (i + 8);
c ^= (uint16_t)p << i;
}
}
Dacă $p=1$. Putem vedea că acest cod chiar verifică dacă există un pic egal cu $1$ pe poziția stângă $i$ din jumătatea noastră superioară, iar dacă este, atunci xor aceia bit cu bit $i$ pe jumătatea noastră de jos. Și tot acel algoritm este egal cu xoring cu deplasare circulară $\lll$:
$s = b \oplus (b \lll 1) \oplus (b \lll 2) \oplus (b \lll 3) \oplus (b \lll 4)$
Știind acest lucru, devine clar că acest tip de echivalență este valabil pentru oricare $GF(2^k)$, cu condiția să alegem $p=1$ (prin convenția codului postat) ca polinomul și multiplicatorul nostru egal cu $2^{\frac {k}{2}+1}+1$.
