第02章 常规加密的经典技术

第二章常规加密的经典技术密码学基本概念常规加密模型隐写术替代加密和转置加密简单的XOR一次一用密码本11.密码学基本概念发送者和接收者在信息传送过程中，主动提供信息的一方称发送者，得到信息的一方称接收者。发送者要确保信息安全传送，使窃听者不能盗取信息。21.密码学基本概念密码技术目的：使不知道如何解密的黑客不可能由其截获的乱码中得到任何有意义的信息；使黑客不可能伪造任何乱码型的信息。密码学(密码技术)分类密码编码学：对信息进行编码实现信息隐蔽密码分析学：研究分析破译密码31.密码学基本概念密码通信系统模型41.密码学基本概念被隐蔽的消息称作明文密码可将明文变换成另一种隐蔽形式，称为密文。由明文到密文的变换称为加密。由合法接收者从密文恢复出明文的过程称为解密（或脱密）。非法接收者试图从密文分析出明文的过程称为破译。对明文进行加密时采用的一组规则称为加密算法。对密文解密时采用的一组规则称为解密算法。加密算法和解密算法是在一组仅有合法用户知道的秘密信息，称为密钥的控制下进行的。加密和解密过程中使用的密钥分别称为加密密钥和解密密钥。51.密码学基本概念明文消息空间M；密文消息空间C；密钥空间K1和K2；加密交换Ek1：M—〉C，其中k1∈K1；

解密变换Dk2：CM，其中k2∈K2；称总体（M，C，K1，K2，Ek1，Dk2）为密码系统。对于给定明文消息m∈M，密钥k1∈K1，加密交换将明文m变换为密文c：c＝f(m,k1)＝Ek1(m)m∈M，k1∈K161.密码学基本概念合法接收者，利用其知道的解密密钥k2对收到的密文进行变换，恢复出明文消息m＝Dk2(c)m∈M，k2∈K2黑客则利用其选定的变换函数h，对截获的密文c进行变换，得到的明文是明文空间的某个元素m’＝h(c)m∈M，k2∈K2一般m’≠m。如果m’＝m，则黑客破译成功。71.密码学基本概念认证，完整性和不许抵赖认证：信息接受者应有可能核查信息来源，任何闯入者无力装扮成原有的发送者。完整性：信息接收者应有可能验证信息在传播中未经修改，闯入者无力用假信息代替合法的原有信息。不可抵赖：发送者在发送出信息后无法抵赖他所发出的信息。81.密码学基本概念算法和密钥密码算法，称为加密算法，是用来加密和解密的数学函数。为给明文信息加密，用加密算法函数。为给密文信息解密，用解密算法函数。如果算法的安全性基于算法工作的保安，这是一个受约算法。近代密码术用密钥来解决安全性问题。91.密码学基本概念算法和密钥加密和解密函数表示EK(M)=CDK(C)=M若加密和解密密钥相同：DK(EK(M))＝M若加密和解密密钥不同：EK1(M)＝CDK2(C)=MDK2(EK1(M))=M101.密码学基本概念密码系统分类用于将明文转换为密文操作的类型。所有加密算法基于两个基本原则：①替代，即明文中的每个元素（比特、字母、比特组合或字母组合）被映射为另一个元素；②转置，即在明文中的元素被重排列，对它们的基本要求是不丢失信息（即所有操作都是可逆转的）。被称为乘积系统的多数系统涉及多个阶段的替代和转置。所使用密钥的数量。如果发送者和接收者双方使用相同的密钥，该系统称为对称加密、单密钥加密、秘密密钥加密或常规加密。如果发送者和接收者各自使用一个不同的密钥，则该系统称为非对称加密、双密钥加密或公开密钥加密。明文处理的方式。分组加密一次处理一块元素的输入，对每个输入块产生一个输出块。流（序列）加密连续地处理输入元素，并随着该过程的进行，一次产生一个元素的输出。111.密码学基本概念单钥密码的特点是无论加密还是解密都使用同一个密钥，因此，此密码体制的安全性就是密钥的安全。如果密钥泄露，则此密码系统便被攻破。最有影响的单钥密码是1977年美国国家标准局颁布的DES算法。优点：安全性高、加解密速度快。缺点：1)随着网络规模的扩大，密钥的管理成为一个难点；2)无法解决消息确认问题；3)缺乏自动检测密钥泄露的能力。121.密码学基本概念双钥体制特点加密密钥与解密密钥不同，此时不需要安全信道来传送密钥而只需利用本地密钥发生器产生解密密钥k2∈K2。并以此来控制解密操作D。双钥密码是1976年W.Diffie和M.E.Hellman提出的一种新型密码体制。优点：由于双钥密码体制的加密和解密不同，且能公开加密密钥，而仅需保密解密密钥，所以双钥密码不存在密钥管理问题。双钥密码还有一个优点是可以拥有数字签名等新功能。最有名的双钥密码是1977年由Rivest，Shamir和Adleman三人提出的RSA密码体制。缺点：双钥密码算法一般比较复杂，加解密速度慢。131.密码学基本概念序列密码加密过程是把明文序列与等长的密钥序列进行逐位模2加。解密过程则是把密文序列与等长的密钥序列进行逐位模2加。安全性：主要依赖于密钥序列。最著名的序列密码是“一次一密密码”，它的密钥序列是真正的随机二元序列。优点：1)处理速度快，实时性好；2)错误传播小；3)不存在串破译问题；4)适用于军事、外交等保密信道。缺点：1)明文扩散性差；2)插入信息的敏感性差；3)需要密钥同步。141.密码学基本概念分组密码加密方式是首先将明文序列以固定长度进行分组，每一组明文用相同的密钥和加密函数进行运算。为了减少存储量和提高运算速度，密钥的长度一般不大，因而加密函数的复杂性成为系统安全的关键。分组密码设计的核心是构造既具有可逆性又有很强的非线性的算法。加密函数重复地使用代替和置换两种基本的加密变换。优点：1)明文信息良好的扩散性；2)对插入的敏感性；3)不需要密钥同步；4)较强的适用性，适宜作为加密标准。缺点：1)加密速度慢；2)错误易扩散和传播。151.密码学基本概念密码破译密码破译则是无须取得密钥而能将密文信息恢复成明文的科学。密码破译成功，不仅恢复明文也可得到密钥。并且发现密码系统中导致上述结果的弱点。仅知密文攻击已知明文攻击选择明文攻击选择文本（自适应选择明文攻击）选择密文攻击选择密钥攻击牛皮筋式破译161.密码学基本概念仅知密文攻击在这种攻击中，密码破译员有几个信息的密文，所有的信息使用相同加密算法加密。为将相同密钥加密的信息解密，密码破译员会尽可能多地恢复信息的明文，或者更好地是导出用于加密信息的密钥。已知：C1=EK(P1)，C2=EK(P2)，…，Ci=EK(Pi)导出：P1、P2…Pi、K或导出从Ci+1=EK(Pi+1)得知Pi+1的算法

