Sliding Window法の誤りつき演算情報を用いたCRT-RSA秘密鍵復元手法

• Item type: Symposium(1)
• 公開日: 2019-10-14
• タイトル: Sliding Window法の誤りつき演算情報を用いたCRT-RSA秘密鍵復元手法
• タイトル / 言語: en
• タイトル: Recovering CRT-RSA Secret Keys from Square-and-Multiply Sequences with Errors in Sliding Window Method
• 言語: jpn
• キーワード / 主題Scheme: Other
• キーワード / 主題: CRT-RSA暗号方式，べき乗算，Sliding Window法，秘密鍵復元，誤り訂正
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_5794
• 資源タイプ: conference paper
• 著者所属: 東京大大学院情報理工学系研究科
• 著者所属: 筑波大学大学院システム系
• 著者所属(英): en
• 著者所属(英): Graduate School of Information Science and Technology, The University of Tokyo
• 著者所属(英): en
• 著者所属(英): University of Tsukuba
• 著者名: 大西, 健斗; 國廣, 昇
• 著者名(英): Kento, Oonishi; Noboru, Kunihiro
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 本発表では，Sliding Window法で実装されたCRT-RSA暗号方式に対し，サイドチャネル情報を用いた秘密鍵復元手法を提案する．Sliding Window法は，二乗算と倍算を用いた，べき乗算の計算手法である．Bernsteinらは，CHES 2017 において，Sliding Window法の二乗算と倍算の実行履歴の取得手法を提案した．さらに，彼らは，実行履歴が正確に取得された状況下で，CRT-RSA秘密鍵復元手法を提案し，window 幅 ωが 4 以下ならば，秘密鍵復元が多項式時間であることを証明した．しかし，実際の実行履歴の取得には誤りが伴い，その場合，彼らの手法は，秘密鍵復元に失敗する．OonishiとKunihiroは，誤りつき実行履歴からの秘密鍵復元手法を提案したが，ω= 1,2の場合でしか，多項式時間で復元可能な誤りの解析を行っていない．本発表では，まず，新たな秘密鍵復元手法を提案する．次に，ω =1,2 では，より多くの誤りの下で，多項式時間で復元可能であることを証明し，ω= 3,4 においても，復元可能な誤りの解析を行う．さらに，数値実験による検証を行う．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: We discuss side-channel attacks on the CRT-RSA encryption scheme implemented by Sliding Window method. Sliding Window method calculates exponentiations by repeating squaring and multiplication. In CHES~2017, Bernstein et al. proposed side-channel attacks of obtaining square-and-multiply sequences in Sliding Window method. Moreover, they proposed the method of recovering CRT-RSA secret keys from the correct square-and-multiply sequences, and they proved that their method recover secret keys in polynomial time when window size ω is less than 4. However, there are errors in obtained square-and-multiply sequences, and their method fail to recover secret keys because of errors. Oonishi and Kunihiro proposed the method of recovering secret keys from square-and-multiply sequences with errors, but they analyze tolerable errors only when ω=1,2. In this presentation, we propose new method of recovering secret keys. We prove that we recover secret keys in polynomial time with more errors when ω=1,2 than previous result, and we analyze tolerable errors when ω=3,4. After that, we verify our analysis by numerical experiment.
• 書誌レコードID / 識別子タイプ: NCID
• 書誌レコードID / 関連識別子: ISSN 1882-0840
• 書誌情報: コンピュータセキュリティシンポジウム2019論文集; 巻 2019, p. 792-799, 発行日 2019-10-14
• 出版者 / 言語: ja
• 出版者: 情報処理学会