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

一种改进的MC线性分拆加密算法
摘要:首先介绍了一种快速求解矩阵覆盖问题的算法,并对此算法进行了扩展,将原算法中向量的各个分量的取值范围扩大;在此算法的基础上改进了一种MC线性分拆的加密算法,对其安全性进行了简要的分析;最后给出的算例表明该加密算法密钥选取简单,同样具有加解密快速、简便的优点.
关键词:公钥加密体制;背包问题;矩阵覆盖(MC);线性分拆;加密算法;解密算法
,,,其破译的计算量比背包向量大得多,密文中不仅含有单个单元的信息,而且含有两两之间的关系信息,,将原先的MC线性分拆加密算法进行了改进.
1 原算法
2003年,张彪等[1]提出了一种快速求解矩阵覆盖问题的算法. 设矩阵
式中, . 则 MC 问题,
的解为:
若则;若则;X的其他分量,若,则;当,则.
2 扩展算法
本文作者扩展了上述的算法,将的取值范围扩展为,其中,.
设
式中,.
解二次背包问题的算法如下:
若,则.
b. 若,则.
c. 若,则([ ]表示取整).
证明a :当时,若,设,则
将等式两边同乘以,则
因而,.
证明b :当时,若,设,则
.
证明c:①当时,若,设,其中,是取整时舍去的小数部分. 令,则
产生矛盾,所以.
②当时,若,设,其中,,则
将等式两边同乘以,则
又因为,则,,所以
产生矛盾,所以.
综合上面①②两条证明,当时,有.
X的其它的分量按照上述算法依次证明,即
当,则;当,则;
当时,.
3 改进的MC线性分拆加密算法
按照上述算法对MC线性分拆算法[2]进行改进,改进后的算法将明文由原先的序列扩展为序列,但加密与解密的速度并没有受到影响.
设
,,
将分拆成个任意矩阵的线性组合,即. 可以直接将公开或者再作一些变换. 这里选择直接将公开.
为公钥,为私钥. 设明文,.
加密: ;
解密: ,
按照上述算法解二次背包问题.
分析此分拆体制的安全性,可以看出:(a)首先最初的矩阵A是一个一般矩阵,将它分拆不会将方程暴露给方程给密文分析者,所以对的取值是没有限制的,可以抵抗已有的一些破译方法[2];(b)再者这个体制是一个二次背包体制,所以二次背包体制具有的安全性它都具有.
4算例
取,,,,,;设明文序列为.
加密: ; .
解密: ;
解此二次背包问题
,所以;
,所以;
,所以
解得明文序列为.
5 结束语
现有的一些二次背包体制,它们的出发点基本上都是从一个一维的正整数超递增向量开始,将其转换为其他的矩阵形式,然后公开,最后解密时再将其还原,,它同样具有快速、简便的优点,所以可以将原先体制中的一