시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 0 0 0 0.000%

문제

A symmetric key cipher consists of two algorithms, the encryption and decryption algorithm. The encryption algorithm E maps a message m and a secret key k to the encrypted message c, that is,

c = E(m, k).

The length of the key is fixed at N bits (for e.g. N = 24). The message m can be of arbitrary length, and both m and c are of the same length. The decryption algorithm D, under the same key, maps c back to m, i.e.

m = D(c, k).

Note that for any m, k, we have

m = D(E(m, k), k).

Let us consider a type of attack where the attackers have a pair of m and the corresponding c but do not know the secret key. Their goal is to find k. If N is small, this attack can be successfully carried out using exhaustive search over all possible keys. To prevent such an attack, a company suggests using two levels of encryption. Given m and two keys k1, k2, the encrypted message is

c = E(E(m, k1), k2). (1)

Hence, the number of secret bits doubled and exhaustive search seems to be much more difficult.

In this question, you take the role of an attacker. Given m and c, your goal is to find the pair of k1 and k2 that satisfies (1). The source code of both routines D and E is available. (see programming instructions give to you)

입력

The first line contains two numbers, separated by a space. The first number is N. In our test files, the value of N ranges from 5 to 17. The second number is the length of the message m, in term of number of bits. In our test files, its value ranges from 30 to 10,000. The second line is the bit sequence of m and the third line is the bit sequence of c. In our representation, the left most bit is the first  bit of the message.

출력

Your program must write two lines to the standard output. The first line is the bit representation of the key k1 and the second line is for k2. The leftmost bit is the first bit of the key. Each line is terminated by a newline character. If there are more than one pair of keys that encrypt m to c, your program just need to output one pair.

예제 입력 1

10 30
000000000000000000000000000000
100101000101011101001111010110

예제 출력 1

1000000000
0100000000

힌트

  1. The cipher used in this question is a "stream cipher" and it has this property: Suppose the message m is the concatenation of two strings m1 and m2, that is m = m1 || m2 where the symbol || means concatenation, then encrypted m1 is the prefix of the encrypted m. That is, for any k, E(m, k) = E(m1, k) || c2 where c2 is some bit sequence.
  2. The time taken to encrypt an M-bit message is roughly proportional to M, for large M.
  3. When N is large, say around 15, it is infeasible to conduct exhaustive search over 230 possible keys within the time-limit given to you. Hence, a "smarter" searching method is required.

프로그래밍

You will be given source code of E and D. The source code also contains an example on the usage of the procedures. This question can be solved without looking into the details of these two procedures.

In your programming environment, you find the program ED.c which conatins an implementation of the functions E and D.

Copy the indicated section of ED.c to your program ("cut-and-paste").

Note that the main function of ED.c contains examples how to use the two functions.