読者です 読者をやめる 読者になる 読者になる

公開鍵暗号 - RSA - 基礎

この記事では、公開鍵暗号の先駆けとして非常に有名なRSA暗号とその原理、幾つかの攻撃手法についての解説を書く。個々の攻撃手法については後々書いていく予定だ。

公開鍵暗号

公開鍵暗号について一通りの説明をする。我々が普段暗号と呼ぶものは、基本的に暗号化と復号に同じ鍵を利用する。DES, AES等の暗号が例として挙げられる。これらは暗号化と復号に"共通"の鍵を利用しているため、共通鍵暗号と呼ばれる。対して、今回解説するRSA暗号Elgamal暗号、NTRU暗号等は暗号化に使用する鍵と復号に使用する鍵が異なる。この時、片方の鍵を"公開"し、自分宛のメッセージは全てその鍵で暗号化してもらうことにする。そうすると、もう片方の鍵は公開していない(つまり、"秘密"な)ため、その鍵で復号することで公開鍵を知るだけで安全にメッセージを送ることができる。このように片方の鍵を公開し、もう片方を秘密にするタイプの暗号を公開鍵暗号と呼ぶ。一般に、公開鍵暗号は計算コストが高いため、例えば鍵の交換にRSAを利用し、そうして交換した鍵を用いてAES-128-GCM等の共通鍵暗号を用いた暗号化通信を行うTLSSSH等も考案され、これらをハイブリッド暗号と呼ぶ。

RSA暗号

RSA暗号は、Rivest, Shamir, Adlemanの3人によって共同で作成された初めての公開鍵暗号の形態を取る暗号だ。巨大な整数の素因数分解が困難であることを安全性の根拠としており、次のように定義される。

パラメータ

パラメータp, q, n, eを決める。p, qはそれぞれ素数で、\(n=pq\)である。また、\((p-1)(q-1)\) と \(e\) は互いに素でなければならない。 この時、p, qはそれぞれ十分に巨大でなければならない。現在では768bitの素因数分解が成功していることや、1024bitの素因数分解も近いと噂されていること等からしても実用上は2048bit以上を使用するのが好ましい。 また、p, q, n, eからもう一つの値dを計算する。この値は、\(d \equiv e^{-1} \mod (p-1)(q-1)\)で計算される、法(p-1)(q-1)上でのeの逆元(eにかけると1になる値のこと。有理数で考えるなら、2に対する逆元は\(\frac{1}{2}\)になる。いわゆる逆数)になる値だ。

「\((p-1)(q-1)\) と \(e\) は互いに素」の条件が必須な理由は、互いに素で無い場合法(p-1)(q-1)上での逆元を計算することが出来ない(つまり、dの計算ができない)からだ。

以上で作られたパラメータのうち、n, eを公開鍵、dを秘密鍵とする。p, qが分かってしまうと、dを計算することが出来てしまうため、dの生成後に破棄されるのが望ましい。

p, qの生成は必ずランダム性があり、偏りがあってはいけない。「偏り」の具体的な例を挙げると、過去にDebianのOpenSSLの脆弱性で、鍵生成された後の公開鍵(n, e)のパターンが高々32768通りと比較的少なく(= 秘密鍵が推定または総当りできてしまう)なってしまったことがある。(CVE-2008-0166)

暗号化

平文をmとした時、RSAの暗号化関数は以下のように定義される。

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

復号

暗号文をcとした時、RSAの復号関数は以下のように定義される。

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

根拠

なぜ、この関数を使用することで公開鍵暗号を実現できるのか?また、なぜnの逆元ではなく(p-1)(q-1)という謎の値で逆元を取るのか?というような疑問が出るかと思う。 そのためには、フェルマーの小定理とそれを一般化したオイラーの定理を知らなければならない。ここでは証明を略するので、興味が有るようなら、参考文献を参考にして見て欲しい。

フェルマーの小定理

pが素数、\(x\in \mathbb{Z}\)なら、「$x$ と $p$ が互いに素ならば \(x^{p-1} \equiv 1 \mod p\)」が成り立つ。

p-1という値が出てきた。この値は、pと互いに素な数の個数を表している。なぜならば、pは素数であり、p-1までの全ての数は全てpと互いに素なので、pを除くp-1個の値がpと互いに素だからだ。

