信息安全概论第四章公钥密码体制

第四章公钥密码体制4.1公钥密码体制的基本原理4.2RSA算法4.3ElGamal密码体制4.4椭圆曲线密码（ECC）体制1公钥密码体制的起源•公钥密码又称为双钥密码和非对称密码，是1976年由Diffie和Hellman在其“密码学新方向”一文中提出的，这在密码学的发展史上具有里程碑的意义，并在1978年由Rivest、Shamire和Adleman提出了第一个比较完善的公钥密码体制算法，即著名的RSA算法。后来陆续出现了ElGalam、ECC等公钥密码体制。解决了对称密码体制中密钥分配、消息认证、加密、数字签名等问题。特别适合于计算机网络系统的应用。主要有以下算法：–Diffie-Hellman密钥交换算法–背包算法–RSA算法–ElGamal算法2公开密钥算法

公开密钥算法是非对称算法，即密钥分为公钥和私钥，因此称双密钥体制双钥体制的公钥可以公开，因此也称公钥算法公钥算法的出现，给密码的发展开辟了新的方向。公钥算法虽然已经历了20多年的发展，但仍具有强劲的发展势头，在鉴别系统和密钥交换等安全技术领域起着关键的作用公钥密码是现代密码体制的一种公钥密码体制的编码系统是基于数学中的单项陷门函数3对称算法的不足（1）密钥管理量的困难传统密钥管理：两两分别用一个密钥时，则n个用户需要C(n,2)=n(n-1)/2个密钥，当用户量增大时，密钥空间急剧增大。如:n=100时，C(100,2)=4,995n=5000时，C(5000,2)=12,497,500（2）密钥必须通过某一信道协商，对这个信道的安全性的要求比正常的传送消息的信道的安全性要高4.1公钥密码体制的基本原理4（3）数字签名的问题传统加密算法无法实现抗抵赖的需求。(4)在进行保密通信时，发送者与接收者需要使用一个安全信道来建立会话密钥。会话密钥的取得可以通过两种方式实现：其一、通过共享密钥加密传输会话密钥（人工方式获得）其二、通过密钥分配中心获得会话密钥，分配成本很高。5基本概念公钥密码体制：指一个加密系统的加密密钥和解密密钥匙不一样的，或者说不能由一个推导出另一个。其中一个称为公钥用于加密，是公开的，另一个称为私钥用于解密，是保密的。公钥密码体制是基于单项陷门函数单向函数：设f是一个函数，如果对任意给定的x，计算y，使得y=f(x)是容易计算的，但对于任意给定的y，计算x，使得x=f-1(y)是难解的，即求f的逆函数是难解的，则称f是一个单项函数。在密码学中，最常用的单项函数有两类：公钥密码体制中的单项陷门函数和消息摘要中的单项散列函数单向陷门函数：设f是一个函数，t是与f有关的一个参数。对任意给定的x，计算y，使得y=f(x)是容易计算的,如果当不知参数t时，计算f的逆函数是难解的，但当知道参数t时，计算函数f的逆函数是容易的，则称f是一个单项陷门函数，参数t成为陷门。6注意：单向函数不能用于加密在公钥密码体制中，计算f(x)相当于加密，陷门y相当于私钥，而利用陷门y，求f(x)中的x则相当于解密。公钥密码体制最初的目标是解决DES算法中密钥管理的问题，而实际结果不但很好地解决了这个难题，还利用公钥密码体制完成了对消息的数字签名以防对消息的抵赖行为；同时，还可以用数字签名发现攻击者对消息的非法篡改，以保护数据信息的完整性。7公开密钥密码的重要特性

加密与解密由不同的密钥完成加密:X

Y:Y=EKU(X)解密:Y

X:X=DKR(Y)=DKR(EKU(X))

知道加密算法,从加密密钥得到解密密钥在计算上是不可行的

两个密钥中任何一个都可以用作加密而另一个用作解密(不是必须的)X=DKR(EKU(X))8基于公开密钥的加密过程Alices向Bob发送加密信9基于公开密钥的鉴别过程Alices与Bob通信，Bob进行验证10用公钥密码实现保密•用户拥有自己的密钥对(KU,KR)•公钥KU公开,私钥KR保密•A

B:Y=EKUb(X)•B:DKRb(Y)=DKRb(EKUb(X))=X用公钥密码实现鉴别•条件:两个密钥中任何一个都可以用作加密而另一个用作解密•数字签名:A

ALL:Y=DKRa(X)ALL:EKUa(Y)=EKUa(DKRa(X))=X•数字签名+保密:A

