# Plaid CTF 2015 - Lazy Writeup

21 April 2015 by nwert

We were provided with the files knapsack.py, utils.py, ciphertext.txt and pubkey.txt. Before having any look at the code, I already suspected that this might be about the Merkle-Hallman knapsack cryptosystem [1] and after a quick one I was proven right. In principle the idea with this system is to generate a superincreasing sequence of numbers $$(x_i)$$, $$x_i \in \mathbb{N}_{>0}$$, thus

$$\forall j: x_j > \sum_{i=0}^{j-1} x_i.$$

To hide the superincreasing property we further choose a random $$r$$ and a modulus $$N$$ and compute the sequence $$(y_i)$$ where $$y_i = rx_i \mod N$$. The public key is then given by $$(y_i)$$ and the private key by $$((x_i), r, N)$$. Now to encrypt a message $$m$$ we split it up in its bits $$(b_i)$$ and compute $$c = \sum_i y_i b_i$$. Decryption is then done by first computing $$c' = c r^{-1} \mod N$$ and recovering $$(b_i)$$ from $$c'$$, which is possible due to the superincreasing nature of $$(x_i)$$. Thus we would check for the first $$x_i \leq c'$$ yielding the first bit, then update $$c'' = c'-x_i$$ and start anew.

Fortunately for us, attacking the scheme is not too hard either [2]. We can use lattice methods to solve the equation

$$c = y_1b_1 + y_2b_2 + \cdots + y_Nb_N$$

for the $$b_i \in \{0,1\}$$. This is done by considering the lattice

$$\begin{pmatrix} y_1 & 1 & 0 & \cdots & 0 \\ y_2 & 0 & 1 & \cdots & 0 \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ y_N & 0 & 0 & \cdots & 1 \\ -c & 0 & 0 & \cdots & 0 \end{pmatrix}$$

and using LLL reduction. After a bit of Sage, finding the right row (basically looking for zeroes and ones) and guessing some non-recovered characters the flag read lenstra_and_lovasz_liked_lattices.

## References

1. Merkle, Ralph; Hellman, Martin (1978). Hiding information and signatures in trapdoor knapsacks.
2. Shamir, Adi (1984). A polynomial-time algorithm for breaking the basic Merkle - Hellman cryptosystem.