Thuật toán AES (Advanced Encryption Standard) nhận các khối từ 128 bit trở lên và áp dụng một chuỗi các thay thế và hoán vị. Sự thay thế sử dụng một “S-box”, được đặt tên là Rijndael S-box theo tên các nhà thiết kế của nó, một phép biến đổi phi tuyến có thể đảo ngược hoạt động trên 8 bit cùng một lúc.
Các bài viết liên quan:
Có thể có 256 = 16 × 16 số 8-bit, và vì vậy S-box có thể được biểu diễn dưới dạng đầu vào ánh xạ bảng 16 x 16 đến đầu ra. Bạn có thể tìm thấy các bảng đại diện cho S-box và nghịch đảo của nó trong đoạn dưới này ở định dạng chế độ tổ chức.
AES S-box
0x11 -> 0x82 và 0xA7 -> 0x5C.
Ví dụ, 0x82 -> 0x11 và 0x5c -> 0xA7.
Bài đăng này sẽ xem xét chi tiết cách các mục nhập của bảng đó được điền. Mô tả cấp cao của thiết kế như sau. Đối với một số x 8 bit,
- Nghịch đảo trong GF (28)
- Nhân với ma trận L
- Thêm một hằng số c.
Tiếp theo, chúng ta đi sâu vào ý nghĩa của từng bước này. Và ở phần cuối, chúng tôi sẽ làm một ví dụ chi tiết.
Nghịch đảo trong GF (2^8)
Bước 1 và 3 lấy nghịch đảo của một số là thành viên của trường hữu hạn GF (2^8), trường hữu hạn có 2^8 phần tử.
Số phần tử trong một trường hữu hạn xác định trường, lên đến đẳng cấu. Nghĩa là, theo một nghĩa nào đó, chỉ có một trường có 2^8 = 256 phần tử. Trong thực tế có nhiều trường khác nhau với 256 phần tử. Các trường này là đẳng cấu, nhưng khi chúng tôi thực hiện các phép tính thực tế, thay vì lý thuyết trừu tượng, chúng tôi cần chỉ định biểu diễn mà chúng tôi đang sử dụng.
Trường hữu hạn có thể được chỉ định dưới dạng đa thức modulo một đa thức bất khả quy. Để thực hiện các phép tính của mình, chúng ta cần chỉ định một đa thức bậc 8 bất khả quy cụ thể với các hệ số nhị phân. Cái mà AES sử dụng là
p (x) = x8 + x4 + x3 + x + 1.
Vì vậy, bằng cách lấy nghịch đảo trong GF (2^8), chúng tôi muốn lấy một số 8 bit y, giải thích nó là một đa thức với các hệ số nhị phân và tìm một số 8 bit khác x^-1 sao cho khi chúng tôi nhân chúng thành đa thức, và lấy phần dư sau khi chia cho p (x) ta được đa thức 1.
Có một vấn đề trong quy trình này: chỉ 255 trong số 256 phần tử của GF (28) có nghịch đảo. Không có nghịch đảo nào cho 0, nhưng vì mục đích của chúng tôi, chúng tôi sẽ lấy nghịch đảo của 0 là 0.
Nhân với L
Ma trận L chúng ta cần ở đây là ma trận nhị phân 8 x 8 có các mục là
10001111
11000111
11100011
11110001
11111000
01111100
00111110
00011111
Khi chúng ta nói nhân x^-1 với L, nghĩa là chúng ta nghĩ về x^-1 như một vectơ trên trường của hai phần tử và thực hiện phép nhân ma trận trong ngữ cảnh đó.
Hằng số cộng
Hằng số mà chúng tôi thêm vào là 0x63. Lý do hằng số cộng được chọn là để đầu vào bằng không sẽ không ánh xạ đến đầu ra bằng không. Lưu ý rằng “phép cộng” ở đây là phép cộng vectơ và được thực hiện trên trường của hai phần tử, giống như phép nhân ở trên. Điều này tương đương với XOR của các bit.
Ví dụ tính toán
Để làm cho mọi thứ ở trên cụ thể hơn, chúng tôi sẽ tính toán thủ công một mục của bảng.
Hãy bắt đầu với đầu vào y = 0x11 = 0b10001. Ta biểu diễn y là đa thức f (x) = x4 + 1 và tìm đa thức g (x) sao cho phần dư khi f (x) * g (x) chia cho p (x) xác định ở trên là 1.
Quá trình tìm g rất phức tạp — có thể tôi sẽ viết blog về nó trong tương lai — nhưng tôi khẳng định
g (x) = x7 + x5 + x4 + x2
có nghĩa là nghịch đảo của y trong GF (2^8), được biểu diễn dưới dạng nhị phân, là 0b10110100 = 0xB4. Bạn có thể tìm thấy một bảng đảo ngược ở đây.
Tiếp theo, chúng ta nhân ma trận L với vectơ được tạo ra từ các bit của y^-1. Tuy nhiên, có một gotcha ở đây. Tác giả nói rằng hãy nhân các bit của y-1 với L, họ cho rằng các bit được sắp xếp từ ít quan trọng nhất đến quan trọng nhất. Vì các bit của y-1 là 10110100, chúng tôi nhân L với vectơ
[0, 0, 1, 0, 1, 1, 0, 1].Phép nhân này cho chúng ta vectơ
[1, 0, 0, 0, 0, 1, 1, 1].Tiếp theo, chúng tôi thêm vectơ được hình thành từ các bit của 0x63, một lần nữa từ ít quan trọng nhất đến quan trọng nhất. Điều đó có nghĩa là chúng tôi đặt ra 0x63 = 0b01100011 là
[1, 1, 0, 0, 0, 1, 1, 0].Điều này cho chúng tôi kết quả
[0, 1, 0, 0, 0, 0, 0, 1].Đọc các bit từ ít quan trọng nhất đến hầu hết, điều này cho kết quả là 0x82.
Tóm lại, chúng tôi đã xác minh rằng hộp AES S có từ 0x11 đến 0x82, như đã nêu trong bảng.
