RSA暗号

概要

　今日は有名なRSA暗号問題について見ていきたい。

RSA暗号とは

RSA暗号とは、何かについて書かれた記事は山ほどあると思うが、一応簡単にここに説明書きを書く。

まず、RSA暗号はいわゆる「公開鍵暗号」、すなわち暗号化に公開鍵を用いて、復号化には秘密鍵を用いることで、お互いに保持しなければならない秘密の鍵というものをなくすことができる。

ポエム的なことを言えば、社会のあらゆる場所で使われていて、情報化社会の縁の下の力持ち。

逆に言えば、これだけ信頼されている仕組みなので、基本的には、「正しい使い方をされていれば解くことが不可能」と言っていい。つまり、RSA暗号問題はその暗号化復号化や、素数判定などどこかに、「本来あってはならない使い方」が為されていて、それをどう攻撃できるか？というのが焦点となる。

まずは、RSA暗号を（僕が分かるレベルの）数学的観点で捉えた後、実際にRSA暗号の実装（と言っても素数生成にpycryptoを使ったりするが）っぽいことをして、最後はRSA関連CTF問題を眺めていくことにする。

RSA理解のための数学

　このパートは基本的に「暗号理論入門」（J.A.ブーフマン）の第３章に基づく。

同値関係

　同値関係(\sim)とは、

反射律 (a\sim a)
対称律 (a \sim b \Longrightarrow b \sim a)
推移律 (a \sim b, b \sim c \Longrightarrow a \sim c) が成立するものである。例えば、自然数mのあまりの関係、すなわち合同式は同値関係である。

群

空でない集合$H$と、$H$上で閉じていて、結合法則を満たす演算子$\circ$の組$(H, \circ)$を半群という。

すなわち、$a, b, c \in H$に対して、

$(a \circ b) \circ c = a \circ (b \circ c)$ が成立する。さらに任意の$a \in H$に対して、$e \circ a = a \circ e = a$を満たす元$e \in H$となる単位元$e$、および$a \in H$に対して、$b \circ a = a \circ b = e$となるものがあれば、$b \in H$となる$a$の逆元$b=a^{-1}$が存在するような$H$を群という。

既約剰余類・既約剰余群

上記した同値関係によって、集合は”グループ分け”することができる。剰余類とは、自然数mによるあまりによってグループ分けしたものであり、例えば、$m$の場合は$0 + mZ, 1 + mZ, \cdots , m - 1 + mZ$のようにm個のグループに分けることができる。

ここで既約剰余類というものを考える。

定義

$gcd(a, m) = 1$である剰余類$a + mZ$を既約剰余類という。

これを考える意義は、剰余類がいつ剰余環$Z/mZ$において逆元を持つか、という点である。

定理

剰余環$Z/mZ$において、剰余類$a + mZ$が可逆元を持つための必要十分条件は、$gcd(a, m) = 1$である。逆に、$gcd(a, m) = 1$であれば、$a + mZ$の逆元は一意に定まる。

この定理より、既約剰余類とは、$Z/mZ$における可逆元ということになる。

定理

$Z/mZ$における既約剰余類の集合は、乗法に関する有限な可換群となる。

この群を$(Z/mZ)*$と書き、既約剰余群という。またこの群の位数を$\phi(m)$と表す。ただし、$\phi$はオイラーのトーシェント関数である。$\phi(m)$は${1,2, \cdots, m}$のうちの$gcd(a, m) = 1$となるaの数を表す

部分群

空でない$H \subset G$が$G$の部分群であるとは、$G$の演算$\circ$について、$H$地震で群をなしていることをいう。

群の元の位数

群の元$g$の位数とは、$g^e = 1$を満たす最小の自然数eのことである。このような自然数がない場合、位数は無限大である。

巡回群

ある$g\in G$について、${g^k ; k \in Z}=$をgにより生成された部分群という。gの位数が有限次数$e$の場合、$$の位数はeである。

ある$g\in G$について$ = G$のとき、$G$は巡回群といい、$g$は$G$の生成元であるという。

定理

Gが有限巡回群であれば、Gはちょうど$\phi(

)$個の生成元を持ち、その生成元は位数$

