第3章对称密码技术




本章导读


本章主要介绍对称密码技术及其相关的内容，包括一些加密算法、密钥的产生和密钥的分配等。

对称密码是一种加密密钥和解密密钥相同的密码体制。

对称密码分为分组密码和流密码。分组密码每次操作(如加密和解密)是针对一个分组而言。流密码则每次加密(或者解密)一位或者一字节。

对密码的攻击方法有基于密码算法性质的密码分析和穷举搜索攻击。

从发展阶段来看，对称密码主要分为两种： 20世纪70年代以前的对称密码（主要指计算机出现以前）和20世纪70年代以后的对称密码。

20世纪70年代以前的对称密码称为古典加密技术，主要使用代换或者置换技巧。20世纪70年代以后的对称密码则同时使用代换和置换技巧。

古典加密技术分为两类： 一类是单字母代换密码，它将明文的一个字符用相应的一个密文字符代替。另一类是多字母代换密码，它是对多于一个字母进行代换。单字母代换密码又分为单表代换密码和多表代换密码。

DES是第一个加密标准，它与古典加密技术不一样，DES同时使用了代换和置换两种技巧，用56位密钥加密64位明文。

AES是用来取代DES的高级加密标准，其结构与DES不同，它是用128、192或者256位密钥加密128位的分组。

SM4是我国官方公布的第一个商用密码算法，它是一种分组对称密码算法，用128位密钥加密128位的分组。

RC6是RSA公司提交给NIST的一个候选高级加密标准算法，其效率非常高。

RC4是被广泛使用的一种同步流密码。

在密码学中的很多场合下都要使用随机数，安全的随机数应该满足随机性和不可预测性。

密钥分配为通信的双方发送会话密钥。



密码技术是信息系统最重要的安全机制。密码技术主要分为对称密码技术（也称单钥或者传统密码技术）和非对称密码技术（也称双钥或者公钥密码技术）。在对称密码技术中，加密密钥和解密密钥相同，或者一个密钥可以从另一个密钥导出。而非对称密码技术则使用两个密钥，加密密钥和解密密钥不相同。对称密码技术主要使用两种技巧： 代换和置换。代换是将明文中的每个元素映射成另一个元素。置换是将明文中的元素重新排列。在20世纪70年代以前的加密技术都是对称加密技术，并且在这些加密技术中只使用了代换或者置换技巧。这个时期的加密技术也称为古典加密技术。在20世纪70年代以后出现的对称加密技术则同时使用了代换和置换两种技巧。这两个阶段的加密技术还有一个典型区别： 古典加密技术一般将加密算法保密，而现代的对称加密技术则公开加密算法，加密算法的安全性只取决于密钥，不依赖于算法。非对称密码技术则产生于20世纪70年代。

信息安全原理与技术（第4版）

第3章对称密码技术



3.1基 本 概 念


密码学（Cryptology）是以研究秘密通信为目的，即对所要传送的信息采取一种秘密保护，以防止第三者对信息进行窃取的一门学科。密码学作为数学的一个分支，包括密码编码学（Cryptography）和密码分析学（Cryptanalysis）两部分。密码编码学是研究加密原理与方法，使消息保密的技术和科学，它的目的是掩盖消息内容。密码分析学则是研究破解密文的原理与方法。密码分析者（Cryptanalyst）是从事密码分析的专业人员。

采用加密的方法伪装消息，使得未授权者不可理解被伪装的消息。被伪装的原始消息(Message)称为明文（Plaintext）。将明文转换为密文的过程称为加密（Encryption），加了密的消息称为密文（Ciphertext），


图3.1加密解密过程

而把密文转变为明文的过程称为解密（Decryption）。加密解密过程如图3.1所示。将明文转换为密文的算法称为密码(Cipher)。一个加密系统采用的基本工作方式叫作密码体制(Cryptosystem)。实际上在密码学中的“系统或体制(System)”“方案(Scheme)”和“算法(Algorithm)”等术语本质上是一回事，在本书中我们也将使用这些术语。加密和解密算法通常是在一组密钥（Key）控制下进行的，分别称为加密密钥和解密密钥。如果加密密钥和解密密钥相同，则密码系统为对称密码系统。


3.2对称密码模型


对称密码也称传统密码，它的特点是发送方和接收方共享一个密钥。对称密码分为两类： 分组密码(Block Ciphers)和流密码(Stream Ciphers)。分组密码也称为块密码，它是将信息分成一块(组)，每次操作(如加密和解密)是针对一组而言。流密码也称序列密码，它每次加密(或者解密)一位或者一字节。


一个对称密码系统(也称密码体制)由五部分组成。用数学符号描述为S＝{M，C，K，E，D}，如图3.2所示。



图3.2对称密码系统模型



（1） 明文空间M，表示全体明文的集合。

（2） 密文空间C，表示全体密文的集合。

（3） 密钥空间K，表示全体密钥的集合，包括加密密钥和解密密钥。

（4） 加密算法E，表示由明文到密文的变换。

（5） 解密算法D，表示由密文到明文的变换。


在发送方，对于明文空间的每个明文，加密算法在密钥的作用下生成对应的密文。接收方将接收的密文，用解密算法在解密密钥的控制下变换成明文。我们可以看到加密算法有两个输入，一个是明文； 另一个是密钥。加密算法的输出是密文。解密算法本质上是加密算法的逆运行，解密算法的输入是密文和密钥，输出是明文。


对明文M用密钥K，使用加密算法E进行加密，常常表示为Ek(M)，同样用密钥K使用解密算法D对密文C进行解密，表示为Dk(C)。在对称加密体制中，解密密钥相同，有：


C＝Ek(M)
M＝Dk(C)＝Dk(Ek(M))



从对称密码模型可以看到，发送方和接收方主要进行加密和解密运算，我们希望这个运算越容易越好，对于攻击者而言，我们希望他们破译密文的计算越难越好。因此，一个好的密码体制至少要满足下面几个条件。


（1） 已知明文M和加密密钥K时，易于计算C＝Ek(M)。

（2） 加密算法必须足够强大，使破译者不能仅根据密文破译消息，即在不知道解密密钥K时，由密文C计算出明文M是不可行的。

（3） 由于对称密码系统双方使用相同的密钥，因此还必须保证能够安全地产生密钥，并且能够以安全的形式将密钥分发给双方。

（4） 对称密码系统的安全只依赖于密钥的保密，不依赖于加密和解密算法的保密。



3.3密 码 攻 击


分析一个密码系统是否安全，一般是在假定攻击者知道所使用的密码系统情况下进行分析的。一般情况下，密码分析者可以得到密文，知道明文的统计特性、加密体制、密钥空间及其统计特性，但不知道加密截获的密文所用的特定密钥。这个假设称为Kerckhoff假设。分析一个密码系统的安全性一般是建立在这个假设的基础上。当然，如果攻击者不知道所使用的密码体制，那么破译是更难的。但是，不应当把密码系统的安全性建立在攻击者不知道所使用的密码体制这个前提之下。因此，在设计一个密码系统时，其目的应当是在Kerckhoff假设下达到一定的安全程度。

攻击对称密码体制有两种方法： 密码分析和穷举攻击(Brute Force Search)。密码分析是依赖加密算法的性质和明文的一般特征等，试图破译密文得到明文或试图获得密钥的过程。穷举攻击则是试遍所有可能的密钥对所获密文进行解密，直至得到正确的明文； 或者用一个确定的密钥对所有可能的明文进行加密，直到得到与所获得的密文一致。


3.3.1穷举攻击 

穷举攻击是最基本的，也是比较有效的一种攻击方法。从理论上讲，可以尝试所有的密钥。因此只要有足够的资源，任何密码体制都可以用穷举攻击将其攻破。幸运的是，攻击者不可能有无穷的可用资源。

穷举攻击的代价与密钥大小成正比。穷举攻击所花费的时间等于尝试次数乘以一次解密（加密）所需的时间。显然，可以通过增大密钥位数或加大解密（加密）算法的复杂性来对抗穷举攻击。当密钥位数增大时，尝试的次数必然增大。当解密（加密）算法的复杂性增大时，完成一次解密（加密）所需的时间增大，从而使穷举攻击在实际中不能实现。表3.1是穷尽密钥空间所需的时间。从表3.1中我们可以发现，当密钥长度达到128位以上时，以目前的资源来说，穷举攻击将不会成功。




表3.1穷尽密钥空间所需的时间



密钥长度/位
密 钥 数 目
每微秒尝试1次

所需时间
每微秒尝试106次

所需时间


32232=4.3×109231微秒=35.8分2.15毫秒
56256=7.2×1016255微秒=1142年 10.01小时
1282128=3.4×10382127微秒=5.4×1024年5.4×1018年
1682168=3.7×10502167微秒=5.9×1036年5.9×1030年
26个字母排列26!=4×10262×1026微秒=6.4×1012年6.4×106年




3.3.2密码攻击类型



密码分析是基于Kerckhoff假设的。密码分析者所使用的策略取决于加密方案的性质以及可供密码分析者使用的信息，正是基于密码分析者所知的信息量，可把对密码的攻击分为以下几种类型。

(1) 唯密文攻击（CiphertextOnly Attack）。密码分析者有一些消息的密文，这些消息都用同一算法加密。密码分析者的任务是恢复尽可能多的明文，或者是最好能推算出加密消息的密钥，以便采用相同的密钥解出其他被加密的消息。这种情况下，密码分析者知道的东西只有两样： 加密算法和待破译的密文。

(2) 已知明文攻击（KnownPlaintext Attack）。密码分析者除知道加密算法和待破译的密文外，而且也知道有一些明文和同一个密钥加密的这些明文所对应的密文，即知道一定数量的明文和对应的密文。

(3) 选择明文攻击（ChosenPlaintext Attack）。密码分析者知道加密算法和待破译的密文，并且可以得到所需要的任何明文所对应的密文，这些明文和待破译的密文是用同一密钥加密得来的，即知道选择的明文和对应的密文。如在公钥密码体制中，攻击者可以利用公钥加密他任意选择的明文。

(4) 选择密文攻击（ChosenCiphertext Attack）。密码分析者知道加密算法和待破译的密文，密码分析者能选择不同的被加密的密文，并可得到对应的解密的明文，即知道选择的密文和对应的明文。解密这些密文所使用的密钥与解密待破解的密文的密钥是一样的。这种攻击主要用于公钥密码算法。

(5) 选择文本攻击（Chosen Text Attack）。选择文本攻击是选择明文攻击和选择密文攻击的结合。密码分析者知道加密算法和待破译的密文，并且知道任意选择的明文和它对应的密文，这些明文和待破译的密文是用同一密钥加密得来的，以及有目的地选择的密文和它对应的明文，解密这些密文所使用的密钥与解密待破解的密文的密钥是一样的。


在以上任何一种情况下，攻击者的目标都是为了确定正在使用的密钥。显然，上述五种攻击类型的强度按序递增，如果一个密码系统能够抵抗选择明文攻击，那么它也能抵抗唯密文攻击和已知明文攻击。一般来说，一个密码体制是安全的，通常是指在受到前三种攻击下系统的安全性，即攻击者一般容易具备前三种攻击条件。在这几种攻击类型中，唯密文攻击难度最大，因为攻击者可利用的信息最少。在此情况下，一种可能的攻击方法是对所有可能的密钥尝试的强行攻击法，即穷举攻击。如果密钥量非常大，则该方法是不现实的。因此，攻击者通常运用各种统计方法对密文本身进行分析。如果攻击者知道的信息越多，就越容易破解密文。在多数情况下，密码分析者能够获得除密文以外的更多信息，如能够获得一段或者多段明文以及对应的密文，或者可能知道某种明文模式将出现在某个消息中，此时可以进行已知明文攻击，攻击者可以从转换明文的方法来推导密钥。


对密码设计者而言，被设计的加密算法一般要能经受得住已知明文的攻击。如果无论攻击者有多少密文，由一个加密算法产生的这些密文中包含的信息都不足以唯一决定对应的明文，也无论用什么技术方法进行攻击都不能被攻破，这种加密算法则是绝对安全(Unconditional Security)。绝对安全指无论攻击者具有多少计算能力都无法破解密文。除一次一密（OneTime Pad）外，没有绝对安全的加密算法。因此，加密算法的使用者应该挑选满足下列标准中的一个或两个的算法。


(1) 破译该密码的成本超过被加密信息的价值。

(2) 破译该密码的时间超过该信息有价值的生命周期。

如果满足上述的两个准则，一个加密算法就可认为是在计算上安全（Computational Security）的。计算上安全是指在计算能力有限的情况下(如计算所需时间比宇宙生存时间还长)，无法破解此密文。目前的加密算法一般在计算上是安全的。



3.3.3密码分析方法

当密钥长度增加到一定的大小时，穷举攻击变得不切实际。因此用密码分析的方法攻击密码越来越引起人们的重视，目前比较流行的密码分析方法是线性密码分析和差分密码分析。这两种方法主要是针对现代密码的攻击。

线性分析是一种已知明文攻击，最早由Matsui在1993年提出。线性分析是一种统计攻击，它以求线性近似为基础，通过寻找现代密码算法变换的线性近似来攻击。如用这种方法在只需要知道243个已知明文的情况下就可以找到DES的密钥。


差分密码分析在许多方面与线性密码分析相似，它与线性密码分析的主要区别在于差分密码分析包含了将两个输入的异或与其相对应的两个输出的异或相比较。差分密码分析也是一个选择明文攻击。差分密码分析被公认为近年来密码分析的最大成就。差分密码分析出现于20世纪 70年代，但在1990年才被公开发布。它的基本思想是： 通过分析明文对的差值与密文对的差值的影响来恢复某些密钥位。差分分析可用来攻击任何一个拥有固定迭代轮函数结构的密码算法。


3.4古典加密技术

