Abstract:
This paper presents an improved method for timing attack. It can attack the fast implementation of RSA, including Montgomery ex¬ponentiation algorithm and Chinese re¬mainder theorem. It gets the relationship between the input parameters and execution time of RSA by analyzing the probability of extra reduction during Montgomery ex¬ponentiation operation, and gets the secret factors bit by bit by timing analyzing with the chosen input ciphertexts, and exposes the factorization of RSA.
Key words:
RSA,
Timing attack,
Montgomery reduction,
Chinese remainder theorem,
Extra reduction
摘要: 给出了一种改进的计时攻击方法。针对采用Montgomery模指数运算和中国剩余定理的RSA快速实现算法,通过分析在Montgomery模指数运算中额外约简发生的概率,得到RSA输入参数与运行时间之间的关系,并通过选择密文输入,计时分析按位获取RSA的秘密因子,最终破解了RSA的因子分解。
关键词:
RSA,
计时攻击,
Montgomery约简,
中国剩余定理,
额外约简
CLC Number:
ZHANG Peng; CHEN Kaiyan; ZHAO Qiang. Timing Attack on Fast Implementation Algorithm of RSA[J]. Computer Engineering, 2007, 33(12): 191-192,.
张 鹏;陈开颜;赵 强. 针对RSA快速实现算法的计时攻击[J]. 计算机工程, 2007, 33(12): 191-192,.