公開鍵暗号系の強度評価

公開鍵暗号とは

公開鍵暗号の概念は、１９７６年にＤｉｆｆｉｅとＨｅｌｌｍａｎによって発表された。 従来の共通鍵暗号では、暗号化鍵と復号鍵が同一であるので、 通信者同士は秘密通信を行うためには 前もって共通の秘密鍵を安全な通信路を使って共有しなければならなかった。 この欠点を公開鍵暗号は暗号化鍵と復号鍵を 異なる鍵にすることによって解決するとともに、 その他にもディジタル署名といった認証機能を実現することも可能にした。 公開鍵暗号では互いに異なる暗号化鍵と復号鍵を用いる。 そして暗号化鍵は公開し、復号鍵は秘密にする。 このことから、公開した鍵は公開鍵、秘密にしておく鍵は秘密鍵と呼ばれる。

公開鍵をｅ、秘密鍵をｄ、とおく。 また、平文をＭとして、公開鍵ｅによる変換をＥ（ｅ，Ｍ）、 秘密鍵ｄによる変換をＤ（ｄ，Ｍ）と表現する。 この時、各変換は以下の条件を満たす必要がある。

  1. ｅが与えられたとき、Ｅ（ｅ，Ｍ）の計算は容易。 また、ｄが与えられたとき、Ｄ（ｄ，Ｍ）の計算は容易。
  2. ｄが与えられていなければ、ｅとＥ（）が与えられていても、 暗号文Ｃ＝Ｅ（ｅ，Ｍ）から平文Ｍを決定することは計算量的に困難。

秘密通信を実現する為には、Ｍ＝Ｄ（ｄ，Ｅ（ｅ，Ｍ））を満たす必要がある。 また、認証機能を実現するためには、Ｍ＝Ｅ（ｅ，Ｄ（ｄ，Ｍ））を満たす必要がある。

公開鍵暗号の強度評価の必要性

公開鍵暗号は共通鍵暗号と比べて新しいので、研究し尽くされてるとは言い難い。 特に、多くの研究者は暗号の安全性を根気よく調べるより、 新しい公開鍵暗号系を作ることに意欲を感じている。 しかし、実際に暗号を活用する立場から考えると、 暗号の強度が真剣に検討されていない状態では積極的には使いにくい。

ＩＰＡセキュリティセンター暗号技術調査室では、 現在使用されている公開鍵暗号の強度評価の必要性を痛感し、 １９９７年度から継続的に公開鍵暗号の強度評価を行うことにした。

公開鍵暗号の強度評価

この研究は、「暗号強度評価に関わる調査研究」の一部として行われた。 発注先は三菱電機で、実施は東京大学の今井秀樹教授。

目的

公開鍵暗号の強度評価を実施するにあたり、 まず現状を把握することが重要である。 そこで、初年度は公開鍵暗号を鳥瞰し、最先端の技術を網羅的に収集することにした。

一口に「公開鍵暗号」といっても、その方式は千差万別であり、 鍵の長さも、暗号化の方式も暗号系によって全く異なっている。 調査の対象として選ばれたのは、 ＥｌＧａｍａｌ暗号に象徴される離散対数問題の困難性に基づく公開鍵暗号、 離散対数問題の特殊系である楕円曲線暗号、 それにＲＳＡ暗号に象徴される素因数分解の困難性に基づく公開鍵暗号である。 このほかに、ナップザック暗号系、ラティス暗号系などが存在するが、 既に弱点が指摘されていたり、実装が困難であり、調査の必要は無いと判断した。

内容

