Chebyshev多项式在公钥密码中的应用

发布时间：2018-07-26 11:26

【摘要】：随着通信技术的迅速发展,公钥密码体制在政治、经济、军事等领域的应用越来越普遍和深入,随之而来的公钥密码体制的安全性问题也受到人们越来越多的关注和重视。本文对近年来提出的若干基于Chebyshev多项式的公钥密码系统进行研究,并利用可证明安全的思想对密码体制的安全性进行了较为全面的论证,指出了在某些情况下有限域上的Chebyshev公钥密码系统的安全性与解离散对数等价,某些情况下要高于求解离散对数。Chebyshev多项式的迭代定义可以看成一个线性移位寄存器序列,利用这一性质,本文首先研究了有限域上Chebyshev多项式的周期,详细分析了周期对密码体制安全性的影响,并对参数的选择提出建议：在模P的情况下,P-1和P+1应分别有一个大的素因子,这样可以有效的避免小周期对密码体制的安全性影响。比较了三种有限域和有限环上的Chebyshev公钥密码体制的优点和缺点,利用孙子定理和周期的性质给出了有限环上的Chebyshev公钥密码体制的快速算法。这种快速算法大大减少了位操作,并且允许并行计算,对运算速度的提升非常明显。RSA, Lucas和Chebyshev公钥密码体制都是Dickson多项式的应用,本文通过研究Chebyshev多项式的周期类比它们的周期,从周期的角度分析了这些密码体制的安全性,并对参数的选择提出了建议。通过周期的研究,指出循环攻击本质上是对小周期的攻击,针对类RSA公钥密码系统提出了一种效率更高的攻击。循环攻击需要对密文重复进行幂运算,这种攻击只须密文自身多次相乘即可。为了抵抗循环攻击,RSA系统里的N=pq应满足p-1和g-1有一个大的素因子,本文结合欧拉函数的性质给出了一个简洁的证明。
[Abstract]:With the rapid development of communication technology, the application of public key cryptosystem in the fields of politics, economy, military and so on is becoming more and more popular, and the security of public key cryptosystem has been paid more and more attention. In this paper, several public-key cryptosystems based on Chebyshev polynomials are studied, and the security of cryptosystems is demonstrated by using the provable security idea. It is pointed out that the security of Chebyshev public key cryptosystem over finite fields is equivalent to the solution of discrete logarithm in some cases, and in some cases the iterative definition of Chebyshev public key cryptosystem is higher than that of solving discrete logarithm. Chebyshev polynomials can be regarded as a sequence of linear shift registers. Using this property, the period of Chebyshev polynomials over finite fields is studied in this paper, and the effect of period on the security of cryptosystems is analyzed in detail. Some suggestions are put forward for the selection of parameters: in the case of module P, there should be a large prime factor for P-1 and P1 respectively, which can effectively avoid the effect of small period on the security of cryptosystem. The advantages and disadvantages of three kinds of Chebyshev public key cryptosystems over finite fields and finite rings are compared. The fast algorithm of Chebyshev public key cryptosystems over finite rings is given by using Sun Tzu Theorem and the property of periodicity. This fast algorithm greatly reduces bit operation, and allows parallel computation. The increase of computing speed is very obvious. RSA. Lucas and Chebyshev public key cryptosystems are all applications of Dickson polynomials. In this paper, we study the periodicity of Chebyshev polynomials to compare their periods. The security of these cryptosystems is analyzed from the point of view of periodicity, and some suggestions on the selection of parameters are put forward. Through the research of periodicity, it is pointed out that cyclic attack is essentially a small period attack, and a more efficient attack is proposed for RSA like public-key cryptosystem. Cyclic attacks require repeated power operations on ciphertext, which requires multiple multiplications of the ciphertext itself. In order to resist the cyclic attack, the N=pq in N=pq system should satisfy p-1 and g-1 with a large prime factor. In this paper, we give a simple proof combining with the properties of Euler function.
【学位授予单位】：中南大学
【学位级别】：硕士
【学位授予年份】：2014
【分类号】：TN918.1;O174.14

【共引文献】