Skip to content

Instantly share code, notes, and snippets.

@hellman

hellman/1_solve.sage

Last active Feb 13, 2020
Embed
What would you like to do?
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)
@hellman

This comment has been minimized.

Copy link
Owner Author

@hellman hellman commented Feb 13, 2020

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

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.