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

公開鍵暗号 - RSA - 基礎

公開鍵暗号

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

公開鍵暗号

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

RSA暗号

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

パラメータ

パラメータp, q, n, eを決める。p, qはそれぞれ素数で、\(n=pq\)である。また、\((p-1)(q-1)\perp 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)\perp e\)という条件は、「(p-1)(q-1)とeは互いに素」と読む。この条件が必須な理由は互いに素で無い場合、法(p-1)(q-1)上での逆元を計算することが出来ない(つまり、dの計算ができない)からだ。

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

p, qの生成は必ずランダム性があり、偏りがあってはいけない。具体的な例を挙げると、過去にDebianのOpenSSLにこの素数の生成が偏ってしまい、鍵生成された後のパターンが高々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\perp p \Rightarrow x^{p-1} \equiv 1 \mod p\)が成り立つ。

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

オイラーの定理

ある正の整数nがあり、\(x\in \mathbb{Z}\)なら、\(x\perp p \Rightarrow 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なので、それぞれに互いに素な数の個数を表している。この数をかけているということがどういうことかを考えてみよう。そう、これはpqに互いに素な数の個数に等しいのだ!

再度、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行目の変形はオイラーの定理を利用した。

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

攻撃

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

Wiener's Attack / Boneh-Durfee's low private exponent Attack

eが一定以上の大きさになると、dが比例して小さくなる。Wiener's Attackでは\(d < \frac{n^\frac{1}{4}}{3}\)、Boneh-Durfeeでは\(d < n^{0.292}\)(正確には\(d < n^{1-\frac{\sqrt{2}}{2}}\) )の時に、このdをe, nから計算することが可能になる攻撃だ。

Common Modulus Attack

m, nが共通、eが異なる幾つかのe, n, cの組がある時、mを計算することができる攻撃。単純な計算が主で、比較的簡単な攻撃になる。

Common Private Exponent Attack

逆にdが共通で、n, eが異なる際に使用できる攻撃。格子理論(LLL程度なのでsageでOK)の話が出てくるが、比較的簡単に実装ができる。

Hastad's broadcast Attack

nが異なり、eと平文が同じ複数の暗号文/公開鍵のセット(n1, e, c1), (n2, e, c2), ...がe個ある時、元の平文を求めることができる攻撃。 e=3であれば3つデータが揃えば可能だし、e=1000であれば1000個データを揃えれば良い。 計算方法としては連立剰余方程式を立て、中国人の剰余定理を用いることでmを求める。

Franklin-Reiter Related Message Attack

元のメッセージm1と、もう一つ少し違うメッセージm2 = a * m1 + bがあり、それぞれの暗号文c1, c2がある時にn, e, c1, c2からm1を導出可能な攻撃。 e=3, 5の場合はWikipediaに載っているが、実はこれはメッセージの数、関数も一般化が可能である。詳しくは元論文へのリンクをリファレンスに書いたので、そちらを参照。

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 / High-bit known Attack

pの上位ビットの一部が判明している時、その一部のpを\(\tilde{p}\)と書く。この時、\(|\tilde{p} - p| < N^\frac{1}{4}\)が成立するならば、元のpを復元することができる。 Coppersmithの定理、Howgrave-Grahamの定理を使用するため、理解さえできれば応用がかなり効く攻撃になる。

CTFの過去問

例としていくらか挙げておく。

  • ASIS CTF 2015 Finals: Bodu (Boneh-Durfee)
  • ADCTF 2014: strangekey (Wiener's Attack)
  • RuCTFe 2013: nsaless (Hastad's broadcast Attack)
  • ASIS CTF 2015 Finals: Honeywall (Common Modulus Attack, Hastad's broadcast Attack)
  • PlaidCTF 2015 : Strength (Common Modulus Attack)

リファレンス