密码学基础及其应用(数据加密、数据安全、消息认证与数字签名)

1Total162ComputerSystemSecurity1计算机系统安全计算机系统安全张载龙主讲南京邮电大学信息网络技术研究所江苏省通信与网络技术工程研究中心Email：[e-mail]162ComputerSystemSecurity2第第44章章密码学基础及其应用密码学基础及其应用Total162ComputerSystemSecurity3§§4.14.1密码学密码学4.1.1传统密码学Total162ComputerSystemSecurity4一、密码学概述一、密码学概述密码算法(有时简称密码)指用于加密和解密的一对函数E(x)、D(x)。试图构造算法D’，使对任何由E加密的密文c=E(M)，都有D’(c)=D(c)=M，这种企图称为对密码算法(E,D,其中D未知)的攻击。早期密码系统的安全性通常基于其密码算法的机密性，即密码算法是秘而不宣的。该机制存在两个根本缺陷：1)不能适应用户数量不断变化的组织2)其安全性无从确认，也不能标准化现代密码学认为密码算法是一组依赖于“密钥”的函数族，该函数族的构造是公开的。一切秘密都在密钥中。Total162ComputerSystemSecurity5密码体制：1)传统密码体制：对称密码体制(单钥体制)2)现代密码体制：非对称密码体制(公钥密码体制、双钥体制)按照对明文的处理方式分为：¾分组密码算法：把明文分成等长的组分别加密¾序列密码算法：一个比特一个比特地处理，用已知的密钥随机序列与明文按位异或。Total162ComputerSystemSecurity6序列密码与分组密码序列密码与分组密码z序列码体制是将明文X看成是连续的比特流(或字符流)x1x2…，并且用密钥序列K=k1k2…中的第i个元素ki对明文中的xi进行加密，即E(X)E(x)E(x)Kk11k22=L2Total162ComputerSystemSecurity7序列密码体制序列密码体制密钥序列产生器密钥序列产生器种子I0发端ki密钥序列产生器密钥序列产生器种子I0收端ki⊕密文序列明文序列明文序列xixiyiyi⊕在开始工作时种子I0对密钥序列产生器进行初始化。按照模2进行运算，得出：yE(x)xkikiiii==⊕Total162ComputerSystemSecurity8序列密码体制序列密码体制密钥序列产生器密钥序列产生器种子I0发端ki密钥序列产生器密钥序列产生器种子I0收端ki⊕密文序列明文序列明文序列xixiyiyi⊕在收端，对yi的解密算法为：D(y)yk(xk)kxkiiiiiiii=⊕=⊕⊕=序列密码又称为密钥流密码。Total162ComputerSystemSecurity9序列密码体制的保密性序列密码体制的保密性z序列密码体制的保密性完全在于密钥的随机性。z如果密钥是真正的随机数，则这种体制就是理论上不可破的。这也可称为一次一密乱码本体制。z严格的一次一密乱码本体制所需的密钥量不存在上限，很难实用化。z密码学家试图模仿这种一次一密乱码本体制。目前常使用伪随机序列作为密钥序列。关键是序列的周期要足够长，且序列要有很好的随机性（这很难寻找）。Total162ComputerSystemSecurity10分组密码分组密码z它将明文划分成固定的n比特的数据组，然后以组为单位，在密钥的控制下进行一系列的线性或非线性的变化而得到密文。这就是分组密码。z分组密码一次变换一组数据。z分组密码算法的一个重要特点就是：当给定一个密钥后，若明文分组相同，那么所变换出密文分组也相同。z分组密码的一个重要优点是不需要同步Total162ComputerSystemSecurity11分组密码体制分组密码体制输入输出加密算法加密算法密钥明文输入输出解密算法解密算法密钥明文nbitnbitnbitnbit密文密文Total162ComputerSystemSecurity12二、加密和解密二、加密和解密加密解密明文M密文C原始明文ME(M)=CD(C)=M即：D(E(M))=M明文Plaintext密文Ciphertext加密Encryption解密Decryption密钥key加密算法的操作类型(P5)：™替换：将明文中的每个元素(位、字节、数据块等)映射为另一个元素。™置换：将明文中元素进行重排。3Total162ComputerSystemSecurity13单钥密码体制EK(M)=CDK(C)=M密码就是一组含有参数k的变换E。设已知信息m，通过变换E得到密文c。即c=Ek(m)，该过程称为加密，参数k称为密钥。解密算法D是加密算法E的逆运算，解密算法也是含参数k的变换。DK(EK(M))=M加密解密明文M密文C原始明文M密钥K密钥K明文加密处理方式(P6)：1)流密码：将明文看作基本元素流，连续地对每个元素进行加密处理，每处理一个输出一个。2)分组密码：将明文中连续的若干元素看作一个组块，加解密处理以组块为单位。Total162ComputerSystemSecurity14双钥密码体制加密是可逆的，即解密是可能的⇔可逆/非奇异变换。映射本身可以是密钥。加密解密明文M密文C原始明文M加密密钥K1解密密钥K2EK1(M)=CDK2(C)=MDK2(EK1(M))=MTotal162ComputerSystemSecurity15密码体制定义它是一个五元组(P,C,K,E,D)满足条件：(1)P是可能明文的有限集；(明文空间)(2)C是可能密文的有限集；(密文空间)(3)K是一切可能密钥构成的有限集；(密钥空间)*(4)任意k∈K,有一个加密算法和相应的解密算法，使得和分别为加密解密函数，满足dk(ek(x))=x,这里x∈P。Eek∈CPek→:PCdk→:Ddk∈Total162ComputerSystemSecurity16加密通信的模型信源加密机解密机接收者安全信道密钥源窃听者xyxk1密钥源k2不安全信道密码分析Total162ComputerSystemSecurity171*.Alice要将明文X=x1x2…xn,(其中xi∈P,1≤i≤n)在不安全的信道上发给Bob，Alice用加密算法ek作yi=ek(xi)，结果的密文Y=y1y2….yn，在信道上发送；Bob收到后解密xi=dk(yi)，得到明文X=x1x2…xn。2*.加密函数ek必须是单射函数，就是一对一的函数。3*.好的密钥算法是唯密钥而保密的。4*.若Alice和Bob在一次通信中使用相同的密钥，则该加密体制为对称的，否则称为非对称的加密体制。Total162ComputerSystemSecurity18三、密码分析三、密码分析1、常用的四类密码分析攻击密码学：对信息进行编码实现隐蔽信息的一门学问。密码分析学：研究分析破译密码的学问。两者相互对立、促进。加密算法：公开。攻击目标：获得密钥K•唯密文攻击(ciphertextonlyattacks)：已知截获部分密文•已知明文攻击(knowplaintextattacks)：已知截获部分密文；若干明文-密文对。•选择明文攻击(chosenplaintextattacks)：已知截获部分密文；自主选择的明文-密文对。•选择密文攻击：暂时接近密码机，可选择密文串，并构造出相应的明文。4Total162ComputerSystemSecurity192、算法的安全性密码算法具有不同的安全等级：以下情况可能是安全的.破译算法的代价大于加密数据的价值.破译算法所需的时间大于加密数据保密的时间.用单密钥加密的数据量小于破译算法需要的数据量Shannon理论：仅当密钥至少和明文一样长时才无条件安全(即加密算法产生的密文中包含的信息不足以唯一确定对应的明文，换言之，若不论密码分析者有多少密文，都没有足够的信息恢复出明文，则该算法就是无条件保密的)。因为这种方法的密钥本身传递就是个问题，所以无条件安全的密码算法实际是不存在的。只有一次一密乱码本，才是无条件安全的。所有其它的密码系统在唯密文攻击中都是可破的(蛮力攻击)。Total162ComputerSystemSecurity20密码学更关心在计算上不可破译的密码系统。若一个算法用(现在或将来)可得到的资源(公开数据)都不能破译，这个算法则被认为在计算上是安全的。计算上安全的密码系统指具有下述特点的系统：1)破译密文的成本超过被加密信息的价值2)破译密文的时间超过该信息要求的安全时期可用不同方式来衡量攻击方法的复杂性：¾数据复杂性：用作攻击输入所需的数据量。¾处理复杂性：完成攻击所需要的时间，这个经常叫做工作因素。¾存储需求：进行攻击所需要的存储量。作为一个法则，攻击的复杂性取这三个因数的昀小化，有些攻击包括这三种复杂性的折中：存储需求越大，攻击可能越快。Total162ComputerSystemSecurity21四、传统密码学四、传统密码学1、移位法将明文字母互相换位，明文的字母不变，但顺序被打乱了。例如：线路加密法明文以固定的宽度水平写出，密文按垂直方向读出。明文：COMPUTERSYSTEMSECURITYCOMPUTERSYSTEMSECURITY密文：CTSETOETCYMREUPSMRUYSITotal162ComputerSystemSecurity22CIPHER145326attackbeginsatfour置换密码置换密码z置换密码(transpositioncipher)则是按照某一规则重新排列消息中的比特或字符顺序。密钥顺序明文根据英文字母在26个字母中的先后顺序，我们可以得出密钥中的每一个字母的相对先后顺序。因为密钥中没有A和B，因此C为第1。同理，E为第2，H为第3,……，R为第6。于是得出密钥字母的相对先后顺序为145326。Total162ComputerSystemSecurity23CIPHER145326attackbeginsatfour置换密码置换密码z置换密码(transpositioncipher)则是按照某一规则重新排列消息中的比特或字符顺序。密钥顺序明文根据英文字母在26个字母中的先后顺序，我们可以得出密钥中的每一个字母的相对先后顺序。因为密钥中没有A和B，因此C为第1。同理，E为第2，H为第3,……，R为第6。于是得出密钥字母的相对先后顺序为145326。Total162ComputerSystemSecurity24CIPHER145326attackbeginsatfour置换密码置换密码z置换密码(transpositioncipher)则是按照某一规则重新排列消息中的比特或字符顺序。密钥顺序明文根据英文字母在26个字母中的先后顺序，我们可以得出密钥中的每一个字母的相对先后顺序。因为密钥中没有A和B，因此C为第1。同理，E为第2，H为第3,……，R为第6。于是得出密钥字母的相对先后顺序为145326。5Total162ComputerSystemSecurity25CIPHER145326attackbeginsatfour置换密码置换密码z置换密码(transpositioncipher)则是按照某一规则重新排列消息中的比特或字符顺序。密钥顺序明文根据英文字母在26个字母中的先后顺序，我们可以得出密钥中的每一个字母的相对先后顺序。因为密钥中没有A和B，因此C为第1。同理，E为第2，H为第3,……，R为第6。于是得出密钥字母的相对先后顺序为145326。Total162ComputerSystemSecurity26CIPHER145326attackbeginsatfour置换密码置换密码z置换密码(transpositioncipher)则是按照某一规则重新排列消息中的比特或字符顺序。密钥顺序明文根据英文字母在26个字母中的先后顺序，我们可以得出密钥中的每一个字母的相对先后顺序。因为密钥中没有A和B，因此C为第1。同理，E为第2，H为第3,……，R为第6。于是得出密钥字母的相对先后顺序为145326。Total162Com