Криптосистема Merkle Hellman Рюкзак

Question

Я работаю над проблемой 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

Ваш вес не увеличивается.

Answer 2

Есть условия для Меркле-Хеллмана, которым вы должны следовать, чтобы ваш вывод был правильным, вот они:

1. простой рюкзак должен быть супер-увеличивающимся
2. вес (множитель) должен быть больше значения, чем сумма вашего простого рюкзака
3. значения модуля и веса не должны иметь общего множителя