電子情報通信学会 研究会発表申込システム
講演論文 詳細
技報閲覧サービス
技報オンライン
‥‥ (ESS/通ソ/エレソ/ISS)
技報アーカイブ
‥‥ (エレソ/通ソ)
 トップに戻る 前のページに戻る   [Japanese] / [English] 

講演抄録/キーワード
講演名 2019-05-17 10:30
[招待講演]Attacking Noisy Secret CRT-RSA Exponents in Binary Method (from ICISC 2018)
大西健斗國廣 昇東大
技報オンラインサービス実施中
抄録 (和) 本発表では,サイドチャネル攻撃に対する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

研究会情報
研究会 ISEC  
開催期間 2019-05-17 - 2019-05-17 
開催地(和) 機械振興会館 
開催地(英) Kikai-Shinko-Kaikan Bldg. 
テーマ(和) 一般 
テーマ(英)  
講演論文情報の詳細
申込み研究会 ISEC 
会議コード 2019-05-ISEC 
本文の言語 日本語 
タイトル(和) Attacking Noisy Secret CRT-RSA Exponents in Binary Method (from ICISC 2018) 
サブタイトル(和)  
タイトル(英) Attacking Noisy Secret CRT-RSA Exponents in Binary Method (from ICISC 2018) 
サブタイトル(英)  
キーワード(1)(和/英) CRT-RSA暗号方式 / CRT-RSA Encryption Scheme  
キーワード(2)(和/英) べき乗算 / Exponentiation  
キーワード(3)(和/英) 誤り訂正 / Error Correction  
キーワード(4)(和/英) サイドチャネル攻撃 / Side-Channel Attacks  
キーワード(5)(和/英) /  
キーワード(6)(和/英) /  
キーワード(7)(和/英) /  
キーワード(8)(和/英) /  
第1著者 氏名(和/英/ヨミ) 大西 健斗 / Kento Oonishi / オオニシ ケント
第1著者 所属(和/英) 東京大学 (略称: 東大)
The University of Tokyo (略称: UTokyo)
第2著者 氏名(和/英/ヨミ) 國廣 昇 / Noboru Kunihiro / クニヒロ ノボル
第2著者 所属(和/英) 東京大学 (略称: 東大)
The University of Tokyo (略称: UTokyo)
第3著者 氏名(和/英/ヨミ) / /
第3著者 所属(和/英) (略称: )
(略称: )
第4著者 氏名(和/英/ヨミ) / /
第4著者 所属(和/英) (略称: )
(略称: )
第5著者 氏名(和/英/ヨミ) / /
第5著者 所属(和/英) (略称: )
(略称: )
第6著者 氏名(和/英/ヨミ) / /
第6著者 所属(和/英) (略称: )
(略称: )
第7著者 氏名(和/英/ヨミ) / /
第7著者 所属(和/英) (略称: )
(略称: )
第8著者 氏名(和/英/ヨミ) / /
第8著者 所属(和/英) (略称: )
(略称: )
第9著者 氏名(和/英/ヨミ) / /
第9著者 所属(和/英) (略称: )
(略称: )
第10著者 氏名(和/英/ヨミ) / /
第10著者 所属(和/英) (略称: )
(略称: )
第11著者 氏名(和/英/ヨミ) / /
第11著者 所属(和/英) (略称: )
(略称: )
第12著者 氏名(和/英/ヨミ) / /
第12著者 所属(和/英) (略称: )
(略称: )
第13著者 氏名(和/英/ヨミ) / /
第13著者 所属(和/英) (略称: )
(略称: )
第14著者 氏名(和/英/ヨミ) / /
第14著者 所属(和/英) (略称: )
(略称: )
第15著者 氏名(和/英/ヨミ) / /
第15著者 所属(和/英) (略称: )
(略称: )
第16著者 氏名(和/英/ヨミ) / /
第16著者 所属(和/英) (略称: )
(略称: )
第17著者 氏名(和/英/ヨミ) / /
第17著者 所属(和/英) (略称: )
(略称: )
第18著者 氏名(和/英/ヨミ) / /
第18著者 所属(和/英) (略称: )
(略称: )
第19著者 氏名(和/英/ヨミ) / /
第19著者 所属(和/英) (略称: )
(略称: )
第20著者 氏名(和/英/ヨミ) / /
第20著者 所属(和/英) (略称: )
(略称: )
講演者
発表日時 2019-05-17 10:30:00 
発表時間 30 
申込先研究会 ISEC 
資料番号 IEICE-ISEC2019-2 
巻番号(vol) IEICE-119 
号番号(no) no.40 
ページ範囲 p.3 
ページ数 IEICE-1 
発行日 IEICE-ISEC-2019-05-10 


[研究会発表申込システムのトップページに戻る]

[電子情報通信学会ホームページ]


IEICE / 電子情報通信学会