公開鍵暗号

共通鍵暗号の課題を解決するため、公開鍵暗号が提案された。
公開鍵暗号とは、暗号化と復号で違う鍵を用いる暗号である。

なお公開鍵暗号にて、暗号化に用いる鍵を公開鍵、 復号に用いる鍵を秘密鍵と呼び、 これらのペアを鍵ペアと呼ぶ。

実際のプロトコル

公開鍵暗号の例

RSA暗号

• 素因数分解の困難性を安全性の根拠とした公開鍵暗号
  • 素因数分解の困難性： $n$ から $p$ と $q$ を現実的な時間で計算できない¹。
    • $p, q$: 大きな素数
    • $n = p \cdot q$

ElGamal暗号

• 離散対数問題が解けないことを仮定した公開鍵暗号
  • 離散対数問題： $y, g, p$ から $x$ を現実的な時間で計算できない¹。
    • $p$: 大きな素数
    • $g, p, x$: $p$ 未満の数
    • $y = g^x \mod p$, ²

公開鍵暗号のデモ（RSA）

1. 鍵ペアの生成

2. 暗号化

3. 復号

公開鍵暗号の特徴

メリット

• 必要な（秘密）鍵の数が少ない
  →n人が相互に暗号通信するのに、必要な共通鍵数はn
• 配送する公開鍵は漏洩しても良い（鍵配送問題を部分的に解決）
  • しかし、配送する公開鍵を改ざんして、すり替える脅威が存在
    →ディジタル署名、PKIと組み合わせることで解決可

デメリット

• 処理が低速

---