公開鍵暗号方式の原理

ここでは、概念を理解することを目的としているので、以下の説明は厳格性を欠いていることに留意してください。

暗号化・復号の方法

発信者は受信者の公開鍵で暗号化し、受信者は受信者の秘密鍵で復号します。公開鍵は、任意の送信者に公開していますが、秘密鍵は受信者以外は知りません。

受信者の公開鍵を（Ｅ、Ｎ）、秘密鍵を（ＤまたはＭ）とし、
　　　Ｅ＝３、Ｎ＝２２
　　　Ｄ＝７、Ｍ＝２０
であるとします。そして、文字列「ＡＢＣ」を暗号化して送信することにします。

• 平文のＡを１、Ｂを２、…、という数値化の対応表は公開されています（実際には複雑な規則になっています）。
• 暗号化では、文字に対応した整数Ｋを、
  　　　Ｓ＝Ｋ^Ｅ mod Ｎ　　　（Ｈ^ＥをＮで割ったときの余り）
  の式で変換します。
  　　平文のＡ：１³ mod ２２→１を２２で割った余り→１→暗号文字はＡ
  　　平文のＢ：２³ mod ２２→８を２２で割った余り→８→暗号文字はＨ
  　　平文のＣ：３³ mod ２２→２７を２２で割った余り→５→暗号文字はＥ
  　これで暗号文は「ＡＨＧ」になります。
• 復号するときは、
  　　　Ｋ＝Ｓ^Ｄ mod Ｎ
  の式を用います。
  　　暗号文のＡ：１⁷ mod ２２→１ mod ２２＝１→平文文字はＡ
  　　暗号文のＨ：８⁷ mod ２２→２０９７１５２ mod ２２＝２→平文文字はＢ
  　　暗号文のＧ：５⁷ mod ２２→８２３５４３ mod ２２＝３→平文文字はＣ
  　となり、復号文は「ＡＢＣ」となります。

このように、公開鍵と秘密鍵が異なっていても、暗号化・復号ができることが、公開鍵暗号方式の特徴です。それには、ＫとＳの変換で１：１の対応が保証されることが必要ですが、その証明は省略します。

公開鍵・秘密鍵の作成方法

暗号化・復号の規則は周知でも、Ｄ＝７という値を知らないと復号できません。さらに、Ｎ、Ｍ、Ｅ、Ｄの作成方法も、次の手順で行っていることが周知なのです。

• 適当に２つの素数ｐとｑを設定する（ここではｐ＝２、ｑ＝１１とした）。
• Ｎ＝ｐ・ｑ＝２×１１＝２２
• Ｍ＝(ｐ－１)(ｑ－１)＝１×１０＝１０
• Ｅを、Ｍと互いに素（共通の約数がない、ＥとＭの最大公約数が１）となるような数にする。ここでは３とした（３と２０は互いに素）。
• Ｅ・Ｄ mod Ｍ＝１　となる数Ｄを求める。Ｄ＝７とすれば、３×７＝２１なので、それを１０で割った余りは１になる。

ＭがわかっていてＥを求めるのは、適当にＥを仮定してＥとＭの最大公約数を求めればよく、それにはユークリッドの互除法などにより、簡単に設定できます。
　また、ＥとＭがわかっているときにＤを求めることは、やや複雑ですが、比較的容易に求めることができます（それで、秘密鍵で「ＤまたはＭ」としたのは、Ｍだけを秘密鍵にしてもよいからです）。

基盤は素因数分解の困難性

このように、鍵の生成方法や暗号化の方法が周知なのに、秘密を保つには、ＥやＮからＤやＭを求めることができないことを保証する必要があります。その保証は、大きな数Ｎの素因数分解には非常に時間がかかることにあります。

ｐとｑを知っていれば、上の手順から容易にＤやＭを知ることができますが、Ｎからｐとｑを求めること、すなわち素因数分解をするのが困難なのです。
　ここではＮ＝２２ですから、直ちに２×１１だとわかりますが、実際にＲＳＡ方式で用いられているＮは、３００桁以上の巨大数なのです。
　巨大数の素因数分解を効率的に解く方法が発見されれば、公開鍵暗号方式は根底から崩れてしまいます。そのような方法が存在するかどうかを確認するために、多くの数学者が研究しているのですが、現在のところ、そのような解法は発見されていません。
　それで、現在ではｐやｑを知るには、世界中のコンピュータを用いても数万年かかるといわれていますし、Ｎの値をもっと大きくすれば、さらに時間がかかります。しかし、量子コンピュータのような現在のコンピュータとは動作原理が全く異なるコンピュータが実用化されると、案外短時間で解けてしまうのではないかといわれています。