2026年11月14日星期六

AES 加密演算法介紹(三):SubBytes

一、SubBytes 的用途

SubBytes 用同一張 AES SBOX 分別替換 4 × 4 State 中的 16 個 byte,為 AES 加入非線性。每個 byte 寫回原本的列與欄。AES-128、AES-192、AES-256 共用這張表。

二、SBOX 查表

SBOX 的全名是 Substitution Box(替換盒)。 AES 的 SBOX 是一張固定的位元組替換表,將 256 種可能的 8 位元輸入一對一映射到 256 種 8 位元輸出。

執行 SubBytes 時,會將 State 中的 16 個 byte 逐一透過 SBOX 查表替換,並將結果寫回原本的位置。SBOX 的功用就是透過這個替換步驟,為 AES 引入非線性。

高 4 bits 選列,低 4 bits 選欄。例如 0x53 查第 5 列、第 3 欄,得到 0xED。表內數值均為十六進位。

列\欄0123456789ABCDEF
0637C777BF26B6FC53001672BFED7AB76
1CA82C97DFA5947F0ADD4A2AF9CA472C0
2B7FD9326363FF7CC34A5E5F171D83115
304C723C31896059A071280E2EB27B275
409832C1A1B6E5AA0523BD6B329E32F84
553D100ED20FCB15B6ACBBE394A4C58CF
6D0EFAAFB434D338545F9027F503C9FA8
751A3408F929D38F5BCB6DA2110FFF3D2
8CD0C13EC5F974417C4A77E3D645D1973
960814FDC222A908846EEB814DE5E0BDB
AE0323A0A4906245CC2D3AC629195E479
BE7C8376D8DD54EA96C56F4EA657AAE08
CBA78252E1CA6B4C6E8DD741F4BBD8B8A
D703EB5664803F60E613557B986C11D9E
EE1F8981169D98E949B1E87E9CE5528DF
F8CA1890DBFE6426841992D0FB054BB16

三、手算過程

(一)乘法反元素

0x53 代表 x⁶ + x⁴ + x + 1。AES 的模約簡多項式是 x⁸ + x⁴ + x³ + x + 1(0x11B)。反元素與 0x53 相乘並對 0x11B 取餘數後,結果為 0x01。

用擴展歐幾里得法,先將 0x11B 和 0x53 各自的 0x53 係數設為 0x00 和 0x01。每一步以多項式除法求商與餘式,減法用 XOR。餘式的 0x53 係數等於「被除式的係數 ⊕(商 × 除式的係數)」。下表均為十六進位。

被除式除式商餘式餘式的 0x53 係數
0x11B0x530x050x040x05
0x530x040x140x030x45
0x040x030x030x010xCA

餘式到 0x01 時,對應係數為 0xCA,所以反元素是 0xCA。驗算:0x53 × 0xCA = 0x3F7E,對 0x11B 取餘數得 0x01。

(二)Affine Transformation

依 FIPS 197 §5.1.1 公式 (5.3),將乘法反元素 b = 0xCA = 11001010₂ 代入 Affine Transformation(仿射轉換)。固定常數為 c = 0x63 = 01100011₂。

b′i = bi ⊕ b(i+4) mod 8 ⊕ b(i+5) mod 8 ⊕ b(i+6) mod 8 ⊕ b(i+7) mod 8 ⊕ ci   (5.3)

i 從 0 到 7,最右邊是 bit 0。每次先依索引取出五個 b 的位元,再與同位置的 c 位元做 XOR。例如 i = 1 時,最後一個輸入索引是 (1 + 7) mod 8 = 0,所以取 b0。

i依公式取位代入 0 或 1輸出
0b0 ⊕ b4 ⊕ b5 ⊕ b6 ⊕ b7 ⊕ c00 ⊕ 0 ⊕ 0 ⊕ 1 ⊕ 1 ⊕ 11
1b1 ⊕ b5 ⊕ b6 ⊕ b7 ⊕ b0 ⊕ c11 ⊕ 0 ⊕ 1 ⊕ 1 ⊕ 0 ⊕ 10
2b2 ⊕ b6 ⊕ b7 ⊕ b0 ⊕ b1 ⊕ c20 ⊕ 1 ⊕ 1 ⊕ 0 ⊕ 1 ⊕ 01
3b3 ⊕ b7 ⊕ b0 ⊕ b1 ⊕ b2 ⊕ c31 ⊕ 1 ⊕ 0 ⊕ 1 ⊕ 0 ⊕ 01
4b4 ⊕ b0 ⊕ b1 ⊕ b2 ⊕ b3 ⊕ c40 ⊕ 0 ⊕ 1 ⊕ 0 ⊕ 1 ⊕ 00
5b5 ⊕ b1 ⊕ b2 ⊕ b3 ⊕ b4 ⊕ c50 ⊕ 1 ⊕ 0 ⊕ 1 ⊕ 0 ⊕ 11
6b6 ⊕ b2 ⊕ b3 ⊕ b4 ⊕ b5 ⊕ c61 ⊕ 0 ⊕ 1 ⊕ 0 ⊕ 0 ⊕ 11
7b7 ⊕ b3 ⊕ b4 ⊕ b5 ⊕ b6 ⊕ c71 ⊕ 1 ⊕ 0 ⊕ 0 ⊕ 1 ⊕ 01

