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

1、1第二章第二章 常规加密的经典技术常规加密的经典技术1. 密码学基本概念2. 常规加密模型3. 隐写术4. 替代加密和转置加密5. 简单的XOR6. 一次一用密码本 21. 1. 密码学基本概念密码学基本概念 发送者和接收者 在信息传送过程中，主动提供信息的一方称发送者，得到信息的一方称接收者。发送者要确保信息安全传送，使窃听者不能盗取信息。 31. 1. 密码学基本概念密码学基本概念 密码技术 目的： 使不知道如何解密的黑客不可能由其截获的乱码中得到任何有意义的信息； 使黑客不可能伪造任何乱码型的信息。 密码学(密码技术 ) 分类 密码编码学：对信息进行编码实现信息隐蔽 密码分析学：研究分析

2、破译密码41. 1. 密码学基本概念密码学基本概念 密码通信系统模型 非法 侵入者 信源 M 加密器 c=Ek1(m) 解密器 m=Dk2(c) 接收者 密码分析员 (窃听者) 密钥源 K1 密钥源 K2 搭线信道 (主动攻击) 搭线信道 (被动攻击) 密钥信道 m c m k1 k2 c m 51. 1. 密码学基本概念密码学基本概念 被隐蔽的消息称作明文明文 密码可将明文变换成另一种隐蔽形式，称为密文密文。 由明文到密文的变换称为加密加密。由合法接收者从密文恢复出明文的过程称为解密解密（或脱密脱密）。 非法接收者试图从密文分析出明文的过程称为破译破译。 对明文进行加密时采用的一组规则称为加

3、密算法加密算法。 对密文解密时采用的一组规则称为解密算法解密算法。 加密算法和解密算法是在一组仅有合法用户知道的秘密信息，称为密钥密钥的控制下进行的。 加密和解密过程中使用的密钥分别称为加密密钥加密密钥和解解密密钥密密钥。 61. 1. 密码学基本概念密码学基本概念 明文消息空间明文消息空间M； 密文消息空间密文消息空间C； 密钥空间密钥空间K1和和K2； 加密交换加密交换Ek1：MC，其中其中k1K1； 解密变换解密变换Dk2：CM，其中其中k2K2； 称总体（称总体（M，C，K1，K2，Ek1，Dk2）为密码为密码系统。对于给定明文消息系统。对于给定明文消息mM，密钥密钥k1K1，加密交换

4、将明文加密交换将明文m变换为密文变换为密文c：cf(m,k1)Ek1(m) mM，k1K171. 1. 密码学基本概念密码学基本概念 合法接收者，利用其知道的解密密钥合法接收者，利用其知道的解密密钥k2对收到对收到的密文进行变换，恢复出明文消息的密文进行变换，恢复出明文消息mDk2(c) mM，k2K2 黑客则利用其选定的变换函数黑客则利用其选定的变换函数h，对截获的密对截获的密文文c进行变换，得到的明文是明文空间的某个进行变换，得到的明文是明文空间的某个元素元素mh(c) mM，k2K2一般一般mm。如果如果mm，则黑客破译成功。则黑客破译成功。 81. 1. 密码学基本概念密码学基本概念

5、认证，完整性和不许抵赖认证，完整性和不许抵赖 认证：信息接受者应有可能核查信息来源，任何闯认证：信息接受者应有可能核查信息来源，任何闯入者无力装扮成原有的发送者。入者无力装扮成原有的发送者。 完整性：信息接收者应有可能验证信息在传播中未完整性：信息接收者应有可能验证信息在传播中未经修改，闯入者无力用假信息代替合法的原有信息。经修改，闯入者无力用假信息代替合法的原有信息。 不可抵赖：发送者在发送出信息后无法抵赖他所发不可抵赖：发送者在发送出信息后无法抵赖他所发出的信息。出的信息。91. 1. 密码学基本概念密码学基本概念 算法和密钥 密码算法，称为加密算法，是用来加密和解密的数学函数。为给明文信

