| 電子情報通信学会 研究会発表申込システム 講演論文 詳細 |
技報閲覧サービス [ログイン] 技報アーカイブ |
| トップに戻る | 前のページに戻る | [Japanese] / [English] |
| 講演抄録／キーワード | ||
| 講演名 | 2018-07-25 15:50 RSA暗号の部分鍵導出攻撃の拡張 ○鈴木海地・高安 敦・國廣 昇（東大）  ISEC2018-29 SITE2018-21 HWS2018-26 ICSS2018-32 EMM2018-28 |
|
| 抄録 | （和） | RSA暗号において，秘密鍵の上位ビットもしくは下位ビットが漏洩したときに鍵全体を復元する多項式時間攻撃アルゴリズムが，Coppersmithの手法を用いてこれまで活発に研究されてきた． この攻撃設定において，Ernstらの攻撃(Eurocrypt'05)とTakayasu-Kunihiroの攻撃(SAC'14)が，現在知られている最も良い攻撃であり，上位と下位いずれのビットが得られる場合も，$d<N^{(9-sqrt{21})/12}$のときに後者は前者より少ない部分情報で攻撃が可能である． ただし，Ernstらは，自身の提案攻撃は，上位ビットと下位ビットが同時に漏洩したときの攻撃に，拡張可能であることをも示した． 彼らの拡張攻撃は，この攻撃設定において，現在知られている最も良い攻撃である． 本論文で，我々は，秘密鍵が$d<N^{(9-sqrt{21})/12}$を満たすほど小さく，その上位ビットと下位ビットが同時に漏洩したときに，Ernstらの攻撃を改良する新たな攻撃アルゴリズムを提案する． 提案攻撃は，Takayasu-Kunihiroの攻撃の拡張となっているが，Ernstらの拡張とは違い，その構成は非自明である． Ernstらの攻撃は，単純な多項式の選択によって得られるのに対し，Takayasu-Kunihiroの攻撃は，上位もしくは下位ビットが得られたときそれぞれに応じて，複雑かつ異なる変数変換を用いて多項式を構成することによって得られる． 我々は，これら二つを特別な場合として含む，より統一的な変数変換を導入することで，Takayasu-Kunihiroの攻撃を拡張する． |
| （英） | Thus far, emph{partial key exposure attacks} on RSA, i.e., attackers are given the most significant bits (MSBs) emph{or} the least significant bits (LSBs) of $d$, have been actively studied. The best known attacks are Ernst et al.'s attack~(Eurocrypt'05) and Takayasu-Kunihiro's attack~(SAC'14), where the latter attack is better than the former for $d<N^{(9-sqrt{21})/12}$. In the same work, Ernst et al. extended their proposed attack to another attack scenario when attackers are given the MSBs emph{and} the LSBs of $d$. The attack is the best known one in the scenario. In this paper, we proposed an improved partial key exposure attack with the MSBs emph{and} the LSBs of $d$. In particular, our attack is better than Ernst al.'s attack for $d<N^{(9-sqrt{21})/12}$. We obtain the attack by extending Takayasu-Kunihiro's attacks. Since complex variable transformations which depend on positions of known bits are core technique of Takayasu-Kunihiro's attack, we develop a general variable transformation which covers previous ones and obtain our attack. |
|
| キーワード | （和） | RSA暗号 / 部分鍵導出攻撃 / Coppersmithの手法 / 格子理論 / / / / |
| （英） | RSA / partial key exposure / Coppersmith's method / lattice / / / / | |
| 文献情報 | 信学技報, vol. 118, no. 151, ISEC2018-29, pp. 155-162, 2018年7月. | |
| 資料番号 | ISEC2018-29 | |
| 発行日 | 2018-07-18 (ISEC, SITE, HWS, ICSS, EMM) | |
| ISSN | Print edition: ISSN 0913-5685 Online edition: ISSN 2432-6380 | |
| 著作権に ついて |
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します．(許諾番号：10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) | |
| PDFダウンロード | ISEC2018-29 SITE2018-21 HWS2018-26 ICSS2018-32 EMM2018-28 |
|
| 研究会情報 | |
| 研究会 | HWS ISEC SITE ICSS EMM IPSJ-CSEC IPSJ-SPT |
| 開催期間 | 2018-07-25 - 2018-07-26 |
| 開催地（和） | 札幌コンベンションセンター |
| 開催地（英） | Sapporo Convention Center |
| テーマ（和） | セキュリティ、一般 |
| テーマ（英） | Security, etc. |
| 講演論文情報の詳細 | |
| 申込み研究会 | ISEC |
| 会議コード | 2018-07-HWS-ISEC-SITE-ICSS-EMM-CSEC-SPT |
| 本文の言語 | 日本語 |
| タイトル（和） | RSA暗号の部分鍵導出攻撃の拡張 |
| サブタイトル（和） | |
| タイトル（英） | Extended Partial Key Exposure Attacks on RSA |
| サブタイトル（英） | |
| キーワード(1)（和/英） | RSA暗号 / RSA |
| キーワード(2)（和/英） | 部分鍵導出攻撃 / partial key exposure |
| キーワード(3)（和/英） | Coppersmithの手法 / Coppersmith's method |
| キーワード(4)（和/英） | 格子理論 / lattice |
| キーワード(5)（和/英） | / |
| キーワード(6)（和/英） | / |
| キーワード(7)（和/英） | / |
| キーワード(8)（和/英） | / |
| 第1著者 氏名（和/英/ヨミ） | 鈴木 海地 / Kaichi Suzuki / スズキ カイチ |
| 第1著者 所属（和/英） | 東京大学 (略称： 東大) University of Tokyo (略称： Univ. of Tokyo) |
| 第2著者 氏名（和/英/ヨミ） | 高安 敦 / Atsushi Takayasu / タカヤス アツシ |
| 第2著者 所属（和/英） | 東京大学 (略称： 東大) University of Tokyo (略称： Univ. of Tokyo) |
| 第3著者 氏名（和/英/ヨミ） | 國廣 昇 / Noboru Kunihiro / クニヒロ ノボル |
| 第3著者 所属（和/英） | 東京大学 (略称： 東大) University of Tokyo (略称： Univ. of Tokyo) |
| 講演者 | 第1著者 |
| 発表日時 | 2018-07-25 15:50:00 |
| 発表時間 | 25分 |
| 申込先研究会 | ISEC |
| 資料番号 | ISEC2018-29, SITE2018-21, HWS2018-26, ICSS2018-32, EMM2018-28 |
| 巻番号（vol） | vol.118 |
| 号番号（no） | no.151(ISEC), no.152(SITE), no.153(HWS), no.154(ICSS), no.155(EMM) |
| ページ範囲 | pp.155-162 |
| ページ数 | 8 |
| 発行日 | 2018-07-18 (ISEC, SITE, HWS, ICSS, EMM) |
[研究会発表申込システムのトップページに戻る]