神のミソ汁のセカイ

大学生活のことや技術的な備忘録を残してます

Pragyan CTF 2015: Weak RSA Write-up

問題

Pragyan CTF 2015: Weak RSA

チャレンジ中のリストはこちらCrypto Challenges List(2015)

解答

与えられたファイルfooはtar形式だったので展開すると次の2つのファイルが現れた。

  • cipher.enc base64形式の暗号文
  • domain.csr 署名要求のためのcsrファイル

csrファイルの中身をopensslコマンドで確認してみる。

$ openssl req -text -modulus -noout -in domain.csr
Certificate Request:
    Data:
        Version: 0 (0x0)
        Subject: C=IN, ST=NITT, L=-, O=-, OU=-, CN=weakrsa.com
        Subject Public Key Info:
            Public Key Algorithm: rsaEncryption
            RSA Public Key: (1024 bit)
                Modulus (1024 bit):
                    00:e8:95:38:49:f1:1e:93:2e:91:27:af:35:e1:00:
                    00:00:00:00:00:00:00:00:00:00:00:00:00:00:00:
                    00:00:00:00:00:00:00:00:00:00:00:00:00:00:00:
                    00:00:00:00:00:00:00:00:00:00:00:00:00:00:00:
                    00:00:00:00:51:f8:eb:7d:05:56:e0:9f:ff:ff:ff:
                    ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:
                    ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:
                    ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:
                    ff:ff:ff:ff:ff:ff:fb:ad:55
                Exponent: 65537 (0x10001)
        Attributes:
            a0:00
    Signature Algorithm: sha256WithRSAEncryption
        7e:d8:a8:25:51:a1:9e:7b:b1:cc:05:87:18:fc:65:59:ba:db:
        07:d7:cd:95:00:6e:ae:d9:4b:ad:ab:f5:b5:7c:92:e8:c0:59:
        2d:11:df:61:c8:db:e4:f8:f7:e0:d2:7c:94:9a:80:49:20:ee:
        2f:3b:96:f0:4e:5f:ab:12:6d:6d:10:7e:39:e9:c8:35:33:71:
        86:d6:0e:30:6b:46:e6:d1:95:42:94:d9:75:6b:cf:10:b2:62:
        fa:56:4c:f9:60:07:84:cf:73:46:85:24:e1:37:9b:aa:84:70:
        b0:3c:4d:09:45:cb:b7:52:28:db:ca:35:6a:9b:22:d6:fc:89:
        25:0a
Modulus=E8953849F11E932E9127AF35E1000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000051F8EB7D0556E09FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFBAD55

Modulusの値に特徴があるので因数分解できるかもしれない。

因数分解アルゴリズムを探しているとフェルマー因数分解Fermat’s factorization method - Wikipediaを見つけた。フェルマー法は素数$n$を$n=(a-b)^2=(a+b)(a-b)$の形に変形することで因数分解する。

上記wikipedia数学者の密室 12章 素因数分解アルゴリズムを参考にフェルマー法で$N$を因数分解を計算するプログラムを書いた。

#! /usr/bin/env python3
# -*-  coding : utf-8 -*-

import gmpy2 as gp2

def fermat_method(n):
    x = gp2.isqrt(N) + 1
    y = gp2.isqrt(pow(x, 2) - N)
    w = pow(x,2) - N - pow(y,2)
    while(w != 0):
        if (w == 0):
            break;
        if w > 0:
            y += 1
        else:
            x += 1
        w = pow(x,2) - N - pow(y,2)

    return (x-y, x+y)

N = 0xE8953849F11E932E9127AF35E1000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000051F8EB7D0556E09FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFBAD55

print('N=', N)
p, q = fermat_method(N)
print('p =', p)
print('q =', q)

実行結果

$ ./Fermat_method.py
N= 163325259729739139586456854939342071588766536976661696628405612100543978684304953042431845499808366612030757037530278155957389217094639917994417350499882225626580260012564702898468467277918937337494297292631474713546289580689715170963879872522418640251986734692138838546500522994170062961577034037699354013013
p = 12779877140635552275193974526927174906313992988726945426212616053383820179306398832891367199026816638983953765799977121840616466620283861630627224899026453
q = 12779877140635552275193974526927174906313992988726945426212616053383820179306398832891367199026816638983953765799977121840616466620283861630627224899027521

無事、$N$の素因数分解に成功したので今度はRSA暗号のソルバを書いた。暗号文はcat cipher.enc | base64 -Dとしてbase64形式から整数に戻した。

#! /usr/bin/env python3
# -*-  coding : utf-8 -*-

import gmpy2
import binascii

e = 65537
p= 12779877140635552275193974526927174906313992988726945426212616053383820179306398832891367199026816638983953765799977121840616466620283861630627224899026453
q= 12779877140635552275193974526927174906313992988726945426212616053383820179306398832891367199026816638983953765799977121840616466620283861630627224899027521

n = p * q
d = gmpy2.invert(e, (p-1)*(q-1))
c = 76628905480111532581338914747271384782783511160722054233840492116126156700750989597598764086667087929882155574613772521441663047915366133539316120325991966661466348138266360394561245386367735156756154303638622049855225176518054696962110019925849223565063511436418197917317987706182132214656056698754744084973 # 暗号文
m = pow(c, d, n)
print (binascii.a2b_hex('%0128x' % m))

実行結果

$ ./solver.py
b'\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00Congrats! The flag is too_close_primes'

よってflagはtoo_close_primes

感想

素因数分解は難しいとはいえ素数$p,q$の選び方次第では因数分解できるんだなあ。しかも和と差の積にして因数分解するアイデアは面白い。

