计算机安全%20%20公钥密码体系

1、编辑ppt 公钥密码体系计算机安全与保密编辑ppt对称算法的不足n密钥必须通过某一信道协商，对这个信道的安全性的要求比正常的传送消息的信道的安全性要高编辑ppt公钥密码背景A用户加密公钥空间密码分析解密私钥空间用户B明文M1(,)CE M k密文1k2k2( ,)MD C k公钥密码体制的特点：n加密密钥与解密密钥在本质上是不同的，即已知一个密钥并不能轻易地求出另一个密钥。1.不需要增加分发密钥的额外信道。编辑ppt公钥密码体制的要求：编辑pptn公钥密码的安全性依赖于从已知的公钥，加密算法和密文中无法求出明文或秘钥。nDiffie和Hellman提出了一种陷门单向函数概念，为建立公钥密码体制

2、找到了一种途径。编辑ppt单向函数n函数f 若满足下列条件n）对任意给定的x，容易计算f(X)=yn）对任意给定的y，求出x使得f(x)=y是困难的。编辑pptn求离散对数问题y=gx mod p若给出p,g,y求x称为求离散对数问题n因子分解问题n=pq若给定n,求p,q称为因子分解问题n背包问题给定一个有限个自然数序列集合B=(b1,b2,bn)及二进制数序列x=(x1,x2,xn)，S= x1 b1 + x2 b2 + + xn bn给定B，S，求x序列，称为求背包问题编辑ppt单向陷门函数：单向陷门函数是满足下列条件的函数f：n给定x，计算y=f(x)是容易的；n给定y, 计算x使x=

3、f-1(y)是不可行的；1.存在陷门t，已知t时，对给定的任何y，若相应的原象x存在，则计算x是容易的。编辑ppt通过陷门单向函数建立公钥密码nf(x)是单向陷门函数，陷门为t。 那么设计公钥密码系统时f(x)作为公钥，陷门t作为私钥，任何人都可将明文m利用公钥f(x)加密得到密文y=f(m)，而任何人不知道私钥即陷门，由密文y都无法求出m，因为f(x)是单向的，但拥有私钥，便可容易求出m编辑pptRSA公钥密码体制1 、1977年由Rivest、Shamir和 Adleman发明并于1978年公布。2 、明文和密文在0n-1之间,n是一个正整数3 、应用最广泛的公钥密码算法4 、只在美国申请

4、专利，且已于2000年9月到期编辑ppt欧拉函数( )n1, )nnnn在中，不大于 而且与 互素的正整数的个数，记作 (编辑ppt欧拉函数( )n11)12)(1)kkppppppp、 为素数， (、 为素数, (1,kkpp计 数 ：中 与互 素 的 数 的 个 数1111,1,kkkkkkkkppppppppppppp除去中 的倍数，剩下的都与互素,2是中所有 的倍数，共有个。所以与互素的数的个数有个1212123(,)1()() ()m mm mmm、若，则编辑ppt欧拉函数( )n11)12)(1)kkppppppp、 为素数， (、 为素数, (1212123(,)1()() ()

5、m mm mmm、若，则1, ( )?nn编辑ppt欧拉函数11)12)(1)kkppppppp、 为素数， (、 为素数, (1212123(,)1()() ()m mm mmm、若，则1212121212121211111221, ( )? ( )()() ()()(1)(1)(1)mmmmeeemeeeeeemmeeemmnnnp ppnp ppppppppppp编辑ppt欧拉函数(300)?练习：2222(300)(253)(2 ) (5 ) (3)2(21)5(51)(31)80,()?p qpq为素数，()( ) ( )(1)(1)pqpqpq编辑pptnRSA密码体制的描述n密钥

6、生成算法：每个用户执行以下操作n随机生成两个不同大素数p,q;n计算n=pq,(n)=(p-1)(q-1);n随机选取整数e,1e2是一个素数，对于任意整数b0,如果(b,p)=1则p一定是b为基的强伪素数这个定理说明了Miller-Rabin算法如果输入的n是素数，正确的输出判定n是素数定理如果n为一奇合数，则在0,n中，至多有1/4个b 0,n满足n是b为基的强伪素数这个定理说明了Miller-Rabin算法如果输入的n是合数，但输出判定n是素数的概率最多是总之，Miller-Rabin算法判定n是素数的正确概率至少为75%编辑pptMiller-Rabin素数判定算法Prime_test

7、(n)For i=0 to 50 b=rand(); if test(n,b)=false return false;/输出n不是素数 return true;/输出n是素数编辑pptP-1分解法0,122mod3gcd(1, )4(1)jStepinputn BStepaStepBaanStepdanStepifdndnelsefor j=2 to 是 的一个因子分解失败编辑ppt2 3 4 5 61333622mod1333,838(838 1,1333)3131 1333nBStepaa ，后，所以是的一个因子，1333=31 43编辑ppt!1|1(1)|!22 mod2 mod21mod(1)|!1mod|1| ,|(1, )(1, )1,(1, )BBppnq pqqBpBStepanpnp napppBapp ap