Presentation 2019-05-17
[Invited Talk] Attacking Noisy Secret CRT-RSA Exponents in Binary Method (from ICISC 2018)
Kento Oonishi, Noboru Kunihiro,
PDF Download Page PDF download Page Link
Abstract(in Japanese) (See Japanese page)
Abstract(in English) 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%.
Keyword(in Japanese) (See Japanese page)
Keyword(in English) CRT-RSA Encryption Scheme / Exponentiation / Error Correction / Side-Channel Attacks
Paper # ISEC2019-2
Date of Issue 2019-05-10 (ISEC)

Conference Information
Committee ISEC
Conference Date 2019/5/17(1days)
Place (in Japanese) (See Japanese page)
Place (in English) Kikai-Shinko-Kaikan Bldg.
Topics (in Japanese) (See Japanese page)
Topics (in English)
Chair Atsushi Fujioka(Kanagawa Univ.)
Vice Chair Shiho Moriai(NICT) / Shoichi Hirose(Univ. of Fukui)
Secretary Shiho Moriai(Tokai Univ.) / Shoichi Hirose(NICT)
Assistant Kazunari Omote(Tsukuba Univ.) / Yuuji Suga(IIJ)

Paper Information
Registration To Technical Committee on Information Security
Language JPN
Title (in Japanese) (See Japanese page)
Sub Title (in Japanese) (See Japanese page)
Title (in English) [Invited Talk] Attacking Noisy Secret CRT-RSA Exponents in Binary Method (from ICISC 2018)
Sub Title (in English)
Keyword(1) CRT-RSA Encryption Scheme
Keyword(2) Exponentiation
Keyword(3) Error Correction
Keyword(4) Side-Channel Attacks
1st Author's Name Kento Oonishi
1st Author's Affiliation The University of Tokyo(UTokyo)
2nd Author's Name Noboru Kunihiro
2nd Author's Affiliation The University of Tokyo(UTokyo)
Date 2019-05-17
Paper # ISEC2019-2
Volume (vol) vol.119
Number (no) ISEC-40
Page pp.pp.3-3(ISEC),
#Pages 1
Date of Issue 2019-05-10 (ISEC)