# Writeup challenge CTF Lab 02
## Phi phai
### Code

from Crypto.Util.number import long_to_bytes, isPrime
import gmpy2

e = 65537
d = 4504287984018183537713208161402766323065548618393723872837173606374276398491834181934336417310620387990925189536232872881499528612504958202701279049935780903977608853793957819684386053139789777966936156264230499424635837453895019683637553474699470241265384239892304309743522811693909773853204104744746499940669186347989219693819334120860342801601135658920550816397929837218587842050717426094705159184294217221659550021174121437354727563286401517383250923022292331155286641664114777714280910808217996581853423619501922201519238297960634332127751600929842715997073072544823353485994644594610107896462399877655553045761
hint = 231925193905919836406214406898885408169720762556845482044575179755202576770665967750292209535638389585617923204488598005919071680696574306168950409350364369661185363429309191455686049593246205245617043129829360203967945465085196018291809693305049028207915207766096530755343783712735226590596701430255772594556
c = 6217038084836470023310381029897048208087224587728895918727075557465841714766785434203795384404277685883194699549944699326316064489862857903738642081680285228167738881574533344177255570731527611503589831001734795490242158816621194509455025049486128406587545324515046616431849802141624745659660349892441242897503306780984369111460208907969417056103375189617092555003582813739896435112054576310776891033107119212517760203084951964632014280482552024983115272574743031704179104705817029355755554440364213319205880788661502753344785708858216051846295494426952842154398100557142240912181225765846610290283305931102820798460

a = e * d - 1

for k in range(1, 1000000):
    if a % k == 0:
        phi = a // k
        n = phi + hint - 1
        delta = hint * hint - 4 * n
        if delta > 0:
            sqrt_delta = gmpy2.isqrt(delta)
            if sqrt_delta * sqrt_delta == delta:
                p = (hint + sqrt_delta) // 2
                q = (hint - sqrt_delta) // 2
                if isPrime(p) and isPrime(q):
                    m = pow(c, d, n)
                    print(long_to_bytes(m))
                    break

### Giải thích
- Ta có:
$$
e \times d \equiv 1\pmod{\varphi(n)}
=> ed-1 = k\varphi(n)
$$
- Vì `phi(n)` thường lớn nên khoảng duyệt k sẽ nhỏ, ta duyệt từ 1 đến 1000000 để tìm `k` chia hết cho a với `a = e * d - 1`
- Sau khi tìm được k thì lấy `a//k` sẽ thu được `phi(n)`.
- Tuy nhiên `phi(n)` này chưa chắc đã là đáp án cuối cùng, ta phải kiểm tra có tồn tại 2 số nguyên tố `p`,`q` sao cho `phi(n) = (p-1)(q-1)`.
- Mà:
$$
\varphi(n)=(p-1)*(q-1) = pq - (p+q) + 1
$$
- Ta thế `p*q = n` và `p + q = hint`:
$$
\varphi(n) = n - hint + 1
$$
- Vậy nên ta thu được `n = phi(n) + hint - 1`.
> Lưu ý ở giai đoạn sau mới là phần kiểm tra n và phi(n) có hợp lệ hay không vì có thể sinh ra nhiều k.
- Ta có `n = p*q` và `hint = p+q`, vậy nên `p`, `q` sẽ là nghiệm của phương trình
$$
x^{2} - hint*x + n = 0
$$
Có
$$
denta = hint^{2}-4n
$$
- Nếu `delta`<0 thì phương trình vô nghiệm, ta bỏ qua.
- Nếu `delta` >= 0 thì ta tiếp tục kiểm tra delta có phải số chính phương hay không, vì `p` và `q` phải là các số nguyên nên $\sqrt{delta}$ phải là số nguyên.
- Sau đó ta sẽ tìm được `p` và `q` theo công thức nghiệm và tiếp tục kiểm tra xem `p` và `q` có phải số nguyên tố hay không.
- Nếu thu được `p` và `q` là 2 số nguyên tố thì `k` đó là chính xác và ta đã thu được `n` và `phi(n)` hợp lệ.
- Ta thế `n` vào công thức sau để tìm bản rõ:
$$
m=c^{d}mod(n)
$$
- Sau đó chuyển `m` về bytes sẽ thu được cờ.
> Flag thu được: W1{phi_phai_la_game_rac_so_1_vn}

---
## phiphai2
### Code

from Crypto.Util.number import long_to_bytes, isPrime
import gmpy2

n = 20842938351896783351765564497257406689875073939168847270109018452331595953195137925905407574790509131975169442262183423216630782056006817670026102637100795102868553295795605909294220001159170312214938967565708237131119660898946450453038715919305770854433454485282482531591669338374784896696254086081923985254456532726474557269047987653955703675146699130077388795028830171715932232259532178061195603162554212575207799198670246556909810593997402979919324116015029695269687378794139114073155816838415492318483626370434226417328166879349978988600491401399315534138391936796615782306743416152563145103425347897571269559877
leak = 1246889223294307854370712989427585884021285335323141671816486223380713311286629425480810174036551750931478373626071781038942054037291709281118654737087599035092443005799430352628570933778452108536502272580400092528062848455445985692614774855796791907610933670663580901476953467808284328166657791568856558571935788405193538986947393116928493787198798661826785549975721130971676199856446097879499458065034678153636052702160287204920680541565366139294026010089009061274372587986143754097126566624340639998228509117420424679732985956823117206903025894886029533740978018513157416105341714161360196840042575896512731742096
ct = 3088291167300681828911890341254838261507896143994085977627215978594078495952883007565773809797879150841185401282724413230256089706081482055304607098189837372445021022139016449305819308800001848241222118389290692225549475347019810385147707744883436586629808823247373108273012523932858309484832402796522454251129915341722714855738383668651266661352021406899104266596812402238487015961091455318371807234925900608259741913811110018686747303985152505270333578971573169716269092799613880511496142576903738948348527279101539196915559331086705114365249818982213416798535758240324625059044600889754519687795415852504666992830
e = 65537