古典加密技术主要使用代换或者置换技术。代换（Substitution）是将明文字母替换成其他字母、数字或者符号。置换（Permutation）则保持明文的所有字母不变，只是打乱明文字母的位置和次序。这些古典代换加密技术分为两类，一类是单字母代换密码(Monogram Substitution Cipher)，它将明文的一个字符用相应的一个密文字符代替。另一类是多字母代换密码(Polygram Substitution Cipher），它是对多于一个字母进行代换。在单字母代换密码中又分为单表代换密码(Monoalphabetic Substitution Cipher)和多表代换密码(Polyalphabetic Substitution Cipher)。单表代换密码只使用一个密文字母表，并且用密文字母表中的一个字母来代替一个明文字母表中的一个字母。多表代换密码是将明文消息中出现的同一个字母，在加密时不完全被同一个固定的字母代换，而是根据其出现的位置次序，用不同的字母代换。



3.4.1单表代换密码



单表代换密码只使用一个密文字母表，并且用密文字母表中的一个字母来代替一个明文字母表中的一个字母。设M和C分别表示为含n个字母的明文字母表和密文字母表。


M={m0，m1，…，mn-1}
C={c0，c1，…，cn-1}



如果f为一种代换方法，那么密文为C=Ek(m)=c0c1…cn-1=f(m0)f(m1)…f(mn-1)。


单表代换密码常见的方法有加法密码、乘法密码和仿射密码。在本章的例子中，我们将用小写字母表示明文，用大写字母表示密文。明文和密文空间都假设为26个字母，即属于Z26，当然很容易推广到n个字母的情况。


1. 加法密码


对每个c，m∈Zn，加法密码的加密算法和解密算法是：


C=Ek(m)=(m+k) mod n
M=Dk(c)=(c-k) mod n



k是满足0<k<n的正整数。若n是26个字母，加密方法是用明文字母后面第k个字母代替明文字母。因此，代换密码中的加密和解密可以看作字母表上的一个字母的置换。Caesar密码是典型的加法密码。


Caesar密码是已知最早的单表代换密码，采用加法加密的方法，由Julius Caesar 发明，最早用在军事上。将字母表中的每个字母，用它后面的第3个字母代替，如下所示。

 明文： meet me after the toga party

 密文： PHHW PH DIWHU WKH WRJD SDUWB

代换方式的定义，如下： 




abcdefghijklmnopqrstuvwxyz
DEFGHIJKLMNOPQRSTUVWXYZABC



可让每个字母等价一个数字，如下： 



abcdefghijklm
0123456789101112

nopqrstuvwxyz
13141516171819202122232425



对每个明文字母m，用密文字母c代换，那么Caesar密码算法如下所示。


 加密： C=E(m)=(m+3) mod 26

 解密： M=D(c)=(c-3) mod 26
移位可以是任意的，如果用k（1≤k≤25）表示移位数，则通用的Caesar密码算法表示如下。


 加密： C=Ek(m)=(m+k) mod 26

 解密： M=Dk(c)=(c-k) mod 26

对Caesar密码安全性的分析如下所示。 


前面已经介绍过，对密码的分析是基于Kerckhoff假设的，因此假设攻击者知道使用Caesar密码加密。如果攻击者只知道密文，即唯密文攻击，只要穷举测试所有可能字母移位的距离，最多尝试25次。实际上攻击者为了加快穷举速度，只要对密文中一个单词进行猜想解密，就可以加快判断密钥的正确性。如果攻击者知道一个字符以及它对应的密文，即已知明文攻击，那么攻击者很快就会通过明文字符和对应的密文字符之间的距离推算出密钥。这个例子说明一个密码体制安全至少要能够抵抗穷举密钥搜索攻击，普通的做法是将密钥空间变得足够大。但是，很大的密钥空间并不是保证密码体制安全的充分条件，下面的例子可以说明这一点。



我们对Caesar密码进行改进，假设密文是26个字母的任意代换，密钥是明文字母到密文字母的一个字母表，密钥长度是26字长。


例如字母代换表如下： 




abcdefghijklmnopqrstuvwxyz
DKVQFIBJWPESCXHTMYAUOLRGZN



若加密的明文为ifwewishtoreplaceletters，那么对应的密文为WIRFRWAJUHYFTS
DVFSFUUFYA。

上面的字母代换表由通信双方事先设计好，一个更实际的构造字母代换表的方法是使用一个密码句子。例如密钥句子为the message was transmitted an hour ago，按照密钥句子中的字母依次填入字母表（重复的字母只用一次），未用的字母按自然顺序排列，可以构造如下的字母代换表。

原字母表如下： 




abcdefghijklmnopqrstuvwxyz



代换字母表如下： 




THEMSAGWRNIDOUBCFJKLPQVXYZ


若明文为please confirm receipt，使用上面的代换字母表，则密文为CDSTKSEBUARJ
OJSESRCL。


使用上面的方法代换，总共有 26!=4×1026种密钥，从表3.1可以看到穷举搜索这么多的密钥很困难。但这并不表示该密码不容易破解。破解这类密码的突破点是由于语言本身的特点是充满冗余的，每个字母使用的频率不相等。由于上面加密后的密文实际上是明文字母的一个排列，因此单表代换密码没有改变字母相对出现的频率，明文字母的统计特性在密文中能够反映出来，即保持明文的统计特性不变。通过统计密文字母的出现频率，可以确定明文字母和密文字母之间的对应关系。英文字母中单字母出现的频率如图3.3所示。




图3.3英文字母中单字母出现的频率


图3.3中的26个字母按照出现频率的大小可以分为下面5类。

(1) e： 出现的频率约为12.7%。

(2) t、a、o、i、n、s、h、r： 出现的频率为6%~9%。

(3) d和l： 出现的频率约为4%。

(4) c、u、m、w、f、g、y、p、b： 出现的频率为1.5%~2.8%。

(5) v、k、j、x、q、z： 出现的频率小于1%。


双字母和三字母组合都有现成的统计数据，常见的双字母组合和三字母组合统计表能够帮助破解密文。

出现频率最高的30个双字母（按照频率从高到低排列）如下： 


thheineranreedonesst
enattonthandoueangas
ortiis etitar tesehiof



出现频率最高的20个三字母（按照频率从高到低排列）如下： 



theingandherereentthanthwaseth
fordthhatsheion inthissthers ver



例3.1已知下面的密文是由单表代换产生的。 

UZQSOVUOHXMOPVGPOZPEVSGZWSZOPFPESXUDBMETSXAIZVUEPHZH

MDZSHZOWSFPAPPDTSVPQUZWYMXUZUHSXEPYEPOPDZSZUFPOMBZWPFUP

ZHMDJUDTMOHMQ

试破译该密文。

首先统计密文中字母出现的频率，然后与英文字母出现的频率进行比较。密文中字母的相对频率统计如表3.2所示。



表3.2密文中字母的相对频率统计



字母次数频率
/%字母次数频率
/%字母次数频率
/%字母次数频率
/%


A21.67H75.83O97.50V54.17
B21.67I10.83P1613.33W43.33
C00.00J10.83Q32.50X54.17
D65.00K00.00R00.00Y21.67
E65.00L00.00S108.33Z1411.67
F43.33M86.67T32.55
G21.67N00.00U108.33



将统计结果与图3.3进行比较，可以猜测密文中P与Z可能是e和t，密文中的S、U、O、M出现频率比较高，可能与明文字母中出现频率相对较高的a、o、i、n、s、h、r这些字母对应。密文中出现频率很低的几个字母C、K、L、N、R、I、J可能与明文字母中出现频率较低的字母v、k、j、x、q、z对应。就这样边试边改，最后得到如下明文。 

it was disclosed yesterday that several informal but direct contacts have been made with political representatives of the viet cong in moscow

在尝试过程中，如果同时使用双字母和三字母的统计规律，那么更容易破译密文。如上面的密文中出现最多的双字母是ZW，它可能对应明文双字母出现频率较大的th，那么ZWP就可能是the，这样就更容易试出明文。


2. 乘法密码

对每个c，m ∈Zn，乘法密码的加密和解密算法是：


C=Ek(m)=(mk) mod n
M=Dk(c)=(ck-1) mod n



其中k和n互素，即gcd(k，n)=1，否则不存在模逆元，不能正确解密。显然，乘法密码的密码空间大小是φ(n)，φ(n)是欧拉函数。可以看到乘法密码的密钥空间很小，当n为26字母，则与26互素的数是1、3、5、7、9、11、15、17、19、21、23、25，即φ(n)=12，因此乘法密码的密钥空间为12。


乘法密码也称采样密码，因为密文字母表是将明文字母按照下标每隔k位取出一个字母排列而成。


例3.2英文字母，选取密码为9，使用乘法密码的加密算法，那么明文字母和密文字母的代换表构造如表3.3所示。




表3.3明文字母和密文字母的代换表



原字母abcdefghijklm
原字母的值0123456789101112
代换字母的值09181101921120312214
代换字母AJSBKTCLUDMVE
原字母nopqrstuvwxyz
原字母的值13141516171819202122232425
代换字母的值1322514236152471625817
代换字母NWFOXGPYHQZIR



若明文为a man liberal in his views，那么密文为AENVUJKXUNLUGHUKQG。


3. 仿射密码


将加法密码和乘法密码结合就构成了仿射密码，仿射密码的加密和解密算法是：

C=Ek(m)=(k1m+k2) mod n

M=Dk(c)=k-11(c-k2) mod n


仿射密码具有可逆性的条件是gcd(k，n)=1。当k1=0时，仿射密码变为加法密码，当k2=0时，仿射密码变为乘法密码。


仿射密码中的密钥空间的大小为nφ(n)，当n为英文字母的个数，即26，φ(n)=12，因此仿射密码的密钥空间为12×26=312。


例3.3设密钥K=(7，3)，用仿射密码加密明文hot。

3个字母对应的数值是7、14和19，分别加密如下： 

(7×7+3) mod 26=52 mod 26=0

(7×14+3) mod 26=101 mod 26=23

(7×19+3) mod 26=136 mod 26=6


3个密文数值为0、23和6，对应的密文是AXG。


例3.4假设获得仿射密码加密的密文是: 

FMXVEDKAPHRERBNDKRXRSREFMORUD5DXYV5HVUPEDKAPRDLYEKV
LRHHHRH

试破译该密码。

同样可以统计密文中各字母出现的频率，然后与英文字母出现频率比较，在尝试过程中同时要考虑仿射密码的条件。

各字母出现的频率统计如表3.4所示。




表3.4例3.4中各字母出现的频率


字母频率(次数)
字母频率(次数)
字母频率(次数)
字母频率(次数)


A2H5O1V4
B1I0P2W0
C0J0Q0X2
D7K5R8Y1
E5L2S3Z0
F4M2T0
G0N1U2




这里虽然只有57个字母，但它足以分析仿射密码，最大频率的密文字母是R(8次)，D(7次)，E、H、K(各5次)和S、F、V(各4次)。首先，我们可以猜想R是e的加密，而D是t的加密，因为e和t是两个出现频率最高的字母。e和t对应的数值是4和19，R和D对应的数值是17和3。对于仿射密码，有c=(k1m+k2)。

所以有如下的关于两个未知数线性方程组： 

17=4k1+k2

13=19k1+k2



这个方程组有唯一解 k1=6，k2=19，但这不是一个合法的密钥，因为gcd(6，26)=2，不等于1。


我们再猜测R是e的加密，而E是t的加密，继续使用上述的方法，得到k1=13，这也是一个不合法的密钥。再试一种可能性： R是e的加密，H是t的加密，则有k1=8，这也是不合法的。继续进行，我们猜测R是e的加密，K是t的加密，这样可得k1=3，k2=5，首先它至少是一个合法的密钥，下一步工作就是检验密钥K＝(3，5)的正确性。如果我们能得到有意义的英文字母串，则可证实该密钥是有效的。对密文进行解密有：

algorithms are quite general definitions of arithmetic processes


3.4.2多表代换密码

单表代换密码是将明文的一个字母唯一地代换为一个字母。加密后的密文具有明文的特征，通过统计密文中字母出现的频率能够比较方便地破解密文。要提高密码的强度，应该让明文结构在密文中尽量少出现。多表代换密码和多字母代换密码能够减少这种密文字母和明文字母之间的对应关系。本节将介绍多表代换密码，第3.4.3节将介绍多字母代换密码。

多表代换密码是对每个明文字母信息采用不同的单表代换，也就是用一系列(两个以上)代换表依次对明文消息的字母进行代换的加密方法。



如果明文字母序列为m=m1m2…，令f=f1，f2，…为代换序列，则对应的密文字母序列为：

C=Ek(m)=f1(m1)f2(m2) … 


若代换系列为非周期无限序列，则相应的密码为非周期多表代换密码。这类密码对每个明文字母都采用了不同的代换表或密钥进行加密，称作是一次一密密码(OneTime Pad Cipher)。这是一种在理论上唯一不可破的密码，一次一密对于明文的特征可实现完全隐蔽，但由于需要的密钥量和明文消息长度相同而难以广泛使用。


在实际中，经常采用周期多表代换密码，它通常只使用有限的代换表，代换表被重复使用以完成对消息的加密。此时代换表系列为：

f=f1，f2，…，fd，f1，f2，…，fd，… 


在对明文字母序列为m=m1m2…进行加密时，相应的密文字母系列为：

C=Ek(m)=f1(m1)f2(m2) …fd(md)f1(md+1)f2(md+2) …fd(m2d) … 



当d=1时，多表代换密码变为单表代换密码。

下面介绍一种比较有名的多表代换密码——维吉尼亚密码。


1. 维吉尼亚密码

维吉尼亚(Vigenère)密码是一种周期多表代换密码，由1858年法国密码学家维吉尼亚提出。它的形式化描述如下。


密钥K＝(k1，k2，…，kd），d为代换周期长度，将明文M=(m1，m2，…，mt)分为长度为d的分段。


加密函数为：


C=Ek(m)=((m1+k1) mod n，(m2+k2) mod n，…，(md+kd) mod n，
(md+1+k1) mod n，(md+2+k2) mod n，…，(m2d+kd) mod n，
 ︙
(mt-d+1+k1) mod n，(mt-d+2+k2) mod n，…，(mt+kd) mod n)



如果密文为C=(c1，c2，…，cn)，则解密函数为：


M=Dk(c)=((c1-k1) mod n，(c2-k2) mod n，…，(cd-kd) mod n，
(cd+1-k1) mod n，(cd+2-k2) mod n，…，(c2d-kd) mod n，
 ︙
(ct-d+1-k1) mod n，(ct-d+2-k2) mod n，…，(ct-kd) mod n)


假设明文和密文都是26个英文字母，维吉尼亚密码常常使用英文单词作为密钥字，密钥则是密钥字的重复。例如密钥字是computer，用它加密明文sender and recipient share a common key，那么密钥将如下所示。


 明文： senderandrecipientshareacommonkey

 密钥： computercomputercomputercomputerc

维吉尼亚密码的加密过程简述如下。

(1) 写下明文，表示为数字形式。

(2) 在明文之上重复写下密钥字，也表示为数字形式。

(3) 加密相对应的明文： 给定一个密钥字母k和一个明文字母m，那么密文字母则是(m+k)mod 26计算结果所对应的字母。


例3.5设密钥字是cipher，明文串是this cryptosystem is not secure，求密文。


在明文下面重复写密钥字，组成密钥。

 明文M： thiscryptosystemisnotsecure

 密钥K： cipherciphercipherciphercip
将明文和密钥转换为数字： 

明文M=(19，7，8，18，2，17，24，15，19，14，18，24，18，19，4，12，8，18，13，14，19，18，4，2，20，17，4)

密钥K=(2，8，15，7，4，17，2，8，15，7，4，17，2，8，15，7，4，17，2，8，15，7，4，17，2，8，15)

对每个明文数字和对应的密钥数字，使用ci=(mi+ki)mod 26加密。得到密文数字为

C=(21，15，23，25，6，8，0，23，8，21，22，15，21，1，19，19，12，9，15，22，8，25，8，19，22，25，19)

于是密文为：

VPXZGIAXIVWPUBTTMJPWIZITWZT

可以看出，维吉尼亚密码是将每个明文字母映射为几个密文字母，如果密钥字的长度是m，则明文中的一个字母能够映射成这m个可能的字母中的一个。因此密文中字母出现的频率被隐蔽了，它的安全性明显比单表代换密码提高了。维吉尼亚密码的密钥空间比较大，对于长度是m的密钥字，密钥空间为26m，当m=5，密钥空间所含密钥的数量大于1.1×107。

2. 一次一密

一次一密是非周期多表代换密码，它使用与明文一样长且无重复的随机密钥来加密明文，并且该密钥使用一次后就不再使用。在实际使用时，通信双方事先协商一个足够长的密钥序列，要求密钥序列中的每一项都是按均匀分布随机地从一个字符表中选取的。双方各自秘密保存密钥序列。每次通信时，发送方用自己保存的密钥序列中的密钥，按次序对要发送的消息进行加密。消息加密完成后，把密钥序列中刚使用过的这一段销毁。接收方每次收到密文消息后，使用同样的密钥序列解密。解密完成后，立即把密钥序列中刚使用过的这一段销毁。由于密钥是随机的，用它加密明文后的密文也是随机的，密文中没有任何明文的特征，因此这个加密方案是绝对完全的。

例如，明文是cryptosystem，选取的密钥序列是djfstlngwjpw。

明文转换数字为：

M=(2，17，24，15，19，14，18，24，18，19，4，12)

密钥转换数字为：

K=(3，9，5，18，19，11，13，6，22，9，15，22)

那么可以得到密文数字为：

C=(5，0，3，7，12，25，5，4，14，2，19，8)

则密文为fadhmzfeocti。


当明文中的字符是位时，密钥序列中的一项也是一位。加密时常采用位异或。

例如，设明文消息是00101001，密钥是10101100，那么加密过程如下： 

密文=明文⊕密钥=00101001⊕10101100=10000101

解密时将密文与密钥异或： 

明文=密文⊕密钥=10000101⊕10101100=00101001

一次一密不可破解的原因是，对于一段密文，与密文相同长度的字母串都可能是明文，密文不能提供明文和密钥的任何信息。对任何与密文一样长的明文，也存在一个密钥用于产生这个明文。也就是说，用穷举搜索所有可能的密钥，就会找到大量可读的明文，但不能确定哪一个是真正需要的明文，可见一次一密是绝对安全的。

由于一次一密的安全性是取决于密钥的随机性，因此首先需要解决产生随机的密钥序列的问题，但产生大规模随机密钥是一件很困难的事情，目前还没有很好的办法来解决这个问题。另外，密钥分配也是一个难点，由于密钥不允许重复使用，因此存在大量的密钥分配问题。由于这些困难，在实际中人们很少使用一次一密，一次一密主要是用于高度机密的低带宽信道。


3.4.3多字母代换密码


前面介绍的密码都是以单字母作为代换对象，如果每次对多个字母进行代换就是多字母代换密码。多字母代换的优点是容易隐藏字母的自然出现频率，有利于对抗统计分析。下面介绍常见的多字母代换密码。



1. Playfair 密码

Playfair 密码是将明文中的双字母音节作为一个单元，并将其转换成密文的双字母音节(即一次代换两个字母)。Playfair算法是基于一个由密钥组成的5×5 阶矩阵。假设密钥是monarchy，构建矩阵的方法是将密钥（去掉重复的字母）从左到右、从上到下填入矩阵中，再将剩余的字母按照字母表的顺序依次填入。在该矩阵中，字母i和j暂且被看作一个字母。这样可以构成如下的密钥矩阵。


MONAR
CHYBD
EFGI/JK
LPQST
UVWXZ


Playfair按照下面的原则加密与解密。

每次以两个字母为一个单位进行操作。


(1) 如果这两个字母一样，则在中间插入一个字母x(事先约定的一个字母)，如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(由加密者自行决定)。


例3.6假设密钥是cipher，使用Playfair算法加密playfair cipher was actually invented by wheatston。


由密钥词cipher可构建如下的密钥矩阵。


CIPHE
RABDF
GKLMN
OQSTU
VWXYZ



将明文按照两个字母分组为：

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 LZ

Playfair密码的安全性比单字母代换密码提高了许多，双字母共有26×26=676 组合，因此频率统计分析表中需要676 条统计数据(而单表代换密码只有 26 条)，另外Playfair 密码比单字母代换更好地隐藏了明文中单字母的结构。一个字母可能代换为不同的字母，如在使用密钥词是monarchy构成的矩阵中，我们观察字母a与不同的字母组合加密后的变化，如as →BX、ar→RM、af→OI等，字母a可以变换为B，以及a所在行的所有字母（除a自己外）。如果密钥词变化，那么a在理论上可以代换为除自己外的任何一个字母，因此Playfair密码能够较好地隐藏明文的特征。Playfair密码在过去一段时间曾经被广泛使用，在第一次世界大战中被英军作为最好的密码系统使用，在第二次世界大战中也曾经被美军和盟军大量使用。当然现在看来，该密码的安全性是很低的，它还有明文的部分特征，只要给定几百个字母的密文情况下，该加密方法就可以被破解。


2. Hill 密码

该密码是1929年由数学家Lester Hill发明的一种多字母代换密码。加密算法将m个明文字母替换成m个密文字母(Hillm密码表示m个明文字母为一组)。这种代换由 m个线性方程决定。


如果m=3，则该密码系统可以表示为：


c1=(k11m1+k12m2+k13m3) mod 26
c2=(k21m1+k22m2+k23m3) mod 26
c3=(k31m1+k32m2+k33m3) mod 26



用向量或者矩阵表示为：

c1c2c3=
k11k12k13k21k22k23k31k32k33m1m2m3 mod 26
或者C=KM mod 26


其中C和M是长度为3的列向量，分别代表密文和明文，K是一个3×3的矩阵，代表加密密钥。运算按照模26执行。


一个Hillm密码加密过程可以简单描述如下。


(1) 将明文字母以m个字母为单位进行分组，若最后一组没有m个字母，则补足没有任何实际意义的哑字母（双方可以事先约定这些字母），并用数字表示这些字母。

(2) 选择一个m阶可逆方阵K，称为Hillm密码的加密矩阵。

(3) 对每m个字母为一组的明文字母，用它对应的值构成一个m维向量。

(4) 计算密文的值C=Km mod 26，然后反查字母表的值，得到对应的m个密文字母。

(5) 同样的方式计算其他明文分组的密文。


例3.7用Hill3对明文pay more money加密，加密密钥为：

K=17175
2118212219


将明文3个字母分为一组，pay  mor  emo  ney，前面3个字母的值用向量表示为：

pay=15024


该3个字母的加密过程为：

K15024=375819486 mod 26=111318=LSN



以此类推，可得整个明文对应的密文是LSN HDL EWN TRW。


解密时使用逆矩阵：



K-1=49151517624017




对于密文LSN，即111318，解密过程为：

K-1111318 mod 26=15024=pay


 Hill密码能够很好地隐藏单字母出现的频率，可以抵抗统计频率分析，但面对已知明文攻击就很容易被破译。



3.4.4置换密码


代换密码是将明文字母用不同的密文字母代替。置换密码（Permutation Cipher）则保持明文的所有字母不变，只是打乱明文字母的位置和次序，所以有时也称换位密码（Transposition Cipher），它的实现方法有很多。下面介绍一种列置换加密方法。

假如用密钥network，加密明文permutation cipher hide the message by rearranging the letter order。

将明文按照密钥的长度一行一行地写成一个矩阵，然后按照密钥字母对应的数值从小到大按照列读出即为密文。


密钥： network
明文： permuta
tioncip
herhide
themess
agebyre
arrangi
ngthele
tterord
er


在密钥network中，字母对应的数字从小到大排列是eknortw，按照这个顺序读出上面矩阵的列即是密文： 

EIEHGRGTRAPESEIEDPTHTAANTEUCIEYNEOTIDSRGLRROREERTE MNHMBAHR


置换密码比较简单，经不起已知明文的攻击。但是置换密码与代换密码相结合，可以得到效果很好的密码。



3.5数据加密标准

1949年Shannon的论文《保密系统的通信理论》，标志着密码学作为一门独立的学科的形成。从此，信息论成为密码学的重要的理论基础之一。Shannon建议采用扩散（Diffusion）、混淆（Confusion）和乘积迭代的方法设计密码。所谓扩散就是将每一位明文和密钥的影响扩散到尽可能多的密文数字中。这样使得密钥和明文以及密文之间的依赖关系相当复杂，以至于这种依赖性对密码分析者来说无法利用。产生扩散的最简单的方法是置换。混淆用于掩盖明文和密文之间的关系，使得密钥的每一个位影响密文的许多位，以防止对密钥进行逐段破译，并且明文的每一个位也应影响密文的许多位，以便隐蔽明文的统计特性。用代换方法可以实现混淆。混淆就是使密文和密钥之间的关系复杂化。密文和密钥之间的关系越复杂，则密文和明文之间、密文和密钥之间的统计相关性就越小，从而使统计分析不能奏效。设计一个复杂的密码一般比较困难，而设计一个简单的密码相对比较容易，因此利用乘积迭代的方法对简单密码进行组合迭代，可以得到理想的扩散和混淆，从而得到安全的密码。近代各种成功的分组密码（如DES、AES等），都在一定程度上采用和体现了Shannon的这些设计思想。


为了适应社会对计算机数据安全保密越来越高的需求，美国国家标准局(NBS)，即现在的美国国家标准和技术研究所(NIST)于1973年5月向社会公开征集标准加密算法，并公布了它的设计要求。

(1) 算法必须提供高度的安全性。

(2) 算法必须有详细的说明，并易于理解。

(3) 算法的安全性取决于密钥，不依赖于算法。

(4) 算法适用于所有用户。

(5) 算法适用于不同应用场合。

(6) 算法必须高效、经济。

(7) 算法必须能被证实有效。



1974年8月27日，NBS开始第二次征集，IBM提交了算法LUCIFER，该算法由Feistel领导的团队研究开发，采用64位分组以及128位密钥。IBM用改版的Lucifer算法参加竞争，最后获胜，成为数据加密标准(Data Encryption Standard，DES)。1976年11月23日，采纳为美国联邦标准，批准用于非军事场合的各种政府机构。1977年1月15日，数据加密标准，即FIPS PUB 46被正式发布。DES是分组密码的典型代表，也是第一个被公布出来的加密标准算法。现代大多数对称分组密码也是基于Feistel密码结构的。


3.5.1DES加密过程

DES同时使用了代换和置换两种技巧。它用56位密钥加密64位明文，最后输出64位密文。整个过程由两大部分组成： 一个是加密过程； 另一个是子密钥产生过程。图3.4是 DES加密算法简图。





图3.4DES加密算法简图



可以将图3.4左半边的处理过程分以下三部分。


(1) 64位明文经过初始置换被重新排列，然后分左右两半，每半各32位。

(2) 左右两半经过16轮置换和代换迭代，即16次实施相同的变换，然后再左右两半互换。

(3) 互换后的左右两半合并，再经过逆初始置换输出64位密文。

图3.4右半边则由56位密钥产生16个48位的子密钥，分别供左半边的16轮迭代加密使用。


1. 初始置换

初始置换(Initial Permutation，IP)是数据加密的第1步，将64位的明文按照图3.5置换。置换表中的数字表示输入位在输出中的位置。



585042342618102
605244362820124
625446383022146
645648403224168
57494133251791
595143352719113
615345372921135
635547393123157


图3.5初始置换



置换后将数据M分成两部分： 左半部分L0和右半部分R0各32位。划分方法原则是偶数位移到左半部，奇数位移到右半部，即 


L0=
M58M50M42M34M26M18M10M2
M60M52M44M36M28M20M12M4
M62M54M46M38M30M22M14M6
M64M56M48M40M32M24M16M8

R0=
M57M49M41M33M25M17M9 M1
M59M51M43M35M27M19M11M3
M61M53M45M37M29M21M13M5
M63M55M47M39M31M23M15M7


2. DES每轮结构




DES每轮的结构如图3.6所示。上一轮的右边Ri-1直接变换为下一轮的左边Li，上一轮的左边Li-1与加密函数F异或后作

图3.6DES每轮结构
为下一轮的右边Ri。加密函数F则是上一轮右边Ri-1和子密钥Ki的函数。即


Li=Ri-1
Ri=Li-1⊕F(Ri-1，Ki)



加密函数F本质上是Ri-1和子密钥Ki的异或，如图3.7所示。但由于它们的位数不一样，不能直接运算。从上式可以看出，加密函数F是32位的，而Ri-1是32位的，子密钥Ki是48位的，因此Ri-1和Ki不能直接异或。DES这样处理该问题： 先用扩展置换E(见图3.8)将Ri-1扩展为48位，与48位子密钥异或，输出48位，再用8个S盒压缩成32位，然后经置换函数P(见图3.9)输出32位的加密函数F。



图3.7加密函数F的计算过程







3212345
456789
8910111213
121314151617
161718192021
202122232425
242526272829
28293031321



图3.8扩展置换E








167202129122817
11523265183110
282414322739
19133062211425



图3.9置换函数P




在加密函数计算过程中使用了8个S盒，S盒是DES保密性的关键所在，它是一种非线性变换，也是DES中唯一的非线性运算。S盒有6 位输入，4 位输出。48位数据经过8个S盒后输出32位数据。



每个S盒都由4行(表示为0，1，2，3)和16列(0，1，…，15)组成，如图3.10所示。每行都是全部的16个长为4比特串的一个全排列，每个比特串用它对应的二进制整数表示。如1001用9表示。48位的输入被分成8个6位的分组，每个分组进入一个S盒进行代换操作，然后映射为4位输出。对每个S盒，将6位输入的第一位和最后一位组成一个二进制数，用于选择S盒中的一行。用中间的4位选择S盒16列中的某一列，行列交叉处的十进制数转换为二进制数可得到4位输出。



S1

1441312151183106125907
0157414213110612119538
4114813621115129731050
1512824917511314100613






S2

1518146113497213120510
3134715281412011069115
0147111041315812693215
1381013154211671205149





S3

1009146315511312711428
1370934610285141211151
1364981530111212510147
1101306987415143115212





S4

7131430691012851112415
1381156150347212110149
1069012117131513145284
3150610113894511127214






S5

2124171011685315130149
1411212471315015103986
4211110137815912563014
1181271142136150910453






S6

1211015926801334147511
1015427129561131401138
9141552812370410113116
4321295151011141760813



图3.10DES的S盒



S7

4112141508133129751061
1301174911014351221586
1411131237141015680592
6111381410795015142312






S8

1328461511110931450127
1151381037412561101492
7114191214206101315358
2114741081315129035611



图3.10(续)


例如对于S1盒而言，如果输入为011001，则行是01(十进制1，即S盒的第2行)，列1100(12，即S盒的第13列)，该处的值是9，转换为二进制数为1001，即为该S盒的输出。

3. 逆初始置换

经过16次迭代后，再交换左右32位，合并为64位作为输入，进行逆初始置换，逆初始置换是初始置换的逆运算，经过逆初始置换后输出即为密文，逆初始置换按照图3.11进行置换。



408481656246432
397471555236331
386461454226230
375451353216129
364441252206028
353431151195927
342421050185826
33141949174725


图3.11逆初始置换



3.5.2DES 子密钥产生

DES加密过程共迭代16轮，每轮用一个不同的48位子密钥。这些子密钥由算法的56位密钥产生。DES算法的输入密钥长度是64位，但只用了其中的56位，如图3.12所示。图中无阴影部分（也就是每行的第8位）将被忽略，主要用于奇偶校验，也可随意设置。




12345678
910111213141516
1718192021222324
2526272829303132
3334353637383940
4142434445464748
4950515253545556
5758596061626364


图3.12DES算法的输入密钥



子密钥的产生过程如图3.13所示。




图3.13子密钥的产生过程



56位密钥首先经过置换选择1(见图3.14)将其位置打乱重排，并将前28位作为C0(见图3.14中的上面部分)，后28位作为D0(见图3.14中的下面部分)。




5749413325179
1585042342618
1025951433527
1911360524436
63554739312315
7625446383022
1466153453729
211352820124


图3.14置换选择1



接下来经过16轮迭代，产生16个子密钥。每一轮迭代中，Ci-1和Di-1循环左移一位或者两位，如图3.15所示。Ci-1和Di-1循环左移后变为Ci和Di，将Ci和Di合在一起的56位，经过



置换选择2(见图3.16)，从中挑出48位作为这一轮的子密钥，这个子密钥作为前面介绍的加密函数的一个输入。再将Ci和Di循环左移后，使用置换选择2产生下一轮的子密钥，如此继续，产生所有16个子密钥。






迭代轮数12345678910111213141516
移位次数1122222212222221


图3.15每轮左移次数的规定





1417112415328
15621102319124
2681672720132
4152313747553040
5145334844493956
3453464250362932


图3.16置换选择2




例3.8用DES加密，明文M=(0123456789ABCDEF)16=(00000001 00100011 01000101 01100111 10001001 10101011 11001101 11101111)2，密钥K=(133457799BBCDFF1)16=(00010011 00110100 01010111 01111001 10011011 10111100 11011111 11110001)2。



加密过程如下所示。 


(1) 初始置换。

 将明文M经过初始置换后分为左右两半。

L0=11001100 00000000 11001100 11111111

R0=11110000 10101010 11110000 10101010

(2) 第1轮迭代运算。

① 确定子密钥K1，将密钥K经置换选择1得： 

C0=11110000 11001100 10101010 1111 

D0=01010101 01100110 01111000 1111

左移1位后经过置换选择2输出48位K1。

K1=00011011 00000010 11101111 11111100 01110000 01110010

② 计算加密函数F。

用扩展置换E将R0扩展为48位，再和K1异或。

E(R0)⊕K1=01100001 00010111 10111010 10000110 01100101 00100111

经8个S盒输出32位。

S1(011000)=0101，S2(010001)=1100，S3(011110)=1000，S4(111010)=0010

S5(100001)=1011，S6(100110)=0101，S7(010100)=1001，S8(100111)=0111

 经置换函数P输出加密函数F如下。


F=00100011 01001010 10101001 10111011


③ 由L0和R0计算出L1和R1。

L1=R0=11110000 10101010 11110000 10101010

R1=L0 ⊕ F(R0，K1)=11101111 01001010 01100101 01000100

因此经过第1轮，得到： 

［R1，L1］=(EF4A6544F0AAF0AA)16

进行类似的运算，经过16轮后得到的结果是：

［R16，L16］=(0A4CD99543423234)16

（3） 逆初始置换。

将第16轮输出合并为一个64位比特串，经过逆初始置换后得到64位密文： 

10000101 11101000 00010011 01010100 

00001111 00001010 10110100 00000101


3.5.3DES解密

DES解密过程与加密过程在本质上是一致的，加密和解密使用同一个算法，使用相同的步骤和相同的密钥。主要不同点是将密文作为算法的输入，但是逆序使用子密钥ki，即第1轮使用子密钥k16，第2轮使用子密钥k15，最后一轮使用子密钥k1。




3.5.4DES的强度

从发布时起，DES就备受争议，很多研究者怀疑它所提供的安全性。争论的焦点主要集中在密钥的长度、迭代次数以及S盒的设计等方面。

DES的安全性依赖于S盒。由于DES里的所有计算，除去S盒，全是线性的。可见S盒对密码体制的安全性是非常重要的。但是自从DES公布以来，S盒设计详细标准至今没有公开。因此就有人怀疑S盒里隐藏了陷门（Trapdoors）。然而到目前为止也没有任何证据证明DES里存在陷门。事实上，后来表明S盒是被设计成能够防止差分密码分析的。

1976年，美国国家安全局（National Security Agency，NSA）披露了S盒的几条设计原则如下： 

(1) 每个S盒的每一行是整数0~15的一个置换； 

(2) 每个S盒的输出都不是其输入的线性或者仿射函数； 

 (3) 改变S盒的输入比特，其输出至少有两比特发生变化；

(4) 对于S盒和任何输入x,S(x)和S(x⊕001100)至少有两比特不同，其中x是一个长度为6的比特串； 

(5) 对于S盒和任何输入x，以及e,f∈{0,1}，S(x)≠S(x⊕11e f 00)，其中x是一个长度为6的比特串； 

(6) 对于S盒，当它的任一输入位保持不变，其他5位输入变化时，输出数字中的0和1的总数接近相等。


DES将Lucifer算法作为标准，Lucifer算法的密钥长度为128位，但DES将密钥长度改为56位。56位密钥共有 256=7.2×1016个可能值，这不能抵抗穷尽密钥搜索攻击。例如在1997年，美国科罗拉多州的程序员Verser在Internet上数万名志愿者的协作下用96天的时间找到了密钥长度为40位和48位的DES密钥。1998年电子边境基金会（EFF）使用一台价值25万美元的计算机在56小时之内破译了56位的DES。1999年，电子边境基金会（EFF）通过Internet上的十万台计算机合作，仅用22小时15分钟就破译了56位的DES。因此需要寻找一个算法替代DES。


另外，DES存在弱密钥。如果一个密钥所产生的所有子密钥都是一样的，则这个外部密钥就称为弱密钥。DES算法的子密钥是通过对一个64位的外部密钥进行置换得到的。外部密钥输入DES后，经密钥置换后分成两半，每一半各自独立移位。如果每一半的所有位都是0或者1，那么在算法的任意一轮所有的子密钥都是相同的。当主密钥是全0全1，或者一半是全0、一半是全1时，就会发生这种情况。因此，DES存在弱密钥。



3.5.5三重DES

DES由于安全问题，美国政府于1998年12月宣布DES不再作为联邦加密标准。新的美国联邦加密标准是高级加密标准(ASE)。在新的加密标准实施之前，为了不浪费已有的DES算法投资，NIST在1999年发布了一个新版本的DES标准（FIPS PUB463），该标准指出DES仅能用于遗留的系统，同时将三重DES（3DES）取代DES成为新的标准。3DES明显存在以下几个优点： 首先，它的密钥长度是168位，足以抵抗穷举攻击； 其次，3DES的底层加密算法与DES的加密算法相同，该加密算法比任何其他加密算法受到分析的时间要长得多，也没有发现有比穷举攻击更有效的密码分析攻击方法。


最简单的多重DES加密是用DES加密两次，每次用不同的密钥，这就是双重DES。但双重DES不安全，没有被人们使用。图3.17是双重DES的加密和解密。对于一个明文M和两个加密密钥K1和K2，加密过程为C=EK2［EK1［M］］，解密过程为M=DK1［DK2［C］］。密钥总长度为112位，似乎密码强度增加了一倍，但由于双重DES存在中间相遇攻击，使它的强度跟一个56位DES强度差不多。



从图3.17中可以观察到C=EK2［EK1［M］］，则X=EK1［M］=DK2［C］。若已知(M，C)，攻击方法如下： 先用256个可能的K1加密M，得到256个可能的值，将这些值从小到大存入一个表中； 再对256个可能的K2解密C，每次做完解密，将所得的值与表中的值比较，如果产生匹配，则它们对应的密钥可能是K1和K2。用一个新的明文密文对检测所得两个密钥，如果两密钥产生正确的密文，则它们是正确的密钥。

为防止中间相遇攻击，可以采用3次加密方式，如图3.18所示。这是使用两个密钥的三重DES，采用加密解密加密(EDE)方案。加密为C=EK1［DK2 ［EK1［M］］］，解密为M=DK1［EK2 ［DK1［C］］］。需要注意的是，加密与解密在安全性上来说是等价的。这种加密方案的攻击代价是2112。





图3.17双重DES



图3.18三重DES





目前还没有针对两个密钥的三重DES的实际攻击方法，但是感觉它不太可靠，如果采用三个密钥的三重DES则比较让人放心。三个密钥的三重DES的密钥长度是168位，采用加密解密加密(EDE)方案。其加密过程为C=EK3［DK2 ［EK1［M］］］，解密过程为M=DK1［EK2 ［DK3［C］］］。目前这种加密方式已经被一些网络应用采用，如本书后面章节要讨论的PGP和S/MIME就采用了这种方案。



3.6高级加密标准

由于DES存在安全问题，而三重DES算法运行速度比较慢，三重DES迭代的轮数是DES的3倍，因此速度比DES慢很多。三重DES的分组长度为64位，就效率和安全性而言，分组长度应该更长。这就注定三重DES不能成为长期使用的加密标准。为此，美国国家标准技术研究所(NIST)在1997年公开征集新的高级加密标准（Advanced Encryption Standards，AES），要求AES比3DES快而且至少和3DES一样安全，并特别提出高级加密标准的分组长度为128位的对称分组密码，密钥长度支持128位、192位和256位。


1997年9月给出的选择高级加密标准的评估准则如下。

(1) 安全性： 由于AES最短的密钥长度是128位，所以使用目前的技术，穷举攻击是没有任何可能的。因此，AES应重点考虑是否能抵抗各种密码分析方法的攻击。

(2) 代价： 指计算效率方面。NIST期望AES能够广泛应用于各种实际应用，因此要求AES必须具有很高的计算效率。

(3) 算法和执行特征： 指算法的灵活性、简洁性以及硬件与软件平台的适应性等方面。1998年6月NIST共收到21个提交的算法，在同年的8月首先选出15个候选算法。1999年NIST从15个AES候选算法中遴选出5个候选算法，它们是： MARS（由IBM公司研究部门的一个庞大团队发布，对它的评价是算法复杂、速度快、安全性高）、RC6（由RSA实验室发布，对它的评价是极简单、速度极快、安全性低）、Rijndael（由Joan Daemen和 Vincent Rijmen 两位比利时密码专家发布，对它的评价是算法简洁、速度快、安全性好）、Serpent（由Ross Anderson、Eli Biham 和 Lars Knudsen发布，对它的评价是算法简洁、速度慢、安全性极高）和Twofish（由Counterpane公司的一个庞大的团队发布，对它的评价是算法复杂、速度极快、安全性高）。从全方位考虑，Rijndael(读成Rain Doll）汇聚了安全、性能、效率、易用和灵活等优点，使它成为AES最合适的选择。在2000年10月Rijndael算法被选为高级加密标准，并于2001年11月发布为联邦信息处理标准(Federal Information Processing Standard，FIPS)，用于美国政府组织保护敏感信息的一种特殊的加密算法，即FIPS PUB 197标准。



3.6.1AES的基本运算


第2章已经介绍了AES的主要数学基础，为了更好地理解AES的加密过程，这部分将介绍与AES相关的一些规定以及运算方法。AES算法中有些是以字节为单位进行运算的，也有的是以4字节（即一个字）为单位的。它将一字节看作是在有限域GF(28)上的一个元素，将一个字看作是系数取自GF(28)，并且次数小于4的多项式。



1. AES中的字节运算


在AES中，一字节是用有限域GF(28)上的元素表示。有限域上的元素有多种表示方法，AES主要采用多项式表示。


有限域GF(28)上的加法定义为二进制多项式的加法，其系数是模2相加。此处加法是异或运算(记为)，11＝0，10＝1，00＝0。因此，多项式减法与多项式加法的规则相同。对于两字节{a7a6a5a4a3a2a1a0}和{b7b6b5b4b3b2b1b0}，其和为{c7c6c5c4c3c2c1c0}，ci=aibi(即c7=a7b7，c6=a6b6，…，c0=a0b0)。



例如，下述表达式彼此相等。

(x6+x4+x2+x+1)+(x7+x+1)=x7+x6+x4+x2(多项式记法)

{01010111}{10000011}={11010100}(二进制记法)

{57}{83}={d4}（十六进制记法）


在有限域GF(28)上的乘法(记为·)定义为多项式的乘积模一个次数为8的不可约多项式： 

m(x)=x8+x4+x3+x+1

用十六进制表示该多项式为{01}{1B}。


例如，{57}·{83}={c1}，因为：


(x6+x4+x2+x+1)(x7+x+1)
=x13+x11+x9+x8+x7+x7+x5+x3+x2+x+x6+x4+x2+x+1
=x13+x11+x9+x8+x6+x5+x4+x3+1


而

(x13+x11+x9+x8+x6+x5+x4+x3+1) mod (x8+x4+x3+x+1)=x7+x6+1


模m(x)确保了所得结果是次数小于8的二进制多项式，因此可以用一字节表示。

如果a(x)·b(x) mod m(x)=1，则称b(x)为a(x)的逆元。


在AES中的倍乘函数xtime()是用多项式x乘一个二进制多项式后再模m(x)。

用多项式x乘以b(x)将得到：

b7x8+b6x7+b5x8+b4x8+b3x4+b2x3+b1x2+b0x



将上述结果模m(x)即可得到x·b(x)的结果。如果b7=0，则该结果已经是模运算后的形式。如果b7=1，则模运算需要异或多项式m(x)完成。由此，乘x(即{00000010}或十六进制{02})可通过字节内左移一位，紧接着的一个与{1B}按位异或来实现。将该操作记为 b=xtime(a)。通过将中间结果相加，可以用xtime()实现任意常数的乘法。


例如{57}·{13}={fe}，因为

{57}·{02}=xtime({57})={ae}

{57}·{04}=xtime({ae})={47}

{57}·{08}=xtime({47})={8e}

{57}·{10}=xtime({8e})={07}


因此

{57}·{13}={57}·({01}{02}{10})

={57}{ae}{07}

={fe}



2. AES中的字运算


AES中的32位字表示为系数在有限域GF(28)上的次数小于4的多项式。考虑含有4个项且系数为有限域元素的多项式，即

a(x)=a3x3+a2x2+a1x+a0


它可以表示为如下形式［a0，a1，a2，a3］的字(Word)。注意，这里的多项式与前面有限域元素定义中使用的多项式操作不同，即使这两类多项式均使用相同的变量x。这里的系数本身就是有限域元素，即字节(Bytes)而不是位(bits)。另外，该4项多项式的乘法使用了一个不同于前面的模多项式，将在下面定义。


为说明加法和乘法运算，令

b(x)=b3x3+b2x2+b1x+b0


为另一个4项多项式。加法是对x相应次数项的有限域系数进行相加运算。该加法对应于相应字节间的异或运算。

因此

a(x)+b(x)=(a3b3)x3+(a2b2)x2+(a1b1)x+(a0b0)


乘法要用两步完成。第1步，对多项式相乘的结果c(x)=a(x)·b(x)进行代数扩展： 

c(x)=c6x6+c5x5+c4x4+c3x3+c2x2+c1x+c0

其中:


c0=a0·b0c4=a3·b1a2·b2a1·b3
c1=a1·b0a0·b1c5=a3·b2a2·b3
c2=a2·b0a1·b1a0·b2c6=a3·b3
c3=a3·b0a2·b1a1·b2a0·b3




所得结果c(x)并没有表示为一个4字节的字。因此，乘法的第2步是模一个4次多项式来化简c(x)，使得结果化简为一个次数小于4的多项式。在AES算法中，这一模多项式取为x4+1，由于

xj mod (x4+1)=xj mod 4


则a(x)和b(x)取模的乘积记为a(x)b(x)，表示为下述的4项多项式d(x)，即

d(x)=d3x3+d2x2+d1x+d0

其中:



d0=a0·b0a3·b1a2·b2a1·b3
d1=a1·b0a0·b1a3·b2a2·b3
d2=a2·b0a1·b1a0·b2a3·b3
d3=a3·b0a2·b1a1·b2a0·b3


当a(x)是一个固定多项式时，等式中定义的运算可以写成矩阵形式，如

d0d1d2d3=a0a3a2a1a1a0a3a2a2a1a0a3a3a2a1a0b0b1b2b3


由于x4+1不是GF(28)上的不可约多项式，因此被一个固定的4次多项式相乘的乘法不一定可逆。然而，在AES算法中选择了一个固定的有逆元的4项多项式的乘法，它按照乘法运算有逆元。


a(x)={03}x3+{01}x2+{01}x+{02}
a-1(x)={0b}x3+{0d}x2+{09}x+{0e}


在AES算法的密钥扩展部分中还要用到的另一个多项式(RotWord()函数)为a0=a1=a2={00}，a3={01}，即多项式x3。该多项式的效果是将输入字中的字节循环移位来得到输出字，即［b0，b1，b2，b3］将变换为［b1，b2，b3，b0］。


3.6.2AES加密








a0a4a8a12
a1a5a9a13
a2a6a10a14
a3a7a11a15


图3.19128位（16字节）
的矩阵排列






在Rijndael算法中，分组长度和密钥长度可以分别是128位、192位和256位。而在AES中，分组长度只能是128位。AES算法中基本的运算单位是字节，即视为一个整体的8比特序列。如果分组长度和密钥长度为128位，假如字节数组将表示为如下形式。


a0，a1，a2，…，a15



其字节排列方式将如图3.19所示。

如果密钥长度（或在Rijndael中的明文分组）为192位、256位，组成的两个矩阵如图3.20和图3.21所示。它们的特点是行数都是4，列数不同。






a0a4a8a12a16a20
a1a5a9a13a17a21
a2a6a10a14a18a22
a3a7a11a15a19a23


图3.20192位（24字节）的矩阵排列








a0a4a8a12a16a20a24a28
a1a5a9a13a17a21a25a29
a2a6a10a14a18a22a26a30
a3a7a11a15a19a23a27a31


图3.21256位（32字节）的矩阵排列




这些矩阵有4行，分组的列数记为Nb，Nb=分组长度（位）÷ 32(位)。显然Nb可以取的值为4、6和8，分别对应的分组长度为128位、192位和256 位。类似地密钥的列数记为Nk，Nk=密钥长度（位）÷32(位)。Nk可以取的值为4、6和8，对应的密钥长度分别为128位、192位和256位。


密码运算的中间结果都是以上面的形式表示，称为状态（State）数组。AES将这些中间结果复制到状态（State）数组中。算法的运行过程是将需要加密的分组从一个状态转换为另一个状态，最后该数组被复制到输出矩阵中。如对于128位分组，假设加密和解密的初始阶段将输入字节数组in0，in1，…，in15复制到如图3.22所示的状态（State）矩阵中。加密或解密的运算都在该状态矩阵上进行，最后的结果将被复制到输出字节数组out0，out1，…，out15。






图3.22状态矩阵、输入和输出




状态矩阵中每一列的4字节可以看作一个32比特字，用行号r作为每一个字中4字节的索引。因此状态可以看作32比特字(列)，w0…w3的一维数组，用列号c表示该数组的索引。在图3.22中，该状态可以看作4个字组成的数组，如下所示： 


w0=s0，0s1，0s2，0s3，0w2=s0，2s1，2s2，2s3，2
w1=s0，1s1，1s2，1s3，1w3=s0，3s1，3s2，3s3，3


在加密和解密的初始阶段，输入数组in按照下述规则复制到状态矩阵中。

s［r，c］=in［r+4c］0≤r<4 且0≤c<Nb

在加密和解密的结束阶段，状态矩阵将按照下述规则被复制到输出数组out中。

out［r+4c］=s［r，c］0≤r<4 且0≤c<Nb


AES密码是一种迭代式密码结构，但不是 Feistel 密码结构。Rijndael算法迭代的轮数与分组长度和密钥长度相关。对于AES算法，算法的轮数依赖于密钥长度。将轮数表示为Nr，当Nk=4时Nr＝10； 当Nk=6时Nr＝12； 当Nk=8时Nr＝14。表3.5是Rijndael算法不同分组长度和密钥长度对应的迭代轮数列。




表3.5Rijndael算法迭代轮数



密钥长度
分组长度为128位
分组长度为192位
分组长度为256位


128位10轮12轮14轮
192位12轮12轮14轮
256位14轮14轮14轮






图3.23AES加密过程

当分组长度和密钥长度均为128位时，AES共迭代10轮，需要11个子密钥。其加密过程如图3.23所示。前面9轮完全相同，每轮包括4阶段，分别是字节代换（Byte Substitution）、行移位（Shift Rows）、列混淆（Mix Columns）和轮密钥加（Add Round Key），最后一轮只有三个阶段，缺少列混淆。


在加密时，将输入复制到状态矩阵中。经过初始轮子密钥加后，通过执行10轮来变换状态矩阵，最后状态将被复制到输出。图3.24是AES加密算法的伪代码表示，每一个变换如SubBytes（）、ShiftRows（）、MixColumns（）和AddRoundKey（）都作用在状态(State)上，数组w［］中包含了密钥编排得到的密钥，这些将后面部分说明。除了最后一轮，所有的轮变换均相同。最后一轮不包括MixColumns（）变换。

下面是AES中出现的一些参数、符号和函数。

AddRoundKey()是加密和解密中使用的变换，它将一个轮密钥异或到状态上。轮密钥的长度等于状态的大小(即对于Nb=4，轮密钥长度等于128比特/16字节)。




InvMixColumns()解密中使用的变换，是MixColumns()的逆变换。

InvShiftRows()解密中使用的变换，是ShiftRows()的逆变换。

InvSubBytes()解密中使用的变换，是SubBytes()的逆变换。

K密码所使用的秘密密钥。

MixColumns()加密中使用的变换，以状态的每一列作为输入，混合每一列的数据(彼此独立的)得到新的列。

Nb状态包含的列(32比特字)的个数。对于AES，Nb＝4。

Nk密钥包含的32比特字的个数。对于该标准，Nk＝4，6或8。

Nr轮数，是Nk和Nb(固定的)的函数。对于该标准，Nr＝10，12或14(参见第6.3节)。

Rcon［］密钥扩展算法中用到的轮常数。

RotWord()密钥扩展算法中使用的函数，对4字节字进行循环移位。

ShiftRows()加密中使用的变换，将状态的最后3行循环移动不同的位移量。

SubBytes()加密中使用的变换，利用一个非线性字节替代表(S盒)，独立地对状态的每字节进行操作。

SubWord()密钥扩展算法中使用的函数，它以4字节字作为输入，对于4字节中的每字节分别应用S盒，得到一个输出字。

XOR异或运算。

异或运算。

两个多项式(每一个的度(Degree)均小于4)相乘再模x4+1。

有限域上的乘法。



Cipher(byte in［4*Nb］，byte out［4*Nb］，word w［Nb*(Nr+1)］)

begin

byte state［4，Nb］
state=in
AddRoundKey(state，w［0，Nb-1］)
for round=1 step 1 to Nr-1

SubBytes(state)

ShiftRows(state)

MixColumns(state)

AddRoundKey(state，w［round*Nb，(round+1)*Nb-1］)
end for
SubBytes(state)

ShiftRows(state)

AddRoundKey(state，w［Nr*Nb，(Nr+1)*Nb-1］)
out=state

end






图3.24AES加密算法伪代码



3.6.3字节代换

字节代换(SubBytes())是非线性的，它独立地将状态中的每字节利用代换表(S盒)进行运算。S盒被设计成能够抵挡所有已知的攻击。该S盒（见图3.25）是由16×16字节组成的矩阵，包含了8位值所能表达的256种可能的变换。State中的每字节按照如下的方式映射为一个新的字节： 将该字节的高4位作为行值，低4位作为列值，然后取出S盒中对应行列交叉处的元素作为输出。例如，十六进制{95}对应的S盒的行值是9，列值是5，S盒中此处的值是{2A}。因此{95}被映射为{2A}。

S盒按照如下的方式构造。 

(1) 逐行按照上升排列的方式初始化S盒。第一行是{00}，{01}，…，{0F}； 第二行是{10}，{11}，…，{1F}等。因此在x行y列的字节值是{xy}。

(2) 把S盒中的每字节映射为它在有限域GF(28)上的乘法逆； 其中，元素{00}映射到它自身{00}。




y

0123456789ABCDEF

x

0637C777BF26B6FC53001672BFED7AB76

1CA82C97DFA5947F0ADD4A2AF9CA472C0
2B7FD9326363FF7CC34A5E5F171D83115
304C723C31896059A071280E2EB27B275
409832C1A1B6E5AA0523BD6B329E32F84
553D100ED20FCB15B6ACBBE394A4C58CF
6D0EFAAFB434D338545F9027F503C9FA8
751A3408F929D38F5BCB6DA2110FFF3D2
8CD0C13EC5F974417C4A77E3D645D1973
960814FDC222A908846EEB814DE5E0BDB
AE0323A0A4906245CC2D3AC629195E479
BE7C8376D8DD54EA96C56F4EA657AAE08
CBA78252E1CA6B4C6E8DD741F4BBD8B8A
D703EB5664803F60E613557B986C11D9E
EE1F8981169D98E949B1E87E9CE5528DF
F8CA1890DBFE6426841992D0FB054BB16




图3.25S盒





(3) 把S盒中的每字节表示为(b7，b6，b5，b4，b3，b2，b1，b0
)8位，对S盒中的每字节中的每位做如下变换： 

b′i=bib(i+4) mod 8b(i+5) mod 8b(i+6) mod 8b(i+7) mod 8ci


其中，对于0≤i<8，bi是字节的第i位，ci是值为{63}或{01100011}的字节c的第i位。在此处和其他地方，在变量的右上角做标记（如b′）表示该变量将用右侧的值更新。AES按照如下的方式用矩阵描述S盒的变换。


b′0
b′1
b′2
b′3
b′4
b′5
b′6
b′7
=

10001111
11000111
11100011
11110001
11111000
01111100
00111110
00011111


b0
b1
b2
b3
b4
b5
b6
b7

11000110




还是用{95}作为输入，可以计算出{95}在GF(28)上的逆为{8A}，用二进制表示为10001010，代入上述变换：


10001111
11000111
11100011
11110001
11111000
01111100
00111110
00011111


01010001


11000110
=

10010010


11000110
=

01010100




结果为00101010，用十六进制表示为{2A}，与前面查表所得结果一样。


3.6.4行移位

行移位(ShiftRows())是一个简单的置换，在行移位变换中，对State的各行进行循环左移位，State的第一行保持不变，第二行循环左移一字节，第三行循环左移两字节，第四行循环左移三字节，如图3.26所示。



图3.26对State的各行移位





对Rijndael而言，分组长度是128位、196位或256位。移位的字节数与分组的大小有关系。后三行的左移量C1、C2、C3与分组长度Nb(矩阵的列数)的关系如表3.6所示。




表3.6移位值



NbC1C2C3


4123
6123
8134




3.6.5列混淆


列混淆(MixColumns())变换在State上按照每一列（即对一个字）进行运算，并将每一列看作4次多项式，即将State的列看作GF(28)上的多项式且被一个固定的多项式a(x)模x4+1乘，a(x)为：

a(x)={03}x3+{01}x2+{01}x+{02}


这可以写成矩阵乘法。令s′(x)=a(x)s(x)： 


s′0，cs′1，cs′2，cs′3，c=02030101010203010101020303010102s0，cs1，cs2，cs3，c0≤c<Nb


经过该乘法计算后，一列中的4字节将由下述结果取代： 

s′0，c=({02}·s0，c)({03}·s1，c)s2，cs3，c

s′1，c=s0，c({02}·s1，c)({03}·s2，c)s3，c

s′2，c=s0，cs1，c({02}·s2，c)({03}·s3，c)

s′3，c=({03}·s0，c)s1，cs2，c({02}·s3，c)

图3.27为列混淆变换示意图。




图3.27列混淆变换示意图



例3.9假设State矩阵的第一列分别是s0，0={87}，s1，0={6E}，s2，0={46}，s3，0={A6}。经过列混淆变换后，s0，0={87}映射为s′0，0={47}，试计算验证这一结果。


第1列第1字节的代换方程为：

({02}·{87})({03}·{6E}){46}{A6}={47}


下面验证上面等式成立。用多项式表示为：


{02}=x
{87}=x7+x2+x+1

那么

x·(x7+x2+x+1)=x8+x3+x2+x

再模一个次数为8的不可约多项式：


m(x)=x8+x4+x3+x+1
(x8+x3+x2+x) mod (x8+x4+x3+x+1)=x4+x2+1


写成二进制形式为00010101。


同样可以计算出{03}·{6E}=10110010，{46}=01000110，{A6}=10100110。因此({02}·{87})({03}·{6E}){46}{A6}计算结果为：

0001 0101

1011 0010

0100 0110

1010 0110




0100 0111={47}


3.6.6轮密钥加


在轮密钥加(AddRoundKey())变换中，128位的State按位与128位子密钥异或。可以将这种操作看成是State一列中的4字节与轮密钥的一个字进行异或，也可以看成是两者之间的字节异或。


3.6.7AES的密钥扩展

如果分组长度和密钥长度都是128位，AES的加密算法共迭代10轮，需要11个子密钥。AES的密钥扩展的目的是将输入的128位密钥扩展成11个128位的子密钥。AES的密钥扩展算法是以字为一个基本单位，而不是以位为操作对象。一个字等于4字节，共32位，刚好是密钥矩阵的一列。因此4个字（128位）密钥需要扩展成11个子密钥，共44个字。若Nr表示加密算法轮数，那么密钥扩展总共生成Nb(Nr+1)个字，并需要一个Nb个字组成的初始集合（即原始密钥），为每一轮产生Nb个字的子密钥。扩展后的密钥编排结果由一个4字节字的线性数组组成，记为［wi］，其中0≤i<Nb(Nr+1)。图3.28是AES的密钥扩展算法的伪码表示。

SubWord（）函数将接受一个4字节输入字，对每一字节应用S盒得到输出字。函数RotWord（）接受字［a0，a1，a2，a3］作为输入，执行循环移位后返回字［a1，a2，a3，a0］。轮常数字数组Rcon［i］，包含了由
［xi-1，{00}，{00}，{00}］给定的值(注意这里的i从1开始，而不是0)，xi-1是有限域GF(28)上x(x记为{02})的指数幂。

如图3.28所示，第一个子密钥的Nk个字由密码的原始密钥直接填充。接下来的每个字w［i］，等于其前一个字w［i-1］与Nk个位置之前的字w［i-Nk］的异或。对于Nk的整数倍位置的字，在异或之前，要对w［i-1］进行一次变换，该变换先进行一次字的字节左循环移位(RotWord（）)，然后再做一次字节替代变换(SubWord（）)，即对字中的4字节应用查表。再异或一个轮常数。



KeyExpansion(byte key［4*Nk］，work w［Nb*(Nr+1)］，Nk)

begin

word temp
i=0
while(i<Nk)

w［i］=word(key［4*i］，key［4*i+1］，key［4*i+2］，key［4*i+3］)

i=i+1

end while
i=Nk
while(i<Nb*(Nr+1))

temp=w［i-1］

if(i mod Nk=0)

temp=SubWord(RotWord(temp))xor Rcon［i/Nk］

else if(Nk>6 and i mod Nk=4)

temp=SubWord(temp)

end if

w［i］=w［i-Nk］xor temp

i=i+1

end while

end






图3.28AES密钥扩展伪代码






需要注意的是，256比特密钥(Nk＝8)的密钥扩展程序与128比特和192比特密钥的扩展程序稍有不同。如果Nk＝8且i-4是Nk的整数倍，异或之前对w［i-1］要做一次字节替代(SubWord（）)变换。


下面以Nk＝4（即密钥为128位）为例，先概括AES的密钥扩展过程，随后将给出密钥扩展的例子。


密钥扩展过程如下。



(1) 将输入密钥直接复制到扩展密钥数组的前4个字中，得到w［0］、w［1］、w［2］、w［3］。

(2) 每次用4个字填充扩展密钥数组w的余下部分，w［i］值依赖于 w［i-1］和w［i-4］，i≥4。

(3) 当数组w下标不是4的倍数时，w［i］值为 w［i-1］和 w［i-4］ 的异或。

(4) 当数组w下标为4的倍数时，按照下面方法计算： 


① 将wi-1的一个字的4字节循环左移一字节，即将输入字［b0,b1,b2,b3］变为［b1,b2,b3,b0］。

② 用S盒对输入字的每字节进行字节代换。

③ 将wi-4异或步骤①和步骤②的结果，再与轮常数Rcon［i］相异或。

轮常数Rcon［i］是一个字，这个字的最右边三字节总是0。因此与轮常数的一个字异或，其结果是与该字最左边的字节相异或。每轮的轮常数均不同，其定义为Rcon［i］=(RC［i］，{00}，{00}，{00})，其中RC［1］={01}，RC［i］={02}
·(RC［i-1］)，用多项式表示为RC［i］=x·(RC［i-1］)=xi-1，i≥2。


字节用十六进制表示，同时理解为GF(28)上的元素。xi-1为GF(28)中的多项式x的i-1次方所对应的字节。考虑x对应的字节为{02}，轮常数也可以写为：

Rcon［i］=((02)i-1，{00}，{00}，{00})


前10个轮常数RC［i］的值如表3.7所示，对应的Rcon［i］ 如表3.8所示。



表3.7RC［i］



i12345678910
RC［i］01020408102040801B36





表3.8Rcon［i］



i12345
Rcon［i］0100000002000000040000000800000010000000
i678910
Rcon［i］200000040000000800000001B00000036000000



例3.10AES的加密密钥为2B 7E 15 16 28 AE D2 A6 AB F7 15 88 09 CF 4F3C，Nk=4，写出扩展后前三个子密钥。


直接得到第一个子密钥的4个字为w［0］=2B7E1516，w［1］=28AED2A6，w［2］=ABF71588，w［3］=09CF43C。第二个和第三个子密钥扩展如表3.9所示。




表3.9密钥扩展例子



iw［i-1］RotWord()后SubWord()后Rcon［i/Nk］与Rcon

异或后w［i-Nk］w［i］=w［i-1］

 w［i-Nk］

409CF4F3CCF4F3C098A84EB01010000008B84EB012B7E1516A0FAFE17
5A0FAFE1728AED2A688542CB1
688542CB1ABF7158823A33939
723A3393909CF4F3C2A6C7605
82A6C76056C76052A50386BE50200000052386BE5A0FAFE17F2C29512
9F2C2951288542CB17A96B943
107A96B94323A339395935807A
115935807A2A6C76057359F67F




3.6.8AES解密算法

AES解密算法是AES加密算法的逆变换，其结构类似于加密算法。解密算法和加密算法轮结构的顺序不同。但是加密和解密算法中的密钥编排形式相同。在加密过程中，其轮结构是字节代换、行移位、列混淆和轮密钥加。在解密过程中，其轮结构是逆向行移位、逆向字节代换、轮密钥加和逆向列混淆。图3.29描述了解密算法的伪代码。



InvCipher(byte in［4*Nb］，byte out［4*Nb］，word w［Nb*(Nr+1)］)

begin

byte state［4，Nb］
state=in
AddRoundKey(state，w［Nr*Nb，(Nr+1)*Nb-1］)
for round=Nr-1 step-1 downto 1

InvShiftRows(state)

InvSubBytes(state)

AddRoundKey(state，w［round*Nb，(round+1)*Nb-1］)

InvMixColumns(state)

end for
InvShiftRows(state)

InvSubBytes(state)

AddRoundKey(state，w［0，Nb-1］)
out=state

end






图3.29AES解密算法的伪代码



1. 逆向行移位

逆向行移位(InvShiftRows())是行移位(ShiftRows())的逆变换。对State的各行按照一定量进行循环移位。当Nb=4或者6时，第0行不移位； 第1行循环右移1位； 第2行循环右移2位； 第3行循环右移3位。




2. 逆向字节代换

逆向字节代换(InvSubBytes())是字节代换(SubBytes())的逆变换，对State的每字节应用逆S盒进行代换。逆字节替代变换中使用的逆S盒如图3.30所示。






y
0123456789ABCDEF

x


052096AD53036A538BF40A39E81F3D7FB
17CE339829B2FFF87348E4344C4DEE9CB

2547B9432A6C2233DEE4C950B42FAC34E

3082EA16628D924B2765BA2496D8BD125

472F8F66486689816D4A45CCC5D65B692
56C704850FDEDB9DA5E154657A78D9D84
690D8AB008CBCD30AF7E45805B8B34506

7D02C1E8FCA3F0F02C1AFBD0301138A6B
83A9111414F67DCEA97F2CFCEF0B4E673
996AC7422E7AD3585E2F937E81C75DF6E
A47F11A711D29C5896FB7620EAA18BE1B
BFC563E4BC6D279209ADBC0FE78CD5AF4
CIFDDA8338807C731B11210592780EC5F
D60517FA919B54A0D2DE57A9F93C99CEF
EA0E03B4DAE2AF5B0C8EBBB3C83539961
F172B047EBA77D626E169146355210C7D




图3.30逆S盒



3. 轮密钥加

轮密钥加变换，其逆变换就是它本身，因为其中只应用了异或运算。


4. 逆向列混淆 

逆向列混淆(InvMixColumns())是列混淆(MixColumns())的逆变换。逆向列混淆在State上对每一列进行运算，将State的列看作GF(28)上的多项式且被一个固定的多项式a-1(x)模x4+1乘，a-1(x)为：

a-1(x)={0b}x3+{0d}x2+{09}x+{0e}


可以写成矩阵乘法。令s′(x)=a-1(x)s(x)： 

s′0，cs′1，cs′2，cs′3，c=0e0b0d09090e0b0d0d090e0b0b0d090es0，cs1，cs2，cs3，c0≤c<Nb


经过该乘法计算后，一列中的4字节将由下述结果取代： 


s′0，c=({0e}·s0，c)({0b}·s1，c)({0d}·s2，c)({09}·s3，c)
s′1，c=({09}·s0，c)({0e}·s1，c)({0b}·s2，c)({0d}·s3，c)
s′2，c=({0d}·s0，c)({09}·s1，c)({0e}·s2，c)({0b}·s3，c)
s′3，c=({0b}·s0，c)({0d}·s1，c)({09}·s2，c)({0e}·s3，c)


3.6.9等价的解密变换


在第3.6.8节描述的解密算法中，其各个变换的操作顺序与加密算法不同，但是加密和解密算法中的密钥编排形式相同。其缺点是对同时要求加密和解密的应用而言，需要两个不同的软件或者固件模块。因此，需要构造一个等价的解密算法，解密时各个变换的操作顺序与加密(由逆向变换取代原来的变换)相同。为了达到这个要求，需要对密钥扩展进行改进。

通过两处改进可以使解密算法结构和加密算法结构一致。前面已经提到，加密算法和解密算法的轮结构顺序不同，如果将解密轮中的前两个变换阶段交换，后两个变换阶段也交换就能保证解密算法结构和加密算法结构相同。


1. 交换逆向行移位和逆向字节代换

字节代换和行移位的顺序不影响结果。先进行行字节代换，再进行行移位等价于先进行行移位，再进行字节代换。对于逆向行移位和逆向字节代换同样成立，因此可以将这两个操作交换。


2. 交换轮密钥加和逆向列混淆


轮密钥加和逆向列混淆并不改变State中的字节顺序。如果将密钥看成是字的序列，那么轮密钥加和逆向列混淆每次都是对State的一列进行操作。列混淆(MixColumns())和逆向列混淆(InvMixColumns())运算是关于列输入的线性变换，那么

InvMixColumns（State Round Key）＝InvMixColumns（State）

InvMixColumns（Round Key）


这表明密钥加和逆向列混淆可以互换，只要将解密中密钥编排得到的密钥列（字）应用InvMixColumns()变换进行修改即可。


AES等价解密算法如图3.31所示。算法将InvSubBytes()变换和InvShiftRows()变换的顺序反转过来，同时当利用InvMixColumns()变换时，修改了1~Nr-1轮的解密密钥编排结果后，并将“轮循环”中使用的AddRoundKey()变换和InvMixColumns()变换的顺序反转。解密密钥编排结果的第一个和最后一个Nb字将不使用该方式进行修改。字数组dw［ ］中包含了修改过的解密密钥编排结果。图3.31中也显示了我们对密钥扩展程序的修改。



EqInvCipher(byte in［4*Nb］，byte out［4*Nb］，word dw［Nb*(Nr+1)］)

begin

byte state［4，Nb］
state=in
AddRoundKey(state，dw［Nr*Nb，(Nr+1)*Nb-1］)
for round=Nr-1 step -1 downto 1

InvSubBytes(state)

InvShiftRows(state)

InvMixColumns(state)

AddRoundKey(state，dw［round*Nb，(round+1)*Nb-1］)

end for
InvSubBytes(state)

InvShiftRows(state)

AddRoundKey(state，dw［0，Nb-1］)

out=state

end
下面的伪代码加在密钥扩展算法后面：
for i=0 step 1 to (Nr+1)*Nb-1

dw［i］=w［i］

end for

for round=1 step 1 to Nr-1

InvMixColumns(dw［round*Nb，(round+1)*Nb-1］)

end for






图3.31AES等价解密算法



3.6.10AES的安全性

AES的设计的各个方面都使它具有能够抵抗所有已知攻击的能力。AES的轮函数设计为基于宽轨迹策略(Wide Trail Strategy)，这种设计策略是针对差分密码分析和线性密码分析的。AES的轮函数设计主要包括两个设计准则： 一是选择差分均匀性比较小和非线性度比较高的S盒； 二是适当选择线性变换，使得固定轮数中的活动S盒的个数尽可能多。如果差分特征(或线性逼近)中某一轮的活动S盒的个数比较少，那么下一轮中的活动S盒的个数就必须要多一些。宽轨迹策略的最大优点是可以估计算法的最大差分特征概率和最大线性逼近概率，由此可以评估算法抵抗差分密码分析和线性密码分析的能力。另外，AES的密钥长度也足以抵抗穷举密钥攻击，并且AES算法对密钥的选择没有任何限制，还没有发现弱密钥和半弱密钥的存在。

3.7中国商用对称密码算法——SM4

SM4原名为SMS4，是由国家密码管理局于2012年3月发布的对称加密算法，具有较好的抗破解能力。SM4是分组对称密码算法，分组长度和密钥长度为128比特。SM4算法的S盒设计已经达到欧美分组密码标准算法S盒的设计水准，具有较好平衡性和非线性,但其算法的整体安全特性还有待进一步研究。SM4算法的提出，无论是对无线局域网产业还是对商用密码研究都有非常重要的意义，极大地推进了对密码算法的研究及其开发本土化的进程。

3.7.1SM4加密

SM4算法是一个采用非均衡的Feistel结构的分组算法，分组长度为128位，密钥长度也为128位。SM4算法中数据处理单位包括字和字节，一个字为4字节，每字节为8比特序列，即一个字为32比特序列。加密算法与密钥扩展算法都采用32轮非线性迭代结构，明文和密文分组都用字表示，128位分组明文和密文表示4个32比特的字，明文记为X0,X1,X2,X3 4个字，密文记为Y0,Y1,Y2,Y3。SM4算法与DES一样采用Feistel结构，但SM4算法左右两边是不均衡的，例如，一边为1个字，另一边则为3个字，下一轮则反过来。SM4加密过程如图3.32所示。128位明文分组用4个字表示，经过32轮迭代后，再进行反序变换，输出即为密文。



图3.32SM4加密过程


1. 基本运算

SM4算法中，采用了两种基本运算： “”表示32比特异或运算，“<<<i”表示32比特循环左移i位。

2. SM4每轮结构

SM4每轮的结构如图3.33所示。上一轮的数据(Xi-1,Xi,Xi+1,Xi+2)，i=1,2,…,32。 循环左移32位即1个字，然后利用加密函数（又称轮函数）F，得到Xi+3=F(Xi-1,Xi,Xi+1,Xi+2,rki-1)。因此，此轮输出(Xi,Xi+1,Xi+2,Xi+3)作为下一轮迭代的输入。如此迭代32轮后，得到输出数据为(X32,X33,X34,X35)。再做反序变换R，得到最终密文： (Y0,Y1,Y2,Y3)=R(X32,X33,X34,X35)=(X35,X34,X33,X32)。



图3.33SM4加密每轮的结构


3. 加密函数F

加密函数F为F(Xi-1,Xi,Xi+1,Xi+2,rki-1)=Xi-1T(XiXi+1Xi+2rki-1)，其中合成置换T是一个可逆变换，由非线性变换τ和线性变换L构成,rki-1为轮密钥。加密函数F的计算过程为： 输入数据的Xi-1与合成置换T的输出做异或运算即可。合成置换T的过程如图3.34所示。 



图3.34合成置换T


τ是由4个相同的八进八出S盒并置而成，每一轮XiXi+1Xi+2rki-1进行计算后，假设得到结果记为32位的A=(a0,a1,a2,a3)，a0、a1、a2、a3每个8位，分为4组进入S盒，输出为B=(b0,b1,b2,b3)=τ(A)=(S(a0),S(a1),S(a2),S(a3))。

S盒为固定的8比特输入8比特输出的置换，记为S(.)，如图3.35所示。S盒中的数据都是通过十六进制表示的，它的置换规则是： 以输入的前半字节为行号，后半字节为列号，行列交叉点处的数据即为输出。

举例： 若输入“ef”，则经S盒后的值为表中第e行和第f列的值，S(ef)=84。

非线性变换τ的输出是线性变换L的输入。设输入为B，单位为字，输出为C，单位为字，则C=L(B)=B(B<<<2)(B<<<10)(B<<<18)(B<<<24)。





0123456789abcdef
0d690e9fecce13db716b614c228fb2c05

12b679a762abe04c3aa44132649860699
29c4250f491ef987a33540b43edcfac62
3e4b31ca9c908e89580df94fa758f3fa6
44707a7fcf37317ba83593c19e6854fa8
5686b81b27164da8bf8ed0f4b70569d35
6le240e5e6358d1a225227c3b01217887
7 d40046579fd327524c3602e7a0c4c89e
8eabf8ad240c738b5a3f7f2ceD 6115al
9 e0ae5da49634la55ad933230f58cble3
aIdf6e22e8266ca60c02923ab0d534e6f
bd5db3745defd8e2f03ff6a726d6c5b51
c8d1baf92bbddbc7f11d95c411f105ad8
d0ac13188a5cd7bbd2d74d012b8e5b4b0
e8969974aOc96777e65b9f1 09c56ec684
f18f07dec3adc4d2079ee5f3ed7cb3948

图3.35SM4的S盒




3.7.2密钥扩展算法

SM4加密算法的轮密钥由加密密钥通过密钥扩展算法生成。加密密钥由4个字，128位组成，表示为MK=(MK0,MK1,MK2,MK3)，其中MKi(i=0,1,2,3)为字。轮密钥表示为(rk0,rk1,…,rk31)，其中rki(i=0,1,2,…,31)为字。

FK=(FK0,FK1,FK2,FK3)为系统参数，CK=(CK0,CK1,…,CK31)为固定参数，用于密钥扩展算法，其中FKi(i=0,1,2,3)、CKi(i=0,1,…,31)为字。

令Ki(i=0,1,…,35)为字，轮密钥生成方法如图3.36所示。 



图3.36SM4轮密钥生成


首先，(K0,K1,K2,K3)=(MK0FK0,MK1FK1,MK2FK2,MK3FK3)，

然后，对i=0,1,2,…,31，rki=Ki+4=KiT′(Ki+1Ki+2Ki+3CKi)。

说明： 

(1) T′变换与加密算法轮函数中的T基本相同，只将其中的线性变化Ｌ修改为以下的L′： 


L′(Β)=Β(Β<<<13)(Β<<<23)；


(2) 系统参数FK的取值，采用十六进制表示为： 

FK0=(A3B1BAC6),FK1=(56AA3350)
FK2=(677D9197),FK3=(B27022DC)

(3) 固定参数CK的取值方法为： 

设cki,j为CKi的第j字节(i=0,1,…,31； j=0,1,2,3)，即CKi=(cki,0,cki,1,cki,2,cki,3)，则cki,j=(4i+j)×7(mod 256)。32个固定参数CKi，其十六进制表示为： 

00070e15, 1c232a31, 383f464d, 545b6269, 

70777e85, 8c939aa1, a8afb6bd, c4cbd2d9, 

e0e7eef5, fc030a11, 181f262d, 343b4249, 

50575e65, 6c737a81, 888f969d, a4abb2b9, 

c0c7ced5, dce3eaf1, f8ff060d, 141b2229, 

30373e45, 4c535a61, 686f767d, 848b9299, 

a0a7aeb5, bcc3cad1, d8dfe6ed, f4fb0209, 

10171e25, 2c333a41, 484f565d, 646b7279

例3.11按照 SM4加密算法，对一组明文（01 23 45 67 89 ab  def fe dc ba 98 76 54 32 10）用密钥加密一次。加密密钥：  01 23 45 67 89 ab  def fe dc ba 98 76 54 32 10。其中，数据采用十六进制表示。求每一轮的轮密钥、每轮最后32位的输出状态以及最终的密文。

解： （1） 第一轮轮密钥rk0的计算过程如下。 

① 将加密密钥MK=(MK0,MK1,MK2,MK3)按字分为4组，分别为：

MK0=(01234567),
MK1=(89abcdef),
MK2=(fedcba98),
MK3=(76543210)

已知FK0=(A3B1BAC6),FK1=(56AA3350),FK2=(677D9197),FK3=(B27022DC)
(K0,K1,K2,K3)=(MK0FK0,MK1FK1,MK2FK2,MK3FK3)。


求出(K0,K1,K2,K3)各个的值： 

MK0=0000 0001 0010 0011 0100 0101 0110 0111
FK0=1010 0011 1011 0001 1011 1010 1100 0110

两者做异或运算后，得：

K0=1010 0010 1001 0010 1111 1111 1010 0001

同理计算，可以分别得：

K1=1101 1111 0000 0001 1111 1110 1011 1111
K2=1001 1001 1010 0001 0010 1011 0000 1111
K3=1100 0100 0010 0100 0001 0000 1100 1100

② 求出T′变换的输出。 

固定参数CK0的十六进制表示为00070e15。则通过异或运算A=(a0,a1,a2,a3)=K1K2K3CK0=（1000 0010 1000 0011 1100 1011 0110 1001），十六进制表示为82 83 cb 69。

再将输出结果A分为4组进入S盒，通过查表，输出B的十六进制为8a d2 41 22。

利用公式L′(Β)=Β (Β<<<13)(Β<<<23)，得：

L′(Β)=0101 0011 1011 0011 0111 1001 0101 1000

③ 利用公式rki=Ki+4=KiT′(Ki+1Ki+2Ki+3CKi)，得到：

rk0=K4=K0T′(B)=1111 0001 0010 0001 1000 0110 1111 1001，十六进制表示为f1 21 86 f9。

（2） 根据第1轮轮密钥rk0的计算结果，将128位的明文同样分组，利用加密函数F(Xi-1,Xi,Xi+1,Xi+2,rki-1)=Xi-1T(XiXi+1Xi+2rki-1)，得到第1轮X4的输出状态为27 fa d3 45。

（3） 按照第（1）步和第（2）步计算，能够求出每轮的轮密钥和后32位的输出状态。 

rk0=f12186f9X4=27fad345，rk1=41662b61X5=a18b4cb2

rk2=5a6ab19aX6=11c1e22a，rk3=7ba92077X7=cc13e2ee

rk4=367360f4X8=f87c5bd5，rk5=776a0c61X9=33220757

rk6=b6bb89b3X10=77f4c297，rk7=24763151X11=7a96f2eb

rk8=a520307cX12=27dac07f，rk9=b7584dbdX13=42dd0f19

rk10=c30753edX14=b8a5da02，rk11=7ee55b57X15=907127fa

rk12=6988608cX16=8b952b83，rk13=30d895b7X17=d42b7c59

rk14=44ba14afX18=2ffc5831，rk15=104495a1X19=f69e6888

rk16=d120b428X20=af2432c4，rk17=73b55fa3X21=ed1ec85e

rk18=cc874966X22=55a3ba22，rk19=92244439X23=124b18aa

rk20=e89e641fX24=6ae7725f，rk21=98ca015aX25=f4cba1f9


rk22=c7159060X26=1dcdfa10，rk23=99e1fd2eX27=2ff60603

rk24=b79bd80cX28=eff24fdc，rk25=1d2115b0X29=6fe46b75

rk26=0e228aebX30=893450ad，rk27=f1780c81X31=7b938f4c

rk28=428d3654X32=536e4246，rk29=62293496X33=86b3e94f

rk30=01cf72e5X34=d206965e，rk31=9124a012X35=681edf34



（4） 按照(Y0,Y1,Y2,Y3)=R(X32,X33,X34,X35)=(X35,X34,X33,X32)，得到的密文结果为68 1e df 34 d2 06 96 5e 86 b3 e9 4f 53 6e 42 46。

3.7.3SM4解密

SM4的解密变换与加密变换结构相同，不同的仅是轮密钥的使用顺序。

 加密时轮密钥的使用顺序为： (rk0,rk1,…,rk31)

 解密时轮密钥的使用顺序为： (rk31,rk30,…,rk0)

3.7.4SM4的安全性

SM4算法是由中国国家专业机构设计，自2006年公布后，SM4分组密码引起了国内外学术界和产业界的极大关注，先后有学者研究了SM4对差分故障攻击、积分攻击、不可能差分密码分析、代数攻击、矩阵攻击、差分密码分析、线性密码分析等分析方法的安全性。至今为止，从专业机构对SM4进行的密码分析来看，SM4算法还是安全的，虽然有学者提出21轮SM4在受到差分密码分析和差分能量分析的攻击时将面临威胁，但尚需经过实践检验。

3.8RC6

RC6是RSA公司提交给NIST的一个候选高级加密标准算法，它是在RC5的基础上设计的。RC6继承了RC5的优点。为了使它符合高级加密标准，RC6在RC5基础上将分组长度扩展成128位，用4个32位区块代替RC5的两个32位区块。RC6是参数可变的分组密码算法，3个可变的参数是： 分组大小、密钥大小和加密轮数。RC6常常写为RC6w/r/b，其中w是字的大小，以位为单位，r为加密轮数，允许值是0，…，255，b为密钥长度，单位是字节，0≤b≤255。例如RC632/16/10 表示字长为32位，迭代的轮数是16，密钥长度为10字节。由于高级加密标准的要求是w=32，r=20，因此满足AES的RC6算法是RC632/20/16，也就是4个32位字(128位)，迭代的轮数为20，密钥长度16字节。RC6定义了6种运算基本操作，以2为底的对数表示为lgw。


a+b： 模2w整数加。

a-b： 模2w整数减。

a⊕b： w位的字按位异或。

a×b： 模2w整数乘。

a <<<b： 循环左移w位的字a，移动位数由b的低位lgw位决定。

a>>>b： 循环右移w位的字a。



3.8.1RC6的加密和解密

RC6和RC5在加解密方面是不一样的，RC6用这4个w位寄存器A、B、C、D来存放输入的明文和输出的密文。明文和密文的第一字节放在A的最低字节（即第一字节），明文和密文的最后一字节放在D的最高字节（即最后一字节）。RC6的加密过程如图3.37所示，其中f(x)=x×(2x+1)。加密算法和解密算法分别如图3.38和图3.39所示。



图3.37RC6的加密过程





RC6w/r/b加密

输入： 明文存入4个w位寄存器A、B、C、D

轮数r

w位轮密钥S［0，1，…，2r+3］

输出： 密文存入4个w位寄存器A、B、C、D

过程： B=B+S［0］

D=D+S［1］

for i=1 to r do

{

t=(B×(2B+1))<<<lgw

u=(D×(2D+1))<<<lgw

A=((At)<<<u)+S［2i］

C=((Cu)<<<t)+S［2i+1］

(A，B，C，D)=(B，C，D，A)

}

A=A+S［2r+2］

C=C+S［2r+3］





图3.38RC6加密算法








RC6w/r/b解密

输入： 密文存入4个w位寄存器A、B、C、D

轮数r

w位轮密钥S［0，1，…，2r+3］

输出： 明文存入4个w位寄存器A、B、C、D

过程： C=C-S［2r+3］

A=A-S［2r+2］

for i=r downto 1 do

{

(A，B，C，D)=(D，A，B，C)

u=(D×(2D+1))<<<lgw

t=(B×(2B+1))<<<lgw

C=((C-S［2i+1］)>>>t)u

A=((A-S［2i］)>>>u)t

}

D=D-S［1］

B=B-S［0］





图3.39RC6解密算法


3.8.2密钥扩展

密钥扩展算法是从密钥K中导出2r+4个字长的密钥，储存在数组S［0，…，2r+3］中用于加密和解密。在这其中用到了两个常量Pw和Qw，Pw和Qw大小是一个字长，定义如下所示。 


Pw=Odd((e-2)2w)

Qw=Odd((φ-2)2w)

其中，e=2.7182818284…(自然对数),φ=1.61803398874…(黄金分割)，Odd(x)是离x最近的奇数。



密钥扩展时，首先将密钥K［0，…，b-1］放入c个w位字的另一个数组L［0，…，c-1］中，其中,c为b/u的整数部分，u=w/8，即L数组上的元素大小为uw位。将u个连续字节的密钥顺序放入L中，先放入L中的低字节，再放入其高字节。如果L未填满，用0填充。当b=0，c=0时，c=1，L［0］=0。

 其次利用Pw和Qw将数组S初始化为一个固定的伪随机的数组，最后将用户密钥扩展到数组S中，密钥扩展算法如图3.40所示。




RC6w/r/b 密钥扩展

输入： 用户密钥字节预放入数组L［0，…，c-1］

轮数r

输出： w位的轮密钥S［0，…，2r+3］

过程： 

 S［0］=Pw

 for i=1 to 2r+3 do

 S［i］=S［i+1］+Qw

 A=B=i=j=0





图3.40RC6密钥扩展算法







 v=3×max{c，2r+4}

 for s=1 to v do

 {

 A=S［i］=(S［i］+A+B)<<<3

 B=L［j］=(L［j］+A+B)<<<(A+B)

 i=(i+1) mod (2r+4)

 j=(j+1) mod c

 }





图3.40（续）




3.8.3RC6的安全性和灵活性

RC6是由RC5发展而来的，加入了二次函数f(x)=x×(2x+1)，这个函数提高了函数密码扩散速度。用二次函数变换的寄存器B和D的值来修改寄存器A和C的值，增加了密码的非线性。因此RC6有很好的抗差分攻击和线性攻击的能力。另外RC6的加密和解密的时间都与数据无关，可以有效地避免计时攻击。同时，也没有RC6存在类似DES中的弱密钥。

与其他加密算法不同的是，RC6算法在加密过程中不需要查找表，加之算法中的乘法运算也可以用平方代替，所以该算法对内存的要求很低。这使得RC6特别适合在单片机上实现。


3.9流密码
3.9.1流密码基本原理

一次一密密码是绝对安全的密码，如果能以某种方式仿效一次一密密码，将可以得到安全性很高的密码。长期以来，人们试图以流密码方式仿效一次一密密码，从而促进了流密码的研究和发展。目前，序列密码的理论已经比较成熟，而且流密码实现简单、加密速度快、密文传输中的错误不会在明文中产生扩散，使得流密码成为许多重要领域应用的主流密码体制。


流密码也称为序列密码，它是对明文以一位或者一字节为单位进行操作。为了使加密算法更安全，一般选取尽可能长的密钥，但是长密钥的存储和分配都很困难。于是流密码采用一个短的种子密钥来控制密钥流发生器创建出长的密钥序列，供加解密使用，而短的种子密钥的存储、分配都较容易。图3.41是流密码的加密过程。种子密钥k输入密钥流发生器，产生一系列密码流，通过与同一时刻的一字节或者一位明文流进行异或操作产生密文流。解密时只要将密文流与密钥流进行异或操作产生明文流。例如，如果密钥流发生器产生的密钥流一字节为10011001，明文流一字节为01001010，那么密钥流与明文流异或可以产生密钥流11010011。同样，将密文流与密钥流异或就能得到明文流。

在流密码中，如果密钥流的产生完全独立于明文流或密文流，则称该流密码为同步流密码（Synchronous Stream Cipher），如图3.42所示。如果密钥流的产生与明文或者密文相关，则称这类流密码为自同步流密码(SelfSynchronous Stream Cipher)，如图3.43所示。



图3.41流密码加密过程




图3.42同步流密码







图3.43自同步流密码



对于同步流密码，只要通信双方的密钥流产生器具有相同的种子密钥和相同的初始状态，就能产生相同的密钥流。在保密通信过程中，通信的双方必须保持精确的同步，接收方才能正确解密，如果失步接收方将不能正确解密。例如，如果通信中丢失或增加了一个密文字符，则接收方将会一直收到错误的信息，直到重新同步为止，这是同步流密码的一个主要缺点。但是同步流密码对失步的敏感性，使我们能够容易检测插入、删除、重播等主动攻击。由于同步流密码各操作位之间相互独立，因此应用这种方式进行加解密时无错误传播，当操作过程中产生一位错误时只影响一位，不影响后续位，这是同步流密码的一个优点。


对于自同步流密码，每一个密钥位是由前面n个密文位参与运算推导出来的，其中n为定值。因此，如果在传输过程中丢失或更改了一个位，则这一错误就要向前传播n个位。因此，自同步流密码有错误传播现象。不过，在收到n个正确的密文位以后，密码自身会实现重新同步。在自同步流密码系统中，密文流参与了密钥流的生成，这使得对密钥流的分析非常复杂，从而导致对自同步流密码进行系统的理论分析非常困难。


3.9.2密钥流产生器

流密码的安全强度完全取决于它所产生的密钥流的特性，如果密钥流是无限长且为无周期的随机序列，那么流密码属于“一次一密”的密码体制，但遗憾的是满足这样条件的随机序列在现实中无法生成。在实际应用当中的密钥流都是由有限存储和有限复杂逻辑的电路产生的字符序列，由于密钥流生成器只具有有限状态，那么它产生的序列具有周期性，不是真正的随机序列。现实设计中只能追求密钥流的周期尽可能长，随机性尽可能好，近似于真正的随机序列。一个好的密钥流需要满足下面几个条件。


(1) 加密序列的周期要长。密钥流生成器产生的比特流最终会出现重复。重复的周期越长，密码分析的难度越大。

(2) 密钥流应该尽可能地接近一个真正的随机数流的特征。如1和0的个数应近似相等。如果密钥流为字节流，则所有的256种可能的字节的值出现频率应近似相等。

(3) 为了防止穷举攻击，种子密钥值也应该有足够的长度，至少要保证它的长度不小于128位。

生成一个具有良好特性的密钥流序列的常见方法有： 线性反馈移位寄存器(Linear Feedback Shift Register，LFSR）、非线性移位寄存器（NLFSR）、有限自动机、线性同余、混沌密码序列等方法。这些方法都是通过一个种子(有限长)密码产生具有足够长周期的、随机性良好的序列。只要生成方法和种子都相同，就会产生完全相同的密钥流。目前密钥流生成器大多是基于移位寄存器。因为移位寄存器结构简单，易于实现且运行速度快。本节主要介绍线性移位寄存器。

密钥流产生器一般由线性移位寄存器(LFSR)和一个非线性组合函数两部分构成。其中线性移位寄存器部分称为驱动部分，另一部分称为非线性组合部分，如图3.44所示。其工作原理是将驱动部分，即线性移位寄存器在j时刻的状态变量x作为一组值输入非线性组合部分的f，将f(x)作为当前时刻的密钥kj。驱动部分负责提供非线性组合部分使用的周期大、统计性能好的序列，而非线性组合部分以各时刻移位寄存器的状态组合出密钥序列。


移位寄存器是流密码产生器的主要部分，图3.45是一个域GF(2)上的反馈移位寄存器，图中标有a1，a2，…，an-1，an的小方框表示二值(0，1)存储单元，可以是一个双稳触发器，信号流从左向右。这n个二值存储单元称为该反馈移位寄存器的级。在任意一个时刻，这些级的内容构成该反馈移位寄存器的状态。每一个状态对应于GF(2)上的一个n维向量，共有2n种可能的状态。每个时刻的状态可用n长序列a1，a2，…，an或n维向量a1，a2，…，an表示，其中ai为当前时刻第i级存储器中的内容。



图3.44密钥流产生器




图3.45反馈移位寄存器




在主时钟确定的周期区间上，每一级存储器ai都将其内容向下一级ai-1传递，并根据寄存器当时的状态计算f(a1，a2，…，an)作为an的下一时间周期的内容，其中反馈函数f(a1，a2，…，an)是n元布尔函数。所以在时钟的每一脉冲下，总是从一个状态转移到另一个状态。


有反馈函数f(a1，a2，…，an)=cna1⊕cn-1a1⊕…⊕cn-1an，其中，ci为0或者1，⊕是模2加法。这个反馈函数是a1，a2，…，an的线性函数。称这种反馈移位寄存器为线性移位寄存器(LFSR)，否则称为非线性移位寄存器。

如果反馈移位寄存器的状态为：

si=(ai，…，ai+n-1)


则ai+n=f(ai，ai+1，…，ai+n-1)，这个ai+n又是移位寄存器的输入。在ai+n的驱动下，移位寄存器的各个数据向前推移一位，使状态变为si+1=(ai+1，…，ai+n)，同时，整个移位寄存器的输出为ai。由此可以得到一系列数据a1，a2，…，an。





图3.46一个三级移位寄存器

例3.12图3.46是一个三级移位寄存器，初始状态是s1=(a1，a2，a3)=(1，0，1)，写出它的输出序列的前5位。


从图3.46中可以发现反馈函数是a1和a3的异或，那么三级移位寄存器的输出如表3.10所示。


表3.10三级移位寄存器的输出


状态(a3，a2，a1)输出状态(a3，a2，a1)输出

10110100
01001100
1011






3.9.3RC4算法

RC4是Ron Rivest在1987年为RSA数据安全公司设计的一种同步流密码。据分析显示该密码的周期大于10100。每输出一字节的结果仅需要8~16条机器操作指令。RC4的应用很广，例如，它被集成于Microsoft Windows、Lotus Notes、Apple AOCE和Oracle Secure SQL中，还被用于SSL/TLS、WEP（Wired Equivalent）等协议中。



RC4不是基于移位寄存器的流密码，而是一种基于非线性数据表变换的流密码，它以一个足够大的数据表为基础，对表进行非线性变换，产生非线性密钥流序列。RC4 是一个可变密钥长度、面向字节操作的流密码，该字节的大小n可以根据用户需要来定义，一般应用中n都取8位。流密钥的生成需要两个处理过程： 一个是密钥调度算法(KeyScheduling Algorithm，KSA)，用来设置数据表S的初始排列； 另一个是伪随机产生算法(Pseudo RandomGeneration Algorithm，PRGA)，用来选取随机元素并修改S的原始排列顺序。


密钥流产生过程是用1～256字节的可变长度的密钥初始化一个256字节的数据表S，S的元素记为S(i)，0≤i≤255，大小为一字节。加密和解密用的每一个密钥K(i)都是由S中的元素按照一定的方式选出一个元素而生成的。每生成一个K(i)值，S中的元素就被重新置换一次。



1. KSA初始化S

初始化时，先对S进行填充，即令S(0)=0，S(1)=1，S(2)=2，…，S(255)=255。用种子密钥填充一个256字节的密钥表K，K(0)，K(1)，K(2)，…，K(255)，如果种子密钥的长度小于K的长度，则依次重复填充，直到将K填满，然后通过S(i)和K(i)置换S中的元素，其过程如下。



for i=0 to 255 do

S(i)=i； 

T(i)=K(i mod keylen)

j=0； 

 for i=0 to 255 do 

 j=(j+S(i)+T(i)) mod 256； 

 Swap (S(i)，S(j))； 





其中keylen为种子密钥长度，T(i)是一个临时数据表。上面过程对S操作仅仅是交换，交换后S所包含的值仍然是0~255的元素。


2. 密钥流生成

数据表S一旦完成初始化，将不再使用种子密钥。当KSA完成S的初始化后，PRGA就将接手工作，它为密钥流选取一个个的字节，即从S中选取随机元素，并修改S以便下一次选取。密钥流的生成是S(0)~S(255)，对每个S(i)，根据当前的S值，将S(i)与S中的另一字节置换。当S(255)完成置换后，操作继续重复从S(0)开始。密钥流的选取过程如下。




i=0，j=0； 

while(true)

i=(i+1) mod 256； 

j=(j+S(i)) mod 256； 

Swap(S(i)，S(j))； 

t=(S(i)+S(j)) mod 256； 

k=S(t)； 





例3.13假如使用3位（0~7）的RC4，其操作是对8取模(而不是对256取模)。数据表S只有8个元素。初始化为:






01234567


S01234567


选取一个密钥，该密钥是由0~7的数以任意顺序组成的。例如选取5、6和7作为密钥。将该密钥如下填入密钥数据表中。






56756756


K01234567


利用如下循环构造实际S数据表。


j=0； 

for i=0 to 7 do 

 j=(j+S(i)+K(i)) mod 8； 

 Swap(S(i)，S(j))； 





该循环以j=0和i=0开始，使用更新公式后j为：


j=(0+S(0)+K(0)) mod 8=(0+0+5) mod 8=5


因此，S数据表的第一个操作是将S(0)与S(5)互换，互换结果如下所示。







51234067


S01234567



i加1后，j的下一个值为：


j=(5+S(1)+K(1)) mod 8=(5+1+6) mod 8=4



即将S数据表的S(1)与S(4)互换，互换结果如下所示。








54231067


S01234567



当该循环执行完后，数据表S就被随机化为：







54071632


S01234567



这样数据表S就可以用来生成随机的密钥流序列了。从j=0和i=0开始开始，RC4将如下所示计算第一个密钥字： 

i=(i+1) mod 8=(0+1) mod 8=1

j=(j+S(i)) mod 8=(0+S(1)) mod 8=(0+4) mod 8=4

Swap(S(1)，S(4))


交换后数据表S变为：






51074632


S01234567




然后如下计算t和k： 

t=(S(i)+S(j)) mod 8=t=(S(1)+S(4)) mod 8=(1+4) mod 8=5

k=S(t)=S(6)=6

第一个密钥字是6，其二进制表示为110。重复该过程，直到生成的二进制位的数量等于明文位的数量。



常见的RC4实现是基于n=8的(数字为0~255)。这种系统执行完KSA后的数据表S是0~255的一个排列，共有256!（即21600）种可能。这相当于使用一个1600位的密钥，这使得穷举攻击变得不可能。在RC4中，有一些弱点可用来破解该加密法。例如，RSA永远不会生成某类密钥，例如j=i+1与S（j）=1。事实证明，这类密钥的数量占到了所有可能密钥数的2-2n。当n＝8时，就是(256!／216)。

RC4算法在设计过程中采用了非线性的S盒，能够抵抗差分攻击和线性分析，但是RC4的安全性还是令人担忧。1999年，Kundanrewich等设计了一个可编程逻辑电路用33天穷举了40位的RC4算法； 2001年，Fluhrer等则提出了分析RC4算法的有效方法，称为FMS的分析方法，该方法主要是针对WEP（Wired Equivalent Privacy）协议，该协议采用流密码算法RC4作为加密算法，为了克服流密钥重用的问题，在WEP协议中引入了初始向量，这样可以增强抗穷举攻击能力，但是也产生了FMS的分析方法，该方法是针对以明文传送的初始向量和对应的802.11帧的特点进行攻击的。



3.10分组密码工作模式

分组密码算法是提供数据安全的一个基本构件。分组密码是针对固定大小的分组进行加密的。例如，DES是对64位的明文分组进行加密，AES是对128位分组操作。但需要保密传输的消息不一定刚好是一个分组大小，为了在实际中应用分组密码，我们定义了5种工作模式,任何一种对称分组密码算法都可以应用这些方式。


3.10.1电子密码本模式




图3.47电子密码本模式

电子密码本(Electronic Code Book，ECB)模式是分组密码的基本工作方式，它将明文分割成独立大小的分组b，最后一组在必要时需要填充，一次处理b位的明文，每次使用相同的密钥加密，如图3.47所示。由于任意b位的明文，只有唯一的密文与之对应，就像密码本一样可以查到对应的密文，因此称为电子密码本模式。ECB对每组进行加密，加密后将各组密文合并成密文消息。在图3.47中，明文被分割成大小为b位的一串分组，记为P1，P2，…，PN，对应的密文为C1，C2，…，CN。


在ECB模式下，每个分组依次独立加密，产生独立的密文组，每个分组的加密结果均不受其他分组的影响。因此使用此种方式，可以利用并行处理来加速加密运算或解密运算，并且在传输时任意一个分组发生错误，不会影响其他分组，这是该模式的一个优点。但是，相同的明文组将产生相同的密文组，这样就会泄露明文的数据模式。在计算机系统中，许多数据都具有固有的模式，这主要是由数据结构和数据冗余引起的。但如果同一明文分组在消息中反复出现，产生的密文分组就会相同，因此，用于长消息时可能不够安全。如果消息有固定的结构，密码分析者就有可能会利用这种规律。例如，如果已知消息总是以某个事先规定的字段开始，那么分析者就有可能会得到许多明文密文对。如果消息有重复的成分，而重复的周期是b位的倍数，那么这些成分都有可能会被密码分析者识别出来。因此ECB模式特别适合短数据(如加密密钥)。


3.10.2密码分组链接模式 


为了克服ECB的缺陷，人们希望设计一种方案使同一明文分组重复出现时产生的密文分组不同。一种简单的方案就是使用密码分组链接(Cipher Block Chaining，CBC)模式，如图3.48所示。


图3.48密码分组链接模式

这种模式和ECB模式一样，也要将明文分成b位的一串分组，最后一组不足b位要进行填充。但是CBC将这些分组链接在一起进行加密操作，加密输入是当前明文分组和前一密文分组的异或，它们形成一条链，每次加密使用相同的密钥，每个明文分组的加密函数输入与明文分组之间不再有固定的关系，所以明文分组的数据模式不会在密文中暴露。



在加密时，最开始一个分组先和一个初始向量（Initialization Vector，IV）进行异或，然后再用密钥加密，每个分组的加密结果均会受到前面所有分组的影响，所以即使在明文中出现多次相同的明文，也会产生不同的密文。对每个分组加密可以表示为：


Ci=EK(Pi ⊕ Ci-1)
C-1=IV 




解密时，将第一块密文解密结果与IV异或可恢复第一块明文。其他的每个密文分组被解密后，再与前一个密文分组异或来产生出明文分组，即：

Dk［Ci］ ⊕ Ci-1=Dk［EK［Pi ⊕ Ci-1］］ ⊕ Ci-1=Pi ⊕ Ci-1 ⊕ Ci-1=Pi


由于CBC模式的链接机制，可以避免像ECB模式下的那种明文数据模式的泄露,并且它对加密大于b位的明文非常合适。CBC模式除了能够获得保密性外，还能用于认证，可以识别攻击者在密文传输中是否做了数据篡改，比如分组的重放、插入和删除等。但CBC模式同时也会导致错误传播，密文传输中任何一组发生错误不仅会影响该分组的正确解密，也会影响其下一分组的正确解密。该加密模式的另一个缺点是不能实时解密，也就是说，必须等到每个b位都被接收到之后才能开始加密，否则就不能得到正确的结果。


IV对于收发双方都应是已知的。为提高安全性，IV应像密钥一样被保护。保护IV的原因如下： 如果攻击者能欺骗接收方使用不同的IV值，攻击者就能够在第一个明文分组中改变某些选定的数据位，这是因为：


C1=EK(IV⊕ Pi)
P1=IV⊕Dk［C1］


用X(i)表示分组b位X的第i位，那么P1(i)=IV(i)⊕Dk［C1］(i)，由异或的性质，有：

P1(i)′=IV(i)′⊕Dk［C1］(i)


其中撇号表示取反。上式意味着如果攻击者篡改IV中的某些位，则接收方收到的P1中相应的位也会发生变化。


3.10.3密码反馈模式

如果需要将加密的明文必须按照一字节或者一位进行处理，就可以采用密码反馈(Cipher Feed Back，CFB)模式或者输出反馈(Output Feed Back，OFB)模式。这两种模式实际上是将分组密码转换为流密码，流密码不需要明文长度是分组长度的整数倍，且可以实时操作。比较适合多媒体数据加密，每一字节（或者一位）加密后可以立即发送，接送方也可以立即解密。



图3.49是密码反馈模式，假设它的输出是s位，s位的大小可以是1位、8位、64位或者其他大小，表示为CFB1、CFB8和CFB64等。因此密码反馈模式可以将分组密码转换成流密码。在加密时，用密钥K加密大小b位移位寄存器中的数据（其大小是该密码算法加密的明文分组长度。例如，若使用DES加密，则大小为64位； 若使用AES加密，大小为128位）。移位寄存器的初始值为某个初始向量IV。

加密后输出的最左边s位与明文的P1（P1与s的大小相同）异或，产生出第一个密文单元C1，并将C1单元传输出去。然后将移位寄存器中的内容左移s位，并将C1送入移位寄存器的最右边s位。就这样持续进行，直到明文的所有单元都被加密为止。



图3.49密码反馈模式


在解密时，除了将收到的密文单元与加密函数的输出进行异或以产生明文单元外，其他与加密采用相同的方案。注意这里使用的是加密函数而不是解密函数。如假设Ss(X)表示X的最左边s位，则：

C1=P1⊕ Ss(E(K，IV))

所以P1=C1⊕ Ss(E(K，IV))。


下面以DES为例，使用CFB8工作模式说明加密过程。

(1) 加密： 加密函数的输入是一个64位的移位寄存器，产生初始向量IV。

(2) 对移位寄存器64位的数据用密钥进行加密，然后取加密数据最左边的8位与输入的明文最初的8位进行异或操作，得到的值作为8位密文单元。

(3) 这8比特密文被移至位寄存器的最右端，而其他位则向左移动8位，最左端8比特丢弃。

(4) 继续加密，与第2段明文输入异或，如此重复直到所有明文单元都完成加密。



有一点必须注意，这里的明文单元Pi和密文单元Ci与电子密码本模式和密码分组链接模式中的含义不一样。我们以DES为例说明这个问题，DES中分组长度是64位（在本书中我们用b位表示）。在电子密码本模式和密码分组链接模式中，将明文分割成一个64位的分组，即Pi的大小，加密后输出一个64位的分组，即Ci的大小。在密码反馈模式中，移位寄存器的大小是64位，加密后选取其中的一部分（大小可以是1位、8位或者64位），假设我们选取8位，再与相同大小的明文单元Pi异或，输出相同大小的密文单元Ci，显然这时Pi和Ci的大小是8位，而不是64位。


显然密码反馈模式具有流密码的优点，也拥有CBC模式的优点。但是它也拥有CBC模式的缺点，即也会导致错误传播。明文的一个错误会影响所有后面的密文以及在解密过程中的逆。另外密码反馈模式会降低数据加密速度。由于无论每次输出多少位，都需要事先用密钥K加密一次，再与相等的明文位异或，所以即使一次输出为1位，也要经过相同的过程，这就降低了加密速度。如果一次输出密文单元与移位寄存器相同的大小，那么密码反馈模式等同于密码分组链接模式。



3.10.4输出反馈模式 


类似于密码反馈模式，不同之处在于输出反馈模式(OFB)是将加密算法的输出反馈到移位寄存器，而密码反馈模式是将密文单元反馈到移位寄存器，如图3.50所示。



图3.50输出反馈模式

与CFB相比，OFB模式的优点是传输过程中的位错误不会被传播。但是相对于其他模式，因为数据之间相关性小，这种加密模式是相对不安全的。如这种模式难于检测密文是否被篡改。如果在密文中某位取反，那么在恢复后的明文中相应位也取反。因此攻击者有可能通过对数据部分和校验部分同时进行篡改，导致纠错码无法检测。所以在应用时除非特别需要，一般不提倡应用OFB模式。


3.10.5计数器模式 


计数器(Counter，CTR)采用与明文分组相同的长度，但加密不同的明文组，计数器对应的值不同。计数器首先被初始化为一个值，然后随着消息块的增加，计数器的值依次递增1。计数器加1后与明文分组异或得到密文分组。解密是使用相同的计数器值序列，用加密后的计数器的值与密文分组异或来恢复明文，如图3.51所示。



图3.51计数器模式


计数器模式比较适合对实时性和速度要求比较高的场合，它具有以下优点。

(1) 处理效率： 由于下一块数据不需要前一块数据的运算结果，所以CTR能够并行加密(解密)。这使其吞吐量可以大大提高。

(2) 预处理： 基本加密算法的执行不依赖明文或者密文的输入，因此可以事先处理。这样可以极大地提高吞吐量。

(3) 随机访问： 由于对某一密文分组的处理与其他密文分组无关，因此可以随机地对任意一个密文分组进行解密处理。

(4) 简单性： 计数器模式只要求实现加密算法，而不要求解密算法，加密阶段和解密阶段都使用相同的加密算法。


3.11随机数的产生

随机数在信息安全中起着非常重要的作用。在很多场合需要用到随机数，如对称密码体制中密钥、非对称密码体制公钥以及用于认证的临时交互号等均使用了随机数。安全的随机数应该满足随机性和不可预测性。随机性有如下两个评价标准。


 分布一致性： 随机数分布是一致的，即每个数出现频率大约相等。

 独立性： 数据序列中的任何数不能由其他数导出。

一般来说，数据序列是否满足均匀分布可通过检测来判断，而是否满足独立性则是无法判断的。但却有很多检测方法能证明数据序列不满足独立性。如果对数据序列进行足够多次数的检测后都不能证明不满足独立性，就可比较有把握地相信该数据序列满足独立性。对产生的数据序列不仅要求其具有随机性而且要求其具有不可预测性，即根据数据序列的一部分不能推导出之前的部分序列，也不能预测后续序列。

一般来说，产生随机数的方式有两种： 一是通过一个确定性的算法，由数字电路或是软件实现，把一个初值扩展成一个长的序列； 二是选取真实世界的自然随机源，比如热噪声等。由前一种方法产生的序列通常被称为伪随机序列，而后者通常被称为真随机序列。



3.11.1真随机数发生器

对于伪随机序列来说，因为使用的是确定的算法，有一定的规律所循，所以只要具备足够的计算能力，总能进行预测。能否产生真正的随机数，长期以来，这个问题一直都处于激烈的争论之中。但对于工程应用来说，只要产生的序列具有随机统计特性，并且不可再现，就可以被称为真随机序列。设计一个真随机数发生器包括两步： 第1步是获取真随机源； 第2步是利用真随机源依照特定的数学方法获得真随机数。真随机源广泛存在于现实世界中，比如计算机网络中IP 包到达的时间、随机噪音、计算机当前的秒级时钟、键盘反应时间、热噪声、操作系统的进程信息、光量子的偏振等。获取方法可以通过调用系统函数或硬件电路来实现。利用真随机源产生真随机数的方法有很多，一种最简单的方法是直接利用真随机源的奇偶特性来产生0和1序列。为了增加序列的随机性，往往还对产生的0和1序列进行一系列的变换，比如归一化、非线性映射、移位、加密等。图3.52是通过提取电路中的热噪声来产生随机数的方法。该方法将提取的热噪声进行放大，输入一个比较器中，与固定的参考电压进行比较，从而确定输出0、1序列。图3.53是基于自激振荡器频率不稳定性的真随机数发生器的原理示意图。




图3.52利用热噪声的随机数发生器




图3.53振荡采样随机数发生器




3.11.2伪随机数发生器

在理想情况下，密码算法和协议中需要的秘密数应该用一个真随机生成器来产生。然而，在大多数实际环境中，真随机比特的生成是一个效率较低的过程，并且安全地存储和传送一个大随机数也是不切实际的。因此，在信息安全中常常用伪随机发生器产生伪随机数。这些随机数尽管不是真正的随机，但能够通过许多随机测试。


1. 线性同余法

线性同余(Linear Congruential)法是一种广泛使用的伪随机数产生方法。其随机数序列{Xn}可通过下面的式子迭代获得： 

Xn+1=(aXn+c) mod m，n≥0

其中： 

 X0称为种子或者初始值，并且0≤X0<m； 

 常数m称为模数，m>0；

 常数a称为乘子，0≤a<m； 

 常数c称为增量，0≤c<m。
当c=0时，该算法称为乘同余法； 当c≠0时，该算法称为混合线性同余法。


为了得到 ［0，1］区间上分布的随机数，可以令：


Rn=Xnm


其中Rn为满足要求的随机数。


a、c、m的取值是产生高质量的随机数的关键。如当a=7，c=0，m=32，X0=1时，生成的数为{1，7，17，23，1，7，…}，该数列的周期为4，而模为32，结果不能令人满意。当随机数周期达到模时，则其周期称为满周期，也就是理论上的最大周期。所以我们在用同余算法生成随机数的时候，要尽可能地使周期达到满周期。合理地选择a、c、m、X0，可以使重复的周期充分长。如果满足下面条件，随机数发生器可以达到满周期。



(1) c和m互素。

(2) 对m的任何一个素因子p，a≡1 mod p。

(3) 如果4是m的因子，则a≡1 mod 4。


对于上面的条件，这些参数一般取下面的值： m=2L，其中L是计算机中存放一个整数值的二进制位数(称为整数的尾数字长)。这种方法有两个优点： 一是m越大，随机数的周期就可能越大； 二是算法上利用计算机的整数溢出原理，可简化计算。其他的参数取值为：

a=4α+1

c=2β+1

其中α和β为任意正整数。



线性同余法的强度取决于乘子和模数的选择。但是除了初值x0的选取具有随机性外，算法本身并不具有随机性，因为选定x0后，以后的数就被确定性地产生了。这个性质可用于对该算法的密码分析，如果攻击者知道正在使用线性同余算法并知道算法的参数，则一旦获得数列的一个数，就可得到以后的所有数。甚至攻击者如果只知道正在使用线性同余算法以及产生的数列中极少一部分，就足以确定出算法的参数。假定攻击者能确定x0、x1、x2和x3，就可通过以下方程组： 

X1=(aX0+c) mod m

X2=(aX1+c) mod m

X3=(aX2+c) mod m

解出a、c和m。


改进的方法是利用系统时钟修改随机数数列。一种方法是每当产生N个数后，就利用当前的时钟值模m后作为新种子。另一种方法是直接将当前的时钟值加到每个随机数上再对m取模。



2. 非线性同余法

非线性同余(Nonlinear Congruential)法的随机数序列{Xn}可通过下面的式子迭代获得： 


Xn+1=f(Xn) mod m，n≥0
Rn=Xnm


其中，Xn∈Zm={0，1，2，…，m-1}，f是Zm上的一个整数函数。如果f(x)=ax+c，则变为线性同余。在非线性同余法中的f通常是Zm上的一个排列多项式。


下面是几种典型的非线性同余发生器，它们的区别主要是f函数不同。


1) 逆同余发生器 


Xn+1=(aX′n+b) mod m，n≥0
Rn=Xnm



其中，X′n是Xn关于模m的乘法逆预元。


2) 二次同余发生器


Xn+1=(aX2n+bXn+c) mod m，n≥0
Rn=Xnm


其中，a、b、c为非负整数，且a≠0。


3) BBS发生器

BBS(Blum Blum Shub)发生器是由Lenore Blum、Manuel Blum 和Michae Shub于1986年共同提出的一种随机数发生器，其递推公式为：


Xn+1=X2n mod m，n≥0
Rn=Xnm


其中，m=pq，p和q是两个大素数，且p≡q≡3(mod 4)，选择随机数s与m互素，计算初始值X0=s2 mod m。


BBS发生器最大的特点是可以直接计算任意一个Xn的值： 

Xn=（X2n mod (p-1)(q-1)0） mod m


BBS发生器的安全性很好，并且通过了几乎所有的理论检验，但其运行速度较慢。



4) 幂同余发生器


