1

I have difficulties with decrypting a message and i would be very glad if someone could help me to solve the following problem:

Given is $n=10010$ and an encryption map $e:\mathbb{Z}_{2}^{5}\rightarrow \mathbb{Z}_{n}$, where $(m_{1},m_{2}, m_{3}, m_{4}, m_{5})\rightarrow \sum_{i=1}^{5}m_{i}l_{i}$ and let $l_{1}=5005$, $l_{2}=910$, $l_{3}=6930$, $l_{4}=4004$, $l_{5}=1430$. I catch a ciphertext $c=5929\in \mathbb{Z}_{n}$.

I have to decrypt this message efficiently, so i have to find an $x\in \mathbb{Z}_{2}^{L}$, such that $e(x)=c$.

Until now i worked only with RSA and one dimension, here i have a 5-dimensional vector... Can anybody help, please? I really don't know how to start and appreciate every comment and remark about this problem. How can we break the protocol in the general case for any $c\in \mathbb{Z}_{2}^{5}$?

Thank you in advance!

Lullaby
  • 2,361

2 Answers2

1

This is an instance of a knapsack cipher. In general it is a quite a bit of work to break knapsack, but it isn't as difficult as it was once thought. So it is considered broken. The given instance is a particularly unsafe knapsack. Many $\ell_i$:s, but not all, share factors $7,10,11$ or $13$ with $n$. This gives you a lot of shortcuts to work with. My educated guess is that you are supposed to take advantage of those in this exercise, and not to worry about the general case.

So for example all but $\ell_5$ are divisible by seven as is $n$. Therefore $$ c\equiv\sum_i m_i\ell_i\equiv m_5\ell_5\pmod7. $$ You should be able to solve $m_5$ from this equation. Now do the same for other moduli that I suggested.

Jyrki Lahtonen
  • 133,153
  • Thank you a lot for your help! I've read the article about Merkle-Hellman knapsack cipher, i didn't know anything about it before, so thank you for this! – Lullaby Oct 18 '13 at 21:08
1

Hint: Figure out what is $l_i\cdot l_j\mod n$ for each pair of $i,j\in\{1,2,3,4,5\}$ with $i\ne j$. If it happens that $l_i\cdot l_j\equiv 0\mod n$, then you solved the problem.

(It happens)

Carlos Eugenio Thompson Pinzón
  • 2,780