for k in range(1, 1000000):
    s = k*n +leak
    t = gmpy2.isqrt(s+2*n)
    if(t * t == s + 2*n):
        delta = t*t - 4*n
        sqrt_delta = gmpy2.isqrt(delta)
        if(sqrt_delta * sqrt_delta == delta):
            p = (t + sqrt_delta) // 2
            q = (t - sqrt_delta) // 2
            if isPrime(p) and isPrime(q):
                phi = (p-1)*(q-1)
                d = pow(e, -1, phi)
                m = pow(ct, d, n)
                print(long_to_bytes(m))
                break

### Giải thích
- Ta có:
$$
leak = (p^{2} + q^{2})mod(n) => p^{2} + q^{2} = kn + leak
$$
- Vì `n` và `leak` đề cho đã rất lớn, vậy nên ta dự đoán `k` sẽ nhỏ. Vậy nên ta dò k trong khoảng 1 đến 1000000.
- Với mỗi k thì ta thu được $p^{2} + q^{2}$
- Ta đặt:
$$
s = p^2 + q^2
$$
- Và ta có:
$$
n = p \times q
$$
- Mà
$$
(p + q)^2 = p^2 + 2pq + q^2
$$

$$
\Rightarrow (p + q)^2 = s + n
$$

$$
\Rightarrow p + q = \sqrt{s + 2n}
$$
- Vì p và q là các số nguyên, vậy nên ta cần kiểm tra $\sqrt{s+2n}$ là số nguyên và đặt là t.
- Vậy nên ta có hệ:

$$
\begin{cases}
p + q = t \\
p \times q = n
\end{cases}
$$

$$
\Rightarrow x^2 - (p+q)x + pq = 0
$$

$$
\Rightarrow x^2 - tx + n = 0
$$
- Ta tìm delta: $delta = t^2 - 4n$
- Nếu `delta`<0 thì phương trình vô nghiệm, ta bỏ qua.
- Nếu `delta` >= 0 thì ta tiếp tục kiểm tra delta có phải số chính phương hay không, vì `p` và `q` phải là các số nguyên nên $\sqrt{delta}$ phải là số nguyên.
- Sau đó ta sẽ tìm được `p` và `q` theo công thức nghiệm và tiếp tục kiểm tra xem `p` và `q` có phải số nguyên tố hay không.
- Sau khi tìm được p và q thì thế vào công thức $\varphi(n) = (p-1)*(q-1)$.
- Tìm được $\varphi(n)$ thì tiếp tục thế vào tìm $d\equiv e^{-1}mod(\varphi(n))$
- Bản rõ $m=ct^dmod(n)$
- Chuyển `m` sang bytes thì thu được flag.
> Flag thu được: W1{i_hope_you_like_this_one}

---
## Sor Sor Sor
### Giải thích
- Ta nhận thấy Flag có dạng W1{A-Za-z0-9\_}. Vậy nên 3 bytes đầu sẽ là `W1{`, ta đem xor với `W1{` thì sẽ ra được 3 bytes đã xor với `W1{` để mã hóa nó.

from Crypto.Util.number import long_to_bytes, isPrime
import gmpy2
from pwn import xor

ct = "2f01090a6f042b4447101f0047460d6e0e5d001100422d156443022c4a3e074a392b033e531d1b47401b44423c411e08"
x = bytes.fromhex(ct)
ans = xor(x,b'W1{')
print(ans.decode('utf-8',errors='ignore'))

- Ta thu được:
- Ta tìm được kí tự mã hóa cho `W1{` là `x0r`
- Ta tiếp tục xor với `x0r` để tìm kí tự mã hóa cho`x0r`
- Ta tìm được kí tự mã hóa cho `x0r` là `r_v`
> W1{x0r...}
- Ta làm tiếp để tìm kí tự mã hóa cho `r_v`
- 
- Ở đoạn này thì có nhiều từ thỏa mãn, ta thử hết các từ thì chỉ có `0rc` là có thể giải ra `r_v`.
> W1{x0r...r_v...}
- Làm tương tự để tìm kí tự mã hóa cho `0rc`. Ta sẽ lại thu được nhiều cặp 3 bytes phù hợp, ta lại thử và chỉ có `t0_` là giải mã ra được `0rc`.
> W1{x0r...r_v...0rc...}
- Ta cứ liên tục tìm ngược, và khi nhiều trường hợp thỏa mãn thì ta thử xem trường hợp nào giải mã ra được 3 bytes ta cần tìm.
> Sau khi dò xong sẽ thu được flag: W1{x0r_p3rmut4t1on_a3r_v3ry_3asy_t0_brut3f0rc3s}

---
## System of Equations
### Code

from sympy import symbols, Eq, solve

x, y, z = symbols('x y z', integer=True)

eq1 = Eq(x**2 + 2*x*y - 8, 4*z**2 + 4*y - 8*z)
eq2 = Eq(x**5 + y**3, 10823714993004958804353333960725385073542379465721 - z**4)
eq3 = Eq(8864612849141*x**2 + 8864612849141*y + 17729225698282*z, 205022233466935232483321764396)

solutions = solve((eq1, eq2, eq3), (x, y, z), dict=True)

for sol in solutions:
    print(sol)