多次元正規分布モデルの最尤推定(計算編)

はじめに

前回の記事多次元正規分布の最尤推定(準備編)で多次元正規分布最尤推定に必要な微分の知識をまとめた。今回は実際に多次元正規分布に従うパターンの最尤推定を計算してみる。

多次元正規分布モデルの尤度関数

多次元正規分布 $\mathcal{N}(\mathbf{x} ; \mathbf{\mu}, \mathbf{Σ})$ に対する$d$次元のパターン$\mathbf{x}$の一般形は次式で表される。

$$ q(\mathbf{x} ; \mathbf{\mu}, \mathbf{Σ}) = \frac{1}{(2\pi)^{\frac{d}{2}}\det(Σ)^\frac{1}{2}}\exp\left( -\frac{1}{2}(\mathbf{x}-\mathbf{\mu})^\mathrm{T}\mathbf{Σ}^{-1}(\mathbf{x}-\mathbf{\mu}) \right) $$

ここで、平均ベクトル$\mathbf{\mu}$は$d$次元の列ベクトル、分散共分散行列$\mathbf{Σ}$は$d\times d$の正定値行列である。そのため$\mathbf{Σ}^\mathrm{T} = \mathbf{Σ}$が成り立つ。 また、$\det(\cdot)$は行列式を表す。

まず、対数尤度関数$\log L(\mathbf{\mu}, \mathbf{Σ})$を計算する。訓練標本を$\{\mathbf{x_i}\}_{i=1}^n$とすると、

$$ \begin{align} \log L(\mathbf{\mu}, \mathbf{Σ}) &= \sum_{i=1}^n \log q(\mathbf{x}_i ; \mathbf{\mu}, \mathbf{Σ}) \\ &= \sum_{i=1}^n \log \frac{1}{(2\pi)^{\frac{d}{2}}\det(Σ)^\frac{1}{2}}\exp\left( -\frac{1}{2}(\mathbf{x}_i-\mathbf{\mu})^\mathrm{T}\mathbf{Σ}^{-1}(\mathbf{x}_i-\mathbf{\mu}) \right) \\ &= \sum_{i=1}^n \left\{ -\frac{d}{2}\log(2\pi) - \frac{1}{2}\log(\det(\mathbf{Σ})) - \frac{1}{2}(\mathbf{x}_i-\mathbf{\mu})^\mathrm{T}\mathbf{Σ}^{-1}(\mathbf{x}_i-\mathbf{\mu}) \right\} \\ &= -\frac{nd}{2}\log(2\pi) - \frac{n}{2}\log(\det(\mathbf{Σ})) - \frac{1}{2}\sum_{i=1}^n(\mathbf{x}_i-\mathbf{\mu})^\mathrm{T}\mathbf{Σ}^{-1}(\mathbf{x}_i-\mathbf{\mu}) \tag{1} \end{align} $$

正規分布モデルでのパラメータの最尤推定値は対数尤度関数を各パラメータで偏微分して極値を求めることで得ることができる。*1

パラメータ$\mathbf{\mu}$の最尤推定

式(1)を$\mathbf{\mu}$で偏微分した式が$\mathbf{0}$となるような$\hat{\mu}$がパラメータ$\mu$の最尤推定値である。

式(1)を$\mu$で偏微分すると $$ \begin{align} \frac{\partial}{\partial \mu} \log L(\mathbf{\mu}, \mathbf{Σ}) &= -\frac{1}{2} \sum_{i=1}^n \frac{\partial}{\partial \mu} (\mathbf{x}_i-\mathbf{\mu})^\mathrm{T}\mathbf{Σ}^{-1}(\mathbf{x}_i-\mathbf{\mu}) \\ &= -\frac{1}{2} \sum_{i=1}^n (-2\mathbf{Σ}(\mathbf{x}_i - \mu)) \\ &= \sum_{i=1}^n\mathbf{Σ}(\mathbf{x}_i - \mu) \tag{2} \end{align} $$

ここでは前回計算した次の関係 $$ \begin{align} \frac{\partial}{\partial \mathbf{a}} \mathbf{a}^\mathrm{T}\mathbf{B}\mathbf{a} &= (\mathbf{B} + \mathbf{B}^\mathrm{T})\mathbf{a} \\ &= 2\mathbf{B}\mathbf{a}\quad(\mathbf{B}^\mathrm{T}=\mathbf{B}) \end{align} $$ を用いた。

式(2)は$\mu = \hat{\mu}$で$\mathbf{0}$に等しくなるから $$ \sum_{i=1}^n\mathbf{Σ}(\mathbf{x}_i - \hat{\mu}) = \mathbf{0} $$

よってパラメータ$\mu$の最尤推定値は $$ \hat{\mu} = \frac{1}{n}\sum_{i=1}^n \mathbf{x}_i $$

パラメータ$\mathbf{Σ}$の最尤推定

式(1)を$\mathbf{Σ}$で偏微分した式が$\mathbf{O}$(零行列)となるような$Σ$がパラメータ$Σ$の最尤推定値である。これを$\hat{Σ}$とする。

式(1)を$\mathbf{Σ}$で偏微分すると

