RSA算法及安全性分析

1、RSA 算法及安全性分析,數(shù)論簡介,模運(yùn)算,設(shè)n是一正整數(shù),a是整數(shù),若 a=qn+r, 0rn, 則a mod n=r 若(a mod n)=(b mod n),稱為a,b模n同余，記為ab mod n 稱與a模n同余的數(shù)的全體為a的同余類，記為a，a稱為這個(gè)同余類的代表元素,模運(yùn)算,同余的性質(zhì) 若n|(a-b)，則ab mod n (a mod n) (b mod n),則ab mod n ab mod n，則ba mod n ab mod n， bc mod n，則ac mod n 求余運(yùn)算a mod n將a映射到集合0,1,n-1,求余運(yùn)算稱為模運(yùn)算,模運(yùn)算,模運(yùn)算的性質(zhì) (a mod

2、 n)+(b mod n) mod n=(a+b) mod n (a mod n)-(b mod n) mod n=(a-b) mod n (a mod n)(b mod n) mod n=(ab) mod n,模運(yùn)算,例：Z8=0,1,2,3,4,5,6,7,模8加法和乘法,模運(yùn)算,若x+y=0 mod n, y為x的加法逆元。每一元素都有加法逆元 若對x，有xy=1 mod n，稱y為x的乘法逆元。在上例中，并非所有x都有乘法逆元 定義Zn=0,1,.,n-1為模n的同余類集合,模運(yùn)算,Zn上模運(yùn)算的性質(zhì) 交換律 （x+w) mod n=(w+x) mod n (xw) mod n=(wx

3、) mod n 結(jié)合律 (x+w)+y mod n=x+(w+y) mod n (xw) y mod n=x(wy) mod n 分配律 w(x+y) mod n=wx+wy) mod n,模運(yùn)算,單位元 (0+w) mod n=w mod n (1w) mod n=w mod n 加法逆元：對wZn,有zZn，滿足w+z=0 mod n, z為w的加法逆元，記為z=-w。 加法的可約律 (a+b)(a+c) mod n, 則bc mod n 對乘法不一定成立，因?yàn)槌朔嬖灰欢ù嬖?模運(yùn)算,定理:設(shè)aZn,gcd(a,n)=1,則a在Zn有逆元 證明思路： 用反證法證明a和Zn中任何兩個(gè)不同

4、的數(shù)相乘結(jié)果都不相同 從1得出aZn=Zn,因此存在xZn,使ax=1 mod n 設(shè)p為素?cái)?shù)，Zp中每一個(gè)非零元素都與p互素，因此有乘法逆元，有乘法可約律 (ab)=(ac) mod n, b=c mod n,中國剩余定理,如果已知某個(gè)數(shù)關(guān)于一些量量互素的數(shù)的同余類集，就可以重構(gòu)這個(gè)數(shù) 定理(中國剩余定理)： 設(shè)m1,m2,mk是兩兩互素的正整數(shù)， 則一次同余方程組 對模M有唯一解,中國剩余定理,中國剩余定理可以將一個(gè)很大的數(shù)x表示為一組較小的數(shù)(a1,ak) 例：x1 mod 2, x2 mod 3, x3 mod 5 x5 mod 7,求x 解：M2357210，M1=105, M2=7

5、0, M3=42, M4=30, (Mi=M/mi),可以求得e1=1, e2=1, e3=3, e4=4,所以x=10511701242333045 mod 210173,費(fèi)爾瑪定理和歐拉定理,費(fèi)爾瑪定理 若p是素?cái)?shù)，a是正整數(shù)且gcd(a,p)=1，則ap-11 mod p 證明： gcd(a,p)=1,則aZp=Zp, a(Zp-0)=Zp-0 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=(p-1)! mod p (p-1)! ap-1=(p-1)! mod p (p-1)!與p互素，所

6、以乘法可約律，ap-1=1 mod p,費(fèi)爾瑪定理和歐拉定理,歐拉函數(shù) 設(shè)n為一正整數(shù)，小于n且與n互素的正整數(shù)的個(gè)數(shù)稱為n的歐拉函數(shù)，記為(n) 定理：若n是兩個(gè)素?cái)?shù)p和q的乘積，則(n) (p) (q)=(p-1)(q-1) 歐拉定理 若a和n互素,則a(n)= 1 mod n,離散對數(shù),求模下的整數(shù)冪 根據(jù)歐拉定理，若gcd(a,n)=1,則af(n) 1 mod n?？紤]一般am 1 mod n, 如果a,n互素，至少有一個(gè)整數(shù)m滿足這一方程。稱滿足這一方程的最小正整數(shù)m為模n下a的階。 例：a=7,n=19. 71 7 mod 19, 72 11 mod 19, 73 1 mod 1

