School:李煌數學研究院/RSA公鑰密碼算法的破解研究(續)

• 符號定義：

RSA算法之公鑰e,私鑰d,公開模數n,密文c,明文m,且RSA(m)=c.

李煌RSA破解算法

破解滿足條件(m,n)=1之明文m

• 唯密文攻擊

李煌破解算法

1. 通過公鑰e,公開模數n,密文c和方程 $c{x}^e\equiv 1(\mathrm{mod}n)$ 計算出x;
2. 通過x,公開模數n和方程$xy\equiv 1(\mathrm{mod}n)$計算出y;
3. 破解出明文$m=ymodn$

由此可知要破解RSA算法，關鍵在于求解方程 $c{x}^e\equiv 1(\mathrm{mod}n)$ ，而該方程在RSA算法下壹定存在解，所以求出該方程的解也就破解了RSA，下面給出解答該方程的李煌-費爾馬算法。如下所示：

李煌算法

• 由公開模數n，密文c和方程$ca\equiv 1(modn)$，求出a

• 由公鑰e和公開模數n，密文c，使用有限次循環結構

    for(i=1;i<=e;i++) {    
       根據公式$x_i\equiv (c(a^{e-1}modn{)}^{\prod _1^{i}e})modn$，求出$x_i$;
          if ($c{x}_i^e\equiv 1(\mathrm{mod}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}mod33{)}^{3\times 3}mod33\equiv 28(169mod33{)}^9\equiv 28\times 4^9\equiv 28\times 262144mod33\equiv 7mod33$

所以方程$28x^3\equiv 1(\mathrm{mod}33)$有解x=7

來源

• 《南昌理工學院學報》.李煌

<<School:李煌數學研究院