网络与信息安全

密码学基础（2）胡建斌北京大学网络与信息安全研究室E-mail:[e-mail]~hjbin目录1.数据加密标准2.公开密钥算法数据加密标准（DataEncryptionStandard,DES)背景发明人：美国IBM公司W.Tuchman和C.Meyer1971-1972年研制成功基础：1967年美国HorstFeistel提出的理论产生：美国国家标准局（NBS)1973年5月到1974年8月两次发布通告，公开征求用于电子计算机的加密算法。经评选从一大批算法中采纳了IBM的LUCIFER方案标准化：DES算法1975年3月公开发表，1977年1月15日由美国国家标准局颁布为数据加密标准（DataEncryptionStandard），于1977年7月15日生效背景美国国家安全局（NSA,NationalSecurityAgency)参与了美国国家标准局制定数据加密标准的过程。NBS接受了NSA的某些建议，对算法做了修改，并将密钥长度从LUCIFER方案中的128位压缩到56位1979年，美国银行协会批准使用DES1980年，DES成为美国标准化协会(ANSI)标准1984年2月，ISO成立的数据加密技术委员会(SC20)在DES基础上制定数据加密的国际标准工作DES概述分组加密算法：明文和密文为64位分组长度对称算法：加密和解密除密钥编排不同外，使用同一算法密钥长度：56位，但每个第8位为奇偶校验位，可忽略密钥可为任意的56位数，但存在弱密钥，容易避开采用混乱和扩散的组合，每个组合先替代后置换，共16轮只使用了标准的算术和逻辑运算，易于实现DES加密算法的一般描述输入64比特明文数据初始置换IP在密钥控制下16轮迭代初始逆置换IP-1输出64比特密文数据交换左右32比特DES加密过程DES加密过程)(6416,,2,1),(16,,2,1)64(1616111100LRIPbitikRfLRiRLbitIPRLiiiiii密文输入码令i表示迭代次数，表示逐位模2求和，f为加密函数DES解密过程令i表示迭代次数，表示逐位模2求和，f为加密函数)(641,,15,16),(1,,15,16)64(0011111616LRIPbitikRfRLiLRbitIPLRiiiiii明文密文DES中的各种置换、扩展和替代初始置换IP和初始逆置换IP—1IP和IP—12014'MM1420'''MMIPIP—1Li-1（32比特）Ri-1（32比特）Li（32比特）48比特寄存器选择扩展运算E48比特寄存器子密钥Ki（48比特）32比特寄存器选择压缩运算S置换运算PRi（32比特）Li=Ri-1DES的一轮迭代扩展置换Ｅ-盒－32位扩展到48位扩展压缩替代S-盒－48位压缩到32位共8个S盒S-盒1S-盒2S-盒3S-盒4S-盒5S-盒6S-盒7S-盒8S-盒的构造1234561626234521133911001110019bbbbbbbbSbbbb行：-盒子行列列：值：14=1100S-盒的构造DES中其它算法都是线性的，而S-盒运算则是非线性的S-盒不易于分析，它提供了更好的安全性所以S-盒是算法的关键所在S-盒的构造准则S盒的每一行是整数0，…，15的一个置换没有一个S盒是它输入变量的线性函数改变S盒的一个输入位至少要引起两位的输出改变对任何一个S盒和任何一个输入X，S（X）和S(X001100）至少有两个比特不同（这里X是长度为6的比特串）对任何一个S盒，对任何一个输入对e,f属于{0,1},S(X)S(X11ef00)对任何一个S盒，如果固定一个输入比特，来看一个固定输出比特的值，这个输出比特为0的输入数目将接近于这个输出比特为1的输入数目S-盒的构造要求S-盒是许多密码算法的唯一非线性部件,因此,它的密码强度决定了整个算法的安全强度提供了密码算法所必须的混乱作用如何全面准确地度量S-盒的密码强度和设计有效的S-盒是分组密码设计和分析中的难题非线性度、差分均匀性、严格雪崩准则、可逆性、没有陷门置换p-盒的构造p-盒的构造准则P置换的目的是提供雪崩效应明文或密钥的一点小的变动都引起密文的较大变化k1（56位）(48位)ki（56位）（48位）64位密钥置换选择1C0（28位）D0（28位）循环左移循环左移C1（28位）D1（28位）循环左移循环左移Ci（28位）Di（28位）置换选择2置换选择2密钥表的计算逻辑循环左移：119121102321124212252132621427215282161DES中的子密钥的生成密钥置换算法的构造准则设计目标：子密钥的统计独立性和灵活性实现简单速度不存在简单关系：(给定两个有某种关系的种子密钥,能预测它们轮子密钥之间的关系)种子密钥的所有比特对每个子密钥比特的影响大致相同从一些子密钥比特获得其他的子密钥比特在计算上是难的没有弱密钥Li-1（32比特）Ri-1（32比特）Li（32比特）48比特寄存器选择扩展运算E48比特寄存器子密钥Ki（48比特）32比特寄存器选择压缩运算S置换运算PRi（32比特）Li=Ri-1DES的一轮迭代DES加密算法的一般描述DES的工作模式电子密码本ECB(electroniccodebookmode)密码分组链接CBC(cipherblockchaining)密码反馈CFB(cipherfeedback)输出反馈OFB(outputfeedback)iKiiKiC=E(P)P=D(C)电子密码本ECBECB的特点简单和有效可以并行实现不能隐藏明文的模式信息相同明文生成相同密文，同样信息多次出现造成泄漏对明文的主动攻击是可能的信息块可被替换、重排、删除、重放误差传递：密文块损坏仅对应明文块损坏适合于传输短信息密码分组链接CBCiKii-1iKii-1C=E(PC)P=D(C)CCBC的特点没有已知的并行实现算法能隐藏明文的模式信息需要共同的初始化向量IV相同明文生成不同密文初始化向量IV可以用来改变第一块对明文的主动攻击是不容易的信息块不容易被替换、重排、删除、重放误差传递：密文块损坏两明文块损坏安全性好于ECB适合于传输长度大于64位的报文，还可以进行用户鉴别,是大多系统的标准如SSL、IPSec密码反馈CFBCFB:分组密码流密码假定：Si为移位寄存器,传输单位为jbit加密:Ci=Pi(EK(Si)的高j位)Si+1=(Sij)|Ci解密:Pi=Ci(EK(Si)的高j位)Si+1=(Sij)|Ci密码反馈CFB加密Ci=Pi(EK(Si)的高j位);Si+1=(Sij)|Ci密码反馈CFB解密Pi=Ci(EK(Si)的高j位);Si+1=(Sij)|CiCFB的特点分组密码流密码没有已知的并行实现算法隐藏了明文模式需要共同的移位寄存器初始值IV对于不同的消息，IV必须唯一误差传递：一个单元损坏影响多个单元输出反馈OFBOFB:分组密码流密码假定：Si为移位寄存器,传输单位为jbit加密:Ci=Pi(EK(Si)的高j位)Si+1=(Sij)|(EK(Si)的高j位)解密:Pi=Ci(EK(Si)的高j位)Si+1=(Sij)|(EK(Si)的高j位)输出反馈OFB加密Ci=Pi(EK(Si)的高j位);Si+1=(Sij)|(EK(Si)的高j位)输出反馈OFB解密Pi=Ci(EK(Si)的高j位);Si+1=(Sij)|(EK(Si)的高j位)0FB的特点分组密码流密码没有已知的并行实现算法隐藏了明文模式需要共同的移位寄存器初始值IV对于不同的消息，IV必须唯一误差传递：一个单元损坏只影响对应单元对明文的主动攻击是可能的信息块可被替换、重排、删除、重放安全性较CFB差多重DES两重DES三重DESDES的安全性F函数(S-Box)设计原理未知密钥长度的争论DES的破译弱密钥与半弱密钥DES密钥长度关于DES算法的另一个最有争议的问题就是担心实际56比特的密钥长度不足以抵御穷举式攻击，因为密钥量只有个早在1977年，Diffie和Hellman已建议制造一个每秒能测试100万个密钥的VLSI芯片。每秒测试100万个密钥的机器大约需要一天就可以搜索整个密钥空间。他们估计制造这样的机器大约需要2000万美元1756102DES密钥长度在CRYPTO’93上，Session和Wiener给出了一个非常详细的密钥搜索机器的设计方案，这个机器基于并行运算的密钥搜索芯片，所以16次加密能同时完成。花费10万美元，平均用1.5天左右就可找到DES密钥美国克罗拉多洲的程序员Verser从1997年2月18日起，用了96天时间，在Internet上数万名志愿者的协同工作下，成功地找到了DES的密钥，赢得了悬赏的1万美元DES密钥长度1998年7月电子前沿基金会（EFF）使用一台25万美圆的电脑在56小时内破译了56比特密钥的DES1999年1月RSA数据安全会议期间，电子前沿基金会用22小时15分钟就宣告破解了一个DES的密钥破译DES1990年，以色列密码学家EliBiham和AdiShamir提出了差分密码分析法，可对DES进行选择明文攻击线性密码分析比差分密码分析更有效弱密钥与半弱密钥弱密钥:EKEK=I，DES存在4个弱密钥即：半弱密钥:EK1=EK2，至少有12个半弱密钥即：(())kkpEEP12()()kkCEPEP其它常规分组加密算法TripleDESIDEARC5RC6AES其他一些较实用的算法，如Blowfish，CAST，以及RC2等使用常规加密进行保密通信易受攻击的位置电话公司市话局接线盒链路加密和端到端加密存储转发通信的加密覆盖范围各种加密策略包含的内容链路层加密对于在两个网络节点间的某一次通信链路,链路加密能为网上传输的数据提供安全保证所有消息在被传输之前进行加密,在每一个节点对接收到的消息进行解密,然后先使用下一个链路的密钥对消息进行加密,再进行传输链路层加密的优点由于在每一个中间传输节点消息均被解密后重新进行加密,因此,包括路由信息在内的链路上的所有数据均以密文形式出现。这样,链路加密就掩盖了被传输消息的源点与终点由于填充技术的使用以及填充字符在不需要传输数据的情况下就可以进行加密,这使得消息的频率和长度特性得以掩盖,从而可以防止对通信业务进行分析链路层加密的缺点链路加密通常用在点对点的同步或异步线路上,它要求先对在链路两端的加密设备进行同步,然后使用一种链模式对链路上传输的数据进行加密。这就给网络的性能和可管理性带来了副作用在一个网络节点,链路加密仅在通信链路上提供安全性,消息以明文形式存在,因此所有节点在物理上必须是安全的,否则就会泄漏明文内容在传统的加密算法中,用于解密消息的密钥与用于加密的密钥是相同的,该密钥必须被秘密保存,并按一定规则进行变化。这样,密钥分配在链路加密系统中就成了一个问题,因为每一个节点必须存储与其相连接的所有链路的加密密钥,这就需要对密钥进行物理传送或者建立专用网络设施。而网络节点地理分布的广阔性使得这一过程变得复杂,同时增加了密钥连续分配时的费用节点加密节点在操作方式上与链路加密是类似的:两者均在通信链路上为传输的消息提供安全性;都在中间节点先对消息进行解密,然后进行加密。因为要对所有传输的数据进行加密,所以加密过程对用户是透明的然而,与链路加密不同,节点加密不允许消息在网络节点以明文形式存在,它先把收到的消息进行解密,然后采用另一个不同的密钥进行加密,这一过程是在节点上的一个安全模块中进行节点加密要求报头和路由信息以明文形式传输,以便中间节点能得