RSA演算法是如何計算的？

RSA 是一種用於公鑰加密的密碼系統，廣泛用於保護敏感資訊，尤其是在透過不安全的網路（包括網際網路）傳送時。

RSA演算法是最流行的非對稱金鑰加密演算法，它依賴於一個數學事實：發現和乘以大素數很容易，但分解它們的乘積卻很複雜。它需要公鑰和私鑰。

RSA演算法示例

讓我們舉一個這個過程的例子來學習這些概念。為了便於閱讀，可以將示例值與演算法步驟一起編寫。

  • 選擇兩個大的素數 P 和 Q

    設 P = 47，Q = 17

  • 計算 N = P x Q

    我們有，N = 7 x 17 = 119。

  • 選擇公鑰（即加密金鑰）E，使其不屬於 (P -1) x (Q – 1)

    • 讓我們找到 (7 - 1) x (17 -1) = 6 x 16 = 96

    • 96 的因子是 2、2、2、2、2 和 3（因為 96 = 2 x 2 x 2 x 2 x 2 x 3）。

    • 因此，可以選擇 E 使得 E 的任何因子都不是 2 和 3。我們不能選擇 E 為 4（因為它有因子 2），15（因為它有因子 3）和 6（因為它同時有因子 2 和 3）。

    • 讓我們選擇 E 為 5（它可以是任何其他數字，其因子不是 2 和 3）。

  • 選擇私鑰（即解密金鑰）D，包括以下等式為真

    (D x E) mod (P – 1) x (Q – 1) = 1

    • 讓我們將 E、P 和 Q 的值代入方程。

    • 我們有 (D x 5) mod (7 – 1) x (17 – 1) = 1。

    • 也就是說，(D x 5) mod (6) x (16) = 1。

    • 也就是說，(D x 5) mod (96) = 1

    • 經過一些計算，讓我們取 D = 77。然後以下為真：(77 x 5) mod (96) = 385 mod 96 = 1，這就是我們想要的。

  • 對於加密，根據以下公式計算密文 (CT) 從明文 (PT)：

    CT = PTE mod N

    假設我們要加密明文 10。那麼，我們有

    CT = 105 mod 119 = 100000 mod 119 = 40。

  • 將 CT 作為密文傳送給接收者。

    將 40 作為密文傳送給接收者。

  • 對於解密，根據以下公式計算明文 (PT) 從密文 (CT)：

    PT = CTD mod N

    執行以下操作

    PT = CTDmod N

    也就是說，

    PT = 4077mod 119 = 10，這是步驟 5 中的原始明文。

更新於： 2023年11月4日

21K+ 瀏覽量

開啟你的職業生涯

透過完成課程獲得認證

開始學習
廣告