RSA 公鑰加密演算法

終端之間信息傳遞安全性的保證始終是業務的剛性需求。不同的加密演算法針對不同的業務需求，

因為公司是金融公司性質，又不是傳統的金融公司(PS:牽扯到數字貨幣、常聽說的比如：比特幣)，加密演算法這塊也算是有一部分的了解。

這裡要講的內容如 標題????

數字簽名

數字簽名就是類似紙質文件上的手寫簽名的電子版。任何人都可以輕鬆地核對簽名，不能偽造它是其存在的根本目的。

數字簽名可以為簽名者身份和其簽署的信息內容提供證明。

對於電子簽署的商業性合同,電子支票,電子購貨單和其他一些各方希望進行認證的電子信息來說是一種理想的解決方案。

素數

在密碼學中需要找到最大的隨機素數是必須的。大素數很多，通常測試適當的隨機整數，知道找到素數的過程是可行的。

Advertisements

素數的分佈函數 π(n): 描述了小於或等於n的素數的數目

素數定理給了 π(n) 一個有用近似：

$$ \lim_{n \to +\infty} \frac{π(n)}{n/(\ln n)} \quad = 1 $$

e.g:

當 n = 10^9 時其誤差不超過 6% 其：π(n)=508,475,34,且 n/ln * n≈ 482,549,42

伯努利實驗

RSA基於素數原理：尋求大素數是很容易的，把一個數分解成兩個最大素數的積卻相當的困難

公鑰加密

公鑰加密，顧名思義有一把 公鑰 與 私鑰

在 RSA 加密演算法中，每一個秘鑰由一對整數組成。在密碼學中常以 Alice 與 Bob 作為例子，這也是每當有人普及比特幣相關的技術的時候頻率出現較多的名詞。

Advertisements

如圖：用 $P_A$ 表示 Alice 公鑰，$S_A$ 表示 Alice 私鑰

同理：

如圖：用 $P_B$ 表示 Bob 公鑰，$S_B$ 表示 Bob 私鑰

秘鑰需要保密，公鑰可以對任何人透露,這個跟比特幣地址是一樣的。

公鑰和秘鑰指定了可用於任何信息的函數。設 $\mathfrak{D}$ 表示允許的信息集合。其可能是所以有限長度的位序列的集合。

在最原始的公鑰加密設想中，要求公鑰與秘鑰指定一種從 $\mathfrak{D}$ 到其自身的一一對應的函數。對應 Alice 的公鑰 $P_A$ 的函數用 $P_A()$ 表示，他的秘鑰 $S_A$ 的函數表示成 $S_A()$, 因此 $P_A()$ 與 $S_A()$ 函數都是 $\mathfrak{D}$ 的排列。架設已知秘鑰 $P_A$ 或 $S_A$,可以有效的計算出函數 $P_A()$ 和 $S_A()$

系統中任何參與者的公鑰和秘鑰都是一個「匹配對」，它們指定的函數互為反函數，也就是說，對於任何消息 $M\in\mathfrak{D} $ 有：

$$ M = S_A(P_A(M)) \ M = P_A(S_A(M)) $$

由此可以看出，運用兩把秘鑰 $P_A$ 和 $S_A$ 對 $M$ 相繼進行變換后，最後任然得到消息 $M$

故在應用程序中：要求除了 Alice 外，沒人能在較實用的時間內計算出函數 $S_A()$。 對於送給 Alice 加密郵件的保密性與 Alice 的數字簽名的有效性。

因為$P_A$是公開的，就比如 數字貨幣的地址，這樣就可以計算出 $P_A()$ 它也是 $S_A()$ 的反函數，這個時候就要保證只有 Alice 能夠計算出 $S_A()$ 。

模擬一個發送環境：

如上圖： Bob 給 Alice 發送一條加密的消息 Message,竊取著得到的是一串亂碼。

  1. Bob 得到 Alice 的公鑰 $P_A$

  2. Bob 計算出對應的 M 的密文 $C=P_A(M)$，並把 C發送給 Alice

  3. 當 Alice 得到密文 C 之後，運用自己的秘鑰 $S_A$ 恢復原始信息: $S_A(C)=S_A(P_A(M))=M$.

由於 $S_A()$ 和 $P_A()$ 互為反函數，所以 Alice 能夠根據 C 計算出 M。因為只有 Alice 能夠計算出 $S_A()$, 所以也只有 Alice 能根據 C計算出 M。因為 Bob 運用 $P_A$ 對M進行加密，所以只有 Alice 可以理解接收的消息。

