文章编号:1001-9081(2012)01-0086-03doi:10.3724/SP.J.1087.2012.00086摘要:为提高有限状态机（FSM）控制器的抗故障攻击能力，提出一种非并发故障检测方案。方案利用线性码的故障检错特性，通过在状态机电路中建立故障传播路径来实现。设计了基于NAF编码的从左至右扫描点乘算法的安全有限状态机电路，并对该电路进行了仿真验证与分析。通过仿真验证，与并发故障检测方案相比该设计能够在减少状态机频繁译码工作量的情况下，正确检测错误并报警，提高了抗故障攻击能力。?关键词:故障攻击；椭圆曲线；有限状态机；非并发?中图分类号:TP331;TP309文献标志码:AAbstract:Toenhanceitsresistibilitytofaultattacks,thispaperproposedanon?concurrentfaultdetectionschemeforcontrollercircuitbasedonFiniteStateMachine(FSM).Usinglinearcodes,thisschemewascarriedoutbyconstructingonepathtodetectfaultsintheFSM.Finally,thispaperusedtheschemetodesignthesecurityFSMcircuitforNAF?basedleft?to?rightscalarmultiplicationalgorithm,andsimulatedandanalyzedthecircuitinresistibilitytofaultattacks.Throughthesimulation,andcomparedwiththeschemeofconcurrenterrordetection,inthecaseofreducingfrequentlydecodingworkloadofthestatemachine,thisdesigncandetecttheerrorcorrectlyandalarm,anditalsoimprovestheabilityoffightingagainstfaultattacks.Keywords:faultattack;ellipticcurve;FiniteStateMachine(FSM);non?concurrent?0引言？故障攻击由Boneh等［1］首次提出，后被Biehl等应用扩展至椭圆曲线密码系统。无效曲线攻击［2-3］和符号改变故障攻击［4-5］是故障攻击椭圆曲线密码系统的主要方法，都建立数据路径的故障模型基础上。Gaubatz等针对有限状态机实现的控制器，对椭圆曲线点乘算法进行了故障分析［6］。Zhu等［7］进一步研宄分析椭圆曲线点乘的有限状态机设计的安全性，提出了一种状态机跳变故障攻击方法，能够在多项式时间内获得点乘的整数?k?。？为了提高有限状态机的抗故障能力，Gaubatz利用故障检测码，提出有限状态机的一种并发的冗余状态编码检测方案。尽管并发机制能够实时地检测状态机的工作情况，但是须频繁地进行编码、译码，增加了系统处理数据的负担；Hadjicostis等利用BCH码，提出有限状态机的一种非并发故障检测方案［8-9］，能够校验多个故障，但是，编译码过程复杂，不适用于硬件设计。为了克服以上两种故障检测方案的不足，本文利用线性码提出一种实用的非并发故障检测方案，能够检测状态机跳变故障，易于硬件实现。？1椭圆曲线点乘的有限状态机?二进制扫描算法是其他椭圆曲线点乘快速实现算法的基础，有从左至右扫描算法和从右至左扫描算法两个版本。以Boneh等提出的能够抵抗无效曲线攻击的从左至右扫描算法1为例，该算法基于二进制NAF编码实现，其状态转换图一般如图1所示。？?算法1计算点乘的从左至右NAF(k)方法。？输入NAF(k),PEE/F?q。？输出Ad=kP。？1)Q=0o?2)对于i从1-1至0，执行：？Q=2Q?若k?i=l，则Q=Q+P;?若k?i=_1，则Q=Q,_Po?3)若QEE/F?q，则返回否则返回0。？？2有限状态机的故障检测方法？?一个有限状态机(?FiniteStateMachine,FSM?)(记作状态机S)可用集合(CU,O,S,e)表示，Q表示状态空间，即有限状态机中的状态个数。用一个d维二进制向量表示Q，则状态空间最大为2?d，Q中的每个状态都是时间的函数，用?q??s(t)表示。I表示状态机的输入空间，用一个P维向量表示，时刻t的状态输入用x?s(t)表示。◦表示状态机的输出空间，用一个v维向量表示，时刻t的状态输出用y?s(t)表示。S的状态转移过程可用函数S??x(•)?(•)表示，即？q??s(t+l)=S??x?s(t)?(?q??s(t))，8??x(•)?(•)是当前状态与输入条件的函数。用e(•)表示状态输出函数，e??x(•)?(•＞亦是当前状态与输入条件的函数。？Mealy?型有限状态机输出可表示为y?s(t)=e??x?s⑴?(?q??s(t))，?Moore?型有限状态机输出可表示为y?s(t)=e??x?s(t)?(?q??s(t))，x?s⑴=0。？为实现状态机S的故障检测设计，须把S扩展映射到另一个状态机(记作状态机T)中。...