$$ \begin{align} \frac{\partial}{\partial \mathbf{Σ}} \log L(\mathbf{\mu}, \mathbf{Σ}) &= -\frac{n}{2}\frac{\partial}{\partial \mathbf{Σ}}\log(\det(\mathbf{Σ})) -\frac{1}{2} \sum_{i=1}^n \frac{\partial}{\partial \mathbf{Σ}} (\mathbf{x}_i-\mathbf{\mu})^\mathrm{T}\mathbf{Σ}^{-1}(\mathbf{x}_i-\mathbf{\mu}) \\ &= -\frac{n}{2}\mathbf{Σ}^{-1} -\frac{1}{2}\sum_{i=1}^n -\mathbf{Σ}^{-1}(\mathbf{x}_i-\mathbf{\mu})(\mathbf{x}_i-\mathbf{\mu})^\mathrm{T}\mathbf{Σ}^{-1} \tag{3} \end{align} $$

ここでは前回計算した次の関係 $$ \begin{align} \frac{\partial}{\partial \mathbf{A}} \log(\det(\mathbf{A})) &= (\mathbf{A}^{-1})^\mathrm{T} \\ \frac{\partial}{\partial \mathbf{B}} \mathbf{a}^\mathrm{T}\mathbf{B}^{-1}\mathbf{a} &= (-\mathbf{B}^{-1}\mathbf{a}\mathbf{a}^\mathrm{T}\mathbf{B}^{-1})^{\mathrm{T}} \\ \end{align} $$ を用いた。

式(3)は$\mathbf{Σ} = \hat{\mathbf{Σ}}$で$\mathbf{O}$となるから $$ \begin{align} -\frac{n}{2}\hat{\mathbf{Σ}}^{-1} +\frac{1}{2}\sum_{i=1}^n \hat{\mathbf{Σ}}^{-1}(\mathbf{x}_i-\mathbf{\mu})(\mathbf{x}_i-\mathbf{\mu})^\mathrm{T}\hat{\mathbf{Σ}}^{-1} = \mathbf{O} \\ n\hat{\mathbf{Σ}}^{-1} = \sum_{i=1}^n \hat{\mathbf{Σ}}^{-1}(\mathbf{x}_i-\mathbf{\mu})(\mathbf{x}_i-\mathbf{\mu})^\mathrm{T}\hat{\mathbf{Σ}}^{-1} \\ \hat{\mathbf{Σ}} = \frac{1}{n}\sum_{i=1}^n (\mathbf{x}_i-\mathbf{\mu})(\mathbf{x}_i-\mathbf{\mu})^\mathrm{T} \\ \end{align} $$

よってパラメータ$\mathbf{Σ}$の最尤推定値は $$ \hat{\mathbf{Σ}} = \frac{1}{n}\sum_{i=1}^n (\mathbf{x}_i-\mathbf{\hat{\mu}})(\mathbf{x}_i-\mathbf{\hat{\mu}})^\mathrm{T} $$ このとき$\mu$も最尤推定値$\hat{\mu}$となる。

参考

杉山将(2009)『統計的機械学習 生成モデルに基づくパターン認識オーム社

*1:実際には2次導関数を調べて、尤度関数の極値でのパラメータが大域的最適解になるかを確かめる必要がある。

ASIS Quals CTF 2015: Golden Metal Write-up

問題

ASIS Quals CTF 2015: Golden Metal

チャレンジ中のリストはこちCrypto Challenges List(2015)

解答

xz形式の問題ファイルを解凍すると次の3つのファイルが入っていた。

  • pub.txt 公開鍵が書かれている
  • enc.txt 暗号文が書かれている
  • golden_medal.py 暗号化プログラム

golden_medal.pyを見ると次のような暗号化を行っていることがわかった。

  1. ブラム素数(法4で余りが3となる素数)を2つ生成する(blumint関数)。
  2. オイラーの規準を用いて$q^2x \bmod p$と$p^2x \bmod q$が平方非剰余となるような$x$を選ぶ(qrn関数)。
  3. $p,q$を秘密鍵、$N=p*q,x$を公開鍵とする。
  4. flagを2進数化し、MSBを除く各bit($m_i$とする)ごとに$\gcd(y, N)$を満たす$y$を選んで暗号文の各bitを$c_i = x^{2y+m_i}y^2 \bmod N$と計算する(goldenmedal関数)。

すなわち平文の各ビットが$x$を底とする指数に隠され、それにランダムに選ばれた$y^2$が掛けられている。

調べたところ、これはGoldwasser–Micali cryptosystemという暗号方式であった。この方式では暗号文の各ビットが平方剰余かどうかを調べることで対応する平文のビットを復号できる。

暗号文の各ビットは$c_i = x^{2y+m_i}y^2 = x^{2y}x^{m_i}y^2=(x^{y}y)^2x^{m_i}$であるから、$c_i$が平方剰余ならば$m_i=0$とわかる。

$c_i$が平方剰余かどうかは$N$を素因数分解して$p,q$を取り出せばオイラーの規準を用いて判断できる。今回はhttp://www.factordb.com/index.phpで$N$の素因数分解を計算した。

以上を踏まえて書いた解読プログラムはこれ。問題ファイルに合わせてpython2系で書いた。鍵と暗号文は別のファイル(ここではkey_and_enc.py)に保存しておいてimportしている。

#!/usr/bin/env python
# -*- coding:utf-8 -*-

import key_and_enc

def decrypt(x, p, q):
    N = p*q
    x_p = x % p
    x_q = x % q
    if pow(x_p, (p-1)/2, p) == 1 and pow(x_q, (q-1)/2, q) == 1:
        return '0'
    else:
        return '1'

x, N = key_and_enc.key
enc = key_and_enc.enc
# http://www.factordb.com/index.php
p = 1285380609783825451015579898011805465763518244839
q = 1358902095093762824984385249873903079031552839163
assert p * q == N
M = ''
for i in range(0 , len(enc)):
    M += decrypt(enc[i], p, q)

m = int('0'+M, 2) # MSBの0を補う
print ("%0512x" % m).decode("hex")

