解けず。しほさんの残したwriteupを見て解いた。これは自力で解けるべき。

problem

$ 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