1、RSA RSA 算法及平安性分析算法及平安性分析數(shù)論簡介數(shù)論簡介模運算模運算o設設n n是一正整數(shù)是一正整數(shù),a ,a是整數(shù)是整數(shù), ,假設假設o a=qn+r, 0rn, a=qn+r, 0rn, 那么那么a mod n=ra mod n=ro假設假設(a mod n)=(b mod n),(a mod n)=(b mod n),稱為稱為a,ba,b模模n n同同余，記為余，記為ab mod nab mod no稱與稱與a a模模n n同余的數(shù)的全體為同余的數(shù)的全體為a a的同余類，的同余類，記為記為aa，a a稱為這個同余類的代表元素稱為這個同余類的代表元素 模運算模運算o同余的性質(zhì)同余的

2、性質(zhì)o假設假設n|(a-b)n|(a-b)，那么，那么ab mod nab mod no(a mod n) (b mod n),(a mod n) (b mod n),那么那么ab mod nab mod noab mod nab mod n，那么，那么ba mod nba mod noab mod nab mod n， bc mod n bc mod n，那么，那么ac ac mod nmod no求余運算求余運算a mod na mod n將將a a映射到集合映射到集合0,1,n-0,1,n-1,1,求余運算稱為模運算求余運算稱為模運算模運算模運算o模運算的性質(zhì)模運算的性質(zhì)o(a mod

3、n)+(b mod n) mod n=(a+b) mod n(a mod n)+(b mod n) mod n=(a+b) mod no(a mod n)-(b mod n) mod n=(a-b) mod n(a mod n)-(b mod n) mod n=(a-b) mod no(a mod n)(a mod n)(b mod n) mod n=(a(b mod n) mod n=(ab) mod nb) mod n模運算模運算o例：例：Z8=0,1,2,3,4,5,6,7,Z8=0,1,2,3,4,5,6,7,模模8 8加法和乘法加法和乘法01234567001234567112345

4、67022345670133456701244567012355670123466701234577012345601234567000000000101234567202460246303614725404040404505274163606420642707654321模運算模運算o假設假設x+y=0 mod n, yx+y=0 mod n, y為為x x的加法逆元。每的加法逆元。每一元素都有加法逆元一元素都有加法逆元o假設對假設對x x，有，有xy=1 mod nxy=1 mod n，稱，稱y y為為x x的乘法的乘法逆元。在上例中，并非一切逆元。在上例中，并非一切x x都有乘法逆都有乘

5、法逆元元o定義定義Zn=0,1,.,n-1Zn=0,1,.,n-1為模為模n n的同余類集合。的同余類集合。模運算模運算oZnZn上模運算的性質(zhì)上模運算的性質(zhì)o交換律交換律 o x+w) mod n=(w+x) mod nx+w) mod n=(w+x) mod no (x (xw) mod n=(ww) mod n=(wx) mod nx) mod no結(jié)合律結(jié)合律o (x+w)+y mod n=x+(w+y) mod n (x+w)+y mod n=x+(w+y) mod no (x (xw) w) y mod n=xy mod n=x(w(wy) mod ny) mod no分配律分配律

6、o w w(x+y) mod n=w(x+y) mod n=wx+wx+wy) mod ny) mod n模運算模運算n單位元單位元n (0+w) mod n=w mod n (0+w) mod n=w mod nn (1 (1w) mod n=w mod nw) mod n=w mod nn加法逆元：對加法逆元：對wZn,wZn,有有zZnzZn，滿足，滿足w+z=0 mod n, zw+z=0 mod n, z為為ww的加法逆元，記為的加法逆元，記為z=-wz=-w。n加法的可約律加法的可約律n (a+b)(a+c) mod n, (a+b)(a+c) mod n, 那么那么bc mod

7、nbc mod nn 對乘法不一定成立，由于乘法逆元不一對乘法不一定成立，由于乘法逆元不一定存在。定存在。模運算模運算o定理定理: :設設aZn,gcd(a,n)=1,aZn,gcd(a,n)=1,那么那么a a在在ZnZn有有逆元逆元o 證明思緒：證明思緒：o用反證法證明用反證法證明a a和和ZnZn中任何兩個不同的中任何兩個不同的數(shù)相乘結(jié)果都不一樣數(shù)相乘結(jié)果都不一樣o從從1 1得出得出a aZn=Zn,Zn=Zn,因此存在因此存在xZn,xZn,使使a ax=1 mod nx=1 mod no設設p p為素數(shù)，為素數(shù)，ZpZp中每一個非零元素都與中每一個非零元素都與p p互素，因此有乘法逆

8、元，有乘法可約律互素，因此有乘法逆元，有乘法可約律o (a (ab)=(ab)=(ac) mod n, b=c mod nc) mod n, b=c mod n中國剩余定理中國剩余定理o假設知某個數(shù)關于一些量量互素的數(shù)的同余類集，就假設知某個數(shù)關于一些量量互素的數(shù)的同余類集，就可以重構(gòu)這個數(shù)可以重構(gòu)這個數(shù)o定理定理(中國剩余定理中國剩余定理)：o 設設m1,m2,mk是兩兩互素的正整數(shù)，是兩兩互素的正整數(shù)， o 那么一次同余方程組那么一次同余方程組o 對模對模M有獨一解有獨一解 kiimM1 kkamxamxamxmodmodmod2211iiiikkkmemMeMaemMaemMaemMxm

