RSA公開鍵暗号アルゴリズムを理解する

こんにちは、yoshiです。弊社製品の電子書籍ビューアー「超縦書」シリーズの開発に携わっています。

はじめに

電子書籍に限らず、Webを介したコンテンツ産業では、暗号化は切り離すことのできない技術です。ユーザー情報や通信内容の秘匿という点もありますし、著作物がファイル共有や違法アップロードされないように、ファイルそのものを暗号化することを考える必要もあります。

私も多分に漏れずそういう技術に触れることがあるのですが、大抵の場合、HTTPサーバーの設定で鍵ペアの場所を指定するだけだとか、アプリケーションに組み込む場合でも、OpenSSLを使うだけで済んでしまいます。私は作業に関わっていませんが、TechRachoも先日HTTPS移行作業を行っていましたね。

もちろん、一般的にはそれで十分でしょう。暗号化はセキュリティ上もっとも重要な技術なので、誰もが自由に、そして簡単に使えるようになっていなければなりません。

技術的詳細を気にすることなく利用できるのは素晴らしいことでもあるのですが、一方で、そこにはどんなメカニズムがあるのか気になると思います。気になりませんか？　気になりますよね。

公開鍵暗号アルゴリズムの中で最も有名なのはRSA暗号でしょう。

Wikipediaにも詳しい記事が載っているので、読んだことのある方もいるのではないかと思います。

RSA暗号が素因数分解の困難さを利用しているというのはそれなりに知られた話だと思いますが、具体的にどのような計算が行われているのか私は詳しくは知りません。というわけで、ちょっと実際に計算してみようと思います。

と言っても、RSA暗号を普通に使うときと同じような長さの暗号鍵を用意しても、とても人間に把握できる計算にはなりません。鍵長を長くするのは暗号化を破られないようにするための措置ですが、今回は計算を確かめるだけなので、人間に扱えるレベルの数を用意してみようかと思います。

Wikipediaを見ると、

をセキュリティパラメータとする。

を ビットの素数とし、 とする。 を 未満の正の整数で、 と互いに素な数とし、 を、 を法とした の逆数（ ）とする。 ただしここで は オイラーのφ関数で、この場合は である。 は、 が既知のときには拡張されたユークリッドの互除法を使えば容易に求まる（ を で割った整数商を とした場合、が成り立ち、かつ の取り方から であるのでこれを解けば良い）。 を秘密鍵とし、 を公開鍵とする ( が漏れると が計算で求まるため、 と は安全に破棄すること)

とあります。

数学アレルギーの人は「あ、もういいです」と言ってしまいそうな説明ですね。私も、真面目に考える気がなければこういう説明を見ても、「あとでいいや」と思ってスルーしてしまうことが多々あります。

ともあれ、今回はちょっと真面目に考えてみます。

鍵ペアの生成

をセキュリティパラメータとする。

いきなり、「セキュリティパラメーター」なる という変数が出てきました。 は自然数を表すのに使われることが多いので、多分自然数なんだろうなと思いますが、今のところよく分かりません。
パラメーターと言うからには、外部から与える値なのかな、という気もします。

続けて、

を ビットの素数とし、 とする。

とのことから、なるほど はどうやら の大きさを決めるための値らしいぞ、ということが見えてきます。 がそれぞれ ビットの数であるということは、 は ビットになります。 後の方を見れば は公開鍵の一部になる事が分かるので、どうやら というのは鍵の長さを表すようです。

つまり、

openssl genrsa -out key.pem 2048

と、鍵を生成する時に指定する鍵長が だということですね。

続いて、

を 未満の正の整数で、 と互いに素な数とし、 を、 を法とした の逆数（ ）とする。 ただしここで は オイラーのφ関数で、この場合は である。

オイラーのφ関数という、また聞き覚えのない関数が出てきましたが、ざっくり言うと、

自然数 に関して、 と互いに素な 未満の自然数の個数を とする

ということらしいです。

で が素数の時、 と、 は と互いに素でないのですから、

   

ということになるのが分かります。

つまり、 は 未満かつ と互いに素な数から適当に選べば良いようですが、ごちゃごちゃ考えずに素数を一個選べば、常に互いに素だよね、ということで、 が選ばれることが一般的なようです。 という数は なので、累乗の計算量が減るのだとか。

ちなみに、openssl genrsaコマンドでは-3オプションを渡すことで の値を にすることも可能です。また、 の値は標準エラー出力から確認することができます。

にしてしまうと手で計算するには面倒なので、今回は私も を使うことにします。

秘密鍵を作ってみる

さて、実際に適当な数を使って、秘密鍵を作ってみましょう。

鍵は小さいほうが手で計算しやすいです。ということで、として、とても小さな鍵にすることにします。この条件で計算すると、

   

   

となります。

さて、鍵ペアを作るなら、秘密鍵 を求めなければなりません。の求め方も書いてあって、

   

ということのようなので、

   

となります。暗算でもとりあえず を選べばこの条件は満たせそうだとわかりますが、Wikipediaの記述のように拡張されたユークリッドの互除法を使うと、

   

となりますので、 の解は、 のとき、 となり、 を求めることができます。

さて、これで鍵ペアが作成できたはずです。

公開鍵は となり、秘密鍵は です。

暗号化と復号

というわけで、この鍵ペアを利用して実際に暗号化と復号をしてみます。
Wikipediaを見ると、

• 暗号化（平文 から暗号文 を作成する）：
• 復号（暗号文 から元の平文 を得る）：

と書いてあります。上記の式を見れば分かるように、暗号化も復号も、 未満のデータにしか適用できません。今回の場合0～14に対してしか暗号化ができないということになります。したがって、それを超えるサイズのデータは分割して暗号化することになります。

適当に の場合を考えてみましょう。

   

   

となります。なるほど、復号できているようですね。
この程度なら、全部同じように計算してしまえるので、やってみます。

平文	暗号文

こうしてみると、しか変化していないですね。これでは全く役に立ちません。まあ、この大きさの鍵では全く役に立たないのは当然なのですが。

とは言え、計算式を見てもらえば、 や の場合はどう頑張っても平文と暗号文が等しくなってしまうことが分かるかと思います。特に、非圧縮データで が連続するというものは珍しくないため、そういったデータを暗号化しようとしても のままになってしまい、意味がありません。

なので、RSA暗号を使う場合、暗号化時にランダムな値でパディングして、復号してからそれを取り去るという操作を行います。そのため、実際に暗号化するブロックサイズはもっと大きなものでなければならず、したがって、 の値が小さいため暗号化できるデータサイズがそもそも小さい鍵では役に立ちません。

また、暗号化ブロックサイズが小さければ復号テーブルを用意して破ることができてしまうのは当然のことです。

というわけで、破られない暗号鍵を作るには大きな数を用意しなければなりません。
現在、RSAでは2048bit以上の大きさの鍵であれば安全であると言われています。ですが、将来はさらに大きな数でなければ破られるようになってしまうかもしれませんね。

まとめ

今まであまり深く考えたことのなかった暗号化アルゴリズムでしたが、こうして計算してみることで理解が深まったように思います。
公開鍵暗号アルゴリズムには、他にも楕円曲線暗号などがあるので、そちらに関してもそのうち調べてみたいと思っています。