计算机网络安全与管理：第六讲 公钥加密算法

计算机网络安全与管理

第六讲公钥加密算法本讲内容数论知识补充难解问题公钥加密系统RSA算法其他素数素数是除了1与自身无其他因子的数它们无法被写为数字的乘积1一般不再考虑之内例如：2，3，5，7是素数，4，6，8，9不是素数是数论研究的中心200以内的素数有：2357111317192329313741434753596167717379838997101103107109113127131137139149151157163167173179181191193197199

素因子N的分解就是将N写为其他数字的分解：n=axbxc

分解一个数要比通过将因子相乘得到一个数要困难得多素分解：互质与最大公约数当两个数最大公约数是1时称两个数互素相反的，我们可以通过比较它们的素因子的最小阶数得到例：300=21x31x5218=21x32

henceGCD(18,300)=21x31x50=6费尔马小定理

（Fermat’sLittleTheorem）ap-1=1(modp)这里的p为素数且gcd(a,p)=1在公钥加密与素性检验中很有用欧拉函数对于模n的算术运算其完全剩余集为：0..n-1

将完全剩余集中与n互素的元素的个数称为欧拉函数EulerTotientFunctionø(n)

例：n=10完全剩余集为{0,1,2,3,4,5,6,7,8,9}其中与n互素的为{1,3,7,9}欧拉函数值为4思考，若n为素数p的k次方，那么欧拉函数值为？欧拉定理是一个费尔马定理的推广aø(n)=1(modn)对于任意的a，n若gcd(a,n)=1例：a=3;n=10;ø(10)=4;

因此34=81=1mod10a=2;n=11;ø(11)=10;

因此210=1024=1mod11素性检验经常被用来寻找大素数传统的方式是试除法该方法通常用于较小的数字实际应用中通常利用素数的统计学特征进行选择：测试所有的素数都满足的特性但有些合数也同样满足MillerRabinAlgorithmTEST(n)is:1.Findintegersk,q,k>0,qodd,sothat(n–1)=2kq2.Selectarandomintegera,1<a<n–13.ifaq

modn=1

thenreturn(“maybeprime");4.forj=0tok–1do 5.if(a2jq

modn=n-1) thenreturn("maybeprime")6.return("composite")选出伪素数的概率小于1/4，通过多次选择a的值增加素数的概率素数的分布大约是每lnn出现由于可以忽略偶数所以实际上在n中平均下来看大约寻找一个素数需要的运算量是

0.5ln(n)

中国剩余定理通常用来加速模运算假设模数为若干数的乘积例如：modM=m1m2..mk

中国剩余定理令我们可以将mi单独的进行模运算由于计算量与大小成正比，这将比直接利用完整的M计算要快中国剩余定理补充要计算A（modM）首先计算ai=Amodmi

确定ci

，这里Mi=M/mi最后组合得到结果本原根由欧拉定理我们有：aø(n)modn=1考虑am=1(modn),GCD(a,n)=1M是一定存在的（因为可以m=ø(n)

）一旦阶数达到m则出现循环若m=ø(n)

那么a被称为本原根若p为素数则连续不断的a的阶生成了模p的群。很有用但难找。离散对数对模p的指数的运算的逆运算被称为离散对数就是找x满足：y=gx(modp)记为

x=loggy(modp)若g为本原根则始终存在，否则可能不存在x=log34mod13无解x=log23mod13=4通过连续的试算可得求解离散对数问题是一个困难问题。私钥密码学传统的私钥加密使用单一的密钥发送方与接收方共享密钥若密钥泄露则通信会出现泄密是对称的，当事双方地位均等。因此无法避免当接收方伪造消息并声称来源于发送方背景对称密钥编码所面临的难题密钥分配。通信密钥太多，管理和分发困难。数字签名和认证。密码体制上的突破Diffie&Hellman,“NewDirectioninCryptography”,1976。首次公开提出了“公开密钥密码编码学”的概念。这是一个与对称密码编码截然不同的方案。提出公开密钥的理论时，其实用性并没有又得到证明：当时还未发现满足公开密钥编码理论的算法；直到1978年，RSA算法的提出。公钥密码学也许是3000年来密码学发展史中最巨大的进步使用两个密钥-私钥与公钥非对称，因此参与者地位不再相当通过巧妙的利用数论观念实现是私钥密码学的补充而不是取代为何采用公钥密码学为解决两个关键性问题密钥分配（keydistribution）-如何在不需要密钥分配中心KDC的前提下安全通信数字签名-