用類似的公鑰系統的設想可以很容易的實現數字簽名，現在 Alice 希望把一個數字簽署的答覆 M^' 發送給 Bob

在公鑰的數字簽名中， Alice 將她的數字簽名 $\sigma = S_A(M')$ 附加到消息 M『上，來對消息 M』 簽名。她將消息/簽名對 $(M', \sigma)$ 發送給 Bob,Bob 通過檢查等式 $M』 = P_A(\sigma)$ 來驗證它。如果等式成立，則他接受 $(M',\sigma)$ 作為 Alice 已經簽名的一個消息

  1. Alice 運用她的秘鑰 $S_A$ 和等式 $\sigma = S_A(M')$ 計算出信息 M』 的數字簽名 $\sigma$.

  2. Alice 把消息/簽名對 $(M', \sigma)$ 發送給 Bob.

  3. 當 Bob 收到 $(M', \sigma)$ 時，他可以利用 Alice 的公鑰，通過驗證等式 $M』 = P_A(\sigma)$ 來證實該消息的確是來自 Alice.

如果 M』 包含 Alice 的名字，這樣 Bob 就知道應該使用誰的公鑰。

由上圖中的驗證可以看到，如果符合 Bob 可以得出消息 M『 確實是 Alice 簽名的結論。如果不成立，那麼 Bob 就可以得出一個結果： 要麼就是信息 M『或數字簽名 $\sigma$ 因傳輸錯誤而損壞，要麼信息對 $(M',\sigma)$ 是一個故意的偽造。

因為一個數字簽名既證明了簽署者身份，也證明了簽署的信息內容，所以它是對文件末尾的手寫簽名的一種模擬。

數字簽名必須可以被能取得簽署者公鑰的人去驗證,一條所簽署過的信息可以被確認方確后再傳送到其他可以驗證簽名的各方。

比如我給你的一個比特幣其實就是一個簽名的過程，只是比特幣採用的是多次簽名加密技術，比這個要複雜許多(做區塊鏈開發的人可能見笑了)，其原理是怎樣的呢？密碼學中一個通俗的例子：

Alice 給 Bob 的一張電子支票，Bob 確認了支票上 Alice 的簽名后，就可以把這張支票交送給銀行，而銀行也可以對簽名進行一個驗證，然後就可以調撥相應的資金。

上面講到的是簽署的信息是沒有加密的,該信息是公開透明的，比如比特幣交易的過程中是公開透明，該行為會向全網進行一個廣播，同而使各個節點都能同步到該交易事件。

而我們這裡要說的反而恰恰相反，我們要把信息進行一個加密，怎樣去加密呢？就是把有關加密和簽名的兩種方案結合起來使用，就可以創建出同時被簽署和加密的消息，簽署者首先把其數字簽名附加在消息的後面，然後再用他預定的接受者的公鑰對最終的消息/簽名對進行加密。接收者用其密鑰對收到的消息進行解密，以同時獲得原始消息和數字簽名。然後接收者可以用簽署者的公鑰對簽名進行驗證。很有意思！

RSA加密系統

公鑰私鑰創建過程

1.隨機選出最大素數 $\mathcal{P}$ 和 $\mathcal{q}$, 使得 $\mathcal{P}\not=\mathcal{q}$ e.g：素數 $\mathcal{P}$ 和$\mathcal{q}$ 可能各有 1024 位。

2.計算 $n=\mathcal{P} \mathcal{q}$

3.選取一個與 $\phi(n)$互質的最小奇數 e，其中由等式 $\phi(n)$ 等於 ($\mathcal{P}-1$)($\mathcal{q}-1$)

4.對模 $\phi(n)$, 計算出 e 的乘法逆元 d 值。

5.將對 $P=(e,n)$ 公開，並作為參與者的 RSA 公鑰

6.使對 $S=(d,n)$ 保密，並作為參與者的 RSA秘鑰

設 $D$ 為集合 $Z_n$.為了變換與公鑰 $P=(e,n)$ 相關的消息 $M$, 計算 $$P(M) = M^e\mod n$$

這個時候變換與秘鑰 $S =(d,n)$ 相關的密文 C，計算 $$S(C)=C^d \mod n$$

上面所看到的等式對加密與簽名是通用的。為了創建一個簽名，簽署人把其秘鑰應用於待簽署的消息，而不是密文中。為了確認簽名，將簽署人的公鑰應用在簽名中，而並非在加密的消息中。

用模的求冪過程，來對公鑰與秘鑰的一些操作。

我們設公鑰(e,n)和秘鑰(d,n)滿足 $\lg e = O(1)$, $\lg d \leq \beta$, 且 $\lg n \leq \beta$.

然後，應用公鑰需要執行 $O(1)$ 次模乘法運算和 $O(\beta^2)$ 次位操作。 應用秘鑰需要執行 $O(\beta)$ 次模乘法運算 $O(\beta^3)$ 次位操作。

RSA安全性保證

RSA加密的安全性主要來源於對最大整數進行因式分解的困難性。如果對方對公鑰中的模 n 進行分解，就可以根據公鑰推導出秘鑰，主要是因為對方和公鑰創建者以同樣的方法使用因子 $\mathcal{P}$ 和 $\mathcal{q}$ .故如果能夠分解大整數，就可以輕易破解 RSA 加密演算法。

這樣來講：對RSA加密系統的破解難易程度取決於分解最大整數的困難度。

在計算機發展的歷史中至今還沒有發行比分解模 n 更容易的方法來打破 RSA加密。

通過隨機選取兩個 1024 位的素數並求出它們的積，就可以創建出一把用現在技術在可行時間內破解的公鑰。也就是說在演算法的發展史上沒有取得新的突破性進展的時候，RSA 加密演算法是一種安全方面的保證。

基於上面論述的原理，在實際的實現過程中 選取的位素數通常在 768到 2048 位。由此就需要能夠有效的找出最大素數。

在實際的應用當中為了提高效率，最長使用的是一種 秘鑰管理 模式的RSA，來實現快速無公鑰加密系統。在這樣的一個系統中，加密秘鑰與解密秘鑰是同一個。

e.g:

Alice 把一條長消息 M 發送給 Bob, 她從快速無公鑰加密系統中選取一把隨機秘鑰 K，然後運用 K 對 M進行加密，得到密文 C。這個時候 C的長度與 M一樣長，但是 K相當短。在一步， Alice 利用 Bob的公開 RSA秘鑰對 K進行加密。 因為 K 很短，所以計算 $P_B(K)$ 的速度也很快。$t_1 = P_B(K)的計算時間$，$t_2 = P_B(M)的計算時間$, 有: $t_1 > t_2$.

最後 Alice 把 $(C,P_B(K))$ 傳送給 Bob, Bob對 $P_B(K)$ 解密得到 K，然後在用 K 對 C 進行解密，得到 M。

通過上面例子了解到：使用一種混合的方法來提高數字簽名的執行效率。

把 RSA 與一個公開的 抗衝突散列演算法 h 結合。 使用該函數的目的就是找出兩條消息 M和M',有 h(M)=h(M').

h(M)的值是消息M的一個短 「指紋」 的一個概念。

如果 Alice 簽署消息 M，她第一步要做的就是把函數 h 作用於 M得到的指紋h(M),然後用她的秘鑰加密h(M). Alice 將 $(M,S_A(h(M)))$ 作為她簽署的 M 的版本發送給 Bob. Bob 可以通過計算 h(M),並將 $P_A$ 應用於收到的 $P_A(h(M))$ 驗證其是否等於h(M)來驗證簽名的真實性。

原理：沒有人能夠同時創建出兩條具有相同指紋的消息，所以在計算機上不可能改變簽署的消息，又保持了簽名的合法性。

所以利用證書可以輕鬆地分配公鑰。

e.g:

在公網中有一個 T，每個人都知道其 公鑰。 Alice 從T得到一條簽署的證書，聲明 「Alice」 的公鑰是 $P_A$. 由於每個人都知道 $P_T$,該證書是 「自我認證」。 Alice 可以把自己的證書含在簽名信息當中，使得接受者可以立即得到 Alice 的公鑰，來驗證其簽名。因為 Alice 的秘鑰是被 T 簽署的，所以接收者知道 Alice 的秘鑰確實是 Alice 本人的秘鑰。

如果你看到這路覺得公式看著彆扭，我也無能為力( ⊙ o ⊙ )！，掘金的富文本還有待加強！！！

Advertisements

你可能會喜歡

Advertisements