# Plaid CTF 2015 - Lazy Writeup

21 April 2015 by nwertWe 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

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

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

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

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