# 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

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)