TSGCTF 2020 Writeup

　2020/07/11 16:00(JST)～2020/07/12 16:00(JST)に開催されたTSGCTF 2020にチーム「N30Z30N」でソロ参加しました。Crypto問題2問を解き、346点（Sanity,Surveyを含む）を獲得して50位でした。順位はともかく、久しぶりにじっくり取り組め、なおかつ楽しめました。

　※2020/07/12 19:45 体調がしんどいので設問とソルバーとフラグだけ紹介し、思考過程や説明などは随時加筆修正いたします。
　※2020/09/22 11:30 Sweet like Apple Pieの項を増補修正しました。

Beginner's Crypto（難易度：beginner, 107points）

設問

pythonのソースファイル（beginners.py）と、ヒントが与えられておりました。以下、日本語の問題文を引用します。

終わりよければすべてよし、ってね。
初心者向けヒント: 添付されたPythonスクリプトにassert文が2つ書いてあるのがわかりますか? これはあなたが満たすべき条件を表しています。これらの命令はflag.txtという名前のファイルを読み込み、正しいフラグかどうかを判定しています。あなたの仕事はこれらの条件を満たすような文字列を見つけることです。実のところ、これらの条件を満たす文字列はただ1つしか存在しないので、ちゃんとこの条件を満たせたら、正しいフラグを得たことになります。

beginners.py

assert(len(open('flag.txt', 'rb').read()) <= 50)
assert(str(int.from_bytes(open('flag.txt', 'rb').read(), byteorder='big') << 10000).endswith('1002773875431658367671665822006771085816631054109509173556585546508965236428620487083647585179992085437922318783218149808537210712780660412301729655917441546549321914516504576'))

解答

solve.py

