问RSA加密，数论

EN

问题是:您有满足关系的值e, d, p：

ed - 1 = k(p-1)

对于某些整数k，您要做的是找到满足关系的其他素数q (在某个大小范围内)：

ed - 1 = k'(q-1)

(对于某些整数k')

如果没有第一个关系，就很难找到第二个关系(因为我们需要在ed-1中找到一个1024位的因素，这是很困难的)，但是，通过利用第一个关系，它是实用的。

有一种方法可以继续下去：

• 计算k = (ed - 1)/(p - 1)，然后获得部分因式分解(即在k和p-1的光滑界M以下查找所有素因子)；即：

p - 1 = p_0 p_1 p_2 … p_n c

k = p'_0 p'_1 p'_2 … p'_{n'} c'

(对于素数p_0, p_1, …, p_n, p'_0, p'_1, …, p'_{n'}和不带素数因子的整数c, c' < M)

然后，迭代值c', p_0, p_1, …, p_n, p'_0, p'_1, …, p'_{n'}的各个子集，其子集如下：

• 子集元素的乘积q-1在大小范围内。
• 一个以上的产品(q)是素数。

满足上述两种关系的值q对于您要寻找的素数(可能有多个)是有效的。

如果存在这样一个q (也就是说，您的e, d, p值来自有效的D31密钥)，如果\gcd( p-1, q-1 ) < M (如果p, q没有被专门选择来拥有一个大的D32)，那么它总是成功的。