把結果從 bit 7 到 bit 0 依序寫出來,得到 11101101₂ = 0xED。

輸入為 0x00 時,第一階段依規範取 0x00,仿射轉換後得到 0x63。

四、State 轉換範例

以下以一個 4 × 4 State 為例。列索引 r 從上往下編為 0~3,欄索引 c 從左往右編為 0~3。每格存放一個十六進位 byte。

輸入 State

r \ c0123
019A09AE9
13DF4C6F8
2E3E28D48
3BE2B2A08

逐格查 SBOX,再寫回相同位置。 左上角 s[0,0] = 0x19,用高半位元 1 選 SBOX 的列、低半位元 9 選欄,得到 0xD4,寫入 s′[0,0]。

右邊一格 s[0,1] = 0xA0,查 SBOX 的 A 列、0 欄,得到 0xE0,寫入 s′[0,1]。第一列另外兩格同樣查得 9A → B8、E9 → 1E,所以整列由 19 A0 9A E9 變成 D4 E0 B8 1E。其餘三列依相同方式處理。

輸出 State

r \ c0123
0D4E0B81E
127BFB441
211985D52
3AEF1E530

五、參考資料

NIST FIPS 197(2023 更新版),§4.2、§5.1.1、公式 (5.2)–(5.4) 與表 4。

AES 加密演算法介紹(二):基本概念、關鍵名詞與計算符號

一、前言

AES 分為 AES-128、AES-192、AES-256 三種規格,主要差異在原始金鑰長度(Key Size)、運算輪數(Nr)與金鑰展開規則。無論使用哪一種 AES,Block Size 都固定為 128 bits(16 Bytes)。

AES Core 內部將資料表示為 4 × 4 Bytes 的 State Matrix,再藉由一系列 Transformation 完成加密與解密。本系列以 FIPS 197 為主要依據,說明核心演算法、公式符號與可追蹤的計算範例。

二、AES-128/192/256 規格比較

項目AES-128AES-192AES-256
Block Size128 bits128 bits128 bits
Key Size128 bits192 bits256 bits
Nb(State Words)444
Nk(Key Words)468
Nr(Rounds)101214
State Size16 Bytes16 Bytes16 Bytes
Round Key Size16 Bytes16 Bytes16 Bytes
Round Key 數量111315
Key Schedule44 Words52 Words60 Words

Nb:State 包含的 32-bit Words 數量,AES 固定為 4
Nk:原始 Key 包含的 32-bit Words 數量
Nr:AES 標準規定的加/解密輪數。

重點:Cipher 在第一輪前先執行 Initial AddRoundKey,因此總共需要 Nr + 1 組 Round Keys;最前面的 Initial AddRoundKey 不計入 Nr。

NIST 對照:FIPS 197 §5、Table 3。

三、關鍵名詞

名詞說明
Bit最小的二進位資料單位,數值為 0 或 1。
Byte8 bits;可表示 0x00~0xFF 共 256 種值。
Word32 bits = 4 Bytes。
BlockAES 單次加密/解密的資料區塊,固定 128 bits = 16 Bytes。
StateAES Core 的內部運算狀態,以 4 × 4 Bytes 矩陣表示。
Original KeyAES 加解密使用的原始金鑰。
Key ScheduleKeyExpansion 產生的完整 Word 序列。
Round Key從 Key Schedule 取出 4 個連續 Words,固定 16 Bytes。
RoundAES 加密或解密的一輪運算。
Transformation對 State 執行的資料轉換運算。
S-BoxSubBytes 使用的非線性位元組替換表。
RconKey Expansion 使用的固定輪常數。
GF(2⁸)含 256 個元素的有限體,供 AES 特定數學運算使用。

Block vs State:Block 表示單次處理的資料長度;State 表示這 16 Bytes 在 AES Core 中的運算形式。兩者大小相同,但定義不同。

四、State Matrix 的資料排列

