网络与信息安全

1、密码学根底2胡建斌北京大学网络与信息平安研讨室: /hjbin .目 录数据加密规范公开密钥算法.数据加密规范Data Encryption Standard,DES).背景发明人：美国IBM公司 W. Tuchman 和 C. Meyer 1971-1972年研制胜利根底：1967年美国Horst Feistel提出的实际产生：美国国家规范局NBS)1973年5月到1974年8月两次发布通告， 公开征求用于电子计算机的加密算法。经评选从一大批算法中采用 了IBM的LUCIFER方案规范化：DES算法1975年3月公开发表

2、，1977年1月15日由美国国家标 准局公布为数据加密规范Data Encryption Standard，于 1977年7月15日生效.背景美国国家平安局NSA, National Security Agency)参与了美国国家规范局制定数据加密规范的过程。NBS接受了NSA的某些建议，对算法做了修正，并将密钥长度从LUCIFER方案中的128位紧缩到56位1979年，美国银行协会同意运用DES1980年，DES成为美国规范化协会(ANSI)规范1984年2月，ISO成立的数据加密技术委员会(SC20)在DES根底上制定数据加密的国际规范任务.DES概述分组加密算法：明文和密文为64位分组长

3、度对称算法：加密和解密除密钥编排不同外，运用同一算法密钥长度：56位，但每个第8位为奇偶校验位，可忽略密钥可为恣意的56位数，但存在弱密钥，容易避开采用混乱和分散的组合，每个组合先替代后置换，共16轮只运用了规范的算术和逻辑运算，易于实现.DES加密算法的普通描画.输入64比特明文数据初始置换IP在密钥控制下16轮迭代初始逆置换IP-1输出64比特密文数据交换左右32比特 DES加密过程.DES加密过程令i表示迭代次数，表示逐位模2求和，f为加密函数.DES解密过程令i表示迭代次数，表示逐位模2求和，f为加密函数.DES中的各种置换、扩展和替代.初始置换IP和初始逆置换IP1 .IP和IP1I

4、PIP1.Li-132比特Ri-132比特Li32比特48比特存放器选择扩展运算E48比特存放器子密钥Ki48比特32比特存放器选择紧缩运算S置换运算PRi32比特Li=Ri-1DES的一轮迭代.扩展置换-盒32位扩展到48位扩展.紧缩替代S-盒48位紧缩到32位共8个S盒.S-盒1S-盒2S-盒3S-盒4S-盒5S-盒6S-盒7S-盒8.S-盒的构造.S-盒的构造DES中其它算法都是线性的，而S-盒运算那么是非线性的S-盒不易于分析，它提供了更好的平安性所以S-盒是算法的关键所在.S-盒的构造准那么S盒的每一行是整数0，15的一个置换没有一个S盒是它输入变量的线性函数改动S盒的一个输入位至少

5、要引起两位的输出改动对任何一个S盒和任何一个输入X，SX和 S(X001100至少有两个比特不同这里X是长度为6的比特串对任何一个S盒，对任何一个输入对e,f属于0,1,S(X) S(X11ef00) 对任何一个S盒，假设固定一个输入比特，来看一个固定输出比特的值，这个输出比特为0的输入数目将接近于这个输出比特为1的输入数目.S-盒的构造要求S-盒是许多密码算法的独一非线性部件,因此,它的密码强度决议了整个算法的平安强度提供了密码算法所必需的混乱作用如何全面准确地度量S-盒的密码强度和设计有效的S-盒是分组密码设计和分析中的难题非线性度、差分均匀性、严厉雪崩准那么、可逆性、没有陷门.置换p-盒

6、的构造.p-盒的构造准那么P置换的目的是提供雪崩效应明文或密钥的一点小的变动都引起密文的较大变化.DES中的子密钥的生成.密钥置换算法的构造准那么设计目的：子密钥的统计独立性和灵敏性实现简单速度不存在简单关系：( 给定两个有某种关系的种子密钥,能预测它们轮子密钥之间的关系)种子密钥的一切比特对每个子密钥比特的影响大致一样从一些子密钥比特获得其他的子密钥比特在计算上是难的没有弱密钥.Li-132比特Ri-132比特Li32比特48比特存放器选择扩展运算E48比特存放器子密钥Ki48比特32比特存放器选择紧缩运算S置换运算PRi32比特Li=Ri-1DES的一轮迭代.DES加密算法的普通描画.DE

7、S的任务方式.电子密码本 ECB (electronic codebook mode)密码分组链接 CBC (cipher block chaining)密码反响 CFB (cipher feedback)输出反响 OFB (output feedback).电子密码本ECB.ECB的特点简单和有效可以并行实现不能隐藏明文的方式信息 一样明文生成一样密文，同样信息多次出现呵斥走漏对明文的自动攻击是能够的 信息块可被交换、重排、删除、重放误差传送：密文块损坏仅对应明文块损坏适宜于传输短信息.密码分组链接CBC.CBC的特点没有知的并行实现算法能隐藏明文的方式信息 需求共同的初始化向量IV 一样明

8、文生成不同密文 初始化向量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=C

9、i(EK(Si)的高j位); Si+1=(Sij)|Ci .CFB的特点分组密码流密码没有知的并行实现算法隐藏了明文方式需求共同的移位存放器初始值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位).输出反响OF

