ElGamal暗号についての要点解説

『時の流れのギャスケット　理論編』の中で少し取り上げられていた公開鍵暗号のトピックスです。

作中、攻撃を加えられた暗号として「RSA暗号」と「ElGamal暗号」が挙げられています。

RSA暗号は素因数分解、ElGamal暗号は離散対数問題の困難性を利用した公開鍵方式暗号です。

今回は特に、ElGamal暗号について要点を解説します。

ElGamal暗号は、クレジット決済のセキュリティ等に応用されています。

次の手順により鍵を生成します。

【１】十分大きな桁数の素数pと、法pにおける原始根g（１〈g〈p）をランダムに選ぶ。

【２】y≡g＾x  mod p　を計算する（xはランダムに選んだ整数（0≤x≤p−2））

【３】暗号化に用いる公開鍵を（p,g,y）、復号化に用いる秘密鍵をxとする

y＝g＾x　の解は　x=loggy　で簡単に求められますが、y≡g＾x  mod p　の解xを求めるのは困難です（この方程式を解く問題を「離散対数問題」といいます）

離散対数問題のこのような性質を利用し、公開鍵で簡単に暗号化できても、秘密鍵がなければ復号化は難しい、という暗号を作成することができます。

『時の流れのギャスケット　理論編』で、RSA暗号、ElGamal暗号等の解読困難なはずの暗号が次々と破られる事件が起こるのですが、攻撃者はこの行為を介して、何かメッセージを伝えたい様子・・・

さらに、これらの問題が、計算量やアルゴリズム、数学体系の全体構造に関する話題にまで広がってゆきます。

個々のトピックが大きなテーマにつながっていく展開をお楽しみいただけたら、と思います。

■新規会員随時募集しています。詳しくはG=world公式サイトまで！