### Giải thích
- Dùng hàm của thư viện sympy để giải hệ phương trình trên tìm ra x, y, z.
- Sau đó nhập `x = 33131538` ,`y = 22029258543363862`, `z = 604095676625` vào chương trình do đề cung cấp và chọn mode `decrypt` thì sẽ in ra flag.
> Flag thu được: W1{y0u_must_b3_th3_m4st3r_0f_3quat1ons_817e31a7ccdbe8fd}

---
## Vi-et
### Code

import sympy as sp
from sympy.utilities.iterables import permutations

S1 = 779122598205443694565344617967399722167
S2 = 196487786916397904192643381759626074607590751745631772329891131596526673844879
P  = 15864378984956659850534060107405422568891641699308509134070157505662198692417476378386001170963905568690006431674713

t = sp.symbols('t')
poly = t**3 - S1*t**2 + S2*t - P

roots = list(sp.roots(poly, t).keys())
primes = [int(r) for r in roots]

flags = set()
for a, b, c in permutations(primes, 3):
    val = 123*a + 456*b + 789*c
    flags.add(f"W1{{{val}}}")

for f in sorted(flags):
    print(f)

### Giải thích
- Bài này mục tiêu là ta đi tìm a,b,c từ hệ phương trình đã biết.
Ta có:
$$
\begin{cases}
S_1 = a + b + c, \\
S_2 = ab + bc + ca, \\
P = a \times b \times c
\end{cases}
$$

- Theo định lí vi-et thì a, b, c là nghiệm của phương trình:$$t^3 -S1t^2 +S2t - P = 0$$
- Dùng thư viện sympy giải phương trình đó tìm được 3 nghiệm.
- Do không có điều kiện nào cho a, b, c nên a, b, c là hoán vị của 3 nghiệm tìm được.
- Vậy nên ta thu được 6 Flag thỏa mãn yêu cầu đề bài:

## Baby Crypto
### Code

