基于DPA对Gauss形式CRT-RSA的选择明文攻击

采用中国剩余定理(CRT)对RSA算法进行加速, 可将其计算速度提高约四倍, 因此CRT-RSA被广泛使用. CRT-RSA算法按结合部分的实现方式可以分为Gauss和Garner两种. 本文提出一种针对Gauss形式CRT-RSA算法的选择明文攻击方法, 攻击的目标操作为模乘运算. 本方法通过选择明文来操纵目标中间值, 然后采用分而治之的方式, 对密钥相关数据分段进行DPA攻击, 从而破解密钥. 文中提出的针对模乘运算带来问题的分而治之解决方案具有一般性, 对所有大数模乘的DPA攻击均有效. 文中分析指出, 为了降低攻击难度并提高攻击的成功率, 需要综合考虑DPA攻击样本空间大小和模乘运算分...

Full description

Saved in:
Bibliographic Details
Published in:Journal of Cryptologic Research 2016-04, Vol.3 (2), p.202
Main Authors: Zeng-Ju, LI, Ru-Hui, SHI, WANG, Jian-Xin, LI, Chao, Hai-Bin, LI, Xin-Ling, SHI, 李增局, 史汝辉, 王建新, 李 超, 李海滨, 石新凌
Format: Article
Language:Chinese
Subjects:
Integers
Messages
Multiplication
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:采用中国剩余定理(CRT)对RSA算法进行加速, 可将其计算速度提高约四倍, 因此CRT-RSA被广泛使用. CRT-RSA算法按结合部分的实现方式可以分为Gauss和Garner两种. 本文提出一种针对Gauss形式CRT-RSA算法的选择明文攻击方法, 攻击的目标操作为模乘运算. 本方法通过选择明文来操纵目标中间值, 然后采用分而治之的方式, 对密钥相关数据分段进行DPA攻击, 从而破解密钥. 文中提出的针对模乘运算带来问题的分而治之解决方案具有一般性, 对所有大数模乘的DPA攻击均有效. 文中分析指出, 为了降低攻击难度并提高攻击的成功率, 需要综合考虑DPA攻击样本空间大小和模乘运算分解的复杂度来决定最佳的选择明文参数的取值范围. 本文对智能IC上运行的1024bit的CRT-RSA运算进行了攻击实验, 在选择明文范围为0-5000的条件下, 使用5000条智能IC卡执行CRT-RSA运算的功耗曲线, 对p×pinv从最高字节开始进行多次分段DPA攻击, 首先对最高3个字节进行攻击, 之后以2字节为一段进行逐段攻击, 最终耗时4个小时攻击得到p×pinv的完整值, 从而完成CRT-RSA算法的破解. 最后本文给出了三种针对本攻击方法的防御方案.
ISSN:2097-4116
DOI:10.13868/j.cnki.jcr.000121