Knapsack Public to Private (Superincreasing knapsack)

Question

I need to convert a hard knapsack to a superincreasing knapsack.

I have these superincreasing values (3,6,11,22,43,87). I also have w = 7 and n = 173. I converted the superincreasing values to hard one (21,42,77,154,128,90) by computing $a_i = x_i * w \bmod{n}$.

(3 * 7) mod 173 = 21
(6 * 7) mod 173 = 42
(11 * 7) mod 173 = 77
(22 * 7) mod 173 = 154
(43 * 7) mod 173 = 128
(87 * 7) mod 173 = 90

Question

I want to ask how can I get the superincreasing values if I have hard one.

example

Can I convert (21,42,77,154,128,90) to (3,6,11,22,43,87) with $w = 7$ and $n = 173$? Or how can I find the x_i if w = 7 and n = 173?

(x1 * w) mod n = 21
(x2 * w) mod n = 42
(x3 * w) mod n = 77
(x4 * w) mod n = 154
(x5 * w) mod n = 128
(x6 * w) mod n = 90

Answer 1

Here's the idea: given $w$ and $n$, we find a number $v$ such that $vw \equiv 1 \pmod{n}$. In your case of $w=7$ and $n=173$, we have $v=99$; such a $v$ will always exist if $w$ and $n$ are relatively prime, and can be found by the extended Euclidean algorithm. The value $v$ allows us to map from the "hard values" to the "superincreasing ones".

Here's how it works, suppose someone wants to send you a message corresponding to the first, third and fifth indicies: to encrypt it, he takes the public key, looks up the first, third and fifth indicides and adds them $21 + 77 + 128 = 226$; he sends the value $226$ as the ciphertext.

What you (the holder of the private key) would do is multiply the ciphertext (226) by $v$ modulo $n$; that gives $226 \times 99 \equiv 57 \pmod{173}$. You then go through the original superincreasing list to decode that, and easily see that $57 = 43 + 11 + 3$; that is the first, third and fifth indicies, correctly decoding the message.

This decoding method works quite well -- the problem with this crypto system is that it can be broken; this paper shows how an attacker can quickly decode even without the private key.