from pwn import xor
import base64
import codecs
ct1 = bytes.fromhex("944073d9c2fdec4334375867fcd9b0c4545d20152151f6d008259a14ea339e4e0a38167ea99fd4817b4e22565772b28c5b6781c67bf16c0c4f4e0efdeaf21f0a5a7e96bff3e8a39008788fd8256c2b522c6d9b446a29e456dee859f536ba1241e5df09a25ea1abf820ab0358c554afaadf371e02b2dc6f949da28f539b4d9845d962a9899280c2301b8be293c69a241d8e39059e9fbf3fe3772b0500505867df29e4afacd12578114bbb48d17ebf9779d784d05e2479dfccc072c814a1b4d6d8286da2d553b1726a5f2590a9d80604fc7038bb6f2f3999f23d4e37626760d4035fb8cc10bdc66ea4b0a8b9a82283c1a1680f0ca91c226ee2a1af6e8dbd03b5d47c88d6e90f5505f02f7e4e5c03c3cd2ba4e66e2049ec32b4032aae025a9065dec4744aef76926beefe5f7a560a3d82e0c603348081889bcf4ec751be9b899cb23a0c117d8c15b0c9e7e217f92f024d8ed2c028e36eb5bbdc332f04981bf05226ab15dda261e569e8869b97228021c84f454d18570a6120dc40d30679154997b91d1398ef2dd166fa64ee1169c550f506013a327c34889eb0b172878f356ec042d3a22c52a3ed99536fbd6f6f1c2058f25c2314adf4190782e542644af809fd80728c7bfd9a53016565615f1cbe323ea5057679ffd8cdaaa29ea41cb3df37aecbb669e0339bbc52ab3885bbb7eef8273f5dbfeeca6d96efda197004473fe41ba54b1a898f0f30f3ec0b253b8d3555ae0a7948d74b2f083c3cf26035f9b97819124dd930c2747950bf0d6d35e7d82a7f8d3f0a7c8ef012b6926efea881d877e9acbf16a883a98d292193fcbf332cc8a5b6b732abc3cbff2e9e19531053759cae090eaf90b7b8357c9351aeacb13c4c03b1fbf8eea7a35ce1ee793f530eae06e55fe536d0ec0c5a4e70a4f6735a240ac0e38713d14ffa32c88927908b3f273febc81e268fe4a6473f8f0e3fca74c436e08e1f1b3690d0b41b29a519bdf7ba78e6fd0dc915dc78609eaf16c4cedc3a71c406b2bbfb0bfe6d86e9e2e00d6f7a1dc8be264751cf3e84bf58cd266b3f33e0948df9d5fcee3b1405192c5401d0bd3b97839260165935e254d64cbf4a2ea318bfe17fcf241f082e8b0ec78dc68369b02d1e1d9900184fe3b62bf56cc4ed66c0dccd433beb8585295cd478d3216eea43f258da09e7011549d9235e4763c57f46e985b6f2e9561157688e266e67b35e1ee8180c00d26b14cea81417b6244175d48d2381364d4fee04df5ea1aadacc07653f1e4857550648644dd62924caa4bf6d9df4cf2fb66e4b4287de8bcbb4fa45d06c1f54256e34639b2ec6cb8e9c9bbb0ad655b6e65c4372688ccf44e65f263f2b677f800e5b4a9464c611e51c1ad31637b7933313bd73e037e0a738ef0d782427a0b56c255dc9e1febf42ed6cbefc27f138aaf00336992a2e970d597bd037f05ff6cc92477a3528c5daaf6bd3c8d47c67ed6f91a4348ea43125352f34842843bb467220097384291a43b098a6c41611041fbfa9900a7733129710436da9c991a08c50eba4ebb7b22165a111cadbb0c86f6448f574857b561fa0813528ae886ad0e80192b53c21c831a317e7f2fea1521f8b3e237b79e40245feac47ae9a8d99fd1ee8f11aaaf8cc6fd7b1a066ae9299b210c55b7651b2052a4be88fd1eb3a85f515adb388d504507236464ef0c83151001e0035b6e55de0bd5091305cca1002de0d4b0fe920ddad16232d0cf82e0c7588399bad23a3bfdbcdda2fdaa532c2f421bc25480e395f5db0d724748b3751156c29348494c88d4fbc75b6a9997dd714a66228f1099f2d36ecab036d77728183c704beae2cfb594dd8484c0d2b299626e1413a584fef756c73945200f16cf05b79568dc94b56dab9569adcdd000d55aa04b35115ec11ba53bd8a05e576d5956b4df9170b6e65c9849a6204fb62c98ef2b8d3d138f95d0335180831ebee7f5583e737c4782895f082defaae68775825a2ab34403347261a6fd497ee7a9eadf050e9954a01b173aaf5e9a21a03d66f")
ct2 = bytes.fromhex("770178bcb4c79bb17a3e9d3fae37aff128817b9528af0fd6ba9b35638095318ca7c640c7b5f4ca9dd5621472887287fc07d9bdeea79c6c68d059cc3e497c036e8fbf6b9ed480d3b4be6069dd834c6a9a162ba2a879cdf7286697670c9d299086e79844760caff21366ebf507d59fe40a0a59fca4df49fb306937faeb4d3b6ad266c2def5b5d78ef5cb6fd66a2e4cbe251d54e71478f539a82683d7f403e583bddcd0db7bf992c6dc1d50de5066c209bf14995e92b0383437719e3f93ccbc9eda83674d770d7d29b182e7fe3f1b791de8231645dfd3c258ae65fec2e1f1e9693c4f138b3b3c714385285fe25c7ab1a7c77c64c974e003c2d0ca4c144f7a6ebeba7d556aefe0929658b96b9252e7c3682a611915583da9c20ca84d3ef1b551f41c5f2adfb76970f8653342064587693dba7318d8118dd1f31ef27f22caad90c1f9145d71074fed2d81928c29d077ad92b679fe8d79ded8c62ca8bf53218df5439b1a81d6f21df99e0432c67f6002a0155b82f0f6953b6c5a5324df90333fe1c731f792e3f27fdc09047b13de99fcc1763cd1fe7a0587becbbf2ce09b9897c6325258450055c49bcf3506db1a2b055f7a029e99f1343888d8d8fa4a84be11ca1f5b85ffbf00b96dc61d05db4b446eba1a53aae9bdbac981d7046ca3158e67cf7e3f9c357fea73718d61da1e0fe42a4e4f10490495deee5174f02326b591b7dbf8d0e52841faf4da6b469d250f65ed794f08c438307752ab5368db551da6aba167bbf3ddb34e54f4ce725512721343714338901492fa298db176449277011ae92d252a7a9c5aac970dfd004329fdb2b0ca7a6d543ee133ed5a3d31e0a1b15a07cb366a25d5569eb124d74237604688fabc5bdec532ef76825d8592e910f6e59b843e8487605e0d823af50b0dea4bd199a9e52818fd90de3194fc0c9e3d30de743301a154cf08e40068234acdc8b4e5b39ca8f0053439db32b029ecc44b74998635d433eaf174b5946715e5ffdb21e3315f3a412c7e2b6ff53832befd256164ef47697dece91de9e7bc2d0095bde64422ef708223d6c0e59f0e0762197d59846b0c9f3060edc4cabc79e01acc72c8580af50b959b2436dde3753fa316cfd9a789facb770c3afdf04a183e897ff5b5b8366f8c3092b1d1ab0975c0f83b0a1da0a1e105cc067339bdee25f82d9a5e02d8ce593691e370e1ca297849e9e932d0773590a61a4ff645b468ad0d9fc0d1899e2ff5aa168d61fda073792e33c50f4a566385b87566afc14449b4fb9ac662a0f9267a872565f6e3458c24999c3972524c7015ad02ed24d93268d362b32ea6f6ea00ebabbae9968cab114f8f835a03802850951f5c16c5446d5f2910b1e72618e453b21e132b2275608471915271e019efc6324a88af1ec0a2c0840f676c64636ac7e8801f67befe418557956f9fb8274031392cb121b5f73434f30436a486f13cb36e39a9ee3bef53a1acbb90340755c2a06a6f1c21fb9f9ac3e520e20a90b952378d2759ae789ab26acbed14fab5d2d5c40e420a356c7ff0050d7368efd10cea07d9a1d7eeecc91ce13a066c93690a513d3cc7b1bbd468575aeb7b3563d60b82613b9ae50c5df8f26ae5bfe84677cc54898d504644e5b423ba47b507b30d495dbaa2e5f87f780be3b9562c1bfe1a1f79d828c4867274d2b5b31ef750f965d4a84dbadef33871e435d61425578fec1f1f6651d615fde35697e31162658239110e4b0ccf1d05e50ac275a82ddc8f7920dda8021f7c14e36692eeba0f2421151f3496566e2e176c6a4d89058d19479b89e043e1e4bb63f892c9134a5100a3b574afa9f7e6c6688e71ad3038c37587a6efb417e0473e06e14ad083b825c7f1caf0e9e61003da38fe526e421e1abad336ffe81fa166d7ff8714bb1972547f08e0cbb80355387f87ffcea8219f96a108f71e1474b68fd46dfda7bcfe899b9e752f7dbc68cf252f31a68435165de7748460b86341f6e3b10d6f5c3f7e6e813fa5ef538380914e127f21f728e0eb3370597c")
ct3 = bytes.fromhex("9a1019a263bf5c2b7473e7afe4c447db8b621e1b68ff78306e2a9f179b0cd3cacc544c3dbf8051f4d4e8bd9f921d07a6a757016bacfcf5075e895f7076303f845a2e7b6971184040cd98d6ceb90ce321afc89374230910051da77a080f544bf0f2c59dade7cb76d055763a9759ef7063d603012e2e525a7801d7928cdf68346883580415447e297107822d298b21522c472a9828b19667dd83cd3250a656f0976a320c35af7660b40900a6b714d6d531a63ea20c1c1982a959d87fe5fc502a0932a688c4530ebb9abb5d696fb8f29eaefdbdd5683d44c3438418c3c8469345fbdb2de1c230c5d36a0aba17fb671dd5b952903e314cdbf467263feedfa1c470879a91b2008600af5f7b69004a34ac6274e4484ea383caf910be86dfa19c43a38518254a04699a54c5718363e9c2a16e56d91bb4e2373069fd9934bfef2b853a79554f57ea4a7c8f199853122df8e556c0b4cb51894c0f5a232555242d2e48ec554bbdadaf5b4baa2cb6cbefe4463422fad383723f9757ad71fd594dbc984a54939b37c19634e62cf10f859e2a712ec603c15bff5526ab6248be1f118c5afa84181d067e4e9f1c0176a2753880634c148518c169a3aa695f12b68d54c4a9f8f976d3a6b0420ac0a39d51638c71199d87b5f185fdc4298247dced58026e3f9ab79424ebda18e8053d5e508f66137fa632b9a5dcd4a25e4d9c5bda508ea9d1a2afb01511387e3b5d3f985e6ac97c7cb8614b316d3a3838acdd808c23d25c19cfd2116cecbda92cae83deb555c8ae8cc983aac571c9e4365a0c0d077a401df2bb8596f7d457f093367b0e49a1a11e79c7723d20a9e4b54d535a945e958323c4d39b648fd314dbb4afafad01c5504cc860f891f89d60a4d87dd90e53b89192bacc0a935c3253dc5f8454f776305d418734b3d5e4c71b6dabcc3230141f2e92129f415ccab55e1d81f07ea8709b008026001d994dad50cb1583a3b141e0a9fa5a2fb20b82558f04090f889b7f9bec4a5055a5f3ef60b278f5fc2c6ed8c51f826b9cc5be88cf667d8f7394342a7735b65001c766ec62f0a94970d90cf94d4d53f6ad8d273f2c6163390321578b2835e396072b6cbf7876e46e24c14a821b85a5be90b34147f0d8e553e361709c7871dda118dac4e1a11b254fe6eaeec628289e6a6fad2d1382c6602dd92b5026a123b1a6d972d9c4000c480574ce1c2c45e33c5437d469857a427964e05ec79ade151943ab01c33bc6e4eff64d81515851f08b3ba64854683217595397161173a47e5de056b290dc47324c68fa47ce7a53c19048d72b549bfa70f2d9f8e06e3d27214be154f9668b02bfcf69576c15ce42e6736e4dff74a21f3754ff7e4ad396132435f19ae605dbdbffba84f99898ca7fb51055af2093658eab899a06318a0e30b01c3b731df1f22751bbce2db6f2a1bd695b386b42203327fb51fddfc616c838f046e6aa6af7149335b43460d6e578eac6c0d3950c3577957ada59d1a68bf12b652a4bdde7cc7dbe304f3e608dd0581439394c3f3e73bb79ef288bdda8d7bc6d2f4b1d31997e320005a92426ea75264fce6fcfd256a17290cac2a62c29dfbfe7e9b0c31ce48643612a949277ac98b6403cd94a99a5c187067562f63377bf7819fa3f0a626dd9d3d53238e60b2603d5cf9ec83ef5c028841799fa11e213c43a549aa1916ad48b27bbd894a7a4825ad2cbf25cec2dacb1da3a22b916a5f2988c17c624f7100d8c9fe6331c3c04f81653798935dfb231ff2802cd8d01700f17e77fbb794dffd6bec64fb8158202f2b989d8a6df2d5970b83f75c9ea6d4b372069254d4bbb926db3cc2758c5a95e573a9af016ace085db954561900a867490a99df789435589bc471936e159521daea5e4a5a90fc37f657cb5c694ff39fa35ae59f45dad5088e923319caa5afd9c46d974a498d339c6b05cd06d07cdda7648d60c6153b452c734e4935cbb3bcf22b3433a8dcca328bc147e697cadd0bd2ff0d0f4c93bf17af2df0ff4a36808f9cc2f6f838518")
key3 = bytes.fromhex("2b753a867adf4ee6123c63a3da5960a6d6f272bf0322e747bff70403bfd43d522ae42ce795840ebc3ba5e28a7b5c689dd6b87c2251ad9d01e5d3b5d08fdb46a7bc8ec51c753568284ffe7d995e5cd998f4dbcfbd6e8c250e989714b99588a176a8d8e50bec8d41485261bca97f7461a53332a6c91abfebe2a3289e66487fb0d7158f122a0f5726eeb25a79eb399f8b409a0620ce369236c9964ea3e1ded237b0fe230191c696814c10a9716c60820ab63f611bf9ea7b096f8075d229bc153a48c8fb20276c85a00731c032ba37ccd1ca8ae648a086cf4348b4f201018745bcef88c38dd0c245a675e565796c601c9b9527debed789987b3c688df53b07e336bff1354b3d3e8756bba71fe8279bf2901a18826bb9c7cd48fa7497656527e3560cea33892d0721f72d89fe3e9818858b4552410231122f600969b0aec134f641732d6f43c0b8dc7e69a2466d5dd86fbdbf249b9b63aa2854b982a750a3c378bcbfdc43d1a76b63308d43f726c893f49dab576dff84c372b3a6d304a58dd0c1626b4dd79ffb0bd202575852248c19c80d1072ab8a51c1d25c6655f943d69274046ba3c03e00b90b1f6191707bbc29665427b931b57b07c0cf11f1c9e37b116351d859e2108d019b01a46b92d66ca856ce2f13786be209f75e2f26304a0beb57301e6f9107ff519f8dad84508410c72364cefd30e4e787a04152a8434f3d69cd09aaf507a6538b9ad9518932aff7e4f5f663e74c9c5e0e22e395c47fd1606943ebd382ae0103294f7c71a440c0145ad0eb4f27300dbb959537bc7963d9f37c0c327e3a915f77c40877939b5851a5bef25ca780a84ccef204654e20547d92b51f992ec8600610ec65ceb15e68f1c61fe36a2f8fc1e98b4aec24328b4db20b877807b35ce79524321d7820baf3930e238f939211871ae3ce955c2a7746d8afade9cfe61fb127a69cf3583c753f45737de444fcf48c04136d7d29f05074360718a74816992e0fdcff8a307be089b8f6e82d6e9b46917e2c5125f394fdbd55bb3044770886039df83c23de68ad85b9116681e4f7d2f0ebd1e68f842ef65a7af782a5556be66acd8e91033a37ac673a7937705dfd1174359d80af5e0dccb1de9b259e27fe4c13c841a11de51bd25817eb129736d2cd4c3049209c88d717815bb77eaedf5540fa6300c11291d2032e2e173433e10ab545c2bfec4de29a82efe30b2b6ddd8fad574531b5170daf39c2dbb398693e37e548eb05f0636e72b36d477e4fc2a2a57f7da6ca08909262871cb365dd2c37d3745413960978a7db2cf72c553c20789ba26d6078be4754ab07b82c6fe833edcdd3694741c163ce7175a6f0b43b686d421f64ef084904ffe0f0ab7ccd4a8cb1c99a8a518a451371d0e1807d32c906d65fea33a5e3ed0a6c89e00323f12012e0902b1bbdefcdec190bb37d317ad26dbea94a006dbadf19b9ede96b8001f41da3986d8e57bfba946d43bd8d12972fa468492ff69b95ab527d69c8c66bce25a9227ef3b575c3995abb6659d1775130399f072ba53f8fb79cf166f03a4096692a4ee126f959691689268636b851bba66cc3061ce267a6661d4bf54e3e846a51520467ea582ade3a139af556f09bc9f985575c4035036f41aecdce899d2eace709ebc40d8854ea21ee4f890c8a49c995a8a73682890a6d8579621d05110b250c6b4402b7443d753dae85a2805a950a89b0c47c874bdd474f0ff3e4ba3ba571e198798f10f24ae84491cc5b1211f58ea07ec9a3314b76e1a945075de2b3d9012d5fe2c93d8d46b9ce72e3c1536e23d8b19dbf48147bdb73d8f58c3940b0dcccd8d1a9bcc3165da911fa13c5a038aa9f101e3bb01a6db3564afe83943ba24901d3749b9e7e2f13b7c4391922d93dbfe8d92726793f8f676c87099ab1f0ce5190f98c7c6a1f12762b8571e9195df6c460b97b9e5854baf40a04e0f24f28ad6de50d0faf31f623c61552ac5249472b921fd9178c96c667a5cfc4fb48e9c3c10e66f1f69e43b43a542c44820572c26c69")

