2025-CISCN(长城杯)-crypto

只写了两道解多的题,还得加油

rasnd

from Crypto.Util.number import getPrime, bytes_to_long
from random import randint
import os

FLAG = os.getenv("FLAG").encode()
flag1 = FLAG[:15]
flag2 = FLAG[15:]

def crypto1():
    p = getPrime(1024)
    q = getPrime(1024)
    n = p * q
    e = 0x10001
    x1=randint(0,2**11)
    y1=randint(0,2**114)
    x2=randint(0,2**11)
    y2=randint(0,2**514)
    hint1=x1*p+y1*q-0x114
    hint2=x2*p+y2*q-0x514
    c = pow(bytes_to_long(flag1), e, n)
    print(n)
    print(c)
    print(hint1)
    print(hint2)


def crypto2():
    p = getPrime(1024)
    q = getPrime(1024)
    n = p * q
    e = 0x10001
    hint = pow(514*p - 114*q, n - p - q, n)
    c = pow(bytes_to_long(flag2),e,n)
    print(n)
    print(c)
    print(hint)
print("==================================================================")
crypto1()
print("==================================================================")
crypto2()
print("==================================================================")

先讲第一部分，通过

$hint_1+0x114 = x_1p+y_1q$

$hint_2+0x514 = x_2p+y_2q$

可以看到x1和x2不大，那就可以通过爆破得到，将上式乘x2,将下式乘x1,再相减得到下式

$(hint_2+0x514)x1-(hint_1+0x114)x2 = (x_1y_2- x_2y_1)q$

再将这个式子和n求最大公因数就可以得到q了

from Crypto.Util.number import *
from gmpy2 import *
n = 14596256954979546388455615429866299814769189386236664598415571659258697441660811804221395084844333638685242792355769696611911089018929745876532193487610702067796387873184769522160041261113079307243492220947327039763927972965579974931285130627177680110010932473886796894099260643791182894790027463066348905823147838513772331296946247115204429623848201472597540168094251184204486630395576662102258307709741156759161888603607786313510305846998960717290499099989493767267901173183092449423521933388069985194531668906702509811484902582004004952318784751635789324635599205184004329544887607475134839141782004363313378335859
c =7807028916998328482519979559419568699179053865197422004156013293667297319522660589750638716332506797616275304240616938711241224824927260852542635179340826277437716033659081018748691856838747505304538200357178926262675969188581668240752622516750333523294335390826124574317996811613192632016308583458955906737146586581707101734731804035687244226473080700278061997856189133391808334285196534827702272923405014712870700670586205969449836864403917994836791359234524063425001245830356006079283780991257984342963849440442503474176388462745562571693601986589012708124846856708488042690555263217295233520446994916625212462092
hint1 = 1774857452928513204026815516727850875429408834324590901773681289135302911704298863251583719151098436487294717795777262052118343365512671369913964622867084527861571253539781225247916946263600038559022100130529985076889295657282675835651266321227294705213288140796075570646690504700825016957762677426760790036874260452236947264395326566153098000
hint2 = 2984402722803879327278565374906350281750664798299447753605977975629075253573333849562277798921811405061671821092499544883376490768080372208987773443003598757615261938983831024041418784423510415271083668985554009994928283687242713271314148308504286491646702017120243102729237311348797012978369734499159177753126818683505032095321991465493288737753712054342517595118354959432486053716613294304810606463701992391457212759539806555797642228817241603663320475229885299
h2 = hint2 +0x514
h1 = hint1 +0x114
for i in trange (2**11):
    for j in trange(2 ** 11):
        k = gcd(h1 * i - h2 * j,n)
        if k != 1 and len(bin(k)[2:]) == 1024:
            print(k)
            break

e = 65537
q = 111977955724186652256223896253180213104114186473775752410824846817368573386997564706883402694510383794901317835526430334460758717676094684026185884026630577746706817723430872041666461215884962502770421248162008750657526798023492876531413358964170651134116583876733205280170983686146541849719320477190770341993
p = n//q
d = invert(e,(p-1)*(q-1))
m = pow(c,d,n)
print((long_to_bytes(m)))

第二部分，注意到n-p-q，联想到加1就可以得到phi(n),变成下式：

$(514p-114q)^{n-p-q+1}*(514p-114q)^{-1} \equiv hint \mod n$

通过欧拉定理可以得到

$(514p-114q)^{-1} \equiv hint \mod n$

那么

$(514p-114q) \equiv hint^{-1} \mod n$

