第6章非对称密码体制Word文档下载推荐.docx
- 文档编号:7847752
- 上传时间:2023-05-09
- 格式:DOCX
- 页数:19
- 大小:795.52KB
第6章非对称密码体制Word文档下载推荐.docx
《第6章非对称密码体制Word文档下载推荐.docx》由会员分享,可在线阅读,更多相关《第6章非对称密码体制Word文档下载推荐.docx(19页珍藏版)》请在冰点文库上搜索。
(6)加密和解密函数可以以两个次序中的任何一个来使用:
M=DKRb(EKUb(M)) M=EKUb(DKRb(M))
陷门单向函数
是满足下列条件的函数f:
(1)给定x,计算y=f(x)是容易的
(2)给定y,计算x使y=f(x)是困难的
(3)存在δ,已知δ时,对给定的任何y,若相应的x存在,则计算x使y=f(x)是容易的
注:
1*.仅满足
(1)、
(2)两条的称为单向函数;
第(3)条称为陷门性,δ称为陷门信息。
2*.当用陷门函数f作为加密函数时,可将f公开,这相当于公开加密密钥。
此时加密密钥便称为公开密钥,记为Pk。
f函数的设计者将δ保密,用作解密密钥,此时δ称为秘密密钥,记为Sk。
由于加密函数是公开的,任何人都可以将信息x加密成y=f(x),然后送给函数的设计者(当然可以通过不安全信道传送);
由于设计者拥有Sk,他自然可以解出x=f-1(y)。
3*.单向陷门函数的第
(2)条性质表明窃听者由截获的密文y=f(x)推测x是不可行的。
公开密钥密码系统的分析方法
●强行攻击(对密钥)。
●公开密钥算法本身可能被攻破。
●可能报文攻击(对报文本身的强行攻击)。
公钥密码系统的应用类型
●加密/解密
●数字签名
●会话密钥交换
例子:
简单数字签名
安全数字签名
6-2 Diffie-Hellman密钥交换算法
●
一个素数q和一个整数a(均公开),a是q的一个原根
用户A选择一个随机数XA<
q,并计算
●类似地,用户B选择一个随机数XB<
q,并计算
每一方都对X的值保密存放而使得Y的值对于另一方可以公开得到
用户A计算密钥:
●用户B计算密钥:
●双方以K作为加、解密密钥,以对称密钥算法进行保密通信
DH例子
●素数q=97,它的一个本原元a=5
●A和B分别选择随机数Xa=36和Xb=58
●A计算公开密钥:
Ya=536mod97=50mod97
●B计算公开密钥:
Yb=558mod97=44mod97
●A计算会话密钥:
K=4436mod97=75mod97
●B计算会话密钥:
K=5058mod97=75mod97
6-3 RSA
由Rivest,Shamir和Adleman在1978年提出来的
数学基础:
Euler定理,并建立在大整数因子分解的困难性之上
RSA密码体制描述
●明文空间P=密文空间C=Zn
●密钥的生成
–选择互异素数p,q,计算n=p*q,(n)=(p-1)(q-1),选择整数e使((n),e)=1,1<
e<
(n),计算d,使d=e-1mod(n)
–公钥Pk={e,n}
–私钥Sk={d,n}
●加密(用e,n)
–明文:
M<
n密文:
C=Me(modn)
●解密(用d,n)
密文:
C明文:
M=Cd(modn)
RSA的例子
●若Bob选择了p=7和q=17
●则n=119,(n)=6×
16=96=25×
3,一个正整数e能用作加密指数,当且仅当e不能被2,3所整除
●假设Bob选择e=5,那么用辗转相除法将求得:
d=e-177(mod96)
●Bob的解密密钥d={77,119},公开{5,119}
●现假设Alice想发送明文19给Bob
RSA的安全性基于:
加密函数ek(x)=xe(modn)是一个单向函数,所以对敌人来说求逆计算不可行。
而Bob能解密的陷门是分解n=pq,知(n)=(p-1)(q-1),从而解出解密私钥d
步骤:
Bob为实现者
●Bob寻找出两个大素数p和q
●Bob计算出n=pq和(n)=(p-1)(q-1).
●Bob选择一个随机数e(0<
(n)),满足(e,(n))=1
●Bob使用辗转相除法计算d=e-1(mod(n))
●Bob在目录中公开n和e作为她的公开钥
密码分析者攻击RSA体制的关键点在于如何分解n。
若分解成功使n=pq,则可以算出φ(n)=(p-1)(q-1),然后由公开的e,解出秘密的d。
要求:
若使RSA安全,p与q必为足够大的素数,使
分析者没有办法在有效时间内将n分解出来。
建议选择
p和q大约是100位的十进制素数。
模n的长度要求至少是
512比特。
为了抵抗现有的整数分解算法,对RSA模n的素因子
p和q还有如下要求:
(1)|p-q|很大,通常p和q的长度相同;
(2)p-1和q-1分别含有大素因子p1和q1
(3)gcd(p1-1,q1-1)应该很小。
为了提高加密速度,通常取e为特定的小整数,如EDI国际标准中规定e=216+1,ISO/IEC9796中甚至允许取e=3。
这时加密速度一般比解密速度快10倍以上。
RSA密钥的生成
例:
p=47,q=61,(n)=(47-1)(61-1)=2760时,SK=167是否为秘密密钥的候选者?
用欧氏算法计算:
gcd(2760,167)=1即可证明。
Q
X1
X2
X3
Y1
Y2
Y3
-
1
2760
167
16
-16
88
-1
17
79
2
-33
9
8
-17
281
7
19
-314
3
-74
1223
用RSA算法加密与解密的过程:
明文=“RSAALGORITHM”
(1)明文用数字表示空白=00,A=01,B=02,…,Z=26(两位十进制数表示)
1819010001120715180920081300
(2)利用加密变换公式C=mPKmodr,即C=18191223mod2867=2756
PK=1223=10011000111
=210+27+26+22+21+20
=1024+128+64+4+2+1
C=18191223(mod2867)
=18191024·
1819128·
181964·
18194·
18192·
18191(mod2867)
=2756
2756200105420669234704081815
RSA算法归纳
选择两个大素数p和q,通常要求每个均大于10100。
◆计算n=pxq和z=(p-1)(q-1)。
◆选择一与z互素的数、令其为d。
◆找到一个e满足e×
d=1(modz)。
选好这些参数后,将明文划分成块,使得每个明文报文P长度m满足0<
m<
n。
加密P时,计算C=Pe(modn),解密C时计算P=Cd(modn)。
由于模运算的对称性,可以证明,
在确定的范围内,加密和解密函数是互逆的。
为实现加密,需要公开(e,n),为实现解密需要(d,n)。
问题……
如何计算abmodn?
如何判定一个给定的整数是素数?
如何找到足够大的素数p和q?
RSA的数字签名应用
数字签名方案:
一个签名方案是由签署算法与验证算法两部分构成。
可由五元关系组(M,A,K,S,V)来描述:
(1)M是由一切可能消息所构成的有限集合;
(2)A是一切可能的签名的有限集合;
(3)K为有限密钥空间,是一些可能密钥的有限集合;
(4)任意k∈K,有签署算法Sigk∈S且有对应的验证算法Verk∈V,对每一个Sigk和Verk满足条件:
任意一个签名:
Ver(x,y)={
RSA的数字签名方案
●选取整数n=pq, M=A=Zn
●定义密钥集合K={(n,e,p,q,d)}|n=pq,d*e1(mod(n))}
●n和e为公钥;
p,q,d为保密的(私钥)
●对x∈M,Bob要对x签名,取k∈K:
●Sigk(x)xd(modn)y(modn)
●Verk(x,y)=真xye(modn)
签名消息的加密传递问题
Ø
假设Alice想把签了名的消息加密送给Bob:
对明文x,Alice计算对x的签名y=SigAlice(x),然后用Bob的公钥加密函数eBob,算出z=eBob(x,y),Alice将z传给Bob
Bob收到z后,先解密:
dBob(z)=dBobeBob(x,y)=(x,y)
后检验:
VerAlice(x,y)=真?
问题:
若Alice首先对消息x进行加密,z=eBob(x),然后再签名,y=SigAlice(eBob(x)),结果如何呢?
Alice将(z,y)传给Bob,Bob先将z解密,获取x;
然后用VerAlice检验关于x的加密签名y
一个潜在问题:
如果Oscar获得了这对(z,y),他能用自己的签名来替代Alice的签名
y=SigOscar(eBob(x))
DES和RSA性能比较(同等强度)
6-4 椭圆曲线密码体制ECC
●椭圆曲线密码体制以高效性著称
●由NealKoblitz和VictorMiller在1985年分别提出
●ECC的安全性基于椭圆曲线离散对数问题的难解性
●密钥长度大大地减小
●是目前已知公钥密码体制中每位提供加密强度最高的一种体制
ECC和RSA性能比较
椭圆曲线的概念和分类
定义:
椭圆曲线是一个具有两个变元x和y的三次方程,它是满足:
Y2+aXY+bY=X3+cX2+dX+e
的所有点(X,Y)的集合,外加一个零点或无穷远点O
1、实数域上的椭圆曲线
●实数域上的椭圆曲线是对于固定的a、b值,满足形如方程:
Y2=X3+aX+b
的所有点的集合,外加一个零点或无穷远点
●其中a、b是实数,X和Y在实数域上取值
2、有限域GF(p)上的椭圆曲线
●GF(p)域上的椭圆曲线是对于固定的a、b值,满足形如方程:
Y2=X3+aX+bmod(p)
●其中a、b,X和Y在GF(p)域上取值
Hasse定理
如果E是定义在GF(p)域上的椭圆曲线,N是E上的点的个数,则:
3、有限域GF(2m)上的椭圆曲线
●是对于固定的a、b值,满足形如方程:
Y2+XY=X3+aX2+b
●其中a、b,X和Y在GF(2m)域上取值
●GF(2m)域上的元素是m位的串
椭圆曲线的加法规则
Abel群:
加法规则1:
●加法规则2:
加法规则3:
互逆点
加法规则4:
加法交换律
加法规则5:
加法结合律
加法规则6:
加法规则7:
●标量乘
●阶
–P是椭圆曲线E上的一点,若存在最小的正整数n,使得nP=O,则称n是点P的阶
椭圆曲线密码体制
●椭圆曲线离散对数问题
–已知椭圆曲线E和点P,随机生成一个整数d,容易计算:
Q=d*P,但给定Q和P,计算d就相对困难
1、系统的建立
●选取:
–一个基域GF(p)
–定义在该基域上的椭圆曲线Ep(a,b)
–E上的一个拥有素数阶n的点P
●其中有限域GF(p),椭圆曲线参数a,b,点P和阶n都是公开信息
2、密钥的生成
●在区间[1,n-1]中随机选取一个整数d
●计算:
Q=d*P
●实体的
–公开密钥:
点Q
–实体的私钥:
整数d
3、加密过程
●待发送消息:
A->B:
M
1.查找B的公开密钥:
2.将消息M表示成一个域元素:
m
3.在区间[1,n-1]中随机选取一个整数k
4.计算点:
(x1,y1)=kP
5.计算点:
(x2,y2)=kQ,如果x2=0,则返回第(3)步
6.计算:
c=mx2
7.传送加密数据(x1,y1,c)给B
4、解密过程
●当实体B解密从A收到的密文(x1,y1,c)时,执行步骤:
–
使用私钥d,计算点:
(x2,y2)=d(x1,y1)
–计算,恢复出消息m
A、ECELG-椭圆曲线ElGamal密码体制
●任务:
B->A:
●用户A选取随机数(私钥)dA,产生公开密钥:
PA=dA*G
●用户B选取随机数(私钥)dB,并计算公钥:
PB=dB*G
●B计算并向A发送:
(PB,m+dB*PA)
●用户A解密:
(m+dB*PA)-dA*PB=m
B、ECMO-椭圆曲线Massey-Omura密码体制
设E是有限域GF(p)上的椭圆曲线,N为椭圆曲线的阶,是明文空间到椭圆曲线群的嵌入
用户A选取一个公钥,私钥,满足,,。
●对于消息m,用户B加密消息为用户A解密过程为:
椭圆曲线密码体制的主要优点
●安全性高
●密钥长度小
●算法灵活性好
椭圆曲线密码体制与离散对数密码体制的比较
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 对称 密码 体制