文献

J-GLOBAL ID：201802269606263236   整理番号：18A1490809

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

Extended Partial Key Exposure Attack on RSA

著者 (3件)： 鈴木海地 (東大 大学院新領域創成科学研究科) ,  高安敦 (東大 大学院情報理工学系研究科) ,  國廣昇 (東大 大学院情報理工学系研究科)
資料名： 電子情報通信学会技術研究報告  (IEICE Technical Report (Institute of Electronics, Information and Communication Engineers))
巻： 118  号： 152(SITE2018 5-41)  ページ： 155-162  発行年： 2018年07月18日 
JST資料番号： S0532B  ISSN： 0913-5685  資料種別： 会議録 (C)
記事区分： 原著論文  発行国： 日本 (JPN)  言語： 日本語 (JA)

抄録/ポイント： RSA暗号において,秘密鍵の上位ビットもしくは下位ビットが漏洩したときに鍵全体を復元する多項式時間攻撃アルゴリズムが,Coppersmithの手法を用いてこれまで活発に研究されてきた。この攻撃設定において,Ernstらの攻撃(Eurocrypt’05)とTakayasu-Kunihiroの攻撃(SAC’14)が,現在知られている最も良い攻撃であり,上位と下位いずれのビットが得られる場合も,d<N^×=×=(9-√<span style=text-decoration:overline>21</span>/12のときに後者は前者より少ない部分情報で攻撃が可能である。ただし,Ernstらは,自身の提案攻撃は,上位ビットと下位ビットが同時に漏洩したときの攻撃に,拡張可能であることをも示した。彼らの拡張攻撃は,この攻撃設定において,現在知られている最も良い攻撃である。本論文で,我々は,秘密鍵がd<N^×=×=(9-√<span style=text-decoration:overline>21</span>/12を満たすほど小さく,その上位ビットと下位ビットが同時に漏洩したときに,Ernstらの攻撃を改良する新たな攻撃アルゴリズムを提案する。提案攻撃は,Takayasu-Kunihiroの攻撃の拡張となっているが,Ernstらの拡張とは違い,その構成は非自明である。Ernstらの攻撃は,単純な多項式の選択によって得られるのに対し,Takayasu-Kunihiroの攻撃は,上位もしくは下位ビットが得られたときそれぞれに応じて,複雑かつ異なる変数変換を用いて多項式を構成することによって得られる。我々は,これら二つを特別な場合として含む,より統一的な変数変換を導入することで,Takayasu-Kunihiroの攻撃を拡張する。(著者抄録)

シソーラス用語： *公開鍵暗号 ,  暗号鍵 ,  *部分 ,  *漏れ ,  理論 ,  変数 ,  変換 ,  暗号理論
準シソーラス用語： *RSA暗号 ,  *暗号攻撃 ,  格子理論 ,  *情報漏洩 ,  秘密鍵

分類 (2件)： 符号理論  (ND02030R) ,  データ保護  (JD01020V)

引用文献 (14件)：

• Blömer J., May A. ′′New partial key exposure attacks on RSA.′′ CRYPTO 2003. LNCS, vol. 2729, pp. 27-43. (2003)
• Boneh D., Durfee G. ′′Cryptanalysis of RSA with private key d less than N^0.292.′′ IEEE Trans. Information Theory 46(4), pp. 1339-1349. (2000)
• Coppersmith D. ′′Finding a small root of a univariate modular equation.′′ EUROCRYPT 1996. LNCS, vol. 1070, pp. 155-165 (1996)
• Ernst M., Jochemsz E., May A., de Weger B. ′′Partial key exposure attacks on RSA up to full size exponents.′′ EUROCRYPT 2005. LNCS, vol. 3494, pp. 371-386. (2005)
• Herrmann M., May A. ′′Attacking power generators using unravelled linearization: When do we output too much?′′ ASIACRYPT 2009. LCNS, vol. 5912, pp. 487-504. (2009)

タイトルに関連する用語 (5件)： RSA暗号 ,  鍵 ,  導出 ,  攻撃 ,  拡張