Codegate 2020 Quals - Polynomials (Crypto 810)

1_solve.sage

from os import urandom
from Crypto.Util.number import long_to_bytes as l2b
from Crypto.Util.number import bytes_to_long as b2l
from Crypto.Cipher import AES

from data import *

load("chall.sage")

keys = []
for part in range(2):
    print("PART", part, "\n")
    if part == 0:
        N, p, q = 55, 3, 4027
        pub = pk1
        enc = enc1
    else:
        N, p, q = 60, 3, 1499
        pub = pk2
        enc = enc2

    C = Chall(N, p, q)
    x = C.x
    mod = x**N - 1
    C.h = h = C.R(pub)
    enc = C.R(enc)

    # standard LLL attack on the NTRU cryptosystem
    mat = matrix(ZZ, 2*N, 2*N)
    mat[:N,:N] = q * identity_matrix(N)
    mat[N:,N:] = identity_matrix(N)
    for i in range(N):
        mult = (h * x**i) % mod
        for j in range(N):
            mat[N+i,j] = mult[j]

    # guess a few positions of 0 coefficients
    # to reduce the dimension
    if part == 0: todel = 0
    if part == 1: todel = 4
    for itr in range(2**20):
        inds = list(range(N, 2*N))
        shuffle(inds)
        inds = inds[:todel]
        ml = mat.delete_rows(inds).LLL()

        row = ml[0]
        print(row[:N])
        if max(map(abs, row)) != 3:
            continue
        print("Solution with inds =", inds)
        g = C.R(list(map(int, row[:N])))
        f = C.R(list(map(int, row[N:])))
        print("g =", g)
        print("f =", f)
        print(f * h % mod)
        assert f * h % mod == g
        break
    
    pts = []
    privkey = f
    for i in range(N):
        pts.append(C.decrypt(enc, privkey*x**i % mod))
    keys.append(pts)
    print()


for k0 in keys[0]:
    if len(k0) != 8: continue
    for k1 in keys[1]:
        if len(k1) != 8: continue
        key = k0 + k1
        print("trying key", key.hex(), key)

        cipher = AES.new(key, AES.MODE_ECB)
        print(cipher.decrypt(l2b(encflag)))
        
'''
trying key b0e24c7443d618e54676965f96ff28ef b'\xb0\xe2LtC\xd6\x18\xe5Fv\x96_\x96\xff(\xef'
b'CODEGATE2020{86f94100f760b45e9c0f6925f5b474b24387ff6be5732ab88d74b4bfbff35951}\x02\x02'
'''

2_chall.sage

#!/usr/bin/env sage
from sage.misc.banner import version_dict
from Crypto.Util.number import long_to_bytes as l2b
from Crypto.Util.number import bytes_to_long as b2l
#from Crypto.Util.Padding import pad
from Crypto.Cipher import AES
from os import urandom

assert version_dict()["major"] >= 9


