公開鍵暗号方式での暗号化・復号の方法、公開鍵・秘密鍵の作り方の概要を理解して、この方式が大きな数の素因数分解に時間がかかることに基づいていることを理解します。
暗号方式、RSA方式、公開鍵・秘密鍵、素因数分解
ここでは、概念を理解することを目的としているので、以下の説明は厳格性を欠いていることに留意してください。
発信者は受信者の公開鍵で暗号化し、受信者は受信者の秘密鍵で復号します。公開鍵は、任意の送信者に公開していますが、秘密鍵は受信者以外は知りません。
受信者の公開鍵を(E、N)、秘密鍵を(DまたはM)とし、
E=3、N=22
D=7、M=20
であるとします。そして、文字列「ABC」を暗号化して送信することにします。
このように、公開鍵と秘密鍵が異なっていても、暗号化・復号ができることが、公開鍵暗号方式の特徴です。それには、KとSの変換で1:1の対応が保証されることが必要ですが、その証明は省略します。
暗号化・復号の規則は周知でも、D=7という値を知らないと復号できません。さらに、N、M、E、Dの作成方法も、次の手順で行っていることが周知なのです。
MがわかっていてEを求めるのは、適当にEを仮定してEとMの最大公約数を求めればよく、それにはユークリッドの互除法などにより、簡単に設定できます。
また、EとMがわかっているときにDを求めることは、やや複雑ですが、比較的容易に求めることができます(それで、秘密鍵で「DまたはM」としたのは、Mだけを秘密鍵にしてもよいからです)。
このように、鍵の生成方法や暗号化の方法が周知なのに、秘密を保つには、EやNからDやMを求めることができないことを保証する必要があります。その保証は、大きな数Nの素因数分解には非常に時間がかかることにあります。
pとqを知っていれば、上の手順から容易にDやMを知ることができますが、Nからpとqを求めること、すなわち素因数分解をするのが困難なのです。
ここではN=22ですから、直ちに2×11だとわかりますが、実際にRSA方式で用いられているNは、300桁以上の巨大数なのです。
巨大数の素因数分解を効率的に解く方法が発見されれば、公開鍵暗号方式は根底から崩れてしまいます。そのような方法が存在するかどうかを確認するために、多くの数学者が研究しているのですが、現在のところ、そのような解法は発見されていません。
それで、現在ではpやqを知るには、世界中のコンピュータを用いても数万年かかるといわれていますし、Nの値をもっと大きくすれば、さらに時間がかかります。しかし、量子コンピュータのような現在のコンピュータとは動作原理が全く異なるコンピュータが実用化されると、案外短時間で解けてしまうのではないかといわれています。