from Crypto.Util.number import *
x = 1002773875431658367671665822006771085816631054109509173556585546508965236428620487083647585179992085437922318783218149808537210712780660412301729655917441546549321914516504576
d = len(str(x))
inv = inverse(2**(10000-d),5**d)
flag = long_to_bytes((x // (2**d) * inv) % 5**d).decode()
print(flag)

フラグ

TSGCTF{0K4y_Y0U_are_r3aDy_t0_Go_aNd_dO_M0r3_CryPt}

Sweet like Apple Pie（難易度：medium, 189points）

設問

問題文は以下の１行。

「正弦曲線暗号」を発明しました！

あとは、暗号化プログラム「run.py」と暗号文データ「output.txt」が与えられました。

run.py

from decimal import *
getcontext().prec = 300

def pi():
    lasts, t, s, n, na, d, da = 0, Decimal(3), 3, 1, 0, 0, 24
    while s != lasts:
        lasts = s
        n, na = n + na, na + 8
        d, da = d + da, da + 32
        t = (t * n) / d
        s += t
    return s

def sin(x):
    x = Decimal(x) % pi()
    p, factor = 0, x
    for n in range(10000):
        p += factor
        factor *= - (x ** 2) / ((2 * n + 2) * (2 * n + 3))
    return p

flag = int.from_bytes(open('flag.txt', 'rb').read(), byteorder='big')
assert(flag < 2 ** 500)
print(sin(flag))

output.txt

0.162452474092990408037062573408259688253995107643493293584426591003988903469791005222132158897198623144937279539555347413553688190959907095952250683633029959235933436782707275021817801890433801800730214807785288112267446678747104887584191096749196212784470161670299495426679759221652356130008110761143

解答

[2020/09/22修正]

　正弦関数（$\sin$）を「暗号化関数」としたのであれば、逆関数である逆正弦関数（$\arcsin$）で引き戻せば復号できるはずです。
　そこで、$\arcsin$の近似計算（マクローリン展開）を実装してみたところ、精度が悪くイマイチだったので、逆正接関数（$\arctan$）を使うことにしました。誤差が出ることが想定されるので、うまく復号できなかった場合は誤差の分をbruteforceすればOK、という方針で取り組みました。
　実装的には、$\arctan$で引き戻してから適当な$10$冪（$10^{299}$）を乗じ、$\mod{10^{299}\pi}$ の整数計算に帰着させました。
　しかし、うまくフラグにたどり着かず原因を探っていたところ、そういえば $\sin(x)=\sin(π-x)$ だった、ということを思い出して再計算したところ、うまくいきました。高校数学で学習した基本を失念していたことが仇となり、ゴールにたどり着くまで余計な時間を費やしていたしまいました。
　大学のレポートであれば誤差の評価まで論理的に説明すべきなのでしょうが、「競技なので」という錦の御旗のもと、今回は（今回も）サボります。

※以前掲載したsolverには、誤差項の試行の部分が抜けていました。訂正後は以下となります。

solve.py

from Crypto.Util.number import *
import gmpy2
from decimal import *
getcontext().prec = 300

def pi():
    lasts, t, s, n, na, d, da = 0, Decimal(3), 3, 1, 0, 0, 24
    while s != lasts:
        lasts = s
        n, na = n + na, na + 8
        d, da = d + da, da + 32
        t = (t * n) / d
        s += t
    return s

def sin(x):
    x = Decimal(x) % pi()
    p, factor = 0, x
    for n in range(10000):
        p += factor
        factor *= - (x ** 2) / ((2 * n + 2) * (2 * n + 3))
    return p

def arctan(x):
    x = Decimal(x)
    p, factor = 0, x
    for n in range(100000):
        p += factor
        factor *= - x ** 2 * (2 * n + 1)  /  (2 * n + 3)
    return p

f = open('output.txt','r')
s = f.read()
f.close()

SIN = Decimal(s)
COS = (Decimal("1") - SIN ** 2 ) ** Decimal(0.5)
TAN = SIN / COS

INV1 = arctan(TAN)
#INV1 = 0.163175637602740964490722062267061389696088139158230600899046968672190506743495294736990774853241661073016774001982145726962910253737719770054606991776546791738735108712813938709131029475508398263190389434698312411911642837531652804269120745335974869150072258589701323425678679477710769757658218467270

INV2 = pi() - INV1
i = 0
while(1):
  INV2 = INV2 + Decimal("0.000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001") * i
  if(sin(INV2) == SIN):
    break
  i += 1
#INV2 = 2.97841701598705227397192132101244149450108126021687522007589762363562589954271370389104405048887540690913131251130016092013093435581286246167075241635193432571154899398912458239642861514744055666719157499411266325402180329094399542951766241993522703999557630833375902518477564717050262384960203067400

K = 10 ** 299
N = int(pi() * K)
A = int(INV2 * K)
d = gmpy2.gcd(K, N)

kinv = inverse(K//d, N//d)
print(long_to_bytes(kinv * A % N//d).decode())

参考までに訂正前のものも載せておきます。

solve.py.old(訂正前)

from Crypto.Util.number import *
import gmpy2
from decimal import *
getcontext().prec = 300

def pi():
    lasts, t, s, n, na, d, da = 0, Decimal(3), 3, 1, 0, 0, 24
    while s != lasts:
        lasts = s
        n, na = n + na, na + 8
        d, da = d + da, da + 32
        t = (t * n) / d
        s += t
    return s

def sin(x):
    x = Decimal(x) % pi()
    p, factor = 0, x
    for n in range(10000):
        p += factor
        factor *= - (x ** 2) / ((2 * n + 2) * (2 * n + 3))
    return p

def arctan(x):
    x = Decimal(x)
    p, factor = 0, x
    for n in range(100000):
        p += factor
        factor *= - x ** 2 * (2 * n + 1)  /  (2 * n + 3)
    return p

f = open('output.txt','r')
s = f.read()
f.close()

SIN = Decimal(s)
COS = (Decimal("1") - SIN ** 2 ) ** Decimal(0.5)
TAN = SIN / COS

INV1 = arctan(TAN)
#0.163175637602740964490722062267061389696088139158230600899046968672190506743495294736990774853241661073016774001982145726962910253737719770054606991776546791738735108712813938709131029475508398263190389434698312411911642837531652804269120745335974869150072258589701323425678679477710769757658218467270

INV2 = pi() - INV1 + Decimal("0.000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000075")
#2.97841701598705227397192132101244149450108126021687522007589762363562589954271370389104405048887540690913131251130016092013093435581286246167075241635193432571154899398912458239642861514744055666719157499411266325402180329094399542951766241993522703999557630833375902518477564717050262384960203067400

assert(sin(INV2) == SIN)

K = 10 ** 299
N = int(pi() * K)
A = int(INV2 * K)
d = gmpy2.gcd(K, N)

kinv = inverse(K//d, N//d)
print(long_to_bytes(kinv * A % N//d).decode())

フラグ

TSGCTF{Tteugeopgo_Dara_Sweee-ee-ee-ee-eet_1ik3_4pple_Pie_Pie}