10、B解密Pi=Ci(EK(Si)的高j位); Si+1=(Sij)|(EK(Si)的高j位).0FB的特点分组密码流密码没有知的并行实现算法隐藏了明文方式需求共同的移位存放器初始值IV对于不同的音讯，IV必需独一误差传送：一个单元损坏只影响对应单元对明文的自动攻击是能够的 信息块可被交换、重排、删除、重放平安性较CFB差.多重DES.两重DES.三重DES.DES的平安性. F函数(S-Box)设计原理未知 密钥长度的争论 DES的破译 弱密钥与半弱密钥.DES密钥长度关于DES算法的另一个最有争议的问题就是担忧实践56比特的密钥长度缺乏以抵御穷举式攻击，由于密钥量只需 个 早在1977年，Di

11、ffie和Hellman已建议制造一个每秒能测试100万个密钥的VLSI芯片。每秒测试100万个密钥的机器大约需求一天就可以搜索整个密钥空间。他们估计制造这样的机器大约需求2000万美圆.DES密钥长度在CRYPTO93上，Session和Wiener给出了一个非常详细的密钥搜索机器的设计方案，这个机器基于并行运算的密钥搜索芯片，所以16次加密能同时完成。破费10万美圆，平均用1.5天左右就可找到DES密钥美国克罗拉多洲的程序员Verser从1997年2月18日起，用了96天时间，在Internet上数万名志愿者的协同任务下，胜利地找到了DES的密钥，博得了悬赏的1万美圆.DES密钥长度199

12、8年7月电子前沿基金会EFF运用一台25万美圆的电脑在56小时内破译了56比特密钥的DES1999年1月RSA数据平安会议期间，电子前沿基金会用22小时15分钟就宣告破解了一个DES的密钥.破译DES1990年，以色列密码学家Eli Biham和Adi Shamir提出了差分密码分析法，可对DES进展选择明文攻击线性密码分析比差分密码分析更有效 .弱密钥与半弱密钥弱密钥: EKEK = I ，DES存在4个弱密钥 即：半弱密钥: EK1 = EK2 ，至少有12个半弱密钥 即：.其它常规分组加密算法.Triple DES IDEA RC5 RC6 AES其他一些较适用的算法，如Blowfish

13、，CAST，以及RC2等.运用常规加密进展严密通讯.易受攻击的位置公司市话局接线盒.链路加密和端到端加密.存储转发通讯的加密覆盖范围.各种加密战略包含的内容.链路层加密对于在两个网络节点间的某一次通讯链路,链路加密能为网上传输的数据提供平安保证一切音讯在被传输之前进展加密,在每一个节点对接纳到的音讯进展解密,然后先运用下一个链路的密钥对音讯进展加密,再进展传输.链路层加密的优点由于在每一个中间传输节点音讯均被解密后重新进展加密,因此,包括路由信息在内的链路上的一切数据均以密文方式出现。这样,链路加密就掩盖了被传输音讯的源点与终点由于填充技术的运用以及填充字符在不需求传输数据的情况下就可以进展加

