中國剩余定理在RSA算法中應(yīng)用的研究實(shí)驗(yàn)演講PPT

1、主講：李雪飛中國剩余定理在中國剩余定理在RSARSA算算法中應(yīng)用的研究實(shí)驗(yàn)法中應(yīng)用的研究實(shí)驗(yàn) RSA 簽名是一種最常用的數(shù)字簽名方法。然而，RSA 算法中的大數(shù)的模冪運(yùn)算比較費(fèi)時(shí)，這一直是制約著RSA 發(fā)展的瓶頸。早期，人們建議使用較小的加密指數(shù)或解密指數(shù)以加快加密或解密( 簽名) 等基本運(yùn)算，但是，1990 年Wiener提出當(dāng)私鑰d 小于模數(shù)N1 /4 時(shí)，RSA 密碼系統(tǒng)是不安全的。2022年4月15日2中國剩余定理2022年4月15日3q孫子算經(jīng)中的題目：有物不知其數(shù)，三個(gè)一數(shù)余二，五個(gè)一數(shù)余三，七個(gè)一數(shù)又余二，問該物總數(shù)幾何？中國剩余定理q孫子算經(jīng)中的解法：三三數(shù)之，取數(shù)七十，與余數(shù)

2、二相乘；五五數(shù)之，取數(shù)二十一，與余數(shù)三相乘；七七數(shù)之，取數(shù)十五，與余數(shù)二相乘。將諸乘積相加，然后減去一百零五的倍數(shù)。中國剩余定理(CRT)3,4,5設(shè)p1,p2,ps是兩兩互素的正整數(shù),即GCD(pi,pj)=1(ij),對于任意整數(shù)d1,d2,ds(0dipi-1,i=1,2,s),同余式方程組 xd1(modp1)xd2(modp2)xds(modps)在0到N=pi內(nèi)有惟一解。2022年4月15日5中國剩余定理 根據(jù)高斯算法，中國剩余定理的解為X=(b1M1y1+b2M2y2+bkMkyk) mod N ，其中N=nln2nk ，Mi=N/ni=n1n2ni-1ni+1nk ，i=1,

3、2, k, yi滿足yi=Mi-1 mod ni。由此可見，中國剩余定理為對高位寬(如1024bit)大數(shù)的模冪運(yùn)算轉(zhuǎn)化成對低位寬(如512bit)相對較小的數(shù)進(jìn)行模冪運(yùn)算提供了可能。2022年4月15日6中國剩余定理用于中國剩余定理用于RSARSA2022年4月15日7基于中國剩余定理，RSA 模冪運(yùn)算可轉(zhuǎn)化為以下運(yùn)算過程：（1） 計(jì)算Cp=C mod p ，Cq=C mod q ；（2） 計(jì)算Mp=CpDp mod p ，Mq=CqDqmod q ；其中Dp=D mod (p-1)，Dq=D mod(q-1)，對于給定素?cái)?shù)p、q及密鑰而言是常數(shù)，可以預(yù)先計(jì)算出來。（3） 計(jì)算Sp=Mp(q

4、(p-1)mod N) mod N ，Sq=Mq(p(q-1) mod N) mod N ；其中，q(p-1)mod N 和p(q-1) mod N 是僅僅決定于素?cái)?shù)p、q 和模N 的常數(shù)，可以預(yù)先計(jì)算出來。（4） 計(jì)算M=(Sp + Sq) mod N中國剩余定理用于中國剩余定理用于RSARSA2022年4月15日8假定模數(shù)N 的二進(jìn)制長度為k，則其兩個(gè)素因子p和q的長度分別為k/2，出于安全性考慮，私鑰d的二進(jìn)制長度應(yīng)與模數(shù)N相當(dāng)，也為k。dp、dq、p-1 mod q、q-1mod p可預(yù)先計(jì)算好，二進(jìn)制長度均為k/2。從上述運(yùn)用中國剩余定理計(jì)算模冪的過程可知S 計(jì)算過程的主要工作花在計(jì)

