分組password算法

代換，S盒。擴散和混淆，這些概念構成了分組password學的基礎。

假設明文和密文的分組長度都為n比特，則明文的每個分組都有2n個可能的取值;

代換：

為使加密運算可逆（即解密運算可行），明文的每個分組都應産生唯一的一個密文分組(多對一)，這樣

的變換是可逆的，稱明文分組到密文分組的可逆變換為代換。

S盒：

一般地，對n比特的代換結構。密鑰的大小是n*2n比特。如對64比特的分組。密鑰大小應該是64*264比特，

難以處理。

實際中常将n分成較小的段。比如可選n==rn0,當中r,n0都是整正數。将設計n個變量的代換變為

設計r個較小的子代換，而每一個子代換僅僅有n0個輸入變量。一般n0都不太大。稱每一個子代換為代換盒。簡稱

S盒。

比如，在DES中将輸入為48比特。輸出為32比特的代換用8個S盒來實作，每一個S盒的輸入端僅為6比特

。輸出端僅為4比特。

擴充和混淆：

 是設計password系統的兩種基本方法，目的是抵抗對手對password系統的統計分析。

擴散就是将明文的統計特性散布到密文中去，實作方式是使得密文中每一位由明文中多位産生。在二進制組password中

，可對資料反複運作某個置換。再對這一個置換作用于某個函數。就可以獲得擴散。

擴散的目的是使明文和密文之間

的統計關系變得盡可能複雜；

混淆是使密文與密鑰之間的統計關系盡可能複雜，以使對手無法得到密鑰。

使用複雜的代換算法可得到預期的混淆

效果，而簡單的線性代換函數得到的混淆效果不夠理想。

擴散和混淆成功地實作了分組password的本質屬性。因而成為設計現代分組password的基礎。

                                                   分組加密步驟

 分組加密算法是對一定大小的明文或者密文做加密或者解密動作。在DES加密系統中。每次

 加密或者解密的分組大小均為64位。是以DES沒有密文擴充問題。

對于大于64位的明文僅僅要按

 每位64位一組進行分割，而對于小于64位的明文僅僅要在後面補“0”就可以。

 DES所用加密或解密密鑰也是64位大小，可是當中有8為是奇偶校驗位，是以64位中真正起密鑰

 作用的僅僅有56位。DES加密與解密所用的算法除了子密鑰的順序不同外，其它部分全然同樣。

 對于随意長度的明文，DES首先對其進行分組，使得每一組的長度為64位，然後分别對每一個

 64位的明文組進行加密。

  每一個64位長度的明文分組的加密步驟例如以下：

  1。初始置換：輸入分組依照初始置換表重排序。進行初始置換。

  2，16輪循環：DES對經過初始置換的64位明文進行16輪類似的子加密過程。

每一輪的子

     加密過程要經過DES的f函數，其步驟例如以下：

    a，将64位從中間，劃分為2部分，每個部分32位，左半部分記為L。右半部分

     記為R，以右半部分進行說明：

     a1,擴充置換：

     将32位的輸入資料依據擴充置換表擴充成48位的輸出資料。

     a2,異或運算：

     将48位的明文資料與48位的子密鑰進行異或運算（以下會說明子密鑰産生過程）

     a3,S盒代換：

     S盒代換是非線性的，48位的輸入資料S盒置換表置換成32位輸出資料。

     a4,直接置換：

     S盒置換後的32位輸出資料依據直接置換表進行直接置換。

     a5,經過直接置換的32位輸出資料與本輪的L部分進行異或操作，結果作為

     下一輪子加密過程的R部分。本輪的R部分直接作為下一輪子加密過程的L部分。

     然後進入下一輪子加密過程，直到16輪所有完畢。

  3，終結置換;依照終結置換表進行終結置換，64位輸出就是密文。

  在每一輪的子加密過程中，48位的明文資料要與48位的子密鑰進行異或或運算，子密鑰的

  産生步驟例如以下：

   a，循環左移：依據循環左移表對C和D進行循環左移，循環左移後的C和D部分作為

    下一輪子密鑰的輸入資料，直到16輪所有完畢。

   b，将C和D部分合并成為56位資料。

   c，壓縮型換位2:56的輸入資料依據壓縮型換位2表輸出48位的子密鑰，這48位的子密鑰

    将與48位的明文資料進行異或操作。

 初始置換：

 經過分組後的64位明文分組将依照初始置換表又一次排序次序，進行初始置換，置換方法例如以下：

 初始置換表從左到右，從上到下讀取。如第一行第一列為58。意味着将原明文分組的第58位置換

 到第1位，初始置換表的下一個數為50，意味着将原明文的分組的第50位置換到第2位，依次類推。将

 原明文分組的64位所有置換完畢。

          置換表

        58 50 42 34 26 18 10 2

        60 52 44 36 28 20 12 4

        62 54 46 38 30 22 14 6

        64 56 48 40 32 24 16 8

        57 49 41 33 25 17 9  1

        59 51 43 35 27 19 11 3

        61 53 45 37 29 21 13 5

        63 55 47 39 31 23 15 7

 16輪循環

 經過了初始置換的64位明文資料在中間生成2部分，每部分32位，左半部分L0和右半部分R0.然後

 ，L0和RO進入加密過程。

