多元一次不定方程解的结构及其应用

The solution structure of multivariate linear indeterminate equation and its application

初等数论是密码学研究的重要基础理论.引入多元一次不定方程的概念,利用多元一次不定方程解的存在性条件和二元一次不定方程一般解的结构,采用递推的数学归纳法,得到并证明了多元一次不定方程一般解及其特解的结构形式.进一步研究并给出了多元一次同余方程非负整数解的存在性条件,在此基础之上利用这个存在性条件对RSA公钥密码体制进行了密钥多元化的改进,论证了其加解密算法的正确性.最后通过例解说明改进后的RSA公钥密码体制较原密码体制更为安全可靠且易于实现.

Elementary number theory was an important basic theory of cryptography investigation.In this paper,the concept of multivariate linear indeterminate equation was introduced.The general solution and particular solution structure formulas of multivariate linear indeterminate equation were obtained and proved by using its existence condition of solution and the general solution of binary linear indeterminate equation,which recurrence mathematical induction was employed.Furthermore the existence condition of nonnegative integral solution for the multivariate congruent linear equation was researched and presented.The result was applied to improve the RSA public key cryptosystem by multivariate keys class.The correctness of its encryption and decryption algorithm was argued.The modified RSA cryptosystem was more safer than the primitive ones and it could be carried out easily through an instantiation in the end.