を持つ

ラグランジュの定理

$G$が有限群であるとき、$G$の任意の部分群の次数は$G$の次数を割り切る。

フェルマー小定理

$gcd(a, m)=1$ならば、$a^{\phi(m)}\equiv 1\bmod m$が成立する　　

RSA暗号

　次にRSA暗号について考える。RSA暗号とは、秘密鍵に二つの素数$p, q$及び、$n = pq$を法とした時のある数$e$の逆元$d$を秘密鍵とし、$(n, e)$を公開鍵として使う。具体的な手順は次の通りである

素数生成

素数$p, q$を生成する。この二つの数の合成数が因数分解できないことが安全性の根拠であるため、短すぎると破られてしまう

自然数$e, d$の生成

$e$は、 $1 < e < \phi(n) = (p-1)(q-1) $ かつ$gcd(e, \phi(n)) = 1$を満たすようにとる。よく使われるのは、0x10001である。

$d$は、nを法とする時の逆元であり、拡張ユークリッドの互除法などを用いて$e, p, q$から計算して求める。

暗号化

平文を$m$とする。このとき、暗号化は $c = m^e \bmod n\ (n = pq)$ によって行われる。このとき、eの累乗は高速化のため、バイナリ法が用いられる。バイナリ法が何か知っている人は、mnemo.proの累乗ハードでもときましょう。

