“安全な暗号”とは何か――「強秘匿性」「頑強性」という概念：クラウド時代の暗号化技術論（2）（2/2 ページ）
前回に引き続き、暗号化手法の一つ「ElGamal暗号」を学びます。そして攻撃に強く、「安全な暗号」に必要な要素とは何かを考えてみます。
攻撃の種類と安全な公開鍵暗号
それでは一体、どのような暗号だと安全なのでしょうか。その説明の前にまず、攻撃者の能力について解説しましょう。
前回、RSA暗号で紹介した選択平文攻撃（CPA）の他に、選択暗号文攻撃（CCA：Chosen Ciphertext Attack）というのを想定します。CCAにはその攻撃能力に応じて2種類あります。
攻撃したい暗号文をcとします。
- 選択平文攻撃（CPA）：暗号文cを受け取る前後に、自分で選んだ平文に対応する暗号文を得られる
- 選択暗号文攻撃（CCA1）：暗号文cを受け取る前に、自分で選んだc以外の暗号文に対応する平文を得られる
- 適応的選択暗号文攻撃（CCA2）：暗号文cを受け取る前後に、自分で選んだc以外の暗号文に対応する平文を得られる
CCAの「c以外の暗号文に対応する平文を得られる」とはどういう意味でしょうか。攻撃者にわざわざ「答え」を教えるような状況は考えにくいです。しかし1998年、ダニエル・ブライヘンバッハー（Daniel Bleichenbacher）は「CCAが現実的にあり得る攻撃である」ということを示します。RSA暗号の標準フォーマット（PKCS #1）の扱いの不備を使って、サーバーの返答情報から平文の一部の情報を取り出したのです。そのため、現在はCCAを想定した暗号理論を構築しています。
ここでたとえ話をすると、CCA1というのは試験前に、自分で作った例題の答えを先生に聞いたら教えてくれる（ただし先生が試験に出すのと同じ問題は答えてくれない）状況です。CCA2は試験が始まってからも、試験中に、問題文そのもの以外の問題について質問すると先生が答えを教えてくれる状況です。これは受験者にとって有利ですね。先生としては、そんな状況でも解けない難しい問題を考えないといけないのです。
攻撃者と挑戦者の関係で見る「CCA1」「CCA2」
より厳密に言うと次のようになります。秘密鍵を持っている人を挑戦者といいます。そして、攻撃者が好きな暗号文ciを選んで、挑戦者にそれを復号してもらうことを何度か繰り返します。そのあと2個の平文m1、m2を選び、挑戦者に送ります。挑戦者はどちからの平文を暗号化して、c=Dec(mi)を攻撃者に渡します。
CCA2ではそのあとさらに、cとは異なる暗号文を選んで挑戦者に復号してもらうことができます。CCA1ではこのフェーズはありません。
そうやって攻撃者はたくさんの情報を集めてから、cがm1とm2のどちらを暗号化したものだったのかを当てるのです。これがでたらめにやって当たる確率、1/2よりも有為に高い場合攻撃者の勝ちとします。
そしてElGamal暗号は、CCA2に対して安全ではないことが知られています。なぜなら攻撃者がc=Enc(m)を攻撃しようとします。攻撃者はCCA2の能力を持っているので、2cという暗号文の答えを教えてくれと頼みます。するとElGamal暗号ではその暗号文に対応するのは2mという平文なので、2mという答えが返ってきます。攻撃者は2mが分かればmが分かり、攻撃が成功します。
このように暗号は、攻撃者の能力に応じて安全性が変わります。現在の暗号理論は、「ある暗号が、どういう仮定のもとで、どういう攻撃に対して、どうなったとき安全なのか」という精緻な論理を展開します。現在考えられている最も安全な公開鍵暗号は、CCA2に対して強秘匿性を持った暗号で「IND-CCA2安全」と呼ばれます。
そして「IND-CCA2安全な暗号は、頑強性も備え持つ」という重要な定理があります。ある暗号がCCA2というとても強い“仮想の敵”に対しても情報を漏らさなければ、攻撃者はその暗号を改変することもできないということです。
IND-CCA2安全な暗号の例として、RSA暗号を改良したRSA-OAEP、ElGamal暗号を改良したCramer-Shoup暗号が知られています。RSA-OAEPの安全性が厳密に証明されたのは2001年です。初めてRSAが登場したのが1977年ですから、意外と最近なことに驚かれるかもしれません。
今回のまとめ：
- 暗号文から平文の情報が漏れないという安全性について、「一方向性」「強秘匿性」「頑強性」の三つのレベルがあり、後者ほど安全である
- 攻撃者の能力について、CPA、CCA1、CCA2の三つのレベルがあり、後者ほど強力である
- 最も安全な公開鍵暗号に「RSA-OAEP」や「Cramer-Shoup」暗号がある
- まだまだ広く深い、暗号の世界――匿名認証や電子投票に利用される「ブラインド署名」「グループ署名」「ゼロ知識証明」
- マイナンバーの漏えい対策にも利用される「検索可能暗号」とは――安全性と利便性の両立を目指す注目の暗号技術
- 動画配信サービスにも応用できる暗号とは――アクセス権を制御する「属性ベース暗号」
- メールアドレスを公開鍵にする――「ペアリング」とその応用例
- クラウドサービスに最適な暗号方式とは？――暗号化したまま計算する「準同型暗号」
- 鍵が漏れることも想定せよ――クラウド時代における「楕円曲線暗号」の必然性
- “安全な暗号”とは何か――「強秘匿性」「頑強性」という概念
- 重要なデータを守るため、もう一度暗号化技術をおさらいしよう
光成滋生（みつなり しげお）
サイボウズ・ラボ株式会社
サイボウズ・ラボ株式会社にてセキュリティとインフラ周りの研究開発に携わる。「数論アルゴリズムとその応用」研究部会（JANT）幹事。
- 2004年放送型暗号の実装でIPA未踏スーパークリエータ認定
- 2005年ストリーム暗号Toyocryptの解読で情報化月間推進会議議長表彰
- 2010年ベクトル分解問題についての論文で電子情報通信学会論文賞受賞
- 2015年 Microsoft MVPアワード Developer Securityを受賞
近著に「応用数理ハンドブック」（朝倉書店、2013：楕円曲線暗号、ペアリング暗号の項目担当）、「クラウドを支えるこれからの暗号技術」（秀和システム、2015）がある。
Copyright © ITmedia, Inc. All Rights Reserved.