なぜ公開鍵暗号は安全なのか

この記事は暗号を理解して解読できるようになろうというシリーズの一部です。シリーズの一覧は次のようになっています。

• Crypto 入門
• 共通鍵暗号への攻撃
• なぜ公開鍵暗号は安全なのか
• RSA 暗号への攻撃
• 楕円曲線暗号への攻撃
• 乱数とハッシュへの攻撃
• 格子暗号への攻撃
• Crypto に使うツール

ここでは公開鍵暗号の入門とそれを応用した技術を理解します。ただ攻撃はしないので攻撃したい人はさらっと読み飛ばすといいかも。

公開鍵暗号

共通鍵暗号の問題は最初に鍵を共有するには物理的に渡す必要があり、それに関わる人を脅されてしまうと鍵を取られて解読・改ざんの一巻の終わりだからです。それを解決させるのが公開鍵暗号です。

公開鍵暗号
暗号化と復号で 別の鍵 を使い、暗号化で使う鍵を 公開 する方式
ex.) RSA暗号, 楕円曲線暗号 など

公開鍵の何が嬉しいのかと言いますと、暗号化と復号で異なる鍵を使い、暗号化で使う鍵を公開することで、誰でも暗号化できて自分以外は復号できない通信が出来ます。

これでは相手から自分への一方向だけの通信しかできませんが、通信相手も公開鍵暗号で通信すれば双方向に通信できます。

そして共通鍵暗号では復号できる鍵を渡す必要がありましたが、公開鍵暗号では一切他人に 復号する権限を渡しません。これが公開鍵暗号の真髄です。これにより共通鍵暗号より真に安全な暗号となります。

こんな公開鍵暗号ですが具体的に暗号を作ろうと思うと比較的難しいです。まずは最も有名な公開鍵暗号である RSA 暗号を紹介しましょう。

RSA 暗号

RSA 暗号とは $N$ で割った余りの世界において $e$ 乗で暗号化、 $e^{-1}$ 乗で復号する暗号です。

$$\begin{aligned} c &= m^e & \pmod N \\ m &= c^{e^{-1}} & \pmod N \end{aligned}$$

例えば $(e, N) = (3, 11)$ の上で平文 $m = 5$ を暗号化すると

$$m^e = 5^3 = 125 = 4 \pmod{11}$$

となります。逆に復号は $e^{-1} = 7$ なので

$$c^{e^{-1}} = 4^7 = 16384 = 5 \pmod{11}$$

とこのように平文と一致するので暗号として成り立っていそうです。

まぁこれだと文字列ではないですし、小さい数ですぐ攻撃されるのでぜんっぜん暗号っぽさがありません。次に文字列を暗号化してみようと思います。

