P6962 [NEERC 2017] Knapsack Cryptosystem

The Merkle-Hellman Knapsack Cryptosystem was one of the earliest public key cryptosystems invented by Ralph Merkle and Martin Hellman in $1978$ . Here is its description Alice chooses $n$ positive integers ${a_{1}, . . . , a_{n}}$ such that each $a_{i} > \sum^{i−1}_{j=1}a_{j},$ a positive integer $q$ which is greater than the sum of all $a_{i},$ and a positive integer $r$ which is coprime with $q$ . These $n + 2$ integers are Alice's private key. Then Alice calculates $b_i = (a_{i} · r)$ mod $q$ . These $n$ integers are Alice's public key. Knowing her public key, Bob can transmit a message of $n$ bits to Alice. To do that he calculates $s$ , the sum of $b_{i}$ with indices $i$ such that his message has bit $1$ in i-th position. This value $s$ is the encrypted message. Note that an eavesdropper Eve, who knows the encrypted message and the public key, has to solve a (presumably hard) instance of the knapsack problem to find the original message. Meanwhile, after receiving $s$ , Alice can calculate the original message in linear time; we leave it to you as an exercise. In this problem you deal with the implementation of the Merkle-Hellman Knapsack Cryptosystem in which Alice chose $q = 2^{64},$ for obvious performance reasons, and published this information. Since everyone knows her $q$ , she asks Bob to send her the calculated value $s$ taken modulo $2^{64}$ for simplicity of communication. You are to break this implementation. Given the public key and an encrypted message, restore the original message.

无

无

Time limit: 3 s, Memory limit: 512 MB.