对称密码体制-第三章-网络09

1、第三章对称密码体制一. 基本要求与基本知识点（1）掌握密码学的基本概念；（2）掌握Shannon模型；（3）了解古典密码技术；（4）掌握分组密码工作原理及数据加密标准算法DES。 （5）掌握流密码工作原理及线性移位寄存器。二. 教学重点与难点（1）Shannon模型；（2）移位寄存器的组成；（3）数据加密标准算法DES。13.1密码学的基本概念3.1.1 引言密码学（Cryptology）是以研究秘密通信为目的，对所要传送的信息采取一种秘密保护，以防止第三者对信息窃取的一门科学。密码学包括密码编码学（Cryptography）和密码分析学（Cryptanalysis）：密码编码学是研究加密原理

2、与方法，使消息保密的技术和科学，它的目的是伪装消息内容。密码分析学则是研究破解密文的原理与方法。密码分析者（Cryptanalyst）是从事密码分析的专业人员。23.1密码学的基本概念被伪装的原始的消息称为明文(Message) 将明文转换为密文过程称为加密（Encryption）加了密的消息称为密文（Ciphertext）把密文转变为明文的过程称为解密（Decryption） 图3-1 加解密过程 33.1密码学的基本概念如图3-1所示为信息的加解密过程，从明文到密文转换的算法称为密码(Cipher) 。一个加密系统采用的基本工作方式叫做密码体制(Cryptosystem)。在密码学中见到“

3、系统或体制”(System)、“方案”(Scheme)和“算法”(Algorithm)等术语本质上是一回事。加密和解密算法通常是在一组密钥（Key）控制下进行的，分别称为加密密钥k1和解密密钥k2。在传统密码体制中，k1=k2，因此传统密码体制又称为对称密码体制（Symmetric Cryptosystem） ；在现代公开密钥密码体制中，k1k2，因此又称为非对称密码体制（Asymmetric Cryptosystem） ；将分别在第三章和第四章介绍两种密码体制。43.1密码学的基本概念在20世纪70年代以前的对称密码体制，只是使用了代换或者置换技术。这个时期的密码体制称为古典密码体制，加密算

4、法是保密的；在20世纪70年代以后出现的对称密码体制，同时使用了代换和置换两种技术。这个时期的对称密码体制称为现代对称密码体制，加密算法是公开的；非对称密码体制产生于20世纪70年代。53.2保密系统的Shannon理论1949年之前的密码知识一种艺术而不是科学，那时的密码专家常常凭直觉和经验设计与分析密码。自从shannon1949年发表了著名文章“communication theory of secrecy system”一文，引发了一场密码学革命，使密码设计和分析建立在严格的理论推导基础之上，从而使密码真正成为一门科学。下面介绍shannon的对称密码模型。 6 明文空间M ，表示全体

5、明文的集合； 密文空间C ，表示全体密文的集合； 密钥空间K ，表示全体密钥的集合，包括加密密钥和解密密钥； 加密算法E ，表示由明文到密文的变换； 解密算法D ，表示由密文到明文的变换； 7在发送方，对明文空间M的每个明文，加密算法E在加密密钥K的控制下生成对应的密文C，经公开传输信道传送给接收方；在接收方，解密算法D在解密密钥K的控制下，将收到的密文C变换成明文M。模型中，解密算法是加密算法的逆过程，加密密钥和解密密钥相同，发送方需要通过安全通道，将密钥发送给接收方。对明文M用密钥K，使用加密算法E进行加密常常表示为Ek(M)，同样用密钥K使用解密算法D对密文C进行解密表示为Dk(C)，有

