Merkle Hellman背包密码体制

Question

我正在研究一个实现Merkle Hellman背包的java问题。维基百科的页面是http://en.wikipedia.org/wiki/Merkle%E2%80%93Hellman_knapsack_cryptosystem。

在使用一些简单的样本数据进行测试后，它们中的一些是成功的，而另一些则不是。例如，input = 'f'；(01100110)

加密：

w = ( 1,2,4,7,12,20,33,54)

r = 147 

q = 250

b = (147,44,88,29,14,190,101,188)

r-1(reverse) = 233    (r*r-1 mod q =1)

The cryptogram is therefore 423 (=44+88+190+101)

Decryption:

Then 423 * 233 mod 250 = 59

59-54=5
5-4=1
1-1=0

结果是10100001。但这是错误的！

我已经检查了很多次，就是找不到我的流程中的哪个步骤出了问题。此外，我知道我使用的数字应该是随机的。在这里，我只想举个例子。

有没有人能解释一下这个？

非常感谢！

Answer 1

你的w不是超增的。

Answer 2

为了使输出正确，Merkle-Hellman需要满足一些条件，下面是这些条件：

简单背包必须乘以super-increasing

• the (

1. )值必须大于简单背包的总和
2. 模数值和权重值不能有公因子