第04章-密码学原理.ppt

1、4.1 密码学概况,4.1.1 密码学发展简况 密码学是一门研究信息安全保护的科学。它最早可追溯到几千年前，主要用于军事和外交通信。随着网络与信息技术的发展，密码学的应用不再局限于军事、政治、外交领域，而是逐步应用于社会各个领域，例如电子商务、个人安全通信、网络安全管理等。 密码学的发展可大致划分为四个阶段：,第一个阶段：从古代到1949年。该时期的密码学没有数学理论基础，与其说是科学，不如说是一种艺术。 第二个阶段：从1949年到1975年。标志性事件是香农在1949年发表的著名论文保密系统的信息理论，该文为对称密码系统奠定了理论基础。 第三个阶段：1976年到1990年。密码技术出现了革命

2、性变化，一是开辟了公钥密码学的新纪元，公钥密码体制诞生。二是美国政府提出了数据加密标准(DES)。这两个事件标志着现代密码学的诞生。,第四个阶段：1990年到至今。因特网的普及和信息技术的发展极大地带动了密码学的应用需求，密码技术成为网络与信息安全的核心技术。在这一时期，密码学的应用得到了社会的广泛认同，密码学正影响着网络与信息技术的发展。,4.1.2 密码学基本概念 密码学，是保护明文的秘密以防止攻击者获知的科学。 密码分，析学是在不知道密钥的情况下识别出明文的科学。 明文，是指需要采用密码技术进行保护的消息。 密文，是指用密码技术处理“明文”后的结果，通常称为加密消息。,将明文变换成密文的

3、过程称作加密(encryption)。 其逆过程，即由密文恢复出原明文的过程称作解密(decryption)。 加密过程所使用的一组操作运算规则称作加密算法。 解密时使用的一组运算规则称作解密算法。 加密和解密算法的操作通常都是在密钥(key)控制下进行的，分别称为加密密钥和解密密钥。,4.2 密码体制分类,4.2.1 对称密码体制 又称作私钥密码体制，是广泛应用的普通密码体制。 该体制的特点是加密和解密使用相同的密钥，如图4-1所示。 此密码体制可看成保险柜，密钥就是保险柜的号码。持有号码的人能够打开保险柜，放入文件，然后再关闭它。持有号码的其他人可以打开保险柜，取出文件。没有保险柜号码的人

4、就必须摸索保险柜的打开方法。 当用户应用这种体制时，消息的发送者和接收者必须事先通过安全渠道交换密钥，以保证发送消息或接收消息时能够有供使用的密钥。,图4-1 私钥密码体制原理示意图,密钥分配和管理是极为重要的问题。 为了保证加密消息的安全，密钥分配必须使用安全途径，例如由专门人员负责护送密钥给接收者。 同时，消息发送方和接收方都需要安全保管密钥，防止非法用户读取。 另外的问题是密钥量。由于加密和解密使用同一个密钥，因此，与不同的接收者进行加密通信时，需要有几个不同的密钥。假设网络中有n个使用者，使用者之间共享一个密钥，则共有n(n-1)/2个密钥。如果n很大，密钥将多的无法处理。,在此体制中

5、，使用者A和B具有相同的加、解密能力，因此使用者B无法证实收到的A发来的消息确实来自A。 虽然有不足之处，但对称密码算法处理速度快，常常用作数据加密处理。 目前，典型算法已有DES、IDEA、AES等，其中，DES是美国早期数据加密标准，现在已经被AES取代。,4.2.2 公钥密码体制 又称非对称密码体制，基本原理是在加密和解密的过程中使用不同的密钥。其中，加密密钥可以公开，而只需要把解密密钥安全存放即可。 在安全性方面，密码算法即使公开时，由加密密钥推知解密密钥的计算也是不可行的。 公钥密码体制原理示意如图4-2所示。,图4-2 公钥密码体制原理示意图,公钥密码体制可看成邮桶，任何人都能容易

6、地把邮件放进邮桶，只要打开口子投进去就行了。把邮件放进邮桶是一件公开的事情，但打开邮桶却不是，它是难的，需要吹焊器或其他工具。然而，如果持有秘密信息(钥匙或组合密码)，就很容易打开了。 与对称密码体制相比较，公钥密码体制有以下优点:,(1) 密钥分发方便，可以以公开方式分配加密密钥。例如，因特网中的个人安全通信常将自己的公钥公布在网页中，方便其他人用它进行安全加密。 (2) 密钥量少。网络中的消息发送方可以共用一个公开加密密钥，从而减少密钥数量。只要接收方的解密密钥保密，消息的安全性就能实现。 (3) 支持数字签名。,4.2.3 混合密码体制 利用公钥密码体制分配对称密码体制的密钥，然后使用对

