背包密码破译原因分析与加法扩散技术引入研究
文章编号：1001-9081（2012）03-0694-05
doi：10.3724/sp。 J. 1087.2012.00694
重新理解背包公共密钥密码的安全性
丁·Yanyan，Fei Xiangdong，Pan
郁闷
（南京科技大学经济与管理学院，南京210009）
通讯作者电子邮件panyu@njut。 edu。 CN）
挑选
关键字：考虑到背包密码反复解密的情况，已经分析了原因。它指出，背包公共密钥序列是从初始序列得出的，初始序列为
该列是由易于分解的背包形成的，并且有冗余，因此背包公共密钥序列不能完全随机。使用这些冗余是成功破译的必要物品。
当前，大多数解密的背包密码仅使用混乱的技术，例如模块化乘法操作，这不足以隐藏初始序列的冗余。为此，其他
分散初始顺序的冗余的方法扩散技术使攻击者在解密过程中很难使用。它提供了示例以说明两种类型的扩展类型：内部扩散和术语间扩散。
分裂技术。分析表明，在使用扩散技术后，它可以抵抗当前已知的攻击方法。
关键字：背包公共密钥密码；冗余;模块化乘法操作；混乱;扩散
中国图片分类编号：TP309.7； TN918.4
文档代码：
SecurityRecasspublic-keycryptosystem
Dingyan - Yan
feixiang-加
panyu
（NA
技术的nguniversity，Nanjingjiangsu210009，中国）
摘要：关于knapsackpublic的提交 - keycryptosystemhasbeenbrokentey，本文
分析这些。 Itisexpoundedthataknapsackpublic- key sequenceSgeneratedBytransFransFormingAnitialSequence
组成的knapsackAckproblembromblebrembromblecredrymency;因此，aknapsackpublic - keysequenceSunlikelyComplet
随机的。目前，大多数破裂
最初序列的纵向不体育。 ITISNESSSNERSERARYTOUTILIZE
山埃及道
加密系统。所以。加法被引入了thispapertodifusethendenceofanitialsequence，因此
破坏丙烯酸系统时的thataneversary callnotmakeuse。内部 - iTemDifusionAndinter-项目
扩散是eillustrupt的。 Theanalysiscondece探讨了已知的AttackSwithDiffusion。
关键字：knapsackpublic - keycryptosystem；冗余;模块化；困惑;扩散
介绍
自1978年至1990年代以来，已经提出了背包密码。
公共密钥密码学领域的热门研究主题被认为是最有前途的加密算法。
背包密码的安全性是基于查找子集和问题的困难以及设计想法
它是为了掩盖易于解决的背包问题，看似困难的背包问题。
它是使用陷阱门。陷阱门信息仅由法律收件人作为私钥控制。
使用它来将问题恢复到易于解决的背包问题，然后轻松解决它
可以用纯文本重建背包；对于非法收件人，最好将纯文本从密文恢复到
有必要解决困难的背包问题。但是有以下问题：
如果隐藏不足，攻击者可以从公共密钥中解决相应的陷阱。
信息;如果足够隐藏，则可以降低背包密度。科斯特等
证书
密度小于0.9408的背包密码容易受到低密度子集和
攻击;如果背包密度大于1，则会导致解密不一致。因此，结构
一
安全的背包密码非常困难，并且其中大多数目前都被打破了
翻译后，通常认为背包密码的前景是昏暗的
。
但是，由于快速加密和解密背包密码的优势以及背包问题的NP
完整性（NP完整，NPC），特别适用于某些资源受限的
在这种情况下，背包密码仍然非常吸引人，许多人仍在打破它
背包密码已反复解密并努力工作。
王的密码
最近，Wang Baocang等
提出了基于随机背包的公共密钥密码（简单）
称其为Wang的密码），人们认为此算法不仅具有背包密码的一般优势，而且还具有
它基于随机背包问题，而不是易于解决背包问题，并且是有效且安全的
的。
如果背包密码是基于随机背包而不是易于使用的背包
问题在于，公共密钥序列是从随机初始序列转换的，因此攻击
用户从公共密钥中进行的推论将无法验证，并且加密算法必须是
牢不可破。但是，本文指出，王的密码不是基于随机背包。
初始序列是规则的。分析表明，使用基于网格的标准算法
和
数字规划方法可以用无可符合的概率解密。
1 1
王密码的简要说明
关键一代
随机选择n背包项目以形成初始序列u =
（“，”，“，⋯，”），其中u是一个正整数，序列v =（。
。 ，，，，
⋯
，，，，
），vi =
12⋯（i = l，2，⋯，n）。选择任何不同的素数P
Q，令人满意：
fp>
lzi
（1）
【
Q> 2 max {∑
一
vi）u
我 （ ”
使用中文残差定理计算序列a =（a，a：，⋯，a），0≤
a≤pq-1，大多数p，。 ￡“（MODP），AF
（ro OD Q）。这里是
采用Modulo n = pq的非负值最小残差。输出背包序列
对于公共钥匙，P和G
是私钥。
加密
n位长度二进制明文（m）::（mm：⋯m），其中
收到的日期：2011-09-26;回复日期：2011-12-01。
基金项目：江苏省软科学研究项目（BR2010080）。
作者资料：丁·Yanyan（Ding Yanyan（1987 I），女性，来自Wuxi，Jiangsu，硕士学位，主要研究方向：管理决策，商业智能； Fei Xiangdong（1966 I），男性，来自Wuxi，江苏，高级工人
Cheng Master，主研究指示大师：加密算法，安全协议； Pan Yu（1955年I），男性，来自江苏省南东，教授，医生，主要研究方向：计算管理，商业智能。
问题3
丁Yanyan等人：重新理解背包公共密钥密码的安全性
695
M = 0或1，被加密为C：A1M1 + A2M2 +⋯ +。 m。
解密
收到密文C后，计算CP：C（mod p），c。 ：
C（mod g），此处c。采用Modulo P的非负最小残差，
绝对最佳模型G
剩下的小，纯文本（m）::（cc。）。
1.2
王密码的非随机性
公共密钥序列a =（a1，a2，⋯，a），ciphertext c = a1ml + a2m2 +
⋯ +om，其中m = 0或1，这是一个0-l背包问题，背包密度定义
IS：d：n/lb（最大0）。
公共密钥序列A由初始序列U和
在中国的残余定理转变之后
序列u的术语
该项目问题之间的区别是2⋯
序列，“ =
+ 2⋯（i = 1，2，⋯，n）。也就是说，序列
这是一个序列
堆叠
为形成添加一个超注重序列。
由于0≤a≤pq-1，因此公共密钥术语A的最大长度（数字数）不大
在PQ的长度上，即：LB（Max A）≤Lb（PQ）。根据公式（1），P的长度
长度大于其长度，Q的长度大于V的长度。
如前所述，背包密度必须大于0.940 8，以确保安全，即PG
长度必须小于N/O。 940 8。
因此，不能随机选择初始序列U的术语IT值。例如：IT =
，但
= 2
一个2
，，，，
长度为2n至1位，PG的长度确定
它必须大于N/O。 940 8位，背包密度小于0.940 8。
为了确保背包密度大于0.940 8，U和
长度必须尽可能长
能量很小，特别是对于U和U，差异是最大的，是2
。
确保
和
尽可能小的方法是采用非常小的绝对值
负数，最大长度为长度。目前，Q的最大长度R必须
必须满足以下关系：
0.940 8
<，（n 2 + r）
现在
r <0.062 9N + 0.940 8。
每个项目的长度小于Q的长度，即
是一个负数的负整数，数字小于r
数字。目前，序列U中的项目可能不会形成超级灌溉关系，而是
绝对值
小于2-1，因此存在以下关系：
+（2-1）> it + l +
+2 +⋯ +
上述关系等同于超级知识关系，该关系适合使用整数编程方法查找
解开。在公式中，P的长度大得多，远大于Q的长度。您可以参考[7]中的文章
找出佛法
和P，从而破解整个算法。
重新理解背包公共密钥密码的安全性
2。1
背包密码的安全性
背包公共密钥序列与随机数序列不同，因为前者来自初始序列。
该列已转换，并使用它隐藏陷阱门。可以将初始序列视为添加
将初始顺序转换为公钥的过程可以视为加密过程。
背包公共密钥序列被认为是加密的密文。从计算复杂性的角度来看，
如果加密过程（从初始序列到公共密钥的转换过程）是安全的，那么
从密码（公共密钥）中解解算法在时空非常复杂，并且
相当于解决NPC问题，该算法被认为是安全的
背包公共密钥密码。
初始序列由易于解决的背包形成，并具有某些规则和特征，例如MH
背包中初始序列的超级插入性，王密码中初始序列的差异
超级增量。这些定律和特征构成了初始顺序的冗余
，冗余
作为算法的一部分，学位被披露。背包公共密钥序列作为初始序列
列转换的最终结果仍然是这些冗余。实际上，任何公钥秘密
代码的公钥必须隐藏全部或部分私钥信息，并且没有完全随机性。
公钥。
如果初始序列是一系列随机数，则其冗余性为零，由于解密
即使仅执行一次MH，也无法搜索和验证密钥。
包
不可能破译，无论是攻击的方法
，或Shamir攻击
]，必须使用初始序列的冗余来解密所有内容。利用初始序列
列的冗余是成功破译的必要条件。其中，Shamir攻击方法
唯一的解决方案距离是4，也就是说，攻击者至少需要使用超侵入性初始序列。
4个项目。
一
背包公共密钥算法是安全的，必要的条件是防止其破裂。
翻译器利用了公共密钥的初始顺序的冗余。
2.2
混乱和传播
Shonnon
提出了两种隐藏加密消息中冗余的方法：
混乱和传播。
混乱是指加密过程中明文，密钥和密文之间的联系。
该系统尽可能复杂，可以掩盖纯文本和密码文本之间的关系。基本方法是
而是使用密码字符代替普通字符。除非关键长度没有限制，例如
“
一
“一个秘密是下一次”，否则仅使用混乱是不够的。
扩散意味着每个纯文本的变化都会尽可能影响密码文本。
更改，将纯文本的冗余分散到密文中；也指每个钥匙的影响
尽可能扩展到密文。基本方法是换位（也称为置换）。
通常，仅扩散很容易被解密。
无论是“混乱”还是“差异”，都必须是可逆的，也就是说，通过反向
可以将初始数据恢复到操作。
2.3
模态乘法操作
有很多方法可以实施混乱
：数据加密标准（数据
加密标准，DES）使用S-box，国际数据加密算法
（国际数据增强算法，想法）使用模型乘法和运输
计算。背包公共钥匙适合模拟乘法以实现混乱。
模块化乘法操作表示为：
b§wu（ro od m1
其中：m是模量，称为乘数，u是乘数，b是模量m的其余部分。
存在以下关系：
B = WU - K
（2）
在
是一个积极的整数。
背包加密系统中的模块化乘法操作是整数中的乘法组操作
在现场，使用一个整数而不是另一个整数。
优势是
和“当更大时，雪崩效应是显而易见的，即
或更改
一
位会导致b的急剧变化。
缺点是转换是线性的：乘数中的每个位均在取模p之后平等扩展。
您之间的原始关系仍然保持模量整数域，tt
生存的冗余完全被完全传递到B中，并很容易被破译者利用。例如：u
有一个共同的因子g和m。从公式（2）中可以看出，g也是b的因素。
即使通过多个模量乘法操作构建了多个MH背包，它们仍然不够。
隐藏初始序列的冗余，解码器可以从公共密钥序列中使用该序列
冗余，然后解密
。
Wang的密码仅使用中文剩余定理进行迭代转换，并且关系
如下：
“
a k。
一个k
其中i = 1，2，⋯，
。可以看出，中国剩余定理形成的相关性
该系统实际上是模块化乘法操作关系。在公式（2）中，当w = 1时，两个是和谐的
相同的。
此外，Wang Baocang和其他人还具有使用中国剩余定理的公钥算法
模块化乘法的迭代结构
，这也很容易被解密，并简要描述算法
如下：
选择6个不同的素数P.，p，⋯，p6，其长度为k = 333
点，令n = p p2⋯
。可选的6阶可逆矩阵M =（
） ，在
696
计算机应用
第32卷
。 ，长度不超过30位。记住矩阵
逆的
〜。由中国剩下的
理论上计算0L，O2，⋯，06，满足Ni E. L1（Rood P1），1 I
21（Rood
p 1），⋯，0l lan。 61（根P1）; ⋯;
6测量端口L6（Rood P6）。 6三
026（ro od p6），⋯，。 6;。 66（Rood P6）。 ‰ 模型
有一个逆元素6。计算
B1; BA1（MODN），⋯，B5§ba5（root n）。公共钥匙是模块化的，b
。 - ，，，
b;私钥是。 ，p
一，
和矩阵M。
解密方法简要描述如下：
使用基于网格的调节算法
找到B的逆元素
，特定方法参考
解密方法的前部分n
。 ，再次找出答案。 ，，，，
，⋯，n。因为
n是由中国残留定理产生的，因此（％-a）的存在最大
公共因子P（这是初始序列Pi，⋯，
冗余），n
长度不是
有30多位数字，所以我会筋疲力尽。
每当您猜测，验证上帝时，这都是可行的（
一
。
）大于1，如果是这样，则p = ged（.6一个。
n），这可以
破译算法。
总而言之，从当前的研究中，仅通过模块化乘法操作或中国残留定理
构建的背包公共密钥算法都是不安全的i4'”
，原因是仅使用
混乱的技术无法完全隐藏初始序列的冗余。
2.4
加法扩散
如上所述，该仪器无法通过依靠混乱技术来确保安全，需要引入和扩展
散射技术以分散初始序列的冗余，因此很难利用破译。
扩散技术有很多类型
，基本方法是转移位置，例如DES，但正确
对于背包密码，转换将导致其他更改和携带，这很难还原。
换位方法不适用； Idea使用模块化添加和模块化独家或操作来实现扩散。
背包公共密钥密码的背包值是初始序列项及其转换表。
子集和。由于添加易于通过反操作减法恢复原始值，因此
该序列的冗余适合通过添加扩散。
不同背包公共密钥的初始顺序中包含的冗余不同，因为
用于分散这些冗余的添加剂扩散技术也不同，必须基于
取决于特定情况，但有两个一般原则：一个是Modulo乘法操作的基础
此外，进一步增强了雪崩效应；其次，它使Deciphers很难根据公共钥匙使用它
初始序列的冗余。
从形式的角度来看，加性扩散技术被分为术语内扩散和期限扩散技术
技术。将一部分分为两个部分，彼此叠加，然后隐藏冗余，这称为项目内扩展
分散;这些项目彼此叠加，隐藏冗余，这称为术语间扩散。
基于IN-INEM扩散技术的背包公共密钥密码
以下使用模式乘法操作和中国残留定理，结合了术语内扩散技术，
构建一个新的背包公共密钥密码。
3.1
算法描述
1）采用超级插入初始序列：
b ：（ bl，⋯，b，⋯，6）; b1 = max（b），i = 1，2，⋯，n
2）选择共同元素的正整数
和M，满足
∑b <m <2b，
3）使用乘数在序列B上执行B上的Modulo乘法并转换B
序列D：
d￡Wb（ro od m）
D ：（ D，⋯，D）
其中d（i：1，2，⋯，n）可以是n + 1位。
4）不对称组的D：D的长度在N + 1位中测量（例如高位
从左至第一个位置不足，算作0），分为两个部分：左右，形成
和
，，，，
位的数量分别为n + 1
在哪里
》 n + 1一个，d =
m bei 2
1， +
。
5）选择整数t，满足（
+ t
）<2-l。令“ =
。 + t
。 ，，，，
在这里”：“”是指作业。容易看，
长度保持不变，以确保背包的密度。
6）选择相互元素的正整数p和g以满足：
∑
我】
∑
使用中国残差定理，生成公共密钥a =（o
- 。 ，n），IE0≤
R上的≤pg-1，R，
兰花
（roodp），嘴三
（mod g），i = 1，2，·一个，n。
私钥是：p，q，t，〜，m。
初始序列
作为固定值嵌入算法中。
3.2
加密
二进制明文
:(
，：，⋯，，
），
是0或1，加密为C =
（0L L + .2 2 +⋯ +血液
）。
3.3
解密
1）计算II：C（roodp），，
= c（ro od q）;
2）计算d =（
-电视）
2“'+;
3）计算y：
d（root m）;
4）使用超插入初始序列B来计算纯文本。
3.4
安全分析
步骤3）第3.1节的第6和6）是模块化乘法操作，这是混乱的技术。
步骤4和5）实施不对称的分组，将D分为左右两部分。
左侧部分比右侧大得多。右侧由T时间扩展，然后叠加在左侧部分以弥补B
和
数值很小，在模量乘法操作的结果中，雪崩效应可能并不明显。
做b。和
轻微的变化遍布整个项目。非对称分组和扩展
扩展和叠加技术是项目内扩散技术。
背包公共密钥密码的主要攻击包括明文恢复攻击和密钥恢复
攻击。前者是指从密码文本中求解纯文本，而后者则是指从公共密钥中搜索。
钥匙。
3.4.1
纯文本恢复攻击
如上所述，背包密度必须为0.940 8-1。 n：5 12
例如：
1）选择超级插入初始序列B ：（ b，b，⋯，b
1，B :)。
2）选择互斥
M，M可以至少选择513位
相互质量的正确性
数字。
3）申请
和m，在序列B上执行模量乘法并将其转换为序列D：
di wb（ro od m）; I：1，2，⋯，512
D的最大长度为513位。
4）不对称分组D：以513位的长度测量，从左至352
该位置的位置分为两个部分：左右，形成
和
，长度分别为352位
和16 1位，D：
％2
。
5）选择整数t，满足（
+ t
）<2。
〜1，
和
长度差
191位，t可以将整数超过1013位；让你：n + t
（I：1，
2，⋯，5 12）。我的长度仍然是352位。
6）选择相互元素的正整数P和Q以满足：
5 F 2
∑
∑
i = l
使用中国剩余定理，生成公共密钥a =（口。，o：，⋯，口
）。
P和Q的长度如下：
将512 U添加在一起，最大膨胀为LB 5 12：9位，因此P的长度可以是
361位。同样，Q的长度可以为170位。
因此，公共密钥A的每个项目的长度小于361 + 170 = 531位。背包密度
D = 512/53L = 0.964 2，在安全区域。
问题3
丁Yanyan等人：重新理解背包公共密钥密码的安全性
697
3.4.2
钥匙恢复攻击
本文中该算法的初始序列B是固定的，可以披露。因此，安全
必须能够承受类似于某个对称密码的“已知明文攻击”。
首先，如果攻击者突破了公共密钥的第六步，中国剩余定理是
覆盖你和
序列，因为d =（“电视）
2”
，必须猜测
获得T后，使用网格攻击或Shamir攻击方法
继续
解密。第3.4.1节解释说，对于512个背包密码，T可以是100位。
对于上述整数，猜测T是不计算的。因此，t的存在使解密者
很难获得D序列，并且不能从公共密钥中使用初始序列和冗余。