9、od1 滿足mod)(222111中國剩余定理o中國剩余定理可以將一個很大的數(shù)中國剩余定理可以將一個很大的數(shù)x表示為一組表示為一組較小的數(shù)較小的數(shù)(a1,ak)o例：例：x1 mod 2, x2 mod 3, x3 mod 5 x5 mod 7,求求xo解：解：M2357210，M1=105, M2=70, M3=42, M4=30, (Mi=M/mi),可以求得可以求得e1=1, e2=1, e3=3, e4=4,所以所以x=10511701242333045 mod 210173費爾瑪定理和歐拉定理費爾瑪定理和歐拉定理o費爾瑪定理費爾瑪定理o 假設假設p p是素數(shù)，是素數(shù)，a a是正整數(shù)且

10、是正整數(shù)且gcd(a,p)=1gcd(a,p)=1，那么，那么ap-11 ap-11 mod pmod po證明：證明：o gcd(a,p)=1, gcd(a,p)=1,那么那么a aZp=Zp, aZp=Zp, a(Zp-0)=Zp-0(Zp-0)=Zp-0o a mod p,2a mod p,(n-1)a mod p =0,1,p-1 a mod p,2a mod p,(n-1)a mod p =0,1,p-1o (a mod p) (a mod p) (2a mod p) (2a mod p) (n-1)a mod p=(p-1)! mod p(n-1)a mod p=(p-1)! mo

11、d po (p-1)! (p-1)! ap-1=(p-1)! mod pap-1=(p-1)! mod po (p-1)! (p-1)!與與p p互素，所以乘法可約律，互素，所以乘法可約律，ap-1=1 mod pap-1=1 mod p費爾瑪定理和歐拉定理費爾瑪定理和歐拉定理o歐拉函數(shù)歐拉函數(shù)o設設n n為一正整數(shù)，小于為一正整數(shù)，小于n n且與且與n n互素的正整互素的正整數(shù)的個數(shù)稱為數(shù)的個數(shù)稱為n n的歐拉函數(shù)，記為的歐拉函數(shù)，記為(n)(n)o定理：假設定理：假設n n是兩個素數(shù)是兩個素數(shù)p p和和q q的乘積，那的乘積，那么么(n)(n) (p) (q)=(p-1)(q-1) (p)

12、 (q)=(p-1)(q-1)o歐拉定理歐拉定理o假設假設a a和和n n互素互素, ,那么那么a(n)= 1 mod na(n)= 1 mod n離散對數(shù)o求模下的整數(shù)冪求模下的整數(shù)冪o根據(jù)歐拉定理，假設根據(jù)歐拉定理，假設gcd(a,n)=1,那么那么af(n) 1 mod n。思索普通。思索普通am 1 mod n, 假設假設a,n互素，至少有一個整數(shù)互素，至少有一個整數(shù)m滿足這一方滿足這一方程。稱滿足這一方程的最小正整數(shù)程。稱滿足這一方程的最小正整數(shù)m為模為模n下下a的階。的階。o例：例：a=7,n=19. 71 7 mod 19, 72 11 mod 19, 73 1 mod 19,所

13、以所以7模模19的階的階為為3。從冪次為。從冪次為4開場出現(xiàn)循環(huán)，循環(huán)周期開場出現(xiàn)循環(huán)，循環(huán)周期與元素的階一樣與元素的階一樣RSA算法的實現(xiàn)算法的實現(xiàn) 實現(xiàn)的步驟如下：實現(xiàn)的步驟如下：Bob為實現(xiàn)者為實現(xiàn)者 (1) Bob尋覓出兩個大素數(shù)尋覓出兩個大素數(shù)p和和q (2) Bob計算出計算出n=pq 和和(n)=(p-1)(q-1) (3) Bob選擇一個隨機數(shù)選擇一個隨機數(shù)e (0e (n)，滿足，滿足(e,(n)=1 (4) Bob運用輾轉(zhuǎn)相除法計算運用輾轉(zhuǎn)相除法計算d=e-1(mod(n) (5) Bob在目錄中公開在目錄中公開n和和e作為公鑰作為公鑰密碼分析者攻擊密碼分析者攻擊RSA體制

14、的關鍵點在于如何分解體制的關鍵點在于如何分解n。假設。假設分分解勝利使解勝利使n=pq，那么可以算出，那么可以算出(n)p-1)(q-1)，然后，然后由公由公開的開的e，解出的，解出的dRSA算法編制算法編制 參數(shù)參數(shù)T=N；私鑰私鑰SK=D；公鑰公鑰PK=E； 設：明文設：明文M，密文，密文C，那么：，那么： 用公鑰作業(yè)：用公鑰作業(yè)：ME mod N = C 用私鑰作業(yè)：用私鑰作業(yè)：CD mod N = M解密正確性證明解密正確性證明ocd mod n med mod n m1 modj(n) mod n mkj(n)+1 mod nom與n互素，由歐拉定理o mj(n)1 mod n, m

15、kj(n)1 mod n, mkj(n)+1m mod nogcd(m,n) 1,m是p的倍數(shù)或q的倍數(shù)，設m=cp，此時gcd(m,q)=1,由歐拉定理， mj(q)1 mod q， mkj(q)1 mod q， mkj(q) j(p)1 mod q mkj(n)1 mod q，存在一整數(shù)r，使mkj(n)1rqo 兩邊同乘m=cp, mkj(n)+1m+rcpq=m+rcn,即mkj(n)+1m mod nRSA算法舉例算法舉例RSA算法的平安性分析算法的平安性分析密碼分析者攻擊密碼分析者攻擊RSA體制的關鍵點在于如何分解體制的關鍵點在于如何分解n假設分解勝利使假設分解勝利使n=pq，那么

16、可以算出，那么可以算出(n)p-1)(q-1)，然后由公開的，然后由公開的e，解出的，解出的d假設使假設使RSA平安，平安，p與與q必為足夠大的素數(shù)，使分析必為足夠大的素數(shù)，使分析者沒有方法在多項式時間內(nèi)將者沒有方法在多項式時間內(nèi)將n分解出來分解出來 n取取1024位或取位或取2048位，這樣位，這樣p、q就應該取就應該取512位和位和1024位。位。RSA算法的平安性分析算法的平安性分析建議選擇建議選擇p和和q大約是大約是100位的十進制素數(shù)位的十進制素數(shù)模模n的長度要求至少是的長度要求至少是512比特比特EDI攻擊規(guī)范運用的攻擊規(guī)范運用的RSA算法中規(guī)定算法中規(guī)定n的長度為的長度為512至

17、至1024比特位之間，但必需是比特位之間，但必需是128的倍數(shù)的倍數(shù)國際數(shù)字簽名規(guī)范國際數(shù)字簽名規(guī)范ISO/IEC 9796中規(guī)定中規(guī)定n的長度位的長度位512比比特位特位密鑰大小 MIPS年 512比特 768比特1024比特2048比特43 1082 10113 10203 10RSA算法的平安性分析算法的平安性分析 為了抵抗現(xiàn)有的整數(shù)分解算法，對為了抵抗現(xiàn)有的整數(shù)分解算法，對RSA模模n的素因子的素因子p和和q還有如下要求即是強素數(shù)：還有如下要求即是強素數(shù)： (1) p-1 和和q-1分別含有大素因子分別含有大素因子p1和和q1 (2) P1-1和和q1-1分別含有大素因子分別含有大素因

18、子p2和和q2 (3) p+1和和q+1分別含有大素因子分別含有大素因子p3和和q3RSA算法的平安性分析算法的平安性分析其它參數(shù)的選擇要求：其它參數(shù)的選擇要求：(1) |p-q|很大，通常很大，通常 p和和q的長度一樣；的長度一樣；(2)p-1和和q-1的最大公因子要小；的最大公因子要??；(3)e的選擇；的選擇；(4)d的選擇；的選擇；(5)不要許多的用戶共用一個不要許多的用戶共用一個n。 定義 假設 modemNm 那么稱那么稱 m m 為為RSARSA的一個不動點。的一個不動點。 對對RSARSA的攻擊共模攻擊的攻擊共模攻擊o每一用戶有一樣的模數(shù)每一用戶有一樣的模數(shù)n no設用戶的公開密

19、鑰分別為設用戶的公開密鑰分別為e1,e2,e1,e2,且且e1,e2e1,e2互素，明文音訊互素，明文音訊為為m,m,密文為密文為o由于由于e1,e2)=1,e1,e2)=1,用歐幾里德算法可求用歐幾里德算法可求 r e1+s e2=1r e1+s e2=1假定假定r r為負數(shù)，從而可知由為負數(shù)，從而可知由EuclideanEuclidean算法可計算算法可計算 o(c1-1) -r (c1-1) -r c2s=m mod n c2s=m mod nnmcnmceemodmod2121對對RSARSA的攻擊低指數(shù)攻擊的攻擊低指數(shù)攻擊令網(wǎng)中三用戶的加密鑰令網(wǎng)中三用戶的加密鑰e e均選均選3 3，而有不同的模，而有不同的模n1, n2, n3n1, n2, n3，假設有一用戶將音訊假設有一用戶將音訊x x傳給三個用戶的密文分別為傳給三個用戶的密文分別為 y1=x 3 mod n1 x n1y1=x 3 mod n1 x n1 y2=x 3 mod n2 x n2 y2=x 3 mod n2 x n2 y3=x 3 mod n3 x n3 y3=x 3 mod n3 x n3 普通選普通選n1, n2, n3n1, n2, n3互素互素( (否那么，可求出公因子，而降低否那么，可求出公因子，