ICC Tokyo 2025: apia Upsolve

apia

authored by elliptic-shiho & chocorusk

the hunter home from the hill

#!/usr/bin/env python3

from Crypto.Util.number import *
import os

with open("flag.txt", "rb") as f:
    FLAG = f.read()
FLAG += os.urandom(512 * 3 // 8 - 1 - len(FLAG))

p = getPrime(512)
q = getPrime(512)
N = p ** 2 * q
d = pow(N, -1, (p - 1) * (q - 1))

def encrypt(pt):
    return pow(pt, N, N)

def decrypt(ct):
    return pow(ct, d, p * q)

print("N:", N)
print("encrypted flag:", pow(bytes_to_long(FLAG), 0x10001, N))

# for test
while True:
    pt = int(input("plaintext: "))
    assert pt > 0
    print(decrypt(encrypt(pt)) == pt)

コードから$N = p^2q$とそれを用いて暗号化されたフラグが渡されます。その後、任意の平文を任意の回数暗号化し、暗号化$\rightarrow$復号をし、平文と一致するかを出力します。

解法

まず、decryptでは$\mod pq$を使われていることから、print(decrypt(encrypt(pt)) == pt)は

\text{(decrypt(encrypt(pt))} = \text{pt} \pmod {pq}

と考えることができます。
そして、$pt > pq$となるとき、復号することはできないためFalseが返されます。
なぜ、$pq$を超えてはいけないのかはこの記事の解法の最初のほうで書いているのでそちらをご覧ください。
https://qiita.com/potyamaaaa/items/b12eef832c12a3c34e30

次に、今回の$p, q$の範囲について考えましょう。

p = getPrime(512)
q = getPrime(512)

こちら、getPrime関数はGitHubでの実装コード(166行~182行)を見てみるとp, qのそれぞれの取りうる範囲がわかります。
https://github.com/Legrandin/pycryptodome/blob/master/lib/Crypto/Util/number.py

2^{511} \leq p, q \leq 2^{512} - 1

より

2^{1022} \leq pq \leq 2^{1024} - 2^{513} + 1 < 2^{1024}

の範囲で二分探索すればよいことがわかるでしょう。

後は$N$の定義より、$p,q$は以下で求まります。

\displaylines{p = N/pq\\q = pq/q}

これを実装すると以下になります。

from pwn import *
from Crypto.Util.number import long_to_bytes

HOST = "localhost"
PORT = 12349

io = remote(HOST, PORT)

io.recvuntil(b"N: ")
N = int(io.recvline().strip())
io.recvuntil(b"encrypted flag: ")
enc_flag = int(io.recvline().strip())

print("N =", N)
print("enc_flag =", enc_flag)

l = 2 ** 1022
r = 2 ** 1024 - 2**513 + 1
while r-l != 1:
    m = (l + r) // 2
    io.sendlineafter(b"plaintext: ", str(m).encode())
    resp = io.recvline().strip()
    if resp == b"True":
        l = m 
    else:
        r = m


pq = r
print("pq =", pq)
p = N//pq
q = pq//p
print("p =", p)
print("q =", q)
e = 0x10001

assert p * p * q == N

d = pow(e, -1, p * (p - 1) * (q - 1))
m = pow(enc_flag, d, N)
flag = long_to_bytes(m)
prefix = b"ICC{"
start = flag.rfind(prefix)
end = flag.find(b"}", start)
print(flag[start:end + 1].decode())

N = 490187088611785603311175380454928518965413058172432450493532710654831003121196711480338846123751096287920165894150966367805263009196870435225445200014300259231241029369249772014129226821482081182804747629571970177087558436997920494556126193484003326916804286166407785843496722844883257263188671670251840872351344438785949013167694139866596651218947257240994742984452251301954214577479681505417705128695565360896786817006793873637526480177806120089025800360848813
enc_flag = 278271870218742830229755951152307324645896554948759729841659405596415094815340799867333392208503363202475578808879839389672482111549495944315134296073303813430328422809050796161732301051945133444031987626391655951783504469131736329350673485353119342456646663819487923336423102249314884314786674126432316496749323702960630618497375107767425458855696598126574053198059240145593948446529510702566743711579896847597367994641013314073021817202100040894321060887626256
pq = 67108715225631989605001426464860545242643321531284734883956700093586517380705520707202769316915595573661053809455903487588706064514735839009568948509472285634617830611003437281027616069223034837833533930907151838216594652268062935574151510067540297141618949057091227604421843989108449940577159523919606862567
p = 7304373015690814329610880499064034956931937296632599214313553041885189544968546122532214546842574692821312851115620107807903668903590458132276744189656139
q = 9187470996001037741098927301601690423366867732072474399102914658855542953658558899135975923932075128404580383420621718186392736443514554386289261055584853
ICC{61fc53e1d8d8aa56a6f92516c6f577a1f205cb956116fbdf57363de9cfcb9051}

Flag: ICC{61fc53e1d8d8aa56a6f92516c6f577a1f205cb956116fbdf57363de9cfcb9051}

おまけ

ICC Tokyoの公式レポジトリに記載されているsolutionを見たら、上記のようなRSAのことをSchmidt-Samoa暗号と呼ぶらしいです。

https://github.com/ctfplatform/icc-2025-jeopardy-problems/tree/main/crypto/apia/solution
英語のwikipedia見てみると

Unlike Rabin this algorithm does not produce an ambiguity in the decryption at a cost of encryption speed.
https://en.wikipedia.org/wiki/Schmidt-Samoa_cryptosystem

と書いているので、暗号化速度は遅いらしい。