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