密码学报2016，Vol.3Issue(5)：447-461,15.DOI:10.13868/j.cnki.jcr.000142
CRT-RSA算法的选择明文攻击*
Chosen Plaintext Attacks on CRT-RSA
摘要
Abstract
The CRT-RSA algorithm is widely used because it is nearly four times as fast as normal RSA, so the security of its implementation is very important. In this paper, we propose two different chosen plaintext attacks on the CRT-RSA Digital Signature. For the first one, we control the values ofpSandSqby means of special plaintext then we can getp(q)andm modp(q)with the help of analyzing the correlation values, finally we get two secret prime keys of CRT-RSA. The second attack uses Montgomery modular multiplication by using Montgomery parameter R. To implement this attack, we need to select the traces according to the value of p or q. The first attack has two ways to implement. We describe the details of the second approach by experiments, the results show that correct keys always indicated the maximum rank among the candidates, furthermore the correlation value has noticeable superiority which extended to 0.01–0.03 compared with the second candidates. The time spent on attacking every 16 bits of the secret key is about 20 mins, and for the whole prime numberp, it takes about 10 hours. The simulation of the second method shows better result for bigger values of p or q. After traces selection, we used about 20000 traces to execute the attack. The results show that the correlation for right key is 0.15 which is 50% higher than other incorrect keys. It seems feasible to implement the attack. In the end we propose two countermeasures for the attack.关键词
CRT-RSA/选择明文/蒙哥马利域/相关性分析Key words
CRT-RSA/chosen plaintext/Montgomery field/DPA分类
信息技术与安全科学引用本文复制引用
李增局,彭乾,史汝辉,李超,马志鹏,李海滨..CRT-RSA算法的选择明文攻击*[J].密码学报,2016,3(5):447-461,15.基金项目
国家科技重大专项-核心电子器件、高端通用芯片及基础软件产品(2014ZX01032401) （2014ZX01032401）
