RSA_NestingDoll

感觉该换博客框架了，目前这个公式渲染不出来：（

定义

• n = p · q · s · r
• n1 = p1 · q1 · s1 · r1

其中存在关系：

• (p1 - 1) = k · p，剩余三个元素同理

并且：

• k = minPrime · minPrime · ... · minPrime

推导

已知费马小定理：

$$ a^{p-1} \equiv 1 \pmod p $$

令通式 p = p1，则存在 p 为 n 的素因子，使得：

$$ a^{(p_1-1)\cdot t} = a^{k \cdot t \cdot p} \equiv 1^{k \cdot t} \pmod{p_1} $$

令：

$$ A = a^{(p_1-1)\cdot t} $$

则有 k' ∈ Z，使得：

$$ A \equiv 1 + k' \cdot p_1 \iff (A-1)\equiv k'\cdot p_1 \iff k\cdot p_1 \equiv k'\cdot p_1 $$

则易知：

$$ \gcd(k' \cdot p_1,\; p_1 \cdot q_1 \cdot s_1 \cdot r_1) = \lambda p_1 $$

（其中 λ 得是 1 才能往下解，从结果上来看大概率为 1，但至于为什么还有待研究。）

后可由 gcd(p1 - 1, n) 得到 p（此处的问题同上处的 λ）。

此时令 n1 = n1 // q1，重复该操作三次，得到剩余元素值。

算法优化

已知 smooth 化的 minPrime 为 20 位数，由此则可跳过非素数的 t 的因子，减少计算量。同时 smooth_Prime 中自带 p,q,r,s 作为因子，将其乘积作为初始值可只碰撞小 prime 后的因子。

且注意到小素数由 getPrime(20) 获取，重复概率值得让人假设不存在重复；对 a 每次都 pow 一个 20 bits 内的 Prime，而非使用 Prime Power。

结尾（RSA）

对于 p,q,r,s 而言，其 φ 值可由欧拉函数的乘法性推得：

$$ \varphi = (p-1)(q-1)(r-1)(s-1) $$

后续走正常 RSA 流程即可。

关于 λ 问题的例子

在 (mod n) 环境下运算，存在非 1 解：

$$ 2^4 \equiv 1 \pmod{15} $$

但此时有：

$$ 2^4 \equiv 1 \pmod{5} $$

并且 gcd(0,n)=n。