ShiftRows

• 一種行移位操作，用於增加密文的擴散性。
• 對狀態矩陣的每一行進行循環左移。
• 移動的位數隨行數的增加而增加：
  • 第一行保持不變。
  • 第二行左移1個位置。
  • 第三行左移2個位置。
  • 第四行左移3個位置。
• 在加密時左移，所以解密時要右移。

(示意圖如下:)

MixColumns

混淆與擴散：
混淆（Confusion）:

• 讓密文與密鑰之間的關聯變得複雜，使得透過觀察密文難以推測出密鑰。
  擴散（Diffusion）:
• 加密過程中讓輸入的每個位元影響到輸出的多個位元，從而使明文和密文的關聯變得複雜。
  AES中的混淆: S-box替換
  AES中的擴散: ShiftRows和MixColumns步驟

Avalanche effect(雪崩效應)：

• 密碼演算法的理想特性
• 輸入稍微改變，輸出就會顯著改變。
• 嚴格雪崩準則( SAC ):
  • 如果在輸入中有一個位元被翻轉，那麼每個輸出位元有50%的機率會改變。

Diffusion through Permutation

https://cryptohack.org/courses/symmetric/aes5/

題目摘要:

簡單介紹了混淆與擴散、雪崩效應以及ShiftRows和MixColumns的步驟。

題意:

完成inv_shift_rows後，對state執行inv_mix_columns，再進行inv_shift_rows，最後轉換為字節格式即可獲得flag。

我將程式碼分成兩部分，加密的部分題目已經給全了。
解密的部分， inv_shift_rows(s) 函式以及輸出的部份我們則要自己完善。
加密:

def shift_rows(s):
    # 執行AES的ShiftRows操作
    # 第二行左移1位
    s[0][1], s[1][1], s[2][1], s[3][1] = s[1][1], s[2][1], s[3][1], s[0][1]
    # 第三行左移2位
    s[0][2], s[1][2], s[2][2], s[3][2] = s[2][2], s[3][2], s[0][2], s[1][2]
    # 第四行左移3位
    s[0][3], s[1][3], s[2][3], s[3][3] = s[3][3], s[0][3], s[1][3], s[2][3]

# 在GF(2^8)上的乘法運算
# 如果a的最高位是1，左移後與0x1B異或；否則左移
xtime = lambda a: (((a << 1) ^ 0x1B) & 0xFF) if (a & 0x80) else (a << 1)

def mix_single_column(a):
    # 對單列進行MixColumns操作
    # 參見 The Design of Rijndael 的4.1.2節

    # 計算列中所有元素的異或和
    t = a[0] ^ a[1] ^ a[2] ^ a[3]
    u = a[0]  # 保存a[0]的原始值

    # 更新每個元素
    a[0] ^= t ^ xtime(a[0] ^ a[1])
    a[1] ^= t ^ xtime(a[1] ^ a[2])
    a[2] ^= t ^ xtime(a[2] ^ a[3])
    a[3] ^= t ^ xtime(a[3] ^ u)  # 這裡使用保存的a[0]值

def mix_columns(s):
    # 對整個狀態矩陣s執行MixColumns操作
    for i in range(4):
        mix_single_column(s[i])  # 對每一列應用mix_single_column

解密

def inv_shift_rows(s):
    # 執行AES的逆ShiftRows操作
    # 第二行右移1位
    s[1][1], s[2][1], s[3][1], s[0][1] = s[0][1], s[1][1], s[2][1], s[3][1]
    # 第三行右移2位
    s[2][2], s[3][2], s[0][2], s[1][2] = s[0][2], s[1][2], s[2][2], s[3][2] 
    # 第四行右移3位
    s[3][3], s[0][3], s[1][3], s[2][3] = s[0][3], s[1][3], s[2][3], s[3][3]

# 在GF(2^8)上的乘法運算
# 如果a的最高位是1，左移後與0x1B異或；否則左移
xtime = lambda a: (((a << 1) ^ 0x1B) & 0xFF) if (a & 0x80) else (a << 1)
    
def inv_mix_columns(s):
    # 執行AES的逆MixColumns操作
    # 參見 The Design of Rijndael 的4.1.3節
    for i in range(4):
        # 對每列進行預處理
        u = xtime(xtime(s[i][0] ^ s[i][2]))  # 計算 2 * 2 * (s[i][0] + s[i][2])
        v = xtime(xtime(s[i][1] ^ s[i][3]))  # 計算 2 * 2 * (s[i][1] + s[i][3])
        # 更新列中的每個元素
        s[i][0] ^= u
        s[i][1] ^= v
        s[i][2] ^= u
        s[i][3] ^= v
    mix_columns(s)
    
 
# 初始狀態矩陣
state = [
    [108, 106, 71, 86],
    [96, 62, 38, 72],
    [42, 184, 92, 209],
    [94, 79, 8, 54],
]

if(True):
    flag = ""
    inv_mix_columns(state)
    inv_shift_rows(state)
    # 將狀態矩陣轉換為字符串
    for i in state:
        for j in i:
           flag += chr(j)  # 將每個數值轉換為對應的ASCII字符
    print(flag)

crypto{d1ffUs3R}

參考資料:

wiki:

• Rijndael MixColumns : https://en.wikipedia.org/wiki/Rijndael_MixColumns
• AES: https://zh.wikipedia.org/zh-tw/%E9%AB%98%E7%BA%A7%E5%8A%A0%E5%AF%86%E6%A0%87%E5%87%86
• Avalanche effect: https://en.wikipedia.org/wiki/Avalanche_effect
  AES進階加密標準:
  https://ithelp.ithome.com.tw/articles/10289999?sc=iThelpR
  題目附的參考文章: https://www.samiam.org/mix-column.html

後話:

今天嘗試理解MixColumns的具體步驟，只能說，似懂非懂。