非對稱加密算法 RSA

• • 如何計算得到 N E D
  • • 1 求 N
    • 2 求 L （在生成密鑰對過程中使用）
    • 3 求 E
    • 4 求 D
  • 執行個體
  • • 生成密鑰對
    • 加密
    • 解密

7 4 m o d 12 7^4 mod 12 74mod12 很好算

但 7 x m o d 12 = 8 7^x mod 12 = 8 7xmod12=8 , x x x 如何求就比較複雜，特别是當是數字特别大時，求離散對數非常困難耗時。

RSA 加密就是利用的這點。

在 RSA 加密中，明文/密鑰/密文 都是數字。

RSA 加密可以用下面公式來概括：

密 文 = 明 文 E m o d N 密文 = 明文^E mod N 密文=明文EmodN

”E 和 N 的組合“就是公鑰。

解密可以用下面的這個公式來概括：

明 文 = 密 文 D m o d N 明文 = 密文^D mod N 明文=密文DmodN

是以 ”D 和 N的組合“ 就是私鑰。

如何計算得到 N E D

1 求 N

1. 随機擷取兩個大質數： p p p、 q q q。
2. N = p ∗ q N = p * q N=p∗q

2 求 L （在生成密鑰對過程中使用）

L 是 p − 1 p - 1 p−1 和 q − 1 q - 1 q−1 的最小公倍數。 L = l c m ( p − 1 , q − 1 ) L = lcm(p - 1, q - 1) L=lcm(p−1,q−1)

3 求 E

E 與 L 的關系：

1 &lt; E &lt; L 1 &lt; E &lt; L 1<E<L

g c d ( E , L ) = 1 gcd(E, L) = 1 gcd(E,L)=1 (E 和 L 的最大公約數 是 1， 這是為了保證存在解密時用到的數 D)

可以用僞随機數生成器産生候選數，然後使用 輾轉相除法 判斷是否滿足 g c d ( E , L ) = 1 gcd(E, L) = 1 gcd(E,L)=1 。

4 求 D

數 D　是根據數　E　計算得到的。D 、E、L 之間滿足下列關系

1 &lt; D &lt; L 1 &lt; D &lt; L 1<D<L

E ∗ D m o d L = 1 E * D mod L = 1 E∗DmodL=1

執行個體

生成密鑰對

1> p = 17, q = 19 那麼 N = 323

2>

L = l c m ( p − 1 , q − 1 ) L = lcm(p - 1, q - 1) L=lcm(p−1,q−1)

= l c m ( 16 , 18 ) = lcm(16, 18) =lcm(16,18)

$= 144 $

3> E 要滿足 g c d ( E , L ) = 1 gcd(E, L) = 1 gcd(E,L)=1，那麼 E 有很多可取的 比如 5、7、等 ，這裡取 E = 7

4> D 要滿足 E ∗ D m o d L = 1 E * D mod L = 1 E∗DmodL=1 ， D = 103

E ∗ D m o d L = 7 ∗ 103 m o d 144 E * D mod L = 7 * 103 mod 144 E∗DmodL=7∗103mod144

= 721 m o d 144 = 721 mod 144 =721mod144

= 1 = 1 =1

此時便得到了密鑰對：

公鑰：E = 7 N = 323

私鑰：D = 103 N = 323

加密

要加密的明文必須是小于 N N N 的數，也就是小于 323 的數。這裡假設明文是 250， 公鑰 $ E = 7$ 、 N = 323 N = 323 N=323， 帶入公式:

明 文 E m o d N = 25 0 7 m o d 323 = 211 明文^E mod N = 250^7 mod 323 = 211 明文EmodN=2507mod323=211

是以密文就是 211。

解密

對密文 211 解密。私鑰是： D = 103 D = 103 D=103、 N = 323 N = 323 N=323。

密 文 D m o d N = 21 1 103 m o d 323 = 250 密文^D mod N = 211^{103} mod 323 = 250 密文DmodN=211103mod323=250

得到明文 250。