## 1. Copperbox
### Challenge:
:::info
Cedric found a mysterious box made of pure copper in the old archive. He is convinced that it contains the secrets he is looking for, but he is unable to penetrate the metal case. Can you help?
:::
---
Source:

import secrets

p = 0x31337313373133731337313373133731337313373133731337313373133732ad
a = 0xdeadbeefdeadbeefdeadbeefdeadbeefdeadbeefdeadbeefdeadbeefdeadbeef
b = 0xdeadc0dedeadc0dedeadc0dedeadc0dedeadc0dedeadc0dedeadc0dedeadc0de

def lcg(x, a, b):
    while True:
        yield (x := a*x + b)

flag = open('flag.txt', 'rb').read()
x = int.from_bytes(flag + secrets.token_bytes(30-len(flag)), 'big')
gen = lcg(x, a, b)

h1 = next(gen) * pow(next(gen), -1, p) % p
h2 = next(gen) * pow(next(gen), -1, p) % p

with open('output.txt', 'w') as o:
    trunc = 48
    # oops, i forgot the last part
    o.write(f'hint1 = {h1 >> trunc}\n')
    o.write(f'hint2 = {h2 >> trunc}\n')

Output:

hint1 = 77759147870011250959067600299812670660963056658309113392093130
hint2 = 50608194198883881938583003429122755064581079722494357415324546

### Analysis

Trông chall có vẻ ngắn :penguin:, nhưng ngắn thì thường hay khó.
Chall sử dụng LCG (Linear Congruential Generator). Source cấp cho ta số nguyên tố p cùng 2 số a và b. Công thức LCG:
$$
s_{i+1}= a.s_i + b \pmod p
$$
Flag x được đem đi padding (`x = int.from_bytes(flag + secrets.token_bytes(30-len(flag)), 'big')`), rồi lấy giá trị đó làm $s_0$. Thuật toán tạo ra 4 giá trị $s_1,s_2,s_3,s_4$. Từ 4 giá trị này, tính ra được hai giá trị $h1$ và $h2$:
\begin{gather}
h1 = s_1.s_2^{-1} \pmod p\\
h2 = s_3.s_4^{-1} \pmod p
\end{gather}đến cuối thì trả về `h1 >> 48` và `h2 >> 48`.
### Exploit
Từ cặp phương trình:
\begin{gather}
h1 = s_1.s_2^{-1} \pmod p\\
h2 = s_3.s_4^{-1} \pmod p \\
=> s_1 - h1.s_2 \equiv 0 \pmod p \\
s_3 - h2.s_4 \equiv 0 \pmod p
\end{gather}
Với giá trị của flag sau khi padded là x, ta có thể viết lại phương trình $s_{i+1}= a.s_i + b \pmod p$ theo x sẽ là $s_i = a^i.x+b.\frac{a^i-1}{a-1}$, viết gọn là $s_i = c_i.x +d_i$.
Với việc $h_1$ và $h_2$ bị dịch 48 bit và trả về hai giá trị $hint1$ và $hint2$ tương ứng, ta có thể viết là:
\begin{gather}
h_1 = hint1<<48 + y1\\
h_2 = hint2<<48 + y2
\end{gather}
Thay vào hai phương trình, ta có:
\begin{gather}
c_1x + d_1 - (hint1<<48 + y1)(c_2x+d_2) \equiv 0 \pmod p \\
c_3x + d_3 - (hint2<<48 + y2)(c_4x+d_4) \equiv 0 \pmod p
\end{gather}
Nhận thấy đây là một hệ 2 phương trình nhưng có đến 3 ẩn. Mục tiêu trước tiên của ta là tìm ra hai giá trị $h1$ và $h2$, vậy nên mình sẽ muốn khử giá trị x trước, sau đó tìm ra y1 và y2 rồi cuối cùng là x và flag. Viết lại hai phương trình với các giá trị a và b thì ta có hai phương trình:

f1 = a * x + b - ((hint1 << 48) + y1) * (a ** 2 * x + a * b + b)
f2 = a ** 3 * x + (a ** 2 + a + 1) * b - ((hint2 << 48) + y2) * (a ** 4 * x + (a ** 3 + a ** 2 + a + 1) * b)

Mò một lúc thì mình biết được rằng có thể tính resultant để loại bỏ bớt nghiệm x. Kết quả trả về sẽ là một phương trình không có biến x. Code như sau:

from sage.all import *

p = 0x31337313373133731337313373133731337313373133731337313373133732ad
a = 0xdeadbeefdeadbeefdeadbeefdeadbeefdeadbeefdeadbeefdeadbeefdeadbeef
b = 0xdeadc0dedeadc0dedeadc0dedeadc0dedeadc0dedeadc0dedeadc0dedeadc0de
hint1 = 77759147870011250959067600299812670660963056658309113392093130
hint2 = 50608194198883881938583003429122755064581079722494357415324546