幂同余发生器是BBS发生器的推广，其迭代公式为：


Xn+1=Xdn mod m，n≥0
Rn=Xnm


其中，d和m为正整数。一个重要的特殊情形是m=pq，且p和q为两个大素数。


5) 指数同余发生器

指数同余发生器的迭代公式为：


Xn+1=gXn mod m，n≥0
Rn=Xnm


其中，g和m为正整数。一个重要的特殊情形是m为一个大素数。



3. 混沌随机数发生器

在混沌区的数据具有两个显著的特性： 迭代不重复性和初值敏感性。如果选定一个迭代方程和适当的系数，方程将进行无限制不循环地迭代。下式是混合光学双稳模型的迭代方程： 

Xn+1=Asin2(Xn-XB)


A和XB是方程的系数，当A=4，XB=2.5时方程处于混沌状态。根据该方程生成混沌序列{Xi}，可以获得不同0和1序列Si。


Si=1，Xi≥23A
0，其他情况



4. 用密码学的方法产生随机数


单向函数可以用于产生伪随机数，方法是首先选取随机种子s，然后再将函数应用于序列s，s+1，s+2，…，进而输出序列f(s)，f(s+1)，f(s+2)，…。该单向函数可以是hash函数（如SHA1），或者是对称分组密码（如DES）。


