针对从右到左平方乘算法的RSA故障分析

陈财森， 杜家兴， 喻 武， 邓柳于勤

(1. 装甲兵工程学院科研部，北京 100072; 2. 装甲兵工程学院训练部，北京100072;3. 装甲兵工程学院信息工程系，北京 100072)

针对从右到左平方乘算法的RSA故障分析

陈财森1， 杜家兴1， 喻 武2， 邓柳于勤3

(1. 装甲兵工程学院科研部，北京 100072; 2. 装甲兵工程学院训练部，北京100072;3. 装甲兵工程学院信息工程系，北京 100072)

提出了针对从右到左平方乘算法实现的RSA故障分析算法，该算法利用多次在模幂运算执行过程中在不同指定位置对模数N注入故障获得的故障签名，通过密钥搜索恢复出参与故障运算的密钥片断，最终恢复完整密钥。从理论上分析了该算法的复杂度，并通过仿真实验进行了验证，得到了密钥搜索空间和所需注入故障数目与一次攻击恢复密钥片断长度之间的对应关系。

旁路攻击；故障分析；模幂运算；从右到左平方乘算法；RSA

目前，随着电子综合信息系统在武器装备自动化控制系统中的广泛应用，智能卡芯片作为密码设备中的基础设施，为武器系统安全提供了有力支撑，尤其是在设备安全认证方面，RSA芯片发挥着重要作用，因此其安全性越来越被研究者们所关注。

随着现代技术手段的不断提高和广泛应用，单纯从密码算法数学结构的角度研究密码芯片安全性已经远远不够，还需要从密码算法的实现角度来考虑其安全性问题。在实际应用中，密码算法通常在各种芯片上实现，如智能卡、加密存储卡和加密机芯片等，密码算法在这些芯片中产生的故障信息可能被攻击者用来破解密码。故障攻击是指通过辐射、X光、微探测或改变电压等方法在芯片中注入故障，依据从芯片泄漏的信息推算出密钥的一种攻击方式。1996年，Boneh等[1]首次提出了利用随机硬件故障攻击RSA签名算法的攻击思想；2002年，Aumuller等[2]针对采用中国剩余定理(Chinese Remainder Theorem, CRT)的RSA算法提出了差分故障攻击算法；2013年，Fouque等[3]提出了基于蒙哥马利乘法实现模幂运算的RSA-CRT签名算法的故障攻击方案，并给出了3个针对小寄存器的故障模型；国内研究者[4-5]多数是针对RSA-CRT算法的故障攻击展开研究。

由于RSA-CRT算法实现过程较为复杂，因此在智能卡芯片的硬件实现过程中一般都采用执行速度较快的“Right-to-Left(从右到左)”平方乘算法。由于原有针对RSA-CRT算法的故障分析方法对平方乘算法实现的RSA存在一定的不适用性，本文为此展开研究，依据模型参数，建立故障分析模型，给出在执行模幂运算过程中针对模数N注入随机字节故障的攻击算法。

1 RSA算法与故障攻击模型

1.1 RSA公钥密码算法

RSA是使用公钥(N,e)加密和私钥d解密的公钥加密系统。它使用的模数N是2个大素数p和q的乘积(N=p×q)，指数e和d必须满足e×d=1mod(p-1)(q-1)。加密运算执行C=memodN，解密运算执行m=CdmodN，可以看出其核心是模幂运算m=CdmodN。一般RSA算法模幂运算采用平方乘算法，分为“Left-to-Right(从左到右)”和“Right-to-Left” 2种算法，如图1、2所示。

图1 从左到右平方乘模幂算法

图2 从右到左平方乘模幂算法

由图1、2可知:2种算法执行时需要同样次数的平方和乘法运算；但算法2总是用固定的m值做乘法。 Berzati等[6]提出了针对算法1的故障分析算法，但是由于算法2中第(2)步的平方与模乘运算是2个独立的过程，从硬件方面来说，它们可被并行实现，减小了算法运算的时钟周期，从而提高了算法的运算速度，因此本文采用算法2来实现模幂运算。

1.2 故障攻击模型

执行一次故障攻击，首先需要对算法和故障影响进行分析研究。除了考虑如何注入故障外，还要考虑如何利用故障的结果获取有用信息，因此需要建立一个注入故障与故障对算法产生影响之间关系的模型。故障按类型分为永久故障和暂时故障[7]：前者指故障一旦注入，则永久对攻击对象产生破坏；而后者只是使攻击对象执行某些计算时暂时出错，如使用电磁辐射、微探测或电压变化等手段。影响故障攻击模型的主要参数有故障注入位置、注入时机、故障大小和故障数目等。依据这些参数，本文建立针对算法2的故障攻击模型，如图 3所示。

图3 故障攻击模型

图3虚线框给出了针对算法2中运算步骤(2)可能发生故障的4个位置。Berzati等[6]在文献[8-9]的基础上扩展了故障模型，在模幂运算执行过程中，对模数N注入故障，修改其值，在错误的模数下执行剩余的操作，而不是在模幂运算执行前注入故障，导致整个执行都是在错误模数情况下完成。攻击模型为：假设攻击者在执行算法2 从0到n-1的过程中，从第j个循环操作开始对模数N注入1个随机字节故障(即控制故障注入的时机t)，故障数目为1，故障类型为暂时故障，故障大小为字节故障(影响模数N中1个字节的值)。

2 针对从右到左平方乘模幂算法的故障攻击

2.1 故障注入

