Feistel 密碼演算法

資訊與網路安全技術：第二章傳統秘密鑰匙系統上一頁 下一頁

2-6 Feistel 密碼演算法

內容：

2-6 Feistel 密碼演算法

2-6-1 Feistel 系統概念

2-6-2 Feistel 系統架構

2-7 傳統密碼系統摘要

2-6-1 Feistel 系統概念

Feistel 是將乘積加密法導入區塊加密法的先趨，到目前為止，許多密碼系統還是引用 Feistel 的基本架構。他的基本原理是利用 XOR(⊕)的的基本特性，如下：

If A⊕B = C 則：

B⊕C = A and A⊕C = B

0⊕0 = 0, 0⊕1 = 1, 1⊕0 = 1, 1⊕1 = 0,
A⊕0 = A

驗證：

If A = 11011010，B = 10110111

11011010

10110111

A⊕B = 01101101 = C

then

10110111

01101101

B⊕C = 11011010 = A

and

11011010

01101101

A⊕C = 10110111 = B

圖 2-7 為『Feistel 加密法』（Feistel Cipher）的基本架構，它兩個重要的特點如下：

加密與解密都是相同的編碼器，亦是，明文經由編碼器處理後，則輸出為密文；密文再經過編碼器處理後，即還原明文。
不受取代裝置 F 函數的影響，亦是，無論 F 函數為任何功能，都不會影響編碼器還原明文的功能。
F 函數取有取代加密的功能，越複雜則明文與密文之間的複雜度越高，亦是，越 F 函數越複雜，由密文猜測出明文越困難。
它將所欲編碼的資料(64 bits)分割成兩群：右邊(R，32 bits)與左邊(L，32 bits)，再交叉換位，因此，也具有換位加密的功能。

圖 2-6 Feistel 密碼系統的基本觀念

圖 2-6 僅使用一支鑰匙加密或解密處理，多支鑰匙連續處理也如同此道理，但輸出轉換僅會在最後支鑰匙才會出現。左邊是加密編碼處理，它將 n 位元的明文區塊（一般都 64 bits）分割成為左右兩個子區塊（n/2 位元，32 位元）：LE_i和 RE_i（{LE_i || RE_i}，其中 || 符號表示排列的意思）；再使用鑰匙K_i+1對左右子區塊加密，而得到另外兩個子區塊LE_i+1和 RE_i+1。

加密後推演如下：(圖 2-6 左邊處理)

明文輸入：M = {LE_i || RE_i}

LE_i+1 = RE_i 式子 (1)

RE_i+1 = LE_i⊕ F(K_i+1，RE_i) 式子 (2)

密文輸出：C = {RE_i+1 || LE_i+1} = { LE_i⊕ F(K_i+1，RE_i) || RE_i }

經過該支鑰匙加密編碼後所得到為 {LE_i+1 || RE_i+1}，如再經過輸出轉換（左右區塊交換位置），則密文輸出為 C = {RE_i+1 || LE_i+1}。上述中函數 f(K_i+1，RE_i) 表示 R_i使用鑰匙 K_i+1加密，F() 函數表示一個特殊處理的取代加密器，然而取代函數是依照鑰匙來變化。另外，⊕ 符號表示 Module-2 的加法（XOR 的運算）。

解密推演如下：(圖 2-6 右邊處理)

密文輸入：C = {LD_i || RD_i}

LD_i+1 = RD_i 式子 (3)

RD_i+1 = LD_i⊕ F(K_i+1，RD_i) 式子 (4)

LD_i = LE_i+1 式子 (5)

RD_i = RE_i+1 式子 (6)

則 Feistel 解碼器輸出為：

LD_i+1 = RD_i （引用式子 (3)）

= LE_i+1 = RE_i （引用式子 (6) 與 (1)）

RD_i+1 = LD_i⊕ F(K_i+1，RD_i) （引用式子 (4)）

= RE_i+1⊕ F(K_i+1，LE_i+1) （引用式子 (5) 與 (6)）

= LE_i⊕F(K_i+1，RE_i)⊕ F(K_i+1，RE_i) （引用式子 (2) 與 (1)）

= LE_i⊕ 0 （因為：A ⊕ A = 0）

= LE_i （因為：A ⊕ 0 = A）

經過解密編碼後輸出為 {RE_i || LE_i}，再經過輸出轉換得到 M = {LE_i || RE_i}，其與圖 2-7 左邊明輸入相同，因此，Feistel 編碼系統具有加密與反向解密的功能。另一個更直得注意的重點是，編碼過程中，不受加密鑰匙與 F() 函數所影響。有就是說，不論鑰匙是何值，編碼函數 F 為何，Feistel 編碼皆具有加密與反向解密的功能。如以『取代加密法』與『換位加密法』概念而言，圖 2-7 中將明文分割成左右兩段並交換處理，即是『換位』；另外，經由 F(K_i+1，RE_i) 函數處理，即是『取代』處理。

驗證 Feistel 編碼器功能

我們用一個範例來驗證 Feistel 架構是否可行。假設 M = {4, 8}、k_i = 6、F = ⊕。則加密過程為：

LE_i = 4、RE_i = 8

RE_i+1 = LE_i⊕ F(RE_i, K_i)

=4 ⊕ 8 ⊕ 6 = A

LE_i+1 = RE_i = 8

則密文為：C = {RE_i+1, LE_i+1} = {A, 8}

解密過程為：

LD_i = A、RD_i = 8

LD_i+1 = RD_i = 8

RD_i+1 = LD_i⊕ F(RD_i, K_i)

=A ⊕ 8 ⊕ 6 = 4

