第18講rsa算法及安全性分析

1、RSA 算法及安全性分析1數(shù)論簡介2模運算設(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稱為這個同余類的代表元素 3模運算同余的性質(zhì)若n|(a-b)，則ab mod n(a mod n) (b mod n),則ab mod nab mod n，則ba mod nab mod n， bc mod n，則ac mod n求余運算a mod n將a映射到集合0,1,n-1,求余運算稱為模運算4模運算模運算的性質(zhì)(a mod n)+(b mod

2、 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 n5模運算例：Z8=0,1,2,3,4,5,6,7,模8加法和乘法01234567001234567112345670223456701334567012445670123556701234667012345770123456012345670000000001012345672024602463036147254040404045052741636064206427076543216模運算若x+y=0 mod

3、n, y為x的加法逆元。每一元素都有加法逆元若對x，有xy=1 mod n，稱y為x的乘法逆元。在上例中，并非所有x都有乘法逆元定義Zn=0,1,.,n-1為模n的同余類集合。7模運算Zn上模運算的性質(zhì)交換律 （x+w) mod n=(w+x) mod n (xw) mod n=(wx) 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 n8模運算單位元 (0+w) mod n=w mod n (1w) mod n=w mod n加法逆元：對wZn,有zZn，滿足w+

4、z=0 mod n, z為w的加法逆元，記為z=-w。加法的可約律 (a+b)(a+c) mod n, 則bc mod n 對乘法不一定成立，因為乘法逆元不一定存在。9模運算定理:設(shè)aZn,gcd(a,n)=1,則a在Zn有逆元 證明思路：用反證法證明a和Zn中任何兩個不同的數(shù)相乘結(jié)果都不相同從1得出aZn=Zn,因此存在xZn,使ax=1 mod n設(shè)p為素數(shù)，Zp中每一個非零元素都與p互素，因此有乘法逆元，有乘法可約律 (ab)=(ac) mod n, b=c mod n10中國剩余定理如果已知某個數(shù)關(guān)于一些量量互素的數(shù)的同余類集，就可以重構(gòu)這個數(shù)定理(中國剩余定理)： 設(shè)m1,m2,mk

5、是兩兩互素的正整數(shù)， 則一次同余方程組 對模M有唯一解 11中國剩余定理中國剩余定理可以將一個很大的數(shù)x表示為一組較小的數(shù)(a1,ak)例：x1 mod 2, x2 mod 3, x3 mod 5 x5 mod 7,求x解：M2357210，M1=105, M2=70, M3=42, M4=30, (Mi=M/mi),可以求得e1=1, e2=1, e3=3, e4=4,所以x=10511701242333045 mod 21017312費爾瑪定理和歐拉定理費爾瑪定理 若p是素數(shù)，a是正整數(shù)且gcd(a,p)=1，則ap-11 mod p證明： gcd(a,p)=1,則aZp=Zp, a(Zp

6、-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互素，所以乘法可約律，ap-1=1 mod p13費爾瑪定理和歐拉定理歐拉函數(shù)設(shè)n為一正整數(shù)，小于n且與n互素的正整數(shù)的個數(shù)稱為n的歐拉函數(shù)，記為(n)定理：若n是兩個素數(shù)p和q的乘積，則(n) (p) (q)=(p-1)(q-1)歐拉定理若a和n互素,則a(n)= 1 mod n14離散對數(shù)求模下的整數(shù)冪根據(jù)歐拉定理，若gcd(a,n)=1

7、,則af(n) 1 mod n?？紤]一般am 1 mod n, 如果a,n互素，至少有一個整數(shù)m滿足這一方程。稱滿足這一方程的最小正整數(shù)m為模n下a的階。例：a=7,n=19. 71 7 mod 19, 72 11 mod 19, 73 1 mod 19,所以7模19的階為3。從冪次為4開始出現(xiàn)循環(huán)，循環(huán)周期與元素的階相同15RSA算法的實現(xiàn) 實現(xiàn)的步驟如下：Bob為實現(xiàn)者 (1) Bob尋找出兩個大素數(shù)p和q (2) Bob計算出n=pq 和(n)=(p-1)(q-1) (3) Bob選擇一個隨機數(shù)e (0e (n)，滿足(e,(n)=1 (4) Bob使用輾轉(zhuǎn)相除法計算d=e-1(mod(

8、n) (5) Bob在目錄中公開n和e作為公鑰密碼分析者攻擊RSA體制的關(guān)鍵點在于如何分解n。若分解成功使n=pq，則可以算出(n)（p-1)(q-1)，然后由公開的e，解出秘密的d16RSA算法編制 參數(shù)T=N；私鑰SK=D；公鑰PK=E； 設(shè)：明文M，密文C，那么： 用公鑰作業(yè)：ME mod N = C 用私鑰作業(yè)：CD mod N = M17解密正確性證明cd mod n med mod n m1 modj(n) mod n mkj(n)+1 mod nm與n互素，由歐拉定理 mj(n)1 mod n, mkj(n)1 mod n, mkj(n)+1m mod ngcd(m,n) 1,m

9、是p的倍數(shù)或q的倍數(shù)，設(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)1rq 兩邊同乘m=cp, mkj(n)+1m+rcpq=m+rcn,即mkj(n)+1m mod n18RSA算法舉例設(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;計算d, ( d*e) mod 96=1; d=77; 私鑰sk=77;設(shè):明文m=19 加

10、密：（19）5 mod 119 = 66 脫密：（66）77 mod 119 = 1919RSA算法的安全性分析密碼分析者攻擊RSA體制的關(guān)鍵點在于如何分解n若分解成功使n=pq，則可以算出(n)（p-1)(q-1)，然后由公開的e，解出秘密的d若使RSA安全，p與q必為足夠大的素數(shù)，使分析者沒有辦法在多項式時間內(nèi)將n分解出來 n取1024位或取2048位，這樣p、q就應(yīng)該取512位和1024位。20RSA算法的安全性分析建議選擇p和q大約是100位的十進制素數(shù)模n的長度要求至少是512比特EDI攻擊標(biāo)準(zhǔn)使用的RSA算法中規(guī)定n的長度為512至1024比特位之間，但必須是128的倍數(shù)國際數(shù)字簽

11、名標(biāo)準(zhǔn)ISO/IEC 9796中規(guī)定n的長度位512比特位21 如果用MIPS年表示每秒鐘執(zhí)行一百萬條指令的計算機計算一年時間的計算量，下表給出了不同比特的整數(shù)的因子分解所需的時間。 22RSA算法的安全性分析 為了抵抗現(xiàn)有的整數(shù)分解算法，對RSA模n的素因子p和q還有如下要求（即是強素數(shù)）： (1) p-1 和q-1分別含有大素因子p1和q1 (2) P1-1和q1-1分別含有大素因子p2和q2 (3) p+1和q+1分別含有大素因子p3和q323RSA算法的安全性分析其它參數(shù)的選擇要求：(1) |p-q|很大，通常 p和q的長度相同；(2)p-1和q-1的最大公因子要??；(3)e的選擇；(

12、4)d的選擇；(5)不要許多的用戶共用一個n。24不動點分析 定義 如果 則稱 m 為RSA的一個不動點。 25 (1) 此時的密文就是明文，因而直接暴露了明文。(2) 利用不動點m可能分解大合數(shù)N。26對RSA的攻擊共模攻擊每一用戶有相同的模數(shù)n設(shè)用戶的公開密鑰分別為e1,e2,且e1,e2互素，明文消息為m,密文為因為（e1,e2)=1,用歐幾里德算法可求 r e1+s e2=1假定r為負(fù)數(shù)，從而可知由Euclidean算法可計算 (c1-1) -r c2s=m mod n27對RSA的攻擊低指數(shù)攻擊令網(wǎng)中三用戶的加密鑰e均選3，而有不同的模n1, n2, n3，若有一用戶將消息x傳給三個用戶的密文分別為 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，可得x3nb，為了使脫密正常進行，應(yīng)該先加密還是先簽名？29平方乘算法30P-1因子分解算法31素性檢驗引理：如果p為大于2的素數(shù)，則方程x21 mod p的解只有和x1和x-1證明: x21 mod