<h1 style="text-align:center;">Low Entropy</h1>


:::spoiler **low_entropy.py**

from Crypto.Util.number import * 
import random 
import os 

FLAG = os.getenv('FLAG', 'HCMUS-CTF{real_flag}').encode()
c = bytes_to_long(FLAG)

bit_size = 2048  
low_entropy = 880
lower_entropy = 512 
p = random.randint(1, 2 ** low_entropy) | 1 
e = 65537 
ns = []


def generate_key():
    pi = 2 ** low_entropy * random.randint(1, 2 ** (bit_size - low_entropy - lower_entropy)) + p 
    while not isPrime(pi):
        pi = 2 ** low_entropy * random.randint(1, 2 ** (bit_size - low_entropy - lower_entropy)) + p 
    qi = getPrime(lower_entropy)
    n = pi * qi
    return n

for _ in range(2): 
    n = generate_key()
    c = pow(c, e, n)
    ns.append(n)

print(f'{ns = }')
print(f'{c = }')

"""
ns = [18349343782375022954049756963828998671589286352990777804455797159005491942354865746019079122256264079046445830499034591933588970104794517643945205842259802188270649916400754976240462414341916304701252487713672075750034805709175580814467227694895179604061815838199426558536015862528348634067337217067827092987035412670435263900286694061416746391283390216294002168497773601824935005695344837600589040258790093470416414169427177336573030541645116758950475481398547599572480264716563089400700561537592414534335881797148406772972369109008774921401863438549477012149118081389629246659135565983103607574743254633155738539403, 2917748607840327501619087191722427080119751486083239768779742070231145699732680440820015392423380940073338576236701868210196226228649653763215407132246374506766690408692238792254728605721277466492498290115419079744936631517871646227510991497917266668224152627283948520140282283531146008869556732414432132579389292193171031478945870968638818715562754735843487275380937480499487402531601843308147521778202843443328308319419844234017608008549235826234836275393583345192922278991956527706916336760712235283399992936114122228699559074577586313287470980708306665209878263196759773824660792116426141549202559489775548298693]
c = 2296306025869549176576925273198461673059177642465145766188113010949469752952208917925262978809882003618471386025111852452429183839187738872562588771348322633103829297972545263418090684622134421352915160508795180689626209280379005732041524247358659732155568988572646810455921816597736960929436581062318909030283823078773339918866991086501841172364298222362372578263826232501517002536189638820771341834636493282811989234174994172015503017381899675863778963311313817997397998587533889632518845294389925945381736535279025070686930516954382888001413967084586898792085145274220252325167619768544541871974787674743342496039
"""

:::

:::spoiler **hint**
:::

++**Mô tả:**++ Challenge này mã hóa **Flag** bằng hai lần RSA với $e = 65537$ và hai modulus là $n_1 = p_1 \cdot q_1$ và $n_2=p_2 \cdot q_2$.
Nhưng điểm yếu nằm ở việc hai số nguyên tố $p_1$ và $p_2$ có chung $880$ bit thấp nhất.

---
Phân tích hàm `generate_key()`:

def generate_key():
    pi = 2 ** low_entropy * random.randint(1, 2 ** (bit_size - low_entropy - lower_entropy)) + p 
    while not isPrime(pi):
        pi = 2 ** low_entropy * random.randint(1, 2 ** (bit_size - low_entropy - lower_entropy)) + p 
    qi = getPrime(lower_entropy)
    n = pi * qi
    return n

Challenge tạo hai số nguyên tố $(p_1, p_2)$ theo công thức:
$$p_1 = 2^{880}*X_1 + p$$

$$p_2 = 2^{880}*X_2 + p$$

Với $(X_1, X_2)$ là hai số Random khoảng $656$ bit và $p$ là một số Random khoảng $880$ bit.

> Vậy ta thấy được rằng $p_1$ và $p_2$ có chung phần $p$ hay $p_1$ và $p_2$ có chung $880$ bit thấp nhất.