6、：CEk(M) MDk(C)Dk(Ek(M) 由于Ek和Dk是依赖于密钥K的一对可逆的数学变换，因此M M从而完成保密通信。8【例】一次一密密码体制。设M=(0110010011)2， K=(0111001001)2在A，B双方通信之前，A首先通过安全信道把密钥K传送给B，然后A将明文M进行加密变换，再通过公开信道传给B。加密过程：C=EK(M)=M K =(0110010011)2 (0111001001)2 =(0001011010)2B收到密文C后，用密钥K进行解密，即：M=DK(C)=C K =(0001011010)2 (0111001001)2 = (0110010011)2= M

7、从而B获得明文M，而那些没有密钥的密码分析者无法获得正确的明文。其中加解密过程均受参数K的控制，且密文、加解密算法是公开的，只需要保管好密钥K。9由shannon模型可见：(1) 已知明文M和加密密钥K时，计算CEk(M)容易，即加密容易；(2) 加密算法必须足够强大，使破译者不能仅根据密文破译消息，即在不知道解密密钥K时，由密文C计算出明文M是不可行的，即破译困难；(3) 由于对称密码系统双方使用相同的密钥，因此必须保证能够安全地产生密钥，并且能够以安全的形式将密钥分发给双方；(4) 对称密码系统的安全只依赖于密钥的保密，不依赖于加密和解密算法的保密；103.3密码攻击对称密码体制的攻击有两

8、种方法：穷举攻击和密码分析。 3.3.1 穷举攻击穷举攻击是最基本也是比较有效的一种攻击方法。穷举攻击(Brute Force Search)是通过试遍所有可能的密钥对所获密文进行解密，直至得到正确的明文；或者用一个确定的密钥对所有可能的明文进行加密，直至得到所获得的密文。穷举攻击的代价与密钥的个数成正比，穷举攻击所花费的时间等于尝试的次数乘以一次解密（加密）所需要的时间。显然可以通过增大密钥位数或加大解密（加密）算法的复杂性来对抗穷举攻击。当密钥位数增大时，密钥的个数增大，尝试的次数必然增大；当解密（加密）算法的复杂性增大时，完成一次解密（加密）所需要的时间增大。从而使穷举攻击只是在理论上可

9、行，在实际上无法实现。113.3.1 穷举攻击表3.1是穷尽密钥空间所需的时间。从表中可以发现，当密钥长度达到128位以上时，以目前的资源来说，穷举攻击将不成功。123.3.2 密码分析当密钥长度增加到一定长度时，穷举攻击不能得逞。因此通过密码分析来攻击密码越来越引起人们的重视。密码分析是依赖加密算法的性质和明文的一般特征等试图破译密文得到明文或试图获得密钥的过程。密钥分析基于Kerckhoff假设：密码分析者可以得到密文，知道明文的统计特性，加密体制，密钥空间及其统计特性，但不知道加密截获的密文所用的特定密钥。密码分析者所使用的策略取决于加密方案的性质以及可供密码分析者使用的信息。根据密码分

10、析者所知的信息量, 把对密码的攻击分为：唯密文攻击、已知明文攻击、选择明文攻击、选择密文攻击、选择文本攻击。133.3.2 密码分析唯密文攻击（Ciphertext-Only Attack）：密码分析者知道加密算法和待破译的密文。已知明文攻击（Known-Plaintext Attack）:密码分析者除知道加密算法和待破译的密文外，而且也知道，有一些明文和同一个密钥加密的这些明文所对应的密文，即知道一定数量的明文和对应的密文。选择明文攻击（Chosen-Plaintext Attack）: 密码分析者知道加密算法和待破译的密文，并且可以得到所需要的任何明文所对应的密文，这些明文和待破译的密文是

11、用同一密钥进行加密的，即知道选择的明文和对应的密文。如在公钥密码体制中，攻击者可以利用公钥加密他任意选定的明文。 143.3.2 密码分析选择密文攻击（Chosen-Ciphertext Attack）: 密码分析者知道加密算法和待破译的密文，密码分析者能选择不同的被加密的密文，并可得到对应的解密的明文，即知道选择的密文和对应的明文。解密这些密文所使用的密钥与解密待破解的密文的密钥是一样的。这种攻击主要用于公钥密码算法。选择文本攻击（Chosen Text Attack）：选择文本攻击是选择明文攻击和选择密文攻击的结合。密码分析者知道加密算法和待破译的密文，并且知道任意选择的明文和它对应的密文

12、，这些明文和待破译的密文是用同一密钥加密得来的，以及有目的选择的密文和它对应的明文，解密这些密文所使用的密钥与解密待破解的密文的密钥是一样的。153.3.2 密码分析在以上几种密码攻击中，唯密文攻击难度最大，因为攻击者可利用的信息最少。如果一个密码体制能够抵抗选择明文攻击，那么它也能抵抗唯密文攻击和已知明文攻击。对密码设计者而言，被设计的加密算法一般要能经受得住已知明文的攻击。如果无论攻击者有多少密文，由一个加密算法产生的这些密文中包含的信息不足以唯一决定对应的明文，也无论用什么技术方法进行攻击都不能被攻破，这种加密体制是绝对安全(Unconditional Security) 。除一次一密（

13、One-Time Pad）外，没有绝对安全的加密体制。163.3.3 理想保密和完善保密设明文为M，密文为C，密钥为K。 如果有I（M;C）=0，即M与C统计独立，从C得不到任何关于M的信息，这种密码体制称为完善保密。如果有0I（M;C）0，即已知密文C，但密钥K是不确定的，因此不能正确恢复明文，这种密码体制称为理想保密。 173.4 古典密码技术古典密码技术主要使用代换或者置换两种技巧。（1）代换（Substitution）是将明文字母替换成其他字母、数字或者符号。（2）置换（Permutation）则保持明文的所有字母不变，只是打乱明文字母的位置和次序。183.4 古典密码技术古典代换密码

14、技术分为单字母代换密码和多字母代换密码两类。 （1）单字母代换密码，它将明文的一个字符用相应的一个密文字符代替。单字母代换密码中又分为单表代换密码和多表代换密码：单表代换密码只使用一个密文字母表，并且用密文字母表中的一个字母来代替一个明文字母表中的一个字母。多表代换密码是将明文消息中出现的同一个字母，在加密时不是完全被同一个固定的字母代换，而是根据其出现的位置次序，用不同的字母代换。 （2）多字母代换密码，它是对多于一个字母进行代换。193.4.1 单表代换密码单表代换密码只是用一个密文字母表，并且用密文字母表中的一个字母来代替一个明文字母表中的一个字母。设M和C分别表示为含n个字母的明文字母

15、表和密文字母表。M=m0， m1，mn-1C =c0，c1， ，cn-1如果f为一种代换方法，那么密文为：C= Ek(m)=c0c1cn-1=f(m0)f(m1) f(mn-1)201. 凯撒密码（Caesar Cipher） 凯撒密码是典型的单表代换密码，由Julius Caesar发明，最早用在军方。将字母表中的每个字母，用它后面的第3个字母代替。例如：明文：meet me after the toga party密文：PHHW PH DIWHU WKH WRJD SDUWB如果让每个字母等价于一个数字：211. 凯撒密码（Caesar Cipher） 那么凯撒密码算法如下：对每个明文字母

16、m，代换成密文字母c， 加密： c = E(m) = (m + 3) mod 26 解密： m= D(c) = (c3) mod 26为了增加凯撒密码的破解难度，允许密文字母和明文字母相隔不限于3个字母，而是可以间隔任意多个字母，即移位数1k25。英语有26个字母，字母a可以换成字母表中任何其他字母（BZ）（换成自身没意义）。因此，每个字母有25种代换的可能。 221. 凯撒密码（Caesar Cipher） 通用的凯撒密码算法表示为：移位数1k25， 加密： c= Ek(m) = (m + k) mod 26 解密： m= Dk(c) = (ck) mod 26显然对凯撒密码的分析要基于Ke

17、rckhoff假设。假设攻击者知道使用凯撒密码加密。如果攻击者只知道密文，即唯密文攻击，只要穷举测试所有可能字母移位的距离，最多尝试25次。如果攻击者知道一个字符以及它对应的密文，即已知明文攻击，那么攻击者很快就通过明文字符和对应的密文字符之间的距离推出密钥。（这里密钥理解为移位数k）231. 凯撒密码（Caesar Cipher） 通用的凯撒密码算法表示为：移位数1k25，加密： c= Ek(m) = (m + k) mod 26解密： m= Dk(c) = (ck) mod 26显然对凯撒密码的分析要基于Kerckhoff假设。假设攻击者知道使用凯撒密码加密。如果攻击者只知道密文，即唯密文

18、攻击，只要穷举测试所有可能字母移位的距离，最多尝试25次。如果攻击者知道一个字符以及它对应的密文，即已知明文攻击，那么攻击者很快就通过明文字符和对应的密文字符之间的距离推出密钥。（这里密钥理解为移位数k）242、凯撒密码改进凯撒密码密文字母和明文字母相隔为k个字母，因此最多只要进行25次尝试，即k=1、2、25，就一定能够成功破解。如果某个明文消息的所有字母不采用相同的替换模式（即k不相同），而是使用随机替换，则在某个明文消息中，每个a可以换成BZ中的任意字母，每个b可以换成CZ、A中的任意字母，等等。这种方式的关键是b的替换和a没有关系，将a换成D未必就要将b换成E，而是可以将b换成任何其他

19、字母。如下字母替换表所示：252、凯撒密码改进一个更实际的构造字母代换表的方法是使用一个密码句子。如密钥句子为the message was transmitted an hour ago，按照密钥句子中的字母依次填入字母表（重复的字母只用一次），未用的字母按自然顺序排列，可以构造以下的字母替换表：262、凯撒密码改进现在使用26个字母的任意替换与组合，总共有26！=4*1026可能，从而使采用穷举攻击进行破解变得十分困难。273.4.2 多表代换密码用单表代换密码加密后的密文具有明文的特征，要提高密码的强度，应该让明文结构在密文中尽量少出现。多表代换密码能够减少这种密文字母和明文字母之间的对

20、应关系。多表代换密码是对每个明文字母信息采用不同的代换，也即用两个以上的代换序列依次对明文消息的字母进行代换的加密方法。如果明文字母序列为m = m1m2，令f = f1，f2，为代换序列，则对应的密文字母序列为： c=Ek(m)= f1 (m1)f2 (m2) 283.4.2 多表代换密码（1）实际中经常采用周期多表代换密码，如维吉尼亚密码。通常只使用有限的代换，代换被重复使用以完成对消息的加密。周期多表代换密码代换序列为： f = f1，f2，fd，f1，f2，fd， 在对明文字母序列为m = m1m2进行加密时，相应的密文字母系列为： C=Ek(m)= f1 (m1)f2 (m2) fd

21、 (md) f1 (md+1) f2 (md+2) fd (m2d) （2）对每个明文字母都采用不同的代换进行加密，称作是一次一密密码(one-time pad cipher), 这是一种在理论上唯一不可破的密码。291、维吉尼亚密码维吉尼亚密码（Vigenre Cipher）是一种周期多表代换密码， 1858年由法国密码学家维吉尼亚提出。维吉尼亚密码常常使用英文单词作为字母表，密文、明文、密钥均为英文字母串。先将英文字母映射为025的数字，然后再进行加密运算。301、维吉尼亚密码密钥K=（k1，k2，kd），d为代换周期长度。（1）加密时，先将明文分为长度为d的分段，再进行加密运算。在分段内

22、，明文为M=（m1，m2，md），加密函数为：C=EK(M)=(m1+k1)mod 26，(m2+k2) mod 26，(md+kd) mod 26)（2）解密时，也要先将密文分为长度为d的分段，再进行解密运算。在分段内，密文为C=（c1，c2，cd），解密函数为：M=DK(C)=(c1-k1)mod 26，(c2-k2) mod 26，(cd-kd) mod 26)311、维吉尼亚密码【例】设密钥是cipher，明文串是this cryptosystem is not secure，求密文。解：密钥K=（cipher）=（2，8，15，7，4，17），密钥长度为d=6。将明文M：thiscr

