Elgamal&RSA小结

前言

要解决的问题：$c\equiv m^{e}\ \textrm{mod}\ N$($m1$)。

分类讨论

首先给出求解方程($q,e$为素数)$y\equiv x^{e}\ \textrm{mod}\ q^{k}$的Python脚本

注：当$k=1$时，可(使用Sagemath)直接在有限域$GF(q)$上对$y$开$e$次方；

$N=p^{a}$

记$g=(e,\phi(N)),e_{1}=e/g$，则$(e_{1},\phi(N))=1$，因此可以计算$d_{1}\equiv e_{1}^{-1}\ \textrm{mod}\ \phi(N)$；$c^{d_{1}}\equiv m^{e\cdot d_{1}}\equiv (m^{g})^{d_{1}\cdot e_{1}}\equiv m^{g}\ \textrm{mod}\ N$，从而可得$m^{g}\ \textrm{mod}\ p^{a}$，接下来使用上述工具求解(最多有$g$个解)。

$N=p_{1}^{a_{1}}\cdots p_{k}^{a_{k}}$

$c\equiv m^{e}\ \textrm{mod}\ N\Rightarrow c\equiv m^{e}\ \textrm{mod}\ (p_{1}^{a_{1}}\cdots p_{k}^{a_{k}})$，则有

$$c\equiv m^{e}\ \textrm{mod}\ p_{1}^{a_{1}}\\ \vdots \\ c\equiv m^{e}\ \textrm{mod}\ p_{k}^{a_{k}}\\$$

记$\phi_{i}=\phi(p_{i}^{a_{i}})$，$g_{i}=(e,\phi_{i})$，$e_{i}=e/g_{i}$，$d_{i}\equiv e_{i}^{-1}\ \textrm{mod}\ \phi_{i}$

$$m^{g_{1}}\equiv c^{d_{1}}\ \textrm{mod}\ p_{1}^{a_{1}}\\ \vdots \\ m^{g_{k}}\equiv c^{d_{k}}\ \textrm{mod}\ p_{k}^{a_{k}}\\$$

这时处理的方式不唯一；我们只考虑那些$g_{i}$很小的线程同余方程，不妨设$g_{1},\cdots,g_{t}$很小；

(1)$g_{1}=\cdots =g_{s}=r$，$s\leqslant t$(不妨设前$s$个$g_{i}$相等)

利用中国剩余定理求解前$s$个方程组成的方程组，得到方程组在模$p_{1}^{a_{1}}\cdots p_{s}^{a_{s}}$下的解；当$m^{r}<p_{1}^{a_{1}}\cdots p_{s}^{a_{s}}$时，直接对解开$r$次方即得$m$；

(2)一般情况，$g_{i}(i=1,\cdots,t)$很小但是大多数各不相同

那么首先对每个方程组利用上述工具求解(记$x_{i}$为第$i$个方程的解，此时大多数方程组有多个解，每个方程组的解最多有$g_{i}$个)

$$m\equiv x_{1}\ \textrm{mod}\ p_{1}^{a_{1}}\\ \vdots \\ m\equiv x_{k}\ \textrm{mod}\ p_{k}^{a_{k}}\\$$

利用中国剩余定理求解前$t$个方程组成的方程组，得到方程组在模$p_{1}^{a_{1}}\cdots p_{k}^{a_{t}}$下的解；当$m<p_{1}^{a_{1}}\cdots p_{t}^{a_{t}}$时，$m$必在这些解中。

注：其实这里也解释了为什么考虑那些$g_{i}$很小的线程同余方程，我们最多要求解$g_{1}\cdots g_{t}$个这样的方程组，每个方程组会求出一个解；如果$g_{i}$很大，那么候选的解太多；但是我们要保证$p_{1}^{a_{1}}\cdots p_{t}^{a_{t}}>m$。