1) 循环加密



图3.54由计数器生成伪随机数

循环加密是一种非常简单的随机数产生方法，如图3.54所示。它用一个种子密钥循环加密计数器，从而产生一个随机序列。计数器的周期为N。如果要产生56位的DES密钥，可以用一个周期为256的计数器，每产生一个密钥，计数器的值增加1，那么这种方法产生的伪随机序列是全周期的，所有的输出序列都是由不同的计数值而来的，所以它们互不相同。由于种子密钥是保密的，所以由生成的随机数不能推出后续的随机数。有时为了增加强度，可以用一个全周期的伪随机数发生器来代替简单的计数器。



2) ANSI X9.17随机数生成器

ANSI X9.17基于3DES随机数生成标准，如图3.55所示。



图3.55ANSI X9.17伪随机数生成器



图3.55中的符号含义如下。

 EDE： 表示用两个密码加密的三重DES，即加密解密加密。

 DTi： 第i轮的初始日期和时间。

 Vi： 第i轮的初始种子值，Vi+1表示第i轮产生的新种子，并作为第i+1轮的种子。


 Ri： 第i轮的所产生的伪随机数。

 K1和K2： DES所使用的密钥。

ANSI X9.17伪随机数生成器采用的输入是DTi和Vi。DTi是一个64位数，代表当前的日期和时间，每产生一个伪随机数它均要改变。Vi是种子值，可以是任意的64位数，并在随机数生成过程中被更新。从图3.55中很容易得到随机数序列和下一轮的种子。



