暗号の安全性の証明について

暗号の安全性の示し方としては二通りのやり方が考えられます。

想定される攻撃を限定し、それらの攻撃一つ一つに対して安全であることを示す。
攻撃者を暗号方式が用いられる場面に置いて妥当な情報が得られる存在としてモデル化し、その攻撃者が攻撃に成功した場合に矛盾の生じることを示す。

どちらの場合も実用的な時間内には解くことができないと考えられている問題（素因数分解問題、離散対数問題など）の困難性に基づいて安全性を証明する計算量的安全性が主となります。
攻撃者のモデルが定式化できると一般的な安全性と考えることができるので2.の場合を用いられることが多いです。

エルガマル暗号方式の安全性

離散対数問題、DH問題

大きな素数pを法とする剰余演算を考えます。例として小さな素数p=5の場合を考えます。法５の剰余演算では0〜4までの値が得られます。このとき、

2¹ ≡　2 (mod 5), 2² ≡　4 (mod 5), 2³ ≡　3 (mod 5), 2⁴ ≡　1 (mod 5)

と2のベキ乗で0を除いた1〜4までの値をすべて表すことができることが分かります。このように mod pの剰余演算において、gkで1|p−1までの値をすべて表すことのできるgを法pに置ける原始元と呼びます。素数pに対しては常に原始元が存在することが示されていて、以下の問題を離散対数問題と言います。

離散対数問題: 正の整数g,a,pに対して、g^x ≡ a (mod p)を満たす整数xを求める問題。

大きな素数pに対してgを原始元とし、aを1〜p−1から選んだ任意の整数とすると離散対数問題は実用的な時間内では解くことのできない問題であると考えられています。離散対数問題に似た問題としてDH問題があります。

DH問題: pを素数、gを法pにおける原始元とし、a,bを正の整数としたとき、g^a mod p, g^b mod pの計算結果のみからg^abを求める問題。

DH問題は離散対数問題を解くことができれば解くことができますが、DH問題が解くことができても離散対数問題を解くことができるかどうかは分かっておりません。しかし、DH問題も離散対数問題と同様に実用的な時間内では解くことのできない問題であると考えられています。エルガマル暗号の安全性は厳密にはDH問題の困難さに基づくものですが、離散対数問題の困難さに基づくと言ってしまう場合が多いです。

暗号方式

暗号方式は通常、暗号・復号の手順と秘密の情報である鍵に分けて考えます。
暗号・復号の手順は予め公開しておき、相手と鍵を秘密に共有してから暗号通信を行います。
暗号化して送りたいメッセージを平文（ひらぶん）と呼びます。
鍵を用いて平文を暗号化して暗号文を得て、相手に暗号文を送ります。
鍵を用いて受け取った暗号文を復号すると相手の送りたかった平文を得ることができます。
秘密にしている鍵を知らない人は暗号文を復号できません。

公開鍵暗号方式

暗号通信における暗号化のための鍵と復号のための鍵を別のものとして、暗号化の鍵を公開しても復号の鍵を知らない限りは復号できないような暗号方式が公開鍵暗号方式です。
公開鍵暗号方式では、暗号化の鍵を公開しますので誰でも暗号文は作成できます。
復号は秘密にしている復号の鍵をもっている人しかできません。

エルガマル暗号方式

エルガマル暗号方式はDH問題が(実用的な時間内には)解けないことに基づく公開鍵暗号方式です。

【鍵生成】: 大きな素数ｐ、法pにおける生成元g、正の整数xをランダムに選び、y=g^x mod pとおく。ｐ,g,yを暗号化のための公開鍵とし、x復号のための秘密鍵とする。
【暗号化】: 平文mは1|p−1までの値から選ばれるとします。rを乱数とし、 u = g^r mod p、　　v = my^r mod p とします。暗号文をu, vの組(u, v)とします。
【復号】: 暗号文(u,v)と復号のための秘密鍵xから平文mを以下の様に復号します。　　　　　v/u^x mod p = my^r/(g^r)^x mod p = m(g^x)^r/g^xr mod p = mg^xr/g^xr mod p = m とします。暗号文をu, vの組(u, v)とします。

エルガマル暗号方式の安全性

攻撃者は公開鍵暗号と暗号文を得ることができるとします。
秘密鍵を知らずにエルガマル暗号を復号することのできる攻撃者がいるとするとDH問題が解けることを示します。
DH問題は解けない問題であるとしていますので、エルガマル暗号を復号できる攻撃者がいるとすると矛盾が生じることになり、このような攻撃者はいないことになります(背理法)。
DH問題を解こうとしている人をA君とし、エルガマル暗号を復号することのできる攻撃者をB君とします。

A君にはDH問題として、素数p、法pにおける原始元g、g^a mod p, g^b mod p (a,bは正の整数)が与えられますが、a,bは教えてもらえません。 A君の目的はg^abを求めることです。
B君はエルガマル暗号の公開鍵として、大きな素数ｐ、法pにおける生成元g、y=g^x mod p (xは正の整数)を与えられますが、ｘは教えてもらえません。 B君は暗号文u = g^r mod p、v = my^r mod p (rは乱数、mは平文)を与えられますが、乱数rと平文mは教えてもらえません。 B君は秘密鍵を知らなくてもエルガマル暗号を復号できるので、mを計算することができてしまいます。
A君はB君にエルガマル暗号の公開鍵として、DH問題の素数p、法pにおける原始元g、g^a mod pを渡します。このときA君も知らない正の整数aがエルガマル暗号の秘密鍵ｘになります。
A君はu = g^b mod pとし、1?p−1の値から乱数vを選び、(u,v)をエルガマル暗号の暗号文としてB君に渡します。このときA君も知らない正の整数bがエルガマル暗号の乱数rと置かれたことになります。
B君はA君に渡された暗号文(u,v)から平文ｍを求めてA君に渡します。復号の式からmは m = v/u^x mod pを満たしていますので、 u^x = v/m mod p が成り立ちます。
A君はvを知っており、mもB君から渡されているのでu^x = v/m mod pを計算することができます。このとき u^x mod p = (g^r)^x mod p = g^rx mod p となります。秘密鍵xはa、乱数rはbと設定されていますので、 v/m mod p = g^rx mod p　=　g^ab mod p が成り立ちますので、A君はv/m mod pを計算することによりDH問題を解いたことになります。