一个改进的MC线性分拆体制.doc

一个改进的MC线性分拆体制摘要：作者：赵中强 - 相关文章关键词：类别：专题技术来源：牛档搜索（Niudown.COM）本文系牛档搜索（Niudown.COM）根据用户的指令自动搜索的结果，文中内涉及到的资料均来自互联网，用于学习交流经验，作品其著作权归原作者所有。不代表牛档搜索（Niudown.COM）赞成本文的内容或立场，牛档搜索（Niudown.COM）不对其付相应的法律责任！一种改进的MC线性分拆加密算法赵中强收稿日期：2005-05-20作者简介：赵中强（1978-），男，浙江长兴人，助教，主要从事信息系统、信息安全方面的研究.，房道伟（河海大学 商学院，江苏 常州 213022）摘要：首先介绍了一种快速求解矩阵覆盖问题的算法，并对此算法进行了扩展，将原算法中向量的各个分量的取值范围扩大；在此算法的基础上改进了一种MC线性分拆的加密算法，对其安全性进行了简要的分析；最后给出的算例表明该加密算法密钥选取简单，同样具有加解密快速、简便的优点.关键词：公钥加密体制；背包问题；矩阵覆盖（MC）；线性分拆；加密算法；解密算法中图分类号： 文献标识码：A背包加密体制是公钥加密体制的一种.它利用一般背包问题的无确定性解和超递增背包问题的有确定性解来进行加密与解密.随着一次背包加密体制逐渐被破解，人们又提出了二次背包加密体制.二次背包加密体制是建立在矩阵覆盖问题之上，可以有力对抗已有的破译一次背包体制的方法.二次背包加密体制用矩阵替代一维向量进行矩阵覆盖，其破译的计算量比背包向量大得多，密文中不仅含有单个单元的信息，而且含有两两之间的关系信息，所以破译的复杂性得到明显加强.本文利用扩展的快速求解矩阵覆盖问题的算法，将原先的MC线性分拆加密算法进行了改进.1 原算法2003年，张彪等1提出了一种快速求解矩阵覆盖问题的算法. 设矩阵式中 ， . 则 MC 问题 ，的解为：若则；若则；X的其他分量，若，则；当，则.2 扩展算法本文作者扩展了上述的算法，将的取值范围扩展为，其中，称之为二次背包问题.当时就是上述介绍的原算法.设式中 ，.解二次背包问题的算法如下：a. 若，则.b. 若，则.c. 若，则（ 表示取整）.证明a ：当时，若，设，则将等式两边同乘以，则因而，这与产生矛盾.由反证法得.证明b ：当时，若，设，则这与产生矛盾.由反证法得.证明c：当时，若，设，其中，是取整时舍去的小数部分. 令，则产生矛盾，所以.当时，若，设，其中，是取整时舍去的小数部分.令，则将等式两边同乘以，则又因为，则，所以产生矛盾，所以.综合上面两条证明，当时，有.X的其它的分量按照上述算法依次证明，即当，则；当，则；当时，.3 改进的MC线性分拆加密算法按照上述算法对MC线性分拆算法2进行改进，改进后的算法将明文由原先的序列扩展为序列，但加密与解密的速度并没有受到影响.设，将分拆成个任意矩阵的线性组合，即. 可以直接将公开或者再作一些变换. 这里选择直接将公开.为公钥，为私钥. 设明文，.加密： ；解密： ，按照上述算法解二次背包问题.分析此分拆体制的安全性，可以看出：(a)首先最初的矩阵A是一个一般矩阵，将它分拆不会将方程暴露给方程给密文分析者，所以对的取值是没有限制的，可以抵抗已有的一些破译方法2；(b)再者这个体制是一个二次背包体制，所以二次背包体制具有的安全性它都具有.4算例取，；设明文序列为.加密： ； .解密： ；解此二次背包问题，所以；，所以；，所以解得明文序列为 .5 结束语现有的一些二次背包体制，它们的出发点基本上都是从一个一维的正整数超递增向量开始，将其转换为其他的矩阵形式，然后公开，最后解密时再将其还原，最后去解一个简单背包问题.从前面推导的解二次背包问题的算法来看，它同样具有快速、简便的优点，所以可以将原先体制中的一维的正整数超递增向量直接用矩阵来替代超递增向量，这样就可以简化中间的一些变换过程，使得密钥的选取更加简单.参考文献1 张彪，王立华.一种新的MC公钥密码体制J.哈尔滨工业大学学报，2003(1)：126-128.2 曹珍富.公钥密码学M.哈尔滨：黑龙江教育出版社，1993.An Improved Encryption Algorithm Based on Linear Decomposition of the Matrix Cover Problem ZHAO Zhong-qiang, FANG Dao-wei(College of Commerce, HoHai Univ. , Changzhou 213022, China)Abstract: Firstly introduce an algorithm resolving Matrix Cover Problem rapidly, extend it and enlarge the scope of the vectors members values. Then improve an encryption algorithm based on this extended algorithm, analysis its safety simply. Lastly give an example of this encryption algorithm, which shows that the selection of the key becomes simple, and this algorithm has advantages of fast encryption and dec