Bức tranh toàn cảnh: đoạn mã này cần tính đa thức nhị phân nghịch đảo modulo bất khả quy $P$ của mọi đa thức nhị phân khác 0 $R$ mức độ thấp hơn so với $P$. Hướng tới điều này, nó đã chọn một đa thức sinh $G=1+x$và lập bảng $Q_i=G^i\bmod P$, đạt được tất cả mong muốn $R$. Nghịch đảo nhân của $R=Q_i$ Là $Q_{255-i}$.
Mã này đánh giá AES S-box và nó nghịch đảo như sau:
(khối mã bắt đầu từ cố gắng) Nó đánh giá p = 0x11b = 283 đại diện cho đa thức nhị phân $P=1+x+x^3+x^4+x^8$ dưới dạng số nguyên: giá trị thu được khi đánh giá đa thức này cho số nguyên $x=2$. Quy ước chung này được sử dụng trong AES để ánh xạ đa thức nhị phân thành số nguyên.
(khối mã bắt đầu từ để t) Nó tính bảng t[tôi] đại diện cho đa thức nhị phân $Q_i=(1+x)^i\bmod P$ theo quy ước này. Điều đó $Q_i$ được tính cho mỗi lần lặp lại $Q_{i+1}=Q_i\,(1+x)\bmod P$ với $Q_0=1$, dịch¹ sang t[i+1] = t[i] ^ ((t[i] << 1) ^ ((t[i] >>> 7) * p)) với t[0] = 1 theo quy ước nói trên.
Ví dụ: $Q_0$ là đa thức (nhị phân) $1$, đại diện bởi t[0] = 1. $Q_1=1+x$, đại diện bởi t[1] = 3. $Q_2=(1+x)^2=1+x^2$, đại diện bởi t[2] = 5. $Q_7=(1+x)^7=1+x+x^2+x^3+x^4+x^5+x^6+x^7$, đại diện bởi t[2] = 0xff = 255. $Q_8=(1+x)^8\bmod P=(1+x^8)\bmod P=x+x^3+x^4$, đại diện bởi t[8] = 0x1a = 26.
(khối mã bắt đầu từ hãy để Sbox) Lập bảng $Q_i=(1+x)^i\bmod P$ hữu ích vì $(1+x)^{255}\bmod P=1$, vì thế $Q_{255-i}$ là nghịch đảo nhân của $Q_i$. Và $Q_i$ tiến tới tất cả các đa thức nhị phân khác 0 có bậc $<8$ (đó là $1+x$ là máy phát điện). Do đó số nguyên t[255 - tôi] đại diện cho nghịch đảo nhân của đa thức mà số nguyên t[tôi] đại diện. Và khi ở trong vòng lặp tôi đi từ 0 đến 254 tạo ra nghịch đảo nhân của mỗi trong số 255 đa thức khác không của bậc $<8$. Sau đó, vòng lặp chỉ áp dụng² phép biến đổi affine được chỉ định trong phần còn lại của định nghĩa của AES S-box. Đa thức bằng 0 là trường hợp đặc biệt.
Ví dụ: khi ở trong vòng lặp tôi = 8, t[tôi] Là t[8] = 0x1a = 26 đại diện $Q_8=x+x^3+x^4$, và t[255-i] (sẽ x, không liên quan đến $x$) Là t[247] = 0xfd = 253 đại diện cho đa thức $Q_{247}=1+x^2+x^3+x^4+x^5+x^6+x^7$. Điều đó $Q_{247}$ là nghịch đảo nhân của $Q_8$. Theo định nghĩa của AES S-box, chỉ còn cách áp dụng phép biến đổi affine² cho x, sau đó đặt kết quả vào Sbox[t[i]] = Sbox[26].
(hàm ngược) Bảng nghịch đảo được tính bằng cách tìm kiếm từng mục trong bảng. Điều đó hoạt động nhưng không hiệu quả. InvSbox[i] = sbox.indexOf(i); có thể được thay thế bằng cách đơn giản và hiệu quả hơn InvSbox[sbox[i]] = i;.
¹ Biện minh: trong t[i+1] = t[i] ^ ((t[i] << 1) ^ ((t[i] >>> 7) * p))
t[tôi] là một số nguyên trong $[0,2^8)$ và đại diện $Q_i$ bằng cấp $<8$t[i] << 1 là số nguyên chẵn trong $[0,2^9)$ và đại diện $Q_i\,x$.t[i] >>> 7 là một trong hai 0 hoặc 1. Đó là hệ số của thời hạn đặt hàng $x^7$ Trong $Q_i$.(t[i] >>> 7) * p tương ứng là một trong hai 0 hoặc 0x11b = 283, đại diện $0$ hoặc $P$.(t[i] << 1) ^ ((t[i] >>> 7) * p) đại diện tương ứng $(Q_i\,x)$ hoặc $(Q_i\,x)+P$, và (bằng cách kiểm tra hai trường hợp) là một số nguyên trong $[0,2^8)$, do đó đại diện cho một đa thức nhị phân bậc $<8$, do đó là $(Q_i\,x)\bmod P$.t[i] ^ ((t[i] << 1) ^ ((t[i] >>> 7) * p)) do đó là một số nguyên trong $[0,2^8)$ và đại diện $Q_i+(Q_i\,x)\bmod P)=Q_i\,(1+x)\bmod P=Q_{i+1}$, bằng cấp $<8$.
Trong C, thành ngữ thời gian không đổi có khả năng tiêu chuẩn cho biểu thức này sẽ là (về cơ bản với & - được sử dụng thay cho phép nhân):
t[i+1] = t[i] ^ ((t[i] << 1) ^ (p & -(t[i] >> 7))).
Lưu ý: một số trình biên dịch C quá nhiệt tình sẽ sủa sai -, khiến họ im lặng.
² Tuyên bố x |= x << 8;nhân đôi các bit trong biến x (đại diện cho nghịch đảo mô-đun của $Q_i$) sao cho các lần dịch phải tiếp theo trở nên tương đương với phép quay khi nói đến 8 bit bậc thấp. tuyên bố x ^= (x >> 4) ^ (x >> 5) ^ (x >> 6) ^ (x >> 7); thực hiện các ma trận tuần hoàn phép nhân. sau đó ^ 0x63 (đại diện cho đa thức $1+x+x^5+x^6$) là phép cộng không đổi, và & 0xFF giữ 8 bit bậc thấp (về mức độ $<8$), hoàn tác trùng lặp.
