Crypto - Taaffeite Encryption

I heard that post-quantum cryptosystems are secure. So even your quantum computer can't break this one. -Nilabha Saha

Full Implementation

Challenge

from sage.all import *
from secret import FLAG
degree = 256
vec_size = 3
p = 3329
smallness = 2
Q.<y> = PolynomialRing(GF(p))
R.<x> = Q.quotient(y**degree + 1)

def gen_small_vect():
    return vector([R([randint(0, smallness) for _ in range(degree)]) for _ in range(vec_size)])

def gen_coeffs():
    return Matrix([[R.random_element() for _ in range(vec_size)] for _ in range(vec_size)])

def encode_message(m):
    bits = sum([[int(b) for b in bin(c)[2:].zfill(8)] for c in m], [])
    return R(bits)

s = gen_small_vect()
coeffs = gen_coeffs()

assert len(FLAG)*8 <= degree

r = gen_small_vect()
err1 = gen_small_vect()
err2 = R([randint(0, smallness) for _ in range(degree)])

flag_b = encode_message(FLAG)

p_round = p//2 + 1
f = p_round*flag_b

ctxt = (coeffs.T*r + err1, (coeffs*s + gen_small_vect())*r + err2 + f)

noise = randint(-vec_size**degree, vec_size**degree)
noisy_s = noise*s
with open("data.txt", 'w') as f:
    f.write(f"noisy_s: {noisy_s}\n")
    f.write(f"ctxt: {ctxt}\n")

We are given a file, in which we find the ciphertexts and noisy_s . The error terms and noisy data makes it look like a LWE problem.

Let's look at how the data is being encrypted.

The flag is constructed into a polynomial form from its bits, $x^{index}$ for 1 and 0 otherwise and is multiplied by p//2+1

The function gen_small_vect() generates vectors of the size 3 which have degree 256 but coefficients in the range {0,2}.

We are given a pair of ciphertexts, which are a combination of error terms and small vectors and noisy_s term.

$$ctxt_{0} = coeffs*r+err_1\\ ctxt_{1} = (coeffs*s+vec)*r + err_2+f) \\ noisy\_s = noise*s$$

First, let us try to get the value of s from noisy_s

$noisy\_s = 1479x^{255} + 1479x^{254} + 2958x^{251} + 2958x^{250}...$

The only coefficients, in noisy_s are 1479 and 2958. This is because s is generated from gen_small_vect() which only has coefficients {0,2} so we can conclude $noise = 1479\mod p$ .

We can find the value of s by multiplying noise_s by $noise^{-1} = 664 \mod p$

Now that we have the value of s,we can now try to find an equation that gives us the value of f (possibly with some error terms).

$$ctxt_0*s = coeffs*r*s + err_1*s \\ ctxt_1 - ctxt_0*s = (coeffs*s*r + vec*r +err_2+f) - (coeffs*r*s +err_1*s) \\ ctxt_1 - ctxt_0*s = vec*r+err_2 -err_1*s+f$$

Let's compare how the equation and flag looks like

$$flag = 1665x^{167} + 1665x^{165} + 1665x^{164} + 1665x^{163} + 1665x^{162} + 1665x^{161} + 1665x^{157} \\ ctxt_1 - ctxt_0*s = ... \ 1771x^{165} + 97x^{164} + 1729x^{163} + 1746x^{162} + 1795x^{161} + 71x^{160} + 1738x^{159} \ ...$$

Although the degrees of the two terms are different, we can map values close to 1665 as 1 and values far from it as 0 to get the same set of values as the flag in the same interval.

p = 3329
degree = 256
Q.<y> = GF(p)[]
R.<x> = Q.quotient(y^degree + 1)
noisy_s= ...
ctxt= ...
Q(1479)^-1
#664
s = vector(R,noisy_s)*664
c0 = vector(R(i) for i in ctxt[0])
k1= ctxt[1]-c0*s
b1 = []
for i in k1.list():
    if (p//2+200)>= i >= (p//2 -200):
        b1.append(i)
    else:
        b1.append(0)
long_to_bytes(int(''.join(['1' if i else '0' for i in b1 ]),2))
#b'Breach{kyb3r_1n_cry5t4l5}\x00\x00\x00\x00\x00\x00\x00'