| 講演名 | 2009-03-10 パリティ検査式を動的に構成する高速相関攻撃におけるLFSRの初期値推定アルゴリズムの改良(情報通信基礎サブソサイエティ合同研究会) 斎藤 裕瑛, 毛利 公美, 福田 洋治, 白石 善明, |
|---|---|
| PDFダウンロードページ |  PDFダウンロードページへ |
| 抄録(和) | ストリーム暗号用の擬似乱数生成器である非線形コンバイナ型乱数生成器(NCG)の予測不可能性の解析アプローチとして高速相関攻撃(FCA)がよく知られている.FCAは,NCGの構成を既知と仮定し,平文と暗号文の対からNCGの出力ビット列を求め,NCGを構成する線形フィードバックシフトレジスタ(LFSR)の出力ビット列とNCGの出力ビット列の相関関係からLFSRの初期値を再構成する攻撃である.先に福田,白石,森井らは,事後確率復号法を利用して量LFSRの初期値を推定する際に,推定済みのビット情報からパリティ検査式の集合を動的に構成,それを使用するFCA(D-FCA)を提案している.本稿では,D-FCAにおける,LFSRの初期値推定アルゴリズムの改良手法を提案し,計算機上のシミュレーション実験により攻撃のリミットノイズが向上することを示す. |
| 抄録(英) | Fast correlation attack (FCA) has been known as a method of cryptanalysis for the unpredictability of Nonlinear Combiner Generator (NCG) which is a pseudo-random number generator of stream ciphers. FCA is a known plaintext attack under the condition that the constitution of NCG is known, reconstructs an initial value of linear feedback shift register (LFSR) by using correlation of the LFSR output bits and the NCG output bits which is obtained by a pair of plaintext and the ciphertext. Fukuta, Shiraishi and Morii have proposed an FCA (D-FCA) estimating the initial states of a LFSR by using dynamically constructed parity check equations. It is based on APP based threshold decoding for binary linear codes. In this paper, we propose a method which improved the D-FCA. Furthermore, we show that our method is effective compared with conventional methods by results of attack simulation on a computer. Using our method, the noise limit is improved. |
| キーワード(和) | ストリーム暗号 / 高速相関攻撃 / 線形フィードバックシフトレジスタ / パリティ検査式 / 2元線形符号 |
| キーワード(英) | stream ciphers / fast correlation attack / linear feedback shift registers / parity check equations / binary linear codes |
| 資料番号 | IT2008-84,ISEC2008-142,WBS2008-97 |
| 発行日 |
| 研究会情報 | |
| 研究会 | WBS |
|---|---|
| 開催期間 | 2009/3/2(から1日開催) |
| 開催地（和） | |
| 開催地（英） | |
| テーマ（和） | |
| テーマ（英） | |
| 委員長氏名（和） | |
| 委員長氏名（英） | |
| 副委員長氏名（和） | |
| 副委員長氏名（英） | |
| 幹事氏名（和） | |
| 幹事氏名（英） | |
| 幹事補佐氏名（和） | |
| 幹事補佐氏名（英） | |
| 講演論文情報詳細 | |
| 申込み研究会 | Wideband System(WBS) |
|---|---|
| 本文の言語 | JPN |
| タイトル（和） | パリティ検査式を動的に構成する高速相関攻撃におけるLFSRの初期値推定アルゴリズムの改良(情報通信基礎サブソサイエティ合同研究会) |
| サブタイトル（和） | |
| タイトル（英） | Improvement of LFSR Initial State Reconstruction Algorithm in Fast Correlation Attack Using Dynamically Constructed Parity Check Equations |
| サブタイトル（和） | |
| キーワード(1)（和/英） | ストリーム暗号 / stream ciphers |
| キーワード(2)（和/英） | 高速相関攻撃 / fast correlation attack |
| キーワード(3)（和/英） | 線形フィードバックシフトレジスタ / linear feedback shift registers |
| キーワード(4)（和/英） | パリティ検査式 / parity check equations |
| キーワード(5)（和/英） | 2元線形符号 / binary linear codes |
| 第 1 著者 氏名（和/英） | 斎藤 裕瑛 / Hiroaki SAITOH |
| 第 1 著者 所属（和/英） | 岐阜大学工学部 Faculty of Engineering, Gifu University |
| 第 2 著者 氏名（和/英） | 毛利 公美 / Masami MOHRI |
| 第 2 著者 所属（和/英） | 岐阜大学工学部 Faculty of Engineering, Gifu University |
| 第 3 著者 氏名（和/英） | 福田 洋治 / Youji FUKUTA |
| 第 3 著者 所属（和/英） | 愛知教育大学教育学部 Faculty of Education, Aichi University of Education |
| 第 4 著者 氏名（和/英） | 白石 善明 / Yoshiaki SHIRAISHI |
| 第 4 著者 所属（和/英） | 名古屋工業大学大学院工学研究科 Graduate School of Engineering, Nagoya Instisute of Technology |
| 発表年月日 | 2009-03-10 |
| 資料番号 | IT2008-84,ISEC2008-142,WBS2008-97 |
| 巻番号（vol） | vol.108 |
| 号番号（no） | 474 |
| ページ範囲 | pp.- |
| ページ数 | 8 |
| 発行日 | |