Ri=EDE［K1，K2］(Vi ⊕EDE［K1，K2］(DTi))
Vi+1=EDE［K1，K2］(Ri ⊕EDE［K1，K2］(DTi))


其中EDE［K1，K2］(X)表示使用两个密钥K1和K2的三重DES加密X。


3.12对称密码的密钥分配
3.12.1密钥分配基本方法

对称密码体制要求双方共享一个共同的密钥，并且为防止攻击者得到密钥，还必须时常更新密钥。通常安全系统存在的问题是出在密钥分配(Key Distribution)上。如何安全地分发这个密钥是对称密码体制的核心问题。在两个用户(主机、进程、应用程序) A和B之间分配密钥的方法有以下几种。


(1) 密钥由A选取，并通过物理手段交给B。

(2) 密钥由第三方选取，并由第三方通过物理手段交给A和B。

(3) 如果A和B事先已有一密钥，则其中一方选取新密钥后，用已有的密钥加密新密钥并发送给另一方。

(4) 如果A和B与可信的第三方C分别有一保密通道，则C为A和B选取密钥后，分别在两个保密信道上发送给A和B。


前两种方法称为人工发送。在通信网中，若只有个别用户想进行保密通信，密钥的人工发送还是可行的。然而如果所有用户都要求支持加密服务，则任意一对希望通信的用户都必须有一共享密钥。如果有n个用户，则密钥数目为n(n-1)/2。因此当n很大时，密钥分配的代价非常大，如当有1000个结点时，需要多达500000个密钥，如果加密在应用层，则每个用户或者进程都需要一个密钥，那么密钥分配任务则更重。