7、称密码体制，进行数据加密和解密运算。 工作原理如图4-3。 第一步，发送者Alice用对称密钥把需要发送的数据加密； 第二步，Alice用Bob的公钥将对称密钥加密，形成数字信封，然后把加密数据和数字信封一起传送给Bob； 第三步，Bob收到Alice的数据后，用自己的私钥将数字信封解密，获取Alice加密消息时的对称密钥； 第四步，Bob使用对称密钥把加密消息解开。,图4-3 混合密码体制原理示意图,4.3 常见密码算法,4.3.1 DES（Data Encryption Standard） DES是数据加密标准，由IBM在20世纪60年代研制出来。 DES的算法是分组加密算法，支持64位明

8、文块加密，其密钥长度为56比特。 但是，随着计算机运算速度的增加和网络计算的进行，在有限的时间内进行大量的运算将变得更可行。1997年，RSA数据安全公司发出了破解DES密文的挑战。,由Roche Verse牵头的一个工程小组动用了70 000多台通过互联网连接起来的计算机，使用暴力攻击程序，大约花费96天的时间找到了正确的DES密钥。 1998年7月，电子前沿基金会(EFF)花费了250 000美元制造的一台机器在56小时里攻破了DES。因此，DES 56比特的密钥长度已不足以保证密码系统的安全了。 NIST于1999年10月25日采用三重DES作为过渡期间的国家标准，以增强DES的安全性，

9、并开始征集AES(Advanced Encryption Standard)算法。,DES算法的原理,DES算法的输入参数有三个：Key、Data、Mode。其中Key为8个字节共64位，是密钥；Data也为8个字节64位，是要加密或解密的数据；Mode为工作方式：加密或解密。 DES算法是这样工作的：如Mode为加密，则用Key对数据Data进行加密，生成Data的密文形式（64位）作为输出结果；如Mode为解密，则用Key对密文形式的数据Data解密，还原为Data的明文形式（64位）作为输出结果。,DES算法的实现步骤,三个步骤： 第一步：变换明文。对给定的64位明文x，通过一个置换表I

10、P来重新排列x，从而构造出64位的x0，x0=IP(x)=L0R0，其中L0表示x0的左32比特，R0表示x0的右32位。 第二步：按照规则对x0进行16轮迭代。规则为 Li = Ri-1 Ri = Lif(Ri-1,Ki) （i=1,2,316） 第一步变换已经得到L0和R0，其中符号表示逻辑运算异或，f表示一种置换，由S盒置换构成，Ki是由密钥编排函数产生的位组。,第三步：对L16R16作逆置换IP-1 ，就得到了密文y。,可以看出，DES加密有四个关键点： 1、IP置换和IP-1逆置换； 2、函数f； 3、子密钥Ki； 4、S盒。,（1）IP置换表和IP-1逆置换表,逆置换表IP-1,（

11、2）函数f,f有两个输入：32位的Ri-1和48位Ki，处理流程如图：,E变换是从Ri-1的32位中选取某些位，构成48位。即将32位扩展为48位，规则根据E选位表，如下：,Ki是由密钥K产生的48位串，具体的算法下面介绍。将E的选位结果与Ki作异或操作，得到一个48位输出。分成8组，每组6位，作为8个S盒的输入。 每个S盒输出4位，共32位，工作原理将在第四步介绍。S盒的输出作为P变换的输入，P的功能是对输入进行置换，P换位表如下：,（3）子密钥ki,假设密钥为K，长度为64位，但是其中第8、16、24、32、40、48、64用作奇偶校验位，实际使用长度为56位。K的下标i的取值范围是1到1

12、6。构造过程如下：,首先，对于给定的密钥K，应用PC1变换进行选位，选定后的结果是56位，设其前28位为C0，后28位为D0。PC1选位如下：,第一轮：对C0作左移LS1得到C1，对D0作左移LS1得到D1，对C1D1应用PC2进行选位，得到K1。其中LS1是左移的位数，如下表。 表中的第一列是LS1，第二列是LS2，以此类推。左移的原理是所有二进位向左移动，原来最左边的比特位移动到最右边。,PC2如下表：,第二轮：对C1，D1作左移LS2得到C2和D2，进一步对C2D2应用PC2进行选位，得到K2。如此继续，分别得到K3，K4K16。,（4）S盒的工作原理,S盒以6位作为输入，而以4位作为输