オイラーの定理

ある正の整数nがあり、\(x\in \mathbb{Z}\)なら、「$x$ と $n$ が互いに素ならば \(x^{\phi(n)} \equiv 1 \mod n\)」が成り立つ。

フェルマーの小定理とはどこが違うだろうか。nが素数という縛りが無くなり、p-1が\(\phi(n)\)という関数に変わった。\(\phi(n)\)とは、nと互いに素な数の個数を表す関数である。例えばnが素数だったとすれば、\(\phi(n) = n-1\)になり、フェルマーの小定理と一致する。この定理は、フェルマーの小定理素数限定の世界から正の整数の世界へと引っ張りあげた、とも言えるだろう。

さて、ここで最初に出てきた(p-1)(q-1)の意味を考える。フェルマーの小定理で見たように、p-1とq-1はそれぞれ 素数-1 なので、p, qに互いに素な数の個数を表している。これをかけているので、結果としてこれはn = pq以下かつnと互いに素な整数の数を表している。

再度、RSA暗号の復号関数を見てみる。\(c^{d} \mod n\)は、\((m^{e})^{d} \mod n \)と書くことができる。更に変形して、\(m^{ed} \mod n\)と書ける。ここで、edは(p-1)(q-1)を法として1と合同、つまりdはeの逆元なので、ある定数kが存在し、\(ed = 1 + k(p-1)(q-1) = 1 + k\phi(n)\)と書くことができる。これを先の式に代入すると、

\( \begin{align} m^{ed} \mod n &= m^{1 + k\phi(n)} \mod n\cr &= m^{1}\cdot m^{k\phi(n)} \mod n\cr &= m\cdot m^{k\phi(n)} \mod n\cr &= m\cdot 1 \mod n \cr &= m \end{align} \)

ここで、上から4行目の変形はオイラーの定理を利用した。

よって、復号関数は元の値を必ず復元することが可能であることがわかった。

攻撃

有名なだけあり、かなりの量の攻撃手法が知られている。代表的なものを以下に書く。

Low Private-Exponent Attack

秘密鍵dが小さい時に使える攻撃。有名なものにWienerが「Cryptanalysis of Short RSA Secret Exponents」で発表した $d < \frac{n ^ \frac{1}{4}}{3}$ の時に $e, n$ から $p, q$ を求めることが可能な攻撃や、Boneh-Durfeeによる $d < n^{0.292}$ の時に $e, n$ から $p, q$ を求めることが可能な攻撃がある。

Common Modulus Attack

m, nが共通、eが異なる幾つかのe, n, cの組がある時、mを計算することができる攻撃。

Common Private Exponent Attack

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

Hastad's broadcast Attack

nが異なり、eと平文が同じ複数の暗号文/公開鍵のセット(n1, e, c1), (n2, e, c2), ...がある時、元の平文を求めることができる攻撃。 $c _ i = m ^ e mod n _ i$とすると、解 $x = m ^ e$ を持つ剰余連立方程式を立てることが可能で、しかもこれは中国人剰余定理によって解を求めることが可能。最低限必要な暗号文の数は 「$m ^ e < \prod _ i {n _ i}$ が成り立つ最小の$i$」だが、多くはe個の暗号文を集めることで十分足りる。

Franklin-Reiter Related Message Attack

元のメッセージm1と、もう一つ少し違うメッセージm2 = a * m1 + bがあり、それぞれの暗号文c1, c2がある時にn, e, c1, c2からm1を導出可能な攻撃。 e=3, 5の場合はWikipediaに載っているが、実はこれはメッセージの数、関数も一般化が可能である。詳しくは元論文「Low-Exponent RSA with Related Messages」。

Coppersmith's short pad Attack

メッセージmがあり、\(k = \lfloor\frac{n}{e^{2}}\rfloor\)とする。暗号化するメッセージm1, m2を\(m1 = 2^{k} m + r_1\), \(m2 = 2^{k} m + r_2\)とし、それぞれの暗号文c1, c2がある時、n, e, c1, c2からmを導出できる攻撃。

Partial-key exposure Attack

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

LSB Leak Attack

Partial-keyではないが、暗号文に対して復号した値の偶奇のみが分かる時、二分探索によって元の平文を求めることが可能な攻撃。

参考文献