再联立$p*q=n$解方程即可

from Crypto.Util.number import *
from gmpy2 import *
from sympy import *
from tqdm import *
n = 12760801554515855427688425930340901667746449170628666737643222835689826125407797329428721177923397576928448108730165749381333344389780282106566098042010785311583719944084778082900490735263936422275202792644203547276293025800431524972290423012612776535807523461639494234681362082676872613423338751496927731627090412251744622903313829319063447674369052911339317183225535775270677684886046687002398887746461454837368896818203504533713684170273247140197678819151487971979855020117223529736375755312552685573827690357185528968366287317529192468839828822829656530427377879487734064849207753407471575982970365833843887094677
c = 4659953384446382269446601443875001481793630357813647440674774098150519027794597617238879078158750960543328895546462816520396742750220519503966444250622987405685949326310830021079313972063553664623000374089455360792476067039041163715552826204537006972576314103772219444850987721990873993340367787936810595376145496315737764286811765282154239822940525101116082548844597998082262646429290705097471181001236791040030357621765810900443049887511419741028866117493827165819836566288502696109573157129669849593247371587522979957403903584120666068144479858939580825271922867902387147490319094228886985776321380553305903474828
h = 5861446040566529193275242814814627204756995659345262394507347101738873702432026914059474060494646209345351318929618525255147120354057795939480638578880119071046747054470172930436248520367771649799318160704010373518086294276698284964206125878010569755854870266371986766839858868458495819409967104325332544156461736720690544450913395646349051833602913358297004700995184783862326355740685460816638306298534989201414796070743607716931703862209405701883661844773076918484749498244781577128843726406407298106076011711783262137926040289355057662262049394854969481337947181662342179986763166504284001857717573310395133905681
e =65537
h1 = invert(h,n)
f1, f2 = symbols("f1, f2")
f_solve = solve([514*f1 - 114*f2 - h1, f1*f2 - n], [f1, f2])
print(f_solve)
p = 103212921920393117976903133089056619673730783162281088249340624356586219235898384109272438994267204403164707002466267303164408681996013806941170471158955885572033549421952545559742770687950077395737327908570761634333391029755509617488282588848079657656653622808017015608792965877071582570841743394102951918589
q = 123635697130618080776832142353999400772397545923402359150804987418719617194276051829242922352746151016597295244868563655936375786358448108357943183357442842731570964364882279561307258564958834257970525343956852920008138490439046975450266901545262023379891661787759184602487702469426995038723050501841171363193
d= invert(e,(p-1)*(q-1))
m = pow(c,d,n)
print(long_to_bytes(m))

fffffhash

import os
from Crypto.Util.number import *
def giaogiao(hex_string):
	base_num = 0x6c62272e07bb014262b821756295c58d
	x = 0x0000000001000000000000000000013b
	MOD = 2**128
	for i in hex_string:
		base_num = (base_num * x) & (MOD - 1) 
		base_num ^= i
	return base_num


giao=201431453607244229943761366749810895688

print("1geiwoligiaogiao")
hex_string = int(input(),16)
s = long_to_bytes(hex_string)

if giaogiao(s) == giao:
	print(os.getenv('FLAG'))
else:
	print("error")

参考的脚本,具体原理准备观摩一下大佬们的博客

base_num = 0x6c62272e07bb014262b821756295c58d
p = 0x0000000001000000000000000000013b
MOD = 2^128

TARGET = 201431453607244229943761366749810895688

n = 20
M = Matrix.column([p^(n - i - 1) for i in range(n)] + [-(TARGET - base_num*p^n), MOD])
M = M.augment(identity_matrix(n+1).stack(vector([0] * (n+1))))
Q = Matrix.diagonal([2^256] + [2^8] * n + [2^16])
M *= Q
M = M.BKZ()
M /= Q

for r in M:
    if r[0] == 0 and abs(r[-1]) == 1:
        r *= r[-1]
        good = r[1:-1]
        break

ans = []
y = int(base_num*p)    
t = (base_num*p^n + good[0] * p^(n-1)) % MOD
for i in range(n):
    for x in range(256):
        y_ = (int(y) ^^ int(x)) * p^(n-i-1) % MOD
        if y_ == t:
            ans.append(x)
            if i < n-1:
                t = (t + good[i+1] * p^(n-i-2)) % MOD
                y = ((int(y) ^^ int(x)) * p) % MOD
            break

print(bytes(ans).hex()) 
# 1df2006d2e3362153d001f53102a7c2a0a591516