Sau đó nó tạo hai số nguyên tố $(q_1, q_2)$ khoảng $512$ bit để tạo hai modulus $(n_1, n_2)$ theo công thức:
$$n_1 = p_1 \cdot q_1$$

$$n_2 = p_2 \cdot q_2$$

---
Vì có chung $880$ bit cuối nên ta có mối quan hệ giữa $(p_1, p_2)$ như sau:
$$
\left\{\begin{matrix}
p_1 \equiv p \pmod {2^{880}} \\
p_2 \equiv p \pmod {2^{880}}
\end{matrix}\right.
$$

Từ đây ta có:
$$
\left\{\begin{matrix}
n_1 = p_1\cdot q_1 \equiv p\cdot q_1 \pmod {2^{880}} \hspace{5mm} (1)\\
n_2 = p_2\cdot q_2 \equiv p\cdot q_2 \pmod {2^{880}} \hspace{5mm} (2)
\end{matrix}\right.
$$

Lấy $(2) \cdot (1)^{-1}$ ta được:
$$n_2\cdot n_1^{-1} = q_2 \cdot q_1^{-1} \pmod {2^{880}}$$

Đặt $\Delta = n_2\cdot n_1^{-1} \mod {2^{880}}$, ta có:

$$
\begin{align}
&\Delta\cdot q_1 \equiv q_2 \pmod {2^{880}} \hspace{5mm} \\
\Rightarrow \hspace{3mm} &\Delta\cdot q_1 + k\cdot 2^{880} = q_2 \hspace{5mm} (*)
\end{align}
$$

---

Vì $(*)$ là phương trình **hai ẩn** $(q_1, k)$ nên trực giác của số đông sẽ là **LLL** để tìm được vector $(q_1, q_2)$, nhưng mà không được đâu, vì $(q_1, q_2)$ có kích thước rất lớn.

Thay vào đó ta sẽ LLL $(*)$ để được một cơ sở mới **đẹp** hơn sao cho $(q_1, q_2)$ vẫn nằm trong cơ sở đó.

Thiết lập cơ sở:
$$
\mathbf{A} =
\begin{bmatrix}
1 & \Delta \\
0 & 2^{880} \\
\end{bmatrix}
$$

Theo như **hint** thì khi LLL ta được một cơ sở mới gồm hai vector $v_1 = (v_{11}, v_{12})$ và $v_2 = (v_{21}, v_{22})$ là:

m = 2**880
M = Zmod(m)
e = 0x10001
n1, n2 = ns

tmp = M(n2)/M(n1)
A = Matrix(ZZ, [[1, tmp], 
                [0, m]]).LLL()

for i in A:
    print(i)

v11, v12 = (-762161043109875112939603459344262000873231049347818760555008367277685515177767850840036345938400002933776179177694390016941418662130, -2141511445372937729448649287720371124234435554272326735268571549364838476875494427950559208420743976495109782911551545208216269701102)

v21, v22 =(3435401163430780886031192936540252823904511081333099896667311313071621862540666436511285888105013052279829653482745070559195709910893, -923930590395465993892619022411634677876605751103038189159850995230415494559240679921051893537938873935925629713008472075280210258493)

Đặt cơ sở mới là:
$$
\mathbf{V} =
\begin{bmatrix}
v_{11} & v_{12} \\
v_{21} & v_{22} \\
\end{bmatrix}
$$

Tồn tại một tổ hợp tuyến tính $r = (r_1, r_2)$ sao cho:
$$
r \times V = (q_1, q_2)
$$

hay:
$$
\left\{\begin{matrix}
r_1\cdot v_{11} + r_2\cdot v_{21} = q_1 \hspace{5mm} (3) \\
r_1\cdot v_{12} + r_2\cdot v_{22} = q_2 \hspace{5mm} (4)
\end{matrix}\right.
$$

Khi này $\mathbf{V}$ là một cơ sở **đẹp** nên vector $r=(r_1, r_2)$ sẽ có kích thước ngắn hơn, ta có thể kiểm tra bằng cách test local như sau:

# test
m = 2**880
M = Zmod(m)
q1 = 10343823766279961233976486085288163702786944750869383603767258543075027258110568327935349117926592195881776455243127251032932351281635322195423331521023773
q2 = 10369589752858783995187759662241707540872352897269605476547328428892350818179881094935907754560230506660910751312109222171933322414829869643025194141464357
ns = n1, n2 = [7492768629833707828041916862134380430807007517825813091694892937926658821021616601093591647845010612124105168241717490275345225079437173615466312285723297651655158247837125709210455158889623002020666262338029929189049317262968444583491798016152806091930757464856538331915267772620989862495358762169271359095551319166498813541565408154298406740457827946740025056819389128366630419766522349852210351397184091105273168521296947839590680032293029198227580492010158462886291995287773214081669112410887871289383713222692840413241000843838215092672511746938314206698432805727491495390558753645897103661212951880771773934219, 2146478385779481448698124778938880774745398812632087295348406378351185502033319063710443102060839633759911987121103542510056622416425059246813959781199903367555493119701039955293433431083971211262585201993565579848765859670187310473846827596619143395608811664139408586680670617849922646627703855361097042880779413353918880247469918440821897755680856940561422145078734141515018795431686281257579744772604205550195444765373235437893799634273805439054940200756236981772518333145397125119355079254978853372066950133961852507513172131168490812766977582052399751470561134897452969261769693160185129387298284974414172340419]

tmp = M(n2)/M(n1)
A = Matrix(ZZ, [[1, tmp], 
                [0, m]]).LLL()
                
v11, v12 = A[0]
v21, v22 = A[1]

A = Matrix(ZZ, [[v11, v12], 
                [v21, v22]])

r1, r2 = A.solve_left(Matrix(ZZ, [q1, q2])).list()

print(f"{r1 = }")
print(f"{r2 = }")
print(is_prime(ZZ(r1*v11 + r2*v21)))
print(is_prime(ZZ(r1*v12 + r2*v22)))

# r1 = 3548240620880633475662
# r2 = 3147220479854714034965
# True
# True

> Có thể thấy rằng $(r_1, r_2)$ có kích thước khá nhỏ, chỉ khoảng $72-73$ bit mà thôi.

Quay trở lại với Challenge, dựa theo **hint**, ta sẽ khai thác hai phương trình $(3), (4)$ để kết hợp chúng và sau đó là **Coppersmith** hai ẩn.

Nhắc đến kết hợp thì ta nghĩ ngay đến **CRT** đúng không? Tiến hành mod phương trình $(3)$ cho $n_1$ và phương trình $(4)$ cho $n_2$, mục tiêu của ta là tìm một giá trị $f$ sao cho:

$$
\left\{\begin{matrix}
f \equiv r_1\cdot v_{11} + r_2\cdot v_{21} \equiv q_1 \pmod {n_1} \\
f \equiv r_1\cdot v_{12} + r_2\cdot v_{22} \equiv q_2 \pmod {n_2}
\end{matrix}\right.
$$

Tiến hành đặt các giá trị như sau (công thức CRT cơ bản thôi không có gì đâu):
$$
\begin{align}
a_1 &= r_1\cdot v_{11} + r_2\cdot v_{21} \\
a_2 &= r_1\cdot v_{12} + r_2\cdot v_{22} \\
N_1 &= n_2 \\
M_1 &\equiv N_1^{-1} \pmod {n_1} \\
N_2 &= n_1 \\
M_2 &\equiv N_2^{-1} \pmod {n_2} \\
\end{align}
$$

Khi này công thức của $f$ sẽ là:
$$
\begin{align}
f &= (N_1\cdot M_1\cdot a_1 + N_2\cdot M_2\cdot a_2) \equiv q_1\cdot q_2\cdot(p_2\cdot M_1 + p_1\cdot M_2) \pmod {n_1\cdot n_2} \\
\Rightarrow f &= (N_1\cdot M_1\cdot a_1 + N_2\cdot M_2\cdot a_2) \equiv 0 \pmod {q_1\cdot q_2}
\end{align}
$$

> Vì vậy khi Coppersmith, ta sẽ chọn $\beta = (q_1\cdot q_2)/(n_1\cdot n_2) \approx (512+512)/(2048+2048) \approx 0.25$.
Nếu chưa biết cách chọn $\beta$ thì có thể đọc thêm ở [**đây**](https://hackmd.io/@at20n0118/Hy5LBsS51l#Introduction-to-Coppersmiths-method).

Ta code như sau:

r1, r2 = PolynomialRing(Zmod(n1*n2), ["r1", "r2"]).gens()
a1 = v11*r1 + v21*r2
a2 = v12*r1 + v22*r2
N1 = n2
M1 = pow(N1, -1,  n1)
N2 = n1
M2 = pow(N2, -1, n2)

f = (N1*M1*a1 + N2*M2*a2)
print(f)

f = 21192032810595048171960742323723997942950424826468782858114631252145225783869532264399295485175758183710931838004487655549977520164251831227738402234368139351557143292698725499812655366698862681006841026337691054791094517254286009384681294573421345326543514029780287433835283522248371103284845802604174206393086834119817528143839882773730683251274463662286854811318654153877465809469423845540402514143380150977669662699678732369485920382950289317017375397830789719208768553277616213424777629336167465189918682477766736678339803567290764882777912034742467747872924065660561011321781860860539091916640876791925874627657767565101202359073025335490333031243832381533511676463643863925080787183721870907360573779462694326448512586043277865818297939260851453686927088354378778013654753668956321649436653991636473550694739793238951846732707267452520209766185877498586376648291241964228159139631034605278146045328786690422150780803194241948498615519350713909563290028990954185707043870821912138068174352541510548609726981898586077865272939827610808345613536128441345879577952507400367491114823681529112012923112851279445157446046851135365426555014698474774052146660853914209828048459953542996129777011396074262025747617512796789741126008349*r1 + 12883316191413328811451022299587470317126861249176724285691071289446868304909116157657583176101074794150080290567744637708691627231680704749129221879339857088301980850110169033243964271884884005961484168316859850284029510553278964724782420141149262699491730699771004245522388160720138038910674058003675522699270027454703573182137260397585645660704843385997222690630775605716010882967828106076677896728352553780981086263295670852136186464719602423592288783474799485054966944119162083966462635848012526441002227490818763192066277427975036324986675257069665166817070308731908859135169190109333033631933121623540553371100207944455405792622845860271076379728280431293604007739874917226305237884308232815389558401243765959993116181863895659699198251209713686154578079784872602266322631678553102318169960579714092461907245426329275655404980890799198466171891909778846696206639692405705429533030533812773307610905033301006343574994008478753033631382185614444432052950189316501495569829657882490217162063063891675406219464717468367053288693328710516805969473254361727886814919834824602647938172763512522414183053192559275384706509237001705764700001745062469335645251453228410452132404913364852443187914441869995204336814678432511468398885345*r2

---

Với **bound** là $(2^{73}, 2^{73})$ và $\beta = 0.25$ thì sau khi thử các tool coppersmith thì chỉ có tool của [**Kiona**](https://github.com/kionactf/coppersmith) là giải được:

Ta được $(r_1, r_2)$ là $(5238320523828960725382, -2672350630505452150681)$.
Thay vào phương trình $(3), (4)$ là có dược $(q_1, q_2)$ thôi:

R1, R2 = [5238320523828960725382, -2672350630505452150681]

q1 = abs(R1*v11 + R2*v21)
q2 = abs(R1*v12 + R2*v22)

assert isPrime(q1) and isPrime(q2)

p1 = int(n1//q1)
p2 = int(n2//q2)

assert p1*q1==n1 and p2*q2 == n2
print(f"{q1 = }")
print(f"{q2 = }")

q1 = 13173040299718759287918245918249314494023572090635346549342612621732756866171255714509550635652207067617350398825207488674718082400795278885788890492451793
q2 = 8748856860525083776224215800395080775119495971157795677865114445014637734061547314682687190903607996507242748279614662180024064336631262462642496448787231

Có $(p,q)$ là tính được $\phi(n)$ rồi, từ đó có thể tính được nghịch đảo của $e$, nhưng một điểm cần chú ý là vì $n_1 > n_2$ nên ta không thể khôi phục **Flag** theo công thức:
$$\text{Flag} = (c^{d_2} \mod n_2)^{d_1} \mod n_1$$

Vì khi ta lấy $c^{d_2} \mod n_2$ ta chỉ được $c_1 \mod n_2$ chứ không được $c_1$ vì $c_1 > n_2$, vì thế ta cần biến đổi $c_1$ thành:
$$c_1 = c^{d_2}\mod n_2 + k\cdot n_2$$

Với giá trị $k$ trong đoạn $[0, \frac{n_1}{n_2}]$.

**Script:**

from sage.all import *
from Crypto.Util.number import *
import sys 
sys.path.append('/mnt/c/vc/test/coppersmith')
from coppersmith_linear import *

"""
hint của author
sau khi LLL với một phương trình gì đó có modulus là 2**880 thì 
được hai vector v1, v2 và tồn tại r1, r2 sao cho:

(q1, q2) = r1*v1 + r2*v2
từ đây ta có hai phương trình:
q1 = r1*v11 + r2*v21 (mod N1)
q2 = r1*v12 + r2*v22 (mod N2)
sau đó thì tự xử, không hint gì thêm


solu của author
1. xây mat = [ [N_1^-1 * N_2, 1], [2^l, 0] ] để LLL thì thu được 2 vector như trong hint ở announcement
2. từ 2 cái phương trình q_1, q_2 mình dùng CRT để xây phương trình x_1 * a_1 + x_2 * a_2 = q_1 * q_2 (mod N_1 * N_2) với a_1 = v_11 mod (N_1) và a_2 = v_12 mod(N_2), tương tự với a_2
3. Coppersmith 2 biến để tìm x_1 và x_2
"""

# LLL để tìm cơ sở đẹp
m = 2**880
M = Zmod(m)
e = 0x10001
n1, n2 = [18349343782375022954049756963828998671589286352990777804455797159005491942354865746019079122256264079046445830499034591933588970104794517643945205842259802188270649916400754976240462414341916304701252487713672075750034805709175580814467227694895179604061815838199426558536015862528348634067337217067827092987035412670435263900286694061416746391283390216294002168497773601824935005695344837600589040258790093470416414169427177336573030541645116758950475481398547599572480264716563089400700561537592414534335881797148406772972369109008774921401863438549477012149118081389629246659135565983103607574743254633155738539403, 2917748607840327501619087191722427080119751486083239768779742070231145699732680440820015392423380940073338576236701868210196226228649653763215407132246374506766690408692238792254728605721277466492498290115419079744936631517871646227510991497917266668224152627283948520140282283531146008869556732414432132579389292193171031478945870968638818715562754735843487275380937480499487402531601843308147521778202843443328308319419844234017608008549235826234836275393583345192922278991956527706916336760712235283399992936114122228699559074577586313287470980708306665209878263196759773824660792116426141549202559489775548298693]
c = 2296306025869549176576925273198461673059177642465145766188113010949469752952208917925262978809882003618471386025111852452429183839187738872562588771348322633103829297972545263418090684622134421352915160508795180689626209280379005732041524247358659732155568988572646810455921816597736960929436581062318909030283823078773339918866991086501841172364298222362372578263826232501517002536189638820771341834636493282811989234174994172015503017381899675863778963311313817997397998587533889632518845294389925945381736535279025070686930516954382888001413967084586898792085145274220252325167619768544541871974787674743342496039

tmp = M(n2)/M(n1)
A = Matrix(ZZ, [[1, tmp], 
                [0, m]]).LLL()

v11, v12 = A[0]
v21, v22 = A[1]

# CRT
r1, r2 = PolynomialRing(Zmod(n1*n2), ["r1", "r2"]).gens()
a1 = v11*r1 + v21*r2
a2 = v12*r1 + v22*r2
N1 = n2
M1 = pow(N1, -1,  n1)
N2 = n1
M2 = pow(N2, -1, n2)

f = (N1*M1*a1 + N2*M2*a2)

# Tìm r1, r2
R1, R2 = coppersmith_linear(basepoly=f, bounds=(2**73, 2**73), beta=0.25)[1]
R1 = int(R1)
R2 = int(R2)
# R1, R2 = [5238320523828960725382, -2672350630505452150681]

q1 = abs(R1*v11 + R2*v21)
q2 = abs(R1*v12 + R2*v22)

assert isPrime(q1) and isPrime(q2)

p1 = int(n1//q1)
p2 = int(n2//q2)

assert p1*q1==n1 and p2*q2 == n2
print(f"{q1 = }")
print(f"{q2 = }")

# giải mã ciphertext
phi1 = (p1-1)*(q1-1)
phi2 = (p2-1)*(q2-1)
d1 = pow(e, -1, phi1)
d2 = pow(e, -1, phi2)

for k in range(0, n1//n2+1):
    flag = long_to_bytes(pow(pow(c, d2, n2) + k*n2, d1, n1))
    if b'HCMUS-CTF{' in flag:
        print(flag)
# b"HCMUS-CTF{tOO_LLL0w_2_13r0t3ct_7he_f14g}"


++Flag++: **HCMUS-CTF{tOO_LLL0w_2_13r0t3ct_7he_f14g}**

# Ghi Chú
Trong quá trình coppersmith nếu gặp lỗi như sau:

INFO:logger:start solve_root_hensel
WARNING:logger:too much root candidates found
INFO:logger:start solve_root_hensel
WARNING:logger:too much root candidates found
INFO:logger:start solve_root_hensel
WARNING:logger:too much root candidates found
INFO:logger:start solve_root_triangulate
Traceback (most recent call last):
  File "/mnt/c/vc/test/coppersmith/test.sage.py", line 29, in <module>
    roots = coppersmith_linear(basepoly=f, bounds=(_sage_const_2 **_sage_const_73 , _sage_const_2 **_sage_const_73 ), beta=_sage_const_0p25 )
            ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
  File "/mnt/c/vc/test/coppersmith/coppersmith_linear.py", line 100, in coppersmith_linear
    sol = rootfind_ZZ(curfoundpols, bounds, **context.rootfindZZopt)
          ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
  File "/mnt/c/vc/test/coppersmith/rootfind_ZZ.py", line 428, in rootfind_ZZ
    result = rootfindZZ_algorithm_dict[algorithm](pollst, bounds, **kwds)
             ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
  File "/mnt/c/vc/test/coppersmith/rootfind_ZZ.py", line 240, in solve_root_triangulate
    ZZsol = solve_ZZ_symbolic_linear_near_bounds_internal(sol_coefs, bounds, **kwds)
            ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
  File "/mnt/c/vc/test/coppersmith/rootfind_ZZ.py", line 167, in solve_ZZ_symbolic_linear_near_bounds_internal
    lll, trans = do_lattice_reduction(mattrans, lllopt_symbolic_linear)
                 ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
TypeError: do_lattice_reduction() takes 1 positional argument but 2 were given

Thì có thể sửa bằng cách vào file `rootfind_ZZ.py`, tìm đến hàm `solve_ZZ_symbolic_linear_near_bounds_internal` và sửa đoạn:
`do_lattice_reduction(mattrans, lllopt_symbolic_linear)` thành `do_lattice_reduction(mattrans, **lllopt_symbolic_linear)`.

---