6、息加密，用加密算法函数。为给密文信息解密，用解密算法函数。 如果算法的安全性基于算法工作的保安，这是一个受约算法受约算法。 近代密码术用密钥来解决安全性问题。101. 1. 密码学基本概念密码学基本概念 算法和密钥 加密和解密函数表示EK(M)=CDK(C)=M 若加密和解密密钥相同： DK(EK(M)M 若加密和解密密钥不同：EK1(M)CDK2(C)=MDK2(EK1(M)=M 111. 1. 密码学基本概念密码学基本概念 密码系统分类 用于将明文转换为密文操作的类型。所有加密算法基于两个基本原则：替代，即明文中的每个元素（比特、字母、比特组合或字母组合）被映射为另一个元素；转置，即在明文

7、中的元素被重排列，对它们的基本要求是不丢失信息（即所有操作都是可逆转的）。被称为乘积系统的多数系统涉及多个阶段的替代和转置。 所使用密钥的数量。如果发送者和接收者双方使用相同的密钥，该系统称为对称加密、单密钥加密、秘密密钥加密或常规加密。如果发送者和接收者各自使用一个不同的密钥，则该系统称为非对称加密、双密钥加密或公开密钥加密。 明文处理的方式。分组加密一次处理一块元素的输入，对每个输入块产生一个输出块。流（序列）加密连续地处理输入元素，并随着该过程的进行，一次产生一个元素的输出。 121. 1. 密码学基本概念密码学基本概念 单钥密码的特点 是无论加密还是解密都使用同一个密钥，因此，此密码体

8、制的安全性就是密钥的安全。如果密钥泄露，则此密码系统便被攻破。最有影响的单钥密码是1977年美国国家标准局颁布的DES算法。 优点：安全性高、加解密速度快。 缺点：1)随着网络规模的扩大，密钥的管理成为一个难点；2)无法解决消息确认问题；3)缺乏自动检测密钥泄露的能力。 131. 1. 密码学基本概念密码学基本概念 双钥体制特点 加密密钥与解密密钥不同，此时不需要安全信道来传送密钥而只需利用本地密钥发生器产生解密密钥k2K2。并以此来控制解密操作D。双钥密码是1976年W.Diffie和M.E.Hellman提出的一种新型密码体制。 优点：由于双钥密码体制的加密和解密不同，且能公开加密密钥，而

9、仅需保密解密密钥，所以双钥密码不存在密钥管理问题。双钥密码还有一个优点是可以拥有数字签名等新功能。最有名的双钥密码是1977年由Rivest，Shamir和Adleman三人提出的RSA密码体制。 缺点：双钥密码算法一般比较复杂，加解密速度慢。 141. 1. 密码学基本概念密码学基本概念 序列密码 加密过程是把明文序列与等长的密钥序列进行逐位模2加。 解密过程则是把密文序列与等长的密钥序列进行逐位模2加。 安全性：主要依赖于密钥序列。最著名的序列密码是“一次一密密码”，它的密钥序列是真正的随机二元序列。 优点：1)处理速度快，实时性好；2)错误传播小；3)不存在串破译问题；4)适用于军事、外

10、交等保密信道。 缺点：1)明文扩散性差；2)插入信息的敏感性差；3)需要密钥同步。 151. 1. 密码学基本概念密码学基本概念 分组密码 加密方式是首先将明文序列以固定长度进行分组，每一组明文用相同的密钥和加密函数进行运算。为了减少存储量和提高运算速度，密钥的长度一般不大，因而加密函数的复杂性成为系统安全的关键。分组密码设计的核心是构造既具有可逆性又有很强的非线性的算法。加密函数重复地使用代替和置换两种基本的加密变换。 优点：1)明文信息良好的扩散性；2)对插入的敏感性；3)不需要密钥同步；4)较强的适用性，适宜作为加密标准。 缺点：1)加密速度慢；2)错误易扩散和传播。 161. 1. 密

11、码学基本概念密码学基本概念 密码破译密码破译则是无须取得密钥而能将密文信息恢复成明文的科学。密码破译成功，不仅恢复明文也可得到密钥。并且发现密码系统中导致上述结果的弱点。 仅知密文攻击 已知明文攻击 选择明文攻击 选择文本（自适应选择明文攻击） 选择密文攻击 选择密钥攻击 牛皮筋式破译 171. 1. 密码学基本概念密码学基本概念 仅知密文攻击在这种攻击中，密码破译员有几个信息的密文，所有的信息使用相同加密算法加密。为将相同密钥加密的信息解密，密码破译员会尽可能多地恢复信息的明文，或者更好地是导出用于加密信息的密钥。已知：C1=EK(P1)，C2=EK(P2)，Ci=EK(Pi)导出：P1、P

