我們通常會發現數學結果在計算機科學中的有趣應用。RSA就是這樣一種應用程序。

RSA是非對稱加密的一種實現，也稱為公鑰加密，由 Diffie 和 Hellman 在New directions in cryptography [1]中介紹。

非對稱加密背後的想法是每台機器A生成兩個函數f和g使得：

g(f(message)) = message

函數f用于加密消息并由A公開。每台想要向A發送消息的機器都會計算f(message)，并将結果發送給A 。

g用于解密并由A保密。在收到加密消息f(message)後， A計算g(f(message)) = message并檢索初始消息。

為了确保通信安全，從f導出g在計算上應該是不可行的。

基于這個革命性的想法，RSA應運而生。RSA基于簡單但神奇的數學結果。在接下來的部分中，我們将探索基礎數學。

下文中，N為大于0的正整數。如無特殊說明，均為正整數。

考慮φ(N)小于 N且與N互質的嚴格正數的數量。

例如φ(8) = 4，因為有 4 個整數小于 8 且與 8 互質，分别是 1、3、5 和 7。

可以證明，對于任意兩個互質整數p和q：

想想看。通過知道有多少整數互質且小于p，以及有多少互質且小于q，我們知道有多少整數互質且小于N=pq而無需處理p和pq之間以及q和pq之間的整數.

一個例子可能有助于突出這個神奇的等式。

以數字 72 為例。它等于互質的 8x9。

• φ (8) = 4 : 與 8 互質的整數是 1, 3, 5, 7
• φ (9) = 6 : 與 9 互質的整數是 1, 2, 4, 5, 7, 8

上面的等式告訴我們有 4x6=24 個互質且小于 72 的數。我們甚至沒有考慮這些數以及它們與 72 的關系，但我們知道有多少個互質且小于 72。并且這是數學的一些魔力。

我将在以後的文章中展示方程式的工作原理。現在，我們關注RSA背後的所有結果的大局以及它們如何協同工作。

歐拉定理規定，對于任意與N 互質的正整數m ，我們有：

這意味着如果我們将任何與N互質的正整數m乘以φ(N)的幂，然後除以N，則除法的餘數将等于 1。

因此，對于任何正整數k，我們有：

将每邊乘以m我們得到：

公式k.φ(N) 1 提醒Bezout identity，它指出對于每個與​φ(N)互質的數字e ，有兩個整數d和k使得：

如果 Bezout 的身份暫時不直觀，請不要擔心，我們将在下一篇文章中回過頭來。

通過替換上面的公式，我們得到：

也可以寫成：

通過考慮f将x映射到f(x) = x^e mod N 的函數，以及g将x映射到g(x) = x^d mod N，其中mod返回除法的餘數，我們有g(f (m)) = m對于每個m < N。

細心的讀者會注意到，Bezout 等式中出現的k是一個整數，可能是正數，也可能不是正數。然而，隻有正k給出m^kφ(N) ≡ 1 mod N。在k為負的情況下，我們隻需将k.φ(N)移動到等式的另一部分：

我們現在有兩個函數f 和g ，它們在我們計算g(f(m))時為我們提供初始整數m。整數m将作為要發送的消息。f将公開，g将是私有的。這意味着整數e和N将是公開的，而整數d是私有的。偶數(e,N)是公鑰，偶數(d,N)是私鑰。我們需要選擇N ，使得隻知道e和N來計算d是不可行的.

要從e導出d，攻擊者必須首先計算φ(N)。

如果我們選擇N為質數，則φ(N)簡單地等于N-1 ，因為1和N-1之間的所有數字都與N互質。在這種情況下，因為N是公開的，所以攻擊者可以毫不費力地獲知φ(N) 。

質數p的平方N : N = p²怎麼樣？好吧，可以很容易地證明φ(p²) = p(p-1)。因此，知道p就足以知道φ(N)。p可以通過在1和N之間執行二進制搜索以對數時間複雜度獲得。

這可以通過選擇兩個不同素數p和q的乘積N來輕松改進：N = pq在這種情況下：

應該知道p和q才能計算φ(N)。計算p和q 的時間複雜度與N相比不是線性的。如果攻擊者達到每秒測試超過 10²⁰ 個數字的巨大速度（想象 1000 家像谷歌這樣規模的公司，使用他們所有的服務器進行搜索，每台服務器以每秒 100 億個數字的速度執行），它仍然需要如果選擇大的p和q（例如，每個 2048 位寬，這是今天使用的大小），他們将花費超過 10¹⁹⁰ 個世紀來導出p和q 。所以選擇N=pq兩個素數的乘積足以保證RSA 的安全。

讓我們總結一下RSA。

每台機器通過執行以下操作生成其（公鑰、私鑰）密鑰對：

1. 随機生成兩個大小為 2048 位的大質數p和q
2. 計算N=pq和φ(N) = (p-1).(q-1)
3. 選擇一個與φ(N)互質的數e
4. 使用Euclid 擴展算法，計算e模φ(N)的倒數d
5. 将(e, N)存儲為公鑰，将(d, p, q, N) 存儲為私鑰。

那麼， A和B之間的消息加密和解密過程如下：

1. A将消息表示為小于N 的整數m
2. A計算c=m^eB mod NB其中(eB, NB)是B的公鑰。c是加密的消息。
3. A将c發送給B
4. B計算c^dB mod NB ，其中dB是其私鑰，并檢索由A加密的初始整數m。
5. B将整數m轉換為初始消息

就是這樣，這就是RSA的基本算法。這并不難理解，但我仍然無法想象發明者是如何想出這個數學可以用來發明革命性加密方式的絕妙想法的。

在以後的文章中，我們将對我們看到的每一個數學結果有更多的直覺。敬請關注！

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