院系:李煌数学研究院/RSA公钥密码算法的破解研究(续)

• 符号定义：

RSA算法之公钥e,私钥d,公开模数n,密文c,明文m,且RSA(m)=c.

李煌RSA破解算法

破解满足条件(m,n)=1之明文m

• 唯密文攻击

李煌破解算法

1. 通过公钥e,公开模数n,密文c和方程 $cx^{e}\equiv 1{\pmod {n}}$ 计算出x;
2. 通过x,公开模数n和方程$xy\equiv 1{\pmod {n}}$计算出y;
3. 破解出明文$m=y{\bmod {n}}$

由此可知要破解RSA算法，关键在于求解方程 $cx^{e}\equiv 1{\pmod {n}}$ ，而该方程在RSA算法下壹定存在解，所以求出该方程的解也就破解了RSA，下面给出解答该方程的李煌-费尔马算法。如下所示：

李煌算法

• 由公开模数n，密文c和方程$ca\equiv 1(\mod n)$，求出a

• 由公钥e和公开模数n，密文c，使用有限次循环结构

    for(i=1;i<=e;i++) {    
       根據公式$x_{i}\equiv {(c({a^{e-1}{\bmod {n}}})^{\prod _{1}^{i}e})}{\bmod {n}}$，求出$x_{i}$;
          if ($cx_{i}^{e}\equiv 1{\pmod {n}}$ ) { 
           則當前$x_{i}$爲方程的解答，退出循環;
          }   
    }

• 例如：c=28，n=33，e=3, 由步骤1求出a=13；
• 再由步骤2，求出当循环到i=2的时候得到满足条件的$x_{i}$，$x\equiv x_{2}\equiv 28(13^{3-1}{\bmod {33}})^{3\times 3}{\bmod {33}}\equiv 28(169{\bmod {3}}3)^{9}\equiv 28\times 4^{9}\equiv 28\times 262144{\bmod {33}}\equiv 7{\bmod {3}}3$

所以方程$28x^{3}\equiv 1{\pmod {33}}$有解x=7

来源

• 《南昌理工学院学报》.李煌

<<School:李煌数学研究院