0

I am currently trying to decrypt this superincreasing Knapsack cipher. I thought I understood how to do it, but the answers I am getting don't seem correct.

Superincreasing w: [2, 9, 16, 43, 71, 156, 301, 619]

q: 1337

modular inverse of r: 236

message: 2846 2947 1589 4010 4633 4053 1531 4053 2738 1589 3426 5676 2262 5676 3902 425 425 2947 4842

What I've done is 236(c)mod1337= x where c equals a number in the message.For example, (236)(2846)mod1337, and then I would get 482. Next, I subtracted the largest element in w which was less than or equal to 482, and repeated until the difference was equal to 0.

482-301=181

181-156=25

25-16=9

9-9=0

I then added the differences 181+25+9+0 = 215, converted 215 to binary 11010111, and then to text, x.

When I started calculating the next numbers, I started getting non ASCII characters, leading me to believe I messed up somewhere when calculating the cipher.

Any advice or help would be greatly appreciated.

Thanks,

Ethan

Mayo
  • 3

1 Answers1

1

Afte you have calculated $482$ you want to find a subset of the set $\{2, 9, 16, 43, 71, 156, 301, 619\}$ such set the elements of this subset sum up to $482$. One such subset is $$\{9,16,156,301\}$$ It is the only subset that sums up to $482$.

To find such a subset is equivalent to solve the equation $$2 \cdot x_0 + 9 \cdot x_1 + 16 \cdot x_2 + 43 \cdot x_3 + 71 \cdot x_4 + 156 \cdot x_5 + 301 \cdot x_6 + 619 \cdot x_7 = 482$$ such that $$ x_0\in\{0,1\},\;x_1\in\{0,1\},\;\ldots,x_7\in\{0,1\}$$ The solution is $$(x_0,x_2,x_3,x_4,x_5,x_6,x_7)=(0,1,1,0,0,1,1,0)$$ because you have $x_i=1$ if the coefficient of $x_i$ of the equation is in the subset and $x_i=0$ otherwise. So the binary message is $01100110$ This represents the binary number

$$ 0 \cdot 2^0+ 1 \cdot 2^1+1 \cdot 2^2+0 \cdot 2^3+0 \cdot 2^4+1 \cdot 2^5+1 \cdot 2^6+0 \cdot 2^7\\=0 \cdot 1+ 1 \cdot 2+1 \cdot 4+0 \cdot 8+0 \cdot 16+1 \cdot 32+1 \cdot 64+0 \cdot 128\\=102$$ This is the ascii code for f.

You find the subset by using your algorithm based on the supermonotonicity of the vector but then you have to add up the corresponding powers of $2$ and not the differences.

remark 1: maybe the $x_i$ are indexed in the other direction, such that $$2 \cdot x_7 + 9 \cdot x_6 + 16 \cdot x_5 + 43 \cdot x_4 + 71 \cdot x_3 + 156 \cdot x_2 + 301 \cdot x_1 + 619 \cdot x_0 = 482$$

remark 2: convince yourself why the supermonotonicity is important

  1. it allows you to find the $x_i$ efficiently
  2. it guaranties that the subset is uniquely determined
miracle173
  • 11,049