Frequency Domain Horizontal Cross Correlation Analysis of RSA

This study shows that a previously published cross correlation based power analysis (CCPA) attack applied to the Montgomery Ladder exponentiation steps of a Rivest Shamir Adleman (RSA) implementation can be improved by working in frequency domain. It is shown that utilizing cross correlation values of discrete Fourier transform (DFT) coefficients instead of time samples, requires lesser power traces to retrieve the key bits of the target implementation. In addition, instead of using DFT coefficients corresponding to the whole measured frequency band, using a few DFT coefficients corresponding to lower bands, even under the first harmonic of the target clock is also an improving factor on the performance of the CCPA. Practical and theoretical results are also compared to both domains. To the best of our knowledge, this is the first study to show the frequency domain applicability and superiorities in terms of horizontal CCPA type attacks.