第4章 非对称密码

非对称密码物联网信息安全06检查回顾新知学习合作探究过关测试五步教学法提纲考核点评1.DES是一种数据分组的加密算法，DES它将数据分为长度为（

）位的数据块，其中一部分用作奇偶校验，剩余部分作为密码的长度

。56位64位112位128位ABCD提交单选题10分

五步教学法检查回顾新知学习合作探究考核点评过关测试独立完成单选题10分2.以下不属于对称密码算法的是（

）。IDEAAESDESRSAABCD提交单选题10分

五步教学法检查回顾新知学习合作探究考核点评过关测试独立完成单选题10分知识目标1.了解非对称加密算法概念；2.掌握RSA算法（重点）；3.了解Elgamal密码系统和椭圆函数密码算法。能力目标

了解密码学，培养网络安全意识，保护好自身安全。思政目标具备实现RSA算法的基本能力。第0章物理层

五步教学法检查回顾新知学习合作探究考核点评过关测试问题引入

五步教学法检查回顾新知学习合作探究考核点评过关测试网络安全体系的五类服务访问控制技术身份鉴别技术加密技术信息鉴别技术访问控制服务对象认证服务保密性服务完整性服务防抵赖服务问题引入使用对称加密：

密钥分配密钥管理签名

五步教学法检查回顾新知学习合作探究考核点评过关测试（投稿回答）对称加密的优缺点有哪些？对称加密系统的特点：优点：对称较密算法使用起来简单快捷，密钥较短，且破译困难。缺点：（1）密钥难以安全传送。（2）密钥量太大，难以进行管理。（密钥的分发和管理非常复杂、代价高昂，特别是针对大型网络，当用户群很大，分布很广时，密钥的分配和管理就成了大问题。）

（3）难以解决数字签名验证的问题。

五步教学法检查回顾新知学习合作探究考核点评过关测试问题引入非对称加密来解决这些问题！1.非对称加密的基本概念

对称加密系统的安全性主要是依赖于加密结构的混淆性、非线性等性质。

而非对称加密则依赖于计算复杂性理论。在非对称加密中，由加密算法和公钥计算出密文是“简单的”，但是只知道密文和公钥，计算出私钥或者恢复出明文是“困难的”。

计算理论中概率多项式时间（ProbabilisticPolynomialTime，PPT）来表示一个函数是可计算的，否则称之为是计算困难的。

五步教学法检查回顾新知学习合作探究考核点评过关测试1.非对称加密的基本概念

非对称加密方案的安全强度随着安全参数的增大而增大。这种安全其实是相对的。加密方案的安全限定了攻击者的计算能力是安全参数的概率多项式倍，即PPT时间敌手。非对称加密允许PPT时间敌手以一定的概率攻破加密方案，但是这个概率必须非常小，称这种概率为可忽略的。

可忽略函数：如果对于每一个多项式p(⋅)，都存在一个N，使得对所有的n>N，都有f(n)<1/p(n)，则称函数f是可忽略的。

五步教学法检查回顾新知学习合作探究考核点评过关测试1.非对称加密的基本概念非对称加密：（公开密钥系统）需要两个密钥：公开密钥（Publickey）和私有密钥（Privatekey）优点：易于实现，使用灵活，密钥较少。弱点：要取得较好的加密效果和强度，必须使用较长的密钥。

五步教学法检查回顾新知学习合作探究考核点评过关测试1.非对称加密的基本概念困难问题：素因数分解问题：选定两个长度为λ的素数p和q，计算n=pq。对于任意的PPT敌手，给定n，如果存在一个可忽略的函数negl(λ)，使得其计算出p′q′=n的概率不大于negl(λ)，则称素因数分解问题是困难的。离散对数问题：对于一个阶为q的循环群G，其中|q|=λ，g为G的一个生成元。随机选取x∈

Z_q，设置ℎ=g^x。对于任意的PPT敌手，给定(G,q,g,ℎ)，如果存在一个可忽略的函数negl(λ)，使得其计算出x’，满足g^x’=ℎ的概率不大于negl(λ)，则称离散对数问题在G群上是困难的。

五步教学法检查回顾新知学习合作探究考核点评过关测试1.非对称加密的基本概念困难问题：判定性Diffie-Hellman问题：对于一个阶为q的循环群G，其中|q|=λ，g为G的一个生成元。随机选取x,y,z∈

