ångstromCTF 2019 Writeup

# はじめに
久々にWriteupを書きます。あまり時間が取れなかったのと、まだまだ実力不足のせいであまり貢献できなかったのが悔しい限りです。

例によって[GitHub](https://github.com/taiyaki8926/angstrom)に問題を掲載しておきます。

## Lithp
> My friend gave me this program but I couldn't understand what he was saying - what was he trying to tell me?

名前から分かる通り、Lispで書かれたコードが表示されます。
自分はLispなんて1秒も勉強したことないのでその都度ググる必要があるわけなのですが…
逆にいうと、(C言語なりPythonなり)少しでもプログラミングをやっていれば、1時間ほどで書かれているLispの内容を理解するレベルまでは到達できます。

与えられたLispコードをPythonに直したものを掲載します。Lispと比較してみてください。
この問題に関しては検索力と意地があればなんとかなります。

```Python3:lisp.py
encrypt = [8930,15006,8930,10302,11772,13806,13340,11556,12432,13340,10712,10100,11556,12432,9312,10712,10100,10100,8930,10920,8930,5256,9312,9702,8930,10712,15500,9312]
reorder = [19,4,14,3,10,17,24,22,8,2,5,11,7,26,0,25,18,6,21,23,9,13,16,1,12,15,27,20]

def enc(plain):
    # setfはC言語の変数宣言みたいなもの
    uwuth = multh(plain)
    uwuth = owo(uwuth)
    out = []
    # dotimes (ind (length plain) out)は
    # indを0から増やしていき, ind == len(plain)になったらoutを出力
    for ind in range(len(plain)):
        # / (nth ind uwuth) -1について,
        # "/ 3 4"は3÷4の意味
        # "nth i list"はlist[i]の意味
        out.append(-uwuth[ind])
    return out

def multh(plain):
    # condはif文, 2行下の"t"はelseの意味
    if plain == []:
        return []
    else:
         # "cons a b"で2つのリストa, bの結合
         # carはリストの先頭を抽出, cdrはリストの先頭以外を抽出
         return [whats_this(1-plain[0], plain[0])] + multh(plain[1:])
        
def owo(inpth):
    out = []
    redth = reorder
    # "do a b c"について
    # aは変数の初期値と行う操作(C言語でいうfor(i=0; i<100; i++)の1,3項目)
    # bはwhile文を抜ける条件(C言語でいうfor(i=0; i<100; i++)の2項目)と返り値
    # cはwhile文内で行う処理
    # a : (redth *reorder* (cdr redth))は初期値redth = reorder, 変数に行う操作はcdr
    # b : ((null redth) out)はredth == nullになればoutを返す
    # c : outにnth (car redth) inpthをappendする
    while redth != []:
        out.append(inpth[redth[0]])
        redth = redth[1:]
    return out

def whats_this(x, y):
    if y == 0:
        return 0
    else:
        return whats_this(x, y-1) + x
```

最低限の注釈を書きましたが、正直限界があるので必要に応じて調べてください。
あとは`what_this`がただの乗算であること、`multh`が各要素に対して
$x \rightarrow x(1-x)$
を施していること、`owo`が入力に対して
「入力の19番目, 入力の4番目, …, 入力の20番目」
と、reorderに沿って並び替えているだけであることに気付ければ簡単です。あとはGitHubに上げている`decrypt.py`を参照してください[^1]。

## Half and half
> Mm, coffee. Best served with half and half!

仕組みはそんなに難しくありません。
flagを前半(milk)と後半(cream)に分けて、各要素に対して XORをとっているだけです。
例えば
flag = 'IamCTFsolver'
なら

```Python3
milk = 'IamCTF'
cream = 'solver'
for i in range(6):
    print(ord(milk[i]) ^ ord(cream[i]))
```
みたいな感じです。
さて、XORをとった結果が12文字なので当然milkもcreamも12文字で、今回のCTFのflagの形式を考えると

```Python
milk = 'actf{???????'
cream = '???????????}'

encrypt = '\x15\x02\x07\x12\x1e\x100\x01\t\n\x01"'
```
と考えられます。XORの性質上
・milk XOR encrypt = cream
・cream XOR encrypt = milk
なので、creamの最初の5文字、milkの最後の文字はすぐに判明します。

```Python
milk = 'actf{??????_'
cream = 'taste??????}'

encrypt = '\x15\x02\x07\x12\x1e\x100\x01\t\n\x01"'
```

そして、ここからは残念ながら閃き力で全てが決まります。今回の問題設定上、"コーヒーのBest served"がキーになると考えると、

```Python3
milk = 'actf{coffee_'
cream = 'taste??????}'
```
と考えるのが自然でしょう(cが大文字の可能性もお忘れなく)。
こう予想してcreamを求めると

```Python3
milk = 'actf{coffee_'
cream = 'tastes_good}'
```
と、意味の通じる文章が導き出せます。`actf{coffee_tastes_good}`入力すると無事正解。

## Runes
> The year is 20XX. ångstromCTF only has pwn challenges, and the winner is solely determined by who can establish a socket connection first. In the data remnants of an ancient hard disk, we've recovered a string of letters and digits. The only clue is the etching on the disk's surface: Paillier.

$e$ではなく$g$が与えられているのでRSAではないようです(もし$e$だとしても流石に大きすぎます)。
$n$は素因数分解できるとして、そこから先は進まないのでとりあえず"Paillier"でググってみるしかなさそうです。

…[Paillier暗号](https://ja.wikipedia.org/wiki/Paillier暗号)なるものがヒット。$g$も使われているので、Wilipediaに掲載されている通りに復号すれば良さそうです。

まずは$n$を[素因数分解](http://www.factordb.com)しておきましょう。
$p$ = 310013024566643256138761337388255591613
$q$ = 319848228152346890121384041219876391791

さて、復号コードを書いていきます。

```Python3:runes?.py
import math
import codecs

n = 99157116611790833573985267443453374677300242114595736901854871276546481648883
g = 99157116611790833573985267443453374677300242114595736901854871276546481648884
c = 2433283484328067719826123652791700922735828879195114568755579061061723786565164234075183183699826399799223318790711772573290060335232568738641793425546869

p = 310013024566643256138761337388255591613
q = 319848228152346890121384041219876391791
_lambda = (p-1) * (q-1) // math.gcd(p-1, q-1)

def L(u):
    return (u-1) // n

m = (L(pow(c, _lambda, n**2)) // L(pow(g, _lambda, n**2))) % n
codecs.decode(('%x'%m), 'hex_codec')
```
ここまではすんなり[^2]いけました。ただ、このコード動かないのです…。
問題は、m = 1であること。もっというと、$L(c^\lambda\ {\rm mod}\ n^2)$が$L(g^\lambda\ {\rm mod}\ n^2)$で割り切れません。

色々検索した結果、Wikipediaに載っている
$$\frac{L(c^\lambda\ {\rm mod}\ n^2)}{L(g^\lambda\ {\rm mod}\ n^2)}\  {\rm mod} \ n$$
は、所謂分数としての計算ではなく、
$$L(c^\lambda\ {\rm mod}\ n^2) \cdot \left(L(g^\lambda\ {\rm mod}\ n^2)\right)^{-1}\  {\rm mod} \ n$$
と、$n$を法とするモジュラ逆数$\left(L(g^\lambda\ {\rm mod}\ n^2)\right)^{-1}$をかける操作であることが判明しました。

このモジュラ逆数は拡張Euclid互除法で求められるので、以上をまとめて正しいコードは以下のようになります。

```Python3:runes.py
import math
import codecs
n = 99157116611790833573985267443453374677300242114595736901854871276546481648883
g = 99157116611790833573985267443453374677300242114595736901854871276546481648884
c = 2433283484328067719826123652791700922735828879195114568755579061061723786565164234075183183699826399799223318790711772573290060335232568738641793425546869

p = 310013024566643256138761337388255591613
q = 319848228152346890121384041219876391791
_lambda = (p-1) * (q-1) // math.gcd(p-1, q-1)

def L(u):
    return (u-1) // n

# 拡張Euclid互除法
def egcd(e, n):
    x, y, u, v = 0, 1, 1, 0
    while e != 0:
        q, r = n // e, n % e
        m, n = x - u * q, y - v * q
        n, e, x, y, u, v = e, r, u, v, m, n
    return x

m = L(pow(c, _lambda, n**2)) * egcd(L(pow(g, _lambda, n**2)), n) % n
codecs.decode(('%x'%m), 'hex_codec')
```

`actf{crypto_lives}`が導けました。

## Paint
> This amazing new paint protocol lets artists share secret paintings with each other! Good thing U.S. Patent 4200770 is expired.

今回の1番の収穫かもしれません。

キーワードとして"U.S. Patent 4200770"がありますが、残念ながら特に有用な情報は得られません。

ソースコード自体は難しいものではありません。簡略のため
$g$ = `base`
$x$ = `secret`(未知)
$h$ = `my_mix`
$G$ = `palette`
と表記すると、
$$g^x = h\ ({\rm mod}\ G)$$
なる$x$を求めろ、との問題です。一般にこれは離散対数問題[^3]と呼ばれ、解くのが非常に難しいのですが、今回は
$$g^n = 1 \ ({\rm mod}\ G)$$
なる最小の$n$(これを$g$の位数と言います)が
$$n = 2^{2045}$$
のように簡単な素因数を持つ場合のみ[Pohlig-Hellmanのアルゴリズム](https://en.wikipedia.org/wiki/Pohlig–Hellman_algorithm)を用いることができます。
対応するアルファベットは上のリンク先と一致させてありますので、今回は$p = 2, e = 2045$となります。

```Python3:solve.py
from Crypto.Util.number import inverse

# base
g = 13489305024865487703110255658234329747698118206959778644688156332043783846078839120693894255527894489531905012244713117142764166452312133019772171674466933769775907460046497284522592167536594047800489828714315435570429416637425443402332599055774982796405757075108551322778712959943658831605397635195107786224617525627358659165255604556424206194207190437525742567525338826878962081515333896433312311548844614323540250054093970082337500580573165008440265840792908334486258260848163001490152587781983042546491301026074736907693887630347258892882871059741621049169714319440564952700454580681894452760215968494428411686329

# palette
G = 32317006071311007300714876688669951960444102669715484032130345427524655138867890893197201411522913463688717960921898019494119559150490921095088152386448283120630877367300996091750197750389652106796057638384067568276792218642619756161838094338476170470581645852036305042887575891541065808607552399123930385521914333389668342420684974786564569494856176035326322058077805659331026192708460314150258592864177116725943603718461857357598351152301645904403697613233287231227125684710820209725157101726931323469678542580656697935045997268352998638215525166389437335543602135433229604645318478604952148193555853611059596230656

# my_mix
h = 6870295205307030503255600311283969014496436297715066273709495591567561187646528069669895230912327862244474990612611625088862250315706633708998214109152824455738719595737772769297517386968692628228327225922261219083693899105983726637012353264168761696183327692619506267951701511870035935612090359086376808592001973358166067468618577312983514388332736591060901174314042634365304017788649960016991442596975922402288221898367955532116456798868804571091463566329706023967280838744359633963847966790121312196824818606244189274966061324393424041211903396020720341163472399763951106703068172772579049891895580785347369093113

p = 2
e = 2045

# Pohlig-Hellmanのアルゴリズム
x = [0]
gamma = pow(g, p ** (e-1), G)
for k in range(e):
    h_k = (pow(inverse(g, G), x[k], G) * h) % G
    h_k = pow(h_k, p ** (e-1-k), G)
    if h_k == gamma:
        d_k = 1
    else:
        d_k = 0
    x.append(x[k] + (p ** k) * d_k)

# secret
x[-1]
```
本当はここから`shared_mix`や`image`を求めたりと、もう少し処理をしなければいけないのですが、ここからは簡単なので割愛します。


[^1]: $x \rightarrow x(1-x)$がほぼ2乗(の-1倍)の操作であることから、`decrypt.py`はencryptの平方根をとって近い値に丸めてるという手法をとっています。例えばencryptの10100は100$\times$101なので101, つまりAsciiでいう0x65に相当すると考えても解けます。

[^2]: すんなり、ではなく実際はint / int$\rightarrow$floatになってしまうため、int // intを使う方が適切、と気づくのにかなり時間を食っています。

[^3]: $x$から$y$を求めるのは容易ですが、$y$から$x$を求めるのは難しい問題のことです。