class Chall:
    def __init__(self, N, p, q):
        self.N, self.p, self.q = N, p, q
        self.R = PolynomialRing(Integers(q), "x")
        self.x = self.R.gen()
        self.S = self.R.quotient(self.x ^ N - 1, "x")
        self.h, self.f = None, None

    def random(self):
        return self.S([randint(-1, 1) for _ in range(self.N)])

    def keygen(self):
        while True:
            self.F = self.random()
            self.f = self.p * self.F + 1
            try:
                self.z = self.f ^ -1
            except:
                continue
            break
        while True:
            self.g = self.random()
            try:
                self.g ^ -1
            except:
                continue
            break
        self.h = self.p * self.z * self.g

    def getPublicKey(self):
        return list(self.h)

    def getPrivateKey(self):
        return list(self.f)

    def encrypt(self, m):
        m_encoded = self.encode(b2l(m))
        e = self.random() * self.h + self.S(m_encoded)
        return list(e)

    def decrypt(self, e, privkey):
        e, privkey = self.S(e), self.S(privkey)
        temp = map(Integer, list(privkey * e))
        temp = [t - self.q if t > self.q // 2 else t for t in temp]
        temp = [t % self.p for t in temp]
        pt_encoded = [t - self.p if t > self.p // 2 else t for t in temp]
        pt = l2b(self.decode(pt_encoded))
        return pt

    def encode(self, value):
        assert 0 <= value < 3 ^ self.N
        out = []
        for _ in range(self.N):
            out.append(value % 3 - 1)
            value -= value % 3
            value /= 3
        return out

    def decode(self, value):
        out = sum([(value[i] + 1) * 3 ^ i for i in range(len(value))])
        return out

    def count(self, row):
        p = sum([e == 1 for e in row])
        n = sum([e == self.q - 1 for e in row])
        return p, len(row) - p - n, n


def wrapper(N, p, q, pt):
    chall = Chall(N, p, q)
    chall.keygen()
    print(chall.getPublicKey())
    print(chall.encrypt(pt))
    print(chall.count(list((chall.F))))

# if __name__ == "__main__":
#     key = urandom(16)
#     cipher = AES.new(key, AES.MODE_ECB)
#     flag = pad(open("flag.txt", "rb").read(), 16)
#     enc_flag = b2l(cipher.encrypt(flag))
#     print(enc_flag)

#     key1, key2 = key[:8], key[8:]

#     wrapper(55, 3, 4027, key1)
#     wrapper(60, 3, 1499, key2)

data.py

encflag = 2960408776014513590203667205130185225161547470030516261741102417822093600856513664346223496713014612247754765985505434047965417819771431223015026059243409921418043319365743779292681722097463141

pk1 = [3627, 1889, 3460, 2627, 3545, 1478, 2307, 3378, 3350, 1272, 2445, 3881, 3110, 1628, 1798, 1826, 259, 1983, 453, 52, 2650, 834, 3307, 907, 2762, 3452, 1085, 3059, 3544, 1136, 3767, 2346, 1952, 699, 3023, 531, 1208, 1449, 3636, 1742, 2692, 1128, 1683, 1152, 2584, 637, 3053, 2072, 2687, 1811, 2981, 3288, 2324, 3632, 1813]
enc1 = [426, 3379, 3985, 160, 2502, 3592, 55, 1753, 3599, 2656, 2380, 582, 1038, 1028, 791, 1695, 1783, 3814, 3687, 3742, 1892, 1053, 2728, 3946, 801, 238, 3766, 1355, 1219, 528, 3560, 9, 3737, 1975, 1469, 85, 1373, 3717, 195, 3252, 2020, 1087, 201, 2536, 1655, 3380, 2322, 2438, 803, 2838, 1034, 457, 3050, 4010, 231]
cnt1 = (22, 18, 15)

pk2 = [314, 1325, 1386, 176, 369, 1029, 877, 1255, 111, 1226, 117, 0, 210, 761, 938, 273, 525, 751, 1085, 372, 1333, 898, 780, 44, 649, 1463, 326, 354, 116, 1080, 1065, 1109, 358, 275, 1209, 964, 101, 950, 415, 1492, 1197, 921, 1000, 1028, 1400, 43, 1003, 914, 447, 360, 1171, 1109, 223, 1134, 1157, 1383, 784, 189, 870, 565]
enc2 = [378, 753, 466, 825, 320, 658, 630, 288, 16, 576, 134, 914, 549, 489, 197, 1392, 328, 361, 1241, 50, 710, 315, 526, 1250, 977, 453, 225, 433, 1342, 1005, 1432, 143, 1326, 1426, 1251, 1397, 237, 1202, 555, 83, 994, 446, 1406, 356, 1127, 1469, 485, 1034, 1224, 230, 1445, 825, 630, 1158, 815, 807, 837, 747, 423, 184]
cnt2 = (20, 20, 20)

NTRU Cryptosystem with weak parameters. Standard LLL attack (see https://latticehacks.cr.yp.to/ntru.html ) + guess a few coordinates to reduce the dimension.