首页 > 代码库 > 分组password算法

分组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算法中,终结置换表和初始置换表的用法同样。

   终结置换表
  40 8 48 16 56 24 64 32
  39 7 47 15 55 23 63 31
  38 6 46 14 54 22 62 30
  37 5 45 13 53 21 61 29
  36 4 44 12 52 20 60 28
  35 3 43 11 51 19 59 27
  34 2 42 10 50 18 58 26
  33 1 41 9  49 17 57 25

                                            子密钥
 C和D要经过16轮类似的操作产生16份子密钥,每一轮子密钥的产生都要经过循环左移和压缩型换位2.
 循环左移要求C部分和D部分要依据循环左移表进行左移,循环左移表给出了每一轮须要循环左移的
 位数,寻黄左移后的C和D部分作为下一轮子密钥的输入数据,直到16轮所有完毕。
 轮数 循环左移位数
 1  1
 2  1
 3  2
 4  2
 5  2
 6  2
 7  2
 8  2
 9  1
 10  2
 11  2
 12  2
 13  2
 14  2
 15  2
 16  1
 经过循环左移之后。C和D部分合并成为56位的数据。之后这56位数据要经过压缩型换位2
 生成终于的48位子密钥,这48位的子密钥将与48位的明文数据进行异或操作。
 压缩型换位2置换表
 14 17 11 24 1 5
 3 28 15 6 21 10
 23 19 12 4 26 8
 16 7 27 20 13 2
 41 52 31 37 47 55
 30 40 51 45 33 48
 44 49 39 56 34 53
 46 42 50 36 29 32

 

??

分组password算法