23、yptosystemisnotsecure分成长度为6的分段，如下：321、维吉尼亚密码（1）在第1分段内，加密函数为：C1=EK(M1)=(m1+k1)mod 26，(m2+k2) mod 26 ， ，(m6+k6) mod 26) =(19+2)mod 26,(7+8) mod 26,(8+15) mod 26, (18+7) mod 26, (2+4) mod 26,(17+17) mod 26) =(21,15,23,25, 6,8)同理，在其他分段内的加密过程相同，结果见上表。最后将各分段的密文合并得到密文：C=(21,15,23,25,6,8,0,23,8,21,22,15,21,

24、1,19,19,12,9,15,22,8,25,8,19,22,25,19)于是密文为： VPXZGIAXIVWPUBTTMJPWIZITWZT。 331、维吉尼亚密码（2）对收到的第1分段的密文，进行解密。解密函数为：M1=DK(C1)=(c1-k1)mod 26，(c2-k2) mod 26，(cd-kd) mod 26)=(c1-k1)mod 26,(c2-k2) mod 26, (c3-k3) mod 26, (c4-k4) mod 26, (c5-k5) mod 26, (c6-k6) mod 26) =(21-2)mod 26,(15-8) mod 26, (23-15) mod

25、26, (25-7) mod 26, (6-4) mod 26, (8-17) mod 26) =(19,7, 8, 18, 2, 17)其余分段的解密同理。341、维吉尼亚密码维吉尼亚密码是将每个明文字母映射为几个密文字母。如上例第一分段的明文字母“t”映射为密文字母“c”，而在第二分段的明文字母“t”映射为密文字母“p”，第三分段的明文字母“t”映射为密文字母“i”。如果密钥的长度是m，明文中的一个字母能够映射成这m个可能的字母之一。维吉尼亚密码的密钥空间比较大，对于长度是m的密钥，密钥空间为26m。当m=5，密钥空间所含密钥的数量大于1.1x107。352、一次一密一次一密是非周期多表代

