信息论与编码（第4版）课件 第7章-加密编码

第7章加密编码信息论与编码（第4版）加密编码2主要内容7.1加密编码的基础知识7.2数据加密标准DES7.3公开密钥加密法7.4量子密码7.1加密编码的基础知识3密码学（cryptology）:数学的一个分支，是密码编码学和密码分析学的统称密码编码学(Cryptography)，对信息进行编码实现隐蔽信息的一门学问密码分析学(Cryptanalytics)，研究分析破译密码的学问7.1加密编码的基础知识4密码学是一门古老而年轻的科学，在当今信息时代，大量敏感信息如法庭记录、私人文档、软件源代码、银行交易、保险单据等常常通过公共通信设施或计算机网络来进行交换为保证信息的保密性、完整性、真实性，可用性、不可抵赖性,必须使用技术手段对其进行处理，把重要信息通过某种变换转换成秘密形式的信息保密性:对信息处理后，保证让他人不能读懂。真实性:对信息处理后，保证他人不能篡改信息（改了之后会被接收者发觉）完整性:对信息处理后，保证他人不能从原始信息中删除或插入其它信息（删除或插入后会被接收者发觉）7.1加密编码的基础知识5信息安全通常包含认证业务：提供某种方法来证实某一声明是正确的。例口令访问控制：控制非授权的访问。例防火墙。保密业务：对未授权者保护信息。例数据加密数据完整性业务：对安全威胁所采取的一类防护措施。不可否认业务：提供无可辩驳的证据来证明曾经发生过的交换。例数字签名技术。密码学是信息安全的核心7.1加密编码的基础知识6基本概念明文（plaintext）M真实数据或消息Message加密算法（cryptography

algorithm）

EK对真实数据施加变化的过程

密文（ciphertext）C加密后的输出，不可直接理解的字符或比特集

解密（decryption）从密文C恢复出明文M的过程称为解密DK密码体制完成加密和解密的算法密钥（key）K变换过程中使用的参数叫密钥加密时使用的密钥与解密时使用的密钥可以相同（单密钥），也可以不同（双密钥）7.1加密编码的基础知识7基本概念保密系统三要素：明文、密文、密钥密码体制要实现的功能可分为：安全性、保密性、真实性7.1加密编码的基础知识8密码体制的安全性如果求解一个问题需要一定量的计算，但环境所能提供的实际资源却无法实现它，则称这种问题是计算上不可能的；如果一个密码体制的破译是计算上不可能的，则称该密码体制是计算上安全的。密码体制的保密性要由截获的密文C系统地求出明文M是计算上不可能的。即使截获了一段密文C，甚至知道了与它对应的明文M，破译者要从中系统地求出解密变换仍然是计算上不可能的。保密性只要求对变换DK（解密密钥）加以保密，只要不影响DK的保密，变换EK可以公布于众。