babypqc(未解决)

import ctypes
from random import getrandbits
import signal
import socketserver
from sympy import nextprime
import numpy as np  
from Crypto.Util.number import *
import ast


def ll_to_polylist(l):
    return list(map(list, list(l)))

class Dilithium:
    def __init__(self):
        self.dilithium_lib = ctypes.CDLL("./dilithium/libpqcrystals_dilithium2_ref.so")
        self.pk_buf = ctypes.c_buffer(1312)
        self.sk_buf = ctypes.c_buffer(2560)
        self.Q = 8380417
        self.N = 256
        self.dilithium_lib.pqcrystals_dilithium2_ref_keypair(self.pk_buf, self.sk_buf)

    def sign_message(self, message: bytes) -> bytes:
        SIGNLEN = 2420
        MLEN = len(message)
        sm_buf = ctypes.create_string_buffer(SIGNLEN + MLEN)
        m_buf = ctypes.create_string_buffer(message)
        smlen_buf = ctypes.c_size_t()
        self.dilithium_lib.pqcrystals_dilithium2_ref(sm_buf, ctypes.byref(smlen_buf), m_buf, MLEN, self.sk_buf)
        return sm_buf.raw[:smlen_buf.value]

    def verify_sign(self, message: bytes, signature: bytes) -> bool:
        msg_buf = ctypes.create_string_buffer(len(signature))
        msg_len = ctypes.c_size_t()
        sm_buf = ctypes.create_string_buffer(signature)
        result = self.dilithium_lib.pqcrystals_dilithium2_ref_open(msg_buf, ctypes.byref(msg_len), sm_buf, len(signature), self.pk_buf)
        return result == 0 and message == msg_buf.raw[:msg_len.value]


class Task(socketserver.BaseRequestHandler):
    def __init__(self, *args, **kargs):
        super().__init__(*args, **kargs)
    

    def timeout_handler(self, signum, frame):
        raise TimeoutError
    

    def dosend(self, msg):
        try:
            self.request.sendall(msg.encode('latin-1') + b'\n')
        except:
            pass


    def recvline(self, msg = None):
        if msg:
            self.request.sendall(msg.encode('latin-1'))
        try:
            data = b""
            while True:
                chunk = self.request.recv(1)
                if not chunk:
                    break
                data += chunk
                if chunk == b'\n':
                    break
        except:
            pass

        line = data.strip().decode()
        return line

        
    def generate_prime(self, BITS):
        a = getrandbits(BITS)
        b = a << 282
        c = nextprime(b)
        return c
    

    def generate_coefs(self, BITS, LEN):
        return [getrandbits(BITS) for _ in range(LEN)]
    

    def get_sk(self):
        poly_t = ctypes.c_int32 * self.dilithium.N
        polyvec_t = poly_t * 4
        rho = ctypes.c_buffer(32)
        tr = ctypes.c_buffer(64)
        key = ctypes.c_buffer(32)
        t0 = polyvec_t()
        s1 = polyvec_t()
        s2 = polyvec_t()
        self.dilithium.dilithium_lib.pqcrystals_dilithium2_ref_unpack_sk(rho, tr, key, t0, s1, s2, self.dilithium.sk_buf)
        return ll_to_polylist(s1), ll_to_polylist(s2)


    def handle(self):
        signal.signal(signal.SIGALRM, self.timeout_handler)
        signal.alarm(40)
        self.dosend("welcome to my crypto system!")
        delta = 1184
        beta = 256
        tau = 704
        self.m = getrandbits(beta)
        self.dilithium = Dilithium()

        p = self.generate_prime(delta)
        q = self.generate_prime(delta)
        N = [p * q]
        ROUND = 25
        for _ in range(ROUND):
            d = getrandbits(704)
            N.append((p + d) * (q + d))
        self.dosend("N = " + str(N))
        s1, s2 = self.get_sk()
        s1 = np.array([i for j in s1 for i in j])
        s2 = np.array([i for j in s2 for i in j])
        H = []
        for i in range(ROUND * ROUND):
            tmp = np.array(self.generate_coefs(32, 1024))
            H.append(int(tmp.dot(s1) % self.dilithium.Q ))
            tmp = np.array(self.generate_coefs(32, 1024))
            H.append(int(tmp.dot(s2) % self.dilithium.Q))

        self.dosend("this is your hint!")
        self.dosend("H = " + str(H))
        self.dosend("another gift: you can choose one message to sign")
        m = int(self.recvline("m: "))
        signature = self.dilithium.sign_message(long_to_bytes(m))
        assert self.dilithium.verify_sign(long_to_bytes(m), signature)
        self.dosend("this is your signature")
        self.dosend("sinature = " + signature.hex())
        num = self.generate_coefs(4, 1)[0]
        self.dosend("you need to give me some signatures in hex format!")
        signatures = ast.literal_eval(self.recvline("signatures: "))
        assert len(list(set(signatures))) == len(signatures)
        answers = sum([self.dilithium.verify_sign(long_to_bytes(self.m), bytes.fromhex(sinature.zfill(len(signature) + len(signature)%2))) for sinature in signatures])
        if answers == num:
            self.dosend("congrats! you got the flag!")
            with open("flag.txt") as f:
                self.dosend(f.read())
        else:
            self.dosend("sorry, you failed!")
            exit()
        


