神のミソ汁のセカイ

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

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