查看“︁School:李煌數學研究院/RSA公鑰密碼算法的破解研究(續)”︁的源代码


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

==李煌RSA破解算法==

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

*唯密文攻擊

==李煌破解算法==

# 通過公鑰e,公開模數n,密文c和方程 <math>cx^e\equiv 1\pmod n</math> 計算出x;
# 通過x,公開模數n和方程<math>xy\equiv 1\pmod n</math>計算出y;
# 破解出明文<math>m= y\bmod n</math>

由此可知要破解RSA算法，關鍵在于求解方程 <math>cx^e\equiv 1\pmod n</math> ，而該方程在RSA算法下壹定存在解，所以求出該方程的解也就破解了RSA，下面給出解答該方程的李煌-費爾馬算法。如下所示：

==李煌算法==
* 由公開模數n，密文c和方程<math>ca\equiv 1(\mod n)</math>，求出a
       
* 由公鑰e和公開模數n，密文c，使用有限次循環結構
     for(i=1;i<=e;i++) {    
        根據公式<math>x_i\equiv {(c({a^{e-1}\bmod  n})^{\prod_{1}^i e})} \bmod n</math>，求出<math>x_i</math>;
           if (<math>cx_i^e\equiv 1\pmod n</math> ) { 
            則當前<math>x_i</math>爲方程的解答，退出循環;
           }   
     }

* 例如：c=28，n=33，e=3, 由步驟1求出a=13；
* 再由步驟2，求出當循環到i=2的時候得到滿足條件的<math>x_i</math>，<math>x\equiv x_2\equiv 28(13^{3-1}\bmod {33})^{3\times 3}\bmod {33}\equiv 28(169 \bmod 33)^9\equiv 28 \times 4^9\equiv 28 \times 262144 \bmod {33}\equiv 7 \bmod 33</math>

所以方程<math>28x^3\equiv 1\pmod {33}</math>有解x=7

== 來源 ==
* 《南昌理工學院學報》.李煌 


<<[[School:李煌數學研究院]]


[[Category:李煌数学研究院]]