実行結果

$ ./solver.py
ASIS{3c4cbc2d6bc6ebbbbbe967b8af5ac414}

よってflagはASIS{3c4cbc2d6bc6ebbbbbe967b8af5ac414}

感想

GoldwasserとMicaliは暗号理論を勉強していてよく出てくる印象。暗号ビットが平方剰余かどうかで平文ビットを決められるのは面白いと思った。

Pragyan CTF 2015: Rubies on Rails Write-up

問題

Pragyan CTF 2015: Rubies on Rails

チャレンジ中のリストはこちCrypto Challenges List(2015)

解答

問題ファイルcrypted.txtの中身は次のような数字の列であった。

777
33
33
7777
8
88
444
7777
777
8
666
9
33
22
2
666
33

携帯電話のキーボード入力ぽいのでプログラムを書いて確かめてみる。

ten_key = {2 : 'abc', 3 : 'def', 4 : 'ghi', 5 : 'jkl', 6 : 'mno', 7 : 'pqrs', 8 : 'tuv', 9 : 'wxyz'}

text = ''
with open('crypted.txt', 'r') as f:
    for line in f:
        n = int(line.strip()[0])
        text += ten_key[n][len(line.strip())-1]
print(text)

結果はreestuisrtowebaoe。これも何かの暗号文になっているようだ。

色々調べてみるとRail fence cipher - Wikipediaという暗号を見つけた。

平文を1文字ずつ$n$段になるようギザギザに並べ、それを1段目から順に結合して暗号化する方式のようだ。(詳細は上のWikipediaの記事や別のサイトに譲る)

http://www.dcode.fr/rail-fence-cipherに復号の仕方が載っていたので、これを参考にして復号プログラムを書いた。

#solver.py
#! /usr/bin/env python3
# coding: utf-8

def decrypt_rail_fence(text, level):
    l = len(text)
    arr = [[] for _ in range(level)]
    ans = ''

    i = 0
    up = True
    for _ in range(l):
        if up:
            arr[i].append('0')
            if i == (level - 1):
                up = False
                i -= 1
            else:
                i += 1
        else:
            arr[i].append('0')
            if i == 0:
                up = True
                i += 1
            else:
                i -= 1

    for i in range(len(arr)):
        arr[i] = [text[j] for j in range(len(arr[i]))]
        text = text[len(arr[i]):]

    i = 0
    up = True
    for _ in range(l):
        if up:
            ans += arr[i].pop(0)
            if i == (level - 1):
                up = False
                i -= 1
            else:
                i += 1
        else:
            ans += arr[i].pop(0)
            if i == 0:
                up = True
                i += 1
            else:
                i -= 1
    return ans

ten_key = {2 : 'abc', 3 : 'def', 4 : 'ghi', 5 : 'jkl', 6 : 'mno', 7 : 'pqrs', 8 : 'tuv', 9 : 'wxyz'}

text = ''
with open('crypted.txt', 'r') as f:
    for line in f:
        n = int(line.strip()[0])
        text += ten_key[n][len(line.strip())-1]

print('Cryptogram of rail fence (Decryption of original):',text)
ans = decrypt_rail_fence(text, 3)
print('Decryption of rail fence:', ans)

実行結果は

$ ./solver.py
Cryptogram of rail fence (Decryption of original): reestuisrtowebaoe
Decryption of rail fence: rubiesaretoosweet

よってflagはrubiesaretoosweet

感想

問題名(Rubies on Rails)が暗号方式のヒントになっていた。 復号プログラムはもう少しきれいに書けそう。

多次元正規分布モデルの最尤推定(準備編)

はじめに

普段CTFのWrite-upばかり上げているのでたまには違う話題を上げてみる。

大学で「パターン認識」という授業を受けていて、その中で多次元正規分布最尤推定を学んだのだけど、その計算方法や関連する微分の知識がややこしかったのでここにメモしておく。

今回は前提となる微分の知識についてまとめる。

(ネットで調べても多次元正規分布微分に関する情報は少なかったので誰かの役に立つかも…)

記法

  • $\mathbf{a}$(小文字の太字)で列ベクトルを、$\mathbf{A}$で行列を表す。なおベクトルや行列は積や和が定義できる適切な次元であり、行列は正則であるとする。
  • $a$でスカラを表し、添字($a_i$や$A_{i,j}$)でベクトルや行列の要素を表す。
  • $\mathbf{a}^\mathrm{T}$や$\mathbf{A}^\mathrm{T}$は転置、$\mathbf{A}^{-1}$は逆行列、$\mathrm{tr}(\mathbf{A})$はトレース、$|\mathbf{A}|$は行列式を表す。
  • $\mathbf{O}$を零行列、$\mathbf{I}$を単位行列とする。

ベクトルの微分

ベクトルに対するスカラでの微分

各要素を微分すればOK。結果はベクトルになる。

$$ \left( \frac{\partial \mathbf{a}}{\partial x} \right)_i = \frac{\partial a_i}{\partial x} $$

スカラに対するベクトルでの微分

スカラをベクトルの各要素で微分する。結果はベクトルになる。 $$ \left( \frac{\partial x}{\partial \mathbf{a}} \right)_i = \frac{\partial x}{\partial a_i} $$

ベクトルに対するベクトルでの微分

上2つを組み合わせて考えれば良い。結果は行列になる。 $$ \left( \frac{\partial \mathbf{b}}{\partial \mathbf{a}} \right)_{i,j} = \frac{\partial b_i}{\partial a_j} $$

内積に対するベクトルでの微分