14、密,这使得音讯的频率和长度特性得以掩盖,从而可以防止对通讯业务进展分析.链路层加密的缺陷链路加密通常用在点对点的同步或异步线路上,它要求先对在链路两端的加密设备进展同步,然后运用一种链方式对链路上传输的数据进展加密。这就给网络的性能和可管理性带来了副作用在一个网络节点,链路加密仅在通讯链路上提供平安性,音讯以明文方式存在,因此一切节点在物理上必需是平安的,否那么就会走漏明文内容在传统的加密算法中,用于解密音讯的密钥与用于加密的密钥是一样的,该密钥必需被保管,并按一定规那么进展变化。这样,密钥分配在链路加密系统中就成了一个问题,由于每一个节点必需存储与其相衔接的一切链路的加密密钥,这就需求对密钥

15、进展物理传送或者建立公用网络设备。而网络节点地理分布的宽广性使得这一过程变得复杂,同时添加了密钥延续分配时的费用.节点加密节点在操作方式上与链路加密是类似的:两者均在通讯链路上为传输的音讯提供平安性;都在中间节点先对音讯进展解密,然后进展加密。由于要对一切传输的数据进展加密,所以加密过程对用户是透明的然而,与链路加密不同,节点加密不允许音讯在网络节点以明文方式存在,它先把收到的音讯进展解密,然后采用另一个不同的密钥进展加密,这一过程是在节点上的一个平安模块中进展节点加密要求报头和路由信息以明文方式传输,以便中间节点能得到如何处置音讯的信息。因此这种方法对于防止攻击者分析通讯业务是脆弱的.端到端

16、加密端到端加密允许数据在从源点到终点的传输过程中一直以密文方式存在采用端到端加密(又称脱线加密或包加密),音讯在被传输时到达终点之前不进展解密,由于音讯在整个传输过程中均遭到维护,所以即使有节点被损坏也不会使音讯泄露.端到端加密的优点端到端加密系统的价钱廉价些,与链路加密和节点加密相比更可靠,更容易设计、实现和维护端到端加密防止了其它加密系统所固有的同步问题,由于每个报文包均是独立被加密的,所以一个报文包所发生的传输错误不会影响后续的报文包从用户对平安需求的直觉上讲,端到端加密更自然些。单个用户能够会选用这种加密方法,以便不影响网络上的其他用户,此方法只需求源和目的节点是严密的即可.端到端加密

17、的缺陷通常不允许对音讯的目的地址进展加密,这是由于每一个音讯所经过的节点都要用此地址来确定如何传输音讯由于这种加密方法不能掩盖被传输音讯的源点与终点,因此它对于防止攻击者分析通讯业务是脆弱的.目 录数据加密规范公开密钥算法.公开密钥算法 公开密钥算法是非对称算法，即密钥分为公钥和私钥，因此称双密钥体制 双钥体制的公钥可以公开，因此也称公钥算法 公钥算法的出现，给密码的开展开辟了新的方向。公钥算法虽然曾阅历了20多年的开展，但仍具有强劲的开展势头，在鉴别系统和密钥交换等平安技术领域起着关键的作用.公开密钥算法的提出公钥密码学是1976年由Diffie和Hellman在其“密码学新方向一文中提出的

18、，见文献： W.Diffie and M.E.Hellman, New Directrions in Cryptography， IEEE Transaction on Information Theory, V.IT-22.No.6, Nov 1976, PP.644-654.公开密钥算法的提出RSA公钥算法是由Rivest,Shamir和Adleman在1978年提出来的参见Communitions of the ACM. Vol.21.No.2. Feb. 1978, PP.120-126该算法的数学根底是初等数论中的Euler欧拉)定理，并建立在大整数因子的困难性之上.加密与解密由不同