故障攻击不仅可以在硬件上通过激光、微探针、瞬态时钟、瞬态电源、瞬态外部电场、光辐射和涡旋电流等故障注入手段实现，还可以通过利用计算机软件模拟技术进行仿真来实现[3]。目前，注入故障的方式主要有2大类：1)攻击者利用被攻击模块执行密码计算期间发生的计算故障，这类故障既可以是攻击者刻意诱导所为，也可以是密码设备受到异常环境作用等因素的影响所致；2)攻击者通过向被攻击模块注入恶意的非法输入数据等信息而实施的故障诱导。本文重点考虑1)类故障注入方式。针对算法2的执行过程，利用激光或微探针的方式对模数N对应的寄存器实施干扰，使其在执行过程中发生1个字节故障，具体故障注入后的结果变换过程如下。

(1)

(2)

(3)

2.2 密钥分析算法

(4)

图4 RSA算法故障攻击流程

图5 RSA算法密钥恢复过程

RSA算法故障攻击流程：

1) 对于从右到左平方乘模幂算法实现的RSA算法，当密钥d从右边d0开始执行到dj-1时都是正确执行的；

RSA算法密钥恢复步骤：

3 仿真实验结果与复杂度分析

3.1 仿真实验结果与对比分析

表1 不同密钥长度对应的执行时间和操作时间

表2 RSA故障攻击仿真实验结果

从表2可以看出：当增加一次恢复的密钥片断长度时，虽然能够减小注入故障数目，但是在匹配密钥片断时却需要更大的密钥搜索空间。如果一次恢复的密钥片断长度太短，在实际注入故障时，会增大故障注入时机的难度，而且太大的注入故障数目有可能造成攻击对象的永久性破坏，因此有必要对攻击算法的复杂度进行分析。

3.2 复杂度分析

图6 算法复杂度分析曲线

4 结论

本文对从右到左平方乘模幂算法实现的RSA故障分析进行了研究，结果表明：简单的平方乘法迭代给故障攻击提供了可能性，采用对模幂运算执行过程中的模数N注入随机字节故障的手段，建立故障模型，利用密钥空间搜索恢复密钥片断，通过多次执行故障注入,最终恢复完整密钥，对从左到右平方乘模幂算法实现RSA故障分析具有一定的借鉴作用。但同时从实验结果可以看出：在进行软件仿真时，由于是软件实现，执行速度较快，因此执行所消耗的时间都是可以忍受的。而在实际攻击中，具有8位CPU的智能卡微控制器通常都不能在数分钟的时间内执行一次RSA计算，因此如何将此攻击算法运用于实际是将来值得研究和关注的。此外，本文仅对模型中可能出现故障的一种情况展开分析，实际应用中故障的情况多变，因此下一步将对其他故障情况进行研究和分析。

[1] Boneh D, DeMillo R A, Lipton R J. On the Importance of Checking Cryptographic Protocols for Faults[J]. Lecture Notes in Computer Science, 1997,1233:37-51.

[2] Aumuller C, Bier P, Fischer W, et al. Fault Attacks on RSA with CRT:Concrete Results and Practical Countermeasures[C]∥Kaliski B S, Koc C K, Paar C.Proceedings of CHES 2002 4th International Workshop, Redwood Shores. CA, USA:Springer,2002:260-275.

[3] Fouque P A, Guillermin N, Delphine L, et al. Attacking RSA-CRT Signatures with Faults on Montgomery Multiplication[J]. Journal of Cryptographic Engineering, 2013, 3(1): 59-72.

[4] 祝力. 公钥密码及其故障分析研究[D]. 上海:上海交通大学, 2007.

[5] 王红胜,宋凯,张阳,等.针对基于中国剩余定理RSA算法的光故障攻击分析[J]. 微电子学与计算机, 2012, 29(1): 38-41.

[6] Berzati A, Canovas C, Dumas J G, et al. Fault Attacks on RSA Public Keys: Left-to-right Implementations are also Vulnerable[C]∥Fischlin M. Proceedings of the Cryptographers’Track at the RSA Conference 2009. San Francisco,USA:Springer,2009:414-428.

[7] Schmidt J M. Differential Fault Analysis[EB/OL]. (2008-06-16)[2014-09-01].http://www.a-sit.at/pdfs/DFA-Report.pdf

[8] Brier E, Chevallier-Mames B, Ciet M, et al. Why One Should Also Secure RSA Public Key Elements[J]. Lecture Notes in Computer Science, 2006,4249:324-338.

[9] Seifert J P. On Authenticated Computing and RSA-based Authentication[C]∥Proceedings of 12th ACM Conference on Computer and Communications Security.New York: Association for Computing Machinery,2005:122-127.

(责任编辑:尚彩娟)

Fault Analysis on RSA with Right-to-left Square and Multiply Algorithm

CHEN Cai-sen1, DU Jia-xing1, YU Wu2, DENG Liu-yu-qin3

(1. Department of Science Research, Academy of Armored Force Engineering, Beijing 100072, China;2. Department of Training, Academy of Armored Force Engineering, Beijing 100072, China;3. Department of Information Engineering, Academy of Armored Force Engineering, Beijing 100072, China)

This paper proposes an algorithm of fault analysis on RSA with “right-to-left” square and multiply algorithm, using the faulty signature which is the result of injecting fault into modulusNat different appointed location repeatedly during module exponentiation, recovering a key segment which is used during the faulty computation by searching secret key, and finally recovering the whole private key. The complexity of this algorithm is analyzed by a theoretical analysis and software simulations experiment, and the relationship-mapping between the researching key samples space, needed fault number and the length of key segment which is recovered in one time is proposed.

side channel attack; fault analysis; module exponentiation; right-to-left square and multiply algorithm; RSA

1672-1497(2015)01-0081-05

2014- 09- 28

国家自然科学基金资助项目(61402528)

陈财森(1983-)，男，助理研究员，博士。

TN918

A

10.3969/j.issn.1672-1497.2015.01.016