A New Side-Channel Attack on Reduction of RSA-CRT Montgomery Method Based

S. Kaedi | Mohammadali Doostari | H. Yusefi | M. B. Ghaznavi-Ghoushchi

---

URL :   http://research.shahed.ac.ir/WSR/WebPages/Report/PaperView.aspx?PaperID=158441
Date :  2020/05/17
Publish in :    Journal of circuit, system and computer
DOI :  https://doi.org/10.1142/S0218126621500389
Link :  http://dx.doi.org/10.1142/S0218126621500389
Keywords :RSA, CRT, Montgomery multiplication, Side-channel attack, MRED attack

Abstract :

---

RSA-CRT is one of the most common algorithms in the digital signature. Several side-channel attacks have been presented on the implementation of RSA-CRT. One of the most important side-channel attacks on RSA-CRT is Modular Reduction on Equidistant Data (MRED). The implementation of RSA-CRT has too many challenges in the multiplications when the key size is too long (e.g. 2048 bit). Montgomery multiplication is one of the common methods for executing the RSA multiplication, which has many implementation problems and side-channel leakage challenges. This article first implements an RSA-CRT algorithm based on the Montgomery multiplication with the high speed and low area hardware. The implementation is named RSA-CRT-MMB (Montgomery Method Based). Next, a new power analysis side-channel attack on RSA-CRT-MMB is presented. We name our attack “Modular Reduction on Equidistant Data on MMB (MREDM).” The attack utilizes new side-channel leakage information about the CRT reduction algorithm implemented by the MMB, for the first time. The past related articles do not investigate the MRED attack on Montgomery multiplication in RSA-CRT. Finally, a new countermeasure is presented to prevent the MREDM attack. The countermeasure does not have any overload in the hardware area or running time of the RSA algorithm. The correctness of our scheme, the 2048-bit RSA-CRT-MMB, is investigated by the implementation of the scheme on the SASEBO-W board in our DPA laboratory. The total running time of 2048-bit RSA is 250 ms and the RSA algorithm occupies only 23 of LUT slice on Spartan-6 FPGA. The proposed countermeasures are also verified by practical experiments.