# Sharif CTF 2016: TPQ

,

$nc ctf.sharif.edu 4000 Our ultra-secure system is generating 10 primes... Done! Please choose options quickly and carefully. Options: [C]hoose two distinct indices to encrypt the flag [R]eveal the encryption function [Q]uit. R def encrypt(m, p, q): e = 65537 return gmpy2.powmod(bytes_to_long(m), e, p*q) C Options: [C]hoose two distinct indices to encrypt the flag [R]eveal the encryption function [Q]uit. Send two distinct indices smaller than 10, separated by space. 0 1 The encrypted flag is: 66342884308702857378588996537492063854217747645145707136158365229718784201687666888851531440948102094050871354281250199051619191417381982677741845572997946131637674939106795454937454594019013552928314626851631427494350520634898214025782887375014485980045023934361110077550243766696785110511318890290534680528 Options: [C]hoose two distinct indices to encrypt the flag [R]eveal the encryption function [Q]uit. C Send two distinct indices smaller than 10, separated by space. 1 2 The encrypted flag is: 57962376138068718677156265868369240598379431839038821639419502376842219140028661549260630737530663282256289760222671917797082802558673532703538843294804844746673528215762295893650110837901698341744673097524364895489313465029261515395092968860404373893907336386124768564654591779445886713573890576800305563053 Options: [C]hoose two distinct indices to encrypt the flag [R]eveal the encryption function [Q]uit. Q Quiting ...  ## solution$c_{i,j} = m^e \bmod p_i p_j$な$c_{i,j}$($0 \le i \lt j \lt 10$)が手に入る。$p$は未知であるので、これを求めたい。 等式$c = m^e \bmod p q$から$\bmod$を除くと、$c = m^e - k p q$。$m^e$を左辺に移して$m^e = c_{i,j} + k_{i,j} p_i p_j$。 これを$2$本用意し合わせると$c + kpq = c’ + k’pq’$。$p$で括ると$c - c’ = p (- kq + k’q’)$。 同様に$c’ - c” = p (- k’q’ + k”q”)$を用意すれば、$p = \gcd(c - c’, c’ - c”)$となり求まる。 このようにして素数をふたつ$p,q$と求めれば、これは秘密鍵であるのでflagが復号できる。 ## implementation #!/usr/bin/env python2 from Crypto.PublicKey import RSA from Crypto.Util.number import long_to_bytes import gmpy2 from pwn import * # https://pypi.python.org/pypi/pwntools import argparse parser = argparse.ArgumentParser() parser.add_argument('host', nargs='?', default='ctf.sharif.edu') parser.add_argument('port', nargs='?', default=4000, type=int) parser.add_argument('--log-level', default='info') args = parser.parse_args() context.log_level = args.log_level p = remote(args.host, args.port) def choose(i, j): p.sendline('C') p.recvuntil('Send two distinct indices smaller than 10, separated by space.\n') p.sendline('%d %d' % (i, j)) p.recvuntil('The encrypted flag is: ') c = int(p.recvline(keepends=False)) log.info('m^e mod p_%d p_%d = %d', i, j, c) return c c01 = choose(0, 1) c02 = choose(0, 2) c03 = choose(0, 3) p0 = gmpy2.gcd(c01 - c02, c02 - c03) log.info('p_0 = %d', p0) assert gmpy2.is_prime(p0) # sometimes fails c12 = choose(1, 2) c13 = choose(1, 3) p1 = gmpy2.gcd(c01 - c12, c12 - c13) log.info('p_1 = %d', p1) assert gmpy2.is_prime(p1) e = 65537 d = gmpy2.invert(e, (p0-1)*(p1-1)) key = RSA.construct(map(long, [ p0*p1, e, d ])) m = key.decrypt(c01) log.info('m: %d', m) log.info('flag: %s', long_to_bytes(m))  $ ./a.py
[+] Opening connection to ctf.sharif.edu on port 4000: Done
[*] m^e mod p_0 p_1 = 898417465536231647536400540300363534095756270151401975210560215118012137798184870674347033212236779788758268859578217720020550326036095933992353173046389706340350199946750138034352981972142984787771567095428041713322162981404191553642418110423562836107519528520435200153290368419223407256249471395525952028
[*] m^e mod p_0 p_2 = 47983970249875729518595397679790798992257455207638822586545393945918749834260197256451217158372405536079397368109311633465789440568960596862895169803863148764451912016698665022878257016944574007230683665137853787961590229748460492531361234480814926738607352963494291159062759542873547223158720091715657142653
[*] m^e mod p_0 p_3 = 63718146176962510784046083901489014487186886194401836666074531679003069909413332829474191357317890493471718757523087304186678542272371060530676545658398840000203413660554860988596298543878973758168145765793971477637562782551301811006022972180277149899879563676683668342098347053462919637823570723227858177595
[*] p_0 = 8671054057175865217444362883518923714252166956201180498299993492027860659074313622499953910455775509322558205899281483731567457911570089732453490928963371
[*] m^e mod p_1 p_2 = 8768108247325380353642336587810803242525652570804843439051241080081702440212252942103223957794188107601392445126524229232163142721564453961815335351412926862849443498595947349606276324390488862717563683202331636715714236503896221686158159544850417862616827305832302082104374214484286479216435538347571394551
[*] m^e mod p_1 p_3 = 34965575361970669990904924551347863119285063716323653171209309246298362524483352779008356876514954897230693301718974583677379489095505599500376935788847100941569779111515079730070825105957736148470535713028103941486167032649382162582266651296416990099979735932463805999720749601826721385930879957747043200966
[*] p_1 = 6845656491513729615106406472194911055875704245574129619347288360884377262703043432192059676423305300481225591991167689787544745946257676157844318403816769
[*] m: 11675752514251168943075626648353196340311926617207550832913508858080729362682279298167179748946164856957
[*] flag: SharifCTF{7c62f12e7e6f08f9f5365e45588d34d8}
[*] Closed connection to ctf.sharif.edu port 4000