B:Z=EKUb(DKRa(X))B:EKUa(DKRb(Z))=X11加密/解密•数字签名(身份鉴别)•密钥交换公钥密钥的应用范围12基本思想和要求•涉及到各方：发送方、接收方、攻击者•涉及到数据：公钥、私钥、明文、密文•公钥算法的条件：–产生一对密钥是计算可行的–已知公钥和明文，产生密文是计算可行的–接收方利用私钥来解密密文是计算可行的–对于攻击者，利用公钥来推断私钥是计算不可行的–已知公钥和密文，恢复明文是计算不可行的–(可选)加密和解密的顺序可交换13常用的公开密钥算法公钥算法的种类很多，具有代表性的三种密码：基于整数分解难题（IFP）的算法体制(RSA)

基于离散对数难题（DLP）算法体制(ElGamal)基于椭圆曲线离散对数难题（ECDLP）的算法体制(ECC)14Diffie-Hellman密钥交换算法Diffie和Hellman在其里程碑意义的文章中，虽然给出了密码的思想，但是没有给出真正意义上的公钥密码实例，也既没能找出一个真正带陷门的单向函数然而，他们给出单向函数的实例，并且基于此提出Diffie-Hellman密钥交换算法15Diffie-Hellman密钥交换算法的原理基于有限域中计算离散对数的困难性问题之上：设F为有限域，g∈F是F的乘法群F*=F\{0}=<g>，并且对任意正整数x，计算gx是容易的；但是已知g和y求x使y=gx，是计算上几乎不可能的这个问题称为有限域F上的离散对数问题。公钥密码学中使用最广泛的有限域为素域FP16Diffie-Hellman密钥交换协议描述当Alice和Bob要进行保密通信时，他们可以按如下步骤来做：(1)Alice选取大的随机数x，并计算X=gx(modP)(2)Bob选取大的随机数x

，并计算X

=gx

(modP)(3)Alice将X传送给Bob；Bob将X

传送给Alice(4)Alice计算K=(X

)X(modP);Bob计算K

=（X)X

(modP),

易见，K=K

=g

xx

(modP)由(4)知，Alice和Bob已获得了相同的秘密值K双方以K作为加解密钥以传统对称密钥算法进行保密通信174.2RSA算法184.2RSA算法最早实现Diffie和Hellman的想法的美国麻省理工学院的Rivest、Shamie

和Adleman3人。他们于1977年研制并于1978年发表了一种密码算法，一般称为RSA算法，实现了公钥密码的基本思想。19RSA安全性是基于大整数分解因子的困难性204.2.1RSA算法描述1.RSA密码体制的建立（1）选择两个大素数p和q，p≠q（2）计算乘积n=pq,n的Euler数φ(n)=(p-1)(q-1)（3）选择随机数e,(1<e<φ(n)),使gcd(e，φ(n))=1（4）使用Euclidean算法计算de=1modφ(n)（5）对每一个密钥k=(n，p，q，d，e)，定义加密变换为

Ek(x)=xemodn,解密变换为Dk(x)=ydmodn，（6）公钥:KU={e,n},私钥:KR={d,p,q}密码分析者攻击RSA体制的关键点在于如何分解n。若分解成功使n=pq，则可以算出φ(n)＝（p-1)(q-1)，然后由公开的e，解出秘密的d。212.RSA算法举例1.设p=7,q=17,2.计算n=7*17=119；参数T={n=119};φ(n)=(7-1)(17-1)=96;3.选择随机数e=5,gcd(5,96)=1;公钥=5;4.计算d,(d*e)mod96=1;d=77;私钥=77;5.设:明文m=19

加密：C=（19）5mod119=66

脱密：m=（66）77mod119=19计算d的过程如下：96=5*19+11=96-5*19mod96=96-5*(-96+19)mod96==96+5*77mod96d=7722RSA实例已知p=11，q=13，e=7,M=85，求解d，c解：n=p*q=143;φ(n)=(p-1)*(q-1)=10*12=120计算d，使得de=1mod120120=7*17+11=120-7*17mod120=120-7*(-120+17)mod120==120+7*103mod120d=10323RSA算法的安全性分析密码分析者攻击RSA体制的关键点在于如何分解n若分解成功使n=pq，则可以算出φ(n)＝（p-1)(q-1)，然后由公开的e，解出秘密的d若使RSA安全，p与q必为足够大的素数，使分析者没有办法在多项式时间内将n分解出来24RSA算法的安全性分析建议选择p和q大约是100位的十进制素数,按每秒109次运算的高速计算机也要计算106年,估计对200位十进制数的因数分解,在上亿次的计算机上要进行55万年。模n的长度要求至少是512比特EDI攻击标准使用的RSA算法