1. なぜ速報？

HackCon 2019にソロ参加しました。
結果は399点173位でした。
Endを日本時間で24日00:30と想定していたので、時間切れで撥ねられてしまいましたorz...

そんな事情から、無念の度合いが大きい、解答できなかった1問の供養を先に行います。

2. Write up（AgainAndAgainAndAgain）

問題文

Someone was thinking encrypting again and again helps, prove them wrong.

c = 196353764385075548782571270052469419021844481625366305056739966550926484027148967165867708531585849658610359148759560853
Edit: the flag format is slightly differen

Code

q1.py

def encrypt(m):
    return pow(m,2,n)

p = 5411451825594838998340467286736301586172550389366579819551237
q = 5190863621109915362542582192103708448607732254433829935869841

n = p*q

flag = int('d4rk{*************REDACTED!!!!!!************}code'.encode('hex'),16)

l = encrypt(flag)
while  l > flag:
    l = encrypt(l)
print l

解法

方針

提示されたencrypt関数は「2乗してmod n」というだけの単純なものですが、これを「何回も」繰り返した旨が問題文で述べられております。
これをdecryptするには「$\mod{n}$の平方根」を求める必要が生じます。$n=pq$で平方根は4個存在し得るので、「どのルートを辿るか」によって正しいゴールに着けるか否か分かれます。$\mod{p}$、$\mod{q}$での平方根の計算は、Tonelli-Shanksのアルゴリズムにて実施すれば良いので何とかなりそうです。

やったこと

眠気がかなり来ており、ロジカル50%、力技（エスパー）50%のハイブリッドでやっつけました（実際は時間切れでやっつけられていない）。なお、$\mod{p}$、$\mod{q}$での平方根の計算のコードはここから拝借しております。
mをdecryptの対象とし、$\mod{p}$での$m$の平方根を$x$、$\mod{q}$での$m$の平方根を$y$、$a,b$を$ap+bq=1$を満たす整数（$p$と$q$は互いに素なので拡張Euclid互除法で計算可能）とすれば、

±ayp±bxq

はmのmod nでの平方根になります。実際、

x^2 = m+sp \\
y^2 = m+tq

とすれば、

\begin{align}
(±ayp±bxq)^2 \mod{n} &\equiv (ayp)^2+(bxq)^2 \mod{n}\\
&\equiv (ap)^2(m+tq)+(bq)^2(m+sp) \mod{n}\\
&\equiv m((ap)^2+(bq)^2) \mod{n}\\
&\equiv m(ap+bq)^2 \mod{n}\\
&\equiv m \mod{n}
\end{align}

となるわけです。
以上を踏まえsolverを作成するわけですが、深度は高々30くらいだろうとか、$m$の$\mod{n}$での平方根は$ayp±bxq$だけ見ておくだとか、かなりエスパー入ってますが結果的に出来てしまいました。あまりにも雑で、人様にお見せできるものではありませんが、今回は間に合わなかった後悔が大きいので公開させていただきます。

solve.py

from crypto.Util.number import *

def ex_euclid(x, y):
    c0, c1 = x, y
    a0, a1 = 1, 0
    b0, b1 = 0, 1

    while c1 != 0:
        m = c0 % c1
        q = c0 // c1

        c0, c1 = c1, m
        a0, a1 = a1, (a0 - q * a1)
        b0, b1 = b1, (b0 - q * b1)

    if a0 < 0:
      a0 = a0 + y

    return a0, b0

def tonelli(n, p): #rosettacode.org/wikiより 
#（略　ただし平方非剰余の場合0を返すように改造）

def decrypt(c1, c2, p,q, depth):
    if(depth == 0):
        return
    n = p * q
    a, b = ex_euclid(p, q)
    aa0 = tonelli(c1, p)
    bb0 = tonelli(c1, q)
    aa1 = tonelli(c2, p)
    bb1 = tonelli(c2, q)
    if(aa0 != 0 and bb0 != 0):
        x00 = (a * bb0 * p - b * aa0 * q) % n
        x10 = (a * bb0 * p + b * aa0 * q) % n
        print(long_to_bytes(x00))
        print(long_to_bytes(x10))
        decrypt(x00, x10, p, q, depth-1)
    if(aa1 != 0 and bb1 != 0 and c1 != c2):
        x01 = (a * bb1 * p - b * aa1 * q) % n
        x11 = (a * bb1 * p + b * aa1 * q) % n
        print(long_to_bytes(x01))
        print(long_to_bytes(x11))
        decrypt(x01, x11, p, q, depth-1)

if __name__ == '__main__':
    c = 196353764385075548782571270052469419021844481625366305056739966550926484027148967165867708531585849658610359148759560853
    p = 5411451825594838998340467286736301586172550389366579819551237
    q = 5190863621109915362542582192103708448607732254433829935869841
    decrypt(c, c, p, q, 30)

この結果をテキストに保存して、「d4rk」で検索するとフラグをゲットできました。

d4rk{r3p3t1t1v3_r4b1n_1s_th4_w0rs7_3vaaaaaar!}code

いろいろな意味で疲れた（とにかく眠い！）ので、本問の「マトモな解法」及び他のwrite upは後日とします。

HackCon'19 write up（速報）

1. なぜ速報？

2. Write up（AgainAndAgainAndAgain）

問題文

Code

解法

方針

やったこと