江鸟's Blog

初识RSA (持续更新)

字数统计: 555阅读时长: 2 min
2019/10/29 Share

RSA超级难!

RSA初探

加密过程

  1. 两个质数 P 和 Q ,越大越难以破解

  2. n 的欧拉函数 ,记为 m

    1
    φ(n) = φ(P * Q)= φ(P - 1)φ(Q - 1) = (P - 1)(Q - 1)
  3. 随机选择整数 e ,条件为 1 < e < m ,且 e 和 m 互质

  4. 找一个整数 d ,使 ( e * d ) % m = 1

    等价于 e * d - 1 = y * m ( y 为整数)

    找到 d ,实质就是求解 e * x - m * y =1

  5. 求出整数解 ,公钥就是(n,e),私钥就是(n,d)

对密文加密过程

假设发送一个中文“中” 以 utf-8 方式编码为 [e4 b8 ad],转为 10 进制为 [228,184,173]。要想使用公钥(n,e) = (4757 , 101)加密,要求被加密的数字必须小于 n,被加密的数字必须是整数,字符串可以取 ascii 值或unicode值,因此将“中”字折为三个字节 [228,184,173],分别对三个字节加密。
假设 a 为明文,b 为密文,则按下列公式计算出 b

1
a^e % n = b

计算 [228,184,173]的密文:
228^101 % 4757 = 4296
184^101 % 4757 = 2458
173^101 % 4757 = 3263
即 [228,184,173]加密后得到密文 [4296,2458,3263] ,如果没有私钥 d ,神仙也无法从 [4296,2458,3263]中恢复 [228,184,173]

解密过程

乙收到密文 [4296,2458,3263],并用自己的私钥(n,d) = (4757 ,1601) 解密。解密公式如下:
假设 a 为明文,b 为密文,则按下列公式计算出 a

1
a^d % n = b

密文 [4296,2458,3263]的明文如下:
4296^1601% 4757 = 228
2458^1601% 4757 = 184
3263^1601% 4757 = 173
即密文 [4296,2458,3263] 解密后得到 [228,184,173]
将[228,184,173] 再按 utf-8 解码为汉字 “中”,至此解密完毕。

假设破解过程

根据密钥生成过程

需要知道私钥即为知道d

需要知道P和Q,他们的来源是n的因数分解,当对于大整数的因数分解,是很困难的,除了暴力破解

目前已破解最大整数

1
2
3
4
5
1230186684530117755130494958384962720772853569595334792197322452151726400507263657518745202199786469389956474942774063845925192557326303453731548268507917026122142913461670429214311602221240479274737794080665351419597459856902143413
=
33478071698956898786044169848212690817704794983713768568912431388982883793878002287614711652531743087737814467999489
x
36746043666799590428244633799627952632279158164343087642676032283815739666511279233373417143396810270092798736308917

所以可破解最大密钥为768位,实际应用中 RSA 的密钥长度为 1024 位,重要场合 2048 位,未来半个世纪不可能破解。

参考:一文搞懂 RSA 算法

CATALOG
  1. 1. RSA初探
    1. 1.1. 加密过程
    2. 1.2. 对密文加密过程
    3. 1.3. 解密过程
    4. 1.4. 假设破解过程