Có điều gì đó sai lệch trong bài viết Wikipedia. Họ viết:
$s = b \oplus (b \lll 1) \oplus (b \lll 2) \oplus (b \lll 3) \oplus (b \lll 4)$
Bằng:
$s = b \times 31 \mod 257$
ở đâu $\times$ là phép nhân đa thức của $b$ và $31$ lấy dưới dạng mảng bit. Nhưng mà $\mod 257$ không phải là hoạt động modulo tiêu chuẩn, nó là mod trong $GF(2^8)$ và $257$ thực tế là đa thức có dạng $x^{9}+1$.
Chúng ta có thể dễ dàng thấy rằng phép nhân ít mang theo của $b \times 31$ bằng:
$s = b \oplus (b \ll 1) \oplus (b \ll 2) \oplus (b \ll 3) \oplus (b \ll 4)$
Trong các bit $7,6,5,4$, ở đâu $\ll$ là dịch chuyển bitwise, không phải là circualr sfift. Nhưng trong ví dụ Wikipedia và trong AES, có sự thay đổi vòng tròn. Vậy thông tư đến từ đâu? Nó xuất phát từ việc giảm bởi đa thức $x^9+1$. Đây là cách phép nhân với rút gọn đa thức hoạt động trong $GF(2^8)$:
#bao gồm <cstdint>
#bao gồm <cstdio>
#include <bitset>
#include<iostream>
uint8_t nhân lên(uint a, uint b)
{
uint8_t p = 1;
uint16_t L=1;
uint16_t c = 0;
for (unsign int i = 0; i < 8; ++i)
{
c ^= a & (L << i) ? (uint16_t)b << i : 0;
}
for (unsign int i = 8; i--> 0; )
{
nếu (c & (L << (i + 8)))
{
c ^= L << (i + 8);
c ^= (uint16_t)p << i;
}
}
trả về (uint8_t)c;
}
int chính ()
{
kết quả uint = 0;
kết quả = nhân (131,31);
std::cout << kết quả;
trả về 0;
}
Ta cần đa thức bậc $9$, nhưng chúng ta có thể định nghĩa đa thức rút gọn trong triển khai thực tế bằng cách chỉ lấy giá trị đầu tiên của nó $8$ bit ít quan trọng nhất, vì vậy trong trường hợp của chúng tôi $p=1$. Bây giờ nếu chúng ta xem xét cách thức hoạt động của phép nhân không mang (vòng lặp đầu tiên), chúng ta có thể thấy điều đó trong $7,6,5,4$ bit, chúng ta sẽ nhận được kết quả tương tự, như với các ca:
$s = b \oplus (b \ll 1) \oplus (b \ll 2) \oplus (b \ll 3) \oplus (b \ll 4)$
Nhưng thay cho bit $11,10,9,8$ sẽ chính xác là các bit được dịch chuyển (bị hủy) trong quá trình dịch chuyển từng bit. Điều này là do phép nhân ít mang di chuyển chúng sang trái bởi $1,2,3...$ vị trí và sau đó tất cả là xored. Như ở đây:
Vì chúng ta đang nhân với $31$ chúng tôi sẽ luôn nhận được $4$ các bit bổ sung ở một nửa có ý nghĩa cao hơn trong kết quả 16 bit của chúng tôi. Và họ sẽ bị xáo trộn, bởi vì đây là cách hoạt động của phép nhân ít mang. Vì vậy, bây giờ chúng tôi có bit $7,6,5,4$ bằng kết quả của:
$s = b \oplus (b \ll 1) \oplus (b \ll 2) \oplus (b \ll 3) \oplus (b \ll 4)$
Và bit $11,10,9,8$, có thể thay cho bit $3,2,1,0$. Để thực hiện dịch chuyển vòng tròn, chúng ta chỉ cần xor lùi các bit này. Điều này được thực hiện bởi:
for (unsign int i = 8; i--> 0; )
{
nếu (c & (L << (i + 8)))
{
c ^= L << (i + 8);
c ^= (uint16_t)p << i;
}
}
Nếu $p=1$. Chúng ta có thể thấy rằng mã này thực sự đang kiểm tra xem có bit nào bằng không $1$ ở bên trái trên vị trí $i$ của nửa trên của chúng tôi, và nếu đúng như vậy, thì nó xor bit đó với bit $i$ trên nửa thấp của chúng tôi. Và tất cả thuật toán đó tương đương với xoring với circialr shift $\lll$:
$s = b \oplus (b \lll 1) \oplus (b \lll 2) \oplus (b \lll 3) \oplus (b \lll 4)$
Biết được điều này, rõ ràng là loại tương đương này đúng với bất kỳ $GF(2^k)$, miễn là chúng tôi chọn $p=1$ (theo quy ước của mã đã đăng) là đa thức và cấp số nhân của chúng ta bằng $2^{\frac {k}{2}+1}+1$.
