退出 DES,進入 Rijndael-關於AES演算法 |
|
hcker
中階會員 ![]() ![]() ![]() 發表:95 回覆:118 積分:62 註冊:2003-02-09 發送簡訊給我 |
//看到前面的AES的演算法,找了個比較好的資料,給大家看看
//不知道發哪里好,就貼這裏了,大大別罵我…… 自 20 世紀 70 年代以來一直廣泛使用的“資料加密標準”(DES) 日益顯出衰老的痕跡,而一種新的演算法 -- Rijndael -- 正順利地逐漸變成新標準。這裏,Larry Loeb 詳細說明了每一種演算法,並提供了關於為什麼會發生這種變化的內幕資訊。 DES 演算法是全世界最廣泛使用的加密演算法。最近,就在 2000 年 10 月,它在其初期就取得的硬體方面的優勢已經阻礙了其發展,作為政府加密技術的基礎,它已由“高級加密標準”(AES) 中包含的另一種加密演算法代替了。AES 是指定的標準密碼系統,未來將由政府和銀行業用戶使用。AES 用來實際編碼資料的加密演算法與以前的 DES 標準不同。我們將討論這是如何發生的,以及 AES 中的 Rijndael 演算法是如何取代 DES 的演算法的。
DES:首要步驟
1973 年 5 月 15 日,美國國家標準局 (NBS) 在“聯邦註冊”上發佈了一條通知,徵求密碼演算法,用於在傳輸和存儲期間保護資料。IBM 提交了一個候選演算法,它是 IBM 內部開發的,名為 LUCIFER。在美國國家安全局 (NSA) 的“指導”下完成了演算法評估之後,在 1977 年 7 月 15 日,NBS 採納了 LUCIFER 演算法的修正版作為新的資料加密標準。這導致了聯邦資訊處理標準 (FIPS) 46(以後更新成 FIPS 46-3)的產生(請參閱參考資料),它描述了 DES 和當前 DES 3 標準的用法。
除政府以外,銀行業是加密的最大用戶。所有用普通電話線處理業務的電子匯款 (EFT) 和自動取款機 (ATM) 都必須加密其財務資料,使外表安全。大規模銀行業的標準是由美國國家標準學會 (ANSI) 制定的。1980 年採用的 ANSI X3.92 指定了要使用 DES 演算法。現在,ATM 仍例行公事地使用著 DES。
DES 的工作方式:可怕的細節
DES 將消息分成 64 位元(即 16 個十六進位數)一組進行加密。DES 使用“密鑰”進行加密,從符號的角度來看,“密鑰”的長度是 16 個十六進位數(或 64 位)。但是,由於某些原因(可能是因為 NSA 給 NBS 的“指引”),DES 演算法中每逢第 8 位就被忽略。這造成密鑰的實際大小變成 56 位。編碼系統對“強行”或“野蠻”攻擊的抵抗力與其密鑰空間或者系統可能有多少密鑰有直接關係。使用的位數越多轉換出的密鑰也越多。密鑰越多,就意味著強行攻擊中計算密鑰空間中可能的密鑰範圍所需的時間就越長。從總長度中切除 8 位就會在很大程度上限制了密鑰空間,這樣系統就更容易受到破壞。
DES 是塊加密演算法。這表示它處理特定大小的純文本塊(通常是 64 位),然後返回相同大小的密碼塊。這樣,64 位(每位不是 0 就是 1)有 264 種可能排列,DES 將生成其中的一種排列。每個 64 位的塊都被分成 L、R 左右兩塊,每塊 32 位。
DES 演算法使用以下步驟:
1. 創建 16 個子密鑰,每個長度是 48 位。根據指定的順序或“表”置換 64 位的密鑰。如果表中的第一項是 "27",這表示原始密鑰 K 中的第 27 位將變成置換後的密鑰 K+ 的第一位。如果表的第二項是 36,則這表示原始密鑰中的第 36 位將變成置換後密鑰的第二位,以此類推。這是一個線性替換方法,它創建了一種線性排列。置換後的密鑰中只出現了原始密鑰中的 56 位。
接著,將這個密鑰分成左右兩半,C0 和 D0,每一半 28 位。定義了 C0 和 D0 之後,創建 16 個 Cn 和 Dn 塊,其中 1<=n<=16。每一對 Cn 和 Dn 塊都通過使用標識“左移位元”的表分別從前一對 Cn-1 和 Dn-1 形成,n = 1, 2, ..., 16,而“左移位”表說明了要對哪一位進行操作。在所有情況下,單一左移位表示這些位輪流向左移動一個位置。在一次左移位之後,28 個位置中的這些位分別是以前的第 2、3……28 位。
通過將另一個置換表應用於每一個 CnDn 連接對,從而形成密鑰 Kn,1<=n<=16。每一對有 56 位,而置換表只使用其中的 48 位,因為每逢第 8 位都將被忽略。
2.
3. 編碼每個 64 位元的資料塊。
64 位元的消息資料 M 有一個初始置換 IP。這將根據置換表重新排列這些位,置換表中的項按這些位元的初始順序描述了它們新的排列。我們以前見過這種線性表結構。
使用函數 f 來生成一個 32 位元的塊,函數 f 對兩個塊進行操作,一個是 32 位的資料塊,一個是 48 位的密鑰 Kn,連續迭代 16 次,其中 1<=n<=16。用 + 表示 XOR 加法(逐位相加,模除 2)。然後,n 從 1 到 16,計算 Ln = Rn-1 Rn = Ln-1 + f(Rn-1,Kn)。即在每次迭代中,我們用前一結果的右邊 32 位,並使它們成為當前步驟中的左邊 32 位。對於當前步驟中的右邊 32 位元,我們用演算法 f XOR 前一步驟中的左邊 32 位。
要計算 f,首先將每一塊 Rn-1 從 32 位擴展到 48 位。可以使用選擇表來重複 Rn-1 中的一些位來完成這一操作。這個選擇表的使用就成了函數 f。因此 f(Rn-1) 的輸入塊是 32 位,輸出塊是 48 位。f 的輸出是 48 位,寫成 8 塊,每塊 6 位元,這是通過根據已知表按順序選擇輸入中的位元來實現的。
我們已經使用選擇表將 Rn-1 從 32 位擴展成 48 位,並將結果 XOR 密鑰 Kn。現在有 48 位,或者是 8 組,每組 6 位。每組中的 6 位現在將經歷一次變換,該變換是演算法的核心部分:在叫做“S 盒”的表中,我們將這些位當作位址使用。每組 6 位在不同的 S 盒中表示不同的位址。該位址中是一個 4 位元數字,它將替換原來的 6 位。最終結果是 8 組,每組 6 位變換成 8 組,每組 4 位(S 盒的 4 位輸出),總共 32 位。
f 計算的最後階段是對 S 盒輸出執行置換 P,以得到 f 的最終值。f 的形式是 f = P(S1(B1)S2(B2)...S8(B8))。置換 P 根據 32 位元輸入,在以上的過程中通過置換輸入塊中的位,生成 32 位輸出。 解密只是加密的逆過程,使用以上相同的步驟,但要逆轉應用子密鑰的順序。DES 演算法是可逆的。
三重 DES(官方叫做 DES 3)只是以某種特殊的順序使用 2 個密鑰執行三次 DES。三重 DES 也可以使用三個單獨密鑰,而不只使用兩個。DES 3 中可能的密鑰有 2112 個,而在 DES 中只有 256 個可能的密鑰。
“高級加密標準”成就
早在 1993 年,政府就意識到 DES 安全性將會受到危害。即使我們假定 NSA 在 DES 中構建了一個後門以允許政府可以對 DES 消息進行常規解密(如公鑰發現者 Diffie 和 Hellman 在 1975 年給 NSA 的信中聲稱的那樣),DES 是日趨過時的加密演算法。這並不是那麼有效的方法。它在硬體上表現並不如人意(如“智慧卡”已開始顯示其缺點)。但直到 1997 年,美國國家科學技術研究所 (NIST) 才開始打著 AES 專案的旗幟徵集其接任者。
1997 年 4 月的一個 AES 研討會宣佈了以下 AES 成就的最初目標:
• 可供政府和商業使用的功能強大的加密演算法
• 支援標準密碼本方式
注:DES 演算法將消息塊置換成密碼塊。如果每一塊都單獨加密,那麼加密方式叫做電子代碼書 (Electronic Code Book) (ECB) 方式。DES 加密有另外兩種方式,分別叫鏈塊編碼 (Chain Block Coding) (CBC) 和密碼反饋 (Cipher Feedback) (CFB),它們使每個密碼塊都依賴於初始 XOR 操作中所有以前的消息塊。由於政府/銀行業都使用這三種方式,所以需要 AES 如何處理資訊方面的相容性。
• 要明顯比 DES 3 有效
• 密鑰大小可變,這樣就可在必要時增加安全性
• 以公正和公開的方式進行選擇
• 可以公開定義
• 可以公開評估
AES 的草案中最低可接受要求和評估標準是:
A.1 AES 應該可以公開定義。
A.2 AES 應該是對稱的塊密碼。
A.3 AES 應該設計成密鑰長度可以根據需要增加。
A.4 AES 應該可以在硬體和軟體中實現。
A.5 AES 應該 a) 可免費獲得,或 b) 遵守與美國國家標準學會 (ANSI) 專利政策一致的規定獲得。
注:這意味著將把受專利權保護的演算法(受 ANSI 政策影響的演算法)也考慮在內。已經放棄了這種想法,因此確保了不受保護(即,無專利)的演算法成為唯一的選擇。
A.6 將根據以下要素評價符合上述要求的演算法:
1. 安全性(密碼分析所需的努力)
2. 計算效率
3. 記憶體需求
4. 硬體和軟體可適用性
5. 簡易性
6. 靈活性
7. 許可證需求(見上面的 A5)
Rijndael:AES 演算法獲勝者
2000 年 10 月,NIST 選擇 Rijndael(發音為 "Rhine dale")作為 AES 演算法。它目前還不會代替 DES 3 成為政府日常加密的方法,因為它還須通過測試過程,“使用者”將在該測試過程後發表他們的看法。但相信它可以順利過關。
Rijndael 是帶有可變塊長和可變密鑰長度的迭代塊密碼。塊長和密鑰長度可以分別指定成 128、192 或 256 位。
Rijndael 中的某些操作是在位元組級上定義的,位元組表示有限欄位 GF(28) 中的元素,一個位元組中有 8 位。其他操作都根據 4 位元組字定義。
加法照例對應於位元組級的簡單逐位元 EXOR。
在多項式表示中,GF(28) 的乘法對應於多項式乘法模除階數為 8 的不可約分二進位多項式。(如果一個多項式除了 1 和它本身之外沒有其他約數,則稱它為不可約分的。)對於 Rijndael,這個多項式叫做 m(x),其中:m(x) = (x8 + x4 + x3 + x + 1) 或者十六進位表示為 '11B'。其結果是一個階數低於 8 的二進位多項式。不像加法,它沒有位元組級的簡單操作。
不使用 Feistel 結構!
在大多數加密演算法中,輪回變換都使用著名的 Feistel 結構。在這個結構中,中間 State 的位元部分通常不做更改調換到另一個位置。(這種線性結構的示例是我們在 DES 部分中討論的那些表,即使用固定表的形式交換位。)Rijndael 的輪回變換不使用這個古老的 Feistel 結構。輪回變換由三個不同的可逆一致變換組成,叫做層。(“一致”在這裏表示以類似方法處理 State 中的位。)
線性混合層保證了在多個輪回後的高度擴散。非線性層使用 S 盒的並行應用,該應用程式有期望的(因此是最佳的)最差非線性特性。S 盒是非線性的。依我看來,這就 DES 和 Rijndael 之間的密鑰概念差異。密鑰加法層是對中間 State 的輪回密鑰 (Round Key) 的簡單 EXOR,如以下所注。
輪回變換由四個不同的變換組成。在偽 C 表示法中,它們是:
Round(State,RoundKey) { ByteSub(State); ShiftRow(State); MixColumn(State); AddRoundKey(State,RoundKey); (EXORing a Round Key to the State) } 加密演算法的最後一個輪回稍有不同。它由以下代碼定義: FinalRound(State,RoundKey) { ByteSub(State); ShiftRow(State); AddRoundKey(State,RoundKey); } 在這個表示法中,“函數”(Round, ByteSub, ShiftRow,...) 對那些被提供指針 (State, RoundKey) 的陣列進行操作。ByteSub 變換是非線性位元組交換,各自作用於每個 State 位元組上。在 ShiftRow 中,State 的行按不同的偏移量迴圈移位。在 MixColumn 中,將 State 的列視為 GF(28) 多項式,然後乘以固定多項式 c( x ) 並模除 x4 + 1,其中 c( x ) = '03' x3 + '01' x2+ '01' x + '02'。這個多項式與 x4 + 1 互質,因此是可逆的。
輪回密鑰通過密鑰計畫方式從密碼密鑰 (Cipher Key) 派生而出。它有兩個組件:密鑰擴展 (Key Expansion) 和輪回密鑰選擇 (Round Key Selection)。輪回密鑰的總位數等於塊長度乘以輪回次數加 1(例如,塊長度等於 128 位,10 次輪回,那麼就需要 1408 個輪回密鑰位)。
密碼密鑰擴充成擴展密鑰 (Expanded Key)。輪回密鑰是通過以下方法從這個擴展密鑰中派生的:第一個輪回密鑰由前 Nb(Nb = 塊長度)個字組成,第二個由接著的 Nb 個字組成,以此類推。
加密演算法由以下部分組成:初始輪回密鑰加法、Nr-1 個輪回和最後一個輪回。在偽 C 代碼中:
Rijndael(State,CipherKey) { KeyExpansion(CipherKey,ExpandedKey); AddRoundKey(State,ExpandedKey); For( i=1 ; i
|
本站聲明 |
1. 本論壇為無營利行為之開放平台,所有文章都是由網友自行張貼,如牽涉到法律糾紛一切與本站無關。 2. 假如網友發表之內容涉及侵權,而損及您的利益,請立即通知版主刪除。 3. 請勿批評中華民國元首及政府或批評各政黨,是藍是綠本站無權干涉,但這裡不是政治性論壇! |