시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 (추가 시간 없음) 1024 MB45414095.238%

문제

The Advanced Encryption Standard (AES) involves a new strong encryption algorithm. It works with three blocks of $128$ bits. Given a message block $p$ (plaintext) and a key block $k$, the AES encryption function $E$ returns an encrypted block $c$ (ciphertext):

$c = E(p, k)$.

The inverse of the AES encryption function $E$ is the decryption function $D$ such that

$D ( E(p, k), k ) = p$, $E ( D(c, k), k ) = c$.

In Double AES, two independent key blocks $k_1$ and $k_2$ are used in succession, first $k_1$, then $k_2$:

$c_2 = E ( E(p, k_1), k_2 )$.

In this task, an integer $s$ is also given. Only the leftmost $4 \times s$ bits of all keys are relevant, while the other bits (the rightmost $128$ minus $4 \times s$ bits) are all zero.

You are to recover the encryption key pairs for some messages encrypted by Double AES. You are given both the plaintext $p$ and the corresponding double-encrypted ciphertext $c_2$, and the structure of the encryption keys as expressed by the integer $s$.

You must submit the recovered keys, and not a recovery program.

입력

You are given ten problem instances in the text files named double1.in to double10.in. Each input file consists of three lines. The first line contains the integer $s$, the second line the plaintext block $p$, and the third line the ciphertext block $c_2$ obtained from $p$ by Double AES encryption. Both blocks are written as strings of 32 hexadecimal digits ('0'..'9', 'A'..'F'). The library provides a routine to convert strings to blocks. All input files are solvable.

출력

The first line contains the key block $k_1$, and the second line the key block $k_2$, such that 

$c_2 = E ( E(p, k_1), k_2 )$.

Both blocks must be written as strings of 32 hexadecimal digits ('0'..'9', 'A'..'F'). If there are multiple solutions, you need submit only one of them.

제한

For the number $s$ of relevant hexadecimal digits in a key it holds that $1 ≤ s ≤ 5$.

예제 입력 1

1
00112233445566778899AABBCCDDEEFF
6323B4A5BC16C479ED6D94F5B58FF0C2

예제 출력 1

A0000000000000000000000000000000
70000000000000000000000000000000

힌트

A good program can recover keys in less than 10 seconds for any allowed input file.

첨부

채점 및 기타 정보

  • 예제는 채점하지 않는다.