RSA暗号 ステップ3

2 千年以上前、ユークリッドは、あらゆる数が唯一の方法で
因数分解できることを示し、これは秘密鍵に利用できます。

素因数分解は、非常に難しい問題だと分かります。

簡単や困難の意味を、「時間複雑性」と呼ばれる概念を
導入して説明します。

我々は全員、掛算の経験がありますが、
それは計算をすばやく行うためです。

掛算用にプログラムすれば、コンピュータは
人類よりもはるかに素早く計算できます。

これは、コンピュータが 2 つの数を掛算するために
必要な時間のグラフです。

もちろん、数が大きくなるにつれて、答を出すために
必要な時間も長くなります。

しかし、計算時間は、かなり大きな数でも、
1 秒よりかなり短いものです。

このため、実行は容易です。
これを素因数分解と比較しましょう。

誰かに 589 の素因数分解を指示されたら、
この問題がずっと難しいことが分かります。

どのような戦術を取るにせよ、589 を割り切れる数を
見つけるまで試行錯誤が必要です。

かなり苦労して 19×31 という
素因数分解の答が得られます。

437,231 を素因数分解するように指示されたら、
手計算は諦めてコンピュータを使うでしょう。

これは小さな数では有効な方法ですが、さらに
大きな数では、暴走効果が発生します。

多数の手順が必要となり、計算に必要な時間が
急速に増加するのです。

数が大きくなると、計算に数十分、
さらには数時間かかります。

さらに巨大な数を因数分解するには
数百年、数千年かかるようになります。

このため、必要時間の増大のために、
素因数分解は難しい問題なのです。

このため、コックスは因数分解を使ってトラップドアを作ったのです。

ステップ 1: アリスが 150 桁以上の素数乱数を
用意します。これを P1 とします。

また同程度の桁数の第 2 の素数乱数も用意します。
これを P2 とします。

アリスはこれらの 2 つの素数を掛算して、合成数 N を
作ります。N は300桁以上の数になります。

この掛算には 1 秒もかかりません。
Web ブラウザでもできます。

そして、アリスは N の因数分解の解である
P1×P2 を隠します。

アリスが N を他人に渡しても、素因数を見つけるには、
コンピュータを使っても何年もかかります。

ステップ 2: コックスは、N の因数を知っている人だけが使える関数を見つける必要がありました。

このため、スイスの数学者 オイラーが
1760 年に産みだした業績を活用しました。