背包公钥密码的改进及其膨胀性研究 (2004年)

背包公钥密码是一种基于数学中背包问题的公钥加密算法，它是公钥密码体系中的一个重要分支。背包问题可以看作是一种寻找物品组合的问题，其中每个物品有自己的大小，目标是找到一种组合方式，使得这些物品的总体积恰好等于背包的容量，或者是在有特定约束条件的情况下尽可能接近这个容量。根据物品之间是否有约束关系，背包问题又可以分为两种类型：一般的背包问题和子集和问题（特殊背包问题）。特殊背包问题的一个特例是当物品的大小构成一个超递增序列时，背包问题就变得容易解决。 在研究背包公钥密码时，通常会涉及到以下几个关键概念和过程： 1. 背包问题的数学模型：背包问题数学上被描述为寻找一组0-1变量xi的值，使得物品的总大小等于背包的容量。这个问题在数学上等同于找到一个向量x，使得Ax = b，其中A代表物品大小矩阵，x代表决策变量向量，b代表背包的容量。 2. 超递增序列：超递增序列是指一个递增的正整数序列，其中任意一个数大于它前面所有数的和。例如，序列1, 2, 4, 8是超递增序列。如果序列是超递增的，那么背包问题有一个多项式时间的解法。背包公钥密码系统中通常使用超递增序列作为公钥的一部分。 3. 超递增公差：如果一个序列是超递增的，并且每个数ai与它之前所有数的和的差是一个常数，这个常数称为超递增公差。 4. Merkle-Hellman背包公钥密码系统：它是背包公钥密码系统中的一种，使用超递增序列作为公钥的一部分。在此系统中，加密过程涉及将明文信息与公钥中的整数进行模运算。明文信息首先被转换成数字形式，然后通过公钥进行加密。为了使背包问题变得困难，Merkle和Hellman引入了一个变换，该变换能够将超递增序列转变为一个没有超递增性质的普通序列。 5. 解密过程：解密过程通常需要使用私钥，私钥包含变换的逆操作。通过私钥可以找到一个解同余方程的方式，进而逆向解算出加密时所用的超递增序列，最终得到原始明文信息。 在该文章中，研究者刘海峰对传统的背包公钥密码算法进行了改进，并提出了一些改进方向及新变换应具备的条件。同时，作者使用膨胀率作为评价背包公钥密码性能的一个重要指标。膨胀率是指在加密过程中密文的长度与明文长度的比率。文章的两个简要结论可能是关于改进的背包公钥密码算法的性能，例如加密和解密的速度、密文的长度、以及安全性的提升等。 总结来说，文章对背包公钥密码算法进行了深入研究，特别关注了如何改进现有算法以提高效率和安全性，同时引入了评估公钥密码性能的新指标——膨胀率，并对改进算法的有效性进行了探讨。