成分計算をして求めてみると次のようになる。 $$ \begin{align} \left( \frac{\partial \mathbf{a}^{\mathrm{T}}\mathbf{b}}{\partial \mathbf{a}} \right)_{i} &= \frac{\partial}{\partial a_i} \sum_{i}a_i b_i \\ &= b_i \end{align} $$ よって $$ \frac{\partial \mathbf{a}^{\mathrm{T}}\mathbf{b}}{\partial \mathbf{a}} = \mathbf{b} $$

行列を微分

行列に対するスカラでの微分

行列の各成分をスカラで微分すればよい。結果は行列 $$ \left( \frac{\partial \mathbf{A}}{\partial x} \right)_{i,j} = \frac{\partial \mathbf{A}_{i,j}}{\partial x} $$

行列の積に対するスカラでの微分

積の微分法ぽくなる。結果は行列 $$ \frac{\partial \mathbf{AB}}{\partial x} = \frac{\partial \mathbf{A}}{\partial x} \mathbf{B} + \mathbf{A}\frac{\partial \mathbf{B}}{\partial x} $$

逆行列に対するスカラでの微分

逆行列の性質$\mathbf{A}\mathbf{A}^{-1} = \mathbf{I}$と上の行列の積の微分を使う。 $$ \frac{\partial \mathbf{A}\mathbf{A}^{-1}}{\partial x} = \frac{\partial \mathbf{A}}{\partial x} \mathbf{A}^{-1} + \mathbf{A}\frac{\partial \mathbf{A}^{-1}}{\partial x} $$ 及び $$ \frac{\partial \mathbf{I}}{\partial x} = \mathbf{O} $$ より $$ \begin{align} \frac{\partial \mathbf{A}}{\partial x} \mathbf{A}^{-1} + \mathbf{A}\frac{\partial \mathbf{A}^{-1}}{\partial x} = \mathbf{O} \\ \mathbf{A}\frac{\partial \mathbf{A}^{-1}}{\partial x} = -\frac{\partial \mathbf{A}}{\partial x} \mathbf{A}^{-1} \\ \frac{\partial \mathbf{A}^{-1}}{\partial x} = -\mathbf{A}^{-1}\frac{\partial \mathbf{A}}{\partial x} \mathbf{A}^{-1} \\ \end{align} $$

行列での微分

行列での微分は計算が複雑になる。成分計算や上の結果を駆使して頑張る。

トレースに対する行列での微分

トレースを成分表示して微分する。 $$ \begin{align} \left(\frac{\partial}{\partial \mathbf{A}}\mathrm{tr}(\mathbf{AB}) \right)_{i,j} &= \frac{\partial}{\partial A_{i,j}} \sum_i \sum_j A_{i,j}B_{j, i} \\ &= B_{j ,i} \end{align} $$ よって $$ \frac{\partial}{\partial \mathbf{A}}\mathrm{tr}(\mathbf{AB}) = \mathbf{B}^\mathrm{T} $$

ちなみに $$ \frac{\partial}{\partial \mathbf{A}}\mathrm{tr}(\mathbf{A}) =\frac{\partial}{\partial \mathbf{A}}\sum_iA_{i,i} = \mathbf{I} $$

行列式に対する行列での微分

余因子展開を用いて成分で表して微分する。

$$ \begin{align} \left(\frac{\partial}{\partial \mathbf{A}} |\mathbf{A}| \right)_{i,j} &= \frac{\partial}{\partial A_{i,j}} \sum_j A_{i,j}C_{i,j} \\ &= C_{i,j} \end{align} $$

上式で$C_{i,j}$は$(i,j)-$余因子である。ところでクラメルの法則により

$$ C_{i,j} = \{|\mathbf{A}|(\mathbf{A}^{-1})^\mathrm{T}\}_{i,j} $$

上記の結果をまとめると

$$ \frac{\partial}{\partial \mathbf{A}} |\mathbf{A}| = |\mathbf{A}|(\mathbf{A}^{-1})^\mathrm{T} $$

行列式の対数に対する行列での微分

合成関数の微分と上の結果を使う。 $$ \begin{align} \left(\frac{\partial}{\partial \mathbf{A}} \log(|\mathbf{A}|)\right)_{i,j} &= \frac{1}{|\mathbf{A}|}\left(\frac{\partial}{\partial \mathbf{A}} |\mathbf{A}| \right)_{i,j}\\ &= \frac{1}{|\mathbf{A}|}\{|\mathbf{A}|(\mathbf{A}^{-1})^\mathrm{T}\}_{i,j} \\ &= \{(\mathbf{A}^{-1})^\mathrm{T}\}_{i,j} \end{align} $$ よって $$ \frac{\partial}{\partial \mathbf{A}} \log(|\mathbf{A}|) = (\mathbf{A}^{-1})^\mathrm{T} $$

多次元正規分布微分するための準備

ここでは多次元正規分布微分するために必要となる微分を計算する。

2次形式に対するベクトルによる微分

$$ \frac{\partial}{\partial \mathbf{a}} \mathbf{a}^\mathrm{T}\mathbf{B}\mathbf{a} $$ を計算したい。$\mathbf{A} = \mathbf{a}^\mathrm{T}, \mathbf{B} = \mathbf{Ba}$として行列の積に対するスカラでの微分を用いると

$$ \begin{align} \left( \frac{\partial}{\partial \mathbf{a}} \mathbf{a}^\mathrm{T}\mathbf{B}\mathbf{a} \right)_{i} &= \frac{\partial \mathbf{a}^\mathrm{T}}{\partial a_i} \mathbf{Ba} + \mathbf{a}^\mathrm{T}\frac{\partial \mathbf{Ba}}{\partial a_i} \end{align} $$