solve3 = [ct1,ct2,ct3,key3]

ans3 = ct1
for i in range(1,4):
    ans3 = xor(ans3,solve3[i])

ans2 = base64.b85decode(ans3)   

ans2 = ans2.decode('utf-8')
ans1 = codecs.decode(ans2, 'rot_13')

print(ans1)

### Giải thích
- Đề đã cung cấp `ct1`, `ct2`, `ct3`, `key3` và đều liên quan đến hàm `cauhoi3` nên ta sẽ phân tích hàm này trước.
- Hàm `cauhoi3` nhận vào 2 chuỗi bytes và trả ra 1 chuỗi bytes, cùng với đó gợi ý đề bài có cung cấp: "Tại sao lại tồn tại một thế giới mà ở đó lại xảy ra chuyện hoang đường: 1+1=0?" nên ta có thể suy ra hàm này xor 2 chuỗi bytes đầu vào.
- `ct1` xor `ct2` xor `ct3` = `key3` xor `weird`, mà `key3` thì file output cũng đã cung cấp nên ta chỉ cần xor 4 biến ở file output với nhau là tìm được `weird`.
- Sau khi xor `ct1`, `ct2`, `ct3`, `key3` với nhau thì ta thu được:
> Ta có thể thấy đây là `weird` và cũng là đầu ra của hàm `cauhoi2`
- Nhận thấy có nhiều kí tự đặc biệt và có dấu `=`, khả năng là `base64`. Nhưng dấu bằng lại xuất hiện ở giữa và có nhiều kí tự nằm ngoài phạm vi `base64`. Khả năng cao là `base85`.
- Thử giải đoạn đó bằng `bas85` thì thu được đầu ra:
> Vậy đó là `enc` cũng là đầu ra của cauhoi1.
- Ta thấy gợi ý cho câu hỏi 1 là: "Số 13 là số nguyên tố nhưng còn 1 ý nghĩa gì đó đằng sau nó mà tôi chưa biết...". Có thể nghĩ đến kiểu mã hóa cổ điển `ROT13`, tức là mã hóa Ceasar với k = 13.
> Thu được Flag: W1{D1d_y0U_GeT_r1Ck_r0lL3d?}

