2017年06月03日

素数の神秘を力に付けた暗号 〜RSA暗号の登場〜

応援クリックを1日1回宜しくお願いいたします。



本日も暗号を進めます。

とうとう現代で活躍中の暗号です。

また、ガッツリ数学(数論)に入ります。

平文$M$も暗号文$c$も、もちろん暗号鍵$p,q,e$も自然数です。

素数$p$と$q$を決めます。

また、$\mathrm{GCD}\left(e,\left(p-1\right)\left(q-1\right)\right)=1$すなわち$\left(p-1\right)\left(q-1\right)$と互いに素(最大公約数が$1$)な$e$を選びます。

公開鍵は$n=p\times q$と$e$です。

暗号化と復号化の手順はこうです。 \begin{eqnarray*} c&=&M^e\mod n\\ M&=&\ c^d\ \mod n \end{eqnarray*}
復号化に登場する$d$が秘密鍵です。

秘密鍵の性質上、$n,e$を知っていても$d$を知り得ない必要があります。

$d=e^{-1}\mod\left(p-1\right)\left(q-1\right)$なので、全部知っている人は$p$も$q$も$e$も知っているので、$\left(p-1\right)\left(q-1\right)$をラクラク計算できます。

しかし、解読者は公開鍵の$n=p\times q$しか知らないので、一旦$n$を素因数分解(約数の総当たり)を行って$p$と$q$を得てからスタートします。

$91=7\times13$程度であれば余裕($2,3,5$の次に$7$を試した時点で約数が確定)なのですが、 \[ 2^{74207281}-1\sim10^{22338617} \] のような$1$億を$2792327$個掛けたような超膨大な数字の積になると、"古典的な"コンピュータでは現実的に太刀打ち不可能です。

Wolfram|Alpha: Computational Knowledge Engine
↑現時点で知られている最大の素数を検索しています。
The Largest Known Primes
↑.eduドメイン(テネシー大学のChris Caldwell教授のページ)によるデータです。

"古典的な"というのは、スーパーコンピュータ(スパコン、通常スペックのコンピュータを膨大に集めて分散処理をする)も含むコンピュータのことで、量子コンピュータのような複数パターンを同時並行で計算できるコンピュータではむしろ一瞬で解かれるそうです。(古典という名称の由来は、古典物理学と量子力学との関係からです。)

複数パターンを同時並行で計算できると、数$n$が数$d$で割り切れるかどうか、$d$の値を変えて調べている素因数分解において、多すぎるパターン数でも同時並行で行えます。

計算自体は1種類なので、一瞬となります。

しかし、量子コンピュータはまだここまでの実用レベルでないそうなのでセーフということです。

このような解読の困難さを利用して、現在も暗号の標準として利用されていて、セキュリティ対策が必要な通信の際に使われています。

"古典的な"コンピュータの場合に大敵な巨大素数はセキュリティ企業の金庫の中に保管して、一般人の手に渡らないようにしてあるそうです。






$e$や$d$の計算方法に込められた数論的意味はご自身でどうぞ。
RとSとAによる論文です。
A Method for Obtaining Digital Signatures and Public-Key Cryptosystems


最後に、RSAで暗号化・復号化するアプリケーションを作成しました。
↓↓↓
RSA暗号


[開発談]
暗号化・復号化の式を見ると分かりますが、べき乗を行っているので、巨大な数を取り扱えるライブラリが必要でした。

Javaで作成したときには、java.mathで長倍精度整数(BigInteger)を扱えたのですが、JavaScriptでも同様のライブラリを探しました。

すると、BigInteger.jsというライブラリがあったので、こちらを重宝しました(・_・v)。



posted by Line Segment at 18:00 | Comment(0) | TrackBack(0) | ホームページ | このブログの読者になる | 更新情報をチェックする