AES 的輸入是連續 16 Bytes,進入 AES Core 後採 Column-major(欄優先)順序載入 4 × 4 State Matrix。

Input Block = 00 11 22 33 44 55 66 77 88 99 AA BB CC DD EE FF
Row / ColumnCol 0Col 1Col 2Col 3
Row 0004488CC
Row 1115599DD
Row 22266AAEE
Row 33377BBFF
s[r,c] = in[r + 4c]r = 0~3;c = 0~3;各個索引自 0 開始

符號說明:s[r,c] 是第 r 列、第 c 欄的 State Byte;in[i] 是輸入 Block 的第 i 個 Byte;r 為 Row Index;c 為 Column Index。

例如:s[1,2] = in[1 + 4 × 2] = in[9] = 0x99

NIST 對照:FIPS 197 §3.4,Equations (3.6)、(3.7),Figure 1。

五、常用計算符號與索引

符號/寫法名稱定義
s[r,c]State Element運算前第 r 列、第 c 欄的 Byte。
s′[r,c]Updated State運算後對應位置的 Byte。
w[i]WordKey Schedule 的第 i 個 32-bit Word。
NkKey Words原始 Key 的 Word 數量。
NbBlock WordsState 的 Word 數量(固定 4)。
NrRoundsAES 的加/解密輪數。
iWord Index展開金鑰時的 Word 索引。
r / cRow / ColumnState 的列/欄索引,0~3。
jConstant Index依上下文使用,例如 Rcon[j]。
⊕XOR互斥或;相同 bit 為 0,不同 bit 為 1。
•Field MultiplyGF(2⁸) 有限體乘法。
modModulo取模/取餘數,依運算對象解讀。
b⁻¹InverseGF(2⁸) 中非零元素 b 的乘法反元素。
b̃Intermediate ByteS-Box 仿射轉換前的中間 Byte。
Rcon[j]Round ConstantKey Expansion 中第 j 個輪常數。

避免誤解:索引 i、r、c 通常從 0 開始;Rcon[j] 的 j 從 1 開始。符號 • 是有限體乘法,不是一般整數乘法。

六、AES 使用的基本數學運算

XOR(Exclusive-OR)

XOR 對應位置的 bit 執行互斥或:兩個 bit 不同時輸出 1,相同時輸出 0。

0x53 ⊕ 0xCA = 0x99

XOR 具有自反性,因此 AddRoundKey 可以使用同一個 Round Key 再 XOR 一次還原資料:

(A ⊕ K) ⊕ K = A

GF(2⁸) 有限體運算

AES 將一個 Byte 視為 GF(2⁸) 的元素,並可用二進位係數多項式表示,其中每個係數 b₀~b₇ 都只能是 0 或 1。

b(x) = b₇x⁷ + b₆x⁶ + ··· + b₁x + b₀

例如,0x53 = 01010011₂,其中第 6、4、1、0 位元為 1:

0x53 ↔ x⁶ + x⁴ + x + 1

AES 在 GF(2⁸) 乘法中使用固定不可約多項式:

m(x) = x⁸ + x⁴ + x³ + x + 1 ↔ 0x11B
  • 加法/減法:同次項係數使用 XOR。
  • 乘法:多項式相乘後,對 m(x) 進行模約簡。
  • 乘法反元素:對非零 b,尋找滿足 b • b⁻¹ = 0x01 的元素。

GF(2⁸) 乘法主要用於 SubBytes 的 S-Box 定義、MixColumns 及 Rcon 的生成;並非每個 AES Transformation 都要執行有限體乘法。

NIST 對照:FIPS 197 §4.1~§4.4。

(三)Hexadecimal(十六進位)

AES 規範與測試資料常使用十六進位數值表示 Byte:

表示方式相同數值
Binary01010011
Hex0x53
Decimal83
NIST Byte Notation{53}

一個 Hex 字元對應 4 bits,因此兩個 Hex 字元代表 1 Byte。後續數值驗算原則上使用 Hex,必要時再展開為 Binary 解釋 XOR、位移或 GF(2⁸) 運算。

七、AES Core 的主要演算法

AES Core 可以區分為三個主要演算法:

演算法功能
KeyExpansion()將 Original Key 展開為完整 Key Schedule。
Cipher()依照 Round Keys 與 State 執行加密流程。
InvCipher()依照 Round Keys 與 State 執行解密流程。

其中,Cipher() 主要使用以下四個 Transformation:

Transformation主要功能
SubBytes()使用 S-Box 逐 Byte 進行非線性替換。
ShiftRows()依列索引對 State 各列執行循環位移。
MixColumns()使用固定矩陣混合每一欄資料。
AddRoundKey()讓 State 與對應 Round Key 逐 Byte XOR。