---
## Learning with Bruteforce
### Code

import numpy as np
from Crypto.Util.number import long_to_bytes
import sympy

b_list = [3142, 2772, 805, 2779, 2853, 1921, 535, 210, 1161, 989, 2484, 2104, 1594, 1048, 452, 3586, 56, 1370, 436, 1601, 512, 274]
A_list = [
    (2413, 2531, 3411, 2884, 2264, 377, 3514, 78, 1702, 3182, 3167, 20, 1054, 3422, 3177, 1535, 680, 3425, 3297, 535, 3390, 3619),
    (3236, 181, 2133, 1731, 844, 3201, 2176, 1268, 1285, 1692, 2874, 705, 1025, 2161, 1800, 992, 774, 625, 1897, 1823, 112, 2314),
    (1036, 1649, 317, 2345, 1900, 2149, 2964, 1518, 2909, 176, 3454, 2808, 465, 2940, 155, 2209, 3019, 1986, 1407, 2536, 3003, 155),
    (725, 237, 85, 2270, 1539, 1946, 1357, 1526, 759, 2183, 725, 1639, 2478, 2453, 2591, 520, 3060, 2483, 104, 1788, 1358, 1690),
    (2084, 1986, 1503, 560, 3033, 1451, 2721, 2749, 3537, 2408, 843, 1955, 498, 1849, 878, 2538, 2717, 3655, 3304, 2856, 926, 2658),
    (2431, 950, 953, 3046, 2543, 2422, 3552, 3656, 2063, 3585, 825, 2811, 497, 3635, 3445, 2579, 1882, 2003, 778, 2285, 866, 1288),
    (2859, 2257, 1451, 2988, 2568, 150, 2901, 3657, 1736, 2551, 3084, 3146, 2300, 3205, 3246, 909, 1574, 1345, 2087, 147, 584, 321),
    (3651, 1560, 3243, 1860, 1523, 1374, 1273, 1296, 1043, 1392, 3063, 2144, 21, 323, 3458, 2766, 2390, 2582, 2815, 211, 9, 1781),
    (2269, 2189, 1832, 1302, 2167, 2126, 863, 1101, 1177, 1689, 3631, 1722, 1933, 2429, 798, 912, 1360, 1811, 1740, 1759, 1981, 1266),
    (1788, 2524, 910, 448, 3558, 2913, 2309, 328, 404, 1995, 1633, 2605, 2421, 3488, 2860, 1259, 364, 1196, 1504, 1732, 2630, 587),
    (1975, 82, 3369, 129, 2504, 854, 1538, 3598, 953, 1324, 1469, 2984, 164, 2565, 744, 2792, 1196, 1383, 2922, 2544, 3609, 2630),
    (3120, 453, 248, 2510, 2464, 3098, 2459, 1219, 1179, 840, 1374, 2641, 1582, 304, 263, 186, 3191, 478, 988, 568, 3300, 929),
    (3401, 2877, 2106, 1352, 3664, 3069, 845, 1219, 1780, 3135, 2801, 251, 3617, 1195, 764, 2232, 2919, 693, 46, 3113, 2144, 874),
    (854, 2101, 3361, 2135, 1797, 3133, 2872, 3494, 2534, 1978, 1066, 1138, 439, 1503, 962, 1509, 2360, 1924, 1574, 483, 2641, 545),
    (2163, 3377, 253, 2530, 1968, 2470, 2662, 2807, 1264, 2924, 2528, 468, 729, 1707, 2692, 1960, 387, 3591, 800, 1428, 655, 2190),
    (1569, 3225, 3456, 1244, 157, 2438, 3248, 3443, 547, 967, 1107, 2571, 3068, 3578, 1799, 98, 452, 2108, 3462, 40, 2302, 41),
    (672, 2649, 1436, 2391, 2011, 2920, 2460, 1672, 3594, 2587, 1647, 1366, 3006, 1449, 2945, 2767, 3023, 991, 82, 1432, 1493, 1498),
    (1763, 3130, 948, 2461, 2695, 1362, 1558, 3344, 2710, 3397, 1845, 1735, 3493, 450, 407, 2907, 1564, 1203, 1497, 1656, 3651, 2348),
    (506, 1747, 50, 967, 1100, 2688, 283, 160, 3599, 2210, 3548, 3191, 252, 3519, 591, 3393, 3482, 1364, 1420, 425, 318, 2133),
    (2136, 625, 2454, 2764, 3635, 3514, 559, 1526, 1301, 2311, 837, 111, 3431, 1363, 3365, 2946, 1116, 1215, 1555, 3594, 973, 3622),
    (2464, 914, 3225, 706, 1804, 137, 2957, 1278, 766, 3570, 2155, 3634, 1960, 3482, 394, 2665, 896, 529, 1510, 1142, 656, 2868),
    (1080, 2030, 878, 945, 658, 1134, 2591, 1512, 313, 3348, 1329, 1571, 1108, 3279, 3185, 1188, 1330, 2315, 2885, 3190, 2141, 1307)
]