已知明文攻击密码破译员不但利用几个信息的密文，而且有这些信息的明文。导出用于加密信息的密钥或用相同的密钥加密任何新的信息的解密算法。已知：P1，C1=EK(P1)，P2，C2=EK(P2)，…，Pi，Ci=EK(Pi)导出：K或导出从Ci+1=EK(Pi+1)得知Pi+1的算法171.密码学基本概念选择明文攻击密码破译员不但利用密文和涉及到的信息的明文，而且能选择加密的明文。这比已知明文攻击更强有力，因为密码破译员能选择专用的明文块加密，可能产生更多关于密钥的信息。导出用于加密信息的密钥或用相同的密钥加密任何新的信息的解密算法。已知：P1，C1=EK(P1)，P2，C2=EK(P2)，…，Pi，Ci=EK(Pi)其中密码分析者选择P1、P2…Pi导出：K或导出从Ci+1=EK(Pi+1)得知Pi+1的算法

选择文本（自适应选择明文攻击）这是选择明文攻击的一个特例。密码破译员不但选择加密的明文，而且能依据以前加密的结果修改选择。在选择明文攻击中，密码破译员可以选择一大块明文加密；在自适应选择明文攻击中，选择一个较小的明文块，然后依据第一次的结果选择另一块，等等。

181.密码学基本概念选择密文攻击密码破译员能选择不同的将要解密的密文和已解的明文，将它们放入一个自动解密的分解判别的工具箱中，导出密钥。已知：C1，P1=DK(C1)，C2，P2=DK(C2)，…Ci，Pi=DK(Ci)导出：K这种攻击主要应用于公开密钥加密系统。选择密文攻击有时对对称算法一样有效。选择密钥攻击这种攻击并不意味破译员能选择密钥。只不过破译员对不同密钥之间的关系有所了解。它较新奇和含混但并不实用。牛皮筋式破译破译员威胁、写黑信或折磨某人直至给出密钥，或用金钱收买，所以也称购买密钥攻击，这已不是科学技术的内容了，但在现实社会中却也常有奏效。