12、2Pi、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的算法 181. 1. 密码学基本概念密码学基本概念 选择明文攻击 密码破译员不但利用密文和涉及到的信息的明文，而且能选择加密的明文。这比已知明文攻击更强有力，因为密码破译员能选择专用的明文块加密，可能产生更多关于密钥的信息。导出用于加密信息的密钥或用相同的密钥加密

13、任何新的信息的解密算法。已知：P1，C1=EK(P1)，P2，C2=EK(P2)，Pi，Ci=EK(Pi)其中密码分析者选择P1、P2Pi导出：K或导出从Ci+1=EK(Pi+1)得知Pi+1的算法 选择文本（自适应选择明文攻击）这是选择明文攻击的一个特例。密码破译员不但选择加密的明文，而且能依据以前加密的结果修改选择。在选择明文攻击中，密码破译员可以选择一大块明文加密；在自适应选择明文攻击中，选择一个较小的明文块，然后依据第一次的结果选择另一块，等等。 191. 1. 密码学基本概念密码学基本概念选择密文攻击密码破译员能选择不同的将要解密的密文和已解的明文，将它们放入一个自动解密的分解判别的

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

15、个或多个明文密文对 选择明文 加密算法待破译的密文由密码破译者选择的明文消息，连同它对应的由其密钥生成的密文 选择文本 加密算法待破译的密文由密码破译者选择的明文消息，连同它对应的由密钥生成的密文 由密码破译者选择的猜测性的密文，连同它对应的由密钥生成的已破译的明文 加密算法待破译的密文由密码破译者选择的猜测性的密文，连同它对应的由密钥生成的已破译的明文 密码破译方法小结211. 1. 密码学基本概念密码学基本概念 算法安全性算法根据攻破的难易标定了不同的安全程度。如攻破某算法的费用大于加密数据的代价，该算法认为是安全的。如攻破某算法的时间长于数据的保密期，该算法也认为是安全的。同样如攻破某算

16、法所需的数据量多于密钥加密的数据量，该算法仍认为是安全的。以上所说的安全并非绝对，因为在密码破译中新的攻破机遇频频发生，另一方面大部分数据的价值会随时间流逝而贬低。所以，安全的要点是数据的价值要继续保持低于攻破安全屏障所花的代价。 221. 1. 密码学基本概念密码学基本概念Lars Knudsen按攻破算法难易的递降顺序，分类如下： 全攻破，密码破译员找到密钥K，于是解密DK(C)=M。 全局推导，密码破译员找到另一算法A，无须知道K，因为A等价于DK(C)而解密。 局部推导，密码破译员找到窃听来的密文的明文而解密。 信息推导，密码破译员得到关于密钥信息或是有关明文格式的信息。利用这些信息而

17、解密。如果无论破译员有多少密文，仍无足够信息能恢复明文，这样的算法是无条件安全的。事实上只有一次一用的密码本是不可攻破的。其它所有密码系统在惟密文攻击下都是可以攻破的。231. 1. 密码学基本概念密码学基本概念加密算法的安全准则： 破译该密码的成本超过被加密信息的价值。 破译该密码的时间超过该信息有用的生命周期。攻击复杂性的度量： 数据复杂性，为攻击所需数据的攻击量。 处理复杂性，执行攻击所须的时间，又称工作因子。 存储需求，做攻击所须的存储量。 241. 1. 密码学基本概念密码学基本概念 自然界常用大数物理类似物 数字 到下个冰世纪的时间 14,000（214）年 到太阳销毁的时间 10

18、9（230）年 行星的寿命 109（230）年 宇宙的寿命 （如果宇宙是开放的 ）1011（267）年 到小质量恒星冷却时间 1016（261）秒 到行星脱离恒星时间 1015（230）年 到所有恒星离开银河的时间 1019（264）年 到天体轨道因向心辐射而消逝时间 1020（267）年 到黑洞因Hawking过程而消逝时间 1064（2213）年 到所有物质冷却成零度液体的时间 1065（2216）年 到所有物质衰变成铁的时间 101026年 到所有物质陷落到黑洞的时间 101076年 251. 1. 密码学基本概念密码学基本概念 密钥长度与安全性评估 密钥长度（bit） 密钥数量 每微秒

