简化剩余类欧拉函数rsa省公开课一等奖全国示范课微课金奖

第三章(2)简化剩下类、欧拉函数及其应用、RSA第1页复习

第2页第3页第4页第5页第6页第7页第8页第9页第10页第11页第12页第13页第14页第15页剩下类及完全剩下系第16页第17页第18页第19页第20页第21页第22页§3简化剩下系与欧拉函数

第23页第24页第25页第26页第27页第28页第29页§4欧拉定理.费马定理及应用

第30页第31页第32页第33页公钥密码体制34第34页RSA算法概况MIT三位年青数学家R.L.Rivest，A.Shamir和L.Adleman等[1978,1979]发觉了一个用数论结构双钥方法，称作MIT体制，以后被广泛称之为RSA体制。它既可用于加密,又可用于数字签字。RSA算法安全性基于数论中大整数分解困难性。35第35页算法描述－密钥产生独立地选取两大素数p和q(各100～200位十进制数字)计算n=p×q，其欧拉函数值

(n)=(p－1)(q－1)

随机选一整数e，1

e<

(n)，gcd(

(n),e)=1在模

(n)下，计算e有逆元d=e-1mod

(n)以n，e为公钥；私钥为d。(p,q不再需要，能够销毁。)

加密将明文分组，各组对应十进制数小于nc=memodn解密

m=cd

modn36第36页解密正确性证实cd

modn≡med

modn≡m1

modj(n)

modn≡mkj(n)+1modngcd(m,n)=1

mj(n)≡1modn—欧拉定理mkj(n)≡1modnmkj(n)+1≡mmodngcd(m,n)≠1m是p倍数或q倍数，设m=cp，gcd(m,q)=1,

mj(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≡mmodn37第37页选p=7，q=17。求n=p×q=119，φ(n)=(p-1)(q-1)=96。取e=5，满足1<e<φ(n)，且gcd(φ(n),e)=1。确定满足d·e=1mod96且小于96d，因为77×5=385=4×96+1，所以d为77公开钥为{5，119}，秘密钥为{77}。设明文m=19，则由加密过程得密文为c≡195mod119≡2476099mod119≡66解密为6677mod119≡19例题38第38页用RSA算法加密与解密过程：例：明文=“RSAALGORITHM”(1)明文用数字表示空白=00，A=01,B=02,…,Z=26(两位十进制数表示)

181901000112071518091300(2)利用加密变换公式C=memodr,即C=18191223mod2867=2756

275605420669234704081815p=47,q=61,(n)=2760时，d=167n=2867e=122339第39页RSA算法实现怎样判定一个给定大整数是素数？已知d怎样计算e，使e*d≡1modΦ(n)？怎样计算C≡Memodn或M≡Cdmodn？40第40页Miller-Rabin素性检验算法

41第41页求模逆元扩展欧几里德算法

42第42页求模幂模重复平方计算法求am，其中a，m是正整数：将m表示为二进制形式bkbk-1…b0，m=bk2k+bk-12k-1+…+b12+b043第43页RSA快速实现加密很快，指数小解密比较慢，指数较大利用中国剩下定理CRT，CRT对RSA解密算法生成两个解密方程（利用M=Cdmodpq）即:M1=Mmodp=(Cmodp)dmod(p-1)

modp

M2=Mmodq=(Cmodq)dmod(q-1)modq解方程M=M1modpM=M2modq含有唯一解（利用CRT）44第44页RSA安全性RSA安全性是基于分解大整数困难性假定假如分解n=p×q，则马上取得

(n)=(p－1)(q－1)，从而能够确定e模

(n)乘法逆d由n直接求

(n)等价于分解nRSA-129历时8个月被于1996年4月被成功分解，RSA－130于1996年4月被成功分解密钥长度应该介于1024bit