版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請進(jìn)行舉報(bào)或認(rèn)領(lǐng)
文檔簡介
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
溫馨提示
- 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 人人文庫網(wǎng)僅提供信息存儲空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負(fù)責(zé)。
- 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。
最新文檔
- 家電清洗行業(yè)合同模板
- 個(gè)人土方回填合同模板
- 家政職工合同模板
- 通道綠化施工合同模板
- 餐飲加盟店合同模板完整版
- 退伙合同模板
- 重大疾病合同模板
- 陽泉房屋租賃合同模板
- 門廠合同模板
- 酒吧物品供貨合同模板
- 電纜溝鋼板樁支護(hù)施工方案
- 公司轉(zhuǎn)款給另一個(gè)公司應(yīng)該有委托轉(zhuǎn)款函
- 農(nóng)民專業(yè)合作社成員名冊(模板)
- 部編版二年級上冊道德與法治第二單元 我們的班級 達(dá)標(biāo)測試卷及答案28
- 裝修工程提出的合理化建議
- 藥品采購供應(yīng)制度檢查表
- 如何做好一名責(zé)任護(hù)士ppt課件
- 通信線路畢業(yè)設(shè)計(jì)(論文):通信光纜線路維護(hù)
- 5索夫矩陣模型在觀眾拓展規(guī)劃中的運(yùn)用
- 管道縮寫代號.xlsx
- 2021年科室人材培養(yǎng)和人材梯隊(duì)建設(shè)計(jì)劃.doc
評論
0/150
提交評論