| 講演名 | 2004-07-20 小林らのガウス整数環上のTSP暗号の解読 林 彬, |
|---|---|
| PDFダウンロードページ |  PDFダウンロードページへ |
| 抄録(和) | 小林邦勝氏らが提案したガウス整数を用いた巡回セールスマン暗号の解読法を提案し,計算機による実証実験の結果を示す.当暗号での暗号化は,加算と乗算とを組み合せるのでLagarias-Odlyzko法(LO法)は適用できないと考えられていた.我々の方法はまず乗算した鍵をはずすことによって,残りの加算部分に対するLO法の適用を可能にする.計算機実験では都市数15までの解読を試み,40%以上の解読率を得た. |
| 抄録(英) | We propose a method for breaking one of the traveling-salesman cryptosystems invented by K. Kobayashi and his students. The target system is different from their previous ones in the following two ways. First, each path has a length of Gaussian integer. Secondly, mixed arithmetic operations of addition and multiplication are used in encipherment. In the present attack multiplied keys are first found, and then the remaining summed part is analyzed by the Lagarias-Odlyzko method. The success rate of atttacks obtained from computer experiments was more than 40% in the case of 5-15 cities. |
| キーワード(和) | 公開鍵暗号 / 巡回セールスマン暗号 / 暗号解読 / ラガリアス・オドリズコ法 |
| キーワード(英) | public-key cryptography / traveling-salesman cryptosystems / cryptanalysis / Lagaris-Odlyzko attack |
| 資料番号 | ISEC2004-20 |
| 発行日 |
| 研究会情報 | |
| 研究会 | ISEC |
|---|---|
| 開催期間 | 2004/7/13(から1日開催) |
| 開催地（和） | |
| 開催地（英） | |
| テーマ（和） | |
| テーマ（英） | |
| 委員長氏名（和） | |
| 委員長氏名（英） | |
| 副委員長氏名（和） | |
| 副委員長氏名（英） | |
| 幹事氏名（和） | |
| 幹事氏名（英） | |
| 幹事補佐氏名（和） | |
| 幹事補佐氏名（英） | |
| 講演論文情報詳細 | |
| 申込み研究会 | Information Security (ISEC) |
|---|---|
| 本文の言語 | JPN |
| タイトル（和） | 小林らのガウス整数環上のTSP暗号の解読 |
| サブタイトル（和） | |
| タイトル（英） | An Attack against the Traveling Salesman Cryptosystem |
| サブタイトル（和） | |
| キーワード(1)（和/英） | 公開鍵暗号 / public-key cryptography |
| キーワード(2)（和/英） | 巡回セールスマン暗号 / traveling-salesman cryptosystems |
| キーワード(3)（和/英） | 暗号解読 / cryptanalysis |
| キーワード(4)（和/英） | ラガリアス・オドリズコ法 / Lagaris-Odlyzko attack |
| 第 1 著者 氏名（和/英） | 林 彬 / Akira HAYASHI |
| 第 1 著者 所属（和/英） | 金沢工業大学 Kanazawa Institute of Technology |
| 発表年月日 | 2004-07-20 |
| 資料番号 | ISEC2004-20 |
| 巻番号（vol） | vol.104 |
| 号番号（no） | 199 |
| ページ範囲 | pp.- |
| ページ数 | 4 |
| 発行日 | |