Editorial for Balkan OI '11 P2 - Decrypt - Olympiads Online Judge

Editorial for Balkan OI '11 P2 - Decrypt

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

There are 2 phases:

Determine $R[0], R[1], R[2]$ $R [0], R [1], R [2]$
Determine $M[0], M[1], \dots, M[255]$ $M [0], M [1], \dots, M [255]$

Phase 1

Solving this problem starts by observing that $R$ $R$ has a period of $7$ $7$ (or $1$ $1$ iff $R[0] = R[1] = R[2] = 0$ $R [0] = R [1] = R [2] = 0$ ).

Also $\oplus$ $\oplus$ (xor) is a bitwise operation so the $8$ $8$ bits of each $R$ $R$ are independent. We are only interested in finding out a bit for now (let's assume least significant bit). The other bits are computed in a similar fashion.

Let $R[0] = a, R[1] = b, R[2] = c$ $R [0] = a, R [1] = b, R [2] = c$ , where $a, b, c$ $a, b, c$ are bits.

$\displaystyle \begin{align*} R[3] &= a \oplus b \\ R[4] &= b \oplus c \\ R[5] &= a \oplus b \oplus c \\ R[6] &= a \oplus c \end{align*}$ $\begin{aligned} R [3] & = a \oplus b \\ R [4] & = b \oplus c \\ R [5] & = a \oplus b \oplus c \\ R [6] & = a \oplus c \end{aligned}$

We start to play with the encryption device. What we ask is not that important, but we have to make sure that we don't ask the same number after $7P$ $7 P$ uses, because we would just waste a query.

What we care about are collisions, i.e. $2$ $2$ queries that give the same answer.

Let $Q_1, Q_2$ $Q_{1}, Q_{2}$ be the queries we asked at times $T_1$ $T_{1}$ and $T_2$ $T_{2}$ , respectively.

Since $M[Q_1 \oplus R[T_1]] = M[Q_2 \oplus R[T_2]]$ $M [Q_{1} \oplus R [T_{1}]] = M [Q_{2} \oplus R [T_{2}]]$ and $M$ $M$ is a permutation we deduce that $R[T_1] \oplus Q_1 = R[T_2] \oplus Q_2$ $R [T_{1}] \oplus Q_{1} = R [T_{2}] \oplus Q_{2}$ . This is the same as $R[T_1] \oplus R[T_2] = Q_1 \oplus Q_2$ $R [T_{1}] \oplus R [T_{2}] = Q_{1} \oplus Q_{2}$ .

This pretty much gives an equation for finding out $a, b, c$ $a, b, c$ .

What we need is $3$ $3$ independent equations (independent collisions). We can continue to play with the device until we get them. Some attention is needed to make sure the equations are really independent.

Once we have $3$ $3$ independent collisions we can find out $a, b, c$ $a, b, c$ .

We can do the same for the rest of the bits: $1$ $1$ through $7$ $7$ . We just have to use a different bit from $Q_1 \oplus Q_2$ $Q_{1} \oplus Q_{2}$ .

Phase 2

Now that we know $R[0], R[1], R[2]$ $R [0], R [1], R [2]$ , we can compute $M$ $M$ . It's important to remember the queries from step (1), otherwise the number of queries can easily exceed $320$ $320$ .

We know the step we are at ( $N$ $N$ ) and the element of $M$ $M$ that we want to compute. Let $X$ $X$ be the index of the element. We query for $R[N] \oplus X$ $R [N] \oplus X$ . This gives us $M[X]$ $M [X]$ .

The total number of queries should be at least $256$ $256$ (for $M$ $M$ ) and $3$ $3$ (for $3$ $3$ collisions). However, many collisions are not independent. Since the tests are random, it's easy to find $3$ $3$ independent collisions in at most $32$ $32$ collisions.

Comments

There are no comments at the moment.