ここで $$ \frac{\partial \mathbf{a}^\mathrm{T}}{\partial a_i} \mathbf{Ba} = \sum_j \delta_{i,j}\{\mathbf{Ba}\}_{j} = \{\mathbf{Ba}\}_i $$ ($\delta_{i,j}$はクロネッカーのデルタ。$i=j$のとき$\delta_{i,j}=1$、それ以外は$\delta_{i,j}=0$となる)

また、 $$ \begin{align} \frac{\partial}{\partial a_i} \{\mathbf{Ba}\}_{j} &= \frac{\partial}{\partial a_i} \sum_k B_{j,k}a_k \\ &= \sum_k B_{j,k}\frac{\partial a_k}{\partial a_i} \\ &= \sum_k \delta_{i,k}B_{j,k} = B_{j,i} \end{align} $$ より $$ \begin{align} \mathbf{a}^\mathrm{T}\frac{\partial \mathbf{Ba}}{\partial a_i} &= \sum_{i}a_iB_{j,i}\\ &= \sum_{i}B_{j,i}a_i\\ &= \{\mathbf{B}^\mathrm{T}\mathbf{a}\}_i \end{align} $$

以上より $$ \left( \frac{\partial}{\partial \mathbf{a}} \mathbf{a}^\mathrm{T}\mathbf{B}\mathbf{a} \right)_{i} = \{\mathbf{Ba}\}_i + \{\mathbf{B}^\mathrm{T}\mathbf{a}\}_i $$ つまり $$ \frac{\partial}{\partial \mathbf{a}} \mathbf{a}^\mathrm{T}\mathbf{B}\mathbf{a} = (\mathbf{B} + \mathbf{B}^\mathrm{T})\mathbf{a} $$

特に$\mathbf{B}$が正定値ならば右辺は$2\mathbf{Ba}$となる。

2次形式に対する行列による微分

$$ \frac{\partial}{\partial \mathbf{B}} \mathbf{a}^\mathrm{T}\mathbf{B}^{-1}\mathbf{a} $$ を計算したい。

このままでは計算しづらいので、まずは被微分値をトレースに置き換える。

$\mathbf{a}^\mathrm{T}\mathbf{B}^{-1}\mathbf{a}$はスカラであるから次の関係が成り立つ。

$$ \begin{align} \mathbf{a}^\mathrm{T}\mathbf{B}^{-1}\mathbf{a} &= \mathrm{tr}(\mathbf{a}^\mathrm{T}\mathbf{B}^{-1}\mathbf{a}) \\ &= \mathrm{tr}(\mathbf{B}^{-1}\mathbf{a}\mathbf{a}^\mathrm{T}) \end{align} $$ 2つめの等式はトレースについての関係$\mathrm{tr}(\mathbf{AB})=\mathrm{tr}(\mathbf{BA})$を使った。

よって被微分値をトレースに置き換えることができた。この値を成分で書き表して微分する。以下では簡単のために$\mathbf{a}\mathbf{a}^\mathrm{T} = \mathbf{A},\mathbf{B}^{-1} = \mathbf{S}$とする。

$$ \begin{align} \frac{\partial}{\partial {B}_{i,j}} \mathrm{tr}(\mathbf{B}^{-1}\mathbf{A}) &= \frac{\partial}{\partial {B}_{i,j}} \sum_{k,l}S_{k,l}A_{l,k} \\ &= \sum_{k,l}\frac{\partial S_{k,l}}{\partial {B}_{i,j}}A_{l,k} \end{align} $$

ここで逆行列微分を用いると

$$ \begin{align} \frac{\partial S_{k,l}}{\partial {B}_{i,j}} &= -\sum_{q,r}S_{k,q}\frac{\partial B_{q,r}}{\partial {B}_{i,j}} S_{r,l}\\ &= -\sum_{q,r}S_{k,q} \delta_{q,i}\delta_{r,j} S_{r,l}\\ &= -S_{k,i}S_{j,l} \end{align} $$

よって

$$ \begin{align} \frac{\partial}{\partial {B}_{i,j}} \mathrm{tr}(\mathbf{B}^{-1}\mathbf{A}) &= -\sum_{k,l}S_{k,i}S_{j,l}A_{l,k} \\ &= -\sum_{k,l} S_{j,l}A_{l,k}S_{k,i}\\ &= -\{\mathbf{S}\mathbf{A}\mathbf{S}\}_{j,i}\\ &= -\{\mathbf{B}^{-1}\mathbf{A}\mathbf{B}^{-1}\}_{j,i} \end{align} $$

つまり $$ \frac{\partial}{\partial \mathbf{B}} \mathbf{a}^\mathrm{T}\mathbf{B}^{-1}\mathbf{a} = (-\mathbf{B}^{-1}\mathbf{a}\mathbf{a}^\mathrm{T}\mathbf{B}^{-1})^{\mathrm{T}} $$

おわりに

かなりの分量になってしまった。特に最後の2つは式変形が怪しい部分もありなんとも言えないが結果はあっていると思う。とりあえず多次元正規分布微分する準備が整った。 次回はこの知識を利用して多次元正規分布(正確には多次元正規分布の対数尤度関数)を平均ベクトルと分散共分散行列で微分して最尤推定を計算してみる。

注意

授業で使用している資料と講義で聞いた説明を元に式を書いています。式変形等が間違っているかもしれないのでご注意ください。(個人的なメモとして読んで下さい)

誤りが見つかったら随時修正します。

参考サイト

跡數與行列式的導數

