Vol． 24 ＲSITY 2014 年 6 月 收稿日期：2014-03-09 作者简介：陈成刚（1976-），男，山东省荷泽市人，副教授，硕士，主要从事大学数学教学和概率统计研究。 一种破解背包公钥密码体制的确定性方法 陈成刚（天津城建大学理学院，天津） 摘要：背包公钥密码体制的破解方法不同于一般的统计分析方法，主要利用公钥（加密）密钥的超可达性，直接从公钥中解密私钥（解密）密钥，从而达到解密密文的目的。 关键词：干扰点；目标；增性；超增性；可达；超可达 中图分类号：TN918。 文献标识码：A 文章号：1009 背包问题的定义 公钥密码体制一直是密码学研究的重要领域之一。 1979年，和提出了背包公钥密码体制。由于背包序列在转换机制上的薄弱，1983年，和的背包公钥密码体制被彻底破解。但由于基于背包问题的公钥密码体制加密解密速度快，因此许多更复杂的公钥密码体制被提出。本文利用密钥的超可达性，提出了一种新的确定性方法破解背包公钥密码体制。所谓背包问题：就是给定若干个重量不同的物品，能否把这n件物品中的若干个放入一个背包，使得它们等于给定的重量L？这个问题就是要找到x=1，2，…，n，使得它们都是正整数。
显然，背包问题的解是一个NP完全问题。如果我们直接求解，例如取n=100，用每秒搜索10种的计算机去穷举搜索，一年只能完成3.次，完成全部搜索需要2（年），这在时间上显然是不允许的。递增和超递增的序列称为超递增背包问题。并不是所有的背包问题都难以求解，如果背包密钥是超递增的，那么这个背包问题就是超递增背包问题。超递增背包问题有一个快速解法： ）即为所求解（明文）。 例如：L=120，背包公钥密码体制又称为非对称密码体制，它是这样设计的：用于加密的密钥与用于解密的密钥不同，并且无法根据加密密钥计算出解密密钥（至少在合理的假设时间内）。加密密钥可以公开，任何人都可以用加密密钥加密信息，但只有相应的解密密钥才能解密信息。在背包公钥密码体制中，解密密钥是一个超增向量，但加密密钥不是超增向量。利用解决一般背包问题的复杂度，只有持有解密密钥的合法用户才能解密明文，而持有加密密钥的其他人则无法解密明文。 密码的选取解密密钥是一个三元组（C，t，p），其中1，2，…，n为正整数）是一个超增向量，p（），其中“mod”为“取模”运算，z满足加密。背包公钥密码的加密是将明文X乘以加密密钥B。背包公钥密码的解密是通过密文L和解密密钥（C，t，p）得到明文X，如下所示：（2）由间接密文L'和超增序列C，利用1。在讨论解密方法之前，我们首先给出以下定义、引理和定理。引理和定理的详细证明可以参见参考文献。1，2，…，n为正整数。 对于一个n维背包向量A,则i成为A的一个扰动点。定义3. mod m) i = 1, 2, ..., n。
记为 ，则B为（A，z，m）超可达。记为 如定义3所述，若能找到一个三元组（C，t，p），则它的整数部分。 引理3.三元组（A，z，m）有目标（C，z，p）当且仅当[za]的所有干扰点i都成立，且若）满足（ub 解密方法给定加密密钥B和定理3.1，可得到以下解密方法： 首先，找到满足以下条件的正整数u，m，z和向量A： 中最大的数； (2) modm），i=1，2，…，n）增加； 4）公式成立； 其次，从上面三元组(A,z,m)中，找出满足如下条件的非负整数t，p，k和向量C： 通过上面的计算，可以得到三元组(C，z，p)，这就是三元组(A，z，m)的目标，也就是所需要的解密密钥。 利用这个解密密钥和 2.验证解密方法的正确性 下面举例验证 3.解密方法的正确性： 假设给定加密密钥B，首先可以得到解密步骤为 m=23，u =14，z(2，3，9，12)； 其次由所得到的m，u，z可进一步得到A=38，t=23，C(4623)mod38=32(1，0，1，1)显然解密后的明文X与实际明文X完全相同，所以3.结论与统计分析解密方法相比，本文介绍的解密方法更加简单，快速，有较高的使用价值。
同时我们会发现解密得到的解密密钥可能不是唯一的，例如例3的解密密钥（C，t，p）可能是（（2，3，12，18），23，38）或者（（2，3，13，20），26，43），虽然它们的值不同，但是都是正确的解密密钥。参考文献：［J］． IEEE Trans． lnfo． ，1978，24（5）：525－530． - ［C］． Symp． Found． Sci，1983（23）：145 ： ＲecentＲ［J］． Proc． IEEE，1988（76）：578－593． 背包公钥密码系统的安全性与设计［J］． 清华大学学报：自然科学版，1988，28（1）：89 －97。 基于ECDLP的背包公钥密码体制［J］。 信息安全与通信保密，2008 (7): 83-85。 一种新的背包公钥密码体制[J]. 解放军理工大学学报，2001 (4): 29-33。 主编：陈燕燕-key 陈（，，，中国）： -key，来自，使用- -key，所以文本。 ：点；目标；超-；超-