7、9,所以7模19的階為3。從冪次為4開始出現(xiàn)循環(huán)，循環(huán)周期與元素的階相同,RSA算法的實(shí)現(xiàn),實(shí)現(xiàn)的步驟如下：Bob為實(shí)現(xiàn)者 (1) Bob尋找出兩個(gè)大素?cái)?shù)p和q (2) Bob計(jì)算出n=pq 和(n)=(p-1)(q-1) (3) Bob選擇一個(gè)隨機(jī)數(shù)e (0e (n)，滿足(e,(n)=1 (4) Bob使用輾轉(zhuǎn)相除法計(jì)算d=e-1(mod(n) (5) Bob在目錄中公開n和e作為公鑰 密碼分析者攻擊RSA體制的關(guān)鍵點(diǎn)在于如何分解n。若分 解成功使n=pq，則可以算出(n)（p-1)(q-1)，然后由公 開的e，解出秘密的d,RSA算法編制,參數(shù)T=N； 私鑰SK=D； 公鑰PK=E； 設(shè)

8、：明文M，密文C，那么： 用公鑰作業(yè)：ME mod N = C 用私鑰作業(yè)：CD mod N = M,解密正確性證明,cd mod n med mod n m1 modj(n) mod n mkj(n)+1 mod n m與n互素，由歐拉定理 mj(n)1 mod n, mkj(n)1 mod n, mkj(n)+1m mod n gcd(m,n) 1,m是p的倍數(shù)或q的倍數(shù)，設(shè)m=cp，此時(shí)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)1rq 兩邊同乘

9、m=cp, mkj(n)+1m+rcpq=m+rcn,即mkj(n)+1m mod n,RSA算法舉例,設(shè) p=7, q=17, n=7*17=119; 參數(shù)T=n=119; (n)=(7-1)(17-1)=96; 選擇e=5, gcd(5,96)=1; 公鑰pk=5; 計(jì)算d, ( d*e) mod 96=1; d=77; 私鑰sk=77; 設(shè):明文m=19 加密：（19）5 mod 119 = 66 脫密：（66）77 mod 119 = 19,RSA算法的安全性分析,密碼分析者攻擊RSA體制的關(guān)鍵點(diǎn)在于如何分解n 若分解成功使n=pq，則可以算出(n)（p-1)(q-1)，然后由公開的e

10、，解出秘密的d 若使RSA安全，p與q必為足夠大的素?cái)?shù)，使分析者沒有辦法在多項(xiàng)式時(shí)間內(nèi)將n分解出來 n取1024位或取2048位，這樣p、q就應(yīng)該取512位和1024位,RSA算法的安全性分析,建議選擇p和q大約是100位的十進(jìn)制素?cái)?shù) 模n的長度要求至少是512比特 EDI攻擊標(biāo)準(zhǔn)使用的RSA算法中規(guī)定n的長度為512至1024比特位之間，但必須是128的倍數(shù) 國際數(shù)字簽名標(biāo)準(zhǔn)ISO/IEC 9796中規(guī)定n的長度位512比特位,如果用MIPS年表示每秒鐘執(zhí)行一百萬條指令的計(jì)算機(jī)計(jì)算一年時(shí)間的計(jì)算量，下表給出了不同比特的整數(shù)的因子分解所需的時(shí)間,RSA算法的安全性分析,為了抵抗現(xiàn)有的整數(shù)分解算

11、法，對RSA模n的素因子p和q還有如下要求（即是強(qiáng)素?cái)?shù)）： (1) p-1 和q-1分別含有大素因子p1和q1 (2) P1-1和q1-1分別含有大素因子p2和q2 (3) p+1和q+1分別含有大素因子p3和q3,RSA算法的安全性分析,其它參數(shù)的選擇要求： (1) |p-q|很大，通常 p和q的長度相同； (2)p-1和q-1的最大公因子要?。?(3)e的選擇； (4)d的選擇； (5)不要許多的用戶共用一個(gè)n,不動點(diǎn)分析,定義 如果,則稱 m 為RSA的一個(gè)不動點(diǎn),1) 此時(shí)的密文就是明文，因而直 接暴露了明文,2) 利用不動點(diǎn)m可能分解大合數(shù)N,對RSA的攻擊共模攻擊,每一用戶有相同的

12、模數(shù)n 設(shè)用戶的公開密鑰分別為e1,e2,且e1,e2互素，明文消息為m,密文為 因?yàn)椋╡1,e2)=1,用歐幾里德算法可求 r e1+s e2=1假定r為負(fù)數(shù)，從而可知由Euclidean算法可計(jì)算 (c1-1) -r c2s=m mod n,對RSA的攻擊低指數(shù)攻擊,令網(wǎng)中三用戶的加密鑰e均選3，而有不同的模n1, n2, n3，若有一用戶將消息x傳給三個(gè)用戶的密文分別為 y1=x 3 mod n1 x n1 y2=x 3 mod n2 x n2 y3=x 3 mod n3 x n3 一般選n1, n2, n3互素(否則，可求出公因子，而降低安全性)，利用中國余定理，可從y1, y2, y3求出 y=x 3 mod (n1 n2 n3)。 由xn1, xn2, xn3，可得x3 n1 n2, n3，故有,習(xí)題,在用戶a對用戶b利用RSA公鑰密碼體制進(jìn)行消息的加密簽名時(shí)，若二者使用的模數(shù)nanb，為了使脫密正常進(jìn)行，應(yīng)該先加密還是先簽名,平方乘算法,P-1因子分解算法,素性檢驗(yàn),引理：如果p為大于2的素?cái)?shù)，則方程x21 mod p的解只有和x1和x-1 證明: x21 mod p