RSA 加密演算法說明 (繁體中文):ejsoon 写了: gemini
將下面文章翻譯成繁體中文,之後用P=5503,Q=8239來驗證。
1. 找两个很大的素数(质数)P 和 Q, 越大越好, 比如 100 位长的, 然后计算它们的乘积 N=P×Q, M=(P-1)×(Q-1)
2. 找一个和 M 互素的整数 E, 也就是说 M 和 E 除了 1 以外没有公约数
3. 找一个整数 D, 使得 E×D 除以 M 余 1, 即 E×D mod M = 1
现在, 世界上先进的、最常用的密码系统就设计好了, 其中 E 是公钥谁都可以用来加密, D 是私钥用于解密, 一定要自己保存好. 乘积 N 是公开的, 即使敌人知道了也没关系.
现在, 我们用式子 X^E mod N 对 X 加密得到密码 Y, 破解密文时用式子 Y^D mod N 得到原文X.
1. 找兩個很大的質數 P 和 Q,越大越好,例如 100 位數長的,然後計算它們的乘積 N = P × Q,以及 M = (P - 1) × (Q - 1)。
2. 找一個和 M 互質的整數 E,也就是說 M 和 E 除了 1 以外沒有公因數 (最大公因數為 1)。
3. 找一個整數 D,使得 E × D 除以 M 的餘數為 1,也就是 E × D mod M = 1 (或表示為 E × D ≡ 1 (mod M))。
現在,世界上先進的、最常用的密碼系統 RSA 就設計好了,其中 E 是公鑰,任何人都可以用來加密;D 是私鑰,用於解密,一定要自己保存好。乘積 N 是公開的,即使敵人知道了也沒關係。
我們用公式 X^E mod N 對 X 加密得到密文 Y,破解密文時用公式 Y^D mod N 得到原文 X。
驗證範例 (P=5503, Q=8239):
* 步驟一:
P = 5503
Q = 8239
N = P × Q = 5503 × 8239 = 45358717
M = (P - 1) × (Q - 1) = (5503 - 1) × (8239 - 1) = 5502 × 8238 = 45342276
* 步驟二:
選擇 E = 65537 (這是一個常用的公鑰值,且與 M 互質)
* 步驟三:
需要找到 D 使得 (E × D) mod M = 1,也就是 65537 × D mod 45342276 = 1。
這個步驟需要使用擴展歐幾里得演算法來求解 D。 D 的值為 20523969。 (此處省略計算過程,可以使用線上工具或程式計算)
加密解密範例 (假設 X = 1234):
* 加密:
Y = X^E mod N = 1234^65537 mod 45358717
(計算結果過大,需要使用特殊工具或程式計算)
* 解密:
X = Y^D mod N = Y^20523969 mod 45358717
(將加密後的 Y 值代入計算,使用特殊工具或程式計算,結果應為 1234)
注意: 由於計算量龐大,實際操作中需要使用專門的數學軟體或程式庫來進行大數的模冪運算。這個例子只是為了說明 RSA 的原理,實際應用中 P 和 Q 的值會更大,以確保安全性。