密码学-公钥密码-课件

密码学公钥密码本章内容公钥密码体制的基本原理数论基础RSA算法Diffie-Hellman密钥交换算法ElGamal密码体制椭圆曲线密码体制ECC公钥密码体制的基本原理公钥密码体制的提出和起源公钥密码的特点公钥密码的应用公钥密码的要求公钥密码的理论基础公钥密码体制的基本原理公钥密码往常:所有的密码算法都是基于代换和置换这两个基本工具。而公钥密码体制为密码学的发展提供了新的理论和技术基础基本工具是数学函数公钥密码算法是以非对称的形式使用两个密钥,两个密钥的使用对保密性、密钥分配、认证等都有着深刻的意义。能够说公钥密码体制的出现在密码学史上是一个最大的而且是惟一真正的革命。问题的提出公钥密码体制的概念是在解决单钥密码体制中最难解决的两个问题时提出的,这两个问题是密钥分配和数字签字。密钥分配问题通信双方要进行加密通信,需要通过秘密的安全信道协商加密密钥,而这种安全信道估计特别难实现;密钥管理问题:两两分别用一对密钥时,则n个用户需要C(n,2)=n(n-1)/2个密钥,当用户量增大时,密钥空间急剧增大。如:n=100时,C(100,2)=4,995n=5000时,C(5000,2)=12,497,500没有签名功能:当主体A收到主体B的电子文挡(电子数据)时,无法向第三方证明此电子文档确实来源于B,无法实现抗抵赖的需求。起源公钥密码又称为双钥密码和非对称密码,是1976年由Stanford大学的Diffie和Hellman在其“密码学新方向”

一文中提出的,见划时代的文献:W、DiffieandM、E、Hellman,NewDirectrionsinCryptography,IEEETransactiononInformationTheory,V、IT-22、No、6,Nov1976,PP、644-654RSA公钥算法是由Rivest,Shamir和Adleman在1978年提出来的,见:munitionsoftheACM、Vol、21、No、2、Feb、1978,PP、120-126、公钥密码的重要特性加密与解密由不同的密钥完成加密:X→Y:Y=EKU(X)解密:Y→X:X=DKR(Y)=DKR(EKU(X))明白加密算法,从加密密钥得到解密密钥在计算上是不可行的两个密钥中任何一个都能够用作加密而另一个用作解密(不是必须的)X=DKR(EKU(X))=EKU(DKR(X))基于公开密码的加密过程用户拥有自己的密钥对(KU,KR),公钥KU公开,私钥KR保密Bob→Alice:Y=EKUa(X)Alice:DKRb(Y)=DKRa(EKUa(X))=X基于公开密码的鉴别过程条件:两个密钥中任何一个都能够用作加密而另一个用作解密鉴别:Ailce→ALL:Y=EKRa(X)ALL:EKUa(Y)=DKUa(EKRa(X))=X基于公开密码的鉴别过程在实际应用中,特别是用户数目特别多时,以上认证方法需要特别大的存储空间,因为每个文件都必须以明文形式存储以方便实际使用,同时还必须存储每个文件被加密后的密文形式即数字签字,以便在有争议时用来认证文件的来源和内容。改进的方法是减小文件的数字签字的大小,即先将文件经过一个函数压缩成长度较小的比特串,得到的比特串称为认证码。认证码具有如此一个性质:假如保持认证码的值不变而修改文件这在计算上是不可行的。用发送者的秘密钥对认证码加密,加密后的结果为原文件的数字签字。基于公开密码的鉴别+保密过程鉴别+保密:

A→B:Z=EKUb(EKRa(X))B:DKUa(DKRb(Z))=X公钥密码的应用范围加密/解密(保密性)数字签名(身份鉴别)密钥交换(会话密钥)基本思想和要求涉及到各方:发送方、接收方、攻击者涉及到数据:公钥、私钥、明文、密文公钥算法的条件:–产生一对密钥是计算可行的–已知公钥和明文,产生密文是计算可行的–接收方利用私钥来解密密文是计算可行的–关于攻击者,利用公钥来推断私钥是计算不可行的–已知公钥和密文,恢复明文是计算不可行的–(可选)加密和解密的顺序可交换其中最后一条尽管特别有用,但不是对所有的算法都作要求。公钥密码的理论基础难解问题:没有有效算法,求解所需时间特别长。易解问题:存在有效算法,求解所需时间短一般来说计算一个难解的问题所需要的时间通常是所输入数据长度的一个指数函数,因此计算时间是随着数据长度的增加急剧增加的。陷门单向函数公钥密码是建立在陷门单向函数上的。单向函数(onewayfunction):(1)给定x,计算y=fk(x)是容易的;(2)给定y,计算x使y=fk-1(x)是不可行的。陷门单向函数(trapdooronewayfunction):(1)给定x,计算y=fk(x)是容易的;(2)给定y,计算x使y=fk-1(x)是不可行的。(3)存在k,已知k时,对给定的任何y,若相应的x存在,则计算x使y=fk-1(x)是容易的。研究公钥密码算法就是要找出合适的陷门单向函数。公钥密码体制的安全性像对称密码体制一样,密钥穷搜索攻击理论上是有效的;然而使用的密钥太大(>512bits)安全性依赖于难解问题;一般难解问题是已知的,然而需要设计的足够难;需要使用特别大的数;因此比对称密码算法要慢;数论基础1、素数2、模运算3、Euclid算法4、费马定理和欧拉定理5、素性测试6、中国剩余定理7、离散对数见:第8章数论入门、ppt经典例子RSA算法Diffe-Hellman密钥交换算法ElGamal密码体制椭圆曲线密码体制ECCRSA公开密钥算法RSA算法描述RSA的实现问题RSA的安全性RSA公开密钥算法1977年由RonRivest、AdiShamir和LenAdleman发明,1978年公布是一种分组加密算法

