院系:李煌數學研究院/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:李煌數學研究院