背包公钥密码体制的数学理论研究

《背包公钥密码体制的数学理论研究》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第25卷第5期湖南工业大学学报VO1．25NO．52011年9月JournalofHunanUniversityofTechnologySep．2011背包公钥密码体制的数学理论研究李步军，王继顺(1．淮海工学院理学院，江苏连云港222005；2．连云港高等师范专科学校数学系，江苏连云港222006)摘要：对背包公钥密码体制的数学理论进行了研究，给出了背包单射加密函数的一个充分必要条件，以及获得单射加密函数的方法，并给出了背包公钥密码体制中的3个数学结论。关键词：背包问题；背包公钥密码体制；单射加密函数中图分类号：TN918．1文献

2、标志码：A文章编号：1673-9833(2011)05—0026—03MathematicalStudyontheKnapsack—TypePublicKeyCryptosystemLiBujun，WangJishun(1．SchoolofScience，HuaihaiInstituteofTechnology，LianyungangJiangsu222005，China；2．DepartmentofMathematics，LianyungangNormalCollege，LianyungangJiangsu222006，China

3、)Abstract：Themathematicaltheoryofpublickeycryptosystemisstudied．ThenecessaryandsuficientconditionsforKnapsackinjectiveandcryptographicfunctionandthefunctionacquiringmethodarepresented．Asaresult，threemathematicalconclusionsinknapsack-typepublickeycryptosystemareobtained

4、．Keywords：knapsackproblem；knapsack-typepublickeycryptosystem；injectiveandcryptographicfunction1研究背景在实际应用中，加密者首先使用公钥A=(a。，以2，⋯，)，通过计算b=fo(x)=x1a1+口2+⋯+，对明文1949年，C．E．Shannon发表了《保密系统的通信胤，x2，⋯，xn，xi∈{0，1)进行加密，然后将密文b发送理论》一文，使密码学成为～门真正的科学。作为给信息接收者，接收者利用其私钥可将密文恢复为一门应用性较强的学科，密

5、码学有坚实的数学理论明文而对密码系统的攻击相当于解决一个背包问基础，在代数学、数论等知识的基础上，出现了基题。本文对背包公钥密码体制问题从数学理论方面于多项式理论的序列密码，基于数论知识的RSA⋯作些探讨。和EIGamal等公钥密码。背包密码是一种基于背包问题的公钥密码，2主要结论该问题就是从背包向量A：(口，，⋯，口)(a∈Z)中求出所有的a，使其和等于给定的正整数b。背包问题如果背包问题存在多个解，这时密文b就对应是一个NP完全问题口，背包公钥密码体制的安全性多个明文，解密后信息接收者会得到不确定的明文，就是基于该问题的难解性。

6、然而对于超递增的背包因此要求加密函数)a1坝2a2+⋯+口是单射，定向量【4J，却存在解决问题的简单方法。理1将给出背包单射加密函数的一个充分必要条件。收稿日期：201卜05—26，基金项目：淮海工学院特色专业建设基金资助项目(5509007)作者简介：李步军(1971-)，男，山东临沂人，淮海工学院讲师，硕士，主要研究方向为信息安全及系统分析，E—mail：lbjbjIs@yahoo．com．ca第5期李步军，等背包公钥密码体制的数学理论研究27定理1函数fo(x)=xlal日2+⋯+Xna(af∈)是示成其它若干个元素的和或差。

7、单射(A为单射背包向量)的充分必要条件为：背包假设=aj+ap一日口，则ai+aq=aj+ae。由于ai,aj，，日q向量A=(aI，a2，⋯，口)的每2个分量，aj都不相等，且中一定有一个最大者，不妨设f最大，从而口，，a每个分量都不能表示成其它若干分量的和或差。必在a前面。由于a比它前面所有项的和还大，所证明用反证法以a?af+ap+a口，这与af+以q=+矛盾。1)必要性根据1)，2)和定理1，推论1得证。若背包向量A=(口，，．．．，a)有两个分量ai,aj相等，定理2设c=(c1，c2，⋯，C)(cEz)，为n维超递设它们

8、对应的系数x，不相等，则增的背包向量，正整数m，f互素且，，z>cl+c2+⋯+c，则厂dlX2⋯Xj⋯『_I·)=1X2⋯⋯X{．．·)，由模乘运算ai=lc％对C『_(c，c，⋯，c)伪装后所得向量因此函数()不是单射。A=(口1