クラシックな機械学習の入門

ベクトルと行列による微分 - 緑茶思考ブログ

BCTF CTF 2015: warmup Write-up

問題

BCTF CTF 2015: warmup

チャレンジ中のリストはこちCrypto Challenges List(2015)

解答

暗号文は

c=0x1e04304936215de8e21965cfca9c245b1a8f38339875d36779c0f123c475bc24d5eef50e7d9ff5830e80c62e8083ec55f27456c80b0ab26546b9aeb8af30e82b650690a2ed7ea407dcd094ab9c9d3d25a93b2140dcebae1814610302896e67f3ae37d108cd029fae6362ea7ac1168974c1a747ec9173799e1107e7a56d783660418ebdf6898d7037cea25867093216c2c702ef3eef71f694a6063f5f0f1179c8a2afe9898ae8dec5bb393cdffa3a52a297cd96d1ea602309ecf47cd009829b44ed3100cf6194510c53c25ca7435f60ce5f4f614cdd2c63756093b848a70aade002d6bc8f316c9e5503f32d39a56193d1d92b697b48f5aa43417631846824b5e86

であり16進数表記された整数である。リンクされているwarmup-c6aa398e4f3e72bc2ea2742ae528ed79.pub.xzを解凍するとRSA公開鍵warmup-c6aa398e4f3e72bc2ea2742ae528ed79.pub(以下warmup.pub)が手に入った。

公開鍵から秘密鍵を作り出して$c$を復号すればいいようだ。

opennsslで公開鍵の中身を見てみる。

$ openssl rsa -pubin -in warmup.pub -text -noout
Modulus (2050 bit):
    03:67:19:8d:6b:56:14:e9:58:13:ad:d8:f2:2a:47:
    17:bc:72:be:1e:ab:d9:33:d1:b8:69:44:fd:b7:5b:
    8e:d2:30:be:62:d7:d1:b6:9d:22:20:95:c1:28:c8:
    6f:82:01:2e:cb:11:61:91:fd:9d:01:8a:6d:02:f8:
    4d:b2:7b:c5:1a:21:30:7d:c8:6f:4b:f7:71:c6:91:
    c1:43:e5:ab:e5:49:b5:bd:2d:6e:b1:a2:1f:d6:27:
    0e:7e:1b:48:fe:06:11:fb:b2:e1:b0:b3:52:4e:6f:
    4d:e8:b4:e4:a3:45:da:44:a1:3d:e8:25:b7:26:08:
    db:6c:7c:4a:40:b7:82:66:e6:c8:7b:bf:de:f6:b4:
    83:81:d4:9c:45:07:a5:8b:cd:47:b7:6d:64:b4:59:
    08:b1:58:bd:7e:bc:4d:ac:b0:b1:cf:d6:c2:c1:95:
    74:f4:0e:b2:ef:d0:e9:e1:0d:c7:00:5c:ad:39:bc:
    af:52:b9:ea:c3:87:33:68:d6:90:31:c5:e7:24:68:
    4a:44:f0:68:ef:d1:d3:dc:09:6d:9b:5d:64:11:e5:
    8b:de:e4:3e:46:b9:9a:0d:04:94:b9:db:28:19:5a:
    f9:01:af:f1:30:d4:a6:e2:03:da:d0:8d:a5:7f:a7:
    e4:02:62:a5:ba:db:2a:32:3e:da:28:b4:46:96:ab:
    30:5d
Exponent:
    00:f3:95:9d:97:8e:02:eb:9f:06:de:f3:f3:35:d8:
    f8:af:d7:60:99:51:dd:ac:60:b7:14:b6:c2:2a:f0:
    fa:91:2f:21:0b:34:20:6b:d2:4a:96:01:c7:8d:f4:
    a0:27:5f:10:7f:d3:ab:55:2d:95:05:7e:b9:34:e7:
    1b:dd:cd:70:45:c2:4b:18:58:7b:8c:8f:cf:5a:dd:
    4c:5d:83:f0:c7:7c:94:dc:9c:50:cb:e4:38:e2:b6:
    7b:af:d3:16:33:b6:aa:f1:78:1d:90:c3:ad:6f:03:
    d0:37:b3:32:18:01:b2:35:46:d4:83:e6:7e:26:06:
    7f:7b:22:34:7d:db:c0:c2:d5:92:ce:81:4c:bf:5d:
    fc:cc:14:14:37:f1:4e:0b:39:90:f8:80:61:e5:f0:
    ba:e5:f0:1e:3f:a7:0d:b0:e9:60:5e:7c:fd:57:5e:
    9c:81:ef:ee:c5:29:c3:3f:d9:03:7a:20:fd:8a:cd:
    51:3a:c9:63:77:68:31:3e:63:f9:83:8a:e3:51:1c:
    dd:0a:9a:2b:51:6f:21:48:c8:d4:75:a3:60:a0:63:
    59:44:97:39:ee:cd:25:1a:bb:42:b0:14:57:3e:43:
    9f:2f:a4:57:35:57:b2:56:99:ff:c1:1e:63:1c:e8:
    ee:97:5a:86:e7:e2:72:bc:f5:f7:6a:93:45:03:48:
    fe:3f

上の結果から$e$が大きいことがわかる。RSAでは$e$が大きいと$d$が小さくなるので解読できる場合がある。

攻撃方法を探すとWiener’s Attackという攻撃を見つけた。 公開鍵暗号 - RSA - Wiener's Attack - ₍₍ (ง ˘ω˘ )ว ⁾⁾ < 暗号楽しいです

連分数展開を用いて攻撃する手法のようだ。詳細は割愛(上のサイトのほかgoogleで調べると解説が多数ヒットする)。