7.1加密编码的基础知识9密码体制的真实性对于给定的C，即使密码分析员知道对应于它的明文M，要系统地求出加密变换EK仍然是计算上不可能的。密码分析员要系统地找到密文C’，使DK（C’）是明文空间上有意义的明文，这在计算上是不可能的。真实性只要求变换EK（加密密钥）保密，变换DK可公布于众。7.1加密编码的基础知识10保密性与真实性保护Ek获得真实性，保护Dk获得保密性7.1加密编码的基础知识11密码体制的分类密码体制分为对称(单钥)体制和非对称(双钥)体制对称密码体制也称为秘密密钥密码体制、单密钥密码体制，加密和解密密钥相同或很容易相互推导单密钥体制要实现保密性和真实性必须对Ek和Dk都保密,只要暴露其中一个，另一个也就暴露了。所以，对称密码体制必须同时满足保密性和真实性的全部要求。应用私人文件加密数据的网络传输：密钥或者由消息发送方生成，然后通过安全的渠道送到接收方；或者由可信的第三方生成，然后通过安全渠道分发给发送方和接收方7.1加密编码的基础知识12密码体制的分类非对称(双钥)体制也称为公开密钥密码体制，加密密钥与解密密钥不同，已知其中一个求出另一个在计算上是不可能的，因此，Ek或Dk中有一个公布不影响另一个的保密保护DK获得保密性，保护EK获得真实性特点加密和解密能力分开，无需事先分配密钥接收者通过保密自己的解密密钥来保障他接收信息的保密性，但不能保证真实性，因为任何知道他的加密密钥的人都可以将虚假消息发给他。发送者通过保密自己的解密密钥来保障他发送信息的真实性。但任何知道他的加密密钥的人都可以破译消息，保密性不能保证可用于数字签名7.1加密编码的基础知识13密码分类根据加密明文数据时的加密单位不同，可以把密码分为分组密码和序列密码两大类分组密码：设M为明文数据，将M分成等长的连续区组M1,M2,…，分组的长度一般是几个字符，并且用同一密钥K为各组加密序列密码：将M分成连续的字符或位m1,m2,…,并用密钥序列K=K1,K2…的第i个元素Ki给mi加密7.2数据加密标准DES14DES历史数据加密标准（dataencryptionstandard,DES）是迄今为止世界上最为广泛使用和流行的一种分组密码算法1973年美国国家标准局NBS(NationalBureauofStandard)正式向社会公开征集加密算法1974年IBM正式向NBS提交了应征方案NBS会同美国国家保密局（NSANationalSecurityAgency)研究发现这是唯一满足各项要求的方案在此方案基础上形成非机密数据的数据加密标准DES(dataencryptionstandard)于1977年1月15日颁布，同年7月正式生效成为美国联邦标准FIPS(FederalInformationProcessingStandard)7.2数据加密标准DES15DES历史其后大约每5年对DES的安全性进行一次审查评估，最后一次是1993年进行1998年5月美国EFF（ElectronicFrontierFoundation）宣布，他们以一台价值20万美元的计算机改装成的专用解密机，用56小时破译了56比特密钥的DES美国已决定1998年12月以后将不再使用DES美国国家标准和技术协会征集并进行几轮评估、筛选，产生了称之为AES(advancedencryptionstandard)新加密标准尽管如此，DES对于推动密码理论的发展和应用毕竟起了重大作用，对于掌握分组密码的基本理论、设计思想和实际应用仍然有着重要的参考价值7.2数据加密标准DES16DES的基本思想加解密双方在加解密过程中要使用完全相同的一个密钥，密钥就经过安全的密钥信道由发方传给收方7.2数据加密标准DES17换位和替代密码换位密码：对数据中的字符或更小的单位(如位)重新组织，但并不改变数据本身7.2数据加密标准DES18换位和替代密码替代秘密：改变数据中的字符，不改变它们之间的相对位置替代盒（S盒）7.2数据加密标准DES19换位和替代密码换位和替代（代换）是古典密码体制中的两个基本操作，也仍然是构造现代对称加密算法的核心7.2数据加密标准DES20DES算法DES密码就是在换位和替代密码的基础上发展的。将输入明文序列分成区组，每组64比特64bit明文→64bit密文没有压缩、扩展64bit的密钥源循环移位产生16个子密钥k1k2…k16第8、16、24、32、40、56、64位为奇偶校验位实际56bit缺点：密钥太短7.2数据加密标准DES21DES算法(1)分组，每组64bit(2)置换7.2数据加密标准DES22DES算法(1)分组，每组64bit(2)置换(3)密码运算，它是在密钥控制下的16次线性变换7.2数据加密标准DES23DES算法密码计算函数①32bit的Ri-1经表7-2的扩充函数变成48bit②与Ki模2加得48bit，经8个S盒得32bit③8个S盒，每个输入为6bit，输出4bit，见表7-3。以输入6bit数据的1、6bit组成的二进制数为行号，以2、3、4、5bit组成的二进制数位列号，将查表得到的数据转换为4bit输出④Ki是由同一个64bit的密钥源循环产生的，64bit中56bit是随机的，8的倍数位为奇偶校验位7.2数据加密标准DES24DES算法密钥表计算置换1，见表7-5移位数，见表7-6置换2，见表7-77.2数据加密标准DES25DES密码的安全性DES的出现在密码学史上是一个创举。以前的任何设计者对于密码体制及其设计细节都是严加保密的。而DES算法则公开发表，任人测试、研究和分析，无须通过许可就可制作DES的芯片和以DES为基础的保密设备。DES的安全性完全依赖于所用的密钥。最初，除了用穷举搜索法攻击外，没有发现更有效的方法56bit密钥，穷举空间为256计算机速度每秒检测1,000,000个密钥，需要近2285年时间超高速计算机出现后，可考虑增加密钥长度DES中所有的计算，除了S盒，都是线性的，S盒对DES的安全性至关重要7.2数据加密标准DES26DES密码的问题和改进DES的密钥短了些选择长的密钥会使成本提高、运行速度降低。新算法很可能要采用128比特密钥。尽管DES算法十分复杂，但它基本上还是采用64比特字符的单字母表替换密码。当同样的64比特明文块进入编码器后，得到的是同样的64比特的密文块。破译者可利用这个性质来破译DES。改进方法：密码块链接、密码反馈方式问题改进思想7.3公开密钥加密法PKC

