公開鍵暗号 - RSA - 基礎

公開鍵暗号

2018/10/22 全体的に問題があったので書き直した. 内容はほぼ変わっていない.

本記事では, 世界で最初に提案された公開鍵暗号であるRSA暗号の基礎事項について解説する. RSA暗号の動作原理について示した後, 簡単な攻撃手法の一覧を載せる.

公開鍵暗号

暗号理論, 特に現代暗号における暗号は「秘密鍵暗号(Secret-key Cipher)」, 「公開鍵暗号(Public-key Cipher)」の2種類に大分される. 秘密鍵暗号はよく知られている通り「秘密の鍵$k$を事前に共有しておき, その鍵を用いて暗号化・復号を行う暗号方式」である. これに対して公開鍵暗号は「暗号化に用いる鍵$k _ {enc}$, 復号に用いる鍵$k _ {dec}$が存在し, 暗号化・復号のそれぞれで異なる鍵を用いる暗号方式」と定義され, このうち$k _ {enc}$は一般に公開されることが多いことが「公開鍵」の所以である. 鍵が分かれているため, 復号することができる人は$k _ {dec}$を持つ人のみであることから, このようにすることで世界中の人々が暗号化した文書を$k _ {dec}$を持つ人に対して自由に送ることができるようになり, 事前に鍵を受け渡す手間を省くことができる. この$k _ {enc}$を公開鍵, $k _ {dec}$を秘密鍵と呼ぶ.

RSA暗号

RSA暗号[1]は世界で初めて提案された公開鍵暗号であり, 提案者であるRivest, Shamir, Adlemanそれぞれの名前をとって呼ばれている. この暗号の安全性は「大きい合成数の素因数分解問題は難しい」という仮定に基づいている.

原理

RSA暗号における公開鍵, 秘密鍵を定義し, その原理について解説する.

まず最初に素数$p$, $q$を選ぶ. これは$p\ne q$でなければならない.　また, 必ずランダム性があり, 偏りがないようにしなければならない. この$p$, $q$について$n = pq$とおく. $e$を$(p-1)(q-1)$と互いに素であるように選び, $ed\equiv 1\pmod{(p-1)(q-1)}$を満たすような$d$を計算する.

このとき, RSA暗号の公開鍵は$(n, e)$, 秘密鍵は$(n, d)$と定義される.

暗号化

平文を$m\in\mathbb{Z}$, $0\leq m\lt n$としたとき, RSAの暗号化関数は以下のように定義される:

$$ Enc(m) := m ^ e \mod n $$

復号

暗号文を$c\in\mathbb{Z}$, $0\leq c\lt n$としたとき, RSAの復号関数は以下のように定義される:

$$ Dec(c) := c ^ d \mod n $$

さて, 暗号が暗号として成立するためには「暗号化して復号したら元に戻る」ことが必要である. このことをチェックするために$Dec(Enc(m)) \equiv m\pmod n$を示す. このためには以下の定理が必要になる.

Thm. 1 (Euler).

$n$を正の整数, $x$を任意の整数としたとき, $x$と$n$が互いに素ならば$x ^ {\phi(n)} \equiv 1 \pmod n$. ただし$\phi(n)$は$n$と互いに素な$1$以上$n$未満の整数の個数を表す(Euler Totient関数).

(証明略)

例として, $p$を素数としたときに$p$と互いに素な数は$p-1$個存在するため$\phi(p) = p-1$である($1, 2, ..., p-1$). すると$p$と互いに素な整数$a$について$a ^ {p-1}\equiv 1\pmod p$であることがわかる. これは実はFermatの小定理として知られる定理であり, このEulerの定理はその拡張であるといえる.

では, $n = pq$と互いに素な数の個数を考えてみよう. $p, 2p, \ldots, (q-1)p$がまず$n$と互いに素ではない. $q$についても同様に$q, 2q, \ldots, (p-1)q$が互いに素ではない. $n$の素因数は$p$, $q$の2つだけなのでこれで互いに素ではない数は全て. よって$(p-1)+(q-1)$通りの数が$n$と互いに素ではないことがわかる. 0を除外するために1引いていることに注意し, 互いに素な数の個数を計算すると以下のように計算できる:

$$ \begin{aligned} \phi(n) &= n - ( (p-1) + (q-1) - 1)\newline &= n - (p+q) + 1\newline &= p(q - 1) - (q - 1)\newline &= (p-1)(q-1). \end{aligned} $$

このことから, RSA暗号が正しく復号できることは以下のように示される:

$$ \begin{aligned} Dec(Enc(m)) &\equiv (m ^ e) ^ d\newline &\equiv m ^ {ed}\newline &\equiv m ^ {1 + k(p-1)(q-1)} & (\mathrm{where}\ k\in\mathbb{Z})\newline &\equiv m ^ 1\cdot (m ^ {(p-1)(q-1)}) ^ k\newline &\equiv m ^ 1\cdot 1 ^ k\newline &\equiv m\cdot 1\newline &\equiv m\pmod {n}. \end{aligned} $$