Z_q。对于任意的PPT敌手，给定(G,q,g,g^a,g^b,T)，如果存在一个可忽略的函数negl(λ)，使得其判断出T=g^ab或T=g^z的概率不大于negl(λ)，则称判断性Diffie-Hellman（DDH）问题在G群上是困难的。计算性Diffie-Hellman问题：对于一个阶为q的循环群G，其中|q|=λ，g为G的一个生成元。随机选取x,y∈

Z_q。对于任意的PPT敌手，给定(G,q,g,g^a,g^b)，如果存在一个可忽略的函数negl(λ)，使得其计算出T=g^ab的概率不大于negl(λ)，则称计算性Diffie-Hellman（CDH）问题在G群上是困难的。

五步教学法检查回顾新知学习合作探究考核点评过关测试3.以下关于非对称密钥加密说法正确的是（

）。

加密方和解密方使用的是不同的算法加密密钥和解密密钥是不同的加密密钥和解密密钥是相同的加密密钥和解密密钥没有任何关系ABCD提交单选题10分多选题10分

五步教学法检查回顾新知学习合作探究考核点评过关测试单选题10分

五步教学法检查回顾新知学习合作探究考核点评过关测试（随机点名）单向陷门函数如果用作加密，应该如何设计呢？（哪些为公钥，哪些为私钥）1.非对称加密的基本概念

五步教学法检查回顾新知学习合作探究考核点评过关测试1.非对称加密的基本概念

五步教学法检查回顾新知学习合作探究考核点评过关测试1.非对称加密的基本概念A容易计算产生一对密钥B知道公开密钥容易计算密文A接收后容易用私有密钥解密

五步教学法检查回顾新知学习合作探究考核点评过关测试1.非对称加密的基本概念（弹幕回答）1.C知道公钥要计算私有密钥可行不？2.C知道公钥要恢复明文可行不？网络中的每一个终端系统都生成一对私钥和公钥，用于加密和对其所接收的消息进行解密每个终端系统都将其加密密钥放入一个公开的注册表或文件，通过访问此注册表或文件即可获取公钥用户希望给另一个用户发消息时，使用后者的公钥进行加密正确的用户接收到消息后，使用其私钥进行解密，其他接收者都无法对此消息解密。

五步教学法检查回顾新知学习合作探究考核点评过关测试1.非对称加密的基本概念公钥加密过程的鲁棒性取决于对公共目录的防护程度和算法的强度。已知密文，哪怕要计算出原始消息的部分信息都是极度困难的。要探测由同一对密钥处理的消息信息流的简单特征是非常困难的。加密算法的长度应当是不变的，即：加密算法的长度并不依赖于消息的长度。

五步教学法检查回顾新知学习合作探究考核点评过关测试1.非对称加密的基本概念2.RSA加密算法

1976年，Diffie和Hellman并未给出有效的加解密算法。

1978年，Rivest、Shamir和Adleman三人合作提出了第一个实用的公钥密码算法，即著名的RSA密码算法。

素因数分解问题是困难的，然而如何基于素因数分解问题直接构造非对称加密方案一直以来都还未实现。为此，RSA加密算法退而求其次，提出了与素因数分解问题相关的RSA假设，并在其基础上构造了RSA加密算法。

五步教学法检查回顾新知学习合作探究考核点评过关测试2.RSA加密算法RSA算法的理论基础

较大的没有明显分解特征的大整数分解的算法时间复杂度;

指定一个大素数为私钥，并选择另外一个大素数，使之与私钥的乘积为公钥；

用素数判定定理选择大素数。

五步教学法检查回顾新知学习合作探究考核点评过关测试2.RSA加密算法

五步教学法检查回顾新知学习合作探究考核点评过关测试2.RSA加密算法密钥生成算法Gen(λ)：算法输入安全参数λ，然后选取两个长度为λ的大素数p,q，n=pq，ϕ(n)=(p−1)(q−1)。随机选取一个e，使得gcd(e,ϕ(n))=1，并计算d，使得de

=

1

mod

ϕ(n)。则RSA加密的公钥pk=(n,e)，私钥为sk=(n,d)。

五步教学法检查回顾新知学习合作探究考核点评过关测试2.RSA加密算法

五步教学法检查回顾新知学习合作探究考核点评过关测试2.RSA加密算法1.首先求出模数n=p*q=17*11=1872.求出(p-1)*(q-1)=16*10=160

3.e=7满足与160互素4.找出d满足e*d=1 mod (p-1)*(q-1)且d<160，这里d=23因为23×7=161=10×160+1然后用n和e作为公钥Pk={187,7}加密：c=m^e

mod

n=88^7mod187=11用n和d作为密钥Sk={187,23}

解密：m=c^d

mod

n=11^23mod187=88

