エルガマル暗号
エルガマル暗号とは、位数が大きい離散対数問題が困難であることを安全性の根拠とした公開鍵暗号の一つです。
暗号化と複合化
送信者は受信者の公開鍵（暗号化鍵）で平文から暗号文を作成し、受信者は自分の秘密鍵（複合化鍵）で暗号文を平文に戻します。平文と暗号文、及び、暗号化鍵と複合化鍵の関係は以下で表されます。
| 送信者（暗号化） | 受信者（複合化） |
| 平文（$M$）→ 暗号文（$C_1,C_2$） | 暗号文（$C_1,C_2$）→ 平文（$M$） |
| 暗号化鍵（$y,g,n$） | 複合化鍵（$x,n$） |
| $C_1=y^rM\pmod{n}$ －① $C_2=g^r\pmod{n}$ －② |
$$M=\frac{C_1}{C_2^x}\pmod{n} －③$$ |
公開鍵の作成
公開鍵（暗号化鍵）$y$ は、素数 $n$ と秘密鍵（複合化鍵）$x$ により以下で求めます。尚、$g$ は除数 $n$ に対する原始根を選びます。
$$y=g^x\pmod{n} －④$$
この（$y,g,n$）を公開鍵として配布します。
複合化と安全性
複合化の確認
③により複合化できることは、③に①と②及び④を代入することで確認することができます。
$$\frac{C_1}{C_2^x}\pmod{n}=\frac{y^rM}{(g^r)^x}\pmod{n}$$$$=\frac{(g^x)^rM}{(g^r)^x}\pmod{n}\equiv M$$
安全性
秘密鍵から公開鍵を求める④について、（$g,n$）が既知とした場合、秘密鍵 $x$ から公開鍵 $y$ を求めるのは容易ですが、公開鍵から秘密鍵を知るのは容易ではありません。④の $x$ を求めることは離散対数問題と呼ばれ、これがエルガマル暗号の安全性の根拠となっています。
例えば、次の計算は容易にできますが、
$$y=7^5\pmod{13}=16807\pmod{13}=11$$
逆に、次の式を満たす $x$ を求めることは容易ではありません。
$$11=7^x\pmod{13}$$
$1\le x\le13$ 程度であれば総当たりで求めることもできますが、$n$ が大きくなると途端に困難になります。
数学
解析学、代数学、幾何学、統計学、論理・基礎論、情報・暗号、機械学習、金融・ゲーム理論、高校数学
www.sansakuro.com
2021.04.13
散策路TOP
数学、応用数学、古典物理、量子力学、物性論、電子工学、IT、力学、電磁気学、熱・統計力学、連続体力学、解析学、代数学、幾何学、統計学、論理・基礎論、プラズマ物理、量子コンピュータ、情報・暗号、機械学習、金融・ゲーム理論
www.sansakuro.com
2021.03.24
