资源描述：
《rsa公钥密码体制简介.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、1公钥密码技术2RSA公钥密码算法主要内容：RSA公钥密码算法，RSA公钥密码的实现。重点：RSA算法，脱密的快速实现，素数生成算法。难点：素数生成算法。3RSA体制由Rivest、Shamir、Adleman于1978年首次发表；最容易理解和实现的公钥算法;经受住了多年深入的攻击;其理论基础是一种特殊的可逆模幂运算，其安全性基于分解大整数的困难性；RSA既可用于加密，又可用于数字签名，已得到广泛采用；RSA已被许多标准化组织(如ISO、ITU、IETF和SWIFT等)接纳；目前许多国家标准仍采用RS
2、A或它的变型4假设m为要传送的报文。1、任产生两个素数p与q，使得n=pq>m2、随机选择数e：e与(p-1)(q-1)互素3、用辗转相除法求d：ed=1mod(p-1)(q-1)4、公开：（e，n），保密：d加密过程：c=memodn解密过程：m=cdmodn一、RSA算法1、RSA算法描述5定义：任给一个正整数m，如果用m去除任意两个整数a、b所得的余数相同，称a、b对模m同余。记为：，若余数不同，则a、b对模m不同余。记为：。定理：，当且仅当m
3、(a-b)。定理：欧拉定理，对任意有推论:费尔马定
4、理，若p为素数，则其中2、工作原理6RSA算法论证①E和D的可逆性要证明：D(E(M))=MM＝Cd＝(Me)d＝Medmodn因为ed＝1modφ(n)，这说明ed＝tφ(n)+1,其中t为某整数。所以,Med＝Mtφ(n)+1modn。因此要证明Med＝Mmodn，只需证明Mtφ(n)+1＝Mmodn。7RSA算法论证在（M，n）＝1的情况下，根据数论(Euler定理)，Mtφ(n)＝1modn，于是有，Mtφ(n)+1＝Mmodn。8RSA算法论证在（M，n）≠1的情况下，分两种情况：第一种情况
5、：M∈{1,2,3,…,n-1}因为n=pq，p和q为素数，M∈{1,2,3,…,n-1}，且（M，n）≠1。这说明M必含p或q之一为其因子，而且不能同时包含两者，否则将有M≥n，与M∈{1,2,3,…,n-1}矛盾。9RSA算法论证10RSA算法论证不妨设M＝ap。又因q为素数，且M不包含q，故有（M，q）＝1，于是有，Mφ(q)＝1modq。进一步有，Mt(p-1)φ(q)＝1modq。因为q是素数，φ(q)＝（q-1），所以t(p-1)φ(q)＝tφ(n)，所以有Mtφ(n)＝1modq。11于
6、是，Mtφ(n)＝bq+1，其中b为某整数。两边同乘M，Mtφ(n)+1＝bqM+M。因为M＝ap，故Mtφ(n)+1＝bqap+M=abn+M。取模n得，Mφ(n)+1＝Mmodn。RSA算法论证12第二种情况：M＝0当M＝0时，直接验证，可知命题成立。RSA算法论证13RSA算法论证②加密和解密运算的可交换性D(E(M))=(Me)d=Med=(Md))e=E(D(M))modn所以，RSA密码可同时确保数据的秘密性和数据的真实性。14RSA算法论证③加解密算法的有效性RSA密码的加解密运算是模幂
7、运算，有比较有效的算法。15RSA算法论证④在计算上由公开密钥不能求出解密钥小合数的因子分解是容易的，然而大合数的因子分解却是十分困难的。关于大合数的因子分解的时间复杂度下限目前尚没有一般的结果，迄今为止的各种因子分解算法提示人们这一时间下限将不低于O（EXP（lnNlnlnN）1/2）。根据这一结论，只要合数足够大，进行因子分解是相当困难的。16RSA算法论证假设截获密文C，从中求出明文M。他知道M≡Cdmodn，因为n是公开的，要从C中求出明文M，必须先求出d，而d是保密的。但他知道，ed≡1mo
8、dφ(n)，e是公开的，要从中求出d，必须先求出φ(n)，而φ(n)是保密的。但他又知道，φ(n)=(p-1)(q-1)，17要从中求出φ(n)，必须先求出p和q，而p和q是保密的。但他知道，n=pq，要从n求出p和q，只有对n进行因子分解。而当n足够大时，这是很困难的。RSA算法论证只要能对n进行因子分解，便可攻破RSA密码。由此可以得出，破译RSA密码的困难性≤对n因子分解的困难性。目前尚不能证明两者是否能确切相等，因为不能确知除了对n进行因子分解的方法外，是否还有别的更简捷的破译方法。183、例
9、子：假设RSA体制中p=3,q=11,取加密密钥e=7.(1)求脱密密钥d;(2)写出相应的加密算法和脱密算法;(3)对明文m=8加密。7dmod20=1因e=7与互素,故可解模方程，即解:此时n＝p×q＝33，且得到d＝3。19故RSA体制明、密文空间:Z/(33)加密密钥：(e,n)=(7,33)脱密密钥：(d,p,q)=(3,3,11)加密算法:c＝m7mod33脱密算法:m＝c3mod33对明文m＝8加密，得:c＝87mod33=220二、RSA