对于第（3）种方法，攻击者一旦获得一个密钥就可获取以后所有的密钥，而且用这种方法为所有用户分配初始密钥时，代价仍然很大。



第（4）种方法比较常用，其中的第三方通常是一个负责为用户分配密钥的密钥分配中心(Key Distribution Center，KDC)。这时每一用户必须和密钥分配中心有一个共享密钥，称为主密钥(Master Key)。通过主密钥分配给一对用户的密钥称为会话密钥(Session Key)，用于这一对用户之间的保密通信。通信完成后，会话密钥即被销毁。如上所述，如果用户数为n，则会话密钥数为n(n-1)/2。但主密钥数却只需n个，所以主密钥可通过物理手段发送。


一个完整的密钥分配方案需要完成两个功能： 一是将密钥分发给双方； 二是双方互相认证，确保密钥一定只给了双方。图3.56是一个典型的密钥分配过程。由密钥分配中心(KDC)产生会话钥，然后分发给A和B。图3.56中字符的含义如下。


 Ka和Kb分别是A和B各自拥有与KDC共享的主密钥。

 Ks是分配给A和B的一次性会话钥。

 N1和N2是临时交互号(Nonces)，可以是时间戳、计数器或随机数，主要用于防止重放攻击。

 IDA和IDB分别是A和B的身份标识（例如A和B的网络地址）。

 f(N2)是对N2的某种变换（例如将N2加1）函数，目的是认证。

 ‖ 表示连接符，如IDA‖IDB‖N1表示同时传送了IDA、IDB和N1。