19、加密1次所需时间 每微秒加密100万次所需时间 32 232 = 4.3 x 109 231us = 35.8分 2.15微秒 56 256 = 7.2 x 1016 255us =1142年 10.01小时 128 2128 = 3.4 x 1038 2127us = 5.4 x 1024年 5.4 x 1018年 26字符（排列） 26! = 4 x 1026 2 x 1026us = 6.4 x 1012年 6.4 x 106年 262. 2. 常规加密模型常规加密模型 常规加密的简化模型272. 2. 常规加密模型常规加密模型 常规密码系统的模型 秘密通道 X X Y X K K 密钥

20、源 加密算法 消息源 解密算法 目的地 密码破译者 282. 2. 隐写术隐写术字符标记：印刷或打印的文本字母经选择用铅笔重写。该标记通常不可见，除非该纸以一定的角度对着亮光看。不可见墨水：使用一些物质来书写，但不留下任何可见痕迹，除非加热该纸或在该纸上涂上某种化学药品。扎小孔：在所选的字母上扎小孔，这些小孔通常不可见，除非把该纸放在光的前面。打字机改正带：用于行间与一根黑带一同打印，用改正带打印的结果仅在强光下才可见。格孔密写卡：将它覆盖在一张纸上从格孔中写入密件，然后在纸上余下部分填入其它字句，使它像一般信件。292. 2. 隐写术隐写术示例： 情 报 在 雨 伞 中 王先生： 来信收悉，

21、你的盛情真是难以报答。我已在昨天抵达广州。秋雨连 绵，每天需备伞一把方能上街，苦诶。大约本月中旬我才能返回，届时 再见。 弟 李明 明文 密文 303. 3. 替代加密和置换加密替代加密和置换加密 替代技术置换技术 转子机（Rotor Machine） 313. 3. 替代加密和置换加密替代加密和置换加密 替代技术替代技术替代技术是这样一种技术，其中明文的字母由其他字母或数字或符号所代替 。如果该明文被视为一个比特序列，则替代涉及到用密文比特模式代替明文比特模式。在经典密码学中，替代加密算法有四种基本类型：1.简单替代加密算法或称单字符加密，明文每一字符被替代成密文中的相应字符。新闻密电就是用

22、这种方法。2.同音替代加密算法，类似于简单替代加密算法，但明文中的单一字符能对应密文中的几个字符。例如“A”可能相应于5、13、25或“B”可能相应于7、19、31或42等等。3.多元替代加密算法，成块的字符加密成一组其它字符。如“ABA”相应于“RTQ”，“ABB”相应于“SLL”等等。4.多字母替代加密算法，由多次简单替代加密组成。例如用5次不同的简单替代加密，具体所用的次数随每一字符在明文中的位置而变化。323.1 3.1 替代加密替代加密 移位密码体制移位密码体制设P=C=K=Z/(26),对k K,定义ek(x)=x+k (mod 26)=y C 同时dk(y) = y - k (m

23、od 26)注1*：26个英文字母与模26剩余类集合0,.,25建立一一对应： A B C D E F G H I J K L M N O P Q R S T U V W X Y Z 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 2*.当k=3时，为Caesar密码： 明文：meet me after the toga party 密文：PHHW PH DIWHO WKH WRJD SDUWB 实际算法为： 有 同时有，d3(y)=y-3 (mod 26)yxxe)26(mod3)(3Px333.1 3.

24、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! 41026，破译者穷举搜索是不行的，然而，可由统计的方式破译它。3*移位密码体制是替换密码体制的一个特例，它仅含26个置换做为密钥空间(0 1 2 3 .23 24 250 1 2 3 .23 24 25)343.1 3.1 替代加密替代加密 仿射密码体制仿射密码体制替换密码的另一个特例就是仿射密码。加密函数取形式为 e(x

25、)=ax+b (mod 26), a,bZ/(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 (mod 26)和dk(y)=a-1(y-b)(mod 26) x,y Z/(26)35 例子，设k（7，3），注意到7-1(mod 26)=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 (mo

26、d 26) 若加密明文：hot ，首先转换字母h,o,t成为数字7,14,19,然后加密：解密：);26(mod6230333191477GXA19147191919623015363.1 3.1 替代加密替代加密 Hill密码体制密码体制设为某个固定的正整数，P=C=(Z/(26)m, K=Z/(26)上的mm可逆矩阵 对每一个k K,定义ek(x)=xK (mod 26)和 dk(y)=yK-1 (mod 26)注：明文与密文都是 m元的向量（x1, x2 , xm );(y1, y2,ym)，Z/(26)为同余类环。在这个环上的可逆矩阵Amxm,是指行列式detAmxm的值 Z*/(26

27、),它为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) K7381137 事实上yi为x1,x2的线性组合，y1=11x1+3x2;y2=8x1+7x2，一般，将取mm的矩阵K作为我们的密钥：有 y=(y1, y2, ym,)=(x1, x2, xm) 换言之，y=xK;且有x=yK-1 若K= ,可得K-1 = 若对明文july加密，它分成2个元素（j,u),(l,y),

