信息安全认证课件 第四章 公钥密码技术

第四章公钥密码2023/6/92公钥密码公钥密码体制的基本概念RSA算法ElGamal密码Diffie-Hellman密钥交换

2023/6/93Diffie和Hellmna于1976年在《密码学的新方向》中首次提出了公钥密码的观点，标志着公钥密码学研究的开始1977年由Rviest，Shmair和Adlmena提出了第一个比较完善的公钥密码算法，即RSA算法。2023/6/94、

A.Shamir,R.Revist,L.Adleman,R.Merkle,M.Hellman,W.Diffie2023/6/95公钥密码体制

公钥密码算法是基于数学函数（如单向陷门函数）而不是基于代换和置换公钥密码是非对称的，它使用两个独立的密钥，即公钥和私钥，任何一个都可以用来加密，另一个用来解密公钥可以被任何人知道，用于加密消息以及验证签名；私钥仅仅自己知道的，用于解密消息和签名加密和解密会使用两把不同的密钥，因此称为非对称2023/6/96一个公钥密码体制有6个部分构成：明文，加密算法，公钥和私钥，密文，解密算法在加密模型中，发送方用接收方的公钥作为加密密钥，用接收方私钥作解密密钥，由于该私钥只有接收方拥有，因此即只有接收者才能解密密文得到明文2023/6/97消息加密算法解密算法消息MMC攻击者接收方B发送方A密钥源PRBPUB图4.1公钥加密模型公钥加密模型2023/6/98公钥密码系统满足的要求同一算法用于加密和解密，但加密和解密使用不同的密钥。两个密钥中的任何一个都可用来加密，另一个用来解密，加密和解密次序可以交换。产生一对密钥（公钥和私钥）在计算上是可行的已知公钥和明文，产生密文在计算上是容易的。接收方利用私钥来解密密文在计算上是可行的。仅根据密码算法和公钥来确定私钥在计算上不可行已知公钥和密文，在不知道私钥的情况下，恢复明文在计算上是不可行的。2023/6/99上面要求的实质是要找一个单向陷门函数单向函数指计算函数值是容易的，而计算函数的逆是不可行的陷门单向函数则存在一个附加信息，当不知道该附加信息时，从函数逆是困难的，但当知道该附加信息时，求函数逆就变得容易了通常把附加信息称为陷门信息，陷门信息作为私钥，公钥密码体制就是基于这一原理而设计的其安全强度取决于它所依据的问题的计算复杂度。2023/6/910RSA算法

RSAAlgorithm2023/6/911RSA的安全性|p-q|要大p-1,q-1都应有大的素因子。e<n且d<n1/4,则d能被容易的确定。2023/6/912算法描述

1.密钥的产生

随机选择两个大素数p,q

计算n=p×q计算秘密的欧拉函数(n)=(p-1)(q-1)选择e使得1<e<(n)，且gcd(e,

(n))=1解下列方程求出d

ed≡1mod(n)，且0≤d≤n

公开公钥：PU={e,N}保存私钥：PR={d,p,q}2023/6/9132.加密过程加密时明文以分组为单位进行加密，每个分组m的二进制值均小于n，对明文分组m作加密运算：c=memodn,且0≤m<n3．解密过程密文解密m=cd

modn

4.签名过程计算签名s=mdmodn5．签名验证过程签名验证m=se

modn2023/6/914例选择素数：p=47和q=71。计算

n=pq=47×71=3337，

(n)=(p–1)(q-1)=46×70=3220。选择e：使gcd(e,3220)=1，选取e=79；决定d：de≡1mod3220，得d=1019公开公钥

{79,3337}，保存私钥{1019,47,71}；RSA实例2023/6/915假设消息为M=6882326879666683，进行分组，分组的位数比n要小，我们选取M1

=688，M2=232，M3=687，M4=966，M5=668，M6=003。M1的密文为C1=68879mod3337=1570，继续进行类似计算，可得到最终密文为

C=1570275620912276158解密时计算M1=15701019mod3337=688，类似可以求出其他明文。2023/6/916RSA算法的安全性