191.密码学基本概念攻击的类型密码破译者己知的东西仅有密文加密算法待破译的密文已知明文加密算法待破译的密文由密钥形成的一个或多个明文——密文对选择明文加密算法待破译的密文由密码破译者选择的明文消息，连同它对应的由其密钥生成的密文选择文本加密算法待破译的密文由密码破译者选择的明文消息，连同它对应的由密钥生成的密文由密码破译者选择的猜测性的密文，连同它对应的由密钥生成的已破译的明文加密算法待破译的密文由密码破译者选择的猜测性的密文，连同它对应的由密钥生成的已破译的明文密码破译方法小结201.密码学基本概念算法安全性算法根据攻破的难易标定了不同的安全程度。如攻破某算法的费用大于加密数据的代价，该算法认为是安全的。如攻破某算法的时间长于数据的保密期，该算法也认为是安全的。同样如攻破某算法所需的数据量多于密钥加密的数据量，该算法仍认为是安全的。以上所说的安全并非绝对，因为在密码破译中新的攻破机遇频频发生，另一方面大部分数据的价值会随时间流逝而贬低。所以，安全的要点是数据的价值要继续保持低于攻破安全屏障所花的代价。211.密码学基本概念LarsKnudsen按攻破算法难易的递降顺序，分类如下：全攻破，密码破译员找到密钥K，于是解密DK(C)=M。全局推导，密码破译员找到另一算法A，无须知道K，因为A等价于DK(C)而解密。局部推导，密码破译员找到窃听来的密文的明文而解密。信息推导，密码破译员得到关于密钥信息或是有关明文格式的信息。利用这些信息而解密。如果无论破译员有多少密文，仍无足够信息能恢复明文，这样的算法是无条件安全的。事实上只有一次一用的密码本是不可攻破的。其它所有密码系统在惟密文攻击下都是可以攻破的。221.密码学基本概念加密算法的安全准则：破译该密码的成本超过被加密信息的价值。破译该密码的时间超过该信息有用的生命周期。攻击复杂性的度量：数据复杂性，为攻击所需数据的攻击量。处理复杂性，执行攻击所须的时间，又称工作因子。存储需求，做攻击所须的存储量。231.密码学基本概念自然界常用大数物理类似物数字到下个冰世纪的时间14,000（214）年到太阳销毁的时间109（230）年行星的寿命109（230）年宇宙的寿命（如果宇宙是开放的）1011（267）年到小质量恒星冷却时间1016（261）秒到行星脱离恒星时间1015（230）年到所有恒星离开银河的时间1019（264）年到天体轨道因向心辐射而消逝时间1020（267）年到黑洞因Hawking过程而消逝时间1064（2213）年到所有物质冷却成零度液体的时间1065（2216）年到所有物质衰变成铁的时间101026年到所有物质陷落到黑洞的时间101076年241.密码学基本概念密钥长度与安全性评估密钥长度（bit）密钥数量每微秒加密1次所需时间每微秒加密100万次所需时间32232=4.3x109

231us=35.8分2.15微秒56256=7.2x1016

255us=1142年10.01小时1282128=3.4x1038

2127us=5.4x1024年5.4x1018年26字符（排列）26!=4x1026

2x1026us=6.4x1012年6.4x106年252.常规加密模型常规加密的简化模型262.常规加密模型常规密码系统的模型272.隐写术字符标记：印刷或打印的文本字母经选择用铅笔重写。该标记通常不可见，除非该纸以一定的角度对着亮光看。不可见墨水：使用一些物质来书写，但不留下任何可见痕迹，除非加热该纸或在该纸上涂上某种化学药品。扎小孔：在所选的字母上扎小孔，这些小孔通常不可见，除非把该纸放在光的前面。打字机改正带：用于行间与一根黑带一同打印，用改正带打印的结果仅在强光下才可见。格孔密写卡：将它覆盖在一张纸上从格孔中写入密件，然后在纸上余下部分填入其它字句，使它像一般信件。282.隐写术示例：293.替代加密和置换加密替代技术置换技术转子机（RotorMachine）303.替代加密和置换加密替代技术替代技术是这样一种技术，其中明文的字母由其他字母或数字或符号所代替。如果该明文被视为一个比特序列，则替代涉及到用密文比特模式代替明文比特模式。在经典密码学中，替代加密算法有四种基本类型：简单替代加密算法或称单字符加密，明文每一字符被替代成密文中的相应字符。新闻密电就是用这种方法。同音替代加密算法，类似于简单替代加密算法，但明文中的单一字符能对应密文中的几个字符。例如“A”可能相应于5、13、25或“B”可能相应于7、19、31或42等等。多元替代加密算法，成块的字符加密成一组其它字符。如“ABA”相应于“RTQ”，“ABB”相应于“SLL”等等。多字母替代加密算法，由多次简单替代加密组成。例如用5次不同的简单替代加密，具体所用的次数随每一字符在明文中的位置而变化。313.1替代加密移位密码体制设P=C=K=Z/(26),对k∈K,定义ek(x)=x+k(mod26)=y∈C同时dk(y)=y-k(mod26)注1*：26个英文字母与模26剩余类集合{0,….,25}建立一一对应：