图3.56密钥分配过程




A和B之间的会话密钥是通过以下几步来完成的。



(1) A向KDC发出会话密钥请求。表示请求的消息由两个数据项组成，第1项是A和B的身份IDA和IDB，第2项是这一步骤的唯一识别符N1，称为临时交互号。每次请求所用的都应不同，且为防止假冒，应使攻击者难以猜测。因此用随机数作为这个识别符最为合适。使用临时交互号的目的是防止重放攻击。



(2) KDC为A的请求发出应答。应答是用A和KDC的共享的主密钥Ka加密，因此只有A才能成功地对这一消息解密，并且A可相信这一消息的确是由KDC发出的。消息中包括给A的两项内容： 

 一次性会话密钥Ks。

 A在第(1)步中发出的请求，包括一次性随机数N1，目的是使A将收到的应答与发出的请求相比较，看是否匹配。这样A能验证自己发出的请求在被KDC收到之前，是否被他人篡改。而且A可以确定收到的这个消息是否是对它请求的响应，而不是对以前消息的重放。
此外，该消息中还有给B的两项内容： 

 一次性会活密钥Ks。

  A的身份IDA。
这两项由B和KDC的共享的主密钥Kb加密，将由A转发给B，以建立A和B之间的连接，并用于向B证明A的身份。


