计算机安全与保密-第3章

《计算机安全与保密-第3章》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、内容欧拉函数与循环群RSA原理RSA实现的问题大数因式分解问题RABIN公钥密码系统公钥思想DiffieandHellman1976.公钥算法Rivest,Shamir,andAdleman1977欧拉函数自变量为正整数n的函数称为欧拉函数ᴪ(n)，ᴪ(n)表示小于n且与n互素的正整数的个数。当n为素数时，ᴪ(n)=n-1.欧拉函数的计算欧拉函数与循环群欧拉(Euler)定理已知a、n为整数，如果gcd(a,n)=1，则有aᴪ(n)=1(modn)费马(Fermat)小定理已知a、n为整数，如果gcd

2、(a,n)=1，则有an-1=1(modn)封闭ab∈G(双向运算)结合律a(bc)=(ab)c幺元ae=ea=a逆元aa-1=a-1a=e如果仅满足(1)和(2)则称G是一个半群(Semigroup)如果仅满足(1)、(2)和(3)则称G是一个含么半群(Monoid)阿贝尔群：ab=ba(交换律)群：实数加e=0,a-1=-a非零实数乘e=1,a-1=a-1.eabceeabcaaecbbbceaccbae实例(Klein群)无限群、有限群

3、、群的阶设(G,*)是群，G的元素个数是无限时，G称为无限群G的元素个数是有限时，G称为有限群G的元素个数称为群G的阶。元素的阶满足an=e的最小正整数n，称为元素a的阶，记作O(a)如果等式永不成立，则称a的阶为无穷大。子群设S是群G的一个非空子集，如果S对G的运算也构成群，则称S是G的子群(Subgroup)，记作：S≤G.循环子群、生成元设G是群，aϵG，令H={ak

4、kϵZ}，则H称为循环子群(CyclicSubgroup)a为生成元循环群一个群(G,*)称为循环群，如果存在一个元素aϵG，使

5、得G={ak

6、kϵZ}：(Z,+)是由1生成的循环群如果p是素数，那么(Zp,+)是循环群b123452bmod1124851067891011973612如果p是素数，那么(Zp*,*)是循环群生成元为2，p=11时的循环群RSA1978年，Rivest，Shamir和Adleman“AMethodforObtainingDigitalSignaturesandPublic-KeyCryptosystems”RFC2313与RFC3447RFC2537：RSA/MD5KEYsandSIGsinthe

7、DomainNameSystem(DNS).RFC2792：DSAandRSAKeyandSignatureEncodingfortheKeyNoteTrustManagementSystem.RFC3110：RSA/SHA-1SIGsandRSAKEYsintheDomainNameSystem(DNS).实例p=101q=113b=6597a=3533n=11413φ=11200x=6218y=9324NP完全问题用非确定性算法可以在多项式时间内求解的问题称为非确定性多项式时间可解类，或简称NP完

8、全问题或NP问题n=pq的大数因式分解问题求ᴪ(n)和大数因式分解是等价的循环攻击p=23，q=31n=23×31=713a=569，b=29ᴪ(n)=(23-1)(31-1)=660x=25y=2529mod713=36y(0)=2529mod713=36y(1)=3629mod713=676y(2)=67629mod713=625y(3)=62529mod713=583y(4)=58329mod713=656y(5)=65629mod713=614y(6)=61429mod713=501y(7)=

9、50129mod713=397y(8)=39729mod713=532y(9)=53229mod713=25y(10)=2529mod713=36同模攻击p=89，q=137n=89*137=12193a1=10429，b1=661a2=4468，b2=1181x=2005y1=2005661mod12193=3429y2=20051181mod12193=11196c1=661-1mod1181=1047c2=(1047×661-1)/1181mod12193=586RSA实现的问题如何找到足够大的

10、素数？一类是通过数学理论构造出一个大的素数另一类是随机给定一个足够大的数，然后去证明它是素数。如何高效地实现模指数运算？素性检测验证一个数是不是素数叫素性检测Wilson定理p是素数22！=1124000727777607680000=-1mod23运算量非常大，并不实用拟素数设n是一个奇合数，若整数b与n互素，成立则n称作对于基b的拟素数。随机选取与n互素的整数b，若bn-1=1(modn)成立，则n为拟素数的概率≤50%，n为素数的概率≥50%该性质