ところで、この暗号化は、全て公開されている値で完結している($e, n$による）。暗号化には秘密の鍵を使わずともすみ、しかも公開鍵で一度暗号化したものは戻せない、というのが公開鍵暗号の特徴である。

バイナリ法

[TODO]

復号化

これは簡単で

$m' = c ^ d$ による。

これは、秘密鍵dを用いる必要があり、理論上この鍵ペアを生成した人しか解くことはできない。

復号化により暗号文がもとにもどることの証明

$c = m^e \bmod n\\ m' = c^d \bmod n$ より、 $m' = (m^e)^d \bmod n\\ = m^{ed} \bmod n$ $ed \equiv 1 mod \phi(n)$となるように$d$をとったので、

$= m^{k\phi(n) + 1} \bmod n\\ = (m^{\phi(n)})^{k} * m \bmod n\\ = m$ より示された。

問題

　前回に引き続き、RSAに関連してそうな問題を@elliptic_shihoさんのCrypto Challenge Listから探した。難易度表示は、ここに記されているもの。　

[Medium Easy]Twin Primes(Tokyo Westerns/MMA CTF 2nd)

概要

まずプログラムを観察すると、次のことがわかる。

双子素数を二組み(p, p+2), (q, q+2)得る
$n_1 = p q$ 、$n_2 = (p+2)(q+2)$と$e=65537$を公開鍵として二回RSA暗号によって暗号化する
手に入るのは、二つの公開鍵、すなわち$n_1, n_2, e$及び、暗号化されたデータ

方針

未知数$p,q$に対して、二つの式が得られるので、当然$p, q$が得られる。

$\begin{array}{l} n_1 = pq\\ n_2 = (p+2)(q+2) = pq + 2(p+q) + 4\\ n_2 - n_1 = 2(p+q) + 4 \end{array}$

したがって、 $p+q = \frac{n_2 - n_1 - 4}{2} = b$

以上から、$p+q$と$pq$がわかるので、

$(x - p)(x - q) = x^2 - bx + n_1$ を解けば、RSA暗号の安全性の根幹である素因数分解ができてしまう。

実際これだけである。僕の解答スクリプトは、docs/03/problems/problem1/solve.pyにある。

[Medium]High-speed RSA Keygen(Sharif University CTF)

概要

コードが汚い（どうでもいいけど）。

get_primesはエラトステネスのふるい
$k_p$は20ビット長の乱数
443までの素数（ただし2を抜く）を掛け合わせてこの値を$p_i$とすると$gcd(t_p, p_i)=1$となるような、$t_p$を$[1, 2^{399})$から探してくる。すなわち$t_p$は399ビット長
$(k_p p_i ) « 400 + t_p$という数が素数かをミラーラビン素数判定法で調べる
見た感じこれが素数であることはほぼ確か
この方法で、$p, q$を生成する

方針

$pi$が既知だったりするので、元の鍵が推測可能かなあと思える。方針は次の通りである。

$p = tp + 2^{400} * pi * kp\\ q = tq + 2^{400} * pi * kq$ であり、今、 $n = pq$ がわかっている。実際にこの$n$がどのように計算されているのかを考えると、

$n = (tp + 2^{400} * pi * kp)(tq + 2^{400} * pi * kq)\\ = (kp*kq*pi^2 * 2^{800} + (tp * kq + tq * kp) * pi * 2^{400} + tp * tq)$ となる。

ここで、各項の係数として結構大きく互いに素な数がくっついていることに着目すると、

$kp\_kq = n / (pi^2 * 2^{800})\\ n_2 = n % (pi^2 * 2^{800})\\ \\ c = n_2 / (2^{400} * pi) d = n_2 % (2^{400} * pi)$ とすると、これらは、 $kp\_kq = kp * kq\\ c = tp * kq + tq * kp\\ d = tp * tq$ となる。

ここで重要となるのは、$kp_kq$が大して大きな数字ではないという事実である。再び上を参照すれば、「$k_p$は20ビット長の乱数」と書いたが、ここで生成部分をよくみてみれば、乱数となるのはたかだか12ビットである。すなわち、因数分解がたかだか$2^12$の回数で可能であることを意味する。

つまり、$kp$と$kq$が得られる。すると、さっき導いたもう二つの式を見ると、

$c = kq * tp + kp * tq d = tp * tq$ という式が見える。tp, tqは400ビットの乱数であり、さすがにこれを総当たりするのは不可能であったが、今連立方程式として得ることができたので、あとは解けば良い。

以上から、

$p = tp + 2^{400} * pi * kp\\ q = tq + 2^{400} * pi * kq$

を用いて、$n = pq$が素因数分解できたことになる。あとはRSAの復号化をすれば答えを得られる。

スクリプトはdocs/03/problems/problem2/solve.pyである。

[Medium Easy]Creative Cheating(Hack.lu CTF 2015)

概要

pcapファイルが与えられ、どうやらAliceとBobの通信らしい（とはいうもののAliceが一方的にBobにメッセージを送りつけ続けているので、Aliceはメンヘラかもしれない）
また問題文を読むと、AliceとBobの公開鍵が与えられ、これは明らかに短いので因数分解可能
pcapの中身を見ると、
```
SEQ = xx; DATA = xx; SIG = xx;
```
という形式で、データを送りつけている

方針

DATAはBobの公開鍵でAliceが暗号化したもの、逆にSIGはAliceがBobに自分の秘密鍵で暗号化した署名だと考えられる。したがって、まず、Dataを復号化するために、Bobの鍵を因数分解すると

sage: factor(0x99122e61dc7bede74711185598c7)
49662237675630289 * 62515288803124247

が得られるので、これをもとに、秘密鍵を逆算する。

ところで、一つのSEQに大していくつか(Data, Sig)の組みがあり、ここから、いくつかがダミーであることが推察できる。つまり、Sigを用いてAliceの署名を確認する（Aliceの鍵が弱すぎてこのデータ自体も偽られていそうなものだが）。

以上より、フラグを得る。

解答スクリプトはdocs/03/problems/problem3/solve.py

電子署名

このように、RSA暗号は電子署名に使うことができる。RSA暗号で、Aliceしか知らない秘密の鍵dを用いて、ある証明するための文mを暗号化するとき、

$c \equiv m^d (mod n)$

となるが、第三者はこれをAliceの公開鍵(e, n)のみを用いて

$c^e = m^(ed) \equiv m (mod n)$

を計算可能である。これが電子署名の原理である。

終わりに

来週は授業が無いのでやりません。再来週にもう一回RSA回をやります。今度はもう少し難しい問題についてやっていきたいと思います。

参考

群論におけるフェルマーの小定理
公開鍵暗号 - RSA - 基礎 - ₍₍ (ง ˘ω˘ )ว ⁾⁾ <; 暗号楽しいです
公開鍵証明書 - Wikipedia
暗号理論入門原書第3版（ブーフマン）