26、换密码，它使用与明文一样长且无重复的随机密钥来加密明文，并且该密钥使用一次后就不再使用。由于一次一密的密钥是随机的，用它加密明文后的密文也是随机的，密文中没有任何明文的特征，因此这个加密方法是绝对安全的。一次一密的安全性是取决于密钥的随机性。但产生大规模随机密钥是一件很困难的事情，目前还没有很好的办法来解决这个问题。并且密钥分配也是一个难点，由于密钥不允许重复使用，因此存在大量的密钥分配问题。一次一密在实际中很少使用，主要是用于高度机密的低带宽信道。363.4.3 多字母代换密码前面介绍的密码都是以单字母作为代换对象，多字母代换密码每次对多个字母进行代换。Playfair密码就是多字母代换密码

27、。371、Playfair 密码 Playfair密码是将明文中双字母音节作为一个代换单元，并将其转换成密文的双字母音节（即一次代换两个字母）。Playfair算法是基于一个由密钥组成的一个55 阶矩阵。假设密钥是monarchy，构建矩阵的方法是将密钥（去掉重复的字母）从左到右、从上到下填入矩阵中，再将剩余的字母按照字母表的顺序依次填入。在该矩阵中，字母I和J暂且当一个字母。这样可以构成如下的密钥矩阵： 381、Playfair 密码 391、Playfair 密码 Playfair按照下面的原则加密。每次以两个字母为一个单位进行操作。（1）如果这两个字母一样，则在中间插入一个字母x(事先约

28、定的一个字母), 如“balloon”变成“ba lx lo on”。（2）如果明文长度不是2的倍数，则在最后填入一个实现约定的字母x。如“table”变为“ta bl ex”。（3）如果两个字母在矩阵的同一行，用它右边的字母来代替(最后一个字母的右边是第1个字母)，如“ar” 加密变为“RM”。（4）如果两个字母在同一列，用它下面的字母来代替它 (最底下的字母的下一个是该列第1个字母)，如“mu”加密变为“CM”。（5）其他的字母都用它同一行，另一个字母的同一列相交的字母代替，如“hs”加密变为“BP”，“ ea”变为“IM”或者“JM” (由加密者自行决定) 。401、Playfair 密

