crypto-learning-with-exploitation.md

Learning with Exploitation

Video

This problem can be solved by solving r. Since there are not enough columns in A, we use LLL to find r.

r can be derived by constructing a matrix that can be solved by SVP using the following 2 formulas and finding LLL.

r*A - U mod p = 0
r is small

from sage.stats.distributions.discrete_gaussian_integer import DiscreteGaussianDistributionIntegerSampler
from sage.crypto.lwe import LWE, samples
from sage.misc.prandom import randrange
from params import *
from Crypto.Util.number import *

p = 0xfffffffffffffffffffffffffffffffeffffffffffffffff
F = GF(p)
d = 100
n = 10
q = int(p // (2 ** 64))
D = DiscreteGaussianDistributionIntegerSampler(q // d // 6) # six sigma

A, T = public_key
A = matrix(GF(p), A)
T = vector(GF(p), T)
# print(A)

for i in range(8):
  U, v = ciphertext[i]

  mat = []
  for i in range(A.ncols()):
      ps = [0]*10
      ps[i]=p
      mat.append(list(A.column(i)) + [-U[i]] + ps)
  for i in range(100):
      vec = [0]*101 + [0]*10
      vec[i] = 2
      vec[-11] = -1
      mat.append(vec)
  mat = matrix(ZZ, mat).transpose()

  lll = mat.LLL()
  # print(lll[1])

  rr = []
  for l in lll[1][10:]:
      rr.append(1 if l == 1 else 0)
  rr = vector(rr)
    
  # print(rr)
  print(long_to_bytes(int((v - rr*T)//q)))

  rr = []
  for l in lll[1][10:]:
      rr.append(0 if l == 1 else 1)
  rr = vector(rr)
    
  # print(rr)
  print(long_to_bytes(int((v - rr*T)//q)))