如何验证消息来源于被声称的发送方公开提出：WhitfieldDiffie&MartinHellman1976其实在60年代中期已在NSA中提出公钥密码学公钥/双密钥/非对称密码学涉及两个密钥公钥：可被所有人知道，可被用来加密消息与验证签名私钥：仅被接受者所知，用来解密消息于创建签名。该类算法被称为非对称因为加密消息或验证签名的那一方无法解密消息或创建签名公钥密码学公钥密码算法的特性 公钥密码算法依赖于两个密钥，这里：如果仅知道算法与加密密钥那么要获取解密密钥在计算上是不可行的当知道相应的加/解密密钥时进行加解密运算在计算上是比较容易的相关联的两个密钥都可以被用来加密消息而另一个则被用来解密公钥密码系统公钥密码学的应用通常被用在三个范畴加密消息（提供安全性）数字签名（提供鉴别）密钥交换（会话密钥）公钥密码策略的安全性像私钥密码算法一样，采用暴力破解理论上是可行的。密钥非常长（512bit）安全性依赖于足够大的加解密与密码分析之间的难度差异需要非常大的数字相比于私钥加密要慢公钥密码算法基础单向函数

对于一个函数，如果对于其定义域上的任意x，都容易计算，同时，对于其值域中几乎所有的取值y，计算其逆函数都是不可行的，则函数被称为单向函数。

可以提供单向函数的三大数学难题大整数分解问题（简称IFP）；离散对数问题（简称DLP）；椭圆曲线离散对数问题（简称ECDLP）。算法基础单向陷门函数对于一个单向函数，如果其逆函数在已知某些辅助信息的情况下容易求解得出，则称该单向函数为单向陷门函数。

构造公钥密码系统的关键是如何在求解某个单向函数的逆函数的NP完全问题中设置合理的“陷门”公钥密码算法基于因子分解问题的Rabin算法；椭圆曲线公钥算法；基于有限域中离散对数难题的ElGamal公钥密码算法基于代数编码系统的McEliece公钥密码算法；基于“子集和”难题的Merkle-HellmanKnapsack公钥密码算法；目前被认为安全的Knapsack型公钥密码算法Chor-Rivest。RSARivest,Shamir&AdlemanofMITin1977最为人所知与广泛采用的公钥策略基于整数有限域中模p的指数运算指数运算需要O((logn)3)（容易）使用大整数（1024bits）安全性来源于大整数的分解困难分解需要O(elognloglogn)（困难）RSA密钥的建立用户通过如下过程生成密钥对选择两个随机的大素数p，q计算它们的成绩（系统的模）n=pq注意ø(n)=(p-1)(q-1)

随机选取加密密钥e这里1<e<ø(n),gcd(e,ø(n))=1解下面的等式获得解密密钥de.d=1modø(n)and0≤d≤n

公开其公钥：PU={e，n}保留私钥：PR={d，n}RSA的使用加密一条消息M，发送方需要：获取公钥PU={e,n}

计算C=Memodn,where0≤M<n解密C，接收方需要利用私钥PR={d,n}

计算M=Cdmodn

必要的时候需要进行分块为何能够成立由欧拉定理aø(n)modn=1这里gcd(a,n)=1由于n=p.qø(n)=(p-1)(q-1）而e，d模ø(n)

互逆因此对某个k应有e.d=1+k.ø(n)

因此Cd=Me.d=M1+k.ø(n)=M1.(Mø(n))k

=M1.(1)k=M1=Mmodn

例子

p=17&q=11n=pq=17x11=187ø(n)=(p–1)(q-1)=16x10=160e:

gcd(e,160)=1;e=7d:

de=1mod160andd<160Valueisd=23since23x7=161=10x160+1PU={7,187}PR={23,18