29、码 【例】假设密钥是cipher，使用Playfair算法加密Playfair cipher was actually invented by wheatston。解：由密钥cipher可构建密钥矩阵：411、Playfair 密码 将明文按照两个字母分组为：pl ay fa ir ci ph er wa sa ct ua lx ly in ve nt ed by wh ea ts to nx则密文为：BS DW RB CA IP HE CF IK QB HO QF SP MX EK ZC MU HF DX YI IF UT UQ LZ422、Playfair 密码 的安全性Playfair密

30、码的安全性比单表代换密码提高了许多。单表代换密码的字母有26种组合，而Playfair密码的双字母共有26 x 26 = 676 组合。Playfair密码中比单表代换更好地隐藏了明文中单字母的结构。一个字母可能代换为不同的字母。如使用密钥monarchy构成的矩阵，可以看到字母a与不同字母组合加密后的变化：asBX，arRM，afOI等，字母a可以变换为B，以及a之外的所有字母，因此较好地隐藏了明文的特征。在第一次世界大战中被英军作为最好的密码系统使用，在第二次世界大战中也曾经被美军和盟军大量使用。当然现在看来，该密码的安全性是很低的，它还有明文的部分特征，只要给定几百个字母的密文情况下，该

31、加密方法就可以破解。433.4.4 置换密码代换密码是将明文字母用不同的密文字母代替。置换密码（Permutation Ciper）则保持明文的所有字母不变,只是打乱明文字母的位置和次序，又称换位密码。下面就是一种列置换加密方法。假如用密钥network，加密明文permutation cipher hide the message by rearranging the letter order。将明文按照密钥的长度一行一行地写成一个矩阵，然后按照密钥字母对应的数值从小到大，按照列读出即为密文。443.4.4 置换密码453.4.4 置换密码在密钥network中，字母对应的数字从小到大排列是