–明文和密文在0~n-1之间,n是一个正整数用数论构造迄今为止理论上最为成熟完善的公钥密码体制应用最广泛的公钥密码算法只在美国申请专利,且已于2000年9月到期RSA公开密钥算法—算法描述算法的论证RSA算法的论证加密和解密运算的可交换性

D(E(M))=(Me)d=(Md)e=E(D(M))modn

因此,RSA密码可同时确保数据的秘密性和真实性加解密算法的有效性

RSA密码的加解密运就是模幂运算,有比较有效的算法RSA算法的论证在计算上由公开密钥不能求出解密钥

小合数的因子分解是容易的,然而大合数的因子分解确是十分困难的。关于大合数的因子分解的时间复杂度下限目前尚没有一般的结果,迄今为止的各种因子分解算法提示人们这一时间下限将不低于O(EXP(lnNlnlnN)1/2)。依照这一结论,只要合数足够大,进行因子分解是相当困难的。RSA算法的论证假设截获密文C,从中求出明文M。他明白

M≡Cd

mod

n,因为n是公开的,要从C中求出明文M,必须先求出d,而d是保密的。但明白,

ed≡1

mod

Ø(n),

E是公开的,要从中求出d,必须先求出Ø(n),而Ø(n)是保密的。RSA算法的论证在计算上由公开密钥不能求出解密密钥但明白,Ø(n)=(p-1)(q-1)

要从中求出Ø(n),必须先求出p和q,而p和q是保密的。明白n=pq,要从n求出p和q,只有对n进行因子分解。而当n足够大时,这是特别困难的。只要能对n进行因子分解,便可攻破RSA密码。由此能够得出,破译RSA密码的困难性<=对n因子分解的困难性。目前尚不能证明两者是否能确切相等,因为不能确知除了对n进行因子分解的方法外,是否还有别的更简捷的破译方法。目前只有Rabin密码具有:破译Rabin密码的困难性=对n因子分解的困难性RSA算法的论证RSA的安全性是基于加密函数ek(x)=xe(modn)是一个单向函数,因此对的人来说求逆计算不可行。而Bob能解密的陷门是分解n=pq,知ϕ(n)=(p-1)(q-1)。从而用扩展的Euclid算法解出解密私钥d。密码分析者攻击RSA体制的关键点在于如何分解n。若分解成功使n=pq,则能够算出φ(n)＝(p-1)(q-1),然后由公开的e,解出秘密的d。猜想:攻破RSA与分解n是多项式等价的。然而,这个猜想至今没有给出可信的证明！！！两个问题和两个假设RSA的安全性是基于RSA假设,而不是基于分解大整数的困难性假定RSA算法举例RSA密码体制的实现实现的步骤如下:Bob为实现者(1)Bob寻找出两个大素数p和q(2)Bob计算出n=pq和ϕ(n)=(p-1)(q-1)、(3)Bob选择一个随机数e(0<e<ϕ(n)),满足(e,ϕ(n))=1(4)Bob使用辗转相除法计算d=e-1(modϕ(n))(5)Bob在目录中公开n和e作为她的公开钥。选好这些参数后,将明文划分成块,使得每个明文报文P长度m满足0<m<n。

加密P时,计算C＝Pe(modn),解密C时计算P＝Cd(modn)。由于模运算的对称性,能够证明,在确定的范围内,加密和解密函数是互逆的。为实现加密,需要公开(e,n),为实现解密需要(d,n)。RSA的加、解密过程示例RSA的实现——参数选择为了确保RSA密码的安全,必须认真选择密码参数:

①p和q要足够大:一般应用:p和q应512b重要应用:p和q应1024b

②p和q应为强素数文献指出,只要(p-1)、(p+1)、(q-1)、(q+1)四个数之一只有小的素因子,n就容易分解。

③

(p-1)和(q-1)的最大公因子要小假如(p-1)和(q-1)的最大公因子太大,则易受迭代加密攻击。RSA的实现——参数选择⑤

