加密和解密使用的是兩個不同的秘鑰，這種算法叫做非對稱加密。非對稱加密又稱為公鑰加密，RSA隻是公鑰加密的一種。

數字簽名 && 數字證書

現實生活中有簽名，互聯網中也存在簽名。簽名的作用有兩個，一個是身份驗證，一個是數據完整性驗證。數字簽名通過摘要算法來确保接收到的數據沒有被篡改，再通過簽名者的私鑰加密，隻能使用對應的公鑰解密，以此來保證身份的一緻性。

數字證書是将個人信息和數字簽名放到一起，經由CA機構的私鑰加密之後生成。當然，不經過CA機構，由自己完成簽名的證書稱為自簽名證書。CA機構作為互聯網密碼體系中的基礎機構，擁有相當高級的安全防範能力，所有的證書體系中的基本條件就是CA機構的私鑰不被竊取。

CA證書的生成過程如下：

證書參與信息傳遞完成加密和解密的過程如下：

歐拉函數

互質關系：互質是公約數隻有1的兩個整數，1和1互質，13和13就不互質了。 歐拉函數：表示任意給定正整數 n，在小于等于n的正整數之中，有多少個與 n 構成互質關系，其表達式為：

其中，若P為質數，則其表達式可以簡寫為：

情況一：φ(1)=1;

1和任何數都互質，所以φ(1)=1；

情況二：n 是質數， φ(n)=n-1;

因為 n 是質數，所以和小于自己的所有數都是互質關系，所以φ(n)=n-1；

情況三：如果 n 是質數的某一個次方，即 n = p^k ( p 為質數，k 為大于等于1的整數)，則φ(n)=(p-1)p^(k-1);

因為 p 為質數，所以除了 p 的倍數之外，小于 n 的所有數都是 n 的質數；

情況四：如果 n 可以分解成兩個互質的整數之積，n = p1 × p2，則φ(n) = φ(p1p2) = φ(p1)φ(p2);

比如，φ(30)=φ(5×6)=φ(5)×φ(6)=4×2=8。此種情況可以通過"中國剩餘定理"證明，證明過程不再本文讨論範圍内。

情況五：基于情況四，如果 p1 和 p2 都是質數，且 n=p1 × p2，則φ(n) = φ(p1p2) = φ(p1)φ(p2)=(p1-1)(p2-1)

例如，φ(39) = φ(3×13) = φ(3)φ(13)=2 × 12 = 14;

而 RSA 算法的基本原理就是歐拉函數中的第五種情況，即： φ(n)=(p1-1)(p2-1);

模反元素

如果兩個正整數 a 和 n 互質，那麼一定可以找到整數 b，使得 ab-1 被 n 整除，或者說ab被n除的餘數是1。這時，b就叫做a的“模反元素”。歐拉定理可以用來證明模反元素必然存在。

可以看到，a的 φ(n)-1 次方，就是a對模數n的模反元素。

RSA算法原理

1、随機選擇兩個質數并計算乘積

n=p x q = 3233，3233寫成二進制是110010100001，一共有12位，所以這個密鑰就是12位。

在實際使用中，一般場景下選擇1024位長度的數字，更高安全要求的場景下，選擇2048位的數字，這裡作為演示，選取p=61和q=53；

2、計算n的歐拉函數φ(n)。

因為n、p、q都為質數，所以φ(n) = (p-1)(q-1)=60×52= 3120

3、随機選擇一個整數e，條件是1< e < φ(n)，且e與φ(n) 互質。

1< e <3120，注意，這裡是和φ(n) 互互質而不是n！假設選擇的值是17，即 e=17；

4、計算e對于φ(n)的模反元素 d

模反元素就是指有一個整數 d，可以使得 ed 被 φ(n) 除的餘數為1。表示為：(ed-1)=φ(n) y --> 17d=3120y 1，算出一組解為(2753,15)，即 d=2753，y=-15，也就是(17 2753-1)/3120=15。

注意，這裡不能選擇 3119，否則公私鑰相同.

5、生成結果

公鑰：(n,e)=(3233,2753) 私鑰：(n,d)=(3233,17)

為什麼無法破解

公鑰是公開的，也就是說 m=p*q=3233 是公開的，那麼怎麼求 e ？e 是通過模反函數求得，17d=3120y 1，e是公開的等于 17，這時候想要求d就要知道 3120，也就是 φ(n)，也就是 φ(3233)，說白了，3233 是公開的，你能對 3233 進行因數分解，你就能知道 d，也就能破解私鑰。

正常情況下，3233 我們可以因數分解為 61*53，但是對于很大的數字，人類隻能通過枚舉的方法來因數分解，所以RSA安全性的本質就是：對極大整數做因數分解的難度決定了 RSA 算法的可靠性。換言之，對一極大整數做因數分解愈困難，RSA 算法愈可靠。

人類已經分解的最大整數是：

這個人類已經分解的最大整數為 232 個十進制位，768 個二進制位，比它更大的因數分解，還沒有被報道過，因此目前被破解的最長RSA密鑰就是 768 位。所以實際使用中的 1024 位秘鑰基本安全，2048 位秘鑰絕對安全。

更多精彩资讯请关注tft每日頭條，我们将持续为您更新最新资讯!