RSA密码体制的安全性是基于分解大整数的困难性假设RSA算法的加密函数c=memodn是一个单向函数，所以对于攻击者来说，试图解密密文是计算上不可行的对于接收方解密密文的陷门是分解n=pq，由于接收方知道这个分解，他可以计算

(n)=(p-1)(q-1)，然后用扩展欧几里德算法来计算解密私钥d。2023/6/917对RSA算法的攻击有下面几个方法：穷举攻击，数学攻击，选择密文攻击，公共模数攻击等最基本的攻击是穷举攻击，也就是尝试所有可能的私钥数学攻击的实质是试图对两个素数乘积的分解2023/6/918ElGamal密码

ElGamal是1985年由T.EIGamal提出的一个著名的公钥密码算法该算法既能用于数据加密也能用于数字签名其安全性是依赖于计算有限域上离散对数这一难题2023/6/9191.密钥产生任选一个大素数p，使得p-1有大素因子，g是模p的一个本原根，公开p与g。使用者任选一私钥x，x∈[0,p-1]计算公钥公开公钥：y,p,g保密私钥：x2023/6/9202.加密过程对于明文m，选取一个r，r∈[0,p-1]计算则密文为3.解密过程先计算再计算出明文证明M=C2/C1x=My

r/grx=Mgxr/gxr

modp=MMODP2023/6/921ElGamal实例选择p=97及本原根a=5•Bob选择秘密钥xB=58

计算并发布公钥yB=558mod97=44mod972023/6/922Alice要加密M=3toBob•首先得到Bob的公开密钥yB=44选择随机k=36计算:yBK=4436mod97

=75mod97•计算密文对:•C1=536=50mod97•C2=75.3mod97=31mod97•发送{50,31}toBob2023/6/923Bob解密，私钥XB=58W=C1XB

=5058=75mod97•Bob计算W-1=22mod97•Bob恢复明文M=31.22=3mod972023/6/924ElGamal方法具有以下优点：(1)系统不需要保存秘密参数，所有的系统参数均可公开；(2)同一个明文在不同的时间由相同加密者加密会产生不同的密文；但ElGamal方法的计算复杂度比RSA方法要大。2023/6/925Diffie-Hellman密钥交换取一素数p≈2180,两个参数a,b,得到Ep(a,b).取Ep(a,b)的一个生成元G(x1,y1),要求G的阶是一个非常大的素数。(阶是满足nG=O的最小正整数n).Ep(a,b)和G公开，A和B密钥交换过程如下A选小于n的整数nA作为秘密钥，并有PA=nAG作为公钥B类似选取自己的秘密钥nB和公开钥PBA和B分别由K=nAPB和K＝nBPA产生共享的秘密钥攻击者如想获得K，必须由PA和G求出nA或PB和G求出nB2023/6/926两个通信主体Alice&Bob,希望在公开信道上建立密钥初始化:选择一个大素数p(~200digits)一个生成元aAlice选择一个秘密密钥xA<p)Bob选择一个秘密密钥钥xB<pAliceandBob计算他们的公开密钥:yA=axAmodpyB=axBmodpAlice,Bob分别公开yA,yB2023/6/927Bob计算共享会话密钥:KAB=(yA)^xBmodpAlice计算共享密钥KAB=(yB)^xAmodpKAB可以用于对称加密密钥2023/6/928

DH算法实例选取素数p=97,及本根a=5Alice选取秘密xA=36计算公钥yA=536mod97=50mod97Bob选取秘密xB=58计算公钥yB=558mod97=44mod97AliceandBob交换公钥(50&44)Alice计算共享密钥K=4436=75mod97Bob计算共享密钥K=5058=75mod972023/6/929对RSA的攻击－共模攻击每一用户有相同的模数n设用户的公开密钥分别为e1,e2,且e1,e2互素，明文消息为m,密文为因为（e1,e2)=1,用欧几里德算法可求re1+se2=1假定r为负数，从而可知由Euclidean算法可计算(c1-1)r

c2s=mmodn2023/6/930对RSA的攻击－低指数攻击令网中三用户的加密钥e均选3，而有不同的模n1,n2,n3，若有一用户将消息x传给三个用户的密文分别为y1=x3modn1

x<n1y2=x3modn2

x<