线性移位寄存器在安全RSA模数中应用的研究

Research on secure RSA modulus based on linear feedback shift register applications

运用线性移位寄存器(LFSR)序列模2个不同素数时的周期一般不同这一性质,尝试构造分解另一类RSA模数的方法;指出对于RSA模数n=pq的一个素因子p,当p2+p+1,p3+p2+p+1,…其中之一仅含有小的素因子时,给出的算法能够分解合数n=pq,并给出了一个基于三级LFSR分解合数的实例来说明算法的具体运算步骤。根据该分解算法,在选取RSA模数时,为确保安全性,除避免已知的不安全因素以外,还需要保证n的素因子p满足p2+p+1,p3+p2+p+1,…均包含大的素因子。

The periods of linear feedback shift register（LFSR） sequence modulo different primes were distinct in general.Using this property,a family of methods for factoring RSA modulus was constructed.For the RSA modulus n = pq,if the prime p satisfies that one of p^2＋p＋1,p^3＋p^2＋p＋1,…was composed of small primes factors,it proposed a method for factorizing the composite integer n=pq.An instance was proposed to illustrate the specific procedure of the proposed factoring algorithm.Based on this factoring algorithm,to make security assurance in selecting RSA modulus,and in addition to avoid the already known insecure factors,one should also make sure that the prime factor p of n must satisfy that each of the p^2＋p＋1,p^3＋p^2＋p＋1,…include a large prime factor.