13、出，现在以S1为例说明其过程。 假设输入为A=a1a2a3a4a5a6，则a2a3a4a5所代表的数是0到15之间的一个数，记为：k=a2a3a4a5；由a1a6所代表的数是0到3间的一个数，记为h=a1a6。在S1的h行、k列找到一个数B，B在0到15之间，它可以用4位二进制表示，为B=b1b2b3b4，这就是S1的输出。 DES算法的解密过程是一样的，区别仅仅在于第一次迭代时用子密钥K16，第二次K15、最后一次用K1，算法本身并没有任何变化。,S1选位表：,4.3.2 IDEA (International Data Encryption Algorithm) IDEA是国际数据加密算法

14、，是一个分组加密算法，其明文和密文分组都是64比特，密钥长度为128比特。 该算法是由来学嘉(X.J.Lai)和Massey提出的建议标准算法，已在PGP中得到应用。IDEA算法能够接受64比特分组加密处理，同一算法既可用于加密又可用于解密。,4.3.3 AES (Advanced Encryption Standard) 1997年4月15日，美国国家标准技术研究所(NIST)发起征集AES算法的活动。目的是确定一个非保密的、公开的、全球免费使用的分组密码算法，用于保护下一世纪政府的敏感信息。 NIST规定候选算法必须满足下面的要求： * 密码必须是没有密级的，绝不能像保护商业秘密那样来保护

15、它； * 算法的全部描述必须公开披露；,* 可以在世界范围内免费使用； * 支持至少128位的分组； * 密钥长度至少为128、192和256比位。 截至1998年8月，提交了15个候选算法用于AES。由于Rijndeal提供了安全性、软件和硬件性能、低内存需求以及灵活性的最好的组合，因此NIST在2000年10月2日确定选择Rijndael作为AES。,4.3.4 RSA Whitefield Diffie和Martin Hellman 于1976年提出了公钥密码系统的思想。MIT的Ronald Rivist、Adi Shamir和Len Adlemar设计出了第一个公钥密码体制。,RSA算