以下に調査項目を示す。

  1. 公開鍵暗号とは
    1. 公開鍵暗号の原理
    2. 公開鍵暗号の機能
      1. 秘密通信
      2. ディジタル署名
    3. 公開鍵暗号の安全性
      1. 暗号解読の安全性
      2. 署名偽造の安全性
  2. 公開鍵暗号の諸方式
    1. 離散対数問題の困難性に基づく方式
      1. 離散対数問題
      2. 離散対数問題の困難性に基づく鍵配送法
      3. 離散対数問題の困難性に基づく公開鍵暗号系
      4. 離散対数問題の困難性に基づくディジタル署名方式
        • ＥｌＧａｍａｌ署名方式
        • Ｓｃｈｎｏｒｒ署名方式
        • ＤＳＳ署名方式
        • ＳＤＳＳ１署名方式
      5. 離散対数問題の困難性に基づくＳｉｇｎｃｒｙｐｔｉｏｎ
        • ＳＣＳ１方式
        • 第三者による署名検証可能な改良Ｓｉｇｎｃｒｙｐｔｉｏｎ方式
    2. 楕円曲線上の離散対数問題に基づく方式
      1. 楕円曲線についての定義
      2. 楕円曲線に基づく公開鍵暗号方式
        • 公開鍵暗号方式
          • ＥｌＧａｍａｌ型暗号方式
          • Ｍｅｎｅｚｅｓ−Ｖａｎｓｔｏｎｅ暗号方式
        • ディジタル署名
          • ＥｌＧａｍａｌ署名
          • ＤＳＡ署名
          • Ｓｃｈｎｏｒｒ署名
        • Ｄｉｆｆｉｅ−Ｈｅｌｌｍａｎ鍵共有
        • Ｓｉｇｎｃｒｙｐｔｉｏｎ方式
      3. 楕円曲線暗号に対する攻撃について
        • Ｓｕｐｅｒｓｉｎｇｕｌａｒな楕円曲線の場合
        • Ａｎｏｍａｌｏｕｓな楕円曲線の場合
    3. ＲＳＡ暗号
      1. 暗号化・復号
      2. 安全性
        • 素因数分解による全面的解読に対する安全性
        • 周期攻撃に対する安全性
        • 部分解読に対する安全性
        • 特殊な暗号文に対する安全性
      3. 利用上の注意点
        • ＲＳＡの数学的特性を利用した署名偽造に関する問題
        • 共通法プロトコルの問題点
        • 低指数公開鍵プロトコルの問題点
        • 故障利用攻撃に関する問題点
        • 時間測定攻撃に関する問題点
      4. その他の応用
      5. 素因数分解アルゴリズムの現状について
      6. 実装について
    4. ハッシュ関数
      1. ハッシュ関数の設計においての要求条件
      2. ＭＤ系列のハッシュ関数
        • ＭＤ５
        • ＳＨＡ−１
        • ＲＩＰＥＭＤ−１６０
        • ＨＡＶＡＬ
      3. ＭＤ系列ハッシュ関数への攻撃
        • ＭＤ５に対する攻撃
        • ＳＨＡ−１、ＲＩＰＥＭＤ−１６０、ＨＡＶＡＬ
      4. セルオトマトンを用いたハッシュ関数
      5. ６４ビットプロセッサのためのハッシュ関数Ｔｉｇｅｒ
      6. ハッシュ関数を用いた認証アルゴリズム
  3. 公開鍵暗号の標準化動向
    1. ＩＥＥＥ−Ｐ１３６１
    2. 主な標準化事項
      1. ＰｒｉｍｉｔｉｖｅとＳｃｈｅｍｅ
      2. ＤＬに基づくＰｒｉｍｉｔｉｖｅ
      3. ＥＣに基づくＰｒｉｍｉｔｉｖｅ
      4. ＤＬとＥＣのＳｃｈｅｍｅ
      5. ＩＦに基づくＰｒｉｍｉｔｉｖｅ
      6. ＩＦのＳｃｈｅｍｅ
      7. ハッシュ関数

成果

上記の項目についての、調査報告書が納入された。 公開鍵暗号全体にわたる広範囲をカバーした調査報告書となった。 付録に電子ファイルが収録されている。