KeyExpansion() 負責提供 AddRoundKey() 所需的 Round Keys;Cipher() 依照 Initial Round、Main Rounds、Final Round 的規則決定各項 Transformation 的順序。

架構提醒:Cipher() 與 InvCipher() 分別是加密與解密流程,不是依序接續執行的兩個階段。

八、本章重點整理

  • AES-128、AES-192、AES-256 的差異主要在 Key Size、Nr 與 Key Expansion 規則。
  • AES 的 Block Size 與 State Size 均固定為 128 bits(16 Bytes)。
  • State 使用 4 × 4 Bytes 的 Column-major 排列,索引 r、c 均由 0 開始。
  • Original Key 與 Round Key 不同;每組 Round Key 都固定為 4 Words(16 Bytes)。
  • KeyExpansion() 產生 Round Keys,供 Cipher() 與 InvCipher() 使用。
  • AES 使用 XOR、GF(2⁸) 乘法及模約簡;不能將有限體乘法當成一般整數乘法。

九、參考資料

NIST, Advanced Encryption Standard (AES), FIPS 197, Updated May 9, 2023.

NIST FIPS 197 官方文件(PDF)

本章對照:§2 Definitions、§3 Notation and Conventions、§4 Mathematical Preliminaries、§5 Algorithm Specifications、Table 3、Figure 1。

2026年8月2日星期日

AES 加密演算法介紹(一):基本概念、規格與常見模式

 AES (Advanced Encryption Standard)

一、AES 是什麼

  • 對稱式加密
  • 區塊加密
  • 加密與解密使用同一把 Key
  • AES 本身不是 Hash,也不是 MAC
  • AES 本身只提供區塊加密能力,實際應用還需要搭配運作模式

     AES 是一種對稱式區塊加密演算法,主要用途是將可以直接閱讀的明文(Plaintext)轉換成無法直接理解的密文(Ciphertext)。持有正確金鑰的一方,才能再將密文解密回原始明文。

二、基本規格

  •     主要有以下三種,差異為金鑰長度及計算幾輪

AES 類型
Key 長度
Key 大小
Round 數
AES-128
128 bits
16 bytes
10
AES-192
192 bits
24 bytes
12
AES-256
256 bits
32 bytes
14

    •     無論使用 AES-128、AES-192 或 AES-256,AES 的區塊大小(Block Size)都固定為 128 bits,也就是 16 bytes。
    • AES-128、AES-192 與 AES-256 中的數字代表的是 Key Size,不是 Block Size。

    三、AES 核心輸入與輸出介面

    加密 AES_Encrypt(Key, PlaintextBlock) → CiphertextBlock

    解密 AES_Decrypt(Key, CiphertextBlock) → PlaintextBlock

    PlaintextBlock:16 bytes
    CiphertextBlock:16 bytes
    Key:16、24 或 32 bytes

     

    四、為什麼需要運作模式

    當資料長度為 100 bytes 時,AES Core 一次只能處理 16 bytes,所以需要規則決定

      • 如何分割資料
      • Block 之間如何連接
      • 是否需要 Padding
      • 是否需要 IV 或 Nonce
      • 是否驗證資料完整性
    五、AES 的五種常見模式

    模式
      完整性/認證   IV/Nonce/Counter    明文 Padding
    ECB
    否               不需要通常需要 
    CBC
    否               IV通常需要 
    CTR
    否               Counter Block不需要   
    GCM
      是,使用 Tag       IV/Nonce不需要   
    CCM
    是,使用 Tag       Nonce不需要   

        補充:Counter Block 通常由 Nonce 與遞增的 Counter 組成,詳細結構將於第五篇介紹。

    六、AES 的常見用途

    • HTTPS/TLS
    • VPN
    • Wi-Fi
    • 硬碟加密
    • 加密韌體映像
    • 安全韌體更新
    • 嵌入式系統
    • PSA Crypto
    • 金鑰儲存與資料保護
    七、小結

    AES 是一種對稱式區塊加密演算法,每次固定處理一個 128-bit,也就是 16-byte 的資料區塊。AES 支援 128、192 與 256-bit 三種金鑰長度,分別執行 10、12 與 14 輪核心運算。由於 AES Core 本身一次只能處理一個 Block,因此實際處理多個資料區塊或任意長度資料時,還需要搭配 ECB、CBC、CTR、GCM 或 CCM 等運作模式。下一篇將進一步介紹 AES Core 內部的主要運算流程。





    打賞按讚