x, y1, y2 = var('x y1 y2')
H1 = (hint1 << 48) + y1
H2 = (hint2 << 48) + y2

f1 = a * x + b - H1 * (a^2 * x + a * b + b)
f2 = a^3 * x + (a^2 + a + 1) * b - H2 * (a^4 * x + (a^3 + a^2 + a + 1) * b)

R.<y1,y2> = PolynomialRing(GF(p))
S.<x> = PolynomialRing(R)

poly1 = S(a * x + b - ((hint1 << 48) + y1) * (a^2 * x + a * b + b))
poly2 = S(a^3 * x + (a^2 + a + 1) * b - ((hint2 << 48) + y2) * (a^4 * x + (a^3 + a^2 + a + 1) * b))

res = poly1.resultant(poly2)
print(res)
#18809326409291330862604976668985876478440966155687736658634682104375929937722*y1*y2 + 8847093735487366209093966454823957795890605679638006162560568687667550519513*y1 + 9116455652870841890444023155057972534288191216309786202639270987921404467639*y2 + 20358866995656196776672201511491715018123597440152646399727887731092141654428

Ngoài ra, còn một cách viết khác với ma trận Sylvester cũng cho ra kết quả tương tự (credit to my man **H4n1e**):

from sage.all import *

p = 0x31337313373133731337313373133731337313373133731337313373133732ad
a = 0xdeadbeefdeadbeefdeadbeefdeadbeefdeadbeefdeadbeefdeadbeefdeadbeef
b = 0xdeadc0dedeadc0dedeadc0dedeadc0dedeadc0dedeadc0dedeadc0dedeadc0de
hint1 = 77759147870011250959067600299812670660963056658309113392093130
hint2 = 50608194198883881938583003429122755064581079722494357415324546


P = PolynomialRing(GF(p), 'x, y1, y2')
x, y1, y2 = P.gens()
f1 = a * x + b - ((hint1 << 48) + y1) * (a ** 2 * x + a * b + b)
f2 = a ** 3 * x + (a ** 2 + a + 1) * b - ((hint2 << 48) + y2) * (a ** 4 * x + (a ** 3 + a ** 2 + a + 1) * b)


g  = f1.sylvester_matrix(f2, x).det()

Có được đa thức $g(y1,y2) \equiv 0 \pmod p$, dùng LLL để tìm lại giá trị y1, y2. Mặc dù bước này có thể sử dụng Coppersmith để giải, nhưng mới học LLL nên thử áp vào xem sao.
Đa thức tìm được có dạng $c_{11}.y_1.y_2+c_{10}.y_1+c_{01}.y_2 \equiv c_{00}\pmod p$. Lập lattice:
\begin{gather}
M =
\begin{bmatrix}
I & c\\
0 & p
\end{bmatrix}
\end{gather}
Với c là vector $\{c_{11},c_{10},c_{01},c_{00}\}$, gồm các hệ số của y1 và y2 và phép toán thực hiện trong trường $GF(p)$.

from sage.all import *

p = 0x31337313373133731337313373133731337313373133731337313373133732ad
N = 1 << 48

c11 = 18809326409291330862604976668985876478440966155687736658634682104375929937722
c10 = 8847093735487366209093966454823957795890605679638006162560568687667550519513
c01 = 9116455652870841890444023155057972534288191216309786202639270987921404467639
c00 = 20358866995656196776672201511491715018123597440152646399727887731092141654428

a = Matrix([
    [1, 0, 0, 0, c11],
    [0, 1, 0, 0, c10],
    [0, 0, 1, 0, c01],
    [0, 0, 0, 1, -c00],
    [0, 0, 0, 0, p]
])

W = diagonal_matrix([1, N, N, 1 << 96, 2 ** 1000], sparse=False)
a = (a * W).LLL() / W

result = list(a[0])
print(result)
#[13182624764637853451387439645, 53006259096585, 248699398699637, -1, 0]

Đến đây thì ta đã tìm được `y1 = 53006259096585` và `y2 = 248699398699637`. Tính được giá trị `h1` và `h2`, đến đây thì có thể tìm được x:

from Crypto.Util.number import long_to_bytes
y1 = 53006259096585
y2 = 248699398699637
hint1 = 77759147870011250959067600299812670660963056658309113392093130
hint2 = 50608194198883881938583003429122755064581079722494357415324546
p = 0x31337313373133731337313373133731337313373133731337313373133732ad
a = 0xdeadbeefdeadbeefdeadbeefdeadbeefdeadbeefdeadbeefdeadbeefdeadbeef
b = 0xdeadc0dedeadc0dedeadc0dedeadc0dedeadc0dedeadc0dedeadc0dedeadc0de

