2018年1月5日セキュリティーツイートこの記事では、私の備忘録と理解度の確認もかねてRSA暗号について書いていきます。整数論の知識が必要ですが、素因数分解と合同式を知っていればそれほど難しくはありません。数式が多く出てくるので、数学が苦手な方は頭が痛くなるかもしれません。スポンサードリンクRSA暗号とはRSA暗号は、桁数の多い数の素因数分解が困難であることを利用したセキュリティー技術です。10桁程度の数なら電卓でも素因数分解できますが(多少の根気はいる)、これが100桁となるとコンピューターでも難しくなります。マサチューセッツ工科大学のリベルト、シャーベル、エードルマンの3人が発明し、RSAはそれぞれの名前の頭文字を取っています。大まかな仕組み公開鍵を公開するまず、大きな異なる素数を2つ選び、2つの数の積と指数を公開します。今回は素数をp,q、指数はrとします。rはp-1とq-1の最小公倍数より小さく、1より大きい互いに素である数を選びます。p=3,q=5の場合、p-1は2、q-1は4なので最小公倍数は41<r<4の範囲で4と互いに素(最大公約数が1)なのは3だけなので、3が指数となります。平文とは暗号化する前の文のことで、数値に変換してから暗号化します。平文をsとして、sのr乗を素数の積pqで割って暗号文tを導きます。pq)$$整数論を勉強している方なら知っていると思いますが、上の式は合同式で、tはsのr乗をpqで割った余りです。今度は暗号文を復号するために、秘密鍵uを使って復号します。uはrとの積ruが(p-1)(q-1)を法として1と合同になるようなる数です。式で表すと$$ru\equiv1(mod(p-1)(q-1))$$を満たす逆元が、復号に使用する秘密鍵になります。暗号文tをu乗して、平文sを得ます。pq)$$文字式だけだとわかりにくと思うので、簡単な例を出してみます。s=17まず、Aさんが平文17を公開鍵25で暗号化してBさんに送信します。62(mod95)$$暗号文62を受け取ったBさんは、公開鍵95と秘密鍵13(求め方は後述)を使って平文を復号します。17(mod95)$$今回は簡単な例として小さい数を使用していますが、実際には300桁以上の素数が使われます。先ほどの例で秘密鍵13を使いましたが、1次合同式とユークリッド互除法で求めてみます。1次合同式で導く方法pが5、qが19なので、p-1=4、q-1=18となり、最小公倍数は36rが25なので、秘密鍵は以下の式を解けば求められます。$$25u\equiv1(mod36)$$両辺を3倍して$$75u\equiv3(mod36)$$72u≡0(mod36)より、$$3u\equiv3(mod36)$$両辺を3で割りたくなりますが、3と36は互いに素ではありません。そこで、右辺の3を左辺に移行して、$$3u-3\equiv0(mod36)$$3でまとめて$$3(u-1)\equiv0(mod36)$$つまり、u-1は12の倍数なので$$u-1\equiv0(mod12)$$よって、$$u\equiv13$$となります。ユークリッド互除法を使う方法1次不定方程式をユークリッド互除法を使って導く方法です。36で割って1余るので、解くべき1次不定式は整数x、yを用いて$$25x+36y=1$$と表せます。ここでユークリッド互除法を使います。36=25・1+1125=11・2+311=3・3+23=2・1+11=3-2・1=3-(11-3・3)・1=11・(-1)+3・4=11・(-1)+(25-11・2)・4=25・4+11・(-9)=25・4+(36-25・1)・(-9)=25・13+36・(-9)よって、x=13、y=-9が整数解のひとつです。式の説明をかなり省いているので、わかりにくいかもしれません。RSA暗号は安全なのか?前述したように、RSA暗号は桁数の多い数の素因数分解が困難であることを利用しています。逆に言えば、素因数分解が容易に解ければ、RSA暗号がすぐに解読され、安全性が危ぶまれてしまいます。素因数分解のようなNP問題を解く多項式時間アルゴリズムはまだ見つかっていないので、当分は安全とみていいと思います。ここであまり見慣れない用語が出てきたので、少し解説します。以下の2つのアルゴリズムを比較してみます。$${n}^5$$$${5}^n$$前者のように、nが大きくなっても計算処理に時間がかからないものを多項式時間、後者はnが大きくなると計算時間が指数関数的に増えていくので指数的時間といいます。試しにn=10でやってみると、10の5乗が100000、5の10乗が9765625となります。多項式時間で解ける問題をP問題、解が正しいかどうかを多項式時間で判定できる問題をNP問題といいます。すべてのPがNPであることはすでに証明されていますが、その逆はまだ証明されていません。これはクレイ数学研究所が2000年に発表したミレニアム問題の1つで、P=NP(またはP≠MP)問題と呼ばれます。こんな話をしたかというと、素因数分解はNP問題であり、もしP=NPならば、方法は発見されていないが素因数分解は多項式時間で解けるということになり、RSA暗号が簡単に破られる危険性があります。現代の数学界では、多くの方がP≠NPだと予想しています。まとめ今回の内容は少々専門的でわかりにくかったかもしれませんが、整数論がセキュリティーで活用されているということはわかっていただけたと思います。P≠NP問題は解けると100万ドル(日本円で約1億)がもらえるので、興味のある方はチャレンジしてみましょう。RSA暗号について詳しく知りたい方は、整数論や暗号の書籍を購入してみることをおすすめします。(必須)ウェブサイト上に表示された文字を入力してください。人気記事(1ヶ月)ハンドルネームの作成メーカーおすすめ12選ブログを運営するうえで、ハンドルネームをどうしようか悩む方は少なくないと思います。そこでこの記事では自動で作成してくれるwebサービスを紹介していきます...大阪弁の一覧(50選)を大阪人がまとめてみたこの記事では、大阪弁の一覧(50個)を意味も合わせて解説していきたいと思います。同じ大阪の方でも、年齢や地域によって使わない表現もいくつかあります...ロゴ作成メーカー60選!アニメ・ドラマ・企業まで総まとめ今回はタイトル通り、ロゴを作成できるジェネレーターサイトを紹介します。アニメ・ドラマ・企業ロゴなど、集められるだけ集めました。2018年に新しく3サイト...キャラクター作成メーカー30選!ブログで使いたいときに超便利ブログで対話形式の記事を書きたいとき、キャラクター(アバター)を用意する必要があります。絵を描く時間が取れないとか、そもそも絵に自信がないという...日常会話を中二病のセリフっぽくしてみた今回はちょっと息抜きに書いてみました。「厨二病」と書くこともありますが、「中二病」のほうが一般的なので、こちらを採用しました(どうでもいいと思いますが一...方言変換サイト8選!正確性はどうなのか?日本には東北弁や関西弁、博多弁など、地域によって独特の方言があります。今回は標準語を方言に変換するサイトを8つ紹介します。エゴサーチのやり方と結果、実践の際は注意が必要エゴサーチ(egoSearch)は自分のこと(名前や運営しているブログ)を検索エンジンやSNSで調べることを指します。他人のことを調べるのは普通にサーチ...語呂合わせジェネレーターで語呂を作る手間を省こう!数字を覚える方法として定番なのが語呂合わせ。「鳴くよ(794)ウグイス平安京」や「いい国(1192)作ろう鎌倉幕府」とかは有名ですよね。...面白いはてなブログ5選!暇つぶしにおすすめさて、タイトルを見て疑問に思った方もいるでしょう。私は読点で結構迷うんですよ。