RSA暗号の部分鍵導出攻撃の拡張

• Item type: SIG Technical Reports(1)
• 公開日: 2018-07-18
• タイトル: RSA暗号の部分鍵導出攻撃の拡張
• タイトル / 言語: en
• タイトル: Extended Partial Key Exposure Attack on RSA
• 言語: jpn
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: 東京大学大学院新領域創成科学研究科
• 著者所属: 東京大学大学院情報理工学系研究科
• 著者所属: 東京大学大学院情報理工学系研究科
• 著者所属(英): en
• 著者所属(英): Graduate School of Frontier Sciences, University of Tokyo
• 著者所属(英): en
• 著者所属(英): Graduate School of Information Science and Technology, University of Tokyo
• 著者所属(英): en
• 著者所属(英): Graduate School of Information Science and Technology, University of Tokyo
• 著者名: 鈴木, 海地; 高安, 敦; 國廣, 昇
• 著者名(英): Kaichi, Suzuki; Atsushi, Takayasu; Noboru, Kunihiro
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: RSA 暗号において，秘密鍵の上位ビットもしくは下位ビットが漏洩したときに鍵全体を復元する多項式時間攻撃アルゴリズムが，Coppersmith の手法を用いてこれまで活発に研究されてきた．この攻撃設定において，Ernst らの攻撃 (Eurocrypt' 05) と Takayasu-Kunihiro の攻撃 (SAC' 14) が，現在知られている最も良い攻撃であり，上位と下位いずれのビットが得られる場合も，d < N (9 -√21) / 12 のときに後者は前者より少ない部分情報で攻撃が可能である．ただし，Ernst らは，自身の提案攻撃は，上位ピットと下位ビットが同時に漏洩したときの攻撃に，拡張可能であることをも示した．彼らの拡張攻撃は，この攻撃設定において，現在知られている最も良い攻撃である．本論文で，我々は，秘密鍵が d < N (9 － √21) / 12 を満たすほど小さく，その上位ビットと下位ビットが同時に漏洩したときに，Ernst らの攻撃を改良する新たな攻撃アルゴリズムを提案する．提案攻撃は，Takayasu-Kunihiro の攻撃の拡張となっているが，Ernst らの拡張とは違い，その構成は非自明である．Ernst らの攻撃は，単純な多項式の選択によって得られるのに対し，Takayasu-Kunihiro の攻撃は，上位もしくは下位ビットが得られたときそれぞれに応じて，複雑かつ異なる変数変換を用いて多項式を構成することによって得られる．我々は，これら二つを特別な場合として含む，より統一的な変数変換を導入することで，Takayasu-Kunihiro の攻撃を拡張する．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: Thus far, partial key exposure attacks on RSA, i.e., attackers are given the most significant bits (MSBs) 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 -√21) / 12. In the same work, Ernst et al. extended their proposed attack to another attack scenario when attackers are given the MSBs 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 and the LSBs of d. In particular, our attack is better than Ernst al.'s attack for d < N (9 -√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.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AA12628305
• 書誌情報: 研究報告セキュリティ心理学とトラスト（SPT）; 巻 2018-SPT-29, 号 26, p. 1-8, 発行日 2018-07-18
• ISSN / 収録物識別子タイプ: ISSN
• ISSN / 収録物識別子: 2188-8671
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会