例えば This is RSA という文字列を暗号化すると J\xce(\x15<D\xce\xf43\xcc\xe5\x10V\x80\r\x8d となり、復号すると This is RSA となります。

これは文字列を ASCII を用いて数にし、素数 $p, q$ を用いて $N = pq$ と $e$ で暗号化、$e^{-1}$ で復号します。

m = This is RSA = 102042840165721490081338177
c = J\xce(\x15<D\xce\xf43\xcc\xe5\x10V\x80\r\x8d = 99433297819769792809975186147967503757

p = 13787377385517866369
q = 9800301481167028771
N = pq = 135120455012699542428087034907156302499
e = 65537
e^-1 = 2799847077334116279129501281763891713

$$\begin{aligned} & m = 102042840165721490081338177 & \pmod{N} \\ & c = m^e = 99433297819769792809975186147967503757 & \pmod{N} \\ & c^{e^{-1}} = 102042840165721490081338177 & \pmod{N} \end{aligned}$$

このようにきちんと暗号っぽく機能していそうです。

これを元に手順と Python での実装をサラっと書くと次のようになります。

RSA 暗号 (Rivest-Shamir-Adleman encryption)

• 鍵生成
  1. 大きな素数 $p, q$ を生成して $N = pq$ と $\phi(N) = (p - 1)(q - 1)$ を計算する。
  2. 整数 $e$ を決めて $d = e^{-1} \pmod{\phi(N)}$ を計算する。
  3. $N, e$ を公開鍵として相手に渡し、$p, q, \phi(N), d$ を秘密鍵とする。
• 暗号化
  渡された公開鍵を用いて平文 $m$ に対して $c = m^e \bmod N$ と暗号化し、相手に送る。
• 復号
  持っている秘密鍵を用いて暗号文 $c$ に対して $m = c^d \bmod N$ と復号する。

from Crypto.Util.number import getPrime, long_to_bytes, bytes_to_long

p = getPrime(512)
q = getPrime(512)
N = p * q
phi = (p - 1) * (q - 1)
e = 0x10001
d = pow(e, -1, phi)

def encrypt(plaintext):
    m = bytes_to_long(plaintext)
    c = pow(m, e, N)
    cipher = long_to_bytes(c)
    return cipher

def decrypt(cipher):
    c = bytes_to_long(cipher)
    m = pow(c, d, N)
    plaintext = long_to_bytes(m)
    return plaintext

cipher = encrypt(b"This is RSA")
print(cipher)
plaintext = decrypt(cipher)
print(plaintext)
# This is RSA

お、出てきましたよ鍵が！(倒置法)

この公開鍵と秘密鍵がそれぞれ暗号化する鍵と復号する鍵に対応します。
本当でしょうか？確かめてみましょう！

公開鍵で暗号化
まず公開鍵 $e, N$ で暗号化することはできるでしょうか。

$$c = m^e \pmod N$$

これはちゃんと秘密鍵を使わずにできますね。

秘密鍵で復号
それじゃ秘密鍵で復号することができるでしょうか。

$$m = c^d \pmod N$$

秘密鍵 $d$ を使って復号していますね。ただ $N$ も使っているので公開鍵も必要そうです。これは秘密鍵から公開鍵は $N = pq, e = d^{-1}\bmod \phi$ と計算できるので大丈夫です。

公開鍵で復号
それでは逆に公開鍵で復号できるでしょうか。これが出来てしまうと暗号として機能していないと言えます。復号する為には公開鍵から秘密鍵 $d$ を求められればよいです。$d$ を求める為には $p, q$ が必要なので $N$ の素因数分解できると復号できてしまいます！このことを踏まえて RSA 暗号は素因数分解が出来ないくらい大きな数 $N$ を使います。実際によく使われる $N$ はだいたい $2^{1024} \approx 10^{400}$ でとっても大きな数です。

秘密鍵で暗号化
最後に秘密鍵で暗号化できるでしょうか。前と同様に秘密鍵から公開鍵を計算できるので暗号化できます。

これらを表にまとめるとこんな感じです。

	自分 (公開鍵 + 秘密鍵)	全員 (公開鍵)
暗号化	可能	可能
復号	可能	不可能

一般の公開鍵暗号

RSA 暗号は素因数分解問題が計算困難なことを用いて暗号が作られました。

素因数分解問題
ある桁数の大きい 2 つの素数の積である合成数 $N = pq$ が与えられたときに素数 $p, q$ を見つける問題。合成数のビット数に対して準指数時間で解ける。
ex.) RSA 暗号, Paillier 暗号, Rabin 暗号など

そして素因数分解問題の他にも離散対数問題という計算困難な問題が知られています。

離散対数問題
位数 $N$ が大きい巡回群 $G$ について $g, y\in G$ が与えられたときに $g^x = y$ となる最小の $x\in \mathbb{N}$ を求める問題。位数のビット数に対して指数時間で解ける。
ex.) DH 鍵共有, DSA, ElGamal 暗号, 楕円曲線暗号など

基本的にこの 2 つの NP 完全な問題を安全性の根拠として沢山の公開鍵暗号が作られます。

公開鍵の応用

公開鍵暗号は通信する以外にも様々な利用方法があります。

鍵共有

共通鍵暗号の一番のネックはそのまま鍵を共有すると盗聴されてしまうことでした。これを公開鍵暗号を用いることで安全に鍵を渡せるようになります。

今でも使われる Diffie と Hellman が考えた画期的な鍵の共有方法を紹介します。

Diffie Hellman 鍵共有

1. アリスとボブは巡回群 $G$ とその生成元 $g$ を共有する。
2. アリスとボブはそれぞれ秘密鍵 $x_a, x_b$ を生成し、公開鍵 $y_a = g^{x_a}, y_b = g^{x_b}$ を公開する。
3. 相手の公開鍵に自分の秘密鍵を掛けた $s$ はアリスとボブだけが知る共有鍵となる。
4. 数学的な値は偏りがある為にハッシュ関数を用いてランダムな数にすることで総当たりに強くする。

$$s = g^{x_ax_b} = y_b^{x_a} = y_a^{x_b}$$

署名

暗号化通信では公開鍵で暗号化されたデータを作りましたが逆に秘密鍵でデータを"暗号化"してみるとどうなるでしょうか？

暗号化通信では誰でも暗号文を作れるけれども自分しか読めないものでしたが、これは自分しか作れないが誰にでも読めるデータを作ることが出来ます。

この機能って署名の機能と同じじゃないでしょうか。さらに平文のハッシュ値を署名することで内容が改ざんされていないことを証明できるようにして一般に使えるようにしたものを電子署名という。

Def. 電子署名
本人が信頼された第三者機関である認証局に署名してもらい、その証明書が存在するなら認証されるような仕組み。

現実の署名では手書きのサインや捺印で自分であることを証明をしますがデジタルでは簡単にコピーできてしまうので公開鍵暗号を用いた電子署名が主流です。

