講演抄録/キーワード |
講演名 |
2019-05-17 10:30
[招待講演]Attacking Noisy Secret CRT-RSA Exponents in Binary Method (from ICISC 2018) ○大西健斗・國廣 昇(東大) ISEC2019-2 |
抄録 |
(和) |
本発表では,サイドチャネル攻撃に対するCRT-RSA暗号方式の安全性解析を行う.CRT-RSA暗号方式では,復号の際,二乗算と倍算の二種類の演算を用いてべき乗算を計算する.べき乗算の実行中にサイドチャネル攻撃を行うと,二乗算と倍算の実行履歴が取得可能である.Bernsteinらは,CHES 2017において,べき乗算がSliding Window法で実装された場合に,二乗算と倍算の実行履歴から,CRT-RSA秘密鍵を復元する手法を提案した.しかし,サイドチャネル攻撃によって得られる二乗算と倍算の実行履歴は,観測誤差等の影響で完全に正しく得られるとは限らず,この場合,Bernsteinらの攻撃が成功するとは限らない.本発表では,$w=1$,つまりBinary法において,二乗算と倍算の実行履歴が誤りつきで得られた場合に,正しい秘密鍵を復元するアルゴリズムを提案する.さらに,もし誤りが5.8%以下のとき,我々のアルゴリズムの時間計算量の期待値は多項式時間であることを証明する. |
(英) |
In this presentation, we give a security evaluation on the RSA encryption scheme with the Chinese remainder theorem (CRT-RSA), against side-channel attacks. In the CRT-RSA scheme, we calculate the exponentiations by squaring and multiplication operations during decryption. The square-and-multiply sequences of the exponentiation can be obtained by side-channel attacks. Bernstein et al. proposed the method recovering CRT-RSA secret keys from the square-and-multiply sequences of the exponentiation when the exponentiations are implemented by Sliding window method in CHES 2017. However, errors occur in the square and multiply sequences because of physical-information observation errors, due to which the secret keys cannot be recovered by using Bernstein et al.'s method, even if window size $w=1$ in sliding window exponentiation. In this presentation, we propose an algorithm for correcting the errors in the square-and-multiply sequences, and for obtaining the correct secret keys, when the square-and-multiply sequences are generated at $w=1$, namely, the binary method.
Moreover, we theoretically prove that the expected time complexity of our algorithm is in polynomial time, when the error rate is less than 5.8%. |
キーワード |
(和) |
CRT-RSA暗号方式 / べき乗算 / 誤り訂正 / サイドチャネル攻撃 / / / / |
(英) |
CRT-RSA Encryption Scheme / Exponentiation / Error Correction / Side-Channel Attacks / / / / |
文献情報 |
信学技報, vol. 119, no. 40, ISEC2019-2, pp. 3-3, 2019年5月. |
資料番号 |
ISEC2019-2 |
発行日 |
2019-05-10 (ISEC) |
ISSN |
Print edition: ISSN 0913-5685 Online edition: ISSN 2432-6380 |
著作権に ついて |
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します.(許諾番号:10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) |
PDFダウンロード |
ISEC2019-2 |