28、分别对应于（9,20）,（11,24）,有mmmmmmkkkkkkkkk21222211121173811112318738（9,20） （9960,72140）（3,4） 且（11,24 ） (12172,88168) （11,22）于是对 july加密的结果为DELW。 为了解密，Bob计算 且 因此，得到了正确的明文“july”7381173811 )20, 9(1123187)4 , 3()24,11(1123187)22,11(393.1 3.1 替代加密替代加密 维吉尼亚密码维吉尼亚密码 (Vigenere)设m为一固定的正整数，定义P=C=K=(Z/(26)m,对一个密钥K（ k

29、1,k2,km),定义 ek(x1,x2,xm)=(x1+k1,x2+k2,xm+km)=y dk(y1,y2,ym)= (x1-k1,x2-k2,xm-km) =x这里的所有的运算都是在（mod 26)中进行的。注：维吉尼亚密码是多表替换体制，分析起来更困难。密钥空间大，如当m=5时，密钥空间所含密钥的数量是1.1107403. 3. 替代加密和置换加密替代加密和置换加密 置换技术通过执行对明文字母的某种置换，取得一种类型完全不同的映射。这种技术称为置换密码。 413.1 3.1 置换加密置换加密 示例： COMPUTERGR APHICSMAYB ESLOWBUTAT LEASTITSEX

30、 PENSIVE 密文：CAELP OPSEE MHLAN PIOSS UCWTI TSBIU EMUTE RATSG YAERB TX 明文：COMPUTER GRAPHICS MAY BE SLOW BUT AT LEAST ITS EXPENSIVE 423.1 3.1 置换加密置换加密 设m为固定的正整数，P=C=(Z/(26)m, K是由1,2,.,m的所有置换构成，对一个密钥K，定义 e (x1, x2,., xm)=(x(1),.,x(m) 和 d (y1, y2,., ym)=(y(1),.,y(m) 这里1为的逆置换。注：这里的加密与解密仅仅用了置换，无代数运算。例子： 设m

31、=6, 取密钥 而) 6452)(31 (264564135231) 5462)(31 (462554136231143若给定的明文是：cryptography 首先找分成6个字母长的明文组：crypto|graphy 求得的密文是：YTCOPRAHGYPR注：事实上，置换密码是Hill密码的特例。给定一个集合1,2,.,m的置换矩阵K =(kij)mm（置换矩阵是每一行和每一列刚好在一个“1”，而其余元素为“0”的矩阵。）YTCOPRroptopcytryccryptoAHGYPRryphypgahraggraphy否则若0)(1ijkij44对上面例子决定的置换 对应：0000100010

32、00100000000001010000000100K00100000001001000000000110000000010011KK453. 3. 替代加密和置换加密替代加密和置换加密 转子机（Rotor Machine） A B C D E F G H I J K L M N O P Q R S T U V W X Y Z 慢转子 (b)在一次击键后的设置 (a)最初设置 快转子 中转子 运动方向 慢转子 快转子 中转子 运动方向 24 25 26 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 1 2 3