Codegate 2020 Quals - Polynomials (Crypto 810)
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' | |
''' |
#!/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) |
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) |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
This comment has been minimized.
NTRU Cryptosystem with weak parameters. Standard LLL attack (see https://latticehacks.cr.yp.to/ntru.html ) + guess a few coordinates to reduce the dimension.