githubにWiener’s Attackを行うプログラムがあったので利用させて頂いた。

pablocelayes/rsa-wiener-attack

上のプログラムを利用してWiener’s Attackを行い、得られた$d$を用いて復号するプログラムがこれ。

#! /usr/bin/env python3
# -*- coding  utf-8 -*-

import RSAwienerHacker
import binascii

e = int('00f3959d978e02eb9f06def3f335d8f8afd7609951ddac60b714b6c22af0fa912f210b34206bd24a9601c78df4a0275f107fd3ab552d95057eb934e71bddcd7045c24b18587b8c8fcf5add4c5d83f0c77c94dc9c50cbe438e2b67bafd31633b6aaf1781d90c3ad6f03d037b3321801b23546d483e67e26067f7b22347ddbc0c2d592ce814cbf5dfccc141437f14e0b3990f88061e5f0bae5f01e3fa70db0e9605e7cfd575e9c81efeec529c33fd9037a20fd8acd513ac9637768313e63f9838ae3511cdd0a9a2b516f2148c8d475a360a06359449739eecd251abb42b014573e439f2fa4573557b25699ffc11e631ce8ee975a86e7e272bcf5f76a93450348fe3f', 16)

n = int('0367198d6b5614e95813add8f22a4717bc72be1eabd933d1b86944fdb75b8ed230be62d7d1b69d222095c128c86f82012ecb116191fd9d018a6d02f84db27bc51a21307dc86f4bf771c691c143e5abe549b5bd2d6eb1a21fd6270e7e1b48fe0611fbb2e1b0b3524e6f4de8b4e4a345da44a13de825b72608db6c7c4a40b78266e6c87bbfdef6b48381d49c4507a58bcd47b76d64b45908b158bd7ebc4dacb0b1cfd6c2c19574f40eb2efd0e9e10dc7005cad39bcaf52b9eac3873368d69031c5e724684a44f068efd1d3dc096d9b5d6411e58bdee43e46b99a0d0494b9db28195af901aff130d4a6e203dad08da57fa7e40262a5badb2a323eda28b44696ab305d', 16)

d = RSAwienerHacker.hack_RSA(e, n)

c = int('1e04304936215de8e21965cfca9c245b1a8f38339875d36779c0f123c475bc24d5eef50e7d9ff5830e80c62e8083ec55f27456c80b0ab26546b9aeb8af30e82b650690a2ed7ea407dcd094ab9c9d3d25a93b2140dcebae1814610302896e67f3ae37d108cd029fae6362ea7ac1168974c1a747ec9173799e1107e7a56d783660418ebdf6898d7037cea25867093216c2c702ef3eef71f694a6063f5f0f1179c8a2afe9898ae8dec5bb393cdffa3a52a297cd96d1ea602309ecf47cd009829b44ed3100cf6194510c53c25ca7435f60ce5f4f614cdd2c63756093b848a70aade002d6bc8f316c9e5503f32d39a56193d1d92b697b48f5aa43417631846824b5e86', 16)

m = pow(c, d, n)

print (binascii.a2b_hex('%0512x' % m))

実行結果は

$ ./solver.py
Hacked!
b'\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00BCTF{9etRea4y!}'

よってflagはBCTF{9etRea4y!}

感想

Wiener’s Attackを行うプログラムを書こうと思ったけどうまく行かなくて既存のものを使った。暗号を勉強してる者としてWiener’s Attackはちゃんと理解しておきたい。

SECCON Quals CTF 2015: Unzip the file Write-up

問題

SECCON Quals CTF 2015: Unzip the file

チャレンジ中のリストはこちCrypto Challenges List(2015)

解答

問題名の通り渡されたzipファイルを解凍すればいい。 unzipで解凍しようとするとパスワードがかかっているようだった。

$ unzip unzip.zip
Archive:  unzip.zip
[unzip.zip] backnumber08.txt password:
   skipping: backnumber08.txt        incorrect password
   skipping: backnumber09.txt        incorrect password
   skipping: flag                    incorrect password

上の結果からzip内にはflagのほかにbacknumber08.txtbacknumber09.txtがあることがわかる。zipのパスワードはpkcrackを用いて既知平文攻撃を行うことで解読できる。そこで平文の1つであるbacknumber08.txtを探す。

googleで検索するとbacknumber08.txtはSECCONの過去のメールマガジンのようだ。 http://2016.seccon.jp/mail-magazine/text/backnumber08.txt

wgetでダウンロードしたらpkcrackで解読にかかる。予めbacknumber08.txtをzipで圧縮したbacknumber08.zipを用意しておく。

$ pkcrack -C unzip.zip -c backnumber08.txt -P backnumber08.zip -p backnumber08.txt -d dec.zip
~~~ 省略 ~~~
Decrypting backnumber08.txt (5315a01322ab296c211eecba)... OK!
Decrypting backnumber09.txt (83e6640cbec32aeaf10ed1ba)... OK!
Decrypting flag (34e4d2ab7fe1e2421808bab2)... OK!
Finished on Sat Jun 24 17:02:29 2017

解読に成功するとdec.zipができるので、解凍してflagを取り出す。

fileコマンドで調べたらflagはwordファイルだった。

$ file flag
flag: Microsoft Word 2007+

wordで開くとflagが無色で書かれていた。色をつけて確認すると

SECCON{1s_th1s_passw0rd_ weak?}

であった。

感想

以前ksnctfで同じような問題を解いていたのですぐに解けた。

解き終えた問題が溜まっているので早くWrite-upを書いて更新したい。