【セキュリティ】数学的困難さを利用！「エルガマル暗号」の正体｜情報処理問題1000本ノック

公開鍵暗号には、いくつかの有名なアルゴリズムがあります。それぞれが「解くのが難しい数学の問題」をベースにしていますが、今回はその一つ「エルガマル暗号」を攻略しましょう。

1. 問題：離散対数問題を利用した暗号

【問題】 公開鍵暗号方式の一つで、有限体における「離散対数問題」を解くのが非常に困難であることを安全性の根拠としている暗号方式はどれでしょうか？

① RSA暗号 ② エルガマル暗号（ElGamal） ③ AES ④ 共通鍵暗号

2. 正解：公開鍵暗号のアルゴリズムに関する正解

正解： ② エルガマル暗号（ElGamal）

3. 解説：数学の難問と暗号のペアを覚える

公開鍵暗号は、計算に膨大な時間がかかる「数学の壁」に守られています。試験対策としては、以下の「問題」と「暗号名」のペアを丸暗記しておくのが最も効率的です。

【必勝！暗記セット表】

■ 離散対数問題（りさんたいすう）

  ⇒ エルガマル暗号 / ディフィー・ヘルマン鍵共有 (DH)

■ 素因数分解問題（そいんすうぶんかい）

  ⇒ RSA暗号

■ 楕円曲線上の離散対数問題

  ⇒ 楕円曲線暗号 (ECC)

[ 関連用語の整理 ]

★ RSA暗号：桁数の大きな素数の掛け算は簡単だが、分解（素因数分解）は難しいことを利用。

★ AES：現代の標準的な共通鍵暗号方式。数学的困難さではなく、複雑な置き換え（撹乱）を利用。

★ 一方向性関数：逆計算が極めて困難な関数の総称。これらが暗号の基礎となっています。

1. 理解のコツ: 離散対数問題そのものを計算できるようになる必要はありません。「離散対数＝エルガマル」という反射神経を鍛えるだけで、試験の得点源になります。名前が少し覚えにくいですが、「エルガマルは、離散（りさん）が得意」とこじつけて覚えるのも手です。
2. 試験対策の視点: 公開鍵暗号の問題では、誤答の選択肢に「RSA」や「AES」が並ぶのが定番です。問題文に「離散対数」という言葉が含まれているか、あるいは「素因数分解」が含まれているかを瞬時に見分けるのが合格への近道です。

4. まとめ

「離散対数問題の困難性を安全性の根拠にする」。これがエルガマル暗号の最大の特徴です。暗号の世界は、こうした「解くのが絶望的に難しいパズル」によって支えられていることを押さえておきましょう！