暗号技術をとりまく最近の話題 ーAES秘密鍵暗号,楕円公開鍵暗号－

Presentation on theme: "暗号技術をとりまく最近の話題 ーAES秘密鍵暗号,楕円公開鍵暗号－"— Presentation transcript:

1 暗号技術をとりまく最近の話題 ーAES秘密鍵暗号,楕円公開鍵暗号－
認証実用化実験協議会 平成10年度第1回定例研究会 1998/4/14 暗号技術をとりまく最近の話題 ーAES秘密鍵暗号,楕円公開鍵暗号－ 暗号技術研究タスクフォース委員 三菱電機株式会社情報技術総合研究所 松井 充 Copyright(C)ICAT 暗号をとりまく最近の話題について

2 AES (Advanced Encryption Standard)
認証実用化実験協議会 平成10年度第1回定例研究会 1998/4/14 AES (Advanced Encryption Standard) ・DES (Data Encryption Standard) の後継暗号を 決定する米国のプロジェクト ・NIST (National Institute of Standards and Technology) が主催する公募によって選定 ・選定されたアルゴリズムは FIPS (Federal Information Processing Standards) に登録 ・AES の Official Home Page Copyright(C)ICAT 暗号をとりまく最近の話題について

3 認証実用化実験協議会 平成10年度第1回定例研究会
1998/4/14 FIPS とは ・米国連邦政府調達品に強制力をもつ標準 民間を拘束しないがその影響力は大きい ・現在 FIPS に登録されている暗号方式の例 FIPS Data Encryption Standard (DES) FIPS Secure Hash Standard (SHA-1) FIPS Escrow Encryption Standard (EES) FIPS Digital Signature Standard (DSS) ( 参照) Copyright(C)ICAT 暗号をとりまく最近の話題について

4 認証実用化実験協議会 平成10年度第1回定例研究会
1998/4/14 DES の歴史 (1/3) DESの成立 ･ NBS (National Bureau of Standards : 現在のNIST) が 標準暗号を一般から公募 ･ IBM が応募したブロック暗号方式が DES の原形 ･ NSA (National Security Agency) が評価および改良 ･ 1976年 FIPS 46 として成立 (現在FIPS 46-2) ･ 1981年 ANSI (American National Standards Institute) に採用 ･ ISO (International Standardization Organization)での 標準化は米国自身が拒否 Copyright(C)ICAT 暗号をとりまく最近の話題について

5 認証実用化実験協議会 平成10年度第1回定例研究会
1998/4/14 DES の歴史 (2/3) DES 成立をめぐる議論 ・暗号化鍵の長さの仕様が56ビットと短い NSA の要請で IBM は鍵の長さを短くした 鍵の総当たり解読の可能性に対する大論争 ・乱数表(S-Box)の設計基準が公開されていない NSA の要請で設計基準は現在も非公開 Trapdoorが存在する可能性を否定できない Copyright(C)ICAT 暗号をとりまく最近の話題について

6 認証実用化実験協議会 平成10年度第1回定例研究会
1998/4/14 DES の歴史 (3/3) DESの現状 ・世界で最も利用されている暗号 ・米国からの輸出規制 例外：金融用途,非暗号用途,鍵縮小版,鍵寄託 ･ 暗号解読法の進歩で強度が低下 鍵の総当たり解読に成功 (1997年) ･ DESの後継暗号に関する議論 TripleｰDES：銀行は賛成,急速に浸透中 SkipJack ：NSA主導 / 国論を二分する大論争 AES ：NIST主催のコンテスト(公募中) Copyright(C)ICAT 暗号をとりまく最近の話題について

7 認証実用化実験協議会 平成10年度第1回定例研究会
1998/4/14 AES のこれまでと今後(確定分) ・1997年1月2日 NIST によるAES プロジェクトのアナウンス ・1997年4月15日 AES の Design Criteria を議論するワークショップ ・1997年9月12日 募集開始 ・1998年6月15日 募集締切 ・1998年8月20ｰ22日 The First Advanced Encryption Standard Candidate Conference Copyright(C)ICAT 暗号をとりまく最近の話題について

8 認証実用化実験協議会 平成10年度第1回定例研究会
1998/4/14 AES の要求条件 ・秘密鍵ブロック暗号であること ・ブロックサイズは128ビットをサポートする こと (DES は64ビット) ・鍵サイズは128,256,512ビットをサポートする こと (DES は56ビット) ・ライセンスフリーで利用できること Copyright(C)ICAT 暗号をとりまく最近の話題について

9 認証実用化実験協議会 平成10年度第1回定例研究会
1998/4/14 ブロック暗号のCBCモード 暗号化 復号化 平文 ブロック１ 平文 ブロック２ 平文 ブロック３ 暗号文 ブロック１ 暗号文 ブロック２ 暗号文 ブロック３ 初期値 暗号化 暗号化 暗号化 復号化 復号化 復号化 初期値 暗号文 ブロック１ 暗号文 ブロック２ 暗号文 ブロック３ 平文 ブロック１ 平文 ブロック２ 平文 ブロック３ ･ 同じ平文が連続しても暗号文は変化する ･ ある２つの暗号文ブロックのデータがたまたま一致したら 対応する２つの平文ブロックの排他的論理和が露呈する ･ このようなことは、n ビットブロック暗号の場合2の(n/2)乗 ブロックに1回程度おこる (birthday paradox) Copyright(C)ICAT 暗号をとりまく最近の話題について