16、法基于大整数分解的困难性，描述如下： 第一步，生成两个大素数 p 和 q ； 第二步，计算这两个素数的乘积 n = pq ； 第三步，计算小于n且与n互素的整数的个数，即(n)=(p1)(q1) ； 第四步，选取一个随机数e，满足1e(n)，且e和(n)互素，即gcd(e,(n) = 1 ； 第五步，计算 d = ( k(n) + 1 ) / e，其中，k是p1和q1的最大公约数； 第六步，用d作为私钥，而n和e作为公钥。,一个RSA加密的实例。 设素数 p=3，q=17，并令e=13，则RSA加密如下： (1) 计算 n = pq = 317 = 51，得公钥 n=51，e=13 ； (2)

17、 计算(n) = (p1)(q1) = 216 = 32 ； (3) 计算 d = ( k(n)+1 ) / e = (232+1)/13 = 5，即私钥是d=5。,(4) 加密和解密处理。 Alice要将明文“2”发送给Bob，首先用Bob的公钥加密明文（Bob的公钥是n=51、e=13 ）， C = Me mod n = 213 mod 51 = 32 Bob收到密文C后，用自己的私钥d（5）解密， M = Cd mod n = 325 mod 51 = 2,RSA安全性在于要使选取的素数p和q足够大，使得给定了它们的乘积n后，在事先不知道p或q的情况下分解n，在计算上不可行。 因此，破译

18、RSA密码体制基本上等价于分解n。 从长远的安全性考虑，要求n的长度至少应为2048位，或者是616位的十进制数。,4.4 杂 凑 函 数,杂凑函数也称哈希（Hash）函数，它能将任意长度的信息转换成固定长度的信息(哈希值、消息摘要)，并且不同信息所生成的哈希值不一样。令h表示Hash函数，则h应满足下列条件： n h的输入是任意长度的消息； n h的输出长度是固定的； n 给定h和M，计算h(M)是容易的； n 给定哈希值，求其逆是不可行的； n给定h，找两个不同的消息M1和M2，使得h(M1)=h(M2)在计算上是不可行的。,Hash函数的主要功能是，保护数据的完整性、认证。 例如，网页防

19、篡改应用。网页文件管理者首先对网页文件生成Hash值，并将Hash值存放在安全的地方。然后定时再计算这些网页文件的Hash值，如果新产生的Hash值与备份的Hash值不一样，则说明网页文件被篡改了。 目前，主要Hash算法有MD5、SHA。 MD5能产生128位长度的哈希值，广泛用于网络中文件的完整性检查。 但是，据最新研究表明，MD5的安全性受到挑战，已被中国的王小云女士攻破。 而SHA由NIST和NSA研究开发，在美国政府中使用，作为安全哈希标准，SHA产生的哈希值比MD5长，有160位。,4.5 数 字 签 名,数字签名(Digital Signature)是手写签名的电子模拟，是通过电

20、子信息计算处理，产生的一段特殊消息，该消息具有与手写签名一样的特点，是可信的、不可伪造的、不可重用的、不可抵赖的以及不可修改的。因而，将这种消息称为数字签名。 数字签名的特性： n 不可伪造； n 不可复制； n不可修改； n不可抵赖。,数字签名的功能： 解决否认、伪造、篡改、冒充等问题，具体为： n 发送者事后不能否认发送的数据签名； n接收者能够核实发送者的签名，但不能伪造发送者的签名； n攻击者不能修改经签名的数据； n攻击者不能冒充另一用户发送数据。,数字签名方案一般由签名算法和验证算法组成。签名算法的密钥是保密的；而验证算法则是公开的。 典型的数字签名方案有RSA签名体制、Rabin

21、签名体制、ElGamal签名体制和DSS标准。 签名与加密相似，签名者利用私钥对需签名的数据进行加密运算，验证方利用签名者的 公钥对签名数据做解密运算。 签名与加密的不同之处在于，加密的目的是保护信息不被非授权用户访问，而签名的目的是让消息接收者确信信息的发送者是谁，信息是否被他人篡改。,下面RSA数字签名的基本流程。 假设Alice需要签名发送一份电子合同文件给Bob。Alice的签名步骤如下： 第一步，Alice使用Hash函数将电子合同文件生成一个消息摘要。 第二步，Alice使用自己的私钥，把消息摘要加密，形成一个数字签名。 第三步，Alice把电子合同文件和数字签名一同发送给Bob。

22、 过程如图4-4所示。,图4-4 数字签名过程示意图,Bob收到Alice发送的电子合同文件及数字签名后，要验证电子合同文件，验证步骤如下： 第一步，Bob使用与Alice相同的Hash算法，计算出所收到电子合同文件的消息摘要。 第二步，Bob使用Alice的公钥，解密来自Alice的消息摘要，恢复出明文形式的消息摘要。 第三步，Bob比较自己产生的消息摘要和恢复出来的消息摘要之间的异同。若两个消息摘要相同，则表明电子合同文件来自Alice。如果两个消息摘要的比较结果不一致，则表明电子合同文件已被篡改。,图4-5 验证数字签名过程示意图,4.6 安 全 协 议,4.6.1 SSL SSL(Se

23、cure Socket Layer)协议是介于应用层和TCP层之间的安全通信协议。 目的是当两个应用层之间相互通信时，使被传送的信息具有保密性及可靠性。 SSL的工作原理是将应用层的信息加密和签名处理后再经TCP/IP网络送至对方，收方经验证鉴别无误后解密还原信息。,图4-6 SSL协议工作机制,SSL协议是一个分层协议，由两个子协议组成。 低层协议为SSL记录协议(SSL Record Protocol)，位于传输层(如TCP)之上。SSL记录协议的用途是将各种不同的较高层协议(如HTTP或SSL握手协议)封装后再传送。 高层协议为SSL握手协议(SSL Handshake Protocol

24、)，其用途是为两个应用程序在开始传送或接收数据前，提供服务器和客户端间的相互认证，并相互协商决定双方通信使用的加密算法及加密密钥。 如图4-7所示。,图4-7 SSL协议组成示意图,SSL协议提供三种安全服务： (1) 保密性。握手协议产生密钥(key)后才开始加、解密数据。加、解密使用对称式密码算法，例如DES、AES等。 (2) 点对点之间的身份认证。采用数字签名，例如RSA签名体制、DSS签名标准等。 (3) 可靠性。信息传送时包含信息完整性检查，使用具密钥之哈希函数，例如SHA、MD5等。,SSL协议是个分层的协议(layered protocol)，于每一层中其消息(message)

25、内有许多可能包含消息长度、叙述、内容(content)等的字段。SSL记录协议(Record Protocol)数据处理过程如图4-8所示，其步骤如下: (1) 将数据分割成若干分组。 (2) 将已分割数据压缩。 (3) 加上消息认证码(MAC)。 (4) 将数据加密，生成即将发送的消息。 (5) 接收端将收到的消息解密、验证、解压缩，再重组后传送至较高层(例如应用层)，即完成接收。,图4-8 SSL记录协议数据处理示意图,4.7 密码理论的网络安全应用举例,4.7.1 路由器安全应用 目前，路由器面临的威胁有路由信息交换的篡改、伪造、泄露、路由器非法访问等。 为了解决路由器的安全问题，密码学已被广泛应用到路由器安全防范工作中，其主要用途有： (1) 路由器口令管理。为了使路由器的口令能安全存储，路由器先用MD5把管理员口令信息进行Hash计算，然后再保存到路由器配置文件中。,(2) 远程安全访问路由器。远程访问路由器常用Telnet，但Telnet容易泄露敏感的口令信息，因此，管