則明文為：M = {RD_i+1, LD_i+1} = {4, 8}

圖 2-7 驗證 Feistel 具有加密/解密功能

2-6-2 Feistel 系統架構

Feistel 的構想是如能利用圖 2-7 的加密程序，重複運算幾次，並且每一次都給予不同的子鑰匙，便能完全打散資料的關聯性，達到複雜加密的效果。圖 2-8 為 Feistel 密碼系統的架構圖，我們將重複加密的次數（假設 16 次），以相同的加密方塊連結畫出來；如此，就可以看出明文是經過多個加密方塊連續的運算出密文來；值得一提的是，加密與解密均使用同樣的演算法，但子鑰匙分配的次序顛倒。

圖 2-7-1 Feistel 密碼系統架構

Feistel 編碼系統的運作程序是通訊雙方皆擁有一把相同的秘密鑰匙 K，再利用某一鑰匙產生函數，將此鑰匙製作出多把子鑰匙（K_i，i=1, 2, .., 16）。傳送端將訊息利用子鑰匙由 K₁, K₂, …., k₁₆，連續編碼後再經由輸出轉換產生密文，發送給接收端。接收端收到密文後，也將秘密鑰匙 K，經過相同的鑰匙產生函數，製造出相同的子鑰匙序列，利用相同的 Feistel 編碼器，將子鑰匙序列倒過來，由 K₁₆, K₁₅, …, k₁，連續編碼後再經過輸出轉換解碼回原明文。

2-7 傳統密碼系統的摘要

自從 Feistel 發表取代與重排所建立的『乘積加密法』之後，20 多年來許多密碼學專家，藉其基本架構發展出各種形式的加密演算法，譬如 DES、IDEA 等等。圖 3-1 為秘密鑰匙演算法的基本模型，其運作程序是：首先將輸入的明文區塊經過『初始排列』，使其適合接下來的加密運算；接著，為了增強明文與密文之間的複雜度（擴散能力），將明文經過多次的重覆排列（如 DES 為 16 次排列），不同的演算法都有各自的排列格式。另一方面，為了增加密文與鑰匙之間的複雜度（混淆能力），首先將加密鑰匙轉換成若干個子鑰匙（如 DES 為 16 把子鑰匙），每一子鑰匙作為加密函數的關鍵性輸入，加密函數是將明文區段與子鑰匙之間，做某些邏輯運作與替代轉換的功能，也是加密演算法最主要的精髓所在，經由許多密碼學專家研究出各種不同的操作方法，延伸出來許多加密驗算法的規範。然而，明文（或稱演算中的密文）重新排列與加密函數混合重覆執行多次，每次輸入不同的子鑰匙，來增加『混淆』與『擴充』的能力。密文經過多次的『取代-移位』之後，再經過最後的『輸出排列』使其回復原來明文的格式，也就是說，『輸出排列』是『初始排列』的反轉換函數。

圖 2-8 秘密鑰匙演算法的基本模型

在實作或研究秘密鑰匙演算法方面，可由圖 2-8 的基本模型中設計及更改各種參數，來增加演算法的複雜度（或強度），相關參數如下：

區塊大小：加密較大區塊的資料，可增加密文的複雜度，但也會增加解密的時間。新的演算法多半提供 128 或 192 bits（DES 為 64 bits），甚至可以使用變動長度來加密。
初始排列：一般初始排列的功能是為了配合編碼處理，較常用的做法是將明文區塊區分為若干個群組（DES 為兩群組），由這些群組作為重新排列的對象；至於如何將明文區塊劃分為群組的選取方法，各種演算法皆有其獨特的技巧。
排列格式：一般情況，排列格式即是將上一回合加密的結果，重新排列（DES 為左右交叉排列）後再給予本次加密（重複性），如此更可增加演算法的複雜度。
編碼函數：這是各種演算法的精髓所在，它是將每個輸入位元以取代方式轉換成其它位元，而在替代過程當中，每一位元也會與子鑰匙的相對應位元之間，做一些邏輯運算（如 XOR 或 AND）。如何設計它，即是許多延伸密碼系統的關鍵因素。
鑰匙長度：較長的鑰匙較為安全（抗拒暴力攻擊），但相對的，演算法的複雜度就越高，DES 所採用的 56 位元長度，其安全性已岌岌可危，128、192、256 位元長度漸受青睞。
子鑰匙的數量：由加密鑰匙（或稱主鑰匙）所計算產生子鑰匙數目的多寡，這牽涉到編碼處理的次數，基本上，每回合的編碼處理都需要一組子鑰匙（一把或多把）。
重覆回合次數：重覆次數越多，所產生的密文也就越複雜（強度也就越高），但相對增加解碼時間。
輸出轉換：一般都是『初始轉換』的反函數，也就是，將相對應的位元回覆原來的位置。

以上是秘密鑰匙演算法的基本參數，隨著不同的需求，可由基本模型中演變出各式各樣的演算法。

翻轉工作室：粘添壽

資訊與網路安全技術

第一章安全性資訊系統簡介
第二章傳統秘密鑰匙系統
- 2-1 密碼學概論
- 2-2 傳統密碼學的基本原理
- 2-3 換位加密法
- 2-4 取代加密法
- 2-5 區塊加密法的基本原理
- 2-6 Feistel 密碼演算法
- 2-7 傳統密碼系統的摘要
- 2-8 DES 密碼系統
- 2-9 DES 操作模式
- 2-10 AES 密碼系統
- 2-11 Triple DES 密碼系統
- 2-12 密碼系統的安全性
- 2-13 密碼破解技巧

翻轉電子書系列：