1. はじめに
4/26、東工大デジタル創作同好会traPさんが主宰する「CPCTF 2023」にソロチーム「N30Z30N」で参加しました。
▼開催案内（ブログ） trap.jp
▼東工大デジタル創作同好会traPさんのTwitter twitter.com
参加できたのが終盤 1時間半くらいでしたので、Crypto 問 のほか OSINT 問などを少しやったぐらいで時間切れとなってしまいましたが、久しぶりに写真ベースの OSINT を楽しめました。
ランキングは 37 位でした。ヨシ、素数だ、頑張った！！
以下、簡単にですが Crypto 2問（いずれも難易度 Medium）の Writeup を書きます。
2. Writeup
2.1. Misuse
設問
以下の SageMath スクリプトと出力データが与えられます。
「misuse.sage」
"""This code is designed to be run with SageMath. See https://www.sagemath.org/ If you don't have SageMath installed, you can use the online version at https://cocalc.com/ or https://sagecell.sagemath.org/ But you may not use pyton lib online... ref: https://doc.sagemath.org/html/en/index.html """ from Crypto.Util.number import bytes_to_long, long_to_bytes, isPrime from flag import flag from Crypto.Cipher import AES from base64 import b64encode from secret import key from Crypto.Util.Padding import pad p = 1457379754778834114393428514496372769300186542434939310975944765431765709327445548009771988242361974038539406450275157591 a = 1236064211753439722521344199773932075287648377233139862790772102290062141518569630890922001641345393262197009050412379555 b = 1128111897991419355721141214155995058314857116431662004640521251265155838304469066234949556324122951758680646976644303642 def lift_x(x, p): assert p % 4 == 3 z = (x**3 + a * x + b) % p res = pow(z, (p + 1) // 4, p) return res % p, -res % p if __name__ == "__main__": assert isPrime(p) F = GF(p) m = flag.encode("utf-8") cipher = AES.new(long_to_bytes(key), AES.MODE_CBC) iv = cipher.iv c = cipher.encrypt(pad(m, AES.block_size)) x = bytes_to_long(long_to_bytes(key) + c) assert x < p d = 65537 ecc = EllipticCurve(F, [a, b]) y = lift_x(x, p)[0] P = ecc(x, y) Q = d * P with open("public.txt", "w") as f: f.write(f"iv={bytes_to_long(b64encode(iv))}\n") f.write(f"Q_x={Q[0]}\n") f.write(f"Q_y={Q[1]}\n")
「public.txt」
iv=1605329254557036569964018111218106639001485748371419774269 Q_x=1392303607889887553584136595208390161792050603172364540235291678701315789244344186052295822556700256817290239704363991998 Q_y=1217907436356492041789129865417129927287034438783900990437895711720259012753482269603468893642710812002767867785347902249
検討
楕円曲線の問題ですが、いわゆる DLP を解く類のものではなく、ある点をスカラー倍された点 Q が与えられ、そのスカラー倍する前の点（の x 座標）を求めるものです。
この問題では特にパラメータが隠されているようなことはないので、SageMath を使い暗号化の逆手順を愚直に計算してゆけばフラグを得ることができそうです。
解法
以下のソルバを書いて解きました。
「solve.sage」
from Crypto.Util.number import * from Crypto.Cipher import AES from base64 import b64decode p = 1457379754778834114393428514496372769300186542434939310975944765431765709327445548009771988242361974038539406450275157591 a = 1236064211753439722521344199773932075287648377233139862790772102290062141518569630890922001641345393262197009050412379555 b = 1128111897991419355721141214155995058314857116431662004640521251265155838304469066234949556324122951758680646976644303642 iv=1605329254557036569964018111218106639001485748371419774269 Q_x=1392303607889887553584136595208390161792050603172364540235291678701315789244344186052295822556700256817290239704363991998 Q_y=1217907436356492041789129865417129927287034438783900990437895711720259012753482269603468893642710812002767867785347902249 d = 65537 F = GF(p) E = EllipticCurve(F,[a,b]) Q = E(Q_x,Q_y) od = E.order() t = inverse(d, od) G = t*Q assert d*G == Q x = long_to_bytes(int(G[0])) key = x[:16] iv = b64decode(long_to_bytes(int(iv))) cipher = AES.new(key = key, mode=AES.MODE_CBC, iv=iv) pt = cipher.decrypt(x[16:]) print(pt)
フラグ
CPCTF{Manual_is_imp0rtant}
2.2. Simple
設問
以下の python スクリプトと出力データが与えられます。
「simple.py」
from Crypto.Util.number import inverse, bytes_to_long, getPrime from flag import flag class complex_over_p: """ a + bi """ def __init__(self, a, b, p): self.a = a self.b = b self.p = p def __mul__(self, other): return complex_over_p( (self.a * other.a - self.b * other.b) % self.p, (self.a * other.b + self.b * other.a) % self.p, self.p, ) def __pow__(self, n: int): ret = complex_over_p(1, 0, self.p) x = complex_over_p(self.a, self.b, self.p) while n > 0: if n & 1: ret = ret * x x = x * x n >>= 1 return ret def __str__(self): return str(self.a) + " + " + str(self.b) + "i" p = getPrime(512) q = getPrime(512) n = p * q phi = (p - 1) * (q - 1) e = 65537 m = bytes_to_long((flag).encode("utf-8")) c_1 = complex_over_p(p, m, n) ** e c_2 = complex_over_p(q, m, n) ** e with open("cipher.txt", "w") as f: f.write(f"c_1 = {str(c_1)}\n") f.write(f"c_2 = {str(c_2)}\n") f.write(f"n = {n}\n") f.write(f"e = {e}\n")
「cipher.txt」
c_1 = 88947353384906315386142174915579230007708484691905461586249734733895208303904624706955572569717469153074453837889147058757297004159523404800499566731846573280606881057150101844929178328363240743156762837486978571114151912836342740869293096891054377782752248810122413624567401981982628574682163267589540717955 + 105796218607197626508309219898970081654433389611035862776816738031930217893350585142033078143656160997324512315260317101196998029046142078518167267210684968483205795618377068578645969888568133775820377659323101885187136507439656053103103802476138541844262969937543381511564444761769799873705129093296227488320i c_2 = 6246646181898635030418930144979030696163268885489193597189892517442414814959679853409630585655482080447639092928109757977342458025765218315720433756032748568912426451942636486110411038484872363928990656032625950245328223463301109739166158341796991125915052131277132622262221136515681121985807852466393611412 + 53817519046828021036896927561082153848829725683909509411136093993919199941896521025977358288420902565544951255959786518459773639829589216874164688208953119794504853435052217109342811249935881805211646847973929482665869312260539685753735469177452027367949870932823024534083790996822338074496201028292592498398i n = 115660927134746496667389439939121894365639159618801107805144217447831876345527158612296725729945512010246362315164908359385194177739042272399000609673334050698528059482827768728850630523188582862374516240503442919767592843273925939238586765096529791229982128395675821790738782110235716669724330392693672332699 e = 65537
検討
c_1、c_2 から p、q をリークしてゆく流れしかなさそうですが、c_1 = (p + m*i)**e mod.n、c_2 = (q + m*i)**e mod.n ですから c_1（resp. c_2）の実部は p（resp. q）で割り切れます*1。
あとは mod. Totient でe の逆数 d を求めてから c_1 の d 乗を計算し、その虚部をバイト（文字列）に変換すればフラグをゲットできます。
解法
以下のソルバを使って解きました。ここで、Totient は (p**2-1) * (q**2-1) になる p, q の取り方によらず (p**2-1) * (q**2-1) を割る*2ことに注意します（これを知らないと解くのは困難です多少回りくどくなります*3）。
from Crypto.Util.number import * c_1 = (88947353384906315386142174915579230007708484691905461586249734733895208303904624706955572569717469153074453837889147058757297004159523404800499566731846573280606881057150101844929178328363240743156762837486978571114151912836342740869293096891054377782752248810122413624567401981982628574682163267589540717955, 105796218607197626508309219898970081654433389611035862776816738031930217893350585142033078143656160997324512315260317101196998029046142078518167267210684968483205795618377068578645969888568133775820377659323101885187136507439656053103103802476138541844262969937543381511564444761769799873705129093296227488320) c_2 = (6246646181898635030418930144979030696163268885489193597189892517442414814959679853409630585655482080447639092928109757977342458025765218315720433756032748568912426451942636486110411038484872363928990656032625950245328223463301109739166158341796991125915052131277132622262221136515681121985807852466393611412, 53817519046828021036896927561082153848829725683909509411136093993919199941896521025977358288420902565544951255959786518459773639829589216874164688208953119794504853435052217109342811249935881805211646847973929482665869312260539685753735469177452027367949870932823024534083790996822338074496201028292592498398) n = 115660927134746496667389439939121894365639159618801107805144217447831876345527158612296725729945512010246362315164908359385194177739042272399000609673334050698528059482827768728850630523188582862374516240503442919767592843273925939238586765096529791229982128395675821790738782110235716669724330392693672332699 e = 65537 class complex_over_p: def __init__(self, a, b, p): self.a = a self.b = b self.p = p def __mul__(self, other): return complex_over_p( (self.a * other.a - self.b * other.b) % self.p, (self.a * other.b + self.b * other.a) % self.p, self.p, ) def __pow__(self, n: int): ret = complex_over_p(1, 0, self.p) x = complex_over_p(self.a, self.b, self.p) while n > 0: if n & 1: ret = ret * x x = x * x n >>= 1 return ret def __str__(self): return str(self.a) + " + " + str(self.b) + "i" p = GCD(c_1[0], n) q = GCD(c_2[0], n) phi = (p**2-1) * (q**2-1) d = inverse(e, phi) pt = complex_over_p(c_1[0], c_1[1], n) ** d print(long_to_bytes(pt.b).decode())
フラグ
CPCTF{c0mp1ex_numbers_4re_simp1e}
3. 感想
今回はほとんど Crypto と OSINT しかやっていませんが、難易度 Medium の Crypto 問は程よくスパイシーで面白かったです。特に「Simple」では貰えるスクリプトの中にあった Totient をミスリードする記載*4に惑わされてしまいました。
時間がなかったとはいえ、全て競プロ問題をスルーしてしまった点は反省＆懺悔しています。
平日の参加は厳しかったですが、次回も参加したいと思います。
*1:これに気づくのに多大な時間を要してしまいました。
*2:4/28訂正。詳細には、有理素数 r に対して r≡1 mod 4 なら r-1、≡3 mod 4 なら r**2-1。今回はp≡1 mod 4 、q≡3 mod 4 だったので phi = (p-1)*(q**2-1)。
*3:※4/27追記：今回の問題のようにフラグが p より小さい（もしくは総当たりで見つかるくらい"少し"大きい）場合、mod p で考え直せば解けるようです。また、フラグが大きくても mod p と mod q で解いて 中国式剰余定理を使えば OK のようです。
*4:なぜそう思ったかというと、phi の値がその後何処にもつかわれていなかったからです。実際ミスリードを意図したか否かは作問者のみぞ知るところですね。