19、的密钥完成 加密： 解密：知道加密算法，从加密密钥得到解密密钥在计算上是不可行的两个密钥中任何一个都可以作为加密而另一个用作解密不是必需的公开密钥算法的根本要求.基于公开密钥的加密过程.用公钥密码实现严密 用户拥有本人的密钥对(KU,KR) 公钥 KU公开，私钥KR严密 .基于公开密钥的鉴别过程.用公钥密码实现鉴别 条件：两个密钥中任何一个都可以用作加密而另外一个用作解密鉴别： 鉴别严密 .公开密钥算法公钥算法的种类很多，具有代表性的三种密码： 基于整数分解难题IFP的算法体制 基于离散对数难题DLP算法体制基于椭圆曲线离散对数难题ECDLP的算法体制.Diffie-Hellman密钥交换算法

20、.单向陷门函数函数 满足以下条件的函数f： (1) 给定x，计算y=f(x)是容易的 (2) 给定y, 计算x使y=f(x)是困难的 (3) 存在z，知z 时, 对给定的任何y，假设相应的x存 在，那么计算x使y=f(x)是容易的所谓计算x= f-1(Y)困难是指计算上相当复杂，已无实践意义.单向陷门函数阐明仅满足(1)、(2)两条的称为单向函数；第(3)条称为陷门性，z 称为陷门信息当用陷门函数f作为加密函数时，可将f公开，这相当于公开加密密钥，此时加密密钥便称为公开钥，记为Pkf函数的设计者将z严密，用作解密密钥，此时z称为钥匙，记为Sk。由于设计者拥有Sk，他自然可以解出x=f-1(y)

21、单向陷门函数的第(2)条性质阐明窃听者由截获的密文y=f(x)推测x是不可行的.Diffie-Hellman密钥交换算法Diffie和Hellman在其里程碑意义的文章中，虽然给出了密码的思想，但是没有给出真正意义上的公钥密码实例，也既没能找出一个真正带陷门的单向函数然而，他们给出单向函数的实例，并且基于此提出Diffie-Hellman密钥交换算法.Diffie-Hellman密钥交换算法的原理基于有限域中计算离散对数的困难性问题之上：设F为有限域，gF是F的乘法群 F*=F0=，并且对恣意正整数x，计算gx是容易的；但是知g和y求x使y= gx，是计算上几乎不能够的这个问题称为有限域F上的

22、离散对数问题。公钥密码学中运用最广泛的有限域为素域FP.Diffie-Hellman密钥交换协议描画Alice和Bob协商好一个大素数p，和大的整数g，1gp，g最好是FP中的本原元，即FP*p和g无须严密，可为网络上的一切用户共享.Diffie-Hellman密钥交换协议描画当Alice和Bob要进展严密通讯时，他们可以按如下步骤来做： (1) Alice选取大的随机数x，并计算 X = gx(mod P) (2) Bob选取大的随机数x，并计算 X = gx (mod P) (3) Alice将X传送给Bob；Bob将X 传送给Alice (4) Alice计算K= (X )X(mod P

23、); Bob计算K =X) X (mod P), 易见，K = K =g xx (mod P)由(4)知，Alice和Bob已获得了一样的值K双方以K作为加解密钥以传统对称密钥算法进展严密通讯.RSA 算法.Euler 函数 一切模m和r同余的整数组成剩余类r 剩余类r中的每一个数和m互素的充要条件是r和m互素 和m互素的同余类数目用(m)表示，称m的Euler函数 当m是素数时，小于m的一切整数均与m互素，因此(m)=m-1对n=pq, p和q 是素数，(n)=(p)(q)=(p-1)(q-1).Euler 函数举例 设p=3, q=5, 那么 15=3-1*5-1=8 这8个模15的剩余类是： 1，2，4，7，8，11，13，14 .RSA算法的实现 实现的步骤如下：Bob为实现者 (1) Bob寻觅出两个大素数p和q (2) Bob计算出n=pq 和(n)=(p-1)(q-1) (3) Bob选择一个随机数e (0e (n)，满足(e,(n)=1 (4) Bob运用辗转相除法计算d=e-1(mod(n) (5) Bob在目录中公开n和e作为公钥密码分析者攻击RSA体制的关键点在于如