五步教学法检查回顾新知学习合作探究考核点评过关测试ex:假设需要加密的明文信息为m=88，选择：e=7，p=17，q=11，写出其公钥和私钥，并且求出其密文和明文（加密和解密过程）。分组讨论：假设需要加密的明文信息为m=85，选择：e=7，p=11，q=13，说明使用RSA算法的加密和解密。

五步教学法检查回顾新知学习合作探究考核点评过关测试2.RSA加密算法其他例子：P=43,q=59,n=43*59=2537,(p-1)(q-1)=2436e=13ed=1(mod2436)2436=187*13+5,13=2*5+3,5=3+2,3=2+11=3-2=3-(5-3)=…=2*13-5*(2436-187*13)=-5*2436+937*13d=937

五步教学法检查回顾新知学习合作探究考核点评过关测试2.RSA加密算法M=134879475204m1=134,m2=879,m3=475,m4=204,c1=134^13mod2537=248,c2=879^13mod2537=……m1=248937mod2537=134……

五步教学法检查回顾新知学习合作探究考核点评过关测试加密消息m时，首先将它分成比n小的数据分组（采用二进制数，选取小于n的2的最大次幂），也就是说，p和q为100位的素数，那么n将有200位，每个消息分组应小于200位长。如果需要加密固定长度的消息分组，可以在左边填充一些0并确保该数比n小。2.1RSA加密算法的应用主要用于

数字签名

密钥交换

数据加密RSA算法用于数字签名时，公钥和私钥的角色变换了。

五步教学法检查回顾新知学习合作探究考核点评过关测试2.2RSA安全性分析80年代末，Rivest、Shamir和Adleman找到了一个129位数(428bits)的两个素数的乘积，称为RSA-129，设计了一套密钥向世界挑战。1994年3月，由Lenstra领导的一组数学家及世界各地600多个爱好者使用了1600台机器，通过因特网协调各自计算机的工作,向这个129位数发动了进攻，花费了8个月的时间，他们就分解出了这个数的两个素数因子，其中一个长64位，另一个长65位。

五步教学法检查回顾新知学习合作探究考核点评过关测试2.2RSA安全性分析1999年，阿姆斯特丹的国家数学与计算机科学研究所（CWI）属下的一个国际密码研究小组宣布，他们在破译RSA公钥密码系统使用的155位RSA密钥的竞赛中荣获冠军，他们使用了一台克雷900-16超级计算机、300台个人计算机以及专门设计的软件。155位的RSA密钥，虽然仍在保护着银行、股票交易所和在线零售商每天价值几十亿美元的业务往来，虽然也不是普通人可以破译的，但155位的密钥长度也还是不富余的。

五步教学法检查回顾新知学习合作探究考核点评过关测试（弹幕回答）破译攻击RSA的关键点在哪？2.2RSA安全性分析密码分析者攻击RSA体制的关键点在于如何分解n。若分解成功使n=pq，则可以算出φ(n)＝（p-1)(q-1)，然后由公开的e，解出秘密的d。（猜想：攻破RSA与分解n是多项式等价的。然而，这个猜想至今没有给出可信的证明！！！）

五步教学法检查回顾新知学习合作探究考核点评过关测试2.2RSA安全性分析强力攻击数学攻击定时攻击迭代攻击不动点问题

五步教学法检查回顾新知学习合作探究考核点评过关测试2.2RSA安全性分析强力攻击（穷举法）：尝试所有可能的私有密钥数学分析攻击：各种数学方法，等价于因子分解时间性攻击：取决于解密算法的运算时间因子分解问题有三类方法：1、分解n，

n=pq,

(n)=(p-1)(q-1)d=e-1mod(n)2、直接确定(n)，

d=e-1mod(n)3、直接确定d

五步教学法检查回顾新知学习合作探究考核点评过关测试2.2RSA安全性分析迭代攻击序列c(0)=m,c(1)=E(c(0)),……,c(k+1)=E(c(k))满足c(k+1)=c(1)最小的k≥1称为m的迭代指数例m=0518,e=17,d=157,n=2773=47*59,φ(n)=2668=2*2*23*29c(0)=m=0518,c(1)=0518^17mod2773=1787c(2)=1787^17mod2773=0894c(3)=0894^17mod2773=1364c(4)=1364^17mod2773=0518c(5)=0518^17mod2773=1787

五步教学法检查回顾新知学习合作探究考核点评过关测试2.2RSA安全性分析需要选择足够大的素数p,q(1075~10100)p,q不能太接近（p-1）和（q-1）应包含大素数因子gcd(p-1,q-1)应很小当e<n且d<n1/4时，d容易确定

