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

 

2-6 Feistel 密碼演算法

內容:

  • 2-6 Feistel 密碼演算法

    • 2-6-1 Feistel 系統概念

    • 2-6-2 Feistel 系統架構

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

2-6-1 Feistel 系統概念

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

  • If AB = C 則:

BC = A  and  AC = B

  • 00 = 0, 01 = 1, 10 = 1, 11 = 0,

  • A0 = A

驗證:

If  A = 11011010B = 10110111

11011010

10110111

AB = 01101101 = C

then

10110111

01101101

BC = 11011010 = A

and

11011010

01101101

AC = 10110111 = B

2-7 Feistel 加密法』(Feistel Cipher)的基本架構,它兩個重要的特點如下:

  • 加密與解密都是相同的編碼器,亦是,明文經由編碼器處理後,則輸出為密文;密文再經過編碼器處理後,即還原明文。

  • 不受取代裝置 F 函數的影響,亦是,無論 F 函數為任何功能,都不會影響編碼器還原明文的功能。

  • F 函數取有取代加密的功能,越複雜則明文與密文之間的複雜度越高,亦是,越 F 函數越複雜,由密文猜測出明文越困難。

  • 它將所欲編碼的資料(64 bits)分割成兩群:右邊(R32 bits)與左邊(L32 bits),再交叉換位,因此,也具有換位加密的功能。

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

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

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

明文輸入:M = {LEi || REi}

LEi+1 = REi                              式子 (1)

REi+1 = LEi F(Ki+1REi)                式子 (2)

密文輸出:C = {REi+1 || LEi+1} = { LEi F(Ki+1REi) || REi }

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

  • 解密推演如下:( 2-6 右邊處理)

密文輸入:C = {LDi || RDi}

LDi+1 = RDi                              式子 (3)

RDi+1 = LDi F(Ki+1RDi)                 式子 (4)

LDi = LEi+1                              式子 (5)

RDi = REi+1                              式子 (6)

Feistel 解碼器輸出為:                  

LDi+1 = RDi                              (引用式子 (3)

= LEi+1 = REi                  (引用式子 (6) (1)

RDi+1 = LDi F(Ki+1RDi)                  (引用式子 (4)

= REi+1 F(Ki+1LEi+1)        (引用式子 (5) (6)

= LEiF(Ki+1REi) F(Ki+1REi) (引用式子 (2) (1)

= LEi 0                       (因為:A A = 0

= LEi                           (因為:A 0 = A

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

  • 驗證 Feistel 編碼器功能

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

LEi = 4REi = 8

REi+1 = LEi F(REi, Ki)

=4 8 6 = A

LEi+1 = REi = 8

則密文為:C = {REi+1, LEi+1} = {A, 8}

解密過程為:

LDi = ARDi = 8

LDi+1 = RDi = 8

RDi+1 = LDi F(RDi, Ki)

=A 8 6 = 4

則明文為:M = {RDi+1, LDi+1} = {4, 8}

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

2-6-2 Feistel 系統架構

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

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

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

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

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

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

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

  • 區塊大小:加密較大區塊的資料,可增加密文的複雜度,但也會增加解密的時間。新的演算法多半提供 128 192 bitsDES 64 bits),甚至可以使用變動長度來加密。

  • 初始排列:一般初始排列的功能是為了配合編碼處理,較常用的做法是將明文區塊區分為若干個群組(DES 為兩群組),由這些群組作為重新排列的對象;至於如何將明文區塊劃分為群組的選取方法,各種演算法皆有其獨特的技巧。

  • 排列格式:一般情況,排列格式即是將上一回合加密的結果,重新排列(DES 為左右交叉排列)後再給予本次加密(重複性),如此更可增加演算法的複雜度。

  • 編碼函數:這是各種演算法的精髓所在,它是將每個輸入位元以取代方式轉換成其它位元,而在替代過程當中,每一位元也會與子鑰匙的相對應位元之間,做一些邏輯運算(如 XOR AND)。如何設計它,即是許多延伸密碼系統的關鍵因素。

  • 鑰匙長度:較長的鑰匙較為安全(抗拒暴力攻擊),但相對的,演算法的複雜度就越高,DES 所採用的 56 位元長度,其安全性已岌岌可危,128192256 位元長度漸受青睞。

  • 子鑰匙的數量:由加密鑰匙(或稱主鑰匙)所計算產生子鑰匙數目的多寡,這牽涉到編碼處理的次數,基本上,每回合的編碼處理都需要一組子鑰匙(一把或多把)。

  • 重覆回合次數:重覆次數越多,所產生的密文也就越複雜(強度也就越高),但相對增加解碼時間。

  • 輸出轉換:一般都是『初始轉換』的反函數,也就是,將相對應的位元回覆原來的位置。

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

 

 

主講人:粘添壽博士

 

資訊與網路安全技術