class ThreadedServer(socketserver.ForkingMixIn, socketserver.TCPServer):
    pass


if __name__ == "__main__":
    HOST, PORT = '0.0.0.0', 13337
    server = ThreadedServer((HOST, PORT), Task)
    server.allow_reuse_address = True
    server.serve_forever()

*lwewl

from Crypto.Util.number import *
from random import randint
from secret import flag

assert flag.startswith(b'flag{') and flag.endswith(b'}')
flag = flag[5:-1]
flag1 = flag[:len(flag)//2]
flag2 = flag[len(flag)//2:]

class LWE:
    def __init__(self, lwe_dim, lwe_num_samples, lwe_plaintext_modulus, lwe_ciphertext_modulus, rlwe_dim, rlwe_modulus):
        self.lwe_dim = lwe_dim
        self.lwe_num_samples = lwe_num_samples
        self.lwe_plaintext_modulus = lwe_plaintext_modulus
        self.lwe_ciphertext_modulus = lwe_ciphertext_modulus
        self.lwe_secret_key = self.distribution(0, self.lwe_ciphertext_modulus - 1, self.lwe_dim)
        self.rlwe_dim = rlwe_dim
        self.rlwe_modulus = rlwe_modulus

    def distribution(self, lbound, rbound, dim):
        return [randint(lbound, rbound) for _ in range(dim)]

    def lwe_encrypt(self, message):
        a = self.distribution(0, lwe_ciphertext_modulus - 1, self.lwe_dim)
        e = self.distribution(-15, 15, 1)[0]
        return a, sum([a[i] * self.lwe_secret_key[i] for i in range(self.lwe_dim)]) + message + e * lwe_plaintext_modulus

    def lwe_keygen(self):
        A = []
        B = []
        for _ in range(self.lwe_num_samples):
            sample = self.lwe_encrypt(0)
            A.append(sample[0])
            B.append(sample[1])
        return A, B

    def encrypt(self, message, lwe_pubkey1, lwe_pubkey2):
        const = vector(ZZ, self.distribution(-1, 1, self.lwe_num_samples))
        e = self.distribution(-15, 15, 1)[0]
        return const * matrix(GF(lwe_ciphertext_modulus), lwe_pubkey1), const * vector(GF(lwe_ciphertext_modulus), lwe_pubkey2) + message + e * lwe_plaintext_modulus

    def rlwe_sample(self, flag):
        P.<x> = PolynomialRing(Zmod(self.rlwe_modulus))

        while True:
            monomials = [x^i for i in range(self.rlwe_dim + 1)]
            c = self.distribution(0, self.rlwe_modulus - 1, self.rlwe_dim) + [1]
            f = sum([c[i] * monomials[i] for i in range(self.rlwe_dim + 1)])
            PR = P.quo(f)
            if f.is_irreducible():
                break
        a = self.distribution(0, self.rlwe_modulus - 1, self.rlwe_dim)
        e = self.distribution(-5, 5, self.rlwe_dim)
        s = [flag[i] for i in range(len(flag))]
        b = PR(a) * PR(s) + PR(e)
        return a, b, f, self.rlwe_modulus

lwe_dimension = 2**9
lwe_num_samples = 2**9 + 2**6 + 2**5 + 2**2
lwe_plaintext_modulus = next_prime(256)
lwe_ciphertext_modulus = next_prime(1048576)
rlwe_dim = 64
rlwe_modulus = getPrime(128)

lwe = LWE(lwe_dimension, lwe_num_samples, lwe_plaintext_modulus, lwe_ciphertext_modulus, rlwe_dim, rlwe_modulus)
lwe_pubkey1, lwe_pubkey2 = lwe.lwe_keygen()
lwe_public_key = [lwe_pubkey1, lwe_pubkey2]
lwe_cipher1 = []
lwe_cipher2 = []
for flag_char in flag1:
    tmp1, tmp2 = lwe.encrypt(flag_char, lwe_pubkey1, lwe_pubkey2)
    lwe_cipher1.append(tmp1)
    lwe_cipher2.append(tmp2)

lwe_ciphertext = [lwe_cipher1, lwe_cipher2]
save(lwe_public_key, "lwe_public_key")
save(lwe_ciphertext, "lwe_ciphertext")

rlwe_ciphertext = lwe.rlwe_sample(flag2)
save(rlwe_ciphertext, "rlwe_ciphertext")

时隔两个多月，终于来写这道题wp了
参考：
DiceCTF 2023 WriteUps——membrane|廢文集中區
2024 CISCN x 长城杯铁人三项 初赛 WriteUp

challenge 1：

给了两个式子

$c_{1\times 612}*A_{612\times 512} = cipher1$

$c_{1\times 612}*B_{612\times 1}+m_0+257*e=cipher2$

先看第一个式子：
我们已知cipher1和$A_{612\times 512}$，一般情况下，可以直接用 solve_left求 $c_{1\times 612}$，但是这道题A矩阵不是满秩矩阵，举个例子：

$s = (x_1,x_2,x_3,x_4)*\left( \begin{matrix} m_{11} & m_{12} & m_{13}\\ m_{21} & m_{22} & m_{23} \\ m_{31} & m_{32} & m_{33} \\ m_{41} & m_{42} & m_{43} \\ \end{matrix} \right) =(c_1,c_2,c_3)$

$\begin{cases} m_{11}x_{1} + m_{21}x_{2} + m_{31}x_{3} + m_{41}x_{4} = c_1 \\ m_{12}x_{1} + m_{22}x_{2} + m_{32}x_{3} + m_{42}x_{4} = c_2 \\ m_{13}x_{1} + m_{23}x_{2} + m_{33}x_{3} + m_{43}x_{4} = c_3 \end{cases}$

这样的式子显然是不能得到确切的x的解，但是可以得到一个特解，还可以利用核空间来表示他的通解，通解可以用下式表示：

$c_{1\times 612} = (c_0,c_0,\cdots,c_0)_{1\times 612}+t_{1\times 100}*K_{100\times 612}$

• c_0表示当t都为0时的那一个特解
• K表示左核空间的一对基
• t是系数(未知)
  以此我们可以造一个格

$Q = \left( \begin{matrix} q & && \\ &q &&\\ & & \ddots&\\ &&&q \\ \end{matrix} \right)_{612\times612}$

$L = \left( \begin{matrix} K_{100\times 612} & 0_{100\times 1}\\ c_0& 1 \\ Q & 0_{612\times 1} \\ \end{matrix} \right)$

注意：造的格比较大，所以采用随机抽取t列K做规约，t太大会导致LLL时间太长，t太小可能规约不出来理想结果，测试后使用153(4*153=612)，最后规约的数拼在一起和直接规约结果是一样的，而且更省时

直接使用一下suhanhan师傅的exp
exp：

from multiprocessing import Pool
from random import shuffle
from tqdm import trange




def attack(range_):
    q = next_prime(1048576)  #1048583

    lwe_pubkey1, lwe_pubkey2 = load('lwe_public_key.sobj')
    lwe_cipher1, lwe_cipher2 = load('lwe_ciphertext.sobj')


    A = matrix(GF(q), 612, 512, lwe_pubkey1)
    B = matrix(GF(q), 612, 1, lwe_pubkey2)
    K = A.left_kernel().basis_matrix()  #求核空间

    def solve_c(c0, cols):  #col为选择的列数
        ALL = list(range(612))
        shuffle(ALL)  #利用这个打乱的列表来对应矩阵A列数的打乱,其实这边如果用置换矩阵来打乱效果应该也是一样的？
        sols = []
        for i in range(0, 612, cols):  #如果不是刚好整除可以再从前面的列随机选一下再加进来
            sel = ALL[i:i + cols]
            KK = matrix(ZZ, [K.column(j) for j in sel]).T
            L = KK.stack(matrix(ZZ, [c0[0][j] for j in sel])).stack(identity_matrix(cols) * q).augment(matrix(ZZ, 254, 1, [0] * 100 + [1] + [0] * cols))
            res = L.LLL()
            for row in res:
                if all(-1 <=j <= 1 for j in row):
                    if row[-1] == 1:
                        sols.append((sel, row[:-1:]))
                    elif row[-1] == -1:
                        sols.append((sel, -row[:-1:]))
        return sols


    tmp_flag = ''
    low, high = range_[0], range_[1]
    for ii in trange(low, high):
        tmp1, tmp2 = lwe_cipher1[ii], lwe_cipher2[ii]
        c = vector([0] * 612)
        c0 = A.solve_left(matrix(GF(q), 1, 512, tmp1)).change_ring(ZZ)
        sols = solve_c(c0, 153)
        for sel, row in sols:
            for idx, val in zip(sel, row):
                c[idx] = val
        tmp = ZZ(tmp2) - ZZ((c * B)[0])
        if tmp >= q // 2:
            tmp -= q
        m = tmp % 257
        e = (tmp - m) // 257
        assert -15 <= e <= 15
        tmp_flag += chr(m)
    return tmp_flag



if __name__ == "__main__":   
    flag1 = ''
    ranges = [(i, i + 3) for i in range(0, 18, 3)]
    with Pool(6) as pool:    
        tmp_flag = pool.imap(attack, ranges)
        flag1 = ''.join(tmp_flag)   
    print(flag1)  
    #a3bc5491-fa53-4f47

到此为止解决了challenge 1，但是我做这道题的时候有点想法不确定能不能实现，先在这里记录一下：
参考：Crypto趣题-Lattice——Matrix|糖醋小鸡块的blog
在遇到这种不满秩的矩阵解方程时，鸡块造了一个这样的格：

$x_{1\times 32}*M_{32\times 16} = c_{1\times 16}\quad(mod\;p)$

$(x_1,x_2,...,x_{32},k_1,k_2,...,k_{16},-1)* \left( \begin{matrix} m_{1,1} & m_{1,2} &... &m_{1,16} &1&0&...&0&0\\ m_{2,1} & m_{2,2} &... &m_{2,16} &0&1&...&0&0 \\ & &...\\ m_{31,1} & m_{31,2} &... &m_{31,16}&0&0&...&1&0\\ m_{32,1} & m_{32,2} &... &m_{32,16}&0&0&...&0&1 \\ p&0&...&0&0&0&...&0&0\\ 0&p&...&0&0&0&...&0&0\\ &&...\\ 0&0&...&p&0&0&...&0&0\\ c_1&c_2&...&c_{16}&0&0&...&0&0\\ \end{matrix} \right)\\ = (0,0,...,0,x_1,x_2,...,x_{32})$

我使用这个格试验了一下，格太大时间很长，所以猜测应该也可以通过shuffle()来抽取几列进行规约来节省时间

challenge 2

一个常规的rlwe
直接用2024-NSSCTF-Round-18-Basic-wp-crypto|糖醋小鸡块的blog的脚本
exp：

from Crypto.Util.number import *
a, b, f, p = load('C:\\Users\\厉子健\\Desktop\\rlwe_ciphertext.sobj')
n = 64
A = a
B = b.list()
def construct_poly_mul_mat(n,v,b):
    assert v[-1] == 1
    mat1 = Matrix(ZZ,n,2*n-1)
    for i in range(n):
        for j in range(n):
            mat1[i,j+i] = b[j]
    mat2 = Matrix(ZZ,2*n-1,n)
    for i in range(n):
        mat2[i,i] = 1
    for i in range(n,2*n-1):
        for j in range(i-n,n):
            mat2[i,j] = -v[j-(i-n)]

        init_row = vector(ZZ,n*[0])
        for j in range(i-n):
            temp = -v[n-1-j]*vector(ZZ,mat2[i-j-1])
            init_row += temp
        for j in range(n):
            mat2[i,j] += init_row[j]
    return(mat1*mat2)

v = f.list()
poly_mul_mat = construct_poly_mul_mat(n,v,A)

I = identity_matrix(n)
B_mat = Matrix(ZZ,B)
O = diagonal_matrix([0]*n)
O_vec = Matrix(ZZ,1,n)
O_vec_T = Matrix(ZZ,n,1)
L = block_matrix(ZZ,[[p*I,O,0],[poly_mul_mat,I,O_vec_T],[B_mat,O_vec,1]])

res = L.LLL()[0]

s = res[n:2*n]
for i in s:
    print(chr(abs(i)),end = "")
# -8819-856a8fe5ada0