ただし, $m ^ {(p-1)(q-1)}\equiv 1\pmod n$はEulerの定理を用いた. また, $ed\equiv 1\pmod {(p-1)(q-1)}$よりある$k\in\mathbb{Z}$が存在して$ed - k(p-1)(q-1) = 1$という事実を用いた.

$0\leq m\lt n$という制約があるので, $Dec(Enc(m)) = m $がこれでいえたことになる.

攻撃

単純な素因数分解

$p$, $q$のいずれかが判明したときに$d$を計算することができるようになるという事実から, まずは単純に素因数分解してしまえばよいのでは?という疑問が浮かぶ. 今実際に運用されているRSA暗号では少なくとも$2 ^ {1024}$通りの範囲を全探索するのに匹敵する計算量が必要になる程度の大きさの素数が用いられているためにあまり問題にはならないが, $p, q$の間に関連性があったり, 特殊な形の合成数に対して適用可能な素因数分解の手法(Pollard Rho法やFermat法等が挙げられる)を適用することで素因数分解できてしまう場合がある.

過去の事例として, DebianのOpenSSLの脆弱性により鍵生成された後の公開鍵$(n, e)$のパターンが高々32768通りと比較的少なく(= 秘密鍵が推定または総当りできてしまう)なってしまったことがある (CVE-2008-0166)[3]. また, たくさんRSA鍵を集めてたまたま同じ素数が使われているものをBirthday Paradoxに期待して探す攻撃手法も実際に効果が無いわけではないことが示されている[2].

Low Private-Exponent Attack

秘密鍵dが小さい時に$(n, e)$から$d$を計算することができる攻撃の総称. 有名なものにWienerが[9]で提案した $d < \frac{n ^ \frac{1}{4}}{3}$ のときに $e, n$ から $d$ を求められる攻撃や, Boneh-Durfeeによる $d < n^{0.292}$ のときに $e, n$ から $d$ を求められる攻撃[6]がある.

Common Modulus Attack

$m, n$が共通, $e$が異なるいくつかの$(e, n, Enc(m))$の組があるとき, mを計算することができる攻撃.

Common Private Exponent Attack

秘密鍵 $d$ が等しく, 公開鍵 $e, n$ が異なるような公開鍵が複数存在する時, 共通する $d$ を求めることが可能な攻撃. [11]

Hastad's broadcast Attack

$n$が異なり, $e$と平文が同じ複数の暗号文/公開鍵 $(n_1, e, c_1), (n_2, e, c_2), ..., (n_k, e, c_k)$ が十分な数あるとき, 元の平文を求めることができる攻撃. $c _ i = m ^ e \mod n _ i$とすると解 $x = m ^ e$ を持つ剰余連立方程式$x\equiv c_i\pmod{n_i}$を立てることができ, この解が中国人剰余定理によって求まることでmodのかかっていない$me$が計算できる. 後は$e$乗根を取ればよい.

このことから最低限必要な暗号文の数は 「$m ^ e < \prod _ i {n _ i}$ が成立する最小の$i$」である. $n_i$の大きさを考えると$e$個ほど集めればよい.

Franklin-Reiter Related Message Attack

ある平文$m_1$について既知の定数$a$, $b$があり$m_2 = am_1 + b$とする. このとき, その暗号文$c_1, c_2$があるとき, $(n, e, c_1, c_2)$から$m_1$を導出できる攻撃. $e=3, 5$の場合はWikipediaに載っているが, 実はこれはメッセージの数, 関数も一般化が可能である. 詳細は[7].

Coppersmith's short pad Attack

ある平文$ m $があり, $k = \lfloor\frac{n}{e^{2}}\rfloor$とする. 暗号化する平文$m_1, m_2$を$m_1 = 2^{k} m + r_1$, $m_2 = 2^{k} m + r_2$とし, それぞれの暗号文$c_1, c_2$があるとき, $n, e, c1, c2$から$ m $を導出できる攻撃.

Partial-key exposure Attack / High-bit known Attack / Low-bit known attack

$d, p, q$等の秘密鍵にあたる部分の一部が漏洩した時に全体を復元することができるという攻撃. 有名な所ではpの上位/下位ビットが十分な量($p ^ 0.5$程度)漏洩しているとき$e, n, pの一部$から$p$全体を復元できる High-bit known (下位ビットの場合はLow-bit known) Attackがある. $d$の一部の場合は特にPartial-key exposure Attackと呼ばれる.

LSB Leak Attack

暗号文に対して復号した値の偶奇が分かるとき, 二分探索によって元の平文を求めることが可能な攻撃.

参考文献