shifted_hint1 = hint1 * (2^48)
shifted_hint2 = hint2 * (2^48)

P.<x> = PolynomialRing(GF(p))

f1 = a * x + b - ((shifted_hint1 + y1)) * (a^2 * x + a*b + b)
f2 = a^3 * x + (a^2 + a + 1)*b - ((shifted_hint2 + y2)) * (a^4 * x + (a^3 + a^2 + a + 1)*b)

sol_f1 = f1.roots()
print(sol_f1)

sol_f2 = f2.roots()
print(sol_f2)

common_x = list(set(sol_f1).intersection(set(sol_f2)))
print(common_x)
#[(499197373884959800644483313698329481494906972244576574509349368118463686, 1)]
print(long_to_bytes(499197373884959800644483313698329481494906972244576574509349368118463686))
#b'HTB{sm1th1ng_mY_c0pp3r_fl4G}L\xc6'

## 2. Verilicious
### Challenge
:::warning
A sacred ward, once thought unbreakable, is built upon a foundation of misplaced trust. The ancient order that devised it never foresaw the cracks in their own defenses. A true cipher-weaver, one with a deep understanding of hidden structures, may find a way to tear it down. Can you?
:::
Source:

from Crypto.Cipher import PKCS1_v1_5
from Crypto.Random import get_random_bytes
from Crypto.PublicKey import RSA
from Crypto.Util.number import getPrime, long_to_bytes as l2b, bytes_to_long as b2l
from random import seed, randbytes
from data import R, s

seed(s)

