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.