2003年第12期 福建计算机 51 陷门背包 公钥加密(MH法) 倪一鸣 (福州市委党校电化教育中心，福建福州) [摘要]本文将介绍MH密码加密解密方法的发展，探讨一种改进的MH加密方法。该加密方法基于一个困难的线性问题，通过一系列数学技巧，发展了原有的MH密码加密方法，从而加强了公钥加密的安全系数。讨论结果表明，该加密体制具有很强的安全性，可以考虑在实际中应用。[关键词] 公钥 MH法 陷门背包 在数据处理中，为了保密起见，可以适当地设法将数据交换成“完全无法识别”的密码信息，这个过程通常称为数据加密。这是数据保密的重要手段。各种加密方法不断出现，讨论十分活跃。 特别是在计算机应用于军事、经济、信贷、储蓄、管理等各个领域之后，人们越来越重视数据信息的保密性。因此，就有一个如何将加密信息恢复到原始数据的“原貌”的过程，这个过程就叫信息解密。显然，如果一个加密信息能够被某人轻易解密，那么这是一个没有什么价值的加密系统。
因此，研究加密体制，使人们很难找到解密加密信息的方法，这就是密码学研究的课题！加密解密过程可以用下面这个简单的图来表示：l 明文—变换加密—不可读的密码（密文）—解密—原文l 现代密码技术按密钥类型分为两大类：一类是对称加密（秘钥加密）体制，一类是公钥加密（非对称加密）体制。在实际应用中，对称加密体制的算法速度极快，这使得它得到广泛的应用。由于算法不需要保密，厂商可以开发出低成本的芯片来实现数据加密，这些芯片应用范围很广，适合大批量生产。公钥加密体制基于前沿的数学问题，计算非常复杂，安全性较高，但其实现速度远远慢于对称密钥加密体制。在实际应用中，可以发挥两者的优点。 采用对称加密体制对文件进行加密，采用公钥加密体制对“加密文件”的密钥（会话密钥）进行加密，这是一种混合加密体制，较好地解决了运算速度和密钥分发管理的问题。
因此，公钥密码通常用于加密密钥、核心机密数据，而对称密码通常用于加密大量数据。 1.公钥密码 公钥密码又称非对称密码。顾名思义，所谓非对称密码就是加密密钥和解密密钥是不同的，加密密钥可以像电话号码一样公开，刊登在书上，方便使用，唯一需要严格保密的就是解密密钥。 公钥加密自问世以来，学者们提出了许多公钥加密方法，它们的安全性建立在复杂的数学问题之上。根据它们所基于的数学问题，目前认为安全有效的有以下三类系统：大整数分解系统（代表为RSA）、椭圆曲线离散对数系统（ECC）和陷门背包公钥加密（MH方法）。 要了解公钥密码的基本原理，有必要先简单介绍一些初等数论知识。 我们以 7 天的一周为例。我们有 7 个数字 0、1、2、3、4、5 和 6。0 代表星期日，或“第 0 天”，1 代表星期一，或“第 1 天”，依此类推。
这种加法叫做“取模”计算，7 就是“取模”值，我们可以确定： 5 + 4 = 2 mod 7（星期五加四天是星期二） 2 + 3 = 5 mod 7（星期二加三天是星期五） 3 + 4 = 0 mod 7（星期-四天是星期日）等等。由于乘法是连续加法，幂运算是连续乘法，所以写出模 7 乘法表和幂运算表并不困难。这些特殊运算，特别是幂运算，当它们与“星期几”相关时，意义并不大。然而，在一些公钥密码系统中，同余运算和幂运算起着重要作用，但“取模”值远不止 7，这是一个非常大的数字，往往是几百位的十进制数（或几千位的二进制数）。 2. 陷门背包公钥密码学 2.1 背包问题： 例如：已知物体的重量分别为1、2、4、8、16、32Kg，背包的承重能力为23。问题是背包里应该装哪些物品。这是一个容易解决的背包问题。从二进制表达式23=1+2+4+16，我们马上就能知道背包里装的物品的重量分别为1、2、4、16Kg。
背包问题一般的数学描述为：给定一个背包向量a=（Q-，Q2，⋯Q），一个背包载荷S，求一个向量X=（XI，】【2，⋯，X）使得S=atX。有些特殊的背包问题很容易解，比如上面的例子，它是一个递增的背包问题i=1-1.∑.Q，称为易背包问题。如果Q是随机背包问题，Q是超递增序列Q，那么它很难求解，称为难背包问题。2.2 易背包问题超递增背包问题是一个简单的背包问题。假设，给定Q（i_1，i-1-2，3，⋯n），且q>。 Q t(j = 1, 2, 3, ⋯ n)，Xi(0 或 1，使得对于给定的 S，满足方程：-1, 2, 3⋯) 可得 n— S = ∑Q . ll 解：由已知条件可得，当 s ≥Q 时，x 不等于零，现 xn：f.s 主 Q“对于 j：-1，t 当 S. ∑，Q 时，形成一个易解的背包：求 X；E f0,1 J ，使得对于给定的 s> 0 ，方程 S = 三 a = ( 17 1, 196, 457 , 119 1, 2 4 10) 。
（2）选取W模P并与P互质，使得（w，p）= 1. p>盅a，例如：取P=8443. W=2550。（3）构造一个困难的背包向量b=（b-，b2，⋯，b），使得bk= ． Q，其中S为明文，例如选取⋯wQ，（mod P），例如由以上数据，我们可以计算出VIP信息