CTFで使う数学　後編 - CTFと共に生きる

どうも。duckです。
後編始めるよ。

ちょっと全体的に難易度が上がるから、前編にもまして証明が雑になるよ。
よくわからんって人はとりあえずcoppersmithの定理だけみておけばいいです。
頻出なんで。
じゃあやっていこうかー。

６．coppersmithの定理　頻度「４」
これ難しいからスルーしてたんだけどCTFで出会った回数が4回目になったときに学ぶ決心をした。
定理を使う条件さえ覚えていれば後はSagemath(数学ライブラリ)が計算してくれるのであんまり気負わず。

条件　・ $N$ は素因子が未知の合成数
　　　・ $N$ の素因子 $b$ が $b \leq N ^ \beta (0 < \beta \leq 1)$
　　　・ $f(x)$ は次数 $\delta$ の1変数モニック多項式（最高次係数が１）
定理： $f(x) \equiv 0 \pmod b (|x| \leq cN^{\frac{\beta^2}{\delta}})$ を満たす解 $x$ は簡単に求まる。

定理の使い方例
① $b \leq N ^ \beta$ から $\beta$ を求める。
② $(|x| \leq cN^{\frac{\beta^2}{\delta}})$ から（c=1とでもしておくとよい）簡単に求まる $x$ の範囲を求める。
③この範囲に求めたい値が含まれれば上の定理を使う。

sagemathコード例

sage: N = 1279012345679004320987654321
sage: K = Zmod(N)
sage: PR.<x> = PolynomialRing(K)
sage: f = x^2 + 78523430
sage: f.small_roots()

small_roots()関数がcoppersmithの定理の計算を勝手にやってくれて、答えの集合の配列を返す。
数字は適当なので気にしないで。ちなみにsmall_roots()は引数も持たせられる。

f.small_roots(X=2^kbits, beta=1/3)

$X$ は解 $cN^{\frac{\beta^2}{\delta}}$ のこと。

この定理にまつわる自身の論文を快く提供してくださった同期Kに感謝します。
証明は1ミリもブログに書いてないけどな。すまんな。

７．平方剰余　頻度「１」
今のところで出会ったことがほとんどない。

定義： $x^2 \equiv a \pmod N$ となる $x$ が存在するとき $a$ は $N$ を法とする平方剰余であるという。

定理： $a$ が $N$ を法とする平方剰余かどうかは簡単にわかる。

端的に言うと $\mod N$ の世界で $\sqrt{a}$ が存在するかはすぐわかるということ。
証明は平方剰余の相互法則によるが、書かない。
sagemathでの使い方を述べるにとどめる。

#kronecker(a,N)
#1なら平方剰余
sage: kronecker(2,7)
1
#-1なら平方非剰余
sage: kronecker(3,7)
-1
#あるNでの平方剰余が全部知りたいとき
sage: quadratic_residues(7)
[0, 1, 2, 4]

８．中国剰余定理　頻度「３」
まあまあでる。直接ではなくても間接的によくお世話になる。

定理：連立合同式
$x \equiv a_1 \pmod {m_1} \\ x \equiv a_2 \pmod {m_2} \\ \quad \vdots\\ x \equiv a_n \pmod {m_n}$
の解 $x$ は $\gcd(m_i,m_j)=1$ ならば $0 \leq x < m_1 m_2 \cdots m_n$ の中に唯一存在する。

答えとなる $x$ を構成することで証明とする。（唯一性の証明は省略）

$m_{ij}^{-1}$ とかいたらそれは $m_i$ の $j$ における逆数という意味で使う。

Garner 法
$x_1 \equiv a_1 \pmod {m_1}$ となる $x_1$ をとってくる。
$x_2 = x_1 + m_1 t_1$ とおき、 $x_2 \equiv a_2 \pmod {m_2}$ となるように $t_1$ を決める。
つまり $x_1 + m_1 t_1 \equiv a_2 \pmod {m_2}$ より $t_1=(a_2-x_1){m_{12}}^{-1}$ とする。
このとき $x_2 \equiv a_1 \pmod {m_1}$ かつ $x_2 \equiv a_2 \pmod {m_2}$
$x_3 = x_2 + m_1 m_2 t_2$ とおき、・・・以下繰り返し。

イメージとしては連立合同式の上から順番に満たすように $x_i$ を拡張していく感じ。

コード：

def inverse(a,N):
    return extend_gcd(a,N)[0] % N

def chinese(a_list,m_list):
    n=len(a_list)
    x=a_list[0]
    m=m_list[0]
    i = 1
    while i < n:
        x=x+(a_list[i] - x) * inverse(m,m_list[i]) * m
        m*=m_list[i]
        i+=1
    return x % m

gcd,extend_gcdは自分で定義した関数。詳しくは前編参照。
CTFで使う数学前編 - CTFと共に生きる

重要な例としてRSA暗号の復号計算を高速化するのに使われているが、それは”暗号まとめ”記事にまとめようと思う。

９．オイラーの定理　頻度「1」
フェルマーの定理の拡張。
まずオイラーのトーシェント関数の定義（ファイ関数ともいう）。

定義：自然数 $N$ と互いに素で1以上 $N$ 以下となるものの自然数の個数を $\varphi (N)$ で表す。

本題。

定理： $a,N$ が互いに素ならば $a ^{\varphi(N)} \equiv 1 \pmod N$

証明概略： $N$ と互いに素な数の集合 $A=\{r_1,r_2,\cdots,r_{\varphi(N)}\}(1 \leq r_i \leq N)$ と $B=\{ar_1,ar_2,\cdots,ar_{\varphi(N)}\}$ の集合は $N$ を法として等しい。
なぜならば $ar_i$ は $N$ と互いに素であるから $ar_i \bmod N = r_j$ ( $A$ の集合の要素のどれかと一致)であり $ar_i \not \equiv ar_j \pmod N$ 。(*)
よって $a ^ {\varphi(N)} r_1 r_2 \cdots r_{\varphi(N)} \equiv r_1 r_2 \cdots r_{\varphi(N)} \pmod N$ 。