广义数域筛法对公钥加密算法的攻击

The GNFS Attacks to the Public-key Encryption

广义的数域筛法(GNFS)是目前最快的整数分解方法,由于公钥加密算法(RSA)是建立在大整数很难分解的基础之上的,所以GNFS也是RSA公钥加密算法最有效的破解方法之一,09年末就有科学家通过NFS成功分解了768bit的大整数RSA-768,本文将结合RSA-768的破解过程,分析GNFS的分解原理和步骤。

The General Number Field Sieve algorithm （ GNFS ） is the fastest known method for factoring large integers. The RSA relies upon the fact that it is computationally difficult to factor a ＂large＂ integer into its component prime integers, so the GNFS is one of the most effective ways to crack the RSA. By the end of 2009, scientists had successfully factored the 768bit large integer （ RSA - 768 ） by the number field sieve （NFS）. This paper will analyse the principles and procedures of the GNFS＇ s decomposition, combining the cracking process of the RSA -768.