e的选择随机且含1多就安全,但加密速度慢。因此,有的学者建议取e=216+1=65537⑥

d的选择

d不能太小,要足够大⑦

不要许多用户公用一个模n:易受共模攻击另外两个常用的e的选择是3和17、然而假如e=3。这时加密速度一般比解密速度快10倍以上。然而易受低指数攻击。注意:密钥产生要求(e,

ϕ(n))=1,因此假如用户选择了e=65537,接着生成了素数p,q,特别有估计不能满足(e,

ϕ(n))=1,因此用户应该去掉那些模65537和1不同余的p和q。RSA实现中的问题(1)如何计算abmodn需要计算模300digits(or1024+bits)的乘法(2)如何判定一个给定的整数是素数？(3)如何找到足够大的素数p和q?其中d是中间结果,d的终值即为所求结果。c在这个地方的作用是表示指数的部分结果,其终值即为指数m,c对计算结果无任何贡献,算法中完全可将之去掉。快速加解密

加密特别快,指数小解密比较慢,指数较大利用中国剩余定理CRT,分别计算modp和modq,再组合成所需的结果。能够加快运算速度,比直截了当计算M=Cdmodn相比,速度大约快4倍。CRT对RSA解密算法生成两个解密方程(利用M=Cdmodn)即:Vp=Mmodp=(Cmodp)dmod(p-1)

Vq

=Mmodq=(Cmodq)dmod(q-1)

解方程M=VpmodpM=Vq

modq具有唯一解(利用CRT

):

定义:Xp=q×(q－1modp)Xq=p×(p－1modq)M=(VpXp+Vq

Xq

)modn只有明白p和q的私钥的拥有者才能使用这种技术;如何判定一个给定的整数是素数？MillerandRabin,WITNESS算法WITNESS(a,n)判定n是否为素数,a是某些小于n的整数;首先将n-1表示为二进制形式bkbk-1…b0,并给d赋初值1,则算法Witness(a,n)的核心部分如下:fori=kdownto0do { x←d; d←(d×d)modn; ifd=1and(x≠1)and(x≠n-1)thenreturnFalse; ifbi=1thend←(d×a)modn }ifd≠1thenreturnFalse;returnTrue、返回值:FALSE:n一定不是素数TRUE:n估计是素数应用:随机选择a<n,计算s次,假如每次都返回TRUE,则这时n是素数的概率为(1-1/2s)。如何找到足够大的素数p和q?1、随机选一个奇数n(如:可使用伪随机数发生器)2、随机选择一个整数a<n3、执行概率素数判定测试(如:用WITNESS(a,n)),假如n未测试通过,则拒绝数值n,转向步骤14、假如n已通过足够的测试,则接受n,否则转向步骤2;说明:①随机选取大约用ln(N)/2的次数,如ln(2200)/2=70②好在生成密钥对时才用到,慢一点还可忍受。③确定素数p和q以后,只需选取e,满gcd(e,φ(n))=1,

计算d=e-1modφ(n)(扩展的Euclid算法);

两个随机数互素的概率约为0、6;对RSA的攻击方法1、强力攻击(穷举法):尝试所有估计的私有密钥2、数学分析攻击:各种数学方法,等价与两个素数乘积的因子分解3、对RSA实现的攻击数学分析攻击

用数学方法攻击RSA的途径有一下三种:分解

n=p、q,如此能够计算ø(n),从而能够确定

d;直截了当确定

ø(n)而不先确定p和q,

也能够计算d;直截了当确定d,而不先确定

ø(n);目前认为后两种方法与第一种方法是等价的,因此对RSA密码分析的讨论大都集中于:将n分解为两个素数因子:尽管因子分解具有大素数因子的数n仍然是一个难题,然而已不像往常那么难。2005、5,差不多能够用格筛法分解200位十进制数(663bit)关于大整数的威胁除了人类的计算能力外,还来自分解算法的进一步改进。二次筛法(QS)→一般数域筛法(GHFS)→格域筛法(LS)估计在未来一段比较长的时期,密钥长度介于1024比特至2048比特之间的RSA是安全的。在使用RSA算法时对其密钥的选取要特别注意其大小,要确保p,q相似的长度,同时满足其他的限制;ProgressinFactoring

ProgressinFactoring对RSA的攻击对RSA的具体实现存在一些攻击方法,但不是针对基本算法的,而是针对协议的。选择密文攻击:共模攻击对RSA的小加密指数攻击对RSA的小解密指数攻击计时攻击:取决于解密算法的运算时间对RSA的选择密文攻击例1:E监听A的通信,收集

由A的公开密钥加密的密文c,E想明白消息的明文m,使m=cdmodn他首先选择随机数r,使r<n。

然后用A的公开密钥e计算x=remodn

y=xc

modnt=r-1modn假如x=remodn,则