ABCDEFGHIJKLMNOPQRSTUVWXYZ

0

12345678910111213141516171819202122232425

2*.当k=3时，为Caesar密码：明文：meetmeafterthetogaparty

密文：PHHWPHDIWHOWKHWRJDSDUWB

实际算法为：有

同时有，d3(y)=y-3(mod26)323.1替代加密替换密码体制设P=C=Z/(26)，K是由26个符号0，1,..,25的所有可能置换组成。任意π∈K，定义eπ(x)=π(x)=y且dπ(y)=-1(y)=x,π-1是π的逆置换。

注：1*.置换π的表示：

π＝2*密钥空间K很大，|k|=26!≈4×1026，破译者穷举搜索是不行的，然而，可由统计的方式破译它。3*移位密码体制是替换密码体制的一个特例，它仅含26个置换做为密钥空间(0123..2324250'1'2'3'..23'24'25')333.1替代加密仿射密码体制替换密码的另一个特例就是仿射密码。加密函数取形式为

e(x)=ax+b(mod26),a,b∈Z/(26)

要求唯一解的充要条件是gcd(a,26)=1

该体制描述为：

设P=C=Z/(26)K={(a,b)∈Z/(26)×Z/(26)|gcd(a,26)=1},

对k=(a,b)∈K,

定义ek(x)=ax+b(mod26)和dk(y)=a-1(y-b)(mod26)x,y∈Z/(26)34例子，设k＝（7，3），注意到7-1(mod26)=15,加密函数是ek(x)=7x+3,相应的解密函数是dk(y)=15(y-3)=15y-19,易见dk(ek(x))=dk(7x+3)=15(7x+3)-19=x+45-19=x(mod26)

若加密明文：hot，首先转换字母h,o,t成为数字7,14,19,然后加密：解密：353.1替代加密Hill密码体制设ｍ为某个固定的正整数，P=C=(Z/(26))m,

K={Z/(26)上的m×m可逆矩阵}对每一个k∈K,定义ek(x)=xK(mod26)和dk(y)=yK-1(mod26)注：明文与密文都是m元的向量（x1,x2…,xm);(y1,y2,…,ym)，Z/(26)为同余类环。在这个环上的可逆矩阵Amxm,是指行列式detAmxm的值∈Z*/(26),它为Z/(26)中全体可逆元的集合。Z*/(26)={a∈Z/(26)|(a,26)=1}，

Z*/(26)={1,3,5,7,9,11,15,17,19,21,23,25}例子：当m=2时，明文元素x=(x1,x2),密文元素y=(y1,y2)(y1,y2)=(x1,x2)

K36事实上yi为x1,x2的线性组合，y1=11x1+3x2;y2=8x1+7x2，一般，将取m×m的矩阵K作为我们的密钥：有

y=(y1,y2,…,ym,)=(x1,x2,…,

xm)

换言之，y=xK;且有x=yK-1

若K=,可得K-1=若对明文july加密，它分成2个元素（j,u),(l,y),分别对应于（9,20）,（11,24）,有37（9,20）＝（99＋60,72＋140）＝（3,4）

且（11,24）＝(121＋72,88＋168)＝（11,22）于是对july加密的结果为DELW。为了解密，Bob计算

且因此，得到了正确的明文“july”

383.1替代加密维吉尼亚密码(Vigenere)设m为一固定的正整数，定义P=C=K=(Z/(26))m,对一个密钥K＝（k1,k2,…,km),定义ek(x1,x2,…,xm)=(x1+k1,x2+k2,…,xm+km)=y

dk(y1,y2,…,ym)=(x1-k1,x2-k2,…,xm-km)=x这里的所有的运算都是在（mod26)中进行的。注：维吉尼亚密码是多表替换体制，分析起来更困难。密钥空间大，如当m=5时，密钥空间所含密钥的数量是>1.1×107393.替代加密和置换加密置换技