32、eknortw，按照这个顺序读出上面矩阵的列即是密文：EIEHGRGTR-APESEIED-PTHTAANTE-UCIEYNEO-TIDSRGLR-ROREERTE-MNHMBAHR置换密码比较简单，经不起已知明文攻击。但是置换密码与代换密码相结合，可以得到效果很好的密码。 463.5分组密码按加密方式，对称密码分为分组密码和流密码。分组密码（Block Cipher）是按字符块加密。流密码(Stream Cipher)是逐个字符加密。473.5.1 分组密码的工作原理分组密码即对固定长度的一组明文进行加密的算法，工作原理如图3-3所示：483.5.1 分组密码的工作原理分组密码先将明文分成固

33、定长度为n的比特块，然后用密钥K分别对每个比特块加密产生相应的长度为n的密文块。解密时，对长度为n的密文块进行解密，得到相应的长度为n的明文比特块，将所有明文比特块合并起来即得到明文。493.5.2 数据加密标准数据加密标准DES(Data Encryption Standard)是分组密码的一个典型代表，是近代密码学发展史上的重要里程碑。美国国家标准局（NBS)1973年5月到1974年8月两次发布通告，公开征求用于政府部门非机密数据的加密算法。1977年由美国国家标准局，基于IBM提出的LUCIFER方案，正式发布了数据加密标准算法，用作政府及商业部门的非机密数据加密标准。DES基本思想是

34、将二进制序列的明文划分成长度为64位的数据块，然后用长度为64位的密钥对数据块进行变换，形成64位密文。DES同时使用了代换和置换两种技巧。503.5.2 数据加密标准1、DES的结构DES结构包括四部分：（1）对64位明文进行初始置换IP；（2）对IP的结果进行16轮乘积变换；（3）对16轮乘积变换的结果进行逆初始置换IP-1，得到64位密文；（4）DES子密钥的产生。如图3-4所示：513.5.2 数据加密标准图3-4 DES结构图523.5.2 数据加密标准 2、初始置换初始置换的目的是将明文的次序打乱。按照表3-2进行置换，将第58位变换到第1位，第50位变换到第2位，等等。然后将变换

35、后新得到的64位的前32位记为L0，后32位记为R0。初始置换过程如图3-5所示。表3-2初始置换IP 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 7533.5.2 数据加密标准图3-5初始置换IP543.5.2 数据加密标准 3、16轮乘积变换乘积变换的目的是进一步增大明文的混乱

36、性和扩散性，使其不具有统计规律，破译者无法反向推出密钥。将初始置换后的L0和R0经过16轮乘积变换。在每一轮乘积变换中，上一轮的右Ri-1直接变换为下一轮的左Li，上一轮的左Li-1与加密函数f异或后作为下一轮的右Ri。加密函数f是上一轮右Ri-1和子密钥Ki的函数。即Li=Ri-1Ri=Li-1f(Ri-1，Ki)其中Ki是由56位密钥产生的子密钥，i=1，2，3， ，16，如图3-6所示。 553.5.2 数据加密标准图3-6 第i轮乘积变换 563.5.2 数据加密标准 DES的关键在于加密函数f(Ri-1，Ki)的计算。首先将32比特的Ri-1，按照表3-3扩展为48位。然后与48位子