(3) A存储会话密钥备用，并向B转发EKb［Ks‖IDA］。因为转发的是由Kb加密后的密文，所以转发过程不会被窃听。B收到后，可得会话密钥Ks，并且可知另一方是A，还从Kb知道Ks的确来自KDC。


完成这一步后，会话密钥就被安全地分配给了A和B。下面需要在A和B之间进行认证。 

(4) B用会话密钥Ks加密另一个临时交互号N2，并将加密结果发送给A。


(5) A以f(N2)作为对B的应答，其中f是对N2进行某种变换（例如加1）的函数，并将应答用会话密钥加密后发送给B。注意一点，如果不将N2进行某种变换，直接以N2作为应答，则会存在重放攻击。


这两步可使B相信第（3）步收到的消息不是一个重放。并且双方进行了认证。


第（4）和第（5）步是典型挑战/应答(Challenge/Response)认证方式。假设A期望从B获得一个新消息，首先发给B一个临时值(Challenge)，并要求后续从B收到的消息(Response)中正确地包含这个临时值。


3.12.2密钥的分层控制 

在网络中，如果用户数目非常多而且分布的地域非常广，一个KDC就无法承担为用户分配密钥的重任。问题的解决方法是使用多个KDC的分层结构。例如，在每个小范围（如一个LAN或一个建筑物）内，都建立一个本地KDC。同一范围的用户在进行保密通信时，由本地KDC为他们分配密钥。如果两个不同范围的用户想获得共享密钥，则可通过各自的本地KDC，而两个本地KDC的沟通又需经过一个全局KDC。这样就建立了两层KDC。类似地，根据网络中用户的数目及分布的地域，可建立三层或多层KDC。


分层结构可减少主密钥的分布，因为大多数主密钥是在本地KDC和本地用户之间共享。此外，如果一个本地KDC出错或者被攻击，则危害只限制在一个局部区域，而不会影响全局。



3.12.3会话密钥的有效期 

会话密钥更换得越频繁，系统的安全性就越高。因为攻击者即使获得一个会话密钥，也只能获得很少的密文。但是，会话密钥更换得太频繁，又将延迟用户之间的交换，同时还会造成网络负担。所以在决定会话密钥的有效期时，应权衡这两个方面。

对于面向连接的协议，在连接未建立前或断开时，会话密钥的有效期可以很长。而每次建立连接时，都应使用新的会话密钥。如果逻辑连接的时间很长，则应定期更换会话密钥。

对于无连接协议（如面向交易的协议），无法明确地决定更换密钥的频率。为安全起见，用户每进行一次交换，都用新的会话密钥。然而这又失去了无连接协议的主要优势，如延时了交易时间，每个交易都希望用最少的费用和最短的延迟。比较好的方案是在某一个固定周期内或者交易一定量内使用同一会话密钥。



3.12.4无中心的密钥分配 

用密钥分配中心（第三方）为用户分配密钥时，要求所有用户都信任KDC，同时还要求对KDC加以保护。如果密钥的分配没有这个中心，则不必有以上两个要求。在下面的分配方案中，每个用户事先和其他用户之间存在一个主密钥，然后使用这些主密钥产生会话钥。如果网络中有n个用户，则需有n(n-1)/2个主密钥。当n很大时，整个网络中的主密钥很多，但每个结点最多只保存n-1个主密钥，用这些主密钥可以产生很多会话钥。图3.57是一个无中心的密钥分配过程。




图3.57无中心的密钥分配过程



两个用户A和B建立会话密钥需要以下3个步骤。

(1) A向B发出建立会话密钥的请求，包括A和B的身份标识和临时交互号N1。



(2) B用与A共享的主密钥MKm对应答的消息加密，并发送给A。应答的消息中包括选取的会话密钥Ks、B的身份标识、f(N1)和另一个临时交互号N2。

(3) A使用新建立的会话密钥Ks对f(N2)加密后返回给B。


以上过程完成了两件事，一是在A和B之间分配会话钥； 二是A和B进行相互认证。在步骤（1）和步骤（2）中，挑战(Challenge)是临时交互号N1，应答(Response)是f(N1)，完成了A对B的认证。在步骤（2）和步骤（3）中，挑战(Challenge)是临时交互号N2，应答(Response)是f(N2)，这样就完成了B对A的认证。




3.13关 键 术 语

密码学（Cryptology）

密码编码学（Cryptography）

密码分析学（Cryptanalysis）

密码分析者（Cryptanalyst）

明文（Plaintext）

加密（Encryption）

密文（Ciphertext）

解密（Decryption）

密码(Cipher)

密码体制(Cryptosystem)

密钥（Key）

分组密码(Block Ciphers)

流密码(Stream Ciphers)

对称加密(Symmetric Encryption)

穷举攻击(Brute Force Search)

唯密文攻击（CiphertextOnly Attack）

已知明文攻击（KnownPlaintext Attack）

选择明文攻击（ChosenPlaintext Attack）

选择密文攻击（ChosenCiphertext Attack）

选择文本攻击（Chosen Text Attack）

绝对安全(Unconditional Security)

计算上安全（Computational Security）

代换（Substitution）

置换（Permutation）

单字母代换密码(Monogram Substitution Cipher) 

多字母代换密码(Polygram Substitution Cipher）

单表代换密码(Monoalphabetic Substitution Cipher)

多表代换密码(Polyalphabetic Substitution Cipher)

代换密码(Substitution Cipher) 

仿射密码(Affine Cipher)

置换密码（Permutation Cipher）

扩散（Diffusion）

混淆（Confusion）

数据加密标准(Data Encryption Standard，DES)

高级加密标准（Advanced Encryption Standards，AES）

同步流密码（Synchronous Stream Cipher）

自同步流密码(SelfSynchronous Stream Cipher)

线性同余(Linear Congruential)

密钥分配(Key Distribution)

主密钥(Master Key)

会话密钥(Session Key)

密钥分配中心(Key Distribution Center，KDC)


习题3

3.1下式是仿射密码的加密变换：

c=(3m+5) mod 26


试求： 

(1) 该密码的密钥空间是多少？

(2) 求出消息hello对应的密文。

(3) 写出它的解密变换。

(4) 试对密文进行解密。



3.2用Playfair密码加密下面的消息： 

ciphers using substitutions or transpositions are not secure because of language characteristics。密钥为the playfair cipher was invented by Charles Wheatstone。


3.3假设密钥为encryption，用维吉尼亚密码加密消息symmetric schemes require both parties to share a common secret key。


3.4Hill密码不能抵抗已知明文攻击，如果有足够多的明文和密文对，就能破解Hill密码。


(1) 攻击者至少有多少个不同的明文密文对才能攻破该密码？

(2) 描述这种攻击方案。


3.5用Hill密码加密消息hill，密钥为：

k=11837


并写出从密文恢复明文的解密过程。


3.6用一次一密加密消息01011010101100111100010101010101011011110001010001，选定的密钥是10010101011110101101000101000001111100100101010010，试写出密文。


3.7使用DES加密，假设明文和密钥都为(0123456789ABCDEF)16=(00000001 00100011 01000101 01100111 10001001 10101011 11001101 11101111)2：

(1) 推导出第1轮的子密钥K1。

(2) 写出R0和L0。

(3) 扩展R0并计算E(R0)⊕K1。

(4) 将第（3）问的结果，输入8个S盒中，求出加密函数F。

(5) 推导出R1和L1。


3.8在GF(28)上{01}的逆是什么？并验证其在S盒中的输入。


3.9假设 AES的State矩阵的某一列分别是s0={87}，s1={6E}，s2={46}，s3={A6}。经过列混淆变换后，s1={6E}映射为s′1={37}，试验证这一结果。


3.10采用AES加密，密钥为2B 7E 15 16 28 AE D2 A6 AB F7 15 88 09 CF 4F 3C，明文为32 43 F6 AD 88 5A 30 8D 3131 98 A2 E0 37 07 34。


(1) 写出最初的State的值。

(2) 写出密钥扩展数组中的前8字节。

(3) 写出初始轮密钥加后State的值。

(4) 写出字节代换后State的值。

(5) 写出行移位后的State的值。

(6) 写出列混淆后State的值。

3.11习题3.10的明文和密钥不变，采用SM4加密。

（1） 求出第1轮的轮密钥rk0。

（2） 求第1轮加密后的明文输出是什么？

3.12有一个四级线性移位寄存器的反馈函数为f(a1，a2，a3，a4)=a1⊕a2，其中初态为(a1，a2，a3，a4)=(1000)，求其输出序列的前12位。


3.13假如使用3位(0~7)的RC4，其操作是对8取模(而不是对256取模)，密钥是326。


(1) 求初始化后S表的值。

(2) 计算第1个密钥字。

(3) 用上面生成的密钥加密明文100101。


3.14在8位CFB模式中，如果在传输中一个密文字符发生错误，这个错误将被传送多远？

3.15编写仿射密码的加密和解密程序。

3.16写一个程序实现维吉尼亚(Vigenère)密码的加密和解密。

3.17编程实现AES算法。

3.18编程实现线性同余伪随机数生成算法。