Security Evaluation Of Modular Exponentiation Algorithm For Extra-reduction Correlation Attacks

Modular exponentiation algorithm,as the core operation of public key algorithm,is the main target of side channel attack.Since the first timed attack was published,the attacker can use the modular exponentiation algorithm in the public key cryptosystem to recover secret information through a side channel attack.Because the "leak" physical information released by the cryptographic device is strongly related to the modular exponentiation algorithm,the unprotected modular exponentiation algorithm provides various possibilities for side-channel attacks.With the development of the side channel attack technology for more than 20 years,the research on the security of the modular exponentiation algorithm against the side channel attack is a very important research topic.So far,there are many side channel attack methods on the modular exponentiation algorithm,but most of them are performed on the binary modular exponentiation algorithm.This thesis starts with the modular exponentiation algorithm,and after studying in-depth the existing attack methods based on extra-reduction information leakage,the correlation attack using extra-reduction is extended from the binary modular power algorithm to a fixed window modular power algorithm to further improve the accuracy of the security assessment.This thesis aims to arouse the attention and research of attack protection researchers on the security of public key algorithms in many aspects.The related work around the modular exponentiation algorithm is as follows:(1): Propose a correlation attack scheme to the fixed window modular exponentiation algorithm.Since the extra-reduction is an inevitable subtraction operation related to the calculation data in the modular power operation,the side channel attacks on the public key algorithm using the extra reduction are not rare.Among them,Dugardin et al.successfully recovered the secret information based on the negative correlation between the extra-reduction of two consecutive modular multiplication operations.However,this thesis notices that the correlation is only applicable to the binary modular exponentiation algorithm and cannot be directly extended to the fixed window modular exponential algorithm.Through careful analysis,two extra-reduction correlations applicable to the fixed window modular exponential algorithm are proposed.After analyzing the attack framework in detail,without changing the attack scenario,this thesis proposes a corresponding attack scheme based on the correlation of the fixed window modular exponentiation algorithm found,and verifies the effectiveness and feasibility through simulation experiments.(2): Optimize the proposed attack scheme.Comprehensively study the correlation between two kinds of fixed window modular power algorithms,and find that according to the attack idea proposed by Dugardin et al.,The extra-reduction correlation cannot be fully utilized,so an attack scheme for a fixed window modular power algorithm combining two correlations is proposed.Simulation experiment results show that the attack scheme reduces the minimum number of samples to successfully recover the complete key from 5000-6000 to 1000-2000 under the same attack scenario.