ぺんぎんさんのおうち

日本語勉強中のドイツ産ペンギンがいろんなことを書く

InterKOSENCTF (2019) strengthened 供養

Write-upを堂々と公開できるほどのスコアでもないため, 供養としてあげておく.

問題の概要

問題のソースコードからまずは以下が読み取れる.

  • nが2048 [bits]
  • eが3
  • c := pow(flag, e, n)
  • flagはKOSENCTFから始まる

eが3とかなり小さいので, cの3乗根を取れば終わりかと思いきや,

while pow(m, e) < n:
    m = m << 1

によって me > n とされるため3乗根をとっても意味がない.
が, 左シフト演算が右に0をパディングしているだけと考えるとmは以下のように表せる.

m = flag || {0}^k

つまり 平文の下位ビットのほとんどが0 である.
これだけわかればなんとインターネットの海を漂うことで解けてしまう.

RSA 平文のほとんどのビットがわかっている」 のようなクエリで検索すれば出てくるだろう.

おしまい.

解法

おしまい. ではない.
ここからはCoppersmith's Theoremについて軽く触れ, 実際のsolverについて解説する.


Coppersmith's Theorem

モニック多項式1 f(x)において, 根が剰余Nのd乗根以下であれば高速に求めることができる. dは多項式の次数.

つまり $$ f_{N}(x_{0}) = 0 $$

上式を満たす \(\boldsymbol{x_0}\)を効率的に求められる.

今回の問題においては flag < n^(1/3) を満たしているという前提で解くことになる.


問題における多項式

まずは問題を安直に解けなくしている諸悪の根源を確認する.

m := m << 1

1ビットの左シフトが2倍演算であることを考えると, kビット左シフトは

m := m << k 
-> m = m * 2^k

と一般化できる.

暗号化の部分を詳しく表記すると

\begin{eqnarray} m^{e} & \equiv & c \, mod \, N \newline {(flag*2^{k})}^{e} & \equiv & c \, mod \, N \end{eqnarray}

これを書き換えると

\begin{eqnarray} {(flag*2^{k})}^{e} + t*N & = & c \newline {(flag*2^{k})}^{e} - c & = & 0 \end{eqnarray}

t = 0としてNを消している. これについてはちゃんと意味があるのだが, ここでは省略する.

以上より, 解くべき多項式は次のようになる.

$$ f_{N}(x) = (x * 2^{k})^{e} - c $$

あとはこれをsage神に投げると解いてくれる. ただしkは不明なのでここだけ全探索. 暗号化する前のmは約700bitsになるはずなので, それを考慮するといいかもしれない.


solver

n = 略
c = 略
e = 3

beta = 1
for k in range(2, 500):
    PR.<x> = PolynomialRing(Zmod(n))
    f = (2^k * x)^e - c
    f = f.monic()

    xs = f.small_roots(X=2^450, beta=beta)
    for x in xs:
        m = 2^k * x
        if pow(m, e, n) == c:
            print 'k =', k
            print 'm =', hex(int(m))
            print 'x =', hex(int(x))
            print

まとめ

暗号って面白いですね.

ykm_crypto/easy/p1 にこの問題を少し改良したものを公開している. 興味があれば解いてみて欲しい.



1: 最高次数の係数が1の多項式