暗号理論の研究動向
暗号技術調査室では、最先端の暗号基礎技術研究の動向を調査してきた。 暗号は、もはや軍事目的のみでなく、日常生活に欠かすことの出来ない基礎技術として、 一般消費者が意識するしないに関わらず頻繁に用いられている。 よって、その基礎となる暗号理論の研究動向を調査し適切な援助をすることは、 ＩＰＡセキュリティセンターの重要な任務の一つである。
共通鍵暗号系は、歴史も古く、官民の隔てなく使用されており、 その安全性は現代社会においてこの上なく重要である。 現在最も使用されている共通鍵暗号は米国の標準暗号である ＤＥＳ（Data Encryption Standard）であり、 これは６４ビットブロック暗号で５６ビットの鍵を用いる。 しかし、指数函数的なコンピュータ性能の向上により、 ＤＥＳの安全性に陰りが出てきた。
米国のＮＩＳＴでは、ＤＥＳに取って代わる新規共通鍵暗号 ＡＥＳ（Advanced Encryption Standard）を決定するために、 １９９７年に広く世界中から候補を募集した。 その結果１５件の応募があり、現在候補の研究調査の段階である。 （１９９９年３月現在。） 共通鍵暗号研究の話題はもっぱらＡＥＳが支配的であり、 これは２０００年に最終アルゴリズムが決定されるまで続く。
前述の通り、ＡＥＳはＤＥＳに代わる標準共通鍵暗号として、 現在選定作業中である。 ＡＥＳの主な仕様項目は、
- １２８ビットブロックの共通鍵暗号
- 鍵は少なくとも、１２８、１９２、及び２５６ビットをサポート
- Ｔｒｉｐｌｅ−ＤＥＳより高速
- Ｔｒｉｐｌｅ−ＤＥＳより安全
- ソフトウェア及びハードウェア実装可能
- ワークステーション
- スマートカード
- ＡＳＩＣ
- Ｊａｖａ
- 著作権、特許権等がフリー（ＡＥＳとして採用された場合）
であり、８ビットプロセッサ上から６４ビットプロセッサ上までサポートするのが前提になっている。 公募の結果、次の１５提案が受理された。
アルゴリズム名 提案会社又は個人（国） CAST-256 Entrust Technologies (Canada) CRYPTON Future Systems (Korea) DEAL (Data Encryption Algorithm with Larger Blocks) Richard Outerbridge (USA) and Lars Knudsen (Norway) DFC (Decorrelated Fast Cipher) CNRS (France) E2 (Efficient Encryption Algorithm) NTT (Japan) FROG TecApro International (Costa Rica) Hasty Padding Cipher Richard Schroeppel (USA) LOKI97 Lawrie Brown, Josef Pieprzyk, and Jennifer Seberry (Australia) Magenta (Multifunctional Algorithm for General-purpose Encryption and Network Telecommunication Applications) Deutsche Telekom (Germany) MARS IBM Corp (USA) RC6 RSA Laboratory (USA) Rijndael Joan Daemen and Vincent Rijmen (Belgium) SAFER+ Cylink Corp (USA) Serpent Ross Anderson (UK), Eli Beham (Israel), and Lars Knudsen (Norway) Twofish Counterpane (USA) かなりの提案が１２８ビットブロックを３２ビットづつに分解して内部処理していて、 用いられている手法はＦｅｉｓｔｅｌネットワークまたはその変形が多い。 また、ＡＥＳの作業スケジュールは以下の通り。
日付 予定 １９９７年１月２日 ＡＥＳ制定の意向表明、コメントの募集開始 １９９７年４月１５日 要求仕様、プロセス、及びコメントに関するワークショップ開催 １９９７年６月１６日 要求仕様とプロセスのドラフト完成 １９９７年９月１２日 候補の募集開始 １９９８年４月１５日 提案のプレレビューの締切 １９９８年５月１５日 提案のプレレビュー終了 １９９８年６月１５日 提案の締切 １９９８年８月２０日−２２日 第１回ＡＥＳ候補コンファレンス開催、候補に対するコメント募集開始 １９９９年３月２２日−２３日 第２回ＡＥＳ候補コンファレンス開催 １９９９年４月１５日 候補に対するコメント締切 １９９９年８月 ５つ程度の最終候補発表、最終候補に対するコメント募集開始 ２０００年４月１０日−１４日 第３回ＡＥＳ候補コンファレンス開催 ２０００年８月 ＡＥＳ発表 その後 ＦＩＰＳ及びＩＳＯ標準化手続き 上記１５候補の内ＬＯＫＩ９７は、第１回ＡＥＳ候補コンファレンスの前に既に破られてしまった。 また、ＦＲＯＧとＭａｇｅｎｔａはコンファレンスで内容を発表した段階で攻撃された。 さらにＤＥＡＬも攻撃されて、１９９９年３月現在では残りの１１候補が暗号研究者の攻撃にさらされている。
生き残りが１１あっても、おのずから５つ程度の最終候補に残る可能性のある物は絞られている。 Ｒｉｊｎｄａｅｌ、ＭＡＲＳ、ＲＣ６、およびＴｗｏｆｉｓｈが有力候補であることは誰もが認めている。 これに続くのは、Ｅ２、Ｓｅｒｐｅｎｔ、ＣＡＳＴ−２５６、それにＣＲＹＰＴＯＮである。 ＤＦＣ、ＨＰＣ、ＳＡＦＥＲ＋は、遅かったり、デザインポリシーが不明確であり遅れをとっている。 実装したときに度の程度の速度が得られるかは、共通鍵暗号において非常に重要であるが、 すべての実装で抜き出て速いものはない。
その他に、新規の共通鍵暗号方式の提案は時々ある。 特に、日本からはＩＳＯに登録する共通鍵暗号がときどき出てくるが、 現在の所インパクトは強くない。
暗号研究において新規の提案も重要ではあるが、 解読法の研究は更に必要であると考える。 解読法の研究は、単に暗号を破るためだけではなく、 暗号の弱点を知ることにより、その点を補強しより強いアルゴリズムを開発することが出来る。
しかしながら、新しい解読法はめったに登場しない。 現時点で、ＢｉｈａｍとＳｈａｍｉｒによる差分解読法（differential cryptanalysis）と、 松井による線形解読法（linear cryptanalysis）が強力であり、 その他の解読法、たとえば高階差分解読法（higher differential cryptanalysis）や 差分線形解読法（differential linear cryptanalysis）、は差分解読法と線形解読法の改良版でしかない。 また、新しく提案される共通鍵暗号（ＡＥＳ候補など）は、 当然これらの攻撃方法に耐えるように設計されている（はずである）。 現在の解読法研究は、アルゴリズムのラウンド数を減らした場合を考慮したり、 アルゴリズム固有の特徴点を探してそこを攻撃するのがほとんどである。
一方、共通鍵暗号の解読法研究で見逃されがちなのが、 キースケジューリング（key scheduling）とか鍵拡大と呼ばれる部分である。 共通鍵暗号の鍵は６４ビットであったり１２８ビットであったりするが、 これらの鍵を暗号化にそのまま用いることはなく、 鍵から各ラウンドで本当に用いる拡大鍵を生成する。 このプロセスを鍵拡大と呼ぶが、 鍵拡大を下手にやってしまうと、どんなに暗号化アルゴリズムが優れていても、 すぐに解読されてしまう。 この典型的な例がＡＥＳ候補のＭａｇｅｎｔａで、 全く単純な鍵拡大をしていたために第１回ＡＥＳ候補コンファレンスで発表と同時に破られてしまった。 しかしながら、鍵拡大に関する系統的な研究は残念ながら存在しない。
公開鍵暗号は共通鍵暗号と比べると歴史が浅い。 それゆえに、高度な数学を用いたアルゴリズムが提案される一方、 その浮き沈みも激しい。 例えば、一時注目されたナップザック暗号は、その弱点が明らかになるにつれ研究者が減り続け、 いまやほとんど無視されてしまった状態になっている。 一方、老舗のＲＳＡ暗号は鍵長が長くなってきてはいるが、未だに健在である。
以下に、個々の公開鍵暗号について述べる。
公開鍵暗号の老舗であり、現在もその地位は揺るぎがない。 最近は１０２４ビットの鍵を用いるようになり、計算が重くなってきてはいるが、 最も使用されている公開鍵暗号であることに変わりはない。 １９９８年始めに、ＲＳＡ暗号が破られたと報道されたことがあったが、 実際にはＰＫＣＳ＃１という、ＲＳＡ暗号を使用する際の推奨フォーマットの欠陥であって、 ＲＳＡ暗号自身が破られたわけではない。 （ＰＫＣＳ＃１は即座に改められた。）
ＲＳＡ暗号を破る最も手っ取り早い方法は、法ｎを素因数分解することである。 素因数分解のアルゴリズムとして現在最も強力なのは一般数体ふるい法（ＧＮＦＳ、general number field sieve）である。 これは、
ｘ＾２ ＝ ｙ＾２ （ｍｏｄ ｎ）
となるｘとｙを探すアルゴリズムであり、そのためには事前計算でばく大なデータを蓄える必要がある。 一般数体ふるい法の実装上の問題点は、この蓄えるデータの量が桁違いである点で、 １９９８年現在で、４００ビット位の数を素因数分解するのがやっとである。 ｎが１０２４ビットの場合に、一般数体ふるい法を用いてｎを素因数分解するのは、 現在のコンピュータでは不可能である。 これは計算速度の問題ではなく、要求されるメモリーとディスク量の問題で、 現在のＲＳＡ暗号の強度に関する議論には、この点の考慮が全く欠けている。なお、ＲＳＡ暗号の安全性と素因数分解の困難性が等価であるか否かは、未だに証明されていない。
楕円曲線暗号に関する研究は３つに大別できる。すなわち、
- 楕円曲線上の演算の高速化
- 安全な楕円曲線を高速に生成する
- 楕円曲線の位数を高速に計算する
- 攻撃
である。
楕円曲線暗号は、一般に楕円曲線上での演算が遅いと言われている。 特に、定数倍する演算を高速化することは、楕円曲線暗号を普及させる上で欠かせない。 そこで、演算を高速化する手法が数多く研究されている。 広く一般に行われている手法は、
- ２倍だけではなく、４倍、８倍など特定の定数倍の公式をもとめ、あらかじめ組み込む
- 射影座標系やモンゴメリー座標系を用いる
- 掛ける定数をなるべく２の巾乗に近い形の数の組み合わせに表現する
- テーブルをあらかじめ計算しておく
などである。 それぞれ、わずかながらではあるが日々進歩している。
楕円曲線暗号はグループ内で同じ曲線を用いるので、必ずしも安全な楕円曲線を高速に生成する必要はない。 しかし、安全な楕円曲線が必要なときいつでも生成できるようにしておく必要はある。 ここで用いられる手法は主に、（１）虚数乗法を持つ超楕円曲線を利用する、 （２）モンゴメリー型の楕円曲線を用いる、の２つである。 各々成果が生まれている。
ここで問題になるのが、安全な楕円曲線とは何か、ということである。 一般に楕円曲線の位数が大きな素因子を持つことが重要であるが、 これを確かめるには楕円曲線の位数を素早く計算しなければならない。 現在もちいられているのはＳＥＡ法と呼ばれ、 ＳｃｈｏｏｆのアルゴリズムをＥｌｋｉｅｓが改良したアルゴリズムとＡｔｋｉｎが改良したアルゴリズムを 組み合わせて用いるものである。 これ以外の計算方法で効率の良いアルゴリズムは今のところ見当たらない。
楕円曲線暗号への攻撃の主流は、特定の群への埋め込み写像を生成し、 その群の中での離散対数問題に帰着させるものである。 典型的なものはＭＯＶリダクションで、似たものではＦＲ法がある。 これらは楕円曲線のトレースが０と２の場合に有力である。 群の離散対数問題に帰着させる方法は、計算量が準指数時間になるだけであるが、 １９９７年に東工大の荒木、埼玉大の佐藤らにより、 トレース１の楕円曲線暗号が多項式時間で解くことが出来ることが示された。
このほか、一般の代数曲線のＪａｃｏｂｉａｎを用いた暗号も研究されているが、 主流ではない。
公開鍵暗号の新アルゴリズムはかなり頻繁に提案されているが、 注目に値するものは多くはない。 しかし、少ないものの中には光っているものもある。 特に、アルゴリズム自身の強度に関してどの程度であるか証明付きで発表される場合、 研究者を納得させることが多い。 その中でも、Ｃｒｙｐｔｏ９８で発表されたＣｒａｍｅｒとＳｈｏｕｐによる公開鍵暗号が注目されている。
この暗号は離散対数問題の困難性に基づくもので、 汎用一方向性ハッシュ函数（universal one-way hash function）の存在を仮定して、 選択暗号文攻撃（chosen-ciphertext attack）に対し強秘匿（indistiuguishable）であることが証明できる。 これ以前の暗号では、ランダムオラクルの存在を仮定して 選択暗号文攻撃に対し強秘匿であることが証明されているアルゴリズムがあったが（ＮＴＴのＥＰＯＣ等）、 ランダムオラクルの存在ではなくより緩い汎用一方向性ハッシュ函数の存在を仮定しているところに意味がある。 さらに、この暗号は構造が複雑ではないので、十分に実用化可能である。
日本国内の公開鍵暗号研究は、最近特に楕円曲線暗号の研究に傾いてきた。 理由のひとつは、中央大学の辻井重男教授を中心とするグループが 超楕円曲線暗号に関して成果をあげていることがあるが、 各企業も楕円曲線暗号を自社製品に取り入れることに積極的になっている。