公開鍵暗号方式の原理<情報倫理・セキュリティ<Web教材<木暮

Web教材一覧情報倫理・セキュリティ

公開鍵暗号方式の原理

学習のポイント

公開鍵暗号方式での暗号化・復号の方法、公開鍵・秘密鍵の作り方の概要を理解して、この方式が大きな数の素因数分解に時間がかかることに基づいていることを理解します。

キーワード

暗号方式、RSA方式、公開鍵・秘密鍵、素因数分解


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

暗号化・復号の方法

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

受信者の公開鍵を(E、N)、秘密鍵を(DまたはM)とし、
   E=3、N=22
   D=7、M=20
であるとします。そして、文字列「ABC」を暗号化して送信することにします。

  • 平文のAを1、Bを2、…、という数値化の対応表は公開されています(実際には複雑な規則になっています)。
  • 暗号化では、文字に対応した整数Kを、
       S=K mod N   (HをNで割ったときの余り)
    の式で変換します。
      平文のA:13 mod 22→1を22で割った余り→1→暗号文字はA
      平文のB:23 mod 22→8を22で割った余り→8→暗号文字はH
      平文のC:33 mod 22→27を22で割った余り→5→暗号文字はE
     これで暗号文は「AHG」になります。
  • 復号するときは、
       K=S mod N
    の式を用います。
      暗号文のA:17 mod 22→1 mod 22=1→平文文字はA
      暗号文のH:87 mod 22→2097152 mod 22=2→平文文字はB
      暗号文のG:57 mod 22→823543 mod 22=3→平文文字はC
     となり、復号文は「ABC」となります。

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

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

暗号化・復号の規則は周知でも、D=7という値を知らないと復号できません。さらに、N、M、E、Dの作成方法も、次の手順で行っていることが周知なのです。

  • 適当に2つの素数pとqを設定する(ここではp=2、q=11とした)。
  • N=p・q=2×11=22
  • M=(p-1)(q-1)=1×10=10
  • Eを、Mと互いに素(共通の約数がない、EとMの最大公約数が1)となるような数にする。ここでは3とした(3と20は互いに素)。
  • E・D mod M=1 となる数Dを求める。D=7とすれば、3×7=21なので、それを10で割った余りは1になる。

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の値をもっと大きくすれば、さらに時間がかかります。しかし、量子コンピュータのような現在のコンピュータとは動作原理が全く異なるコンピュータが実用化されると、案外短時間で解けてしまうのではないかといわれています。


情報倫理・セキュリティへ