RSA算法的數(shù)論基礎(chǔ).doc

ID:59252773

大?。?77.50 KB

頁數(shù):6頁

時間:2020-09-08

RSA算法的數(shù)論基礎(chǔ).doc_第1頁
RSA算法的數(shù)論基礎(chǔ).doc_第2頁
RSA算法的數(shù)論基礎(chǔ).doc_第3頁
RSA算法的數(shù)論基礎(chǔ).doc_第4頁
RSA算法的數(shù)論基礎(chǔ).doc_第5頁
資源描述:

《RSA算法的數(shù)論基礎(chǔ).doc》由會員上傳分享,免費在線閱讀,更多相關(guān)內(nèi)容在教育資源-天天文庫。

1、RSA算法的數(shù)論基礎(chǔ)一、公鑰密碼體制基礎(chǔ)一個好的密碼體系的必要條件是合法用戶能夠很容易對秘密消息進行加密和解密,而這些過程對于其他人則是非常難的。公鑰密碼體制的實現(xiàn)基于單向陷門函數(shù)。單向陷門函數(shù):設(shè)f是一個函數(shù),t是與f有關(guān)的一個參數(shù)。對于任意給定的x,計算y,使得y=f(x)是容易的。如果當(dāng)不知道參數(shù)t時,計算f的逆函數(shù)是難解的。但當(dāng)知道參數(shù)t時,計算f的逆函數(shù)是容易的。則稱f是一個單向陷門函數(shù),參數(shù)t稱為陷門。二、RSA算法的安全基礎(chǔ)計算機科學(xué)家Rivest、Shamir和Adleman提出

2、了基于素性檢測和整數(shù)分解的第一個使用公鑰密碼體制。算法的安全性建立這一數(shù)論難題基礎(chǔ)上:將兩個大素數(shù)相乘是容易計算的,而將該乘積分解成兩個大素數(shù)因子是困難的。素性檢測問題:檢測n的素性的最好額判定算法運行時間為,關(guān)于輸入長度呈超越多項式速度增長。整數(shù)因子分解問題:分解一個一般的整數(shù)n的最好的算法運行時間為,關(guān)于輸入長度呈亞指數(shù)速度增長。三、RSA算法實現(xiàn)的基礎(chǔ)定理算術(shù)基本定理:任何大于1的整數(shù)n能被因式分解為如下唯一形式:n=p1p2…pl(p1,p2,…,pl為素數(shù))費馬小定理:若p是素數(shù),a與

3、p互素,則歐拉定理:歐拉函數(shù)表示不大于n且與n互素的正整數(shù)的個數(shù)。當(dāng)n是素數(shù),。,p,q均為素數(shù)時,則對于互素的a和n,有四、RSA算法的實現(xiàn)1.密鑰的產(chǎn)生①選兩個互異的大素數(shù)p和q。②計算n=p×q,φ(n)=(p-1)(q-1),其中φ(n)是n的歐拉函數(shù)值。③選一隨機整數(shù)e,滿足1

4、}為秘密鑰。2.加密加密時首先將明文比特串分組,使得每個分組對應(yīng)的十進制數(shù)小于n,即分組長度小于。然后對每個明文m,作加密運算:3.解密對密文分組的解密運算為:五、證明RSA算法中解密過程的正確性設(shè)p,q是不同的素數(shù),n=pq記φ(n)=(p-1)(q-1),如果e,d是與φ(n)互素的兩個正整數(shù)(e,d<φ(n)),并滿足ed≡1(modφ(n)),則對于每個整數(shù)x,都有。分析:為了證明,只要證明φ(n)是的因數(shù)即可。又因為n=pq,而p,q都是素數(shù),故只要證明p和q都是的因數(shù)即可,即(1)(

5、2)證明:證明式1,若p是x的因數(shù)則式1必然成立若p不是x的因數(shù),則由ed≡1(modφ(n))得ed-1=k(p-1)(q-1),k為任意整數(shù)則根據(jù)費馬小定理因為x與p互素所以所以同理可證即證六、RSA算法中的計算問題1.模運算性質(zhì)RSA的加密、解密過程的運算都為求一個整數(shù)的整數(shù)次冪,再取模。如果按其含義直接計算,則中間結(jié)果非常大,有可能超出計算機所允許的整數(shù)取值范圍。而用模運算的性質(zhì):(a×b)modn=[(amodn)×(bmodn)]modn就可減小中間結(jié)果。2.模重復(fù)平方計算法例如求,

6、直接計算的話需做15次乘法。然而如果重復(fù)對每個部分結(jié)果做平方運算即求x,,,,則只需4次乘法。3、乘法逆元的求法(歐幾里德算法)整數(shù)e,滿足1

7、bin素性檢驗:給定奇整數(shù)和安全參數(shù)k寫,其中t為奇整數(shù)1.隨機選取整數(shù)b,2.計算3.(a)如果或,則通過檢驗,可能為素數(shù)?;氐?.繼續(xù)選取另一個隨機整數(shù)b,(b)否則,有以及,計算4.(a)如果,則通過檢驗,可能為素數(shù)?;氐?.繼續(xù)選取另一個隨機整數(shù)b,(b)否則,有,計算如此繼續(xù)下去。需要檢測多少個隨機整數(shù)(特定)才能找到一個素數(shù)。定義為不超過x的素數(shù)的個數(shù),素數(shù)定理:在1~x中隨機選取一個整數(shù),其為素數(shù)的概率大約為1/Inx。八、因子分解分解任意正整數(shù)n是,要尋找n的一個非平凡因子。對R

8、SA的公開模數(shù)n,找到其任意一個非平凡因子即意味這徹底分解n和該RSA密碼的破解。舉例Pollardp-1分解算法:1.選擇一個界B2.選擇一個整數(shù)k,k是大部分b的乘積滿足3.選擇一個隨機整數(shù)4.計算5.計算d=gcd(r-1,n)6.如果1

當(dāng)前文檔最多預(yù)覽五頁,下載文檔查看全文

此文檔下載收益歸作者所有

當(dāng)前文檔最多預(yù)覽五頁,下載文檔查看全文
溫馨提示:
1. 部分包含數(shù)學(xué)公式或PPT動畫的文件,查看預(yù)覽時可能會顯示錯亂或異常,文件下載后無此問題,請放心下載。
2. 本文檔由用戶上傳,版權(quán)歸屬用戶,天天文庫負(fù)責(zé)整理代發(fā)布。如果您對本文檔版權(quán)有爭議請及時聯(lián)系客服。
3. 下載前請仔細(xì)閱讀文檔內(nèi)容,確認(rèn)文檔內(nèi)容符合您的需求后進行下載,若出現(xiàn)內(nèi)容與標(biāo)題不符可向本站投訴處理。
4. 下載文檔時可能由于網(wǎng)絡(luò)波動等原因無法下載或下載錯誤,付費完成后未能成功下載的用戶請聯(lián)系客服處理。
关闭