5、算Cp 和Cq上，最后，一步合成C只是兩次乘法和一次加法運(yùn)算，在計(jì)算時(shí)間復(fù)雜度時(shí)可忽略不計(jì)。中國剩余定理用于中國剩余定理用于RSARSA2022年4月15日9使用傳統(tǒng)算法計(jì)算Cp 和Cq需要3/2*(k/2)次k/2比特的模乘運(yùn)算，總共需要s1=2*3/2*(k/2)*(k/2)2=3/8*k3次位操作。如果不用中國剩余定理，直接計(jì)算需要s2=3/2*k3次位操作。因此，使用中國剩余定理計(jì)算模冪乘比不使用大約快了4倍。四素?cái)?shù)RSA算法 在傳統(tǒng)雙素?cái)?shù)SA 密碼算法基礎(chǔ)上，把素?cái)?shù)個(gè)數(shù)取為4，算法依然成立，其描述如下: 1) 隨機(jī)選取4 個(gè)不同的大素?cái)?shù)p，q，r和s，計(jì)算n = pqrs， ( n)

6、 = ( p1)(q1)(r1)(s1)。 2) 取加密密鑰e = 65537，計(jì)算出私鑰d，滿足de1 mod( n) 。 3) 加密解密過程與傳統(tǒng)算法一樣，仍為: 加密算法c = E( m) me mod n 解密算法m = D( c) cd mod n2022年4月15日10中國剩余定理用于四素?cái)?shù)RSA算法 運(yùn)用中國剩余定理，對消息摘要D 的數(shù)字簽名可轉(zhuǎn)換為 以下運(yùn)算過程: 1) 計(jì)算mp = D mod p，mq = D mod q，mr = D mod r，ms = D mod s; 2) 計(jì)算dp = d mod ( p1)，dq = d mod ( q1)，dr =d mod (

7、 r1)，ds = d mod ( s1) ; 3) 計(jì)算M1 = mpdp mod p，M2 = mpdq mod q，M3 = mrdr mod r，M4 = msds mod s; 4) 計(jì)算S = ( M1( qrs) p1 + M2( prs) q1 + M3( pqs) r1 + M4( pqr) s1 ) mod n，即得出簽名S。2022年4月15日11四素?cái)?shù)RSA算法的復(fù)雜度 假定模數(shù)N 的二進(jìn)制長度為k，則其四個(gè)素因子p、q、r和s的長度分別為k/4，出于安全性考慮，私鑰d的二進(jìn)制長度應(yīng)與模數(shù)N相當(dāng)，也為k。dp、dq、dr、ds、p-1 mod qrs、q-1mod pr

8、s、r-1 mod pqs、s-1mod pqr可預(yù)先計(jì)算好，二進(jìn)制長度均為k/4。從上述運(yùn)用中國剩余定理計(jì)算模冪的過程可知S 計(jì)算過程的主要工作花在計(jì)算Cp 、Cq、Cr和Cs上，最后，一步合成C只是16次乘法和3次加法運(yùn)算，在計(jì)算時(shí)間復(fù)雜度時(shí)可忽略不計(jì)。使用傳統(tǒng)算法計(jì)算Cp 、Cq、Cr和Cs需要3/2*(k/4)次k/4比特的模乘運(yùn)算，總共需要s1=4*3/2*(k/4) *(k/4)2=3/16*k3次位操作。2022年4月15日12四素?cái)?shù)RSA算法2022年4月15日13RSA算法實(shí)現(xiàn)2022年4月15日14RSA算法實(shí)現(xiàn)2022年4月15日15 1 Yunfei Li,Qing L

9、iu,Tong Li. Design and Implementation of an Improved RSA AlgorithmJ,International Conference on E-Health Networking, Digital Ecosystems and Technologies ,2010,3903932 費(fèi)曉飛，胡捍英. CRT-RSA 算法安全性分析M.微計(jì)算機(jī)信息,2009.(1-3):37383 武濱，使用中國剩余定理提高RSA算法效率安全性分析及改進(jìn)方法J.網(wǎng)絡(luò)與安全技術(shù),2006,(3):7880.4 肖振久，胡馳，陳虹. 四素?cái)?shù)SA 數(shù)字簽名算法的研究與實(shí)現(xiàn)J.計(jì)算機(jī)應(yīng)用,2013,33(5):13741377.5 張宏，劉方園. 四素?cái)?shù)RSA 加密算法的研究與分析J.為計(jì)算機(jī)信息,2010,26(5-3):2930.6 李云飛，柳青，赫林，周保林. 一種有效的RSA 算法改進(jìn)方案J.計(jì)算機(jī)應(yīng)用,2010,30(9):23932397.7柳青,李云飛,周保林,彭華.基于多素?cái)?shù)的批處理RSA算法的研究J.計(jì)算機(jī)應(yīng)用研究2011.28(2):714-716 8 賀毅朝，劉建芹，陳維海. 中國剩余定理在RSA解密中的應(yīng)用J.河北省科學(xué)院學(xué)報(bào),200