10 認証実用化実験協議会 平成10年度第1回定例研究会
1998/4/14 AES の選考過程 ・詳細な選考スケジュールは未定 ・応募方式のなかから一次選考で５個以内に ・現在米国内外十数組織が応募の意志を表明 ・応募内容はすべて公開される(公開方法未定) ・最終決定(2000年?)は NIST の判断で行なう Copyright(C)ICAT 暗号をとりまく最近の話題について

11 認証実用化実験協議会 平成10年度第1回定例研究会
1998/4/14 AES をめぐる諸問題 ・強度評価は誰がどのようにして行なうのか？ ・NSA の Confidential Comments をどう扱うか？ NSA によるアルゴリズムの変更はあるのか？ (NSA は NIST の重要なコンサルタント：NIST談) ・NIST の最終的な選択基準は何か？ ・現在急速に普及している Triple-DES との 住み分けは？ Copyright(C)ICAT 暗号をとりまく最近の話題について

12 楕円暗号 (Elliptic Curve Cryptosystem)
認証実用化実験協議会 平成10年度第1回定例研究会 1998/4/14 楕円暗号 (Elliptic Curve Cryptosystem) 公開鍵暗号の分類 素因数分解型 RSA暗号，Rabin暗号 離散対数型 ElGamal暗号，Diffie-Hellman鍵交換方式， DSA署名方式 素因数分解型の楕円暗号と、離散対数型の楕円暗号があるが、 楕円暗号とは通常離散対数型を意味する。 これは(通常の素因数分解/離散対数型の)法演算の体系を 楕円曲線上の演算体系にそのまま置き換えたもの。 Copyright(C)ICAT 暗号をとりまく最近の話題について

13 認証実用化実験協議会 平成10年度第1回定例研究会
1998/4/14 楕円暗号の利点 ・楕円曲線上の演算体系による離散対数問題は、通常の 法演算体系による離散対数問題より解くことが難しい と予想されている ・このためRSA暗号や ElGamal暗号よりも扱うデータ量 が少なくしかも高速に計算を行うことができる 鍵サイズ1024ビットのRSA暗号の安全性が、鍵サイズ 160ビットの楕円ElGamal暗号の安全性と同程度 ・楕円暗号はシステム固定のパラメータが多く、これを 最適化することでさらに高速化をはかることができる Copyright(C)ICAT 暗号をとりまく最近の話題について

14 認証実用化実験協議会 平成10年度第1回定例研究会
1998/4/14 RSA暗号と楕円暗号の性能 ･ RSA 暗号も楕円暗号も最適化された S/W なら 現在のパソコン上で充分高速 ･ ICカード等計算能力の限られた環境では RSA 暗号は低速なため専用ハードウエアが必要 ･ 楕円暗号は高速なのでこのような環境でも ソフトウエアだけで実現できる可能性がある ･ RSA 暗号は署名検証が署名生成よりも高速 楕円暗号は署名生成が署名検証よりも高速 Copyright(C)ICAT 暗号をとりまく最近の話題について

15 認証実用化実験協議会 平成10年度第1回定例研究会
1998/4/14 RSA1024 vs ECC160 総計算量比較の一例 RSA暗号 楕円ElGamal暗号 暗号化／署名検証 復号化／署名生成 ･ RSA公開鍵は65537固定，RSA署名にはChinese Remainder Theoremを利用 ･ 楕円曲線は素体 GF(p) 上で p=a-3 なるものを利用 ･ 楕円ElGamal署名生成時には1280バイトの事前テーブルを利用 Copyright(C)ICAT 暗号をとりまく最近の話題について

16 認証実用化実験協議会 平成10年度第1回定例研究会
1998/4/14 楕円暗号の標準化 ・IEEE P1363 RSA暗号を含む公開鍵暗号の標準化 数多くの方式を網羅的に収録, draft ・ANSI X9.62 楕円DSAアルゴリズムを記述, draft ・SET Version 2 議論途上、Version 1 と互換性なし Copyright(C)ICAT 暗号をとりまく最近の話題について

17 認証実用化実験協議会 平成10年度第1回定例研究会
1998/4/14 楕円暗号の安全性 ・システムパラメータの取り方によっては 安全性が失われることがある 弱い楕円曲線の例 (1) MOV Reduction が適用できる曲線 (2) Anomalous 曲線 ・現在知られている弱い楕円曲線の割合は 全体から見れば無視できるほど少ない ・暗号設計者が弱い楕円曲線にならないよう システムパラメータを設計するのは容易 Copyright(C)ICAT 暗号をとりまく最近の話題について

18 認証実用化実験協議会 平成10年度第1回定例研究会
1998/4/14 楕円暗号最前線 ・楕円曲線の設計手法 狙い撃ち生成法 vs ランダム生成法 狙い撃ち生成法は曲線の種類が限定されるが高速、 ランダム生成法は汎用的だが低速 ・楕円曲線の実装手法 PC用高性能CPU vs 組み込みマイコン PC用高性能CPUでは署名生成/検証が数～十数msec 組み込みマイコンでの実装例 (三菱電機)： 16bitマイコンM16C(10MHz)上の完全S/W実装 総メモリ4KBで楕円DSA署名150msec, 検証630msec Copyright(C)ICAT 暗号をとりまく最近の話題について

19 認証実用化実験協議会 平成10年度第1回定例研究会
1998/4/14 楕円暗号の今後 ・小型機器を中心に楕円暗号は用いられる ようになるであろう ・楕円暗号が RSA 暗号に完全にとってかわる とは考えにくい ・楕円暗号の現在唯一の欠点は「若い」こと ・安全性に関する議論が一段落するためには 今しばらくの時間が必要 Copyright(C)ICAT 暗号をとりまく最近の話題について