電子署名専用のアルゴリズムもあります。

DSA; Digital Signature Algorithm
DLP ベースの署名

• 鍵生成
  1. 素数 $q$ を用いて $p = 2q + 1$ と表される素数 $p$ を生成する。
  2. $g\in\mathbb{F}_p$ と $x\in\mathbb{F}_q$ を生成して $y = g^x \bmod p$ を計算する。
• 署名
  乱数 $k$ を生成し、署名したいメッセージ $m$ を用いて $r = (g^k\bmod p)\bmod q$ と $s = k^{-1}(H(m) + xr) \bmod q$ を署名として公開する。
• 検証
  $v = (g^{s^{-1}H(m)}y^{s^{-1}r} \bmod p)\bmod q$ を計算して $r = v$ なら正当な署名となる。

練習問題
$k$ がランダムであるかはかなり重要です。
Easy: $k = m$ かつ $p, q$ 固定のとき $m$ を取り出すことができる。どうやって？ (WaniCTF DSA?)
Hard: IP 偽装を署名を用いて防ぐことはできるでしょうか？

公開鍵認証

離散対数問題

でもやっぱり実際に解こうとしてみないと難しいといっても指数時間だけ掛ければ解けるという状況が直観的に分からないと思います。素因数分解問題は次回に回すことにしてここでは離散対数問題を実際に解くことを目指します。

離散対数問題 (DLP: Discrete Logarithm Problem)
位数 $N$ の巡回群 $G$ について $g, y\in G$ が与えられるので $g^x = y$ となる最小の $x\in \mathbb{N}$ を求める問題。

暗号では有限体と楕円曲線の 2 種類の巡回群を用いたものが主流です。

• 有限体 $\mathbb{F}_p$ の DLP は FFDLP; Finite Field DLP と呼ばれる。巡回群 $\mathbb{F}_p$ の位数は $p-1$ となる。
• 楕円曲線 $E$ 上での DLP は ECDLP; Elliptic Curve DLP と呼ばれる。巡回群 $E/\mathbb{F}_p$ の位数は Hasse の定理より $|\#E/\mathbb{F}_p - (p+1)|\leq 2\sqrt{p}$ に制限される。

これらを含め、すべての巡回群を用いた問題を解きます。

Baby-step Giant-step

競プロでいう半分全列挙で解きます。

Baby-step Giant-step
$m = \lceil\sqrt{N}\rceil$ とし、DLP の解 $n$ を $m$ で割って $n = qm + r$ とおく。

$$\begin{aligned} y & = g^{qm + r} & (q, r\in[0, m-1]) \end{aligned}$$

このとき $yg^{-r}$, $g^{qm}$ を全列挙し、どちらかのリストの要素をもう 1 つのリストで検索して $yg^{-r} = g^{qm}$ となる組を探索し、$n = qm + r$ を求める。

この計算量は $O(\sqrt{N}\log N)$ で、メモリも $O(\sqrt{N})$ ほど必要となります。つまり 64 ビット素数の DLP を解くには 2.2TB 必要となります。

Pollard's $\rho$ 法

誕生日のパラドックスを用いて解きます。

Prop. 誕生日のパラドックス
誕生日が同じ 2 人を見つけたいときに確率 $P$ を超えるには人を何人集めればよいのかという問題です。鳩ノ巣原理から $366$ 人いれば必ず同じ誕生日の人が出てきます。$50\%$ を超えるには $23$ 人で十分です。

Proof.
$N$ 種類の元から $k$ 個の元を取ってきたとき $k-1$ 個までそれぞれ相違なり, $k$ 個目で同じとなる確率は $t \ll 1$ のときの近似 $1 - t\approx e^{-t}$ を行うことで次のようになる。

$$P(A) = \frac{k}{N}\prod_{i = 0}^{k-1}\left(1-\frac{i}{N}\right) \leq \frac{k}{N}\prod_{i = 0}^{k-1}e^{-i/N} = \frac{k}{N}e^{-k(k-1)/2N} \leq \frac{k}{N}e^{-k^2/2N}$$

試行回数 $k$ に対する期待値は $t = k/\sqrt{N}$ と変数変換し、ガウス積分することで求まる。

$$E(A) \leq \sum_{k=1}^N k\cdot\frac{k}{N}e^{-k^2/2N} = \sum_{k=1}^N t^2e^{-t^2/2} \leq \sqrt{N}\int_0^\infty t^2e^{-t^2/2}dt = \sqrt{\frac{\pi N}{2}}$$

よって期待値は大体 $\sqrt{\frac{\pi N}{2}}$ となる為、$N = 365$ を代入すると 50% を超えるには 23.95 人が必要となる。$\Box$

