淘先锋技术网

首页 1 2 3 4 5 6 7


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=pq

2 求 L (在生成密钥对过程中使用)

L 是 p − 1 p - 1 p1 q − 1 q - 1 q1最小公倍数 L = l c m ( p − 1 , q − 1 ) L = lcm(p - 1, q - 1) L=lcm(p1,q1)

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 EDmodL=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(p1,q1)
= 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 EDmodL=1 , D = 103
E ∗ D m o d L = 7 ∗ 103 m o d 144 E * D mod L = 7 * 103 mod 144 EDmodL=7103mod144
= 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。