p = 3671
n = 22

A = sympy.Matrix(A_list)
b = np.array(b_list, dtype=int)

A_inv = np.array(A.inv_mod(p), dtype=int)
pow_p = [pow(p, j) for j in range(n)]

e_val = (2006, 2506)

for i in range(2**n):
    bits = [(i >> k) & 1 for k in range(n)]
    e = np.array([e_val[bit] for bit in bits], dtype=int)

    y = (b - e) % p
    s = (A_inv.dot(y) % p)                

    s_list = [int(x) for x in s]

    flag_num = sum(s_list[j] * pow_p[j] for j in range(n))

    try:
        flag = long_to_bytes(flag_num)
    except:
        continue

    if flag.startswith(b'W1{') and flag.endswith(b'}'):
        print(flag)
        break

### Giải thích
- Ý tưởng bài toán là tìm s để khôi phục flag.
- Đề bài cung cấp cho ta ma trận A và b. với `b = s*A + e`
- Vậy nên: $s=(b-e)*A^{-1}$
- `n` là số chữ số của `n` trong biểu diễn cơ số 3671 và cũng là độ dài của mỗi hàng của ma trận A. Vậy `n = 22`.
- Vì e có 22 phần tử và mỗi phần tử có 2 trường hợp, nên có $2^{22}$ vector e thỏa mãn => Có thể bruteforce.
- Đoạn code chuyển ma trận A thành ma trận Sympy (tận dụng hàm lấy nghịch đảo module do thư viện này cung cấp).
- Tìm ma trận nghịch đảo của A theo modulo p với `p = 3671`.
- `pow_p` lưu các lũy thừa của `p` để quả trình khôi phục flag trong hàm `for` được nhanh hơn.
- Chuyển ma trận A và b sang numpy để thao tác tính toán trên ma trận được nhanh hơn.
- Tạo vòng lặp $2^{22}$ trường hợp.
- Xây dựng list `e` ở các trường hợp theo giá trị nhị phân của `i`(Biến của vòng lặp).
- Tìm được ma trận `S` ở từng trường hợp theo công thức trên, dùng nó để khôi phục Flag, các trường hợp gây lỗi thì bỏ qua.
- Dò hết $2^{22}$ trường hợp của vector `e` và tìm trường hợp nào khôi phụ được flag có dạng `W1{...}` thì in ra.
> Flag thu được: W1{M3ss1_1s_t43_90AT!!!!!!!!!!!}.

