24221번 - Double Crypt 4 스페셜 저지다국어

문제

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$.

힌트

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

첨부

• double_4.in