初等数论ppt第三章简化剩余类欧拉函数ppt课件.ppt

《初等数论ppt第三章简化剩余类欧拉函数ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第三章(2)简化剩余类、欧拉函数及其应用、RSA复习剩余类及完全剩余系§3简化剩余系与欧拉函数§4欧拉定理.费马定理及应用公钥密码体制36RSA算法概况MIT三位年青数学家R.L.Rivest，A.Shamir和L.Adleman等[1978,1979]发现了一种用数论构造双钥的方法，称作MIT体制，后来被广泛称之为RSA体制。它既可用于加密、又可用于数字签字。RSA算法的安全性基于数论中大整数分解的困难性。37算法描述－密钥产生独立地选取两大素数p和q(各100～200位十进制数字)计算n=p×q，其欧拉函数值(n)=(p－1)(q

2、－1)随机选一整数e，1e<(n)，gcd((n),e)=1在模(n)下，计算e的有逆元d=e-1mod(n)以n，e为公钥。秘密钥为d。(p,q不再需要，可以销毁。)加密将明文分组，各组对应的十进制数小于nc=memodn解密m=cdmodn38解密正确性证明cdmodn≡medmodn≡m1modj(n)modn≡mkj(n)+1modngcd(m,n)=1mj(n)≡1modn—欧拉定理mkj(n)≡1modnmkj(n)+1≡mmodngcd(m,n)≠1m是p的倍数或q的倍数，设m=cp，gcd(m,q)=1,mj(

3、q)≡1modq，mkj(q)≡1modq，[mkj(q)]j(p)≡1modqmkj(n)≡1modq，存在一整数r，使mkj(n)≡1＋rq两边同乘m=cp,mkj(n)+1≡m+rcpq=m+rcn,即mkj(n)+1≡mmodn39选p=7，q=17。求n=p×q=119，φ(n)=(p-1)(q-1)=96。取e=5，满足1

4、程得密文为c≡195mod119≡2476099mod119≡66解密为6677mod119≡19例题40用RSA算法加密与解密的过程：例：明文=“RSAALGORITHM”(1)明文用数字表示空白=00，A=01,B=02,…,Z=26(两位十进制数表示)1819010001120715180920081300(2)利用加密变换公式C=memodr,即C=18191223mod2867=27562756200105420669234704081815p=47,q=61,(n)=2760时，d=167n=2867e=122341RSA

5、算法实现如何判定一个给定的大整数是素数？已知d如何计算e，使e*d≡1modΦ(n)？如何计算C≡Memodn或M≡Cdmodn？42Miller-Rabin素性检验算法43求模逆元的扩展欧几里德算法44求模幂的模重复平方计算法求am，其中a，m是正整数：将m表示为二进制形式bkbk-1…b0，m=bk2k+bk-12k-1+…+b12+b045RSA的快速实现加密很快，指数小解密比较慢，指数较大利用中国剩余定理CRT，CRT对RSA解密算法生成两个解密方程（利用M=Cdmodpq）即:M1=Mmodp=(Cmodp)dmod(p-1)

6、modpM2=Mmodq=(Cmodq)dmod(q-1)modq解方程M=M1modpM=M2modq具有唯一解（利用CRT）46RSA的安全性RSA的安全性是基于分解大整数的困难性假定如果分解n=p×q，则立即获得(n)=(p－1)(q－1)，从而能够确定e的模(n)乘法逆d由n直接求(n)等价于分解nRSA-129历时8个月被于1996年4月被成功分解，RSA－130于1996年4月被成功分解密钥长度应该介于1024bit到2048bit之间4748RSA的安全性

7、p-q

8、要大p-1,q-1都应有大的素因子。e

9、/4,则d能被容易的确定。49作业6P601,3P641,2