RSA暗号 ~理論編~

暗号

はじめに

RSA暗号ってなに?
歴史 1977年に発明され、発明者であるロナルド・リベスト、アディ・シャミア、レオナルド・エーデルマンの原語表記の頭文字をつなげてこのように呼ばれる。 Wikipediaより引用 RSAというのは3人の頭文字を繋げて付けられた名前なん...

こちらがRSA暗号の入門編の記事です。あまり詳しくない方はこっちから読んだほうがイメージできると思います!

今回は理論的な側面からRSA暗号を見ていきます。

アルゴリズム

ここから数式たくさん出てきますよ~!

準備

まず準備するものは2つの素数\(p,q\)です。そして\(n=p\times q\)とします。

そこから次の条件を満たす\(e\)を選びます。

  1. \(2 \leq e \leq \phi(n) \)
  2. \(e\)と\(\phi(n)\)は互いに素

(\(\phi(n)\)は\(n\)未満で\(n\)と互いに素な自然数の個数を表します。)

この\(e\)は暗号化する際に使用する公開鍵です。なぜこれらの条件を満たす必要があるかは後々説明します。

次に大事な大事な秘密鍵\(d\)を求めます!\(d\)は次の条件を満たす必要があります。

  1. \(2 \leq d \leq \phi(n) \)
  2. \(e\times d \equiv 1 \bmod \phi(n) \)

これはどうやって求めればよいのでしょうか?またどんな\(e\)に対してもこれを満たす\(d\)は存在するのでしょうか??

条件2を満たす\(d\)について考えてみます。これはある整数\(k\)を用いて\[e\times d + \phi(n)\times k = 1\]を満たすことと同値です。\(e\)と\(\phi(n) \)は互いに素なので、拡張されたユークリッドの互除法より、これと条件1を満たす\(d\)と\(k\)を求めることができます。

ちなみに\(e\)と\(\phi(n) \)が互いに素じゃなかったらこれを満たす\(d\)と\(k\)は存在しません。存在すると仮定すると、\(e\times d + \phi(n)\times k = 1\)の左辺は\(\gcd(d, k) \neq 1\)で割り切れますが、右辺はもちろん割れないため矛盾します。だから、\(e\)と\(\phi(n) \)が互いに素という条件があるんですね。

こうして生成された\(n\)と\(d\)と\(e\)のうち、\(n\)と\(e\)を公開鍵に、\(d\)を秘密鍵にします。ではLet’s 暗号化です!!

暗号化

AliceがBobにメッセージを送信するとしましょう。AliceはBobが公開している公開鍵\(n\)と\(e\)を取得します。まずはAliceが送りたいメッセージをなんらかの方法(a→1,b→2などの簡単な置換でOK)で数字に変換します。ここで変換してできた数字は\(n\)よりも小さい必要があります。そのため送るメッセージが大きい場合は、\(n\)よりも小さくなるように分割してから1つずつ送ります。

そうして生成された数字を\(m\)とすると、Aliceは\[m^{\prime} = m^e \bmod n\]を求めます。これで暗号化完了です。Aliceは\(m^{\prime}\)を送信することで誰かに盗聴されても解読されることはありません!

復号

Bobは受け取った暗号\(m^{\prime}\)を復号します。実はこの方法も簡単で、秘密鍵\(d\)を用いて\[m^{\prime \prime} = (m^{\prime})^d \bmod n\]を求めるだけです。すると\(m=m^{\prime \prime}\)となるんです。あとはこの\(m^{\prime \prime}\)を数字から文字列に変換すれば復号完了です!

なぜ\(m=m^{\prime \prime}\)となるのでしょうか?実際に計算してみましょう。

\begin{align}
m^{\prime \prime} &= (m^{\prime})^d \bmod n\\
&= (m^e)^d \bmod n\\
&= m^{de} \bmod n\\
&= m^{1-\phi(n)\times k} \bmod n\\
&= m\times (m^{\phi(n)\times (-k)}) \bmod n \\
&= m\times (m^{\phi(n)})^{-k} \bmod n
\end{align}

ここでオイラーの定理(フェルマーの小定理の一般化)を用いると\(m^{\phi(n)} \equiv 1 \bmod n\)(\(m\)と\(n\)は互いに素になると仮定)となるので、

\begin{align}
m^{\prime \prime} &= m\times (1)^{-k} \bmod n \\
&= m \bmod n
\end{align}

となるので、\(m^{\prime \prime} < n\)を満たす\(m^{\prime \prime}\)で\(m^{\prime} = m^{\prime \prime}\)となります。メッセージを分割せずに\(n\)よりも大きい状態で送っていたら\[m \equiv m^{\prime \prime} \bmod n \Leftrightarrow m = m^{\prime \prime}\]とはなりません。

 

美しいアルゴリズムですね~(笑)ほんと大好きです。

安全性

この暗号方式は安全なのでしょうか??

この暗号に対する攻撃法として真っ先に思いつくのは秘密鍵を解読することでしょう。公開鍵\(e\)と\(n\)から秘密鍵\(d\)がバレることはないのでしょうか?秘密鍵\(d\)は\(\phi(n)\)が分かれば導出することができます。しかし、\(\phi(n)\)は\(n\)を構成している\(p, q\)を知る必要があります。つまり、\(n\)を素因数分解する必要があります!

しかし、未だに効率的な素因数分解のアルゴリズムは見つかっていないのです。一応多項式時間(短い時間)で素因数分解を行うアルゴリズムは発見されているようですが、係数が大きすぎて実用はされていないようです。

とはいえ、\(p\)や\(q\)、\(n\)が小さすぎると現在のコンピュータでは簡単に解読されてしまいます。そのため、\(n\)は2048ビットから4096ビット程度が推奨されています。LINEのメッセージも2048ビットのRSA暗号で暗号化されて送信されているそうですよ。

素因数分解以外にもこのRSA暗号を攻撃する手法はあるかもしれません。ですが、誰もそれを発見していないため、40年ほど経った今でもRSA暗号は使用されています。

おわりに

とにかく素晴らしいアルゴリズムですね。考案した方に感謝です(笑)

素因数分解の計算が難しいと思われているからこのアルゴリズムが実用されていると説明させていただきました。でも今後もっと計算の速いコンピュータ、最近話題の量子コンピュータなどが実用化されるとRSA暗号は一瞬で解読されると言われています。そのため、RSA暗号が使用されなくなる日ももしかしたら近いかもしれませんね‥

実は公開鍵暗号方式にはもう一つ、公開鍵暗号方式には楕円曲線暗号というものがあります。いずれそっちも解説する予定ですので、乞うご期待を!!

コメント

タイトルとURLをコピーしました