[InterKosenCTF 2019] Pascal Homomorphicity

tags: InterKosenCTF 2019 crypto

概要

メッセージを入力すると秘密の鍵を使って暗号化するサービス。
フラグ

$k$および2つの素数の積

$n$に対して

$c=(n+1{)}^k\mathrm{mod}{n}^2$

が与えられる。また、任意の

$m$に対して

$c=(n+1{)}^m\mathrm{mod}{n}^2$

が計算できる。なお、

$m$のビット数は

$k$のビット数より大きい必要があり、フラグのビット数は383である。

解法

フラグのビット数が分かるので二分探索で

$k$が求まりそう。試しに

$k$として考えられる下限と上限を与える。

from ptrlib import *

def calc(x):
    sock.recvuntil("> ")
    sock.sendline(str(x))
    sock.recvline()
    y = int(sock.recvline())
    return y

sock = Socket("localhost", 8002)

bl = 383

sock.recvline()
c = int(sock.recvline())

x1 = 1 << (bl - 1)
x2 = (1 << bl) - 1

print(c)
print(calc(x1))
print(calc((x1 + x2) // 2))
print(calc(x2))

良い感じにcがcalc(x1)とcalc(x2)の間に入っている。

$ python solve.py 
[+] __init__: Successfully connected to localhost:8002
1624995286371349887134414371930208840247474960919742158556836801978888046325951794111319264943461942007918889509763823590024654811100664967374799802508533401860420970136152847820573869003457196742529167786314999921772911706262906441476163949246002571028186811631161697716501942703646905598553452526120855426855123100812575535539431442243290323890381848664999833270209904922842067944942987759901838589072732136131743227262556
1378659899449326278338678437282545329232985718196070185648386835350506047883631920274499747945181398058087354292104520610300118147211218103353268403140576478768914132525024779984555794494742516927018674792423354678893219467429267812098103902158693954477369809516945206323559676114357688236999064033455155126769890939554188129741657950551790824532830668037895915484801023154267427204010279804713058164609755215216373519089665
2067989849173989417508017655923817993849478577294105278472580253025759071825447880411749621917772097087131031438156640957104647547562839976490083075853996393236876467351550729990571578568470400694629082522024477231907790691108024693077482356851500577799922067065839192750877283267854039946590820436138631310130922357011756074074919067908924967023534517924894953588281099550801427081297906224600969358089904332810210315314506
2757319798898652556677356874565090658465971436392140371296773670701012095767263840548999495890362796116174708584208901262254706621168449028166717277424284632621333533614063119982849475815841659158138419918236154571354400424822658599126534307930847555038606971824311795912657121325032884065090352452866208873515867826788850138945748043184820379289949851943842911330681611127935140683303046126957498440394781940418397074859338

あとは2分探索するだけ。

from ptrlib import *

def calc(x):
    sock.recvuntil("> ")
    sock.sendline(str(x))
    sock.recvline()
    y = int(sock.recvline())
    return y

sock = Socket("localhost", 8002)

bl = 383

sock.recvline()
c = int(sock.recvline())

left = 1 << (bl - 1)
right = (1 << bl) - 1

while True:
    #print(hex(left), hex(right))
    yl = calc((left + right) // 2)
    if yl < c:
        left = (left + right) // 2
    elif yl > c:
        right = (left + right) // 2
    else:
        break

print(bytes.fromhex(hex((left + right) // 2)[2:]))

$ python solve.py 
[+] __init__: Successfully connected to localhost:8002
b'KosenCTF{Th15_15_t00_we4k_p41ll1er_crypt05y5tem}'
[+] close: Connection to localhost:8002 closed

感想

良いと思う。修正前より確実に難易度下がったと思う。