RSA演算法
- RSA演算法流程
- 1.產生密鑰
- 2.分組
- 加密
- 解密
- 實體
- RSA演算法的計算問題
- 加密和解密中的計算
- 密鑰產生程序的計算問題
- 改進的RSA演算法
- RSA的安全性
- RSA的攻擊
- 1.共模攻擊
- 2.低指數攻擊
RSA演算法流程
RSA演算法是迄今為止理論上最為成熟的公鑰密碼體制，并且已經得到廣泛的應用，
1.產生密鑰
產生密鑰的程序如下：
- 選擇兩個保密的大素數P和q
- 計算n=p×q，φ(n)=(p-1)(q-1)
- 選擇公鑰e，e∈(1,φ(n))范圍內的一個整數，且gcd(φ(n),e)=1
- 計算密鑰d，d·e≡1 mod φ(n)，即d≡e-1 mod φ(n)
- 以{e,n}為公鑰，{d,n}為私鑰
2.分組
將明文位元串分組，使得每個分組對應的十進制數小于n，即分組長度小于log2n
加密
對每個明文分組m，作加密運算：
解密
對密文分組的解密運算如下：
實體
這里以未分組的問題進行示例：
對于分組問題，當加密的時候，需要補零則在后面進行補零操作；解密時需要補0，則在每個分組前面進行補零操作
RSA演算法的計算問題
加密和解密中的計算
RSA演算法的加密和解密程序都為求一個整數的整數次冪再取模的運算，因此可能有如下問題：
1.中間結果非常大，超出計算機的整數取值范圍，
2.指數的運算很復雜
針對不同的問題有不同的解決方法：
1.針對問題1，可以合理運用模運算的性質：
2.針對問題2，可以通過如下變形提高指數運算的有效性，減少運算次數，
基于該思想有快速指數演算法如下：
應用解決方法的具體示例：
問題：求7560 mod 561.
解：將560協程二進制形式為1000110000，應用快速指數演算法的結果為：
密鑰產生程序的計算問題
密鑰產生程序中的計算問題主要是大素數的確定問題：
產生密鑰時，需要考慮兩個大素數p、q的選取，以及e的選取和d的計算，因為n=pq在體制中是公開的，因此為了防止敵手通過窮搜索發現p、q的值，這兩個素數應該是在一個足夠大的整數集合中選取的大數，且RSA演算法的優越性和有效地尋找大素數有密切聯系，
尋找大素數一般先隨機選取一個大的奇數(如用偽亂數產生器)，然后用素性檢驗演算法檢驗選擇的奇數是否是素數，若不是，則選取另一大奇數，直到滿足條件為止，后續作業可由Euclid演算法完成
改進的RSA演算法
改進的RSA演算法是利用中國剩余定理來提高解密運算的速度，其解密程序如下：
由中國剩余定理，有解：
且已經表明，改進后的演算法可以很大程度上減少解密運算時間
RSA的安全性
RSA的安全性是基于分解大整數的困難性假定，
且能夠證明由n直接確定n的歐拉函式等價于對n的分解，
因此RSA的安全性對密鑰的選取提出了大小的注意，除此還對p和q提出了以下要求：
1.|p-q|要大
2.p、q的選取要保證能使t很大，才能抵抗重復加密攻擊
RSA的攻擊
RSA由于引數選擇不當會存在一下兩種攻擊
1.共模攻擊
共模攻擊就是指由于模數相同從而容易造成的攻擊方法，可通過給用戶設定不同的模數來進行抵抗
2.低指數攻擊
低指數攻擊是指用戶的加密指數很小，攻擊者利用中國剩余定理從而求解出m的攻擊方法
轉載請註明出處，本文鏈接：https://www.uj5u.com/qukuanlian/304387.html
標籤：區塊鏈