27前面介绍的秘密密钥加密法，算法公开，密钥是保密的（对称密钥）。如果要进行通信，必须在这之前把密钥通过非常可靠的方式分配给所有接收者，这在某些场合是很难做到的。因而提出了公开密钥加密法PKC（PublicKeyCryptography）PKC使用两个不同密钥（非对称密钥体制）；一个公开（公钥），另一个为用户专用（私钥）；通信双方无需事先交换密钥就可进行保密通信；要从公钥或密文分析出明文或私钥，在计算上是不可能的。7.3公开密钥加密法PKC

28PKC应用保密通信：多个用户将信息传给某用户，可用该用户的公钥加密，唯有该用户可用自己的私钥解读。7.3公开密钥加密法PKC

29PKC应用数字签名：用自己的私钥加密信息，而以公钥作为解密密钥，用来确认发送者。数字签名就是附加在数据单元上的一些数据,或是对数据单元所作的密码变换。这种数据或变换允许数据单元的接收者用以确认数据单元的来源和数据单元的完整性并保护数据,防止被人进行伪造。7.3公开密钥加密法PKC

30MIT三位年青数学家R.L.Rivest，A.Shamir和L.Adleman等[1978,1979]发现了一种用数论构造双钥的方法，称作MIT体制，后来被广泛称之为RSA体制RSA密码体制7.3公开密钥加密法PKC

31RSA密码体制理论基础：利用数论

正：要求得到两个大素数（如大到100位）的乘积在计算机上很容易实现。

逆：但要分解两个大素数的乘积在计算上几乎不可能实现。密钥设计：两个密钥：公钥（e，n）

私钥（d，n）加密解密：

加密时：

解密时：7.3公开密钥加密法PKC

32RSA密码体制算法步骤选取两个很大的素数p和q，令求n的欧拉函数并从2至[

(n)－1]中任选一个数作为加密指数e；解同余方程，求得解密指数d；设计２个密钥(e，n)即为公开密钥(d，n)即为秘密密钥加密时解密时7.3公开密钥加密法PKC

33例题－保密通信例7-1在RSA方法中，令p＝3，q＝17，取e＝5，试计算解密密钥d并加密M＝2。解：n＝p×q＝51

(n)＝(p－1)×(q－1)＝32(5×d)mod32＝1，可解得d＝13

加密 y＝xemodn＝25mod51＝32

解密 ydmodn＝3213mod51＝2＝x注：若需发送的报文内容是用英文或其他文字表示的，则可先将文字转换成等效的数字，再进行加密运算。7.3公开密钥加密法PKC

34RSA公开密钥体制用于数字签名发送者A用自己的秘密解密密钥(dA，nA)计算签名；用接收者B的公开加密密钥(eB，nB)再次加密：接收者B用自己的秘密解密密钥(dB，nB)解密：查发送者A的公开密钥(eA，nA)计算，恢复出发送者的签名，认证密文的来源。(dA，nA)(eB，nB)(dB，nB)(eA，nA)MiSiSSiMi

7.3公开密钥加密法PKC

35例－数字签名例7-2用户A发送给用户B一份密文，用户A用首字母B＝02来签署密文。用户A知道下列三个密钥：

AB公开密钥(e，n)(7，123)(13，51)秘密密钥(d，n)(23，123)A计算他的签名：再次加密签名：7.3公开密钥加密法PKC

36接收者B必须恢复出02＝B认证他接收的密文。接收者也知道三个密钥：

AB公开密钥(e，n)(7，123)(13，51)秘密密钥(d，n)(5，51)B用户用自己的秘密解密密钥一次解密：

再用A用户的公开密钥解密：B用户可以确认：该签名是由A发出——用A公钥可解读；该签名是发给自己的——用了B的公钥。例－数字签名7.4量子密码37从信息论的角度，只有“一次一密”加密系统是完全不可破译的。但要求使用的密钥长度太长，不实用。

“量子算法”利用量子计算机的并行性可以有效破译RSA算法。量子密码系统借助量子物理原理设计出在理论上可以满足“一次一密”加密系统要求的密码协议，具有理论上的无条件安全性。

7.4量子密码38物理基础海森堡测不准原理不确定原理德国物理学家维尔纳·海森堡于1927年提出当我们试图更精确地测量一个物理量时，另一个物理量的测量精度就会不可避免地降低这个原理揭示了量子世界与经典物理世界的根本不同，即在量子层面上，粒子的性质