五步教学法检查回顾新知学习合作探究考核点评过关测试4.RSA加密体制是基于（

）。离散对数难题费马最后定理大整数因子分解问题椭圆曲线问题ABCD提交单选题10分

五步教学法检查回顾新知学习合作探究考核点评过关测试独立完成单选题10分5.在RSA算法中，取P=3，q=11,e=3，则d等于多少（

）。3320147ABCD提交单选题10分

五步教学法检查回顾新知学习合作探究考核点评过关测试独立完成单选题10分3.Diffie-Hellman密钥交换第一个公钥方案Diffie&Hellman在1976发表note:nowknowthatJamesEllis(UKCESG)secretlyproposedtheconceptin1970公开交换一个秘密密钥的使用方法大量使用在商业产品中

五步教学法检查回顾新知学习合作探究考核点评过关测试3.Diffie-Hellman密钥交换密钥分发方案

不能用于交换任意消息可以建立共享密钥(双方共享)依赖于双方的公、私钥值基于有限域上的指数问题安全性是基于计算离散对数的困难性

五步教学法检查回顾新知学习合作探究考核点评过关测试3.Diffie-Hellman密钥交换两个通信主体A&B,希望在公开信道上建立密钥初始化:

选择一个大素数p(200digits)一个生成元A选择一个秘密钥(secretkey(number)xA

<p)B选择一个秘密钥(secretkey(number)xB<pAandB计算他们的公开密钥:

yA=axAmodpyB=axBmodpA,B分别公开yA，yB

五步教学法检查回顾新知学习合作探究考核点评过关测试3.Diffie-Hellman密钥交换两个通信主体A&B,希望在公开信道上建立密钥计算共享密钥:KAB=axA.xBmodpKAB=yAxBmodp(whichBcancompute)KAB=yBxAmodp(whichAcancompute)KAB

可以用于对称加密密钥

五步教学法检查回顾新知学习合作探究考核点评过关测试3.Diffie-Hellman密钥交换举例：Alice和Bob打算交换密钥:达成协议，选取q=353，

α=3随机选择密钥:A选xA=97,B选xB=233计算公钥:yA=397mod353=40 (Alice)yB=3233mod353=248

(Bob)计算共享会话密钥:KAB=yBxAmod353=24897=160 (Alice)KAB=yAxBmod353=40233=160 (Bob)

五步教学法检查回顾新知学习合作探究考核点评过关测试分组讨论：（投稿回答）选取素数p=97,及本根a=5Alice选取秘钥xA=36，Bob选取秘钥xB=58，计算Alice和Bob各自的公钥及双方的公享密钥。

五步教学法检查回顾新知学习合作探究考核点评过关测试3.Diffie-Hellman密钥交换两个主体每次可以选择新的秘密密钥(私钥),并计算及交换新的公钥可以抵抗被动攻击,但不能抵抗主动攻击每次可以给出新的密钥为抵抗主动攻击,需要其它新的协议也可以建立长期公钥

五步教学法检查回顾新知学习合作探究考核点评过关测试6.以下各种加密算法中属于非对称加密算法的是（

）。DES加密算法Caesar替代法Vigenere加密算法Diffie-Hellman加密算法ABCD提交单选题10分多选题10分

五步教学法检查回顾新知学习合作探究考核点评过关测试单选题10分4.ElGamal加密方案Diffie-Hellmankeydistributionscheme的变形能够用于安全交换密钥publishedin1985byElGamal:

T.ElGamal,"APublicKeyCryptosystemandaSignatureSchemeBasedonDiscreteLogarithms",IEEETrans.InformationTheory,volIT-31(4),pp469-472,July1985.安全性是基于离散对数

五步教学法检查回顾新知学习合作探究考核点评过关测试4.ElGamal加密方案--密钥建立密钥生成：选取一个大素数p及本原元gmodp选择秘密秘钥a0<g<p,1<a<p-1计算y=gamodp公钥（g,p,y）

五步教学法检查回顾新知学习合作探究考核点评过关测试4.ElGamal加密方案--加密为加密M

发送者选择随机数k,0<=k<=p-1计算消息密钥key:Key=ykmodp=(ga)kmodp

计算密文对:C={C1,C2}C1=gkmodpC2=m×keymodp=m×(ga)kmodp发送到接收者k需要永久保密

五步教学法检查回顾新知学习合作探究考核点评过关测试指数积分法（IndexCalculus）4.ElGamal加密方案--解密首先计算消息密钥key

Key=C1amodp=gk.amodp计算明文:M=C2.Key-1modp=(m×(ga)k)×g-k.amodp=m

五步教学法检查回顾新知学习合作探究考核点评过关测试4.ElGamal加密方案--举例选择p=97及本原根g=5Bob选择秘密钥a=58&计算并发布公钥yB=558=44mod97Alice要加密M=3toBob首先得到Bob的公开密钥yB=44选择随机k=36计算:

Key=4436=75mod97计算密文对:C1=536=50mod97C2=75×3mod97=31mod97发送{50,31}toBobBob恢复messagekeyKey=5058=75mod97Bob计算Key-1=22mod97Bob恢复明文M=31×22=3mod97

五步教学法检查回顾新知学习合作探究考核点评过关测试7.若Alice想向Bob分发一个会话密钥，采用ElGamal公钥加密算法,那么Alice应该选用的密钥是（

）。Alice的公钥Alice的私钥Bob的公钥Bob的私钥ABCD提交

五步教学法检查回顾新知学习合作探究考核点评过关测试单选题10分5.椭圆函数密码算法1985年，N.Koblitz和V.Miller分别独立提出了椭圆曲线密码体制(ECC)，其依据就是定义在椭圆曲线点群上的离散对数问题的难解性。随后，Koyama等在Crypto91、Demytko在Eurocrypt93中分别提出了新的基于椭圆曲线的单项限门函数，生成了类似于RSA的公钥密码算法。

五步教学法检查回顾新知学习合作探究考核点评过关测试5.椭圆函数密码算法

密码编码学上我们关心的是一种受限形式的椭圆曲线——定义在有限域Fp上，满足如下方程的元素加上无穷远点θ：y2≡x3+ax+b(modp)

其中非负整数a,b满足：4a3+27b2(modp)≠0

五步教学法检查回顾新知学习合作探究考核点评过关测试5.1椭圆曲线上的D-H密钥交换原始形式：本原元g,大素数p大家共享A：选取a（保密），把ga传送给BB：选取b（保密），把gb传送给AA与B分别计算(gb)a=(ga)b=gab，gab为共享密钥椭圆曲线上：阶数较大的点P,曲线E共享A：选取a（保密），把aP传送给BB：选取b（保密），把bP传送给AA与B分别计算abP为共享密钥

五步教学法检查回顾新知学习合作探究考核点评过关测试5.2椭圆曲线密码的安全性ECC的安全性依赖于给定P和kP计算出k的难度，这被称为椭圆曲线上的对数问题。

椭圆函数密码算法运算速度大大加快，为达到与RSA密码算法同等的安全性，它的密钥长度可以缩短到RSA密钥的六分之一。

椭圆函数密码成为密码学发展的新方向。

五步教学法检查回顾新知学习合作探究考核点评过关测试5.2椭圆曲线密码的安全性

五步教学法检查回顾新知学习合作探究考核点评过关测试ECC密钥长度RSA密钥长计算机解密代价（年）按每秒100万条指令计16010241E+1232051201E+36600210001E+7812001200001E+1688.在现有的计算能力条件下，对于椭圆曲线密码算法(ECC)，被认为是安全的最小密钥长度是（

）。128位160位512位1024位ABCD提交

五步教学法检查回顾新知学习合作探究考核点评过关测试单选题10分加密算法在物联网中的应用

满足概率加密的非对称加密方案中会存在密文扩张问题，且往往涉及到较为复杂的计算，如指数运算、模运算等。因此在物联网中单独使用非对称加密，会受到硬件、通讯环境等限制。为了平衡加密效率、安全性和便捷性，混合加密方法被广泛应用在各类系统中。设对称加密方案的加密算法和解密算法为SE-Enc和SE-Dec，非对称加密方案的算法分别为ASE-Gen、ASE-Enc和ASE-Dec，混合加密的过程如下：（1）Gen(λ)：混合加密的公私钥对<pk,sk>由ASE-Gen(λ)产生。（2）Enc(pk,m)：算法首先随机选取一个对称加密密钥k，运行ASE-Enc(pk,k)产生部分密文c_1。然后运行SE-Enc(k,m)产生c_2。最后输出密文c=(c_1,c_2)。（3）Dec(sk,c)：算法将密文分为两部分(c_1,c_2)，然后运行ASE-Dec(sk,c_1)解密得到对称密钥k，再使用对称密钥运行SE-Dec(k,c_2)得到明文。

五步教学法检查回顾新知学习合作探究考核点评过关测试6.混合密码系统（投稿回答）对称密码系统的优点、缺点；非对称密码系统的优点、缺点。

五步教学