class Verilicious:
    def __init__(self):
        self.key = RSA.import_key(open('privkey.pem', 'rb').read())
        self.cipher = PKCS1_v1_5.new(self.key, randbytes)

    def verify(self, c):
        c = b'\x00'*(self.key.n.bit_length()//8-len(c)) + c
        return int(self.cipher.decrypt(c, sen := get_random_bytes(self.key.n.bit_length()//8)) != sen)

    def encrypt(self, m):
        return self.cipher.encrypt(m)

orac = Verilicious()

enc_flag = orac.encrypt(open('flag.txt', 'rb').read()).hex()

assert all(orac.verify(l2b(pow(r, orac.key.e, orac.key.n) * int(enc_flag, 16) % orac.key.n)) for r in R)

import os ; os.system('openssl rsa -in privkey.pem -pubout -out pubkey.pem')

with open('output.txt', 'w') as f:
    f.write(f'{enc_flag = }\n')
    f.write(f'{R = }\n')

Output:

enc_flag = '723e808e262486bb05c39cef2a4ca2334e885ce90ebf318d6f0ab1d9e95fc9650cf95e7e4d5df2e3afef8aba4796240e958be4cc933cb944a0ec748619cdb9138b11ad0eb2e5f492c6280909e55def3db966cc96eb02f0212be4b33c04f5b4576d2d87a180649b6770dac45fd07d17d0a68bbbed87c0d18cd1610c1d52c25b52'
R = [134115821619995314496122564547916126947599980819405235082517192808507030501092656706168887309982033289987953471348763955476089416556147406160259955040757648917395767651179830169779066153799931136707924690852827516288300826437643041264226686893395744277118552895070277286649305077822610943759606681582403285622, ...,
130829797409030268973352996767957779365311690002579378946982172341323743450377476516069574855855224485237210467599418067612712824380628946412878127911436900313997947604882192929110839317179000399541063224855604445875473626055054487308281408204582792705082064340692302772564869303002107776645416860156072622955]

pubkey.pem:

-----BEGIN PUBLIC KEY-----
MIGfMA0GCSqGSIb3DQEBAQUAA4GNADCBiQKBgQDWmV7JV9wyE9iy3UBOOKlRdElU
ws+0JCymoKJAlJ7GoJRRpRAaaqsMC34wOgc4pnIlx44QwRGu2ldYLqb0LweVLLRv
oppUDMUFLjoKyRoam0ZfGZi5HjkHvimi/Tgmi4eI32+w0siLNA3+rIFj4ltQCmfX
tIMfJt7YHVROdEKNKwIDAQAB
-----END PUBLIC KEY-----

### Analysis
Mã hóa RSA 4sure. Từ file pubkey, ta có được giá trị N và e:

e = 65537
n = 150696614629132057109111480582577778723820969345630437367143066912323132221202404868706476552913390819783711643546310151820832496789087095879886490636812504690842921497146409465300931707997961967930772720006749985178086455545423786599439466838471458478125360273903249535338101526493597879081698428178510548267

Trong file output, ta có được flag bị mã hóa dạng hex và tập R gồm 78 phần tử. Đi vào class `Verilicious`, ta thấy rằng mã hóa sử dụng PKCS#1 v1.5. Hàm `verify` nhận bản mã `c`, giải mã và kiểm tra sự hợp lệ của padding sử dụng tham số `sen`. Hàm `encrypt` mã hóa sử dụng mã hóa RSA.
Đáng chú ý nhất có lẽ là hàm `verify`. verify nhận giá trị c, giải mã và kiểm tra xem thông điệp có được đệm theo chuẩn PKCS#1 v1.5 hay không. Để tạo ra các kết quả xác định, một sed cố định được sử dụng cho `random`. Nếu không được pad đúng cách, `sen` được trả về, đây cơ bản là một chuỗi byte ngẫu nhiên. Trong tập $R$ với các giá trị $r_i$, ta có:
$$
verify(c.r_i^e \pmod N)=verify((mr_i)^e \pmod N) = 1
$$hay nói cách khác thì $mr_0, mr_1, mr_2,...,mr_{77}$ đều hợp lệ.
Hàm verify hoạt động như thế này:
Research các cách tấn công liên quan đến PKSC, thấy được trong document mà anh Tuệ đưa cho có cái này:
Hiểu rằng khi được pad bằng PKSC#1 v1.5 thì bản mã luôn bắt đầu bằng `\x00\x02`.
Đây có thể đưa về bài toán HNP, có thể giải bằng LLL. Mình có thể lập lattice như dưới đây:
([chôm chôm từ đây](https://hackmd.io/@nhatviet/rkb0WFXbR#Hidden-Number-Problem))

Code:

from Crypto.Util.number import getPrime, long_to_bytes as l2b, bytes_to_long as b2l
enc_flag = '723e808e262486bb05c39cef2a4ca2334e885ce90ebf318d6f0ab1d9e95fc9650cf95e7e4d5df2e3afef8aba4796240e958be4cc933cb944a0ec748619cdb9138b11ad0eb2e5f492c6280909e55def3db966cc96eb02f0212be4b33c04f5b4576d2d87a180649b6770dac45fd07d17d0a68bbbed87c0d18cd1610c1d52c25b52'
R = [134115821619995314496122564547916126947599980819405235082517192808507030501092656706168887309982033289987953471348763955476089416556147406160259955040757648917395767651179830169779066153799931136707924690852827516288300826437643041264226686893395744277118552895070277286649305077822610943759606681582403285622, 126686940482640273524125094354894225795941673993143643794156275578369198472583478553784929652753543884124774686804705186877104318595795254647323754005334399647982071651049942560477743142470231462889041407837267742625786144055962080350415361176206007614719875397296238162863188765950829446087586697209194992647, 137700382018057974172801996890791468140252370097114533331144882331394632683850942352930846213387255651807591056575151165151821404724765116419181774183159941114789572865774691939551028712774400221727830866466949861946298957357691615350511045647142347165504397341701652469388698714703335038415612851594768265730, 11345090943857551298893350047778290247351987888446929151460627421081288322850272396607499382644573641725079169399292658877661305665824106993961939805232014754354929634319667417844903300007441697088293004659522765108146476052721225986953530690715949616049873309178488075140659007114922264423613679921086297454, 8243033103849375366214077610986869692939255424651215481170249554422467022331691456032000509340702393808895926994440735368619062210434273430249282007185400714538771434327364503395892235103103470054162289662454139622742520100762493619371229895954298607540243061038326539706592728230347259691678868677152044994, 20029653153410965022543927121537891643867865766164870087036816407614708056735668015008498465803648399584208967487667576040889586285869017929227716584630382285304189051665141702936407032405322109610921680877120876429579695662879409801476723263900889285956477542843798176479967974998324710434490825972264869636, 149610206036302098686322006263598085270386864336505502127403243835517052049055163264650559483614217070959507372017216226825545802300948562468718276693274492673856583172616720483713318949102250123131010071297606983424640999754637694655804021800306455419495600882350654009343959077307817574837737187465795062091, 91316124559682343208074208813723209163052879008810554598159813236459719417838681357319178848139410053028511191000427830825441750628019383705685275921576966868125801154712692642258256964327250498375331724751861179769099892353590092490597048340408573796462539147836172513018084627735376367108859303865171511186, 112506957691013811301214275792258698352942897640919001808631327988034087051571618538019422776325033038514281959834586395709104591707580916848960336181887229024565726460519873518471809658546356679995872384052382047451030172958276881486514045486447051397012668658051735648437184272105045080671058672430832635379, 53820880539788068656111206060467418637589519198042590464142016200864569464624198007844978013900856408567314147011384775123406186021206685112387276895755328523218200924530032995302060388636977222303459285995558853900345978662322013601091050025177183937301743744434660621268655445812344264546392198625298243776, 112777748026052034887880732094789333080976863096436028491057183969297521302053766744199215574876237313919703290816273715007242523355217591831493406992836973703850350531947198182102964338695710967811842762719639173247511205341500439037269622259643929286450842942983016300078995690251964448961460800081578966321, 19405895457804838534429296125132000146361695227964879657208108616631611699055632071496824499230311041391304160621321491579889875273332229610087933645839800774688771509101004154531036166333410222574953502792903590517679509102754345819784146119502585836096551570965796785143666655131189761578357964410010048126, 129829766887698854518441173602138687228472398591016009480256302067700430768157163788383341528803480925941469069846111656499170016237114375259712468421520425648742515620074558477969099182669734836613256042665214047734243358438219467389230886071359701204787448954177322733963489708837416080630803131561927975866, 142753554762407317418064593088581485770994009035623759624745794450022154254410560044337398014884427071578477755753297732435636964687189179843392414923347995708556874636633545610170155200890185838212275526551777533403189160669690418461699954413163236961486096361746342352466426568187127773789991442923590687098, 31848485606403805660359010256458859933561680110753174294368170127902357093111090324815234108951386841730209973680764934067081739632412872174521545618218633998271500176896814510764824208363263774876451479981322635210991509586097341996524291566854664137801833119902516189909887554845632337233003618961931398265, 119427280513223394465671587936817129340474436986146679808299863745370773172322627283783972788929779720719874249124534251555207155305834085611708264351177098456941681016029887788115925439718919160482636038012687614032024024554741219581489481933689253951547348069278838091519972195418651202612643508290983082367, 71613131691072916431457333730256441527872084731798610502545924910967785743936683076937736145664513231970752324897210652713700428473246412782236894596174492215048479809179710135056236788305443077894242449646947942899482434893360025951016252048071480556484809927133240235939345574631121859269021670931249455209, 55931276480201064561212160109434903927810346508498965824503894607485088777712841792542635776657364286195994239425096077623617896778080481300148221454029594606776134206519787490888923195818849034615415097268866630101502072944285890452719057991427079368024154867455912885746643423308784013706621098854199287885, 45453250333134002159475105074532179391947577652902995324382950527219787059334126164115967471286216608409826301992907982500817432162376889522935088702163739521277183031777261274356467600845500177074921180458362288632330329726553320471675499966119909557386541316543593552318585426836032973427963350304728038604, 22776398347754436334415967090013538910856440120622875754087049715445583542472595862572076975543045738000913875085716067407777524276874252475043524397600636191688500978519071482403076242963636891862036284501789827172052247791747790416932142713797301824514401872748977034296564306894179907557348257091862993124, 72097855146097516517926404693372078544785753794489580738432244018681527163163614199417222494555050322436982483051228479962895248225688582214551806009082897486628311694983330042034927226767682224165949996068489652339573973367946983448877966036244884058330163270551297138048645654530781077109620908837241644595, 33788611695548710258786604004395492813515526838965903788325650989505464314142569035590326039907880431575689715404483012914664185323778200840622622570700346272660047419256049443191003377557570780061135695758384058022595117056839820894715875730866685287309641373350484299903079330455447446734521699546146327377, 71580831088514761998941611146487603717949222245552951283142350837097516300007890084635041563074829339295889477378430185881025793370223794951593688502196419684030393466364573653410386432354047707182043609454659960953300417654763813771754158051841424625722427431931617407780217916755274165289623648771602370321, 60154824588247300758317864479504213491013905086995914401697444268160958291594903315952654341551076811810347186811041286454798529944458304111653808222541907517321117598562056305697734814636848865846721431057739149164142040015392573000803031905751795437681622076570122357285500719017910643987658169015266995787, 133229027552304562350749113186352510066399952626204167507023336930418797081589577213205771140861708097123649571250123554060711526015132933191972453099412659799985558315445952578254719250702319346771263947954861229758660241521705934517585110128017151383952876129879702480319617002570041237659361034751018767962, 49424498448453418981780043749883850149685593575762680016632520578023066674934203120908342872085168879864126990622799380820875728860416097340242122251226847254418023995345167339727781435968479201144154055951254497456573277814432879248680059406564890858586206254428697761436801302716503940017785981258178889558, 137520851721938412994104141504416409928993113615331093761596065872170362960575675329502697032557559641951917864243392185857101174104772854400519718687029981631568877418764808100436893662916289450535512686490751204865173306011924652753579145605481999366391313397488160738436093692615278799128424376503701721057, 122660530441656704682291330890848436490287055655712331153816744613446460341613856194950091586820657944039914166008481346297505105696896223600167045517983194443697946922712750116194694524027835134883463877251055761080164584071319102302093221564564708938563135190217574911107179961848047138832431834616241874491, 71919458804584969138329772463937357894279465534733634554698162389428158842393640344014738343895556465936826828615128149256589067308629059007268877733539789591763975671236013556153681699401434955011748209286256339243848412808170126927390116006491288766190214307554068335543145426219007016337141615056893363096, 83981044266615346668992711332478965320549701990847032389271665887350440941009555054741832884242369336071488305332407737722160015596001076180472443559357858332588712551386607215636113327709020873912806189071716044244475129048406480735239052337937759658564664559822263134456251195122218309731156693009364246115, 113526245869492002386819808028719183495254441541322434616734339008157290605256204755443542940518440388866174601257899385042422417254001060594861162378537709040846287682886328951075705141106883748733357050763424482372544756470518285946112590063395573633925278995301071667950884287797276429413700260746814612724, 10778333149738296249606428743141036087673940932784928690833085912067765786592692842506725124432138421811889392620731247674932566342287765116316958486580959829638381269502585878029223347693390702371325011557750248519127550419000533782995064910385765375254438442047999482715797022447801460586631871714440811006, 82374844386696358215488030085215624454239597925277257621065695502366211880195906896916025387768061728962246360067193858893687343233778507670016763806686452400272373616383247477432277099682611510273856492829538758415868135926706256819954667874983489708509878920107769996464888662641088448484443994596068277031, 133851320478944782300829367538219394760069515617595912310203195387138353397907776296182918533923228937923740485069287342153872772296595783863153436798788341026864532634032790862018432749134695668891838779713877036507192627152535522015004403801543900107236319249202244118451881989324115120282404718028960752590, 86856971212723907962265522737132279286450867915429195107179329613980973574679256753848739991673641810544903457373127834785436886976887709517346465352392284874663419242105641801825840665436026285253360566625723214060796042113733453566405856103366905452513799525132359758555658191883574637456800568551279464096, 56261905097412379039475002608051608139924020193741602440873763653629946034171757730757567224412330044488990441318274893272720417297619329566497969125221818165619354502540568094713610078868260721850788589072318237879703008703671343754674565598605297145067643609585527578385726583120949563247470292431676707095, 17125941790404002706068303081270165379083470009417705715736395866453116457152593836336219590003464851830933631503824645839229957797670511797987360187513815469982464240704861326816218323851530295878510611758324523984037411437295422568750421467718530888459196113087268571403084702783647264338828719239632743485, 71838729667517395896398485835102850037185257605166619360904353940933046357095565237718225390275809541021942046806337810377489573659562253891545415817176698280682302979274542417750636084458188805073848282629096523363836619758188267751812075303984587938050814557370816755571321415628376955864524146999868252460, 127974746344151231383604948219131948022498918778022836762057280350019291640867437586581603755464286084968353980306950345300178495774575903110744418620637520621301196458897557324658381282022808591810198763373335605521988079663798490207190852439358537157445928427489652600555565173461541941923771011126087491992, 52142948073333942465300501391458180255258792137508707947185530370314233009187637715252131976886442793356262235532583951043256181865337343630400114254589537352162899476658691643501313542083612688103294406123493851631427583696573660464188034397230262705745175462855436843425765235959284281584793363560248220126, 57286497064011335982545504168325882682222763813397141869229285275629057407417157616290838681522612364631089271974594323265941744347737793843289362333253949624281708326301874036705865798151111845455218586209539254699064186589281512683745458302693597700806095927906734797923501852455654597532902245873000586219, 91486578095731795863641171891297179774171492166832871440693422020035468567861719969756198258955062108497547793110833299074053541512858279604213093819608920211718597710234336743964614459695701442993521151114199083965155147219250827072802002021214076136279023407247700596719184614932275412977995617945264115156, 44881695511720751253110051616032820323149197003129630046353832954247396427155584170406243595999531069365422542473518446473067764175826421576497946071256811071409089683859488766882949880556713166426791554064798608451704845110797788467750550555148504145102558334174589801924758678599325669333252775343731397755, 66577991951640377940305512154057696998882156706139658273893421926823842513383662884872498268329663056705670844376870647682208769180512858778535806856966291692871806179861992436876978634927300214651693807565332257199464920538307573454864668880794435167252931316653942833222200662647129739394289067732387329208, 75502747582374165111970117640891332633674595738633020635487107504413605685869993875922674661085976527416635036740854557484346436179747322108315826536596903169451399413997158393701670765865023422945142459829510837835133549305106390187739891071075475060080639753565121678226547764829885616698380964160353116926, 41046367212666707562561717415608546853908723744325483734052600386040692630774245588693948871576947918988417333356036608672260156954800480343778100751106264680628792230163199549017895038914879340044516568172656004408520178985041807201432843452616079664552587051509660770033863906055684703525487542443570302244, 83806472919569651054862978818601489707300185771944129184997298047993466205260786164924796178283728871665202176568703346056013399365769087180430344149320818697008299310797077762235941586068080902312021501896275779428242552059150587741617617936198056502807393974315658489642291638568782728198979644919299212715, 24739743209823951489766433199032092643057692214072547970498159971575156904118004617298171321356162636324732269206585237845975158750481379293371094043234869280085524697643627955125384244905339024763223228396490612144101032366274011273718275081508914231081038861751332977936286610898609589530264938001982293664, 82129440544669586934394114922355746567871927215884829311461059973225934947781996853360844797569871993698671847962080223217354395354845434409582271295616851866893448681562851690372159996010846264018986692956705621771189920816647897792978634393418192181564102817367849081255956343080899628584607298258004733996, 125552012717651183360247308070011890876729141918858460502143730636255125875830320044249689971762842597646559530452930361131164296263057198928027684040324524581416870766349465968499608482478060900125605854425109129815341209917995515282654173777769158657867700581181207068685404698725523669466797346730304285571, 83947870853689996471074310034092953984257663199720902983758486827948442558467300760429971433520453027300219532964447764337873932205766511101705648864277872050935086397861067376670962445643494427457298241410966409365051763099614769560931472859191107718079054735135217441034188201443530434650208283592266287165, 18959741741653643990117190647584745543855142883131602972595053314821122448381252215178556150503805159621724061571905444118692566059395769251946915157931438335410738423998178147440394291613476103786532027698320116860225814815079281129535421730856533130332542431987496875511309480445212503841162538047915143159, 107612465943150417029479755114658077125496770072550346231710797329519737195975009080497301598414721894604835627940895660997959987679303781196029634395813456213594175513956565520819104375564102891915189694581368847704002991793226380676124251760651958095132938649894353349009803875057192223276967439627426317987, 37277928756112443758963176833362881294624317669412376598425463541168921107044065296731945863091956067035176580720573588717534511688827137235224682665257997654261792262808604426109495114356161826432368833503726841924267897271631727460019120714217793961749710681385670939277424772565279964285608083425408927782, 129358305657534137928454639739943612931709250799892293835469448501711792548090049471856320994054615683148345585974909728453830662422225137158850651954869064685977121996084611116249600242286343950417812465580180711124697562827677882618346842687566844522792137789808797060303033049525269602607145198900296452103, 139352996059386986594788650162753175273432132369394202697887222092226087271755513301429168820885927379742435360091148126915838160417078681375860841419769004653460977569768459293315899065311751087433070535922954349715229069406553971250493219689429791988199395816825683930820736487870076660365525410910478862304, 61471323757508646826749758004672828688160061323635616553075261071717618215238241912395352164128544686094007324613055429323602892654739764311752763802241684984936204707538417929211336646976805729278604440593432155285350636246157201386000768129000583060688992675762378394131402888107770351367304925466626214048, 114962144783461983549669796975568112996782182228310402397172751754543428538678431793589522214144081333572080634006005528027039752176111524319614093598297031613731278988601336187958050272185591619394012246337102344443329379960925776166181024957229573848536349114811744640925979599779393985681838332717716441294, 48255023546265027347984580518215873856374173764765564394781014589560438381965149281418028032606158247650819534637673261692965824832487118862552330740599609519200786970397584046880858358279904356494193781235701393668370159040296435569977721648781017277266718645578361090468988813280418744887644824597038761492, 27598184226061722561421909420242685247530267321561341260982478729272457839064031236869824663285645138596475495467481730052973967387040285804661489807093920964019503119841013978403550910795469869312253299494569549678397930546758208225275376432671148573000655491059478679159805093370787242474438587116179835254, 9172189900725146147320014233819417944972736522906115085200626165643144611479158875456050521838059028176056950793248400405976760098708199644480431086019875730389796948309150399026924402724074200274808284364090021240334313769340314425941767599744464531858236835676814799788454350054408907682304413451856914763, 112454930650486243223444475466715721228514923804861107156569536455788574089671134754391692974340847164372159380731997341335446439428628496640949731117857223715415627146287801390475387414261934807529727408346775554306133971000750998882883801683358336218685876634166158867354123900398628093567259830236389527462, 57582665235477673234971900359941596367925201095652005203528383346250079352794727403160672349375805059941235961990823919061645434858708113960626569323021774157203119645075643479066566725319094388225611600779197537434550710085275048849233156790057851139338203553968886988611797056889749248067141450187538903838, 55453692904278762147507492837272344999608085498317687500857454405515852458462595599826271215060714248916849617734712728449463285666514490991698881180820426039695135344978645048718406553687688348907025271450489585481109307279406962524446184927577832621122127757458854796129869037917019082245682162460958450635, 37236040377767026836201014213343958728521337333276018082514478497599227101314052548574676401080933526160744922882581153787344008604377348564607972552056734182645782461245411089737311308245663057858048453076051575356238379292361138984177518218512142682871806330692758190061375016639307225178605658043424627686, 82769858937118339412083115982330899266613898643428579499591447230927840273521694287981670135340609656558076143968548344893960144314052926281153393616195093583624815422122194566479936563229764790582444716949479299011012103414346471261561637167364046829854784241512021448434797057172664081146824315765918302757, 105451159029524574579228316115495933452351075366509686689498625190934805740584327463649134964671345071741969583813669362212159963424032955211954007998592686593435736392885387705332547807919064670303589870312388845363462930208179658725667070862802833494919310558431676975890889343149337029006974551009418964964, 18259433849406921008492950543135544457281668954765127757131107440835592156871611795730237625053177221690052727063828023555912001111475461224352735224643966818941138857222639755892144008290148193980318425870696979587528014945132804078915631313452810048995379989122287598486654650279049661238555283401034949898, 78525167495322929975512457097464718088537184796626822533797724324800009438643227590499112423982363077008038335141900726960786973776021364251492894530883613770194189300674399811493557360751271747863845161064410829788475335386441069243327175469636135982092290795015294893327004240375664613283088410781761382830, 112485042460783721670013506716566790838592536945604536251812331499603059455502034125853493425571342502947335758387876092100908225091873211842790191638720723091456936203918340624730312732926779434533921586444948568019295848920312745076065483095223140554427640600809640024386062369665992074230368098717176592756, 95576919179139279079226574650282940474445688562801492652871566846892408224664427972493100781597873993344814045250438105833732687753293207127900065283011725451074598652442413698010373946991380013535996249926384138384529506156563149116933599866723965986261665726377117854987961618289727778796309500398661382917, 54219654948823318949353558134729647408528033078605450261710447248526931981389076366980791949387642433071065582792937355983620874421744623335979527846852740103404585916578675431375401166059525955613465106037568623523270836438448759386651661722151254807392308299836330059199007367174905836583286889987216815050, 35869172105073034975556096235258299638707891490235012188766841767244229723310917897401808054472607608792812969601559201602628580086657191952130787739893319004369902854653575666943324355363380637079930011912608863176644470479294749440933466533383738514721569349941257647158990358542979527511485933319882970785, 33585321284062015644628872525939167507033306689554250848095948952429865522047703119829617290091551521682239829250049756977570017816430059774096107954197232368207599300130661280510652420740089226343552474590403108229902871875586731165431796252447431312546948219290047499307018054290019358535681224393460998288, 34363063581955617713283358462977664682257832977620676364107767891095308255700558544765528275299946118597889167559960878802358804759430370206126814546909201603575606082043558255431021053488010978895093093984860049133918050324268289058598677973242974041658522222592016265462123282652487010520883927854399753032, 83303045014068598146239782836034572342661644739001378581085837509255968029431407176051614456594134112623953587188672599551029837808585911586762040880543248486616814921195820637197650347212641142881084135754833912810899047660641992645842889761973065877155412625476806148364533743554579144029169415470801026317, 113151374551030379905863439802781831613481971442242467973016594520046104484764387720297172281653500237890289948985294204511730848101104617294684815301705325430373479781345088617167985586923258569092520852815109295762192933273911091518345150383332084519963792546884769750659224626477438372213616603209047291257, 130829797409030268973352996767957779365311690002579378946982172341323743450377476516069574855855224485237210467599418067612712824380628946412878127911436900313997947604882192929110839317179000399541063224855604445875473626055054487308281408204582792705082064340692302772564869303002107776645416860156072622955]
e = 65537
n = 150696614629132057109111480582577778723820969345630437367143066912323132221202404868706476552913390819783711643546310151820832496789087095879886490636812504690842921497146409465300931707997961967930772720006749985178086455545423786599439466838471458478125360273903249535338101526493597879081698428178510548267

B = 2**1008 #Bài này mình lấy 2^(l-16)
a_i = [0x0002 * B for _ in range(len(R))]
t_i = R.copy()

W = diagonal_matrix(len(t_i) * [1] + [QQ(B) / QQ(n)] + [B], sparse = False)
L = block_matrix(QQ, [
    [identity_matrix(len(R)) * n, 0, 0],
    [matrix(t_i),1, 0],
    [matrix(a_i), 0, 1],
])
L *= W
L = L.LLL()
L /= W

for row in L.LLL():
    if  b'HTB{' in l2b(abs(int(row[-2]))):
        print(l2b(abs(int(row[-2]))))
#b"\x02\xb3-\xa2]v\xfcl\xb0G\xe2u\xd4\x93Z\xb50\xc1\xb6y\xedl\x8b-\xcc,\xec\xaf\x9f\xd3\xca\xc8\xde\x195oo[\xb4\x9fB\x19\xbd\r\xb4'\xb3\x00HTB{Bleichenbacher_Lattice_Attack_and_The_Hidden_Number_Problem___Cool_Right?!}"