# BÀI TẬP RSA ## EASY ### BIG PRIME (easy) :::spoiler chall.py ```py= from Crypto.Util.number import getPrime, bytes_to_long arr=[0]*32 N=phi=1 e=65537 flag=b'HUFLIT{*flag*}' m=bytes_to_long(flag) for i in range(32): arr[i]=getPrime(64) for i in arr: phi=phi*(i-1) N=N*i c=pow(m,e,N) print("c =",c) print("N =",N) print("e =",e) ``` ::: - Vì N được tạo từ 32 số nguyên tố 64 bit nên ta có thể factor dễ dàng. :::spoiler solve.py ```py= from Crypto.Util.number import long_to_bytes c = 7858185067710438675662001007304183656778436351123954087500766652075731404004517934762813666211947534011338163291340182240227236808558316266182382986395653680100925915308056886824256143797352577079783964851721686596414063813157538614116244241438656248907818466758594759249608114083027337683122876360838326976308984768566661317499159688854884283319781412997404435108391575278721930058762737468296989617425634245899737330892628320631590301478774868102712768238359079108142133109985649136097053287669402260169292289180209063784568436257879015039297816302737526460176147091581707584298180941231355031853885727544853713 N = 8632605909781338184285927064368567971915974732310762165421928121995129976993527644425770991611640378558724240151466728386565399545784274203071401925250866716567797058626881665309245219300723445329288679910154207239809278317016931305073588073279573649131559190382723170976132014716436828160783491922849402978700180286211973681761783870070673509005829394453213725311712316631226171883192791297824640302825469017100928098822454691276391914490349423038959050840982947742458161868987775975989252150845837566232994111364882898703122350657924496622697207692582605413276668649332394422599423367519049623951575000736802973 e = 65537 primes = [9362041171381277893 , 10231894034444487211 , 10338285888029928863 , 10872790960343391161 , 11262548642068797121 , 11488475851977526091 , 11556800382011371933 , 11573938116376429393 , 12291696385949937101 , 12322383250893551071 , 13395813490011718607 , 13966189010823427457 , 14367827409833742751 , 14684782621859089021 , 14791612552218590003 , 14949555143538711499 , 15177127802377859627 , 15276267006343343593 , 15317981050316620073 , 15945576441452122379 , 16002040371967633859 , 16099181742100207027 , 16873508828740677151 , 16893493643157343811 , 16904595743933129663 , 16929145519320082259 , 17087469192138944587 , 17099299523276938211 , 17374526971776921697 , 17678279161522375717 , 17787703711539237779 , 18442957044636300899] phi = 1 for p in primes: phi *= (p-1) print(long_to_bytes(pow(c, pow(e, -1, phi), N))) # ouput: b'HUFLIT{R5a_1s_3aSY_Ri9hT}' ``` ::: ### ezRSA (easy) :::spoiler chall.py ```py= from Crypto.Util.number import bytes_to_long, getPrime FLAG = b"W1{??????????????????????????}" p = getPrime(512) q = getPrime(512) e = 65537 n = p*p*q*q hint1 = p + q hint2 = p*q - (p+q) + 1 print("c =", pow(bytes_to_long(FLAG),e,n)) print("hint 1:", hint1) print("hint 2:", hint2) ``` ::: - Ta có $\phi(N) = (p-1)(q-1) = p.q - p - q +1 = p.q - (p+q) +1 = N - (p+q) + 1$ - Nên $\phi(N) = hint2, N = \phi(N) + hint1 -1$ :::spoiler solve.py ```py= from Crypto.Util.number import long_to_bytes e = 65537 c = 3778334964020085693122279865085669931544565594340822345918989508952697153279656102136896766069941711654206670695651429514092145744418890327941850114654449578138707810321552701030453820757236624767312202504750622959336960778419511800007797894081002357542180182105523582777650174695635469165347460411204007947912540366848738081190639561262267609709489546444644666346330477076696996699487362844232320060737648554287501932392681294728341607571792807384910146769288304726543715115373869342606973465866039825063286085254744403580981503955159533367921918990386586002820616696289107796591370087382822623875066545105848859819 hint1 = 20978135329472294939914714948198369484813382661367102444419294293577936274622454399412643333395069230540445488817871514639266385242274229865025904807357796 hint2 = 107283957759499663953333972940428532630825517639279168870550288698510570747194633174133941850038669632558664539532901591228896545932212704369190692506696118889217688783240077805671896860608066777266155415930965012190554894872594664088620308010376579887314084964024069034816205917207469185957050769629280580688 phi = hint2 n = phi + hint1 - 1 print(long_to_bytes(pow(c, pow(e, -1, phi), n))) # b'W1{0k_th1s_1s_e4sy_RSA_1nd33d}' ``` ::: ### hashad_croadcast_e3 ::: spoiler chall.py ```py= #!/usr/bin/env python3 import os, secrets, json def bytes_to_long(b: bytes) -> int: return int.from_bytes(b, "big", signed=False) def egcd(a, b): if b == 0: return (1, 0, a) x, y, g = 0, 1, b u, v, w = 1, 0, a while g != 0: q = w // g w, g = g, w - q*g u, x = x, u - q*x v, y = y, v - q*y return (u, v, w) def invmod(a, m): a %= m x, y, g = egcd(a, m) if g != 1: raise ValueError("inverse does not exist") return x % m def gcd(a, b): while b: a, b = b, a % b return a def is_probable_prime(n: int, rounds: int = 48) -> bool: if n < 2: return False small_primes = [2,3,5,7,11,13,17,19,23,29,31,37] for p in small_primes: if n % p == 0: return n == p d = n - 1 s = 0 while d % 2 == 0: d //= 2 s += 1 for _ in range(rounds): a = secrets.randbelow(n-3) + 2 x = pow(a, d, n) if x == 1 or x == n-1: continue skip = False for __ in range(s-1): x = pow(x, 2, n) if x == n-1: skip = True break if skip: continue return False return True def gen_prime(bits: int, require_p_mod3_eq2: bool = False) -> int: assert bits >= 64 while True: candidate = (1 << (bits - 1)) | secrets.randbits(bits - 1) | 1 if require_p_mod3_eq2 and (candidate % 3) != 2: continue if is_probable_prime(candidate): return candidate def gen_rsa_modulus(bits_each_prime: int, e: int): while True: p = gen_prime(bits_each_prime, require_p_mod3_eq2=(e==3)) q = gen_prime(bits_each_prime, require_p_mod3_eq2=(e==3)) if p == q: continue phi = (p-1)*(q-1) if gcd(e, phi) == 1: return p, q, p*q def main(): BASE = os.path.dirname(__file__) HANDOUT = os.path.join(BASE, "handout") ORGANIZER = os.path.join(BASE, "organizer") os.makedirs(HANDOUT, exist_ok=True) os.makedirs(ORGANIZER, exist_ok=True) e = 3 bits_each = 1024 FLAG = os.environ.get("FLAG", "cybercon{SNIP}").encode() p1,q1,n1 = gen_rsa_modulus(bits_each, e) p2,q2,n2 = gen_rsa_modulus(bits_each, e) p3,q3,n3 = gen_rsa_modulus(bits_each, e) assert gcd(n1, n2) == 1 and gcd(n1, n3) == 1 and gcd(n2, n3) == 1 m = bytes_to_long(FLAG) c1 = pow(m, e, n1) c2 = pow(m, e, n2) c3 = pow(m, e, n3) Nprod = n1*n2*n3 assert m**e < Nprod, "m^e must be < n1*n2*n3" with open(os.path.join(HANDOUT, "public.txt"), "w") as f: f.write("# Classic Håstad Broadcast (e=3)\n# Recover the flag string.\n") f.write(f"e = {e}\n") f.write(f"n1 = {n1}\n") f.write(f"n2 = {n2}\n") f.write(f"n3 = {n3}\n") f.write(f"c1 = {c1}\n") f.write(f"c2 = {c2}\n") f.write(f"c3 = {c3}\n") private = { "e": e, "p1": p1, "q1": q1, "n1": n1, "p2": p2, "q2": q2, "n2": n2, "p3": p3, "q3": q3, "n3": n3, "flag_str": FLAG.decode(), "flag_int": int.from_bytes(FLAG, "big"), "c1": c1, "c2": c2, "c3": c3 } with open(os.path.join(ORGANIZER, "private.json"), "w") as f: json.dump(private, f, indent=2) print("Generated handout/public.txt and organizer/private.json") if __name__ == "__main__": main() ``` ::: - Sourrce code của challenge khá dài nhưng ta thấy cùng một mũ e nhưng được mã hóa bằng 3 plaintext khác nhau nên ta có thể dùng Hashad Croadcast attack (Vì $m^e < N$ (với $N = N_1.N_2.N_3$)) ::: spoiler solve.py ```py= from Crypto.Util.number import long_to_bytes from gmpy2 import iroot def crt(r, n): ans = 0 N = 1 for i in n: N *= i for a, mod in zip(r, n): ans += a * pow(N//mod, -1, mod) * N//mod return ans % N e = 3 n1 = 15335841914037473058105049846306295913293561531198976085439445577305545207058122106375835687017209864514946494948354957415022647160332630755796719301949418569340848682130150560684956670781567317181294546938961711717909415607126915793155082936817722543172855926452078345765663607783495965098911032477754839592097153839337440006189349906109450341414254327699698110073784428784603793947289773978586082480655170178456924485838477519395475573998387932853755670959803532935966438000480674622318987085748507773864908648032689646822008401699711880281367277638380156891431562798722662077433958970170813522015738496434795953833 n2 = 20585610513285794800931119629810175934238015101159466069828431052775337882863742226119730257875804549398739852189029195628897191926883262426948740553208449151893652204896522807406651998992293180848101089999914749140511072111953866458203876097704565608353166088994839467531229162246229982252794345284531311972092052820621828122590761440658831540927177059297509249989837132567809607863250486742546352704209285591769485183491690483104155742018589590652626543300935514923515758021503108846344248992853720114648623675562070656741070278187947293499563036729636558221050666142123527353407605366003089692268089001698348073007 n3 = 28869597832583423090269111540653417314815220268829164627778154193217494935340799450077898515291200985710970129054953008296441465611174093579050204211558903523884370974239449693658458827781184285102630628567136173921175455351234997823259184091935068471718677508316606735411157654415314705121014252146479368426272543268262179768550790890769079807634096035274896456483829333689706353098760735639111239787853596583793449184036723332812432901645017249909220072392050317651075987874921448996671506725589330323200301496907095817601809006776859360764813267011452965388404147237784503248738969867013802953229930499443289949337 c1 = 249852220826328268464079521149028429732542389684864045421419630232819243189078213538649881453539435545506592859573314001551027168608367029227262514781078331946300046128367329461011963286878775900794308905136067987815473113124922565154424809354590715075511840615579243086815115150112954559875918789431663439644231541908947737781956329891053126380286330089104606816291055380135189392023982390677889987729120266373602221753706482268496731476961560543324585175800481622781866934794233049819311765651546138140895410674116216001113852568677 c2 = 249852220826328268464079521149028429732542389684864045421419630232819243189078213538649881453539435545506592859573314001551027168608367029227262514781078331946300046128367329461011963286878775900794308905136067987815473113124922565154424809354590715075511840615579243086815115150112954559875918789431663439644231541908947737781956329891053126380286330089104606816291055380135189392023982390677889987729120266373602221753706482268496731476961560543324585175800481622781866934794233049819311765651546138140895410674116216001113852568677 c3 = 249852220826328268464079521149028429732542389684864045421419630232819243189078213538649881453539435545506592859573314001551027168608367029227262514781078331946300046128367329461011963286878775900794308905136067987815473113124922565154424809354590715075511840615579243086815115150112954559875918789431663439644231541908947737781956329891053126380286330089104606816291055380135189392023982390677889987729120266373602221753706482268496731476961560543324585175800481622781866934794233049819311765651546138140895410674116216001113852568677 r = [c1, c2, c3] n = [n1, n2, n3] M = crt(r, n) m = iroot(M, e)[0] print(long_to_bytes(m)) # b'cybercon{1439f4eb2ceed0c46a2b1c5b2ab9e44b7155810005dcea0b9df7b480d5e6f005}' ``` ::: ### multi-RSA :::spoiler chall.py ```py= from Crypto.Util.number import long_to_bytes, getPrime from flag import flag p = getPrime(512) q = getPrime(512) e = 0x10001 n = p*q print(f"{n=}") out = open("cipher.txt", "w") for i in flag: out.write(str(pow(i,e,n))+'\n') # n=137011087466687507043856080810007427676937372756720323313836337110015956311054965751021707260815779836225195061060567426076623047184467073381300274273736204725459186831416986630039134760936272393597299287460953675802510481111090704695373863158640914763202192071078887569535605405964001133848039027030595079721 ``` ::: - Challenge mã hóa từng ký tự $i$ trong flag, mà mỗi ký tự $i$ = 1 byte = 8 bit => $i \in [0, 255]$, ta hoàn toàn có thể brute-force so sánh $i^e \pmod N == C$. :::spoiler solve.py ```py= from Crypto.Util.number import long_to_bytes from gmpy2 import iroot n=137011087466687507043856080810007427676937372756720323313836337110015956311054965751021707260815779836225195061060567426076623047184467073381300274273736204725459186831416986630039134760936272393597299287460953675802510481111090704695373863158640914763202192071078887569535605405964001133848039027030595079721 e = 65537 with open("cipher.txt") as f: ciphers = [int(x.strip()) for x in f] flag = '' for c in ciphers: for k in range(256): if(pow(k, e, n) == c): flag += long_to_bytes(k).decode() print(flag) # W1{brut3-f0rc3_c4n_s0lve_everyth1n9} ``` ::: ### miniRSA (medium) ::: spoiler chall.py ```py= from Crypto.Util.number import * from sympy import * def generate_key(): p = getPrime(1024) q = nextprime(p) n = p*q e = 65537 return n, e def encrypt_flag(): n, e = generate_key() flag = open("flag_rsa.txt", "r").read() flag = bytes_to_long(flag.encode()) encrypted_flag = pow(flag, e, n) return encrypted_flag,n def main(): encrypted_flag,n = encrypt_flag() print(f"Encrypted flag: {encrypted_flag}") print(f"n: {n}") with open("encrypted_flag.txt", "w") as f: f.write(f"encrypted_flag: {encrypted_flag}\n") f.write(f"n: {n}\n") if __name__ == '__main__': main() ``` ::: - Ta chú ý vào hàm sinh khóa: ```py= def generate_key(): p = getPrime(1024) q = nextprime(p) n = p*q e = 65537 return n, e ``` - `q = nextprime(p)`, tức là q sẽ là số nguyên tố tiếp theo đứng sau p, nên giá trị của p, q rất gần nhau. Vậy ta sẽ dùng Fermat attack. :::spoiler solve.py: ```py= from Crypto.Util.number import long_to_bytes from gmpy2 import iroot # n = p.q = ((p+q)/2)^2 - ((p-q)/2)^2 = x^2 - y^2 = (x + y)(x-y) # x = p+q/2 = p = sqrt(n) def fermat_attack(n): x = iroot(n, 2)[0] y = x**2 - n while y < 0: x += 1 y = x**2 - n while iroot(y, 2) == False: x += 1 y = x**2 - n return x + iroot(y, 2)[0], x - iroot(y, 2)[0] encrypted_flag = 2116434344760189570236071040826505770249644017864993891504255317659546686379782534435794212418514770732606777280358621440854725902927768001368698896382566043665411412689982003865543400955841867605465523553372418197723894461006103300810124479049320062465141550726700593441564260457241763819288423850725210529027101817002012166147729264640558291949462638083394474950533256723840009958816204024127563688097968261712800687742740485642782051591871131529672103479634900293661632121580477515845054319574588163626277722355372749870011795591249453084158878921370637433414899782502816229195059775464731419141042698700812034549 n = 10485845010311923631824067727292243533485945301872066796651194026452596147191359227489960650186984449355967534693309589769645241334663207263021480863316290733524446097316364769463182208111879930408226303114221992091822728915801139830161809680748469832564474774097656690096040844539452542796990312081217929885479649921972891857714514352748445051123716677123866539689138653272817248379689846267775288576105349412812817340352448806881213343524825252997261556158777105441043372947134515022800251273116921144977008845181631258930019593700480994849055096190313749777991037979833537039314655628498956987639678072678321639671 e = 65537 p,q = fermat_attack(n) print(long_to_bytes(pow(encrypted_flag, pow(e, -1, (p-1)*(q-1)), n))) # b'UTECTF{R54_m4y_b3_w33k_1251539023}' ``` ::: ### rsag ::: spoiler chall.py ```py= #!/usr/bin/env sagemath # -*- coding: utf-8 -*- # Respect the shebang and mark file as executable import os from Crypto.Util.number import getPrime from Crypto.Util.number import isPrime from Crypto.Util.number import bytes_to_long def generate_primes(): while True: p = getPrime(512), q = (2*p) + 1 r = (2*q) + 1 s = (2*r) + 1 if isPrime(q) and isPrime(r) and isPrime(s): break return (p, q, r, s) def main() -> int: (p, q, r, s) = generate_primes() N = p * q * r * s e = 0x10001 with open("flag.txt", "r") as flag_file: flag = flag_file.read().strip() CT = pow(bytes_to_long(flag.encode()), e, N) print(f"{N = }") print(f"{CT = }") return 0 if __name__ == '__main__': raise SystemExit(main()) # vim:filetype=python ``` ::: - Ta chú ý vào phần: ```py= def generate_primes(): while True: p = getPrime(512), q = (2*p) + 1 r = (2*q) + 1 s = (2*r) + 1 if isPrime(q) and isPrime(r) and isPrime(s): break return (p, q, r, s) ``` - $N = p.q.r.s$, ta có thể viết lại: $$N = p(2p + 1) (2(2p + 1) + 1)(2.(2.(2.p + 1) + 1) + 1)$$ - Vậy giải phương trình này ta sẽ tìm được $p$, sau đó dễ dàng tìm được $q, r, s$. Mình sẽ dùng sage để giải ![Screenshot 2025-10-20 140536](https://hackmd.io/_uploads/Bk4oMw70ex.png) ![Screenshot 2025-10-20 140544](https://hackmd.io/_uploads/rJ7oGPQRel.png) - Vậy ta đã tìm được nghiệm nguyên của p :::spoiler p ```py= p = 9352496155192295944243473644483853835662636576410969996619180877861158926367873785037099054018741236476166923118647057249968914650337399039210616026612969 ``` ::: ::: spoiler solve.py: ```py= from Crypto.Util.number import long_to_bytes N = 489654925303072532553659432557377999607856370197579144782976005904927235244321459117898721690940319487769632950077647476152880207627385231603017537961906244964117707813500615680799967895028255666319186794462243666159201392490299439947399915406223652423977002396844720487588735149486903743362109592536081726574342051928022071576485169655694281378301551060632699138055044915993078059902577590451519251321215765308977494770310317350866241246677761542212605478044672014913289740381478940929584556588858045439572693806615268502627912952686133840081188641597461343817750411035667135310831687533531094008308185320371643348451 CT = 58535947031303233853656030097871859886777764034955095086618901763996192727846608049414977429851683454541344096765319691912454768331685486037922533236779909508856486986528041125267338846421238077083738092020495236946742989769815669001100361743526446503248639704900983287986142636083524250650662602975802778548032518674346903013262799229594298599457623347987250272218522320743415393958131916181915804368140008312975210397791293701839101635851486434802271100141743496402698229558250485987421664294229816166263965806962242894230766553316312608696594536239328785792283453559549564751529321240567418095487324718881437825650 e = 0x10001 p = 9352496155192295944243473644483853835662636576410969996619180877861158926367873785037099054018741236476166923118647057249968914650337399039210616026612969 q = (2*p) + 1 r = (2*q) + 1 s = (2*r) + 1 d = pow(e, -1, (p-1)*(q-1)*(r-1)*(s-1)) print(long_to_bytes(pow(CT, d, N))) # b'gctf{54dly_50ph13_63rm41n_pr1m35_wh3r3_n07_u53d_53curly}' ``` ::: ### tung_tung_tung_sahur :::spoiler chall.py ```py= from Crypto.Util.number import getPrime, bytes_to_long flag = "grey{flag_here}" e = 3 p, q = getPrime(512), getPrime(512) N = p * q m = bytes_to_long(flag.encode()) C = pow(m,e) assert C < N while (C < N): C *= 2 print("Tung!") # now C >= N while (C >= N): C -= N print("Sahur!") print(f"{e = }") print(f"{N = }") print(f"{C = }") ``` ::: :::spoiler output.txt ``` Tung! Tung! Tung! Tung! Tung! Tung! Tung! Tung! Tung! Tung! Tung! Tung! Tung! Tung! Tung! Tung! Tung! Tung! Tung! Tung! Tung! Tung! Tung! Tung! Tung! Tung! Tung! Tung! Tung! Tung! Tung! Tung! Tung! Tung! Tung! Tung! Tung! Tung! Tung! Tung! Tung! Tung! Tung! Tung! Tung! Tung! Tung! Tung! Tung! Tung! Tung! Tung! Tung! Tung! Tung! Tung! Tung! Tung! Tung! Tung! Tung! Tung! Tung! Tung! Tung! Tung! Tung! Tung! Tung! Tung! Tung! Tung! Tung! Tung! Tung! Tung! Tung! Tung! Tung! Tung! Tung! Tung! Tung! Tung! Tung! Tung! Tung! Tung! Tung! Tung! Tung! Tung! Tung! Tung! Tung! Tung! Tung! Tung! Tung! Tung! Tung! Tung! Tung! Tung! Tung! Tung! Tung! Tung! Tung! Tung! Tung! Tung! Tung! Tung! Tung! Tung! Tung! Tung! Tung! Tung! Tung! Tung! Tung! Tung! Tung! Tung! Tung! Tung! Tung! Tung! Tung! Tung! Tung! Tung! Tung! Tung! Tung! Tung! Tung! Tung! Tung! Tung! Tung! Tung! Tung! Tung! Tung! Tung! Tung! Tung! Tung! Tung! Tung! Tung! Tung! Tung! Tung! Tung! Tung! Tung! Tung! Tung! Tung! Tung! Sahur! e = 3 N = 140435453730354645791411355194663476189925572822633969369789174462118371271596760636019139860253031574578527741964265651042308868891445943157297334529542262978581980510561588647737777257782808189452048059686839526183098369088517967034275028064545393619471943508597642789736561111876518966375338087811587061841 C = 49352042282005059128581014505726171900605591297613623345867441621895112187636996726631442703018174634451487011943207283077132380966236199654225908444639768747819586037837300977718224328851698492514071424157020166404634418443047079321427635477610768472595631700807761956649004094995037741924081602353532946351 ``` ::: - Chall mã hóa C không phải như cách thông thường mà là đầu tiên sẽ tính $C = m^e$, nếu C còn nhỏ hơn N thì lấy $C$ *= 2 và in ra chữ "Tung!", nếu C đã lớn hơn $N$ thì lấy $C$ -= $N$ rồi in "Sahur!". - Vậy giờ ta sẽ làm ngược lại để tính ra giá trị $C$ ban đầu, cụ thể: - Nếu nó là chuỗi "Sahur!" thì lấy C += N - Nếu là chuỗi "Tung!" thì C //= 2 - Khi đã có giá trị C ban đầu thì tính $m = \sqrt [e] {C}$ :::spoiler solve.py: ```py= from Crypto.Util.number import long_to_bytes from gmpy2 import iroot e = 3 N = 140435453730354645791411355194663476189925572822633969369789174462118371271596760636019139860253031574578527741964265651042308868891445943157297334529542262978581980510561588647737777257782808189452048059686839526183098369088517967034275028064545393619471943508597642789736561111876518966375338087811587061841 C = 49352042282005059128581014505726171900605591297613623345867441621895112187636996726631442703018174634451487011943207283077132380966236199654225908444639768747819586037837300977718224328851698492514071424157020166404634418443047079321427635477610768472595631700807761956649004094995037741924081602353532946351 with open("output.txt") as f: for x in f.readlines()[::-1]: if x == "Sahur!\n": C += N if x == "Tung!\n": C //= 2 print(long_to_bytes(iroot(C, e)[0])) # b'grey{tUn9_t00nG_t0ONg_x7_th3n_s4hUr}' ``` ::: ## MEDIUM ### Baby RSA :::spoiler chall.py ```py= from Crypto.Util.number import * flag = b"KCSC{???}" # Params m = bytes_to_long(flag) p = getPrime(512) q = getPrime(512) n = p*q e1 , e2 = getPrime(15) , getPrime(15) # Encrypt c1 , c2 = pow(m,e1,n) , pow(m,e2,n) #Print print(f'{c1 = }') print(f'{c2 = }') print(f'{n = }') # c1 = 43946260278933165267431660993044179256450733940962448204621518943475853900082006280519072025814200897790997592340463936456190958275666594052429995580298318496180813719454334563715414909165832843522756119935976461092478885641955852178168496150011655624379719912171071289603245412892961948366155515278642890726 # c2 = 128310176397306858891446325231403610621098642187330349239489878341148171560057825931212023839177308332325958639449594866005405570172437515529356365161126570201717589561767400076906280689289461272183010707070634476880143832792975654032711035308135704921921241852756875248875673992949337763386726353743428471285 # n = 136973822933716552336015210410086061910624054358619578509115117334628335462050100007125608207863413129800784125730025310219736602623178611290649570777043217574184550605465181131198300470624226421519634791007102521649222963071618444042047066059200007171516431004284842846905028782392942642458999153116596453733 ``` ::: - Nhìn qua thì đây là dạng As an external attacker nhưng ta không có giá trị của $e_1$, $e_2$. Mình nghĩ đến brute-force tìm e vì e là số nguyên tố 15 bit. Nhưng ta phải brute-force một cách tối ưu nhất có thể vì nếu dùng 2 vòng for trực tiếp thì sẽ chạy rất lâu. - Thư viện sympy có hàm `primerange()` dùng để sinh các số nguyên tố trên đoạn [a, b) rất tối ưu (nó sử dụng sàng Eratosthenes và được chia thành từng đoạn). Thay vì phải duyệt khoảng 268 triệu vòng lập thì chỉ cần duyệt khoảng 1.06 triệu lần. :::spoiler solve.py: ```py= from Crypto.Util.number import * from gmpy2 import gcdext from sympy import primerange c1 = 43946260278933165267431660993044179256450733940962448204621518943475853900082006280519072025814200897790997592340463936456190958275666594052429995580298318496180813719454334563715414909165832843522756119935976461092478885641955852178168496150011655624379719912171071289603245412892961948366155515278642890726 c2 = 128310176397306858891446325231403610621098642187330349239489878341148171560057825931212023839177308332325958639449594866005405570172437515529356365161126570201717589561767400076906280689289461272183010707070634476880143832792975654032711035308135704921921241852756875248875673992949337763386726353743428471285 n = 136973822933716552336015210410086061910624054358619578509115117334628335462050100007125608207863413129800784125730025310219736602623178611290649570777043217574184550605465181131198300470624226421519634791007102521649222963071618444042047066059200007171516431004284842846905028782392942642458999153116596453733 for e1 in primerange(2**14, 2**15): for e2 in primerange(e1 + 1, 2**15): g, u, v = gcdext(e1, e2) if(g == 1): flag = long_to_bytes(pow(c1, u, n) * pow(c2, v, n) % n) if b"KCSC{" in flag: print(flag) # b'KCSC{3x73rn4l_4774ck_1n_r54}' ``` ::: ### decimal RSA ::: spoiler chall.py: ```py= from Crypto.Util.number import * from sage.all import * from decimal import * getcontext().prec = 1337 m = int.from_bytes(open("flag", "rb").read(), "big") p = getPrime(1024) q = getPrime(1024) n = p * q e = 0x10001 c = pow(m, e, n) k = Decimal(13 * p) / Decimal(37 * q) 37*(n/p).k = 13*p 37/13*n*k = p^2 print(f"{n = }") print(f"{k = }") print(f"{c = }") # n = 17836315959849005845422913663414767117290475262210084622418539759689446526987983742651500754163602658702257438603344638391750819833709014484652708660912517485982576088329107650903579302135534346444527279395069706657542682545893504177489484878621091879201295227306042107538374526455876591399833571819123247023786020228360607799594672502655951840534378236130046255384167067161776621232261217694793553143425503847220013445117355362394757758134988247473606426051594142031253234833680135858089993033130033931424522824906259429530883731507010765394295893181162700003958569803358503992193879775739289254856625735853342656691 # k = Decimal('0.35446461146963444739100675019102427357742992648252679674999337860249514861192798736714999768802138877188987392684434984434144197346204736005963436261945282663139698407968154340692664314828815899336950075608038792449489090135267728757601438063136872975188570457340429981256096772094559698810422884676267599207870407837622200963038727101881041482893243181001811673162760179737922603650432405683896302254608853145829174684136576632615125057461035561006166588616534081650626850782025114955080335366309301772569589757429270179660568900330573464408796713721197954022970442599587489433052980288173667649600013009228667427447792587021853498147264391918385888912849882116066995440393702466541549251997103552974697549782099608620829417323165099966257193351492516942787771855106373851382745426598388778335847224000662124245942956989214545858513358450753373387923120632015977747472238670285286237716130056230984986202065783225256225423691426735932011376256751926687386762108587816483740258699371757433615173305137434119292838712721416785355612250164642843800878962968768192098173866139532824196545174345900695673844077156572039278918984913397930317429787962557294721805738693054179811835717065028952910215615224680053236949692064119797385474426572790113251198730129280310478508674699026563792292928948060895646025882846864383863565586607209169223951') # c = 4673035924389272278475077726179721834196795767239453119170003013692946332412255268083504867136759422845861665483227559383954843143670952281969970077731089347972838420010231661960479713394051608043031384693412159099965328507230965509961198520502268922686515047278411684052852995138615616040668732298091594792133478881624324818221814267947449074861355947381041272802241830653539106368971391423458933624515377831472054507217929993173878266225197776099109251511985341724790608910932841987840837417562296646705505719209341249852963919620413828831930283409960629361329433160615299527749956602571547705926320519915041473366 ``` ::: - Challenge này cho ta hằng số $k$ với $k = \frac {13p} {37q}$ (Decimal là kiểu dữ liệu để tính các số thập phân với độ chính xác cao). Vậy dựa vào $k$, ta sẽ tìm được $p, q$. $$k = \frac {13p} {37q} <=> 37q.k = 13p <=> \frac {37} {13}. \frac {N} {p}.k = p <=> p^2 = \frac {37} {13}.N.k $$ - Nhưng việc tính $p$ như vậy sẽ đến sai số vì phân số $\frac {37} {13}$ không phải là một phân số thập phân vô hạn tuần hoàn, khi được nhân với $N$ sẽ dẫn đến sai số rất lớn, nên khi ta tính một $f$ nào đó (với $f = \frac {37} {13}.N.k$), nó sẽ không đúng = $p^2$ mà là một giá trị nào đó xung quanh phụ thuộc vào độ chính xác mà ta tính được. Nên thay vì chỉ tính $f$ thì ta phải xét các số xung quanh $f$ như $f+1, f-1, f+2,...$ :::spoiler solve.py ```py= from Crypto.Util.number import * from decimal import * from gmpy2 import iroot getcontext().prec = 1337 n = 17836315959849005845422913663414767117290475262210084622418539759689446526987983742651500754163602658702257438603344638391750819833709014484652708660912517485982576088329107650903579302135534346444527279395069706657542682545893504177489484878621091879201295227306042107538374526455876591399833571819123247023786020228360607799594672502655951840534378236130046255384167067161776621232261217694793553143425503847220013445117355362394757758134988247473606426051594142031253234833680135858089993033130033931424522824906259429530883731507010765394295893181162700003958569803358503992193879775739289254856625735853342656691 k = Decimal('0.35446461146963444739100675019102427357742992648252679674999337860249514861192798736714999768802138877188987392684434984434144197346204736005963436261945282663139698407968154340692664314828815899336950075608038792449489090135267728757601438063136872975188570457340429981256096772094559698810422884676267599207870407837622200963038727101881041482893243181001811673162760179737922603650432405683896302254608853145829174684136576632615125057461035561006166588616534081650626850782025114955080335366309301772569589757429270179660568900330573464408796713721197954022970442599587489433052980288173667649600013009228667427447792587021853498147264391918385888912849882116066995440393702466541549251997103552974697549782099608620829417323165099966257193351492516942787771855106373851382745426598388778335847224000662124245942956989214545858513358450753373387923120632015977747472238670285286237716130056230984986202065783225256225423691426735932011376256751926687386762108587816483740258699371757433615173305137434119292838712721416785355612250164642843800878962968768192098173866139532824196545174345900695673844077156572039278918984913397930317429787962557294721805738693054179811835717065028952910215615224680053236949692064119797385474426572790113251198730129280310478508674699026563792292928948060895646025882846864383863565586607209169223951') c = 4673035924389272278475077726179721834196795767239453119170003013692946332412255268083504867136759422845861665483227559383954843143670952281969970077731089347972838420010231661960479713394051608043031384693412159099965328507230965509961198520502268922686515047278411684052852995138615616040668732298091594792133478881624324818221814267947449074861355947381041272802241830653539106368971391423458933624515377831472054507217929993173878266225197776099109251511985341724790608910932841987840837417562296646705505719209341249852963919620413828831930283409960629361329433160615299527749956602571547705926320519915041473366 e = 65537 f = round(Decimal('37') / Decimal('13') * Decimal(n) * k) for i in range(-10000, 10000): p = f + i if iroot(p, 2)[1] == True: p = iroot(p, 2)[0] q = n // p print(long_to_bytes(pow(c, pow(e, -1, (p-1)*(q-1)), n))) #b'W1{now_you_know_how_to_use_continued_fraction!}' ``` ::: - Ban đầu code của mình nó không thể tìm ra được giá trị thật sự của p dù đã thử brute-force các khoảng rất lớn xung quanh $f$, sau đó mình mới nhận ra là phải đặt `getcontext().prec = 1337`, điều này sẽ kiến giá trị mặc định của `.prec`(độ chính xác sau dấu phẩy thập phân) là 28 lên đến 1337, nếu không tăng `.prec()` lên thì $f$ nó sẽ rất xa giá trị $p^2$, do đó gần như không thể brute-force ### war(sa)mup ::: spoiler chall.py ```py= from Crypto.Util.number import getStrongPrime, GCD, long_to_bytes import os flag = b"zer0pts{warm_up_rsa}" def pad(m: int, n: int): # PKCS#1 v1.5 maybe ms = m.to_bytes((m.bit_length() + 7) // 8, "big") ns = n.to_bytes((n.bit_length() + 7) // 8, "big") assert len(ms) <= len(ns) - 11 1 <= len(ms) <= 117 ps = b"" while len(ps) < len(ns) - len(ms) - 3: p = os.urandom(1) if p != b"\x00": ps += p return int.from_bytes(b"\x00\x02" + ps + b"\x00" + ms, "big") while True: p = getStrongPrime(512) q = getStrongPrime(512) n = p * q phi = (p-1)*(q-1) e = 1337 if GCD(phi, e) == 1: break m = pad(int.from_bytes(flag, "big"), n) c1 = pow(m, e, n) c2 = pow(m // 2, e, n) print("n =", n) print("e =", e) print("c1 =", c1) print("c2 =", c2) # n = 113135121314210337963205879392132245927891839184264376753001919135175107917692925687745642532400388405294058068119159052072165971868084999879938794441059047830758789602416617241611903275905693635535414333219575299357763227902178212895661490423647330568988131820052060534245914478223222846644042189866538583089 # e = 1337 # c1 = 89077537464844217317838714274752275745737299140754457809311043026310485657525465380612019060271624958745477080123105341040804682893638929826256518881725504468857309066477953222053834586118046524148078925441309323863670353080908506037906892365564379678072687516738199061826782744188465569562164042809701387515 # c2 = 18316499600532548540200088385321489533551929653850367414045951501351666430044325649693237350325761799191454032916563398349042002392547617043109953849020374952672554986583214658990393359680155263435896743098100256476711085394564818470798155739552647869415576747325109152123993105242982918456613831667423815762 ``` ::: - Hàm `pad` sẽ không làm thay đổi flag nên ta không cần chú ý nhiều, và ta có 2 hệ phương trình sau: - $C_1 \equiv m^e \pmod n$ (1) - $C_2 \equiv (m//2)^e \pmod n$ - Ta có 2 trường hợp: + Nếu m chia hết cho 2, thì m//2 sẽ thật sự là phép chia, lúc này phương trình 2 trở thành $C_2 \equiv m^e. 2^{-e} \pmod n$ <=> $C_2.2^e\equiv m^e \pmod n$. Do đó ta có thể kiểm tra m có là số chẵn hay không bằng cách so sánh $C_1$ có bằng $C_2. 2^e \pmod n$ không + Mình đã so sánh và thấy nó không bằng, do đó ta xét trường hợp thứ 2. Đó là khi m lẻ, lúc này phép m//2 sẽ = $\frac {m-1}{2}$ <=> phương trình 2 trở thành $C_2.2^e \equiv (m-1)^e \pmod n$. Giờ ta thu được 2 đa thức $f_1, f_2$ trên vành $Z_N$, với: - $f1 = m^e - C_1 \pmod n$ - $f2 = (m-1)^e - C_2.2^e \pmod n$. - Ta có thể tìm nghiệm m bằng cách tính $GCD(f_1, f_2)$. :::spoiler solve.py ```py= def poly_gcd(f, g): while g: f, g = g, f % g return f.monic() def gcd_polynomial(n, b, d, c1, c2, e): k = pow(2, e, n) * c2 % n R.<X> = PolynomialRing(Zmod(n)) f1 = (X + b)**e - c1 f2 = (X + d)**e - k g = poly_gcd(f1, f2) return -g.coefficients()[0] n = 113135121314210337963205879392132245927891839184264376753001919135175107917692925687745642532400388405294058068119159052072165971868084999879938794441059047830758789602416617241611903275905693635535414333219575299357763227902178212895661490423647330568988131820052060534245914478223222846644042189866538583089 e = 1337 c1 = 89077537464844217317838714274752275745737299140754457809311043026310485657525465380612019060271624958745477080123105341040804682893638929826256518881725504468857309066477953222053834586118046524148078925441309323863670353080908506037906892365564379678072687516738199061826782744188465569562164042809701387515 c2 = 18316499600532548540200088385321489533551929653850367414045951501351666430044325649693237350325761799191454032916563398349042002392547617043109953849020374952672554986583214658990393359680155263435896743098100256476711085394564818470798155739552647869415576747325109152123993105242982918456613831667423815762 m = gcd_polynomial(n, 0, -1, c1, c2, e) m_int = int(m) flag = m_int.to_bytes((m_int.bit_length() + 7) // 8, byteorder='big') print(flag) # zer0pts{y0u_g07_47_13457_0v3r_1_p0in7} ``` ::: ### integrity :::spoiler chall.py ```py= from Crypto.Util.number import * from binascii import crc_hqx p = getPrime(1024) q = getPrime(1024) n = p*q e = 65537 tot = (p-1)*(q-1) d = pow(e, -1, tot) flag = 100000000000000000000 ct = pow(flag, e, n) #signature = pow(flag, d, n) # no, im not gonna do that signature = pow(flag, crc_hqx(long_to_bytes(d), 42), n) print(f"{n = }") print(f"{ct = }") print(f"{signature = }") ``` ::: - Challenge thay vì tính $signature \equiv m^d \pmod n$ thì lại tính $signature \equiv m^{k} \pmod n$ (với k = crc_hqx(long_to_bytes(d), 42)). - Hoạt động của crc về cơ bản là một phép chia đa thức trong trường nhị phân, đối với crc_hqx thì đa thức sinh của nó là $x^{16} + x^{12} + x^5 + 1$, và nó sẽ sử dụng các phép XOR để tính toán dữ liệu. Và nó sẽ luôn trả về một số nguyên dương k nhỏ hơn 16 bit. Dựa vào challenge thì ta rút ra được 2 phương trình: $$C \equiv m^e \pmod N$$ $$S \equiv m^k \pmod N$$ - Và theo định lý Euclid mở rộng, ta luôn tìm được u, v thỏa $e.u + k.v = gcd(e, k)$. Vậy mình sẽ brute-force tìm k sao cho $S \equiv m^k \pmod N$ và $gcd(e, k) = 1$ (vì như vậy thì $C^u.S^v \pmod N = m$). :::spoiler solve.py ```py= from Crypto.Util.number import long_to_bytes from gmpy2 import gcdext n = 10564138776494961592014999649037456550575382342808603854749436027195501416732462075688995673939606183123561300630136824493064895936898026009104455605012656112227514866064565891419378050994219942479391748895230609700734689313646635542548646360048189895973084184133523557171393285803689091414097848899969143402526024074373298517865298596472709363144493360685098579242747286374667924925824418993057439374115204031395552316508548814416927671149296240291698782267318342722947218349127747750102113632548814928601458613079803549610741586798881477552743114563683288557678332273321812700473448697037721641398720563971130513427 c = 5685838967285159794461558605064371935808577614537313517284872621759307511347345423871842021807700909863051421914284950799996213898176050217224786145143140975344971261417973880450295037249939267766501584938352751867637557804915469126317036843468486184370942095487311164578774645833237405496719950503828620690989386907444502047313980230616203027489995981547158652987398852111476068995568458186611338656551345081778531948372680570310816660042320141526741353831184185543912246698661338162113076490444675190068440073174561918199812094602565237320537343578057719268260605714741395310334777911253328561527664394607785811735 s = 1275844821761484983821340844185575393419792337993640612766980471786977428905226540853335720384123385452029977656072418163973282187758615881752669563780394774633730989087558776171213164303749873793794423254467399925071664163215290516803252776553092090878851242467651143197066297392861056333834850421091466941338571527809879833005764896187139966615733057849199417410243212949781433565368562991243818187206912462908282367755241374542822443478131348101833178421826523712810049110209083887706516764828471192354631913614281317137232427617291828563280573927573115346417103439835614082100305586578385614623425362545483289428 e = 65537 for k in range(2, 2**16): g, u, v = gcdext(e, k) if g == 1: m = pow(c, u, n) * pow(s, v, n) % n if pow(m, k, n) == s: print(long_to_bytes(m)) # ictf{oops_i_leaked_some_info} ``` ::: ### chinese_rsa :::spoiler chall.py ```py= from Crypto.Cipher import AES from Crypto.Util.number import bytes_to_long, getPrime from Crypto.Util.Padding import pad import os flag = b"byuctf{th1nhph4tn3}" print("[+] Generating values...", flush=True) key = os.urandom(160) p, q, n, e = [], [], [], [] for i in range(3): p.append(getPrime(1024+512*i)) q.append(getPrime(1024+512*i)) n.append(p[i]*q[i]) cipher = AES.new(key[:16], AES.MODE_ECB) print(cipher.encrypt(pad(flag, AES.block_size)).hex()) print("We will encrypt the key three times, and you can even choose the value of e. Please put your distinct e values in increasing order.") try: e = list(map(int, input().split(" "))) assert e[0]>1 assert e[1]>e[0] assert e[2]>e[1] except Exception as e: print("sorry, invalid input") quit() key = bytes_to_long(key) for i in range(3): print(f"n{i}=",n[i], sep="") print(f"c{i}=", pow(key, e[i], n[i]), sep="") ``` ::: - Mình chỉ có file challenge nên sẽ chạy local bài này. - Đầu tiên, sever sẽ sinh ngẫu nhiên 1 key ngẫu nhiên có 160 byte. Sau đó mã hóa flag bằng AES-ECB với 16 byte đầu của key. - Ngoài ra, challenge còn cho ta chọn khóa e nhưng với điều kiện: ```py= e[0]>1 e[1]>e[0] e[2]>e[1] ``` - Ta sẽ tập trung khai thác lỗ hỏng dựa trên điều này. - Đầu tiên mình nghĩ ngay đến Hastad Broadcast attack, nhưng để attack kiểu này thì ta các m trong hệ phương trình đồng dư của ta phải được mã hóa chung một e, nhưng ở đây ta chỉ có thể chọn e khác nhau. - Sau đó mình có suy nghĩ là ta vẫn có thể "chuẩn hóa" các e thành một E nào đó, miễn là ta có thể giải được hệ phương trình đó là được. - Cụ thể, ta thu được 3 phương trình: - $C_1 \equiv m^{e_1} \pmod {n_1}$ $C_2 \equiv m^{e_2} \pmod {n_2}$ $C_3 \equiv m^{e_3} \pmod {n_3}$ - Chuẩn hóa về cùng 1 E: - $C_1^{\frac {E} {e_1}} \equiv m^{E} \pmod {n_1}$ $C_1^{\frac {E} {e_2}} \equiv m^{E} \pmod {n_2}$ $C_1^{\frac {E} {e_3}} \equiv m^{E} \pmod {n_3}$ - Giải hệ này ta sẽ thu được $M$ với $M \equiv m^E \pmod N$ (với $N = n_1.n_2.n_3$). - Từ phương trình này, ta rút ra 2 điều kiện về E để có thể tính được m: + $m^E < N$. mà $m$ = 160 byte = 1280 bit. Còn $n_1.n_2.n_3$ lần lượt = 2048, 3072, 4096 bit. Vậy $E < \frac {2048.3072. 4096 } {1280}$, suy ra $E < 7$ + $E$ phải chia hết cho $e_1, e_2, e_3$. Hay nói cách khác $E$ phải là bội chung nhỏ nhất của $e_1, e_2, e_3$ ($E = lcm(e_1, e_2, e_3$). Với $1 < e_1 < e_2 < e_3$ - Kết hợp tất cả các điều kiện đó lại với nhau thì ta chỉ có được 1 bộ ba $e_1, e_2, e_3$ thỏa đó là {2, 3, 6}, ($E = lcm(2, 3, 6) = 6$). - Đến đây ta chỉ cần CRT rồi sau đó tính m = $\sqrt[6]{M}$, chuyển m về byte rồi lấy 16 byte đầu của nó để giải AES, ta sẽ thu được flag. :::spoiler solve.py ```py= #!/usr/bin/env python3 from pwn import process from Crypto.Cipher import AES from Crypto.Util.Padding import unpad from Crypto.Util.number import long_to_bytes from gmpy2 import iroot def crt(n_list, c_list, e_list, E): N = 1 ans = 0 for n in n_list: N *= n for n, c, e, in zip(n_list, c_list, e_list): ans += c**(E//e) * pow(N//n, -1, n) * N//n return ans % N p = process([ "python", "server.py" ]) p.recvline() aes_hex = p.recvline().strip().decode() aes_bytes = bytes.fromhex(aes_hex) p.recvline() p.sendline(b"2 3 6") n_list = [] c_list = [] for i in range(3): line = p.recvline().decode().strip() n = int(line.split("=")[1]) n_list.append(n) line = p.recvline().decode().strip() c = int(line.split("=")[1]) c_list.append(c) E = 6 e_list = [2, 3, 6] M = crt(n_list, c_list, e_list, E) key = iroot(M, E)[0] aes_key = long_to_bytes(key)[:16] cipher = AES.new(aes_key, AES.MODE_ECB) flag = unpad(cipher.decrypt(aes_bytes), AES.block_size) print(flag.decode()) p.close() ``` ::: ### oracle :::spoiler chall.py ```python= from Crypto.Util.number import * import os flag = bytes_to_long(b"wgmy{ilovecryptohuhu}") p = getStrongPrime(1024) q = getStrongPrime(1024) e = 0x557 n = p*q phi = (p-1)*(q-1) d = inverse(e,phi) while True: print("Choose an option below") print("=======================") print("1. Encrypt a message") print("2. Decrypt a message") print("3. Print encrypted flag") print("4. Print flag (X)") print("5. Exit") try: option = input("Enter option: ") if option == "1": m = bytes_to_long(input("Enter message to encrypt: ").encode()) print(f"Encrypted message: {pow(m,e,n)}") elif option == "2": c = int(input("Enter ciphertext to decrypt: ")) if c % pow(flag,e,n) == 0 or flag % pow(c,d,n) == 0: print("HACKER ALERT!!") break print(f"Decrypted message: {pow(c,d,n)}") elif option == "3": print(f"Encrypted flag: {pow(flag,e,n)}") elif option == "4": print("(X)") elif option == "5": print("Bye!!") break except Exception as e: print("HACKER ALERT!!") ``` ::: - Challenge cho ta 5 option, ta chỉ quan tâm 3 option đầu tiên. - `Option 1` sẽ cho phép ta gửi message bất kỳ để encrypt nó. - `Option 2` thì sẽ cho ta decrypt `C` nào đó. Nhưng `C` phải thỏa điều kiện `c % pow(flag,e,n) != 0 or flag % pow(c,d,n) != 0`. - `Option 3` dùng để nhận ciphertext. - Hướng giải: - Bài này ta không thể dùng kiểu blinding attack như thông thường là gửi $C'$ đến sever để qua mặt với $C' \equiv C.r^e \pmod N$. Vì sever đã kiểm tra là $C'$ nào đó gửi đến nó không được là một bội của $C$. Mặt khác ta cũng không thể gửi đến $C$ nào đó mà sau khi mã hóa ra m nó là một ước của flag. - Vậy ta sẽ dùng một chiến thuật tinh vi hơn đó là gửi $C'$ sao cho $C' \equiv C.r^e + k*N \pmod N$. (với k là số nguyên). Khi ta cộng theo $k*N$ vào $C'$ thì $C'$ lúc này nó không còn là một bội của $C$ nữa, và đồng thời khi giải mã thì $k*N \equiv 0 \pmod N$ nên ta sẽ thu được $m' = m.r^e$. - Nhưng lại xuất hiện thêm 1 vấn đề nữa là ta không biết giá trị của N. Challenge chỉ cho ta e thôi, vậy ta phải tận dụng `Option 1` nữa. Vậy tìm $N$ từ đó như thế nào. - Giả sử ta có 2 ciphertext $C_1, C_2$ với: - $C_1 \equiv m_1^e \pmod N$ $C_2 \equiv m_2^e \pmod N$ - Tương đương: - $C_1 - m_1^e = i.N$ $C_2 - m_2^e = j.N$ - Vậy ta chỉ cần lấy $gcd(C_1 - m_1^e, C_2 - m_2^e)$ thì sẽ thu được $N$. Có $N$ rồi thì ta tiến hành blinding attack :::spoiler solve.py: ```py= from Crypto.Util.number import * from pwn import process import os from math import gcd p = process(["python", "chall.py"]) m_list, c_list = [], [] e = 0x557 n = 1 r = 2 menu = p.recvuntil(b"Enter option: ") while n == 1: p.sendline(b"1") p.recvuntil(b"Enter message to encrypt: ") random_m = os.urandom(60) random_m_text = random_m.hex().encode() p.sendline(random_m_text) p.recvuntil(b"Encrypted message: ") enc = int(p.recvline().strip()) m_list.append(bytes_to_long(random_m_text)) c_list.append(enc) if len(m_list) > 2: n = gcd(c_list[-1] - m_list[-1]**e, c_list[-2] - m_list[-2]**e) p.sendline(b"3") p.recvuntil(b"Encrypted flag: ") c = int(p.recvline().decode().strip()) p.sendline(b"2") p.recvuntil(b"Enter ciphertext to decrypt: ") p.sendline(str(c*pow(r, e, n) + n).encode()) p.recvuntil(b"Decrypted message: ") m = int(p.recvline().decode().strip()) flag = long_to_bytes(m//r) print(flag) p.close() ``` ::: ## HARD ### Qu4dr4t1c :::spoiler chall.py ```py= from Crypto.Util.number import * e = 65537 flag = b'KCSC{s0m3_r3ad4ble_5tr1ng_like_7his}' def reverse(n):{ #function to reverse binary of n } while True: p = getPrime(1024) q = inverse(e, p) if not isPrime(q): continue n = p * q cipher = pow(bytes_to_long(flag),e,n) n = reverse(n) f = open('output.txt','w') print(f"N = {n}",file=f) print(f"e = {e}",file=f) print(f"Cipher = {cipher}",file=f) ``` ::: - Challenge sinh `p` ngẫu nhiên nhưng tính $q \equiv e^{-1} \pmod p$. Ta biến đổi phương trình này lại thành $q.e = 1 + k.p$ - Ta có $N = p.q$ nên $N.e = p.q.e = p(1 + k.p) = p + k.p^2$. Vậy ta đã rút ra được phương trình $N.e = p + k.p^2$, ta có thể viết nó lại thành một phương trình bậc 2: $k.p^2 + p - N.e = 0$. Phương trình này có 2 nghiệm, nghiệm dương của nó sẽ có dạng: $p = \frac{-1 + \sqrt{1 + 4.k.N.e}}{2k}$. Ta có thể brute-force cho đến khi $p$ là một nghiệm nguyên dương. - Ta còn phải xử lý một vấn đề nữa là các bit của N đã bị đảo ngược, ví dụ $N = 0b10010$ thì challenge đảo thành $N = 0b01001$. Mình sẽ dùng các tính chất đặc biệt của các toán tử bit để đảo bit N: ```py= def reverse(N, bit_len): res = 0 for _ in range(bit_len): res = (res << 1) | (N & 1) N >>= 1 return res ``` - Giải thích. Ví dụ $N$ lúc đầu = $0b0101$. ta đặt $res = 0$, với mỗi bit của $N$ thì ta sẽ dịch trái bit của res qua trái 1 lần (để có chỗ trống chèn bit cuối của $N$ vô). ($N$ & 1) sẽ trả về bit cuối của $N$, vì số nào & 1 cũng trả về chính nó. sau đó ta chèn bit cuối của $N$ vô bằng phép OR với bit cuối của res (lúc này là 0). mỗi lần thực hiện ta sẽ "xóa" bit cuối của $N$ bằng phép dịch phải $N$ đi 1 đơn vị. :::spoiler solve.py: ```py= from Crypto.Util.number import * from gmpy2 import iroot def reverse(N, bit_len): res = 0 for _ in range(bit_len): res = (res << 1) | (N & 1) N >>= 1 return res N = 13524733362044232010736349595937464796777752381282044858904535549598695415259485540306280531287404403541039855661018351433654227342950710134306170544748441173774593898898768923907735212448495520658645896437678387670188401560165044043577269969416130117140222729708904953465161496726313677920240975640999580444678641072701612002184731572732086781180661428229265121878536891979130796853074814897843058889565035037987946761236280609366824566706376823708457581218333217098354233306312287549927586100725051273954453617494755601749327688591032955254157726764321151877093977335572150146339853526534429133266975640029987854181 e = 65537 c = 3678620397255743852788853741107986108860981676309723331641730290544731009447106060307185476663548386172571801713658668783790148410569386488760778490944114348420614589196065297281576228195492339713201469195237426515519163981864121592862248581092535664172672153903696701157467812876812796524706730400133900257530235932000707810825149259236944828592989457788651053131965278448678769098840150302476398856999420129829083563611916558475165369663734941095660119099130765405955767410469621006246831917091632524062249541513097151767121519911807673852738866453379562168834013804186606786287157327927655505568604704262776577804 N = reverse(N, N.bit_length()) k = 1 p = 0 while k < e: delta = 1 + 4*k*N*e if iroot(delta, 2)[1] and (-1 + iroot(delta, 2)[0]) % (2*k) == 0: p = (-1 + iroot(delta, 2)[0]) // (2*k) break k += 1 print(long_to_bytes(pow(c, inverse(e, (p-1)*(N//p-1)), N))) # KCSC{1f_D4m14n_g3t_m4rr13d_w1th_4ny4,th3_34st_4nd_th3_W3st_w1ll_b3_p34c3ful!!!!} ``` ::: ### war(sa)up - Đã làm ở medium ### zoltraak :::spoiler chall.py: ```py= from Crypto.Util.number import * FLAG = b'KCSC{???????????????????????????????????????}' m = bytes_to_long(FLAG) p = getPrime(512) q = getPrime(512) n = p * p * q e = 0x10001 d = inverse(e, p * (p-1) * (q-1)) assert m < n c = pow(m, e, n) hint = pow(d, e, n) print(f'c = {c}') print(f'hint = {hint}') print(f'n = {n}') """ c = 216895836421936226664808806038131495725544658675106485670550453429609078893908601117272164909327632048129546753076380379045793859323244310633521321055388974634549104918284811813205866773238823220320222756056839297144222443834324484452750837978501262424186119512949111339142374067658940576220209924539508684423305539352188419127746551691195133913843198343764965016833190033138825402951884225991852311634388045499747652928427089105006744062452013466170009819761589 hint = 119347490709709918515362500613767389632792382149593771026067086829182731765211255478693659388705133600879844115195595226603111752985962235917359759090718061734175658693105117154525703606445141788266279862259884063386378441258483507592794727728695131221071650602175884547070684687593047276747070248401583807925835550653444240529379502255688396376354105756898403267623695663194584556369065618489842778593026855625193720218739585629291162493093893452796713107895772 n = 947166029378215681573685007119017666168984033297752775080286377779867377305545634376587741948207865073328277940177160532951778642727687102119230712410226086882346969888194915073996590482747649286982920772432363906920327921033567974712097884396540431297147440251083706325071265030933645087536778803607268099965990824052754448809778996696907531977479093847266964842017321766588821529580218132015882438704409614373340861025360688571007185362228026637160817305181421 """ ``` ::: - Chall tạo $n = p.p.q$, và dựa vào chall ta rút ra được 2 phương trình sau: - $d \equiv e^{-1} \mod(p.(p-1)(q-1))$ (1) - $hint \equiv d^e \mod n$ (2) - Thế (1) vào (2): - $hint \equiv (e^{-1} \mod p.(p-1)(q-1))^e \mod n$. - Rút gọn module ta được: - $hint \equiv (e^{-1} \mod p.)^e \mod p$ - $hint.e^e - 1 \equiv 0 \mod p$ - Vậy ta có thể lấy $gcd(hint.e^e - 1, n)$ sẽ được $p$. Từ đó tính được $d$ và tìm ra flag. :::spoiler solve.py: ```py= from math import gcd from Crypto.Util.number import long_to_bytes from gmpy2 import iroot c = 216895836421936226664808806038131495725544658675106485670550453429609078893908601117272164909327632048129546753076380379045793859323244310633521321055388974634549104918284811813205866773238823220320222756056839297144222443834324484452750837978501262424186119512949111339142374067658940576220209924539508684423305539352188419127746551691195133913843198343764965016833190033138825402951884225991852311634388045499747652928427089105006744062452013466170009819761589 hint = 119347490709709918515362500613767389632792382149593771026067086829182731765211255478693659388705133600879844115195595226603111752985962235917359759090718061734175658693105117154525703606445141788266279862259884063386378441258483507592794727728695131221071650602175884547070684687593047276747070248401583807925835550653444240529379502255688396376354105756898403267623695663194584556369065618489842778593026855625193720218739585629291162493093893452796713107895772 n = 947166029378215681573685007119017666168984033297752775080286377779867377305545634376587741948207865073328277940177160532951778642727687102119230712410226086882346969888194915073996590482747649286982920772432363906920327921033567974712097884396540431297147440251083706325071265030933645087536778803607268099965990824052754448809778996696907531977479093847266964842017321766588821529580218132015882438704409614373340861025360688571007185362228026637160817305181421 e = 0x10001 p = gcd(hint*(e**e) - 1, n) q = n // (p*p) d = pow(e, -1, p*(p-1)*(q-1)) print(long_to_bytes(pow(c, d, n))) ``` ::: ### Really Simple Algorithm :::spoiler chall.py ```python= from Crypto.Util.number import getPrime, bytes_to_long as btl menu = '''(1) Encrypt Message (2) Receive Flag (3) Exit''' e = 1337 size = 1024 flag = open('flag.txt', 'r').read().rstrip() print('Welcome to the L3ak Really Simple Algorithm (RSA) Encryption Service™!') print('Here you can encrypt your own message, or choose to receive the encrypted flag.') print('Good luck!\n') while True: p, q = getPrime(size), getPrime(size) n = p*q print(menu) option = int(input('Select Option: ')) if option == 1: message = btl(input('Your Message: ').encode()) enc_msg = pow(message, e, n) print(f'n = {n}') print(f'c = {enc_msg}') elif option == 2: enc_flag = pow(btl(flag.encode()), e, n) print(f'n = {n}') print(f'flag = {enc_flag}') elif option == 3: print('Goodbye!') exit() else: print('Invalid choice! Please try again.') ``` ::: - Challenge cho ta chọn 3 option, option 1 cho phép ta gửi một plaintext ngẫu nhiên để nhận được ciphertext tương ứng, option 2 thì ta sẽ nhận được ciphertext của flag. - Điểm đặc biệt là mỗi lần ta gửi option thì N đều được sinh ngẫu nhiên tiếp, ta có thể lợi dụng điều này để thực hiện Hastad broadcast attack. Nhưng để thực hiện được thì ta phải gửi đi 1337 lần (số lượng phương trình phải lớn hơn hoặc bằng e). :::spoiler solve.py ```python= from pwn import process from Crypto.Util.number import long_to_bytes from sympy.ntheory.modular import crt import sys from gmpy2 import iroot e = 1337 c_list, n_list, m_list = [], [], [] p = process([sys.executable, "chall.py"]) while len(c_list) < e: p.recvuntil(b"Select Option: ") p.sendline(b"2") n = p.recvline().decode().strip().split("=")[1] c = p.recvline().decode().strip().split("=")[1] c_list.append(int(c)) n_list.append(int(n)) print(len(c_list)) M = crt(n_list, c_list)[0] m = iroot(M, e)[0] print(long_to_bytes(m).decode()) p.close() ``` ::: ### noreply :::spoiler chall.py: ```py= # reply2000 from Crypto.Util.number import getPrime, long_to_bytes, bytes_to_long # Install pycryptodome FLAG = b"HCMUS-CTF{?????????????????????????????????????????}" # Alice and Bob communicated in 2000s. # Alice # usual stuff p = getPrime(1024) q = getPrime(1024) n = p*q phi = (p-1)*(q-1) print(f"{n = }") # Alice has 2 public keys e1 = 2000 e2 = 2**16 - 1 # Bob sends Alice his message. m = bytes_to_long(FLAG) print(m) ct1 = pow(m, e1, n) ct2 = pow(m, e2, n) print(f"{ct1 = }") print(f"{ct2 = }") # n = 14522345803952951497854746956950429925714998568959329105863205708689185597355859293717114187773682087437056115503976819640144002239462632711502747866637932043366614821903920862363899959984636870000958750750983419968182435497432639514942413700204282567496628406198010952659927828472035115659189681437243789047864734407874916017869024955600036417945382400990673953014525661178396128073261668494708827415945567280112878906126975987081420301162844731698144544717058251742983595736398008606258830677240405674609798045982586017662281175658509107812545104789242101547411016679842609143686612094846357997607098036946974159819 # ct1 = 12958994082704767729467983847493496476733123307172725452599822036951998238786745372306618183705966866053277246395468894482018535285184465501335591787791271667293966714564083791660333011817260068079774626208592964305668430077934263170152882723315221366045071199710220968120091402625656555934987730796571335135115758245436948062739057773179532373894660922324274780874057755144707362741815760933346845021294047019594881090300645470053730942117695366916034416583835532585436841922821179783068343849309001079323991717401395244377500867312117772043738986178913742296865573482074215514303359431554569689122135538844236034237 # ct2 = 2113955544726990374545779358207294597126721958718803911158090276756063442389261656290989563782057417086282692034192325485313160125992822058842573479431969990730642851863191934094456673766166782888440264483490938748223953235410415079609742387917395625451363712731611383025449692145904580587799693041297852615026482837269275327958049359681162578625623923739849463589046962684491436964915263151468696220639361192823823768748471318446445269025418833128898006657253602421656068778255337952139751340290625845534830716895274546516497219657845581365268163620764154310717952199701486367227114583121809542836138920790167864853 ``` ::: - Bài này là dạng Common Modulus Attack, vì c được mã hóa với 2 e khác nhau. Nhưng nếu ta làm như cách thông thường là tìm gcd($e_1$, e_2) thì nó ra 5. lúc này $C_1^u.C_2^u = m^5 \pmod N$ Nên ta phải brute-force căn đúng của $m^5 \pmod N$ nữa. :::spoiler solve.py: ```py= from math import gcd from gmpy2 import * from Crypto.Util.number import * n = 14522345803952951497854746956950429925714998568959329105863205708689185597355859293717114187773682087437056115503976819640144002239462632711502747866637932043366614821903920862363899959984636870000958750750983419968182435497432639514942413700204282567496628406198010952659927828472035115659189681437243789047864734407874916017869024955600036417945382400990673953014525661178396128073261668494708827415945567280112878906126975987081420301162844731698144544717058251742983595736398008606258830677240405674609798045982586017662281175658509107812545104789242101547411016679842609143686612094846357997607098036946974159819 ct1 = 12958994082704767729467983847493496476733123307172725452599822036951998238786745372306618183705966866053277246395468894482018535285184465501335591787791271667293966714564083791660333011817260068079774626208592964305668430077934263170152882723315221366045071199710220968120091402625656555934987730796571335135115758245436948062739057773179532373894660922324274780874057755144707362741815760933346845021294047019594881090300645470053730942117695366916034416583835532585436841922821179783068343849309001079323991717401395244377500867312117772043738986178913742296865573482074215514303359431554569689122135538844236034237 ct2 = 2113955544726990374545779358207294597126721958718803911158090276756063442389261656290989563782057417086282692034192325485313160125992822058842573479431969990730642851863191934094456673766166782888440264483490938748223953235410415079609742387917395625451363712731611383025449692145904580587799693041297852615026482837269275327958049359681162578625623923739849463589046962684491436964915263151468696220639361192823823768748471318446445269025418833128898006657253602421656068778255337952139751340290625845534830716895274546516497219657845581365268163620764154310717952199701486367227114583121809542836138920790167864853 e1 = 2000 e2 = 2**16 - 1 g, u, v = gcdext(e1, e2) M = pow(ct1, u, n) * pow(ct2, v, n) % n k = 0 while True: if iroot(M + k*n, g)[1] == True: print(long_to_bytes(iroot(M + k*n, g)[0])) break print(k) k +=1 ``` ::: ### a_little_rsa :::spoiler chall.py ```python! from Crypto.Util.number import * p = getPrime(225) q = getPrime(1024) n = p*q phi = (p-1)*(q-1) # e = 0x10001 nah i wont choose this e e = pow(p, -1, phi) m = b"HUTECHCTF{?????????????????????}" c = pow(bytes_to_long(m), e, n) print(f"{n = }") print(f"{e = }") print(f"{c = }") # n = 5556369470452763001820995400343197157881225256466459471266947042857859221436868226999883166837636079989051971281740453000522522318458883517943008269265976364488734185791746486253297012852675437707711425510743320700302443844988537297588120145526952818833842183731495837445197199126781269287892288815748800736516819862248407728112529942064511813068245715261534163060369753903477 # e = 2821451964839154368120355125521441683447698420101739611869753703735023988667052593422844018719345959808708061053551730361466879351905608000370153314148352231127182530625251231728840798469202860164833424204081656024425220775376047588258744154510324007016843143772305062316764527767975757836191060491803955215361562401454158664942149294190741313368539099967880840186625474961731 # c = 5246932780619400297520625573328767417031234540567446402388345313285954715314864844597047027908845692631360790313020857940733222636101148405784137813245133418351478678755948432358373630693543578809099352314292987399977109948624098749477326271010582974794896556549863741961222783274164717707961078869751264399342702980687345149913008415919007870052304096963467094561767044922702 ``` ::: - Challenge tính $e = p^{-1} \pmod {\phi(N)}$ - Dựa vào đây ta có thể khai thác lỗ hỏng và tính được $p$. - Ta có thể viết lại phương trình ban đầu đó thành: $e \equiv p^{-1} \pmod{p-1}$ <=> $e.p \equiv 1 \pmod{p-1}$ mà $p \equiv 1 \pmod {p-1}$, nên $e \equiv 1 \pmod {p-1}$=> $e - 1 = k.(p-1)$ (*) - Theo định lý nhỏ Fermat , với p là số nguyên tố và $gcd(a, p)$ khác 1 thì $a^{p-1}-1 \equiv 0 \pmod p$. Vậy ta sẽ lấy: $a^{e-1} - 1 = a^{k.(p-1)} - 1 = (a^k)^{p-1} -1\equiv 0 \pmod p$. - Giờ ta chỉ cần lấy $gcd(a^{e-1} - 1, N)$ thì sẽ tìm được nhân tố chung là $p$. Nhưng $e$ trong challenge này rất lớn, ta phải lấy $a^{e-1} - 1$ mod đi cho $N$ để có thể tính toán. :::spoiler solve.py: ```py= from Crypto.Util.number import long_to_bytes from math import gcd n = 5556369470452763001820995400343197157881225256466459471266947042857859221436868226999883166837636079989051971281740453000522522318458883517943008269265976364488734185791746486253297012852675437707711425510743320700302443844988537297588120145526952818833842183731495837445197199126781269287892288815748800736516819862248407728112529942064511813068245715261534163060369753903477 e = 2821451964839154368120355125521441683447698420101739611869753703735023988667052593422844018719345959808708061053551730361466879351905608000370153314148352231127182530625251231728840798469202860164833424204081656024425220775376047588258744154510324007016843143772305062316764527767975757836191060491803955215361562401454158664942149294190741313368539099967880840186625474961731 c = 5246932780619400297520625573328767417031234540567446402388345313285954715314864844597047027908845692631360790313020857940733222636101148405784137813245133418351478678755948432358373630693543578809099352314292987399977109948624098749477326271010582974794896556549863741961222783274164717707961078869751264399342702980687345149913008415919007870052304096963467094561767044922702 a = 2 p = gcd(pow(a, e - 1, n) - 1, n) q = n//p d = pow(e, -1, (p-1)*(q-1)) print(long_to_bytes(pow(c, d, n))) # HUTECHCTF{RSA_s0_ezzzzzz,right?} ``` ::: ### hear_break :::spoiler chall.py: ```python= from Crypto.Util.number import getPrime, bytes_to_long FLAG = "W1{???}" FLAG_PART1, FLAG_PART2 = FLAG[:len(FLAG)//2], FLAG[len(FLAG)//2:] f = open("output.txt", "w") def part1(): p = getPrime(2048) q = getPrime(2048) e = 0x10001 n = p * q d = pow(e, -1, (p-1)*(q-1)) m = bytes_to_long(FLAG_PART1.encode()) c = pow(m, e, n) f.write("ct = " + str(c)) hints = [p, q, e, n, d] for _ in range(len(hints)): hints[_] = (hints[_] * getPrime(1024)) % n if hints[_] == 0: hints[_] = (hints[_] - 1) % n f.write("\nHints = " + str(hints) + "\n") def part2(): e = getPrime(10) p = getPrime(256) q = getPrime(256) n = p * q # print(e) m1 = bytes_to_long(FLAG_PART2.encode()) m2 = m1 >> 8 c1, c2 = pow(m1, e, n), pow(m2, e, n) f.write(f"n = {n}\nc1 = {c1}\nc2 = {c2}\n") if __name__ == "__main__": part1() part2() ``` ::: - Challenge chia flag ra làm 2 phần, part1 là nữa đầu của flag, part2 là nữa sau. - Ta sẽ phân tích phần 1: ```python= def part1(): p = getPrime(2048) q = getPrime(2048) e = 0x10001 n = p * q d = pow(e, -1, (p-1)*(q-1)) m = bytes_to_long(FLAG_PART1.encode()) c = pow(m, e, n) f.write("ct = " + str(c)) hints = [p, q, e, n, d] for _ in range(len(hints)): hints[_] = (hints[_] * getPrime(1024)) % n if hints[_] == 0: hints[_] = (hints[_] - 1) % n f.write("\nHints = " + str(hints) + "\n") ``` - Ban đầu mảng `hints = [p, q, e, n, d]`. Sau đó mỗi phần tử sẽ bằng chính nó nhân với 1 số nguyên tố 1024 bit bất kỳ rồi mod đi cho n. Nếu sau khi đã tính toán, `hints[i]` nó có giá trị là 0 thì `hints[_] = (hints[_] - 1) % n` = (0 -1) % n = n - 1. - Mình suy nghĩ về trường hợp `hints[_] == 0`, và nhận ra rằng chỉ có 1 trường hợp mà hint[_] trả về 0. đó chính là `hints[_] = (n * k) % n`. Vậy nên để tìm n thì ta chỉ cần lấy `hints[3] + 1`. - Bên cạnh đó, với `hints[0] = (p * k) % n`. Ta có thể viết lại là $hints[0] \equiv p.k \pmod p$ (vì $p|n$). <=> $hints[0] = p.k + i.p = p(k + i)$ Vậy $gcd(hints[0], n) = gcd(p(k + i), p.q) = p$. - Tìm được $p$ sẽ tìm được $q, \phi(n), d$ và sẽ tính được phần 1 của flag. Giờ ta tiếp tục với part2: ```python= def part2(): e = getPrime(10) p = getPrime(256) q = getPrime(256) n = p * q # print(e) m1 = bytes_to_long(FLAG_PART2.encode()) m2 = m1 >> 8 c1, c2 = pow(m1, e, n), pow(m2, e, n) f.write(f"n = {n}\nc1 = {c1}\nc2 = {c2}\n") ``` - Có thể xác định luôn là Franklin-Reiter attack vì ta có 2 thông điệp m1, m2 được mã hóa chung một $e, n$. - Giờ ta phải tìm cách biểu diễn m2 theo m1 (hoặc ngược lại). Biết rằng `m2 = m1 >> 8`. Đây là phép dịch bit sang phải 8 lần, nó sẽ tương đương với $m2 = \left\lfloor \frac{m1}{2^8} \right\rfloor$ (chia nguyên làm tròn xuống), hay $m1 = 2^8.m2 + r$, viết lại theo m2 trên vành $Z_N$ ta được $m2 = pow(2^8, -1, N)(m1 - r)$. - Ta lập được hai đa thức $f_1, f_2$ với: $$ \begin{aligned} f_1 &\equiv m_1^e - c_1 \pmod N \\ f_2 &\equiv [\mathrm{pow}(2^8, -1, N)*(m_1 - r)]^e \pmod N \end{aligned} $$ - Tính gcd của 2 đa thức này sẽ tìm được nghiệm chung $m_1$. Nhưng có 1 vấn đề là ta không biết $e$ cũng như không biết $r$, nên sẽ phải brute-force cả 2 giá trị. :::spoiler solve.py ```sage= from Crypto.Util.number import * from math import gcd from sympy import primerange def poly_gcd(f, g): while g: f, g = g, f % g return f.monic() c_part1 = 239991743627005761506047553716973180857493049128968395824678613535924041735819278721655197652704368009118731671080782572692443257002266295841054097811995343407149181564647568019524547331554506022380795516159222363510661688595308307174873885160951837722610012918052195448795081291878933355634383798002056753336540546915811592763747343189324926404600658482137848658910189331650916354541907427173491308413908173314104508974384232290785538938623142120477030045742266779693627293755590884412082209151425384896460777577066084111556036719259982254175935197376972307183776259868229411302259648873045160120795060467866459055693698198316577983136619062944244317116994863470942099523485902299419458583301056211340627830237050622364646501838811516544340499168319955128200158195905283972429746772105746244910156671549456233908152186037286726530314472293814226978595268877619521165090870514287104577960355240428728213124348138646047728851553209042359051265045752603864312856768918350064549850618348693037041311112677351368226231458377933846664981185928405481697006968220556167073996713389716367133156065980195285148700027809062253416860922839857907535460170132744912543758918516134641462581544039400881675553681819294266618981791250077585566821053 hints = [1659380349228980310793195740551091998951133377142727433181233112954301485314646349955561783455759149036476737520702967988760310760312391176774501840210477308343796277178701715703164651184747756453236376960884981254635386807663657355175214655034193946682205904113897156938926175413312324159809831274187894029251371896829385517428693915588566248998565348483747234270329027561433356156355227738138379418717200316600111392671357267757409316691191187929104999221832963378673907868493499459459256894553552195468110517716115678897171373484791903085022119845347228569870830569321957438966030560930098761455953418479618027428739560761186901956751224602703471828674970337530768801203531827467185690264637238603523292728974955840936711823826949100349569805942227432262275344597592991937770320032450419910426614638156263968483514069904464463402987714698220412063100772910040673056263954301063853666792319306234733964442731206579494701823, 2473062479389297534384652365580702456631745761133091301459488546735676124432184165907268360691972078275036508838070797476235444908532100862886958054816201240359777405719375503276188588243722655521225159899315126844306119104997283731460041142142861614319514182297180409656236066011186834375282437648078334082114411988739789392926471318552017202390239258487258487037639778148532362214152519137264282830808294108610004403460587358629486534247288993860831438267841520573973916758902637404855712721811250301202405252158590233975917681798839166192235032424495289048875626437256513981936177292903742966118351026329401662519672777610159422234703124064225710846129876359778079390437505753932101501472252131924073957349012610362952003934494293369977045255000415066563914471132856401071867358687200638320541179048296074882945411664474157308113874183763200469775985802906031999934356545932354932945475129644344782759659758587119586377699, 10811389778781749507848369001995006527965136627134898173336798777178617924322548317218123003648199959431162146218350234488676047952720517043381973357960494027353001493321216082118308994614655309535481054291078777020047697030175144901965025751169815034274454689657181813765988172412194436669592236745329922983348687, 302270795345262652787049603034608860428203534578338699389744017410286806560707153186173595970011317749221953776227374491075684575774328458397778789729965544452010822737225229627108698874874960910965283322537095645241316756015118860396297708799504427117968454341778975073542738740964812664233075630257595196115893498655587491091126391722042679460013562303363850840912825755508680428829444388842951146482726568654418889598972824414109879370032604627990857015975495697530048397401132619555923308480516678981072029040306410523264480829688927798146165580384683689546853438820269495274502502143436234210825345362323042888891473423488116618918996618482754420372481893339222050268599796400452566639228520072261554594477336671016198833620427171498256007475831231524217372147783123617237105584613811522861590112133798309937116024168109605161059186745904038968516182034441583819409524470833832445513001764653452246905494902592731421744692331296978104865554556383417129664683066891729999411036376957753554228948901872115141778394712481069999501808719302346670855531871069366050528261442730651167165455031776639195754458920584910014448480393554851269958179362536781346169282601003523441289868134223507188615919092337658908484201829621953970243126, 292884935929549246643624576832991010496540593142708150947518571090956754050658797955786741707549303442499542376031718493862827439931968289137063776270385766876597819025272388601563339731026897291119786098658019861515084557432779618732711248671531045529170282246847559014298960824095511448557742476351035447816620523706582563446012744989424367197536652910056457067991830630881476241325631891896455745762634189112349619740103725259844111996043190764424736601828139403024375351372351763169837210283497390177391509068689722596094161210899552103572279045474893618035695053640281885367691987326728488743356438444158731410968935525788220429173044772188634219137052045984284351149340419125628533953328666109489959225736888258255952666488686965689900369280599239198825803111830614815595803322570878359992207842211026468967074229662081167123002174445268278747577520774432781623852071789431202030569577689851124794177654088403580945598530502231516822280930459410373890257129917535480957183190120541342731664708767982764672591340622307503858396934095635519503588136203556304925670734741505400274178108097309035870578129722954864083937813328351751442713938490297629659866083082398939022316220801556516785394083566880368038684968532814902807429836] n_part1 = hints[3] + 1 p_part1 = (gcd(hints[0], n_part1)) e_part1 = 0x10001 d_part1 = pow(e_part1, -1, (p_part1 - 1)*(n_part1//p_part1 - 1)) flag_1 = (long_to_bytes(pow(c_part1, d_part1, n_part1))).decode() n_part2 = 3942322022657678598973964668297464188690492529227912763243818849286024502988170927049337618748813366973108404930787214396933140242919629931061653981563183 c1 = 711628464933911477721875076362382562533209928505813633932265201230108117662370018036520970813120568151605229871541865330790006742825947411425842775387464 c2 = 199593868713063917388131306750677766968978918100656918000052209242691143624414286755644005020481267183225454134184719235765273635594459821952870709463733 R.<X> = PolynomialRing(Zmod(n_part2)) flag_2 = "" check = 0 for e in primerange(2**9, 2**10): for r in range(256): f1 = X**e - c1 f2 = (pow(256, -1, n_part2)*(X-r) )**e - c2 g = poly_gcd(f1, f2) if g.degree() == 1: check = 1 m = -g.coefficients()[0] m_int = int(m) flag_2 = long_to_bytes(m_int).decode() break if check == 1: break print(flag_1 + str(flag_2)) ``` ::: ### rsarsarsarsarsarsa :::spoiler chall.py ```py= from math import gcd import os from Crypto.Util.number import getPrime, bytes_to_long e = 19 while True: p = getPrime(2048) q = getPrime(2048) if gcd((p - 1) * (q - 1), e) == 1: break n = p * q flag = os.environ.get("FLAG", "Alpaca{**** REDACTED ****}") assert len(flag) == 26 and flag.startswith("Alpaca{") and flag.endswith("}") m = bytes_to_long((flag * 1337).encode()) c = pow(m, e, n) print(f"{n = }") print(f"{e = }") print(f"{c = }") ``` ::: - Ta nhận thấy m = 1337 chuỗi flag nối với nhau, gọi x là giá trị int của flag, ta có: $$m = x + x.2^{26.8} + x.2^{26.8.2} + x.2^{26.8.3} + ... + x.2^{26.8.1336}$$ - Đặt $A = 2^{26.8}$ ta được: $$m = x + x.A + x.A^{2} + x.A^{3} + ... + x.A^{1336}$$ - Vậy $m = x.\sum_{i=0}^{1336} A^i \;=\;x. \frac{A^{1337}-1}{A-1} = x.S$ - Khi này ta lập được hàm $f(x)$ với: $$f(x) = (S.x)^e - c$$ - Bậc của f(x) = d = 19. Mà để Coppersmith được nghiệm x thì $x < n^{\frac {1}{d}}$. Ở challenge này ta có n = 4096 bit => $n^{\frac {1}{19}} = 2^{\frac {4096}{19}}$ xấp xỉ $2^{215,5}$, còn flag thì 26 byte = 208 bit < $2^{215,5}$ nên sẽ Copersmith được. giá trị $\beta$ sẽ = 0.499 vì $lenbit(p) = lenbit(q)$. :::spoiler solve.py ```py= from Crypto.Util.number import long_to_bytes n = 434245275129793896913302623186216967500119715299127153234221039838158526818290666891561167619572507897277032319251523352710966722158326513857889678449160348496647427753832233179173745189495799707833020232209447520485615893168704144655033371807912826948460011240258726843346618328839282439390863464375320181495406806870462330735361196286553150480225927729088313551861682406252457739974850015509783430978939475350707211461876140420181118923743456062581297038004651412953310377554877499792225388059857865550418697212704277742826280689987165702071346542831836616149138379224837551040036947064990027047482745931141458056028719767845142490618375017582275824317241572815337810658684051187938258804346960781372035972758516593800419459342799854863845667715099378564373594732798224797622583907677749880918106223965727445907355069025939554400938193579295415911074889648122298896605189398591684277376327938718166279159875826993866460251900514487349848332991005775574378131897581182876147580659857596204121970624162722935263271888969020482566142620134100258216288390250174699829806817678453601913377347867137739622906815272561714188564065071077762169177825466514512198167566882661748389120146622447920498988341055543170346944366105037929197965527 e = 19 c = 78338816976998323261765735600063671710448529902850366859501110834174319629348492230679353792803618614020892663940158627385470036549819116375194598599193512981265682997072278631964394686243958989105159463105190885437258093111178664394786430767942639437287236999171486583513816766766869843448941665224796216610702708658300011987744401747551989248270799179750556330952646223694000679475842632497149402602469848595868051660228892506097962300820851000134370939783634534516434054009303981106884637932006844265722691022870174977860945699441650254771777451995160642261482879537396171107016491225773397809485749640163676209732235156461483660111845782227127763086286553520914359194795617080980736767821995556156173267185240945707717461037831992544868933876015548419376861213017988005848033349136839971120363078490938026883354839573512645985195570831018461470031329716026531550172207332072481279548470657090575709419245114386419567236219816237412255505882075283974654569995321334498673793010812162088796252555619242463561750801895032793870706949913548310632113206159695535952422316840587214237406730422405058644629458566515378607614900910335034732797410592671297941526063690060922625005949094383664832255082556088451940780657576420871470920836 q = 2**(8 * 26) s = (pow(q, 1337, n) - 1) * pow(q - 1, -1, n) % n x = PolynomialRing(Zmod(n), 'x').gen() f = ((s*x)^e - c) f = f.monic() root = f.small_roots(X=2^(26*8), beta=0.499) m = root[0] print(long_to_bytes(int(m))) ``` ::: ### Lowkey RSA :::spoiler chall.py ```python= from Crypto.Util.number import * def gen_primes(SIZE): p = random_prime(1 << (SIZE - 1), 1 << SIZE) while True: q = random_prime(1 << (SIZE - 1), 1 << SIZE) if p < q: p, q = q, p if q < p < 2*q: break return p, q nbits = 1024 flag = b"L3AK{<REDACTED>}" R = RealField(nbits) p, q = gen_primes(nbits//2) N = p*q phi = (p**4-1)*(q**4-1) N_s = R(N**2) N_ss = R(N**4) t = (2*N_ss-49*N_s + 2)/(4*N+170*N_s) while True: d = randint(1, round(sqrt(t)) - 1) if gcd(phi-d, phi) == 1: break e = inverse_mod(phi-d, phi) c = pow(bytes_to_long(flag), e, N) print(f"e = {e}\nN = {N}\nc = {c}") ''' e = 370641246943654763647982436393968410523035056803076571952063446221981054741105804986870907803130391736840420704227524827167178043545763070520011423497365360567040835216714988776285676818833967899487393611410406708467049153990487431775151667103817558875154145780446157545062795321820537740212495675608976163877567007753523774447008611976905578477758365862741282887079873779055623972564793977884741350325450634869927603664722967323341473363320613467433998603537242156610765948379449307405122629600556105209482040761323271134932553579828576227233549741862990693111061962892676568398083446001891012661453694340879845386900986024512140441823076068075531089610607812090402852586184229193699718454197060072575595570232588935191272416546819793045623275550409871218062357273309812154110783534714662063322116568964675372602159108306251453500390105034890229052958512010283429459687714879084097494098542745605324460172680461006303552579466987732938596341830436505942616479890554056163452471835707573885837976471753073413505028206370632139586750855217201926605743452826397576584492732225029497982216694648573014796836126574081158869231364821712046050068243878660143909750030922147254462228826952501087389154612318844202411291844150163167021 N = 10222014062768125922601962004686361136447658578111413896046596746110249358112354000488449664371774177977274016313103826803116662735101208575040021998413602496525815373151213550295992813258424882626853824039678993334143891154760939712139640336395595628492284893024078520796288685014103193630287988814952604029 c = 4323184196594280140760873888779221921406692838206184372853784052006066772207175604399047711017170078453742445880600303200397632746051500194774569530024097959399922254605516672962219900174336028512116159752401576376530557036245218800162889461620882177398454137759956927838320086276276377067055171421259852996 ''' ``` ::: - Bài này mình được hint là dùng phân số liên tục, nên mình sẽ tập trung vào khai thác kiểu attack này. - Challenge tính $\phi(n) = (p^4−1)(q^4−1)$, và chọn d ngẫu nhiên $(1\le d\le \lfloor\sqrt{t}\rfloor-1)$. Ta có thể dự đoán $t$ sẽ xấp xỉ $N^2$ vì $t = \frac{2N^4−49N^2+2≈}{4N+170N^2170N2} ≈ \frac{2N^4}{170N2} = \frac{N^2}{85}$. Nên sẽ không thể Wiener được. - e cũng được tính một cách lạ lùng: `e = inverse_mod(phi - d, phi)` => $e \equiv (\phi(N) - d)^{-1} \pmod{\phi(N)}$ Từ công thức này ta rút ra được $$e(\phi(N) - d) = 1 + t\phi(N)$$ $$-e d + e\phi(N) - t\phi(N) = 1$$ $$(e - t)\phi(N) = 1 + ed$$ - Đặt k = e - t ta được: $e.d + 1 = k\phi(N)$ - Từ $e.d + 1 = k\phi(N)$,ta chia cả 2 vế cho $d\phi$ sẽ được. $$\frac{e}{\phi} = \frac{k}{d} - \frac{1}{d\phi}$$ - Ta không biết $(\phi)$ nhưng biết $(\phi = N^4 - (p^4+q^4) + 1)$ sẽ xấp xỉ $N^4$. - $\dfrac{k}{d}$ là một xấp xỉ rất tốt của $\dfrac{e}{\phi}$, sai số đúng bằng $\dfrac{1}{d\phi}$. Khi $\phi$ rất lớn so với $d$, sai số này rất nhỏ, vì thế $\frac{k}{d}$ sẽ xuất hiện trong convergents của phân số liên tục của $\dfrac{e}{\phi}$ (và do $\phi\approx N^4$, ta có thể dùng $e/N^4$ làm xấp xỉ), vậy ta tính các phân số xấp xỉ của $\frac{e}{N^4}$ = $\frac{p_1}{q_1}, \frac{p_2}{q_2}, \frac{p_3}{q_3}, \dots$ với hi vọng rằng một trong số đó = $\frac{k}{d}$ - Việc code tính phân số liên tục sẽ tương đối phức tạp, nên mình dùng 2 hàm `continued_fraction, continued_fraction_convergents` của sympy để tính toán: :::spoiler solve.py ```py= from sympy import Rational from sympy import continued_fraction, continued_fraction_convergents from Crypto.Util.number import long_to_bytes e = 370641246943654763647982436393968410523035056803076571952063446221981054741105804986870907803130391736840420704227524827167178043545763070520011423497365360567040835216714988776285676818833967899487393611410406708467049153990487431775151667103817558875154145780446157545062795321820537740212495675608976163877567007753523774447008611976905578477758365862741282887079873779055623972564793977884741350325450634869927603664722967323341473363320613467433998603537242156610765948379449307405122629600556105209482040761323271134932553579828576227233549741862990693111061962892676568398083446001891012661453694340879845386900986024512140441823076068075531089610607812090402852586184229193699718454197060072575595570232588935191272416546819793045623275550409871218062357273309812154110783534714662063322116568964675372602159108306251453500390105034890229052958512010283429459687714879084097494098542745605324460172680461006303552579466987732938596341830436505942616479890554056163452471835707573885837976471753073413505028206370632139586750855217201926605743452826397576584492732225029497982216694648573014796836126574081158869231364821712046050068243878660143909750030922147254462228826952501087389154612318844202411291844150163167021 N = 10222014062768125922601962004686361136447658578111413896046596746110249358112354000488449664371774177977274016313103826803116662735101208575040021998413602496525815373151213550295992813258424882626853824039678993334143891154760939712139640336395595628492284893024078520796288685014103193630287988814952604029 c = 4323184196594280140760873888779221921406692838206184372853784052006066772207175604399047711017170078453742445880600303200397632746051500194774569530024097959399922254605516672962219900174336028512116159752401576376530557036245218800162889461620882177398454137759956927838320086276276377067055171421259852996 x = Rational(e, N**4) convs = list(continued_fraction_convergents(continued_fraction(x))) for i, frac in enumerate(convs): k = frac.p d = frac.q if k == 0: continue ed1 = e * d + 1 if ed1 % k != 0: continue phi = ed1 // k d_2 = (phi - d) % phi m = long_to_bytes(pow(c, d_2, N)) if b"L3AK{" in m: print(m) break # L3AK{L0wK3y_Th1S_RSA_i5_kiNda_ScuFf3D_LmA0} ``` :::