---
## Bo tu sieu dang
### Code

from Crypto.Util.number import long_to_bytes
e =65537
m1 = 2**1024-3 
m2=2**1022-2
m3=2**1020-1
m4=2**1018
c = 2027792127378145444099302510462900300257442068928010403052259994880511317607407514908720534902489134379904618947792557805368190009359079320337075768626232418980864987406619809977532904702783433112202254001367719098893178820312980355187703995660867067442830169498602243151057835147454968516377852012013934653
m1_list =[13,
          107,
          87671,
          3870037838243,
          279462107025143615623321823017,
          1325706410421371952032007611396267]
n=1
for i in m1_list:
    n*=i
    
def rsa_solve(a,b):
    x=0
    for ri,mi in zip(a,b):
        Ni=n//mi
        x+=ri*Ni*pow(Ni,-1,mi)
    return x%n

for i in range(100):
    for j in range(100):
        for k in range(100):
            x=c+i*m2+j*m3+k*m4
            if x>=m1: continue
            if (((x%m2)%m3)%m4)!=c: continue
            x_list=[pow(x,pow(e,-1,p-1),p) for p in m1_list]
            m=rsa_solve(x_list,m1_list)
            flag=long_to_bytes(m)
            if flag.startswith(b'W1{') and flag.endswith(b'}'):
                print(flag)
                exit(0)

### Giải thích
- Từ biểu thức tính ra `c` do đề cung cấp ta có thể suy ra:
$$
m^e = a1m1 + a2m2 + a3m3 + a4m4 + c
$$
Với a1, a2, a3, a4, b là các số nguyên chưa biết.
- Hoặc viết lại:
$$
x = im2 + jm3 + km4 + c
$$
Với $x=m^{e}mod(m1)$
- Bài toán này làm phát sinh nhiều giá trị x khác nhau, vậy nên ta phải brute force để tìm các giá trị x đó và giải theo giải thuật RSA và tìm m.
- Ta phân tích m1 thành các thừa số nguyên tố bằng công cụ [factordb.com](https://) và xây dựng list `m1_list`
- Tuy nhiên số cuối không phải số nguyên tố nên ta bỏ qua. Vậy nên mảng list `m1_list` gồm 6 phẩn tử.
- Khôi phục lại `m1` với 6 phần tử của `my_list`, đặt là `n`.
- Ta xây dựng hàm `rsa_solve` để khi tìm được `x` và kết hợp list `m1_list` sẽ khôi phục được m.
- Ta Brute Force các giá trị i, j, k từ 0 đến 99 để tìm khóa(vì m2, m3, m4 lớn nên giá trị này thường nhỏ).
- Vì là `x` đã lấy mod(m1) nên ta bỏ qua các trường hợp x > m1.
- `x_list` là danh sách các kết quả giải mã riêng rẽ trên từng modulus nhỏ.
- Hàm `rsa_solve` dựa trên ý tưởng biến thể `crt` của RSA: giúp ta ghép lại thành m khi ta có các kết quả riêng lẻ x[i] tương ứng với từng p[i], ta cần ghép chúng lại thành 1 kết quả duy nhất (mod n).
- Cuối cùng ta chuyển số `m` vừa tìm được sang bytes, so khớp với định dạng flag để quyết định xem có lấy hay không.
- Tìm được flag thì in ra ngay và dừng chương trình.
> Flag thu được: W1{RSA_w1th_0v3rl4pp1ng_m0dulo}

---
## Tổng kết
- Report khi xuất sang pdf có nhiều chỗ code bị khuyết.
- Link github chứa đầy đủ code từng bài: [https://github.com/TrangTuanAnh/Writeup_challenge_CTF_Lab_02](https://)