## ASCIS 2023 WarmUp - Welcome RSA, Hidden Message
Mình sẽ viết WU này để tổng hợp kiến thức cũng như để chia sẻ thêm về cách giải của một số bài mình giải được ở vòng khởi động giải CTF mới diễn ra ASCIS 2023 WarmUp.

# Welcome RSA
Đây là đề bài:

#!/usr/bin/python3

from Crypto.Util.number import getPrime
from Crypto.Util.number import bytes_to_long

N = 1024
p = getPrime(N)
q = getPrime(N)

m = 0
with open('flag.txt', 'rb') as f:
    m = bytes_to_long(f.read())
e = 65537

phi = (p-1) * (q-1)
c_p = pow(m, e, p)
c_q = pow(m, e, q)

print(f"c_p = {c_p}")
print(f"c_q = {c_q}")
print(f"N = {p * q}")
print(f"phi = {phi}")

Nhìn sơ qua đề thì ta thấy rằng đề đã cho ta biết `phi` và `N` mà giá trị `phi` đóng vai trò cực kỳ quan trọng trong bài toán này vì nếu có `phi` và `N` thì việc tìm hai biến số nguyên tố `p` và `q` là một việc dễ dàng.

Ta có:
\begin{equation}
\left\{
\begin{array}{l}
p*q = N \\
(p-1)*(q-1) = phi
\end{array}
\right.
\end{equation}

\begin{equation}
\Leftrightarrow
\left\{
\begin{array}{l}
p= {N \over q} \\
(p-1)*(q-1) = phi
\end{array}
\right.
\end{equation}

\begin{equation}
\Leftrightarrow
\left\{
\begin{array}{l}
p= {N \over q} \\
({N \over q}-1)*(q-1) = phi
\end{array}
\right.
\end{equation}

\begin{equation}
\Leftrightarrow N-{N\over q} -q+1-phi=0
\end{equation}

\begin{equation}
\Leftrightarrow q^2-N*q-q+phi*q+N=0
\end{equation}

\begin{equation}
\Leftrightarrow q^2-(N+1-phi)*q+N=0
\end{equation}

Từ đây ta có thể giải ra `q` và cho ra 2 nghiệm dương đều thoả mãn phương trình trên với 2 nghiệm đó lần lượt là `p` và `q`, tuy ta không biết được nghiệm nào là `p` và nghiệm nào là `q` nhưng ta có thể thử cả hai để tìm ra flag.

Đây là code giải bài này:

from Crypto.Util.number import long_to_bytes,inverse
from gmpy2 import gcd
c_p = 70770563170413485640234825332830715579644049285355981293505262738914209029517352373077018947770320280278746620671203215024503799950910898732397153179084074098233352980719945417330407037538618730258842372338429001603903091610752262516741188853590089951756761811040256580538917054394236602707893767220570272331
c_q = 13851492318566804426180559171717895114036816324429566434285593612538644178623395941843619351600718862105589158342528216101368809170495598383990497387251379469346455961514711553702647806756877972791529391358173595919397389755049646932111264878041754835352170573649918876911510785389021472942167961552938040890
N = 19694268725205416932271364425385420707850329840157673295273677195054630515982058976079498206887037469237238398405928480684350200120501078231388088496277582527947938156849419785864562896382735306087325118435609429713312673380764412264707904939485238218886677027240033716280913510048689954579551621705920549746909058000987771268371934823850223213735201866888065931847369642802547725217919776237783287489769890109322726430755322073866327698639461994686267421903262258256777595366148454467865658097293146857749360141451451546041703858527691932299750797762597565953059522307802045384870886086792768277420112890024197381341
phi = 19694268725205416932271364425385420707850329840157673295273677195054630515982058976079498206887037469237238398405928480684350200120501078231388088496277582527947938156849419785864562896382735306087325118435609429713312673380764412264707904939485238218886677027240033716280913510048689954579551621705920549746628074068680399113370686212746795530576012850939713222911207509162211597032002438837189193853944160004364194868287701610512383924569996771883743351575199994707067296109349832389723176764968511964606092023026149281647383744920057620837615083525637277639792424720226658009593127619853405831534160987224728925500

q = 133879566549680173115010000656575599386347196254555820845731098396987569234168170667682173669730202089319438083372479965107156729576438511660256112210092621038817523549520785823861905813922287648879467800147350606041615014555319097811201748949898135983939033500537527258201074877029166631336090676510695537951
p = 147104365757691981886238610446852083772841819693796888090431035243348558951749166732911919966095528015639093479095140498246787044493026711142267958117969642510892775707277836254280575518402347244263800318277951658352705099052315213650933965287062152329328064087037860117076683589910195814549861226288772917891
e = 65537
print(p)
print(q)
phi_q = q-1
phi_p = p-1
print(gcd(e,phi_q))
print(gcd(e,phi_p))
d_q = inverse(e,phi_q)
d_p = inverse(e,phi_p)
assert pow(c_q,d_q,q) == pow(c_p,d_p,p)
print(long_to_bytes(pow(c_q,d_q,q)))
# 147104365757691981886238610446852083772841819693796888090431035243348558951749166732911919966095528015639093479095140498246787044493026711142267958117969642510892775707277836254280575518402347244263800318277951658352705099052315213650933965287062152329328064087037860117076683589910195814549861226288772917891
# 133879566549680173115010000656575599386347196254555820845731098396987569234168170667682173669730202089319438083372479965107156729576438511660256112210092621038817523549520785823861905813922287648879467800147350606041615014555319097811201748949898135983939033500537527258201074877029166631336090676510695537951
# 1
# 1
# b'ASCIS{W3lc0me_t0_th3_P4rty_8597b0394054835f80ebd573a238ddbe1d86942657a59a7b6f84660d629472b5}\n'

Ta có `flag` được encrypt bằng thuật toán RSA với 2 modulo khác nhau là `p` và `q`

c_p = pow(m, e, p)
c_q = pow(m, e, q)

đồng thời `p` và `q` là 2 số nguyên tố (prime) và đóng vai trò là `N`. Và vì nếu `N` là prime thì `phi = N-1` và tiếp đến ta xét $GCD$ của `e` và `phi`, nếu $GCD(e,phi)=1$ thì sẽ có $d=inverse(e,phi)$, cùng với đó ta cũng biết rằng $e*d≡1 (mod \ phi)$, vậy ta sẽ có:
\begin{equation}
m^e (mod \ p) = c_p
\end{equation}

\begin{equation}
\Leftrightarrow c_p^d (mod \ p) =m^{ed} (mod \ p) = m^1 (mod \ p) = m
\end{equation}

# Hidden message
Đề bài cho ta một tấm ảnh [lsb.png](https://hackmd.io/_uploads/HJvGZcJbp.png)

Nếu ta để ý góc trên cùng bên trái sẽ thấy có một số pixel có màu xanh dương (ban đầu mình cũng không thấy đâu :smile:) vậy thì ta dùng tools [stegsolve.jar](https://github.com/Giotino/stegsolve) (một tool phổ biến để phân tích các plane màu của một tấm ảnh)

Qua tới Red plane 7 thì mình thấy có một vài chấm đen ở trên cùng vì thế mình tiến hành Analyse->Data Extract->Chọn Red 7->Preview và kéo lên trên cùng
Phew~ ta đã có flag :smile: `ASCIS{w3ll_d0n3_st3g0_1s_fun}`, khá đơn giản nếu bạn đã làm quen từ trước với các tool forensic cơ bản.

Hehe đến đây là hết bài WU của mình, các bài trên đều khá là đơn giản nếu như bạn nắm được căn bản của thuật toán mã hoá RSA và sử dụng được các tool cơ bản bên forensic. Vì đây là vòng khởi động nên mình thấy vẫn chưa quá khó.

Và cuối cùng vẫn cảm ơn bạn vì đã đọc WU của mình :kissing_smiling_eyes:, mong rằng mình đã truyền đạt tốt qua bài WU này và chúc bạn một ngày tốt lành!

#KienSD