<h1 style="text-align:center; color:#56755e"> PicoCTF Walkthrough: Part 2 </h1> Dưới đây là các lời giải cho một số thử thách của **picoCTF** mà mình cảm thấy thú vị và hữu ích. Phần này sẽ là phần nối tiếp cho <a href="https://hackmd.io/@0160ca14/rJ5nw6B9xx">phần 1</a> khi chúng ta sẽ tiếp tục giải quyết các thử thách mật mã học. Phần này chủ yếu là các bài với độ khó **Hard** trong **picoCTF** nên sẽ hơi khó đối với các bạn mới bắt đầu học về mật mã học. ## corrupt-key-1 ![image](https://hackmd.io/_uploads/Hy2s0j1Cee.png) :::spoiler <b>msg.enc</b> (Đây là một file kỳ lạ nên mình không thể hiển thị ở đây được) ::: :::spoiler <b>private.key</b> ```text! -----BEGIN RSA PRIVATE KEY----- MIICXAIBAAKBgQC4yxzKmbasQYdsGIRXMqXL/Idd80bukALOYIUItfz2tgpax3Iq LWTvdOFEOjOOcKc+Y6MD86ya3xmFlWmfbp8wwAnSGcfZjE7IQgNhCDQCnHlWfvwI 9mtLw/Vkv7VxVGoGt+SPs1u5zOqaLNRDSfgpJCB436ZNUlknv9VdCZwCTwIDAQAB AoGAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAACQQDnAFaP9Qa9WJKv klkhJeBsvpvUXf6v6TGjM8E0YwI9TwAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA AAAAAAAAAkEAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAJBAAAAAAAAAAAAAAAAAAAAAAAAAAAA AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAACQAAA AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA AAAAAAAAAAAAAAAAAAACQAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA= -----END RSA PRIVATE KEY----- ``` ::: Như bản chất của mấy bài **crypotgraphy** trên trang web này, cứ thích lai tạp **forensics** vào, khiến cho các bài mật mã học này không còn mang trong mình dòng máu thuần khiết nữa. Cơ bản thì chúng ta sẽ có file chứa thông tin về toàn bộ tham số của RSA ở định dạng <a href="https://en.wikipedia.org/wiki/Privacy-Enhanced_Mail">PEM</a>, tuy nhiên thì định dạng này bị mất một phần thông tin (những chỗ chỉ toàn chữ **A**) nên chúng ta không thể dùng thư viện **Pycryptodome** của **python** để đọc các tham số RSA được. Tuy nhiên, ta có thể từ định dạng PEM đọc được các tham số RSA (kể cả khi PEM bị lỗi) bằng cách nhập lệnh này vào **Bash** như sau: ```bash! $ openssl asn1parse -in private.key -inform PEM ``` (Nhớ là nhập lệnh này tại vị trí có chứa file `private.key`) Sau khi nhập lệnh này thì ta sẽ thu được thông tin như sau: ![image](https://hackmd.io/_uploads/B1oWMFMAgg.png) :::info Tiêu chuẩn phổ biến nhất **(PKCS#1)** định nghĩa một khóa riêng tư RSA trong **ASN.1** là **một SEQUENCE chứa 9 số INTEGER** theo thứ tự chính xác như sau: ```text RSAPrivateKey ::= SEQUENCE { version INTEGER, -- Phiên bản (thường là 0) modulus INTEGER, -- n (Đây là thành phần của khóa công khai) publicExponent INTEGER, -- e (Đây cũng là thành phần của khóa công khai) privateExponent INTEGER, -- d (Số mũ bí mật) prime1 INTEGER, -- p (Số nguyên tố thứ nhất) prime2 INTEGER, -- q (Số nguyên tố thứ hai) exponent1 INTEGER, -- d mod (p-1) exponent2 INTEGER, -- d mod (q-1) coefficient INTEGER -- (q^-1) mod p } ``` ::: Như vậy ta đã thu được các thông tin quan trọng như sau: ```python! n = 0xB8CB1CCA99B6AC41876C18845732A5CBFC875DF346EE9002CE608508B5FCF6B60A5AC7722A2D64EF74E1443A338E70A73E63A303F3AC9ADF198595699F6E9F30C009D219C7D98C4EC84203610834029C79567EFC08F66B4BC3F564BFB571546A06B7E48FB35BB9CCEA9A2CD44349F829242078DFA64D525927BFD55D099C024F e = 0x010001 p_approx = 0xE700568FF506BD5892AF92592125E06CBE9BD45DFEAFE931A333C13463023D4F0000000000000000000000000000000000000000000000000000000000000000 ``` Chúng ta dễ dàng quan sát rằng $256$ bit kém quan trọng nhất của $p$ đã bị mất, vậy là chúng ta phải dùng đến <a href="https://en.wikipedia.org/wiki/Coppersmith%27s_attack">tấn công Coppersmith</a> để khôi phục lại $p$, từ đó giải ra RSA. Tuy nhiên, vì quá nhiều số bit bị mất (đúng một nữa số bit của $p$) nên ta khó có thể dùng tấn công này để giải ra được. Vì vậy, ta sẽ tiến hành brute-force một vài bit cao nhất bị mất của $p$ sau đó ta sẽ dùng tấn công này để khôi phục lại $p$ (Ở đây thì mình brute-force $7$ bit cao nhất trong những bit bị mất của $p$). Kể cả chúng ta đã cải tiến chiến lược tấn công, thì phương thức `small_roots()` của **SageMath** lại quá già nua và cũ kỹ để có thể brute-force với một số lượng lớn bit bị mất như vậy. Do đó, đến lúc chúng ta phải sử dụng một công cụ tân tiến và hiện đại hơn đó chính là triển khai <a href="https://github.com/kionactf/coppersmith"> tấn công Coppersmith của Kiona</a>. **Kiona** đã cải tiến Coppersmith khiến nó trở nên mạnh mẽ hơn, từ đó chúng ta có thể tiến hành khôi phục $p$ kể cả với số lượng bit bị mất gần như là một nửa. Thực tế thì thuật toán này đã thành công và mình đã khôi phục được $p$ để tiến hành lấy lại tất cả các tham số của RSA. Sau khi đã khôi phục RSA đầy đủ, chúng ta sẽ lấy **ciphertext** bằng cách tính `c = open('msg.enc', 'rb').read()` rồi sau đó lấy `bytes_to_long(c)` là được. Vậy là chúng ta đã khôi phục lại được **flag** rồi 🎉! >[!Important] Cách cài đặt Kiona's Coppersmith >Dưới đây sẽ là lưu ý và hướng dẫn nhanh cài đặt công cụ để thực hiện tấn công Coppersmith của **Kiona**. Vì đây là cách mình thực hiện trên máy tính của mình nên không biết máy các bạn khi làm có thành công không nữa. >1. Bạn chỉ cần nhập lệnh `git clone https://github.com/kionactf/coppersmith` để lấy folder **coppersmith** từ github. >Không cần phải nhập mấy lệnh build bằng **Docker** gì cả vì lệnh đó hình như cài cả môi trường ảo và cài luôn cả **SageMath** trong đó, cũng như cài rất khó khăn và phức tạp đồng thời cũng tốn dung lượng nên bạn không cần thiết phải cài bằng mấy lệnh đó làm gì cả. >2. Bạn nhập các lệnh `which flatter` và `which fplll` trên **Bash** để kiểm tra xem hai cái thuật toán này nằm ở đâu trên máy bạn nhé! >![image](https://hackmd.io/_uploads/HyuFJqzReg.png) >3. Hãy tìm file `lll.py` từ trong thư mục **coppersmith**, sau đó bấm vào đó và tìm đến dòng số 21 (ở dưới sẽ có các biến `_fplll_path` và `_fplll_path`). Ta sẽ chỉnh sửa đường dẫn của hai biến này thành các đường dẫn của mà bạn đã cài trong máy của bạn. >``` >_coppersmith_dir = os.path.dirname(__file__) ># _fplll_path = os.path.join(_coppersmith_dir, 'fplll', 'fplll') # /usr/bin ># _flatter_path = os.path.join(_coppersmith_dir, 'flatter', 'build', 'bin') # /usr/bin > ># Chỉnh lại thành đường dẫn bạn đã cài >_fplll_path = "/usr/bin" >_flatter_path = "/usr/local/bin" > >fplll_path = os.environ.get('COPPERSMITHFPLLLPATH', _fplll_path) >flatter_path = os.environ.get('COPPERSMITHFLATTERPATH', _flatter_path) >``` > > Vậy là ta đã hoàn thành trong việc cài đặt công cụ Coppersmith của **Kiona**, từ giờ nếu bạn muốn sử dụng nó thì chỉ cần dùng cách lệnh này trong file của bạn: >```text >import sys >sys.path.append("../../coppersmith") # Thay bằng đường dẫn đến folder coppersmith trong máy bạn. >from coppersmith_onevariable import coppersmith_onevariable >``` Dưới đây là toàn bộ lời giải cho thử thách này: :::spoiler <b style="color:#56755e">solution.py</b> ```python= # openssl asn1parse -in private.key -inform PEM from sage.all import PolynomialRing, Zmod from Crypto.Util.number import bytes_to_long, long_to_bytes, isPrime from tqdm import trange import re import sys sys.path.append("../../coppersmith") from coppersmith_onevariable import coppersmith_onevariable n = 0xB8CB1CCA99B6AC41876C18845732A5CBFC875DF346EE9002CE608508B5FCF6B60A5AC7722A2D64EF74E1443A338E70A73E63A303F3AC9ADF198595699F6E9F30C009D219C7D98C4EC84203610834029C79567EFC08F66B4BC3F564BFB571546A06B7E48FB35BB9CCEA9A2CD44349F829242078DFA64D525927BFD55D099C024F e = 0x010001 p_approx = 0xE700568FF506BD5892AF92592125E06CBE9BD45DFEAFE931A333C13463023D4F0000000000000000000000000000000000000000000000000000000000000000 R = PolynomialRing(Zmod(n), name='x') x = R.gen(0) bit_nums = 7 for i in trange(97, 2**bit_nums): f = x + (p_approx + i*(2**(256 - bit_nums))) possible_roots = coppersmith_onevariable(f, bounds=2**(256 - bit_nums), beta = 0.499) if(possible_roots != []): p = int(f(possible_roots[0])) break assert isPrime(p) and n%p == 0, "Critical Error 1!" q = n//p d = pow(e, -1, (p-1)*(q-1)) c = open('msg.enc', 'rb').read() c = bytes_to_long(c) m = pow(c, d, n) raw_flag = long_to_bytes(m) flag = re.search(rb'picoCTF\{[!-~]+\}', raw_flag).group() print("[!] Got flag:", flag.decode()) # [!] Got flag: picoCTF{d741543f172970457e6a9aaa890935b8} ``` ::: :::success **Flag: picoCTF{d741543f172970457e6a9aaa890935b8}** ::: ## corrupt-key-2 ![image](https://hackmd.io/_uploads/HJt5Z9MAlx.png) :::spoiler <b>msg.enc</b> (Đây là một file kỳ lạ nên mình không thể hiển thị ở đây được) ::: :::spoiler <b>private.key</b> ```text! -----BEGIN RSA PRIVATE KEY----- MIICXQIBAAKBgQDCDU8HkvFi4/NIb0fCxbBWlrpcgewJ9Thr90G3KJuF4tdEVZgl ojsK4JTaIU8xWDROXVuob7Hs0fQMhoKnvuVQIeuncuI3kwAaOLnMy/3B2TFszMO3 ms0EXFErRODzaXODlYETooB5HhfCP+gPo4CZ5JB/cPTSKCharGntLTvPmQIDAQAB AoGAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAACQQD+iYRAewgWzCjl zMa7c3kAAAAAAMo4Bt0s/fyNYWsAAAAAYQmk2+OHa40bityRdd+6Dh7zGIAWSNYA AAAAAKBbAkEAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAJBAAAAAAAAAAAAAAAAAAAAAAAAAAAA AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAACQAAA AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA AAAAAAAAAAAAAAAAAAACQQAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA -----END RSA PRIVATE KEY----- ``` ::: Tiến hành thực hiện tương tự như bài trên, ta thu được các thông tin như sau: ```python! n = 0xC20D4F0792F162E3F3486F47C2C5B05696BA5C81EC09F5386BF741B7289B85E2D744559825A23B0AE094DA214F3158344E5D5BA86FB1ECD1F40C8682A7BEE55021EBA772E23793001A38B9CCCBFDC1D9316CCCC3B79ACD045C512B44E0F3697383958113A280791E17C23FE80FA38099E4907F70F4D228285AAC69ED2D3BCF99 e = 0x010001 p_approx = 0xFE8984407B0816CC28E5CCC6BB73790000000000CA3806DD2CFDFC8D616B000000006109A4DBE3876B8D1B8ADC9175DFBA0E1EF318801648D60000000000A05B ``` Vậy là lần này tham số $p$ của chúng ta đã bị mất bit ở $3$ đoạn khác nhau, vì vậy chúng ta phải thực hiện **tấn công Copppersmith đa biến** để có thể tiến hành khôi phục lại được $p$. Vào thời điểm bài này ra mắt, bài này được xem là rất khó và rất người giải được tại vì các công cụ để giải các loại bài toán như thế này chưa nhiều và phổ biến. Tuy nhiên bây giờ nhờ có sự ra đời của tấn công Coppersmith do **Kiona** triển khai đã khiến cho công việc của chúng ta đơn giản hơn rất nhiều! Quay trở lại bài toán, chúng ta có thể sử dụng hàm `coppersmith_linear` của **Kiona** để có thể khôi phục lại được $p$, từ đó tiến hành giải RSA như bình thường để tìm lại được **flag**. >[!Warning] Lưu ý >Bạn cũng có thể sử dụng hàm`coppersmith_multivariate_heuristic` để tiến hành giải bài này, tuy nhiên thời gian chạy sẽ rất lâu và có thể không bao giờ ra vì hàm này dùng cho các đa thức đa biến phi tuyến tính nên sẽ không sử dụng thuật toán tối ưu nhất cho đa thức đa biến tuyến tính. Dưới đây là toàn bộ lời giải cho thử thách này: :::spoiler <b style="color:#56755e">solution.py</b> ```python= from sage.all import PolynomialRing, Zmod from Crypto.Util.number import bytes_to_long, long_to_bytes, isPrime from tqdm import trange import re import sys sys.path.append("../../coppersmith") from coppersmith_linear import coppersmith_linear n = 0xC20D4F0792F162E3F3486F47C2C5B05696BA5C81EC09F5386BF741B7289B85E2D744559825A23B0AE094DA214F3158344E5D5BA86FB1ECD1F40C8682A7BEE55021EBA772E23793001A38B9CCCBFDC1D9316CCCC3B79ACD045C512B44E0F3697383958113A280791E17C23FE80FA38099E4907F70F4D228285AAC69ED2D3BCF99 e = 0x010001 p_approx = 0xFE8984407B0816CC28E5CCC6BB73790000000000CA3806DD2CFDFC8D616B000000006109A4DBE3876B8D1B8ADC9175DFBA0E1EF318801648D60000000000A05B R = PolynomialRing(Zmod(n), names=['x', 'y', 'z']) x, y, z = R.gens() f = p_approx + x*(2**16) + y*(2**240) + z*(2**352) # roots = coppersmith_linear(f, bounds=[2**40, 2**32, 2**40], beta=0.4995, maxmatsize=1000) roots = [[378000827011, 3705861630, 508722975783]] p = int(f(roots[0])) assert isPrime(p) and n%p == 0, "Critical Error 1!" q = n//p d = pow(e, -1, (p-1)*(q-1)) c = open('msg.enc', 'rb').read() c = bytes_to_long(c) m = pow(c, d, n) raw_flag = long_to_bytes(m) flag = re.search(rb'picoCTF\{[!-~]+\}', raw_flag).group() print("[!] Got flag:", flag.decode()) # [!] Got flag: picoCTF{1d68da1447328c3f11541d076c9c613957d86566} ``` ::: :::success **Flag: picoCTF{1d68da1447328c3f11541d076c9c613957d86566}** ::: ## Crack the Power (No Explanation) ![image](https://hackmd.io/_uploads/Bkbn_aM0le.png) Cách giải tương tự như <a href="https://hackmd.io/@0160ca14/rJ5nw6B9xx#miniRSA"> bài này</a>, dưới đây là toàn bộ lời giải cho thử thách này: :::spoiler <b style="color:#56755e">solution.py</b> ```python= from gmpy2 import iroot from Crypto.Util.number import long_to_bytes n = 850192488671724411593414949333510077483071096693707903102320394742378571491822843376283851949470861818075806890108388902283722696668432346180309651398955117306256948731892014648343377360635785299710817523857883289731618311263576636534276821109010420753178559634901340604789378658384724082370234431202376505073916905797889582817291820128432338436795333472591627108500484583437460271290400727808143317685206529913860880388410819991953427656993999578446847886284133946345826907392741888144462855876768547242994732490563454256944592727712939356381982412479605674698360217956794649324851741497508338306178016089690893896727773801236898349451444330491834875383019269692995647054086984557199231912700593359965115480535588019251208951193389706283342052708339088009842599360838510657480988484569382209724798179960116217058860965664026167273593807065515579582799464235844963766943691956575895590072958419204106268470174384974256944727515089108203146759010721456357518632849463815363310102936852180475614018304971992469403717152671755972494356941624331593844086439040441750462174234098120769699801791240221868759583096250196002695990769933290823843554087140747685618298617765095616935510198740482360863741880033855877177191156207986255667268177 e = 20 c = 640637430810406857500566702096274080295167731635479640274760705704329834745477874965672179442241380279649152291050969332091830976943198847734415977548283171453481035282640484509583761270819296888257025423610485662327686746807124249949801573622622025474105445411840040848707900538974836502204083674934003917014859170779890252120520936707231672530138550675052950661474192855295453830397195247783998452664323732349420008517294161050124199670265314439879598381647127314712772548808612160779354709720895650121981177223490008248201450405152764628551694278264566165847529527374683997923166335487870492633337964403006300189760469566049124557315678595808047255318170512104170886552702569378959458824295010481695843284719354153292787385820974271650396981741339320687983380628305498834020090930469888563923010239874356737632339575780299779123268795656555862306591438587341766174657770814212432221156762042052091807416027774410855528501728964161702794878631542708859539338820717896541175233336294156172568901530237626544862910267079985279152762092723288118416875741016667540126137577917228529419644972932304443300913541487225113046155490500715183529932578432401 k = 0 while(True): expression = c + k*n m, exact = iroot(expression, e) if exact: flag = long_to_bytes(m).decode() break print("[!] Got flag:", flag) # [!] Got flag: picoCTF{t1ny_e_837d7226} ``` ::: :::success **Flag: picoCTF{t1ny_e_837d7226}** ::: ## Very Smooth ![image](https://hackmd.io/_uploads/S1Q_66z0xl.png) :::spoiler <b>gen.py</b> ```python= #!/usr/bin/python from binascii import hexlify from gmpy2 import * import math import os import sys if sys.version_info < (3, 9): math.gcd = gcd math.lcm = lcm _DEBUG = False FLAG = open('flag.txt').read().strip() FLAG = mpz(hexlify(FLAG.encode()), 16) SEED = mpz(hexlify(os.urandom(32)).decode(), 16) STATE = random_state(SEED) def get_prime(state, bits): return next_prime(mpz_urandomb(state, bits) | (1 << (bits - 1))) def get_smooth_prime(state, bits, smoothness=16): p = mpz(2) p_factors = [p] while p.bit_length() < bits - 2 * smoothness: factor = get_prime(state, smoothness) p_factors.append(factor) p *= factor bitcnt = (bits - p.bit_length()) // 2 while True: prime1 = get_prime(state, bitcnt) prime2 = get_prime(state, bitcnt) tmpp = p * prime1 * prime2 if tmpp.bit_length() < bits: bitcnt += 1 continue if tmpp.bit_length() > bits: bitcnt -= 1 continue if is_prime(tmpp + 1): p_factors.append(prime1) p_factors.append(prime2) p = tmpp + 1 break p_factors.sort() return (p, p_factors) e = 0x10001 while True: p, p_factors = get_smooth_prime(STATE, 1024, 16) if len(p_factors) != len(set(p_factors)): continue # Smoothness should be different or some might encounter issues. q, q_factors = get_smooth_prime(STATE, 1024, 17) if len(q_factors) != len(set(q_factors)): continue factors = p_factors + q_factors if e not in factors: break if _DEBUG: import sys sys.stderr.write(f'p = {p.digits(16)}\n\n') sys.stderr.write(f'p_factors = [\n') for factor in p_factors: sys.stderr.write(f' {factor.digits(16)},\n') sys.stderr.write(f']\n\n') sys.stderr.write(f'q = {q.digits(16)}\n\n') sys.stderr.write(f'q_factors = [\n') for factor in q_factors: sys.stderr.write(f' {factor.digits(16)},\n') sys.stderr.write(f']\n\n') n = p * q m = math.lcm(p - 1, q - 1) d = pow(e, -1, m) c = pow(FLAG, e, n) print(f'n = {n.digits(16)}') print(f'c = {c.digits(16)}') ``` ::: :::spoiler <b>output.txt</b> ```text! n = b03ea698ce2b51fb00e11e6fbaf1e5373dc5b0c70eb2b14a36d21e8667be8774eee51f6050a10237f6b24f21204fc8013681e7ed72ed051188f3274aae8f1de0d39389b514c196fa82c98a270bfabefd044da8c687b0e114ebbde82536c0709ac5ad81bfe0077e9d9b798ad5abecee52767e68f8060c45936521fd93893102eb1676f2ff41324a7a6b3dff2e830538e06d25934e9f14bf6b40ab5674fe648e314bf06f84282f5ef52bc1401de3a42eb66e64bcdadd2674348e5bdb7016feda44d719af387a948ad81cbaed10213dd930fc7bc7677d8c4cdab0645d0ff15e6ad6ca37135942c3be08f23e7be0992c8b3370dcdc31045e086d823107fb2e443dc9 c = a913a96e215b5aa79c702d27fa375c73d06787639c4131fb32877cafefaa8faf70e15f6a17ef2a9a6f5310b157cb287b740e77cb5385081d1853a9104bc16357b259fa2d146bd87398d4ef6f1c078289812952c67792cf9cd745049aeb9d4ab4dff2825a9c0b3381f19b2a67164f9d4de33c25f98bc2f224feb5507b531e1a1c7be5ed2d8ddd01f3fae37245e8cf99c75a21848993d445e1d6d69d555a3e6cc8055704fdde88df9084bda3ea65a9384fa64bf8df4d88946449526320c15d4d2d871638070489adf3f8c95caffeab40b0d137a9319be20cdf6ebbaf037f62093d9bd33edd4ffd7e1929b9ab06252956fd85250a0515ef2b4e035017be5702cdd3 ``` ::: Bài này nhìn phức tạp vậy thôi chứ thực chất chỉ là tạo hai số nguyên $p$ và $q$ sao cho $p - 1$ và $q - 1$ là các số smooth. Vì vậy, để làm bài này chúng ta sẽ dùng thuật toán <a href="https://en.wikipedia.org/wiki/Pollard%27s_p_%E2%88%92_1_algorithm"><b>Pollard's p − 1</b></a> để có thể phân tích thừa số nguyên tố. Để đọc thêm và hiểu sâu hơn về thuật toán này, bạn có thể độc mục **3.5 Pollard’s p −1 Factorization Algorithm** trong cuốn **An Introduction to Mathematical Cryptography \[Hoffstein-Pipher-Silverman\]** nhé! >[!Tip] >Bạn có thể tự viết lại thuật toán này cũng được, tuy nhiên ta có thư viện <a href="https://pypi.org/project/primefac/"><b>primefac</b></a> đã làm sẵn việc này cho chúng ta! Dưới đây là toàn bộ lời giải cho bài toán này: :::spoiler <b style="color:#56755e">solution.py</b> ```python= import primefac from Crypto.Util.number import long_to_bytes n = 0xb03ea698ce2b51fb00e11e6fbaf1e5373dc5b0c70eb2b14a36d21e8667be8774eee51f6050a10237f6b24f21204fc8013681e7ed72ed051188f3274aae8f1de0d39389b514c196fa82c98a270bfabefd044da8c687b0e114ebbde82536c0709ac5ad81bfe0077e9d9b798ad5abecee52767e68f8060c45936521fd93893102eb1676f2ff41324a7a6b3dff2e830538e06d25934e9f14bf6b40ab5674fe648e314bf06f84282f5ef52bc1401de3a42eb66e64bcdadd2674348e5bdb7016feda44d719af387a948ad81cbaed10213dd930fc7bc7677d8c4cdab0645d0ff15e6ad6ca37135942c3be08f23e7be0992c8b3370dcdc31045e086d823107fb2e443dc9 c = 0xa913a96e215b5aa79c702d27fa375c73d06787639c4131fb32877cafefaa8faf70e15f6a17ef2a9a6f5310b157cb287b740e77cb5385081d1853a9104bc16357b259fa2d146bd87398d4ef6f1c078289812952c67792cf9cd745049aeb9d4ab4dff2825a9c0b3381f19b2a67164f9d4de33c25f98bc2f224feb5507b531e1a1c7be5ed2d8ddd01f3fae37245e8cf99c75a21848993d445e1d6d69d555a3e6cc8055704fdde88df9084bda3ea65a9384fa64bf8df4d88946449526320c15d4d2d871638070489adf3f8c95caffeab40b0d137a9319be20cdf6ebbaf037f62093d9bd33edd4ffd7e1929b9ab06252956fd85250a0515ef2b4e035017be5702cdd3 e = 0x10001 p = primefac.pollard_pm1(n) q = n//p d = pow(e, -1, (p - 1)*(q - 1)) m = pow(c, d, n) flag = long_to_bytes(m).decode() print("[!] Got flag:", flag) # [!] Got flag: picoCTF{p0ll4rd_f4ct0r1z4at10n_FTW_376ebfe7} ``` ::: :::success **Flag: picoCTF{p0ll4rd_f4ct0r1z4at10n_FTW_376ebfe7}** ::: ## NSA Backdoor ![image](https://hackmd.io/_uploads/HJCtUAXCle.png) :::spoiler <b>gen.py</b> ```python= #!/usr/bin/python from binascii import hexlify from gmpy2 import * import math import os import sys if sys.version_info < (3, 9): math.gcd = gcd math.lcm = lcm _DEBUG = False FLAG = open('flag.txt').read().strip() FLAG = mpz(hexlify(FLAG.encode()), 16) SEED = mpz(hexlify(os.urandom(32)).decode(), 16) STATE = random_state(SEED) def get_prime(state, bits): return next_prime(mpz_urandomb(state, bits) | (1 << (bits - 1))) def get_smooth_prime(state, bits, smoothness=16): p = mpz(2) p_factors = [p] while p.bit_length() < bits - 2 * smoothness: factor = get_prime(state, smoothness) p_factors.append(factor) p *= factor bitcnt = (bits - p.bit_length()) // 2 while True: prime1 = get_prime(state, bitcnt) prime2 = get_prime(state, bitcnt) tmpp = p * prime1 * prime2 if tmpp.bit_length() < bits: bitcnt += 1 continue if tmpp.bit_length() > bits: bitcnt -= 1 continue if is_prime(tmpp + 1): p_factors.append(prime1) p_factors.append(prime2) p = tmpp + 1 break p_factors.sort() return (p, p_factors) while True: p, p_factors = get_smooth_prime(STATE, 1024, 16) if len(p_factors) != len(set(p_factors)): continue # Smoothness should be different or some might encounter issues. q, q_factors = get_smooth_prime(STATE, 1024, 17) if len(q_factors) == len(set(q_factors)): factors = p_factors + q_factors break if _DEBUG: import sys sys.stderr.write(f'p = {p.digits(16)}\n\n') sys.stderr.write(f'p_factors = [\n') for factor in p_factors: sys.stderr.write(f' {factor.digits(16)},\n') sys.stderr.write(f']\n\n') sys.stderr.write(f'q = {q.digits(16)}\n\n') sys.stderr.write(f'q_factors = [\n') for factor in q_factors: sys.stderr.write(f' {factor.digits(16)},\n') sys.stderr.write(f']\n\n') n = p * q c = pow(3, FLAG, n) print(f'n = {n.digits(16)}') print(f'c = {c.digits(16)}') ``` ::: :::spoiler <b>output.txt</b> ```text! n = 575ccba5eb432070f54b12237b91996ff33d9e8fd7c8766da0833a89fd1d95abda573a9e6973c7769f60de749cd044a5d50c62f929680eeb44c0b93b014c1bfdbf668f581a2bfa034c09b2f6b755f8ffe883b5b4e756621b983967e64d728f09f1e8485672b896550928bcab85e72569d140e8e2ddf79dde58a6f6bbcae9c4ae6e8b93e4dc882e0da5ab78a07a92b4257564b34a64b7b19d91f1dac8e695f9b988c49063d72a891762c08683bdee592ff7ce8bd5906a671ea8ea5a54c65211a7182f628e5aa87ad3d388be3fae703ed8c43df264c33dd4c8d6faf3d8571b5c220c05f14093a72b93fe0d93d73b1440fdad30e310daa87e566219b82217d0895d c = 307652ee5a77dab4e70ded15e2c791c268e2c2e389d1f02887ea5baf8cf2b4aab98b4c9c47556a3c4b98c668a90d856c548c574dfa9e252fb92c1886d0fb54ef2492de80879ed5c655ed7e3edebb748599ce2f5d6efaf3843818571d96c92a072f8d7d246c7f440001b5b9e75d6736bb96549e35b45f8e2ba7c133d9238b997c0a6c88a8748e086432017566a372b3defe3c070d0f68694eb3e3c1dd4d12942769d619ec214b6ec1a2d269b81363f5f4866ea8558bb10b22659069001083f45445031a9612df9cf9ee8cc905529e98b4d8c079fd1876d3f03b49c16f2105d3ca5fd9e0b14e777a678d6951aa9c92a35313ce444320e57b17e034ee6278926345 ``` ::: Bài này gần như tương tự bài trên khi ta cũng có $p$ và $p$ là những số nguyên tố sao cho $p - 1$ và $q - 1$ là những số trơn (**smooth number**), chỉ khác là lần này ta không phải giải RSA nữa mà giải phương trình logarithm rời rạc $3^{\text{flag}} \equiv c \pmod{n}$. Sau khi khôi được $p$ và $q$ thì ta sẽ tiến hành giải các phương trình như sau: $$ \begin{cases} 3^{\text{flag}_p} \equiv c \pmod{p} \\ 3^{\text{flag}_q} \equiv c \pmod{q} \end{cases} $$ Vì $p - 1$ và $q - 1$ là các số trơn nên ta có thể dễ dàng giải các phương trình logarithm rời rạc này bằng <a href="https://en.wikipedia.org/wiki/Pohlig%E2%80%93Hellman_algorithm"> thuật toán <b>Pohlig - Hellman</b> </a>. Sau khi giải được các phương trình thì ta sẽ thu được: $$ \begin{cases} \text{flag}_p \equiv u \pmod{p - 1} \\ \text{flag}_q \equiv v \pmod{q - 1} \end{cases} $$ Đến đây, ta chỉ cần sử dụng <a href="https://en.wikipedia.org/wiki/Chinese_remainder_theorem"> định lý thặng dư Trung Hoa </a> để có thể tìm được $\text{flag} \equiv \text{flag}_{\varphi(n)} \pmod{\varphi(n)}$, hiển nhiên ta có thể thấy rằng $\text{flag} < \varphi(n)$ nên ta đã khôi phục được **flag** hoàn chỉnh 🎉! Dưới đây là toàn bộ lời giải cho thử thách này: :::spoiler <b style="color:#56755e">solution.py</b> ```python= import primefac from Crypto.Util.number import long_to_bytes, isPrime from sage.all import Zmod, crt n = 0x575ccba5eb432070f54b12237b91996ff33d9e8fd7c8766da0833a89fd1d95abda573a9e6973c7769f60de749cd044a5d50c62f929680eeb44c0b93b014c1bfdbf668f581a2bfa034c09b2f6b755f8ffe883b5b4e756621b983967e64d728f09f1e8485672b896550928bcab85e72569d140e8e2ddf79dde58a6f6bbcae9c4ae6e8b93e4dc882e0da5ab78a07a92b4257564b34a64b7b19d91f1dac8e695f9b988c49063d72a891762c08683bdee592ff7ce8bd5906a671ea8ea5a54c65211a7182f628e5aa87ad3d388be3fae703ed8c43df264c33dd4c8d6faf3d8571b5c220c05f14093a72b93fe0d93d73b1440fdad30e310daa87e566219b82217d0895d c = 0x307652ee5a77dab4e70ded15e2c791c268e2c2e389d1f02887ea5baf8cf2b4aab98b4c9c47556a3c4b98c668a90d856c548c574dfa9e252fb92c1886d0fb54ef2492de80879ed5c655ed7e3edebb748599ce2f5d6efaf3843818571d96c92a072f8d7d246c7f440001b5b9e75d6736bb96549e35b45f8e2ba7c133d9238b997c0a6c88a8748e086432017566a372b3defe3c070d0f68694eb3e3c1dd4d12942769d619ec214b6ec1a2d269b81363f5f4866ea8558bb10b22659069001083f45445031a9612df9cf9ee8cc905529e98b4d8c079fd1876d3f03b49c16f2105d3ca5fd9e0b14e777a678d6951aa9c92a35313ce444320e57b17e034ee6278926345 p = primefac.pollard_pm1(n) assert isPrime(p) and n%p == 0, "Critical Error 1!" q = n//p Fp = Zmod(p); Fq = Zmod(q) cp = Fp(c); cq = Fq(c) flag_p = cp.log(Fp(3)) flag_q = cq.log(Fp(3)) raw_flag = crt([flag_p, flag_q], [p - 1, q - 1]) flag = long_to_bytes(raw_flag).decode() print("[!] Got flag:", flag) # [!] Got flag: picoCTF{b3w4r3_0f_c0mp0s1t3_m0dul1_1ca93858} ``` ::: :::success **Flag: picoCTF{b3w4r3_0f_c0mp0s1t3_m0dul1_1ca93858}** ::: ## triple-secure ![image](https://hackmd.io/_uploads/ryKzm14Agg.png) :::spoiler <b>encrypt.py</b> ```python= #!/usr/bin/env python3 from Crypto.Util.number import getPrime, bytes_to_long with open('flag.txt', 'rb') as f: flag = f.read() p = getPrime(1024) q = getPrime(1024) r = getPrime(1024) n1 = p * q n2 = p * r n3 = q * r moduli = [n1, n2, n3] e = 65537 c = bytes_to_long(flag) for n in moduli: c = pow(c, e, n) with open('public-key.txt', 'w') as f: f.write(f'n1: {n1}\n') f.write(f'n2: {n2}\n') f.write(f'n3: {n3}\n') f.write(f'e: {e}\n') f.write(f'c: {c}\n') ``` ::: :::spoiler <b>public-key.txt</b> ```text! n1: 15192492059814175574941055248891268822162533520576381643453916855435310880285336743521199057138647926712835561752909538944229702432795423884081992987060760867003375755338557996965825324749221386675061886921763747311599846248565297387814717840084998677273427776535730840343260681623323972936404815862969684384733188827100528542007213405382537935243645704237369770300643318878176739181891072725262069278646319502747718264711249767568106460533935904219027313131270918072460753061248221785076571054217566164086518459844527639082962818865640864990672033657423448004651989761933295878220596871163544315057550871764431562609 n2: 15896482259608901559307142941940447232781986632502572991096358742354276347180855512281737388865155342941898447990281534875563129451327818848218781669275420292448483501384399236235069545630630803245125324540747189305877026874280373084005881976783826855683894679886076284892158862128016644725623200756074647449586448311069649515124968073653962156220351541159266665209363921681260367806445996085898841723209546021525012849575330252109081102034217511126192041193752164593519033112893785698509908066978411804133407757110693612926897693360335062446358344787945536573595254027237186626524339635916646549827668224103778645691 n3: 16866741024290909515057727275216398505732182398866918550484373905882517578053919415558082579015872872951000794941027637288054371559194213756955947899010737036612882434425333227722062177363502202508368233645194979635011153509966453453939567651558628538264913958577698775210185802686516291658717434986786180150155217870273053289491069438118831268852205061142773994943387097417127660301519478434586738321776681183207796708047183864564628638795241493797850819727510884955449295504241048877759144706319821139891894102191791380663609673212846473456961724455481378829090944739778647230176360232323776623751623188480059886131 e: 65537 c: 5527557130549486626868355638343164556636640645975070563878791684872084568660950949839392805902757480207470630636669246237037694811318758082850684387745430679902248681495009593699928689084754915870981630249821819243308794164014262751330197659053593094226287631278905866187610594268602850237495796773397013150811502709453828013939726304717253858072813654392558403246468440154864433527550991691477685788311857169847773031859714215539719699781912119479668386111728900692806809163838659848295346731226661208367992168348253106720454566346143578242135426677554444162371330348888185625323879290902076363791018691228620744490 ``` ::: Bài này sẽ cho chúng ta $n_1 = p\cdot q$, $n_2 = p\cdot r$, $n_3 = q\cdot r$ và tiến hành mã hóa RSA dựa vào $3$ số $n$ này. Chúng ta có thể khôi phục được $p$, $q$ và $r$ bằng cách tính: $$ \begin{cases} \displaystyle r = \frac{\sqrt{n_1n_2n_3}}{n_1} \\ \displaystyle q = \frac{\sqrt{n_1n_2n_3}}{n_2} \\ \displaystyle p = \frac{\sqrt{n_1n_2n_3}}{n_3} \end{cases} $$ (Chứng minh công thức này tại sao đúng thì mấy đứa cấp 2 cũng làm được nên mình không ghi cách chứng minh ở đây) Sau khi có được $p$, $q$ và $r$, thì ta có thể dễ dàng khôi phục **flag** bằng cách giải RSA ngược lại với những gì đề bài đã làm. Dưới đây là toàn bộ lời giải cho thử thách này: :::spoiler <b style="color:#56755e">solution.py</b> ```python= from gmpy2 import iroot from Crypto.Util.number import long_to_bytes n1 = 15192492059814175574941055248891268822162533520576381643453916855435310880285336743521199057138647926712835561752909538944229702432795423884081992987060760867003375755338557996965825324749221386675061886921763747311599846248565297387814717840084998677273427776535730840343260681623323972936404815862969684384733188827100528542007213405382537935243645704237369770300643318878176739181891072725262069278646319502747718264711249767568106460533935904219027313131270918072460753061248221785076571054217566164086518459844527639082962818865640864990672033657423448004651989761933295878220596871163544315057550871764431562609 n2 = 15896482259608901559307142941940447232781986632502572991096358742354276347180855512281737388865155342941898447990281534875563129451327818848218781669275420292448483501384399236235069545630630803245125324540747189305877026874280373084005881976783826855683894679886076284892158862128016644725623200756074647449586448311069649515124968073653962156220351541159266665209363921681260367806445996085898841723209546021525012849575330252109081102034217511126192041193752164593519033112893785698509908066978411804133407757110693612926897693360335062446358344787945536573595254027237186626524339635916646549827668224103778645691 n3 = 16866741024290909515057727275216398505732182398866918550484373905882517578053919415558082579015872872951000794941027637288054371559194213756955947899010737036612882434425333227722062177363502202508368233645194979635011153509966453453939567651558628538264913958577698775210185802686516291658717434986786180150155217870273053289491069438118831268852205061142773994943387097417127660301519478434586738321776681183207796708047183864564628638795241493797850819727510884955449295504241048877759144706319821139891894102191791380663609673212846473456961724455481378829090944739778647230176360232323776623751623188480059886131 e = 65537 c = 5527557130549486626868355638343164556636640645975070563878791684872084568660950949839392805902757480207470630636669246237037694811318758082850684387745430679902248681495009593699928689084754915870981630249821819243308794164014262751330197659053593094226287631278905866187610594268602850237495796773397013150811502709453828013939726304717253858072813654392558403246468440154864433527550991691477685788311857169847773031859714215539719699781912119479668386111728900692806809163838659848295346731226661208367992168348253106720454566346143578242135426677554444162371330348888185625323879290902076363791018691228620744490 moduli = [n1, n2, n3] n_prod = n1*n2*n3 prime_prod, exact = iroot(n_prod, 2) assert exact, "Critical Error 1!" r = prime_prod//n1 q = prime_prod//n2 p = prime_prod//n3 phi_pq = (p - 1)*(q - 1) phi_pr = (p - 1)*(r - 1) phi_qr = (q - 1)*(r - 1) d_pq = pow(e, -1, phi_pq) d_pr = pow(e, -1, phi_pr) d_qr = pow(e, -1, phi_qr) for d, n in zip((d_qr, d_pr, d_pq), moduli[::-1]): c = pow(c, d, n) flag = long_to_bytes(c).decode() print("[!] Got flag:", flag) # [!] Got flag: picoCTF{1_gu3ss_tr1pl3_rs4_1snt_tr1pl3_s3cur3!!!!!!} ``` ::: :::success **Flag: picoCTF{1_gu3ss_tr1pl3_rs4_1snt_tr1pl3_s3cur3!!!!!!}** ::: ## XtraORdinary ![image](https://hackmd.io/_uploads/BkIcPyN0ex.png) :::spoiler <b>encrypt.py</b> ```python= #!/usr/bin/env python3 from random import randint with open('flag.txt', 'rb') as f: flag = f.read() with open('secret-key.txt', 'rb') as f: key = f.read() def encrypt(ptxt, key): ctxt = b'' for i in range(len(ptxt)): a = ptxt[i] b = key[i % len(key)] ctxt += bytes([a ^ b]) return ctxt ctxt = encrypt(flag, key) random_strs = [ b'my encryption method', b'is absolutely impenetrable', b'and you will never', b'ever', b'ever', b'ever', b'ever', b'ever', b'ever', b'break it' ] for random_str in random_strs: for i in range(randint(0, pow(2, 8))): for j in range(randint(0, pow(2, 6))): for k in range(randint(0, pow(2, 4))): for l in range(randint(0, pow(2, 2))): for m in range(randint(0, pow(2, 0))): ctxt = encrypt(ctxt, random_str) with open('output.txt', 'w') as f: f.write(ctxt.hex()) ``` ::: :::spoiler <b>public-key.txt</b> ```text! 57657535570c1e1c612b3468106a18492140662d2f5967442a2960684d28017931617b1f3637 ``` ::: Bài này sẽ cho `flag` của chúng ta mã hóa với một `key` bí mật, sau đó lại tiếp tục mã hóa với các phần tử trong danh sách `random_strs` để cho ra **ciphertext**. Nhân tiện thì cách mã hóa trong bài này đơn giản là phép **XOR** mà thôi! Nhờ vào tính chất đặc biệt $(x \oplus a) \oplus a = x$ nên mỗi phần tử trong `random_strs` ta chỉ cần hoặc là không giải mã với **ciphertext** hoặc là giải mã với **ciphertext**. Tiếp theo, ta thấy `flag` được mã hóa với một `key` bí mật, mà đầu **flag** sẽ là ký tự "picoCTF{" nên sau khi brute-force với các phần tử trong `random_strs`, ta sẽ tiếp tục giải mã với ký tự `b"picoCTF{"` để xem được một phần (hoặc toàn bộ) khóa. Như vậy, ta sẽ sử dụng thuật toán quay lui để có thể làm điều này. Sau khi sử dụng và tiếp hành brute-force ta thu được kết quả như sau: ![image](https://hackmd.io/_uploads/H1NtkZNAex.png) (ở đây mình chỉ lấy có $8$ byte đầu tiên của kết quả) Trong cách ký tự kia, bạn sẽ thấy kí tự được khoanh đỏ không phải là ký tự vô nghĩa là chữ **A** đã được lặp lại, vậy ta có thể đoán rằng **key** chính là từ khóa **Africa!**. Như vậy, ta chỉ cần tiến hành brute-force lại với `key = b"Africa!"` là ta đã có thể ra ngay **flag**. Dưới đây là toàn bộ lời giải cho thử thách này: :::spoiler <b style="color:#56755e">solution.py</b> ```python= from Crypto.Util.number import long_to_bytes def encrypt(plaintext, key) -> bytes: ciphertext = b'' for i in range(len(plaintext)): ciphertext += bytes([plaintext[i] ^ key[i % len(key)]]) return ciphertext def decrypt(ciphertext, key) -> bytes: plaintext = b'' for i in range(len(ciphertext)): plaintext += bytes([ciphertext[i] ^ key[i % len(key)]]) return plaintext def backtrack_list(i, n, useful_random_strings, current, key): if(i == n): print(decrypt(current, key)[:8]) return for j in range(2): if(j == 0): result = backtrack_list(i+1, n, useful_random_strings, decrypt(current, useful_random_strings[i]), key) else: result = backtrack_list(i+1, n, useful_random_strings, current, key) def backtrack_return(i, n, useful_random_strings, current, key): if(i == n): possible_flag = decrypt(current, key) if(possible_flag.startswith(b"picoCTF{")): return possible_flag return None for j in range(2): if(j == 0): result = backtrack_return(i+1, n, useful_random_strings, decrypt(current, useful_random_strings[i]), key) if(result is not None): return result else: result = backtrack_return(i+1, n, useful_random_strings, current, key) if(result is not None): return result return None with open("output.txt", "r") as file: ciphertext = bytes.fromhex(file.read()) useful_random_strings = [ b'my encryption method', b'is absolutely impenetrable', b'and you will never', b'ever', b'break it' ] # backtrack_list(0, len(useful_random_strings), useful_random_strings, ciphertext, b"picoCTF{") # b'Elrmoq<T' # b"'\x1e\x17\x0c\x04QU " # b' \x1a\x17\x1f\n\x07Y&' # b"Bhr~a'0R" # b'$\x02\x16M\x16\x1eIt' # b'Fps,}> \x00' # b'Ats?sh,\x06' # b'#\x06\x16^\x18HEr' # b',\x1fR\x0c\r\x02S8' # b'Nm7mf":L' # b'Ii7~ht6J' # b'+\x1bR\x1f\x03T_>' # b'Mq6,tm&\x18' # b'/\x03SM\x1fMOl' # b'(\x07S^\x11\x1bCj' # b'Ju6?z;*\x1e' # b'(\x15R\x08\x01\x12N-' # b"Jg7ij2'Y" # b'Mc7zdd+_' # b'/\x11R\x1b\x0fDB+' # b'I{6(x};\r' # b'+\tSI\x13]Ry' # b',\rSZ\x1d\x0b^\x7f' # b'N\x7f6;v+7\x0b' # b'Africa!A' # b'#\x14\x17\x08\x08AH5' # b'$\x10\x17\x1b\x06\x17D3' # b'Fbrzm7-G' # b' \x08\x16I\x1a\x0eTa' # b'Bzs(q.=\x15' # b'E~s;\x7fx1\x13' # b"'\x0c\x16Z\x14XXg" flag = backtrack_return(0, len(useful_random_strings), useful_random_strings, ciphertext, b"Africa!") print("[!] Got flag:", flag.decode()) # [!] Got flag: picoCTF{w41t_s0_1_d1dnt_1nv3nt_x0r???} ``` ::: :::success **Flag: picoCTF{w41t_s0_1_d1dnt_1nv3nt_x0r???}** ::: ## Summary Trên đây là các thử thách chủ yếu ở mức độ khó trên **picoCTF**, ngoại trừ hai bài đầu rất ít lời giải ra thì các bài còn lại có khá nhiều lời giải nên độ khó có thể được coi là dễ nhất trong các thử thách khó rồi. Chúc bạn một ngày vui vẻ và hi vọng các lời giải này sẽ giúp ích cho bạn 👋.