# Learning with Exploitation author's writeup ## Challange summary In this challenge, I implemented multibit-variant of [Regev's cryptosystem](https://en.wikipedia.org/wiki/Learning_with_errors#Public-key_cryptosystem). ### Normal Regev's cryptosystem First, the cryptosystem generates [LWE Oracle](https://doc.sagemath.org/html/en/reference/cryptography/sage/crypto/lwe.html). The matrix $A$, vector $s$, error vector $e$, and target vector $t$ that holds: $$A\cdot s+e=t$$ and $A,t$ will be a public key. To encrypt, the cryptosystem generates vector consisting of only 0 or 1 $r$. The ciphertext $(u,v)$ of $m\in\{0,1\}$ will be: $$(u,v)=(r\cdot A,r\cdot t+mq)$$ Note that $q:=\lceil \frac{p}{2}\rceil$ Decryption will be as follows: * If $v-u\cdot s\approx 0$, $m=0$. * If $v-u\cdot s\approx q$, $m=1$. ### Extended Regev's Cryptosystem in this challenge I extended this cryptosystem to encrypt multibit rather than single bit. In this challenge, to encrypt 64-bit plaintext $0\le m<2^{64}$, I defined $q:=\lceil \frac{p}{2^{64}}\rceil$. The encryption and decryption are almost the same as the original. ## Solution Unfortunately, this trivial extensions do not work. In this cipher, the following equation holds. $$u=r\cdot A$$ $A$ and $u$ are known and $r\:(\in \{0,1\}^{100})$ is hidden. By taking one row from $A$, recovering the parameter $r$ is almost the same with attacking [Merkle–Hellman knapsack cryptosystem](https://en.wikipedia.org/wiki/Merkle%E2%80%93Hellman_knapsack_cryptosystem). It is known that, with certain conditions, [Low-Density attack](https://web.stevens.edu/algebraic/Files/SubsetSum/p229-lagarias.pdf) works well for attacking knapsack cryptosystem. In the condition given, The bit length of the element of A is far longer than 100bit (to make the cryptosystem work with 64bit plaintext). Low-density attack can be applied and $r$ can be recoverd. After $r$ is recovered, we can restore the plaintext $m$ from the equation $v=r\cdot t+mq$. ## Solver ```python from output import public_key, ciphertext from sage.modules.free_module_integer import IntegerLattice p = 0xfffffffffffffffffffffffffffffffeffffffffffffffff F = GF(p) d = 100 n = 10 q = p // (2 ** 64) A, T = public_key A = matrix(F, A) T = vector(F, T) N = 2 ** 64 t = 2 flag = b'' for (U, v) in ciphertext: U = vector(F, U) v = F(v) M = [] for i in range(d): g = [0 for _ in range(d + t)] for j in range(t): g[j] = int(A[i][j]) * N g[i + t] = 2 M.append(g) g = [0 for _ in range(d + t)] for i in range(t): g[i] = -int(U[i]) * N for i in range(d): g[i + t] = -1 M.append(g) for i in range(t): g = [0 for _ in range(d + t)] g[i] = p * N M.append(g) print('LLL start') lattice = IntegerLattice(M, lll_reduce=True) print('LLL end') E = lattice.reduced_basis ok = False r_recovered = None for g in E: if g[0] == 0 and all(x == 1 or x == -1 for x in g[t:]): r_recovered = vector([F((x + 1) // 2) for x in g[t:]]) print(r_recovered) print((r_recovered * A)[0:3]) print(U[0:3]) if U == r_recovered * A: ok = True break if not ok: print('attack failed') exit() m = (v - r_recovered * T) / q flag += int(m).to_bytes(8, 'big') print(flag) ```