RO經過一系列的置換得到32位輸出，再與L0進行異或運算。其結果成為

 下一輪的R1,R0則成為的L1。如此連續運作16輪。

 異或——XOR

 Ri = Li-1 XOR f(Ri-1,Ki)

 Li = Ri-1(i=1,2,3,4.......16)

 每一輪的循環中，右半部分須要經過一系列的子加密過程，這個子加密過程也叫做f函數，子加密

 過程包含

  a1,擴充置換

  a2,異或運算

  a3,S盒代換

  a4,直接置換

 擴充置換

  32位的右半部分明文資料首先要進行擴充置換，擴充置換将32位的輸入資料擴充成48位

  的輸出資料。其目的：1，産生了與密鑰同長度的資料以進行異或運算；2，它提供了更長

  的結果，使得在以後的子加密過程中能進行壓縮。3。它産生雪崩效應。這也是擴充置換、

  最基本的目的，使得輸入的一位将影響兩個替換，是以輸出對輸入的依賴性将傳播的更快

  （雪崩效應），擴充置換的置換方法更初始置換同樣，僅僅是置換表不同，擴充置換表例如以下

   擴充置換表

   32  1 2 3 4 5

   4 5 6 7 8 9

   8 9 10 11 12 13

   12 13 14 15 16 17

   16 17 18 19 20 21

   20 21 22 23 24 25

   24 25 26 27 28 29

   28 29 30 31 32 1

 異或運算 同樣為0，不同為1

 S盒置換

  是算法中最重要的部分，由于其它的運算都是線性的。易于分析，僅僅有S盒是非線性的，它

  比其它不論什麼一步都提供了更好的安全性。

  經過異或得到的48位輸出資料要經過S盒置換。置換由8個盒完畢，記為S盒。

  每一個S盒都有6位輸入，4位輸出。

  每一個S盒是不同的，每一個S盒的置換方法例如以下表，用法：48位的輸入分成8組。沒組6位

  ，分别進入8個S盒，将每一個組的6位輸入記為B0B1B2B3B4B5。那麼表中的行号由B0，B5決定。

  而列号由B1 B2 B3 B4決定。

比如。第一個分組111000要進入第一個S盒S1。那麼行号位10（B0B5）

  即第2行，列号位1100（B1B2B3B4）即第12列，第2行第12列相應的資料為3。是以這個S盒的4位

  輸出就是3的二進制0011

  S[1])

  14 4 13 1 2 15 11 8 3 10 6 12 5 9 0 7

  0 15 7 4 14 2 13 1 10 6 12 11 9 5 3 8

  4 1 14 8 13 6 2 11 15 12 9 7 3 10 5 0

  15 12 8 2 4 9 1 7 5 11 3 14 10 0 6 13

  S[2]

  15 1 8 14 6 11 3 4 9 7 2 13 12 0 5 10

  3 13 4 7 15 2 8 14 12 0 1 10 6 9 11 5

  0 14 7 11 10 4 13 1 5 8 12 6 9 3 2 15

  13 8 10 1 3 15 4 2 11 6 7 12 0 5 14 9

  S[3]

  10 0 9 14 6 3 15 5 1 13 12 7 11 4 2 8

  13 7 0 9 3 4 6 10 2 8 5 14 12 11 15 1

  13 6 4 9 8 15 3 0 11 1 2 12 5 10 14 7

  1 10 13 0 6 9 8 7 4 15 14 3 11 5 2 12

  S[4]

  7 13 14 3 0 6 9 10 1 2 8 5 11 12 4 15

  13 8 11 5 6 15 0 3 4 7 2 12 1 10 14 9

  10 6 9 0 12 11 7 13 15 1 3 14 5 2 8 4

  3 15 0 6 10 1 13 8 9 4 5 11 12 7 2 14

  S[5]

  2 12 4 1 7 10 11 6 8 5 3 15 13 0 14 9

  14 11 2 12 4 7 13 1 5 0 15 10 3 9 8 6

  4 2 1 11 10 13 7 8 15 9 12 5 6 3 0 14

  11 8 12 7 1 14 2 13 6 15 0 9 10 4 5 3

  S[6]

  12 1 10 15 9 2 6 8 0 13 3 4 14 7 5 11

  10 15 4 2 7 12 9 5 6 1 13 14 0 11 3 8

  9 14 15 5 2 8 12 3 7 0 4 10 1 13 11 6

  4 3 2 12 9 5 15 10 11 14 1 7 6 0 8 13

  S[7]

  4 11 2 14 15 0 8 13 3 12 9 7 5 10 6 1

  13 0 11 7 4 9 1 10 14 3 5 12 2 15 8 6

  1 4 11 13 12 3 7 14 10 15 6 8 0 5 9 2

  6 11 13 8 1 4 10 7 9 5 0 15 14 2 3 12

  S[8]

  13 2 8 4 6 15 11 1 10 9 3 14 5 0 12 7

  1 15 13 8 10 3 7 4 12 5 6 11 0 14 9 2

  7 11 4 1 9 12 14 2 0 6 10 13 15 3 5 8

  2 1 14 7 4 10 8 13 15 12 9 0 3 5 6 11

 直接置換

  盒置換後的32位輸出資料将進行直接置換，該置換把每一個輸入位映射到輸出位。随意一位、

  不能被映射兩次，也不能略去。直接置換表的用法與初始置換同樣。

   直接置換表  

  16 7 20 21

  29 12 28 17

  1 15 23 26

  5 18 31 10

  2 8 24 14

  32 27 3 9

  19 13 30 6

  22 11 4 25

 終結置換

  終結置換與初始置換相相應。他們都不影響DES的安全性。主要目的是為了更easy的将明文

  和密文資料以位元組大小放入DES的f算法中，終結置換表和初始置換表的用法同樣。