如何理解加密算法RSA

本篇內容介紹了“如何理解加密算法RSA”的有關知識，在實際案例的操作過程中，不少人都會遇到這樣的困境，接下來就讓小編帶領大家學習一下如何處理這些情況吧！希望大家仔細閱讀，能夠學有所成！

RSA加密

我們需要先預習一下還給數學老師的知識

歐拉函數

在數論中，存在正整數 n，小于n并且與n互質的正整數的數目稱為n的歐拉函數記著φ(n)。例如：

• φ(7) 7對應的比7小的與7互質的數有1、2、3、4、5、6共6個，因此φ(7)=6;

• φ(8) 8對應的比8小的與8互質的數有1，3，5，7共4個，因此φ(8)=4;

• φ(9) 9對應的比9小的與9互質的數有1，2，4，5，6，7，8共7個，，因此φ(9)=7。

通式(P是數N的質因數)

• φ(10)=10×(1-1/2)×(1-1/5)=4;

• φ(30)=30×(1-1/2)×(1-1/3)×(1-1/5)=8;

• φ(49)=49×(1-1/7)=42。

若m n互質：φ(n * m)=φ(n)* φ(m)，如果n為質數那么φ(n)=n-1。

分解質因數求值：φ(12)=φ(4 * 3)=φ( 2^2 * 3^1 )=( 2^2 - 2^1 ) * (3^1 - 3^0)=4。

歐拉定理

如果兩個正整數m和n互質，那么m的φ(n) 次方對n取余衡等于1。m^φ(n)%n≡1。

費馬小定理

存在一個質數p，而整數a不是p的倍數，則存在a^(p-1)%p≡1。費馬小定理是歐拉定理的特殊情況。因為φ(p)=p-1(任何數都與質數互質)。

模反元素

如果兩個正整數e和x互質，那么一定存在一個整數d，使得ed-1能夠被x整除，則稱d是e對x的模反元素。e * d % x≡1，那么e * d ≡  k*x+1。

由以上定理得出以下幾個公式：

1. m^φ(n)%n≡1

2. m^(k * φ(n))%n≡1 兩端同乘以m

3. m^(k * φ(n)+1)%n≡m

4. e * d≡k * x+1

5. m^e * d%n≡m 替換第3步k * φ(n)+1

而m^e*d%n≡m就是我們需要的一個非對稱加密的公式。m為明文，e和d分別對應的是公鑰私鑰。迪菲卡爾曼秘鑰交換對公式拆分：

• m^e%n=c 加密

• c^d%n=m 解密

其中c為通過e加密后的密文，然后通過d可以解出明文m。因此：

• 公鑰： e、n

• 秘鑰：d、n

• 明文：m

• 密文：c

RSA加密過程

1. 取兩個質數p1、p2;

2. 確定n值，n=p1 * p2，n值一般會很大長度一般為1024個二進制位;

3. 確定φ(n)，φ(n)=(p1-1) * (p2-1);

4. 確定e值，1

5. 確定d值，e*d%φ(n)=1;

6. 加密 c=m^e%n;

7. 解密m=c^d%n。

實際驗證：

1. p1=3， p2=7;

2. n=p1 * p2=3 * 7=21;

3. φ(n)=(p1-1) * (p2-1)=2*6=12;

4. 1

5. e * d % φ(n)=5 * d % 12=1，得d=17;

6. 設置明文m=3，則c = m^e % n = 3^5 % 21=12;

7. 解密密文m=c^d % n=12^17 % 21=3。

通過上面的講解我們知道在RSA 加密中用到的幾6個參數

p1  p2  n  φ(n)  e  d

這六個數字之中，公鑰用到了兩個(n和e)，其余四個數字都是不公開的。其中最關鍵的是d，因為n和d組成了私鑰，一旦d泄漏，就等于私鑰泄漏。

那么，有無可能在已知n和e的情況下，推導出d?

1. e*d%φ(n)=1 (只有知道e和φ(n)，才能算出d。)

2. φ(n)=(p1-1) * (p2-1) (只有知道p1和p2，才能算出φ(n)。)

3. n=p1*p2 (只有將n因數分解，才能算出p和q。)

結論：如果n可以被因數分解，d就可以算出，也就意味著私鑰被破解。

可是，大整數的因數分解，是一件非常困難的事情。目前，除了暴力破解，還沒有發現別的有效方法。維基百科這樣寫道：

"對極大整數做因數分解的難度決定了RSA算法的可靠性。換言之，對一極大整數做因數分解愈困難，RSA算法愈可靠。

假如有人找到一種快速因數分解的算法，那么RSA的可靠性就會極度下降。但找到這樣的算法的可能性是非常小的。今天只有短的RSA密鑰才可能被暴力破解。到2008年為止，世界上還沒有任何可靠的攻擊RSA算法的方式。

只要密鑰長度足夠長，用RSA加密的信息實際上是不能被解破的。"

或許你看到這里還不相信，我寫個程序挨著試 不就可以破解出來嗎?例如 21 你或許會很快的分解成 3×7 但是這個數再大一點 比如 這個質數  2^57,885,161-1 它有超過1千7百萬個數位 如果讓傳統計算機來驗證他是不是質數 估計可以跑到天荒地老。

“如何理解加密算法RSA”的內容就介紹到這里了，感謝大家的閱讀。如果想了解更多行業相關的知識可以關注億速云網站，小編將為大家輸出更多高質量的實用文章！