第二章 密码学(1)

计算机学院网络教研室12020/2/4第二章密码学基础密码学发展过程及相关术语对称密码非对称密码报文摘要技术计算机学院网络教研室22020/2/42.1密码学发展及相关术语产生背景古代国家政治、军事，外交领域，主要应用军事上消息传递的需要发展历程第一阶段古典密码（1949年以前）特点：是艺术而非科学数据的安全基于算法的保密计算机学院网络教研室32020/2/4Phaistos圆盘，一种直径约为160mm的Cretan-Mnoan粘土圆盘，始于公元前17世纪。表面有明显字间空格的字母，至今还没有破解保密的谁都不知道了计算机学院网络教研室42020/2/4第2阶段(1949~1975年)Shannon发表《保密系统的信息理论》，标志密码学阶段的开始。产生了信息论，及对称密码。背景：计算机使得基于复杂计算的密码成为可能。1967kahn出版《破译者》，使普通人开始知道密码学。主要特点：数据的安全基于密钥而不是算法的保密计算机学院网络教研室52020/2/4第3阶段（1976至今）1976年Diffie和Hellman发表《密码学新方向》提出非对称密码学。密码学开始发挥商用和社会价值。1977年Rivest,Shamir&Adleman提出了RSA公钥算法。90年代逐步出现椭圆曲线等其他公钥算法。同时对称密钥也在不断发展。1977年DES正式成为标准，RC6,MARS,Twofish,Serpent等出现。2001年Rijndael成为DES的替代者，计算机学院网络教研室62020/2/4第4阶段基于物理学的密码学量子密码，号称最安全的密码，理论基础是量子力学，而以往密码学的理论基础是数学。应该再加一阶段计算机学院网络教研室72020/2/4先来一个总体认识-密码系统的模型信源加密明文解密密文接收者明文密钥源密钥源密钥密钥密钥信道入侵者计算机学院网络教研室82020/2/4密码学：研究密码系统和通信安全的一门学科。分为密码编码学和密码分析学。明文(Plaintext):原始的消息称为为明文。密文(Ciphertext):加密后的消息称为为密文。密码算法(CryptographyAlgorithm):是用于加密和解密的数学函数。相关术语计算机学院网络教研室92020/2/4密码体制：密码体制是一个五元组（P,C,K,E,D)满足条件：其中1.P是可能明文的有限集；（明文空间）2.C是可能密文的有限集；（密文空间）3.K是一切可能密钥构成的有限集；（密钥空间）4.任意k∈K,有一个加密算法(ek∈E)和相应的解密算法(dk∈D)，使得ek:P→C和dk:C→P分别为加密解密函数，满足dk(ek(x))=x,这里x∈P。计算机学院网络教研室102020/2/4依据密码个数，分为对称密码和非对称密码。对称密码（又称分组密码）加密密钥能够从解密密钥推算出来，反过来也成立。在大多数对称算法中，加密/解密的密钥是相同的。要求发送者和接收者在安全通信之前，商定一个密钥。非对称密码（公钥私钥密码）加解密的密钥不同，并且已知一个无法推出另一个密码体制分类计算机学院网络教研室112020/2/4对称算法的安全性依赖于密钥，泄漏密钥就意味着任何人都能对消息进行加/解密。分为两类：序列密码和分组密码序列密码：一次只对明文中的单个位（有时对字节），又称序列算法活流密码，是手工和机器密码时代的主流。分组密码：将明文分成固定长度的组，用同一密钥和算法对每一块加密，输出也是固定长度的密文。这些位称为分组（block），又称分组算法。对称密码的特点计算机学院网络教研室122020/2/4经典加密算法：替代：明文的字母由其它字母或数字或符号代替。分以下四种：简单代替密码：将明文字母表中的每个字母用密文字母表中相应的字母来代替。同音代替密码：明文字母表中的每个字母可用密文字母表中的多个字母之一来代替多表代替密码对于不同位置的字母周期使用不同的代替规则。多字母代替密码每次代替多个明文字母。置换：明文字母不变，但顺序打乱(特殊的代替密码)发展总是继承过去计算机学院网络教研室132020/2/4简单替代实例凯撒密码：公元前50年明文：ABCDEFGHIJKLMNOPQRSTUVWXYZ密文：DEFGHIJKLMNOPQRSTUVWXYZABC明文：Systemmodels密文：Vbvwhpprghov多字母替代：ABA→RTQ􀀹ABB→SLL问题：没有隐藏统计信息和关联信息，可用频率分析来破解。计算机学院网络教研室142020/2/4美国密码学家W.F.Friedman在调查了大量英文资料后,得出英文字母的普遍使用规律.计算机学院网络教研室152020/2/4如纵行移位明文：Zhongyuanuniversityoftechnologyzhongyuanuniversityoftechnology密文：znfyhitovenecgrhysnuioatlbyouog置换加密举例计算机学院网络教研室162020/2/42.2对称密码－分组密码为确保数据的安全性,shannon提出了混乱原则和扩散原则。混乱原则：为了避免分析者利用明文和密文之间的依赖关系进行破译，密码的设计应该保证这种以来关系足够复杂。是明文和密文之间、密文和密钥之间的统计相关特性极小化，从而使统计分析攻击不能奏效。扩散原则：为避免密码分析者对密钥的逐段破译，密码的设计应该保证密钥和明文的每位数字能够影响密文中多位的值。产生扩散的最简单方法是通过“置换(Permutation)”（比如：重新排列字符）。计算机学院网络教研室172020/2/4产生背景：1973年5月15日,美国国家标准局(NationalBureauofStandards,NBS)开始公开征集标准加密算法,并公布了它的设计要求:(1)算法必须提供高度的安全性(2)算法必须有详细的说明,并易于理解(3)算法的安全性取决于密钥,不依赖于算法(4)算法适用于所有用户(5)算法适用于不同应用场合(6)算法必须高效、经济分组密码的典型代表DES（DataEncryptionStandard）计算机学院网络教研室182020/2/41974年8月27日,NBS开始第二次征集,IBM提交了算法LUCIFER，该算法由IBM的工程师在1971~1972年研制1975年3月17日,NBS公开了全部细节1976年,NBS指派了两个小组进行评价，11月23日，采纳为联邦标准，批准用于非军事场合的各种政府机构。1977年1月15日,“数据加密标准”FIPSPUB46发布最近的一次评估是在1994年1月，已决定1998年12月以后，DES将不再作为联邦加密标准DES历史计算机学院网络教研室192020/2/4DES算法描述明文IPR0L0fL1R0R1L0f(R0，K1)LiRi-1RiLi-1f(Ri-1，Ki)L15R14R15L14f(R14，K15)L16R15R16L15f(R15，K16)IP-1密文fffK1K2KiK16一轮加密计算机学院网络教研室202020/2/4第一步，对于给定的明文m，通过初时置换矩阵IP获得m0，并分为两部分，前一部分为L0，后一部分为R0，即m0=IP(m)=L0R0.置换矩阵见下图.每一轮下列方法计算Li、Ri,共16轮计算。Li=Ri-1,Ri=Li-1⊕f(Ri-1,Ki)其中，Ki为第i轮使用的子密钥，其生成方案见稍后描述。f(X1,X2)中，X1为32位字符串，X2位48位字符串，输出位32位字符串。DES算法描述计算机学院网络教研室212020/2/4f(X1，X2)计算方法如下：X1由固定的扩展函数E将X1扩展位48位字符串记为X1*，计算X1*⊕X2，并将结果分为8个长度为6位的字符串，并记为B＝B1B2B3B4B5B6B7B8。使用8个S盒，每个S盒为一4×16的矩阵，元素取0～15的整数，如图S盒，Bj记为长度为6的比特串Bj=b1b2b3b4b5b6。计算Sj(bj)的方法是，用b1b6对应的整数确定的Sj的行r，b2b3b4b5对应的整数确定为Sj的列q，第r行q列对应的整数为输出各个S盒输出的8×4＝32位输出，通过置换P得到的结果为函数f的输出。如图置换P。DES算法描述计算机学院网络教研室222020/2/4第三步，应用逆置换IP-1对L16R16进行置换得到密文c。40848165624643239747155523633138646145422623037545135321612936444125220602835343115119592734242105018582633141949175725逆置换IP-1计算机学院网络教研室232020/2/4DES的解密过程将密文C作为输入，以逆序(即K16,K15,…,K1)使用密钥方案，输出明文P计算机学院网络教研室242020/2/4密钥搜索所需的时间取决于密钥空间的大小和执行一次加密所需的时间。若假定DES加密操作需时为100s(一般微处理器能实现)，则搜索整个密钥空间需时为7.2×1015秒，近似为2.28×108年。1997年1月28日，美国的RSA数据安全公司在RSA安全年会上公布了一项“秘密密钥挑战”竞赛，其中包括悬赏1万美元破译密钥长度为56比特的DES。美国克罗拉多洲的程序员Verser从1997年2月18日起，用了96天时间，在Internet上数万名志愿者的协同工作下，成功地找到了DES的密钥，赢得了悬赏的1万美元DES破解计算机学院网络教研室252020/2/41999年1月RSA数据安全会议期间，电子前沿基金会用22小时15分钟就宣告破解了一个DES的密钥。Wiener报道了使用流水线的技术达到每秒5000万个密钥搜索速率的芯片的设计；1993年10万美元的模块包含5760个密钥搜索芯片；DES的搜索造价搜索时间$100,00035小时$1,000,0003.5小时$10,000,00021分钟DES破解计算机学院网络教研室262020/2/4分组密码每次加密的明文数据量是固定的分组长度n，而实用中待加密消息的数据量是不定的，数据格式可能是多种多样的。需要采用适当的工作模式来隐蔽明文的统计特性、数据的格式等，以提高整体的安全性，降低删除、重放、插入和伪造成功的机会。简单已于实现。美国NSB在规定了DES的四种基本工作模式：电子密码本(ECB)，密码反馈链接(CBC)，密码反馈(CFB)，输出反馈(OFB)。分组密码工作模式计算机学院网络教研室272020/2/4电子密码本ECB(ElectronicCodeBook)模式直接利用DES算法分别对各64bits数据组加密简单有效，可并行。同一个64比特明文如果出现多次，其密文总是一样的。误差传递：密文块损坏仅对应明文块损坏xykDESyxkDES-1分组密码工作模式计算机学院网络教研室282020/2/4密码分组链接CBC(CipherBlockChaining)模式密文分组Ci-1被反馈到输入端，明文分组Pi与Ci-1的异或结果被作为DES加密算法的输入，从而得到下一个密文分组，即。解密过程为第一组明文Pi加密时尚无反馈密文，为此收发双方必须选用同一IV。)(1iiKiCPDCxiyikDESyix’kDES-1++64bit存储64bit存储yi-11)(iiKiCCEP分组密码工作模式计算机学院网络教研室292020/2/4k-比特密码反馈CFB(CipherFeedback)模式待加密消息必须按字符(如电传电报)或按比特处理时，可采用CFB模式。实际上将加密算法DES作为一个密钥流产生器，当k＝1时就退化为流密码。CFB与CBC的区别是反馈的密文不再是64bit，而是长度为k，且不是直接与明文相加，而是反馈至密钥产生器。分组密码工作模式计算机学院