このように $N$ 種類のボールが入った袋から無作為に取ってきたら同じ種類のボールが 2 つ取れるような個数が $\mathcal{O}(\sqrt{N})$ であることを利用して計算量を落とすことを考えます。まず大枠としては次のようなアルゴリズムです。

1. 初期値 $a_0$ と決定的疑似乱数関数 $f$ を決めて数列 $a_{i+1} = f(a_i)$ を生成する。
2. $a_i = a_j$ となる $i, j\ (0\leq i<j<N)$ を発見する。
3. $a_i, a_j$ を用いて DLP を解く。

2 で見つけるのにだいたい $\mathcal{O}(\sqrt{N})$ 必要となるので数列を管理するのに平衡二分木を用いると計算量は $\mathcal{O}(\sqrt{N}\log N)$ となります。
図にすると次のような "$\rho$" の形になります。

Pollard's $\rho$ 法
巡回群 $G$ 上の $y = g^x$ のもとで初期値 $a_0 = g$ とし、関数 $f$ については $G$ を $G_1, G_2, G_3$ に振り分けて次のように定義する。

$$f(a)= \begin{cases} ya & (a \in G_1) \\ a^2 & (a \in G_2) \\ ga & (a \in G_3) \end{cases}$$

すると任意の生成元は $a_i = g^{s_i}y^{t_i} = g^{s_i + xt_i}\ (s_i, t_i \in \mathbb{N})$ と表される。ここで $a_i = a_j$ のとき

$$\begin{aligned} a_ia_j^{-1} & = g^{(s_i + xt_i) - (s_j + xt_j)} = 1 \\ x &= \frac{s_i - s_j}{t_j - t_i} & \pmod N \end{aligned}$$

となり $x$ が分かる。

Pollard-$\rho$ 法の $\rho$ は文字 $\rho$ の形が $a_i$ の由来となっています。

この派生形として 2 つの数列を作って衝突させる Pollard's Kangaroo 法 ($\lambda$ 法) もあります。

Pohlig-Hellman

有限体では $|G| = p - 1$ より

Theorem. 有限アーベル群の構造定理
巡回群の位数が $|G| = \displaystyle\prod_{i = 1}^n p_i^{e_{i}}$ と素因数分解できるとき $G \cong \displaystyle\prod_{i = 1}^n \mathbb{Z}/p_i^{e_{i}}\mathbb{Z}$ となる。

詳細は群論を学んでほしい。これより中国剰余定理から $\mathcal{O}(\max{p_i^{e_i}})$ に落ちる。

指数計算法 (Index Calculus Algorithm)

指数計算法は小さな元の離散対数問題を解くことで大きな数の離散対数問題を解く方法です。

1. $y$ に対していくつか $g$ を掛けた $yg^k$ が小さな因子基底 $p_j$ を用いて $yg^k = \displaystyle\prod_{j = 1}^m p_j^{e_{j}}$ と書けるような $k$ を見つける。
2. $g^{k_i} = \displaystyle\prod_{j = 1}^m p_j^{e_{ij}}$ と因子分解できるような $k_i$ を $n$ 個以上見つける。

すると次のように書ける。

$$\begin{aligned} g^{k_i} & = \prod_{j = 1}^m p_j^{e_{ij}} & \pmod p \\ k_i & = \sum_{j = 1}^m e_{ij}\log_g{p_j} & \pmod{p-1} \\ \begin{pmatrix} k_1 \\ \vdots \\ k_n \\ \end{pmatrix} & = \begin{pmatrix} e_{11} & \cdots & e_{m1} \\ \vdots & \ddots & \vdots \\ e_{1n} & \cdots & e_{mn}\\ \end{pmatrix} \begin{pmatrix} \log_g p_1 \\ \vdots \\ \log_g p_m \\ \end{pmatrix} & \pmod{p-1} \end{aligned}$$

これより逆行列を掛けて $\log_g p_1, \ldots, \log_g p_n$ が求まる。よって次の式より $x$ が求まる。

$$x = \log_g{y} = \sum_{j = 1}^me_j\log_g{p_j} - k \pmod {p-1}$$

計算量は $\exp((\sqrt{2}+c)(\log n)^{1/2}(\log\log n)^{1/2})$ となる。

まとめ

公開鍵暗号の基礎と応用の部分をやりました。暗号の中でもかなり不思議なものだったと思います。私も経験的に納得してるだけで直観的には納得しきれてません。なのでここで納得できてなくても大丈夫です。ここら辺は CTF をすれば咀嚼できるようになれると思います。

次はお待ちかね、CTF の中で最も出題されていると言っても過言ではない RSA 暗号への攻撃です！数学をかなり使うのでそれを補う「計算機代数」の章も参照しながらやっていくといいと思います。

参考文献

• https://www.zkdocs.com/
• ZenGo-X/zk-paillier: A collection of Paillier cryptosystem zero knowledge proofs (github.com)