37、密钥Ki进行异或运算，得到一个48位的比特串。再将该48比特分成8组，每组6比特，分别输入到8个Si盒（即S1、S2、S3、S4、S5、S6、S7、S8）。每个Si盒是一个4行（0、1、2、3）16列（0、1、2、15）的表，表中的每一项都是4比特的数。如表3-5所示。573.5.2 数据加密标准 表3-3 扩展置换表E 32 1 2 3 4 5 4 5 6 7 8 9 8 9 10 11 12 13 12 13 14 15 16 1716 17 18 19 20 21 20 21 22 23 24 25 24 25 26 27 28 29 28 29 30 31 32 1 583.5.2 数

38、据加密标准593.5.2 数据加密标准603.5.2 数据加密标准每个Si盒的输入为6位：b1b2b3b4b5b6，其中b1b6确定Si表的行，b2b3b4b5确定Si表的列，行列交叉处的十进制数转换为4位二进制数，即为Si盒的4位输出。假设S1盒的输入为011001，b1b6= (01)2= (1)10，b2b3b4b5=(1100) 2=(12)10，1行12列交叉处为(9)10=(1001)2，即为S1的输出。于是8个Si盒共输出32位，再经过表3-4的置换P后，形成函数f(Ri-1，Ki)的32比特输出。如图3-7所示： 613.5.2 数据加密标准 表3-4 置换P16 7 20 2

39、129 12 28 17 1 15 23 26 5 18 31 10 2 8 24 1432 27 3 919 13 30 622 11 4 2562图3-7 f函数计算过程63图3-8 16轮乘积变换过程 16轮乘积变换过程如图3-8所示。643.5.2 数据加密标准4、逆初始置换IP-1将16轮乘积变换后得到的L16（32位）和R16（32位），再按表3-6经过逆初始置换IP-1，最后得到64位的输出密文，如图3-9所示。 表3-6 逆初始置换IP-140 8 48 16 56 24 64 3239 7 47 15 55 23 63 3138 6 46 14 54 22 62 3037 5

40、 45 13 53 21 61 2936 4 44 12 52 20 60 2835 3 43 11 51 19 59 2734 2 42 10 50 18 58 2633 1 41 9 49 17 57 25653.5.2 数据加密标准图3-9 逆初始置换 663.5.2 数据加密标准5、DES子密钥产生DES是用56位密钥加密64位明文，输出64位密文的算法。密钥长度为64位，其中第8、16、24、32、40、48、56、64位共8位是奇偶校验位，在算法中不起作用，有效密钥长度为56位，如下图所示。673.5.2 数据加密标准683.5.2 数据加密标准56位密钥经过置换选择1，循环左移、

41、置换选择2等变换，产生16个48位的子密钥，分别用于16轮乘积变换，如图3-10所示： 69图3-10 DES子密钥产生过程 703.5.2 数据加密标准56位密钥经过表3-7的置换后，生成C0（28位，前4行）和D0（28位，后4行），如图3-11所示： 表3-7 置换选择1 57 49 41 33 25 17 9 1 58 50 42 34 26 18 10 2 59 51 43 35 27 19 11 3 60 52 44 36 63 55 47 39 31 23 15 7 62 54 46 38 30 22 14 6 61 53 45 37 29 21 13 5 28 20 12 4

42、713.5.2 数据加密标准图3-11 置换选择1 723.5.2 数据加密标准将C0（28位）和D0（28位）各循环左移1位，得到C1和D1。然后将C1和D1合并为56位，经过表3-8的置换，生成48位的子密钥K1。每轮Ci-1和Di-1按照表3-9循环左移1位或者2位，Ci-1和Di-1循环左移后变为Ci和Di，将Ci和Di合在一起的56位，经过置换选择2，从中选出48位作为这一轮的子密钥Ki。如图3-12所示。如此继续，产生所有16个子密钥。例题，自学教材例3.5.2（P56）。733.5.2 数据加密标准 表3-8 置换选择2 14 17 11 24 1 5 3 28 15 6 21

