一种改进的MC线性分拆加密算法.doc

一种改进的MC线性分拆加密算法.doc:..一种改进的MC线性分拆加密算法摘要:首先介绍了一种快速求解矩阵覆盖问题的算法,并对此算法进行了扩展,将原算法屮向量的各个分量的取值范围扩大;在此算法的基础上改进了一种MC线性分拆的加密算法,对其安全性进行了简耍的分析;最后给出的算例表明该加密算法密钥选取简单,同样具有加解密快速、:公钥加密体制;背包问题;矩阵覆盖(MC);线性分拆;加密算法;•随着一次背包加密体制逐渐被破解,,,其破译的计算量比背包向量大得多,密文中不仅含有单个单元的信息,而且含有两两Z间的关系信息,所以破译的复杂性得到明显加强•本文利用扩展的快速求解矩阵覆盖问题的算法,,张彪等⑴\\ a\2 …a\n°21 a22 …a2nA=•• • •• • •_an\an2…ann_/-I式屮如>工%/,工勺+工勺=2,-••,/?).贝0MC问题c=XAXT,呵 详j J=iX=3,…心)w{0,1}"的解为:若c>ann则兀“=1;若c<%则£=();X的其他分量兀•(,=1,…,刃一1),若c-乞cijjX;巴5,;=/+1则=1;当c一工仙打,则x(==M2扩展算法本文作者扩展了上述的算法,将兀(,=1,…小)的取值范围扩展为{0,・・・,灯,其中kni,=\\a\2a22a2nanl%式中,~>疋(工勺+工勺)(Z=2,・・・/)・z#j zj y=i解k二次背包问题的算法如下:>k2ann,则xw=・若cv4山,则xn=・若ann<c<k2aIU1,则兀=Jc/%([]表示収整).证明a:当c>k2ann时,若x”<k,设xf}=k-r(0<r<k)t则£_1C=工勺兀勺=心k一r)2+工乞工+hjXjXj/=! 炸J将等式两边同乘以PS则Fc=k2altn(k-r)2+/(工⑷工+工终产•勺)<疋伙一r)2afm+annf=l 详j"©”+(皿-2RS+1)%S因而c<k2ann,这与c> “=:当CVQ加时,若£>0,设xzz=r(0<r<Z:),则n—1+7ax1+7a^xx>a/ ijnn/=! iwj这与cvd””产生矛盾•由反证法得X”=:①当ann<c<k2ann时,若x”>[jc/九J,设£=jc/%+厂-/,其屮0<<k-\yjc/aiin\fF是Qc/%[c7a~=s,贝!J71—1C=Yauxixj=%S+厂一02+工色工+Ea^Xjij z=l 详j=anns2+ann(r2+V+2rs-2rt-2刃)+工给#+工鶴必巧/=! 详j2=%S+%[(厂—f)2+2s"-f)]+£%工+Y,aijXiXJi=\ &j=C+a