배낭 암호 체계

머클-헬만 배낭 암호 체계는 가장 이른 시기의 공개 키 암호 방식 가운데 하나다. 랄프 머클과 마틴 헬만이 1978년에 발표했다. 방식은 다음과 같다.

앨리스는 모든 $i$에 대해 $a_i > \sum_{j=1}^{i-1} a_j$를 만족하는 양의 정수 $n$개 $a_1, \dots, a_n$과, $a_1 + \dots + a_n$보다 큰 양의 정수 $q$, 그리고 $q$와 서로소인 양의 정수 $r$를 고른다. 이 $n + 2$개의 정수가 앨리스의 개인 키다.

이어서 앨리스는 $b_i = (a_i \cdot r) \bmod q$를 계산한다. 이 $n$개의 정수가 앨리스의 공개 키다.

밥은 공개 키만 알아도 앨리스에게 $n$비트짜리 메시지를 보낼 수 있다. 밥은 자기 메시지의 $i$번째 자리가 1인 인덱스 $i$의 $b_i$를 모두 더해 $s$를 계산한다. 이 값 $s$가 암호문이다.

공개 키와 암호문을 아는 도청자 이브는 원래 메시지를 알아내려면 어렵다고 알려진 배낭 문제를 풀어야 한다. 반면 앨리스는 $s$를 받은 뒤 선형 시간에 원래 메시지를 복원한다.

이 문제에서 다루는 구현에서 앨리스는 속도를 위해 $q = 2^{64}$로 정하고 이 사실을 공개했다. 모두가 $q$를 알고 있으므로, 앨리스는 통신을 간단히 하려고 밥에게 $s$를 $2^{64}$로 나눈 나머지를 보내달라고 한다.

이 구현을 깨라. 공개 키와 암호문이 주어지면 원래 메시지를 복원하면 된다.

첫째 줄에 정수 $n$이 주어진다 ($1 \le n \le 64$).

다음 $n$개 줄에 정수 $b_i$가 한 줄에 하나씩 주어진다 ($1 \le b_i < 2^{64}$).

마지막 줄에 암호문을 $q$로 나눈 나머지 $s \bmod q$가 주어진다 ($0 \le s \bmod q < 2^{64}$).

주어지는 수열 $b_1, \dots, b_n$은 위 구현의 올바른 공개 키이고, 주어지는 값은 올바른 암호문이다.

원래 메시지의 비트를 순서대로 한 줄에 $n$개 출력한다. 각 문자는 0 또는 1이다.

$a_1, \dots, a_n$에서 고른 부분집합의 합이 서로 모두 다르므로, 입력과 맞는 메시지는 하나뿐이다.