43、10 23 19 12 4 26 8 16 7 27 20 13 12 41 52 31 37 47 55 30 40 51 45 33 48 44 49 39 56 34 53 46 42 50 36 29 3274表3-9 循环左移位数表 75图3-12 置换选择2 763.5.2 数据加密标准6、DES解密DES解密过程与加密过程本质上一致，加密和解密使用同一个算法，使用相同的步骤和相同的密钥。主要不同点是将密文作为算法的输入，但是逆序使用子密钥Ki，即第1轮使用子密钥K16，第2轮使用子密钥K15，最后一轮使用子密钥K1。773.5.2 数据加密标准7、对DES的评述（1）虽然DES描

44、述较长，但它能以硬件或软件方式非常有效地实现。需要完成的运算仅为比特串的异或，扩展置换E、S盒、置换IP和IP-1以及K1、K2、K16的计算都能在固定时间内通过查表（以软件或电路）来实现。（2）从发布时起，DES就备受争议，人们质疑其安全性。争论的焦点主要集中在密钥的长度、迭代次数以及S盒的设计等方面。DES的安全性是依赖S盒，事实表明S盒被设计成能够防止差分密码分析。 783.5.2 数据加密标准DES密钥长度为56位，共有56位密钥256=7.2*1016个可能值，这不能抵抗穷尽密钥搜索攻击的。例如：1997年，克罗拉多州的程序员Verser在Inrernet上数万名志愿者的协作下用96

45、天的时间找到了密钥长度为40位和48位的DES密钥；1998年电子边境基金会（EFF）使用一台价值25万美元的计算机在56小时之内破译了56位的DES；1999年，电子边境基金会（EFF）通过互联网上的10万台计算机合作，仅用22小时15分破译了56位的DES；793.5.2 数据加密标准（3）由于DES安全问题，1999年美国国家标准技术研究所(NIST )发布了一个新版本的DES标准（FIPS PUB46-3），将三重DES（简写为3DES）取代DES成为新的标准。3DES存在以下优点：首先它的密钥长度是168位，足以抵抗穷举攻击；其次，3DES的底层加密算法与DES的加密算法相同，该加密

46、算法比任何其它加密算法受到分析的时间要长得多，也没有发现有比穷举攻击更有效的密码分析攻击方法。这种加密方案穷举攻击代价是2112。由于DES存在安全问题，而三重DES算法运行速度比较慢。2000年美国国家标准技术研究所(NIST )提出新的美国联邦加密标准是高级加密标准（Advanced Encryption Standards，AES），其分组长度为128位的对称分组密码，密钥长度支持128位、192位、256位。803.6 流密码 3.6.1 流密码基本原理流密码又称序列密码，其工作原理如图3-13所示：813.6.1 流密码基本原理其中m=m0m1是一个待加密的明文序列（通常为0，1序列

47、），k=k0k1是一个与明文序列等长的二元（伪）随机序列，即密钥序列，收发双方事先都知道该密钥序列。发送方使用密钥序列k对明文序列进行加密过程，即将k和m对应位进行模2相加，得到密文c=c0c1。在接收端，合法接收者进行解密过程，即将密文序列c和密钥序列k的对应位进行模2相加，从而得到恢复的明文序列m= m0m1。823.6.2 线性移位寄存器从保密系统的shannon模型和流密码的工作原理可知，流密码保密的关键是如何高效的产生可靠的二元随机序列作为密钥流。由于二元序列长度是有限的，因此其具有周期性，它是周期范围内的随机序列，而不是真正意义的随机序列，称其为伪随机二元序列。通常将伪随机二元序列

48、作为密钥流。线性移位寄存器就是能够产生伪随机序列的逻辑电路，其工作原理如图3-14所示：833.6.2 线性移位寄存器图3-14 线性移位寄存器843.6.2 线性移位寄存器图中标有an，an-1，a1的小方框表示寄存器，每个寄存器有两个状态：0或1。n称为线性移位寄存器的级数。f(an,an-1,a1)=c1a1 c2a2 cnan是反馈函数，其中ci为0或1， 是模2加法。该反馈函数是an，an-1，a1的线性函数，因此称其为线性移位寄存器LFSR(Linear Feedback Shift Register)，否则称为非线性移位寄存器。当一个时钟脉冲到来时:最左边一个寄存器的值输出，其余寄