对公钥加密算法RSA的错误注入攻击方法和装置

摘要

本申请提出一种对公钥加密算法RSA的错误注入攻击方法和装置，该方法包括：获取RSA算法对明文的值进行加密运算得到的第一加密结果；对所述明文的值进行错误注入攻击，得到错误明文的值；使用所述RSA算法对所述错误明文的值进行加密，得到第二加密结果；根据所述明文的值、所述错误明文的值、所述第一加密结果、所述第二加密结果之间的运算关系，求解所述明文。该方法攻击范围的精度要求低，实现简单，且攻击过程的时间复杂度较低。

说明书

技术领域

本申请涉及时间同步技术领域，尤其涉及一种对公钥加密算法RSA的错误注入攻击方法和装置。

背景技术

随着信息技术的迅猛发展，信息安全重要性是毋庸置疑的。虽然安全芯片中有复杂的加解密算法和密钥保护机制，然而近年来安全芯片易受到错误注入攻击，从而导致在加密算法执行的过程中产生瞬态的逻辑错误，攻击者通过分析正确的和错误的加密结果，最终引起密钥的泄露。安全芯片的错误注入攻击已被列为美国联邦信息处理标准“FIPS140-3”中重要的一类攻击方式。因此，对新的错误注入攻击方法的研究能够帮助设计者及早发现算法及硬件中存在的潜在风险，使得在设计阶段就能做出相应的防御措施，规避可能的风险。目前的研究中提出的对RSA(RSA algorithm，公钥加密算法)的攻击方法主要包括这几类：对RSA的私钥进行一位或者两位的错误注入攻击，对RSA进行部分密钥攻击以及对CRT-RSA运算中的S_p或者S_q进行错误注入攻击。

对于已有的几种错误注入攻击方法，第一种方法要求错误注入的精度很高，而且耗时很长才能逐位破解出全部密钥位，另外，实际使用中，设计者都对密钥位做了防护，所以直接攻击密钥也很难轻易实现。第二种方法是基于一部分已知的密钥位来破解出其余的密钥位的方法，该方法对已知的密钥位有严格的要求，破解的算法比较复杂。最后一种攻击方法的前提是算法必须基于CRT-RSA才有效，但由于CRT-RSA面积开销比较大，所以用的场合比较少。

发明内容

为解决现有技术中的上述问题，本申请的一个目的在于提出一种对公钥加密算法RSA的错误注入攻击方法，对明文的攻击范围要求宽松，攻击精度要求低，复杂度低。

为达到上述目的，本申请实施例提出的对公钥加密算法RSA的错误注入攻击方法，包括：获取RSA算法对明文的值进行加密运算得到的第一加密结果；对所述明文的值进行错误注入攻击，得到错误明文的值；使用所述RSA算法对所述错误明文的值进行加密，得到第二加密结果；根据所述明文的值、所述错误明文的值、所述第一加密结果、所述第二加密结果之间的运算关系，求解所述明文。

为达到上述目的，本申请实施例提出的对公钥加密算法RSA的错误注入攻击装置，包括：获取模块，用于获取RSA算法对明文的值进行加密运算得到的第一加密结果；攻击模块，用于对所述明文的值进行错误注入攻击，得到错误明文的值；加密模块，用于使用所述RSA算法对所述错误明文的值进行加密，得到第二加密结果；求解模块，用于根据所述明文的值、所述错误明文的值、所述第一加密结果、所述第二加密结果之间的运算关系，求解所述明文。

由以上本申请实施例提供的技术方案可见，通过对RSA算法加密中的明文进行错误注入攻击，获取一个对正确明文的加密结果和一个队错误明文的加密结果，根据已知的RSA算法、公钥和注入的错误字段，即可通过现有的数学手段推导计算得到明文的值，进而破解RSA算法加密的明文，攻击范围的精度要求低，实现简单，且攻击过程的时间复杂度较低。

本申请附加的方面和优点将在下面的描述中部分给出，部分将从下面的描述中变得明显，或通过本申请的实践了解到。

附图说明

为了更清楚地说明本申请实施例或现有技术中的技术方案，下面将对实施例或现有技术描述中所需要使用的附图作简单地介绍，显而易见地，下面描述中的附图仅仅是本申请的一些实施例，对于本领域普通技术人员来讲，在不付出创造性劳动的前提下，还可以根据这些附图获得其他的附图。

图1是本申请一实施例的对公钥加密算法RSA的错误注入攻击方法的流程示意图；

图2是本申请另一实施例的对公钥加密算法RSA的错误注入攻击方法的流程示意图；

图3是本申请一实施例的对公钥加密算法RSA的错误注入攻击装置的结构示意图；

图4是本申请另一实施例的对公钥加密算法RSA的错误注入攻击装置的结构示意图。

具体实施方式

本申请实施例提供一种对公钥加密算法RSA的错误注入攻击方法和装置。需要理解的是，错误注入攻击指在密码芯片设备中通过在密码算法中引入错误，导致密码设备产生错误结果，对错误结果进行分析从而得到密钥。错误注入的攻击方法与攻击对象所采用的密码算法的算法实现方法和原理有关，攻击方法是从该算法实现中找到攻击点并提取出攻击方法，所以针对的密码算法不同，攻击的原理也不同。

为了使本技术领域的人员更好地理解本申请中的技术方案，下面将结合本申请实施例中的附图，对本申请实施例中的技术方案进行清楚、完整地描述，显然，所描述的实施例仅仅是本申请一部分实施例，而不是全部的实施例。基于本申请中的实施例，本领域普通技术人员在没有作出创造性劳动前提下所获得的所有其他实施例，都应当属于本申请保护的范围。

图1是本申请一实施例提出的对公钥加密算法RSA的错误注入攻击方法的流程示意图，如图1所示，该方法包括：

步骤101，获取RSA算法对明文的值进行加密运算得到的第一加密结果。

步骤102，对所述明文的值进行错误注入攻击，得到错误明文的值。

步骤103，使用所述RSA算法对所述错误明文的值进行加密，得到第二加密结果。

步骤104，根据所述明文的值、所述错误明文的值、所述第一加密结果、所述第二加密结果之间的运算关系，求解所述明文。

具体地，上述的明文为需要破解的字符串，在RSA运算的硬件实现过程中会将输入的明文转换为数值m，例如通过Unicode编码或者二进制编码等进行转换，然后对m进行加密运算。本发明的错误注入攻击方法的攻击目标是明文，对明文的攻击范围要求很宽松，不要求高精度的攻击。对明文的错误注入攻击可以是对实现算法的硬件芯片进行粒子级别的攻击，使其运算中的明文码值产生变化。本方法的原理是先对未知的明文进行一次正确的加密得到加密结果c，然后在对明文进行错误注入攻击的情况下，再使用原来的算法进行一次加密得到错误的加密结果c’。由于加密算法是已知的，加密结果也是可以知道的，因此，根据一次错误的加密结果和一次正确的加密结果就能计算得出明文的值，进而分析出明文的内容。

根据本申请的一个实施例，在所述明文的值m中随机注入错误字段，得到所述错误明文的值m’＝m+r，其中，r为错误字段的值。具体地，可利用激光、重粒子等常见的错误注入工具对明文进行错误注入攻击，实际是通过物理手段使特定位置的数字产生翻转或变化，得到错误明文的值，这一过程可以等效为随机生成一个值r，将r与m相加得到新的明文m’＝m+r。

本申请的实施例通过对RSA算法加密中的明文进行错误注入攻击，获取一个对正确明文的加密结果和一个队错误明文的加密结果，根据已知的RSA算法、公钥和注入的错误字段，即可通过现有的数学手段推导计算得到明文的值，进而破解RSA算法加密的明文，攻击范围的精度要求低，实现简单，且攻击过程的时间复杂度较低。

图2是本申请另一实施例提出的对公钥加密算法RSA的错误注入攻击方法的流程示意图，如图2所示，该方法包括：

步骤201，使用RSA算法对明文进行加密运算，得到第一加密结果。

具体的，明文为需要破解的字符串，在RSA运算的硬件实现过程中会将输入的明文转换为数值m，例如通过Unicode编码或者二进制编码等进行转换，然后对m进行加密运算。设RSA算法中(e,N)为公钥对，(d,N)为私钥对，m为明文的值，c为密文，m’为被错误注入攻击后的明文的值，c'为错误的加密结果，输入明文进行加密运算，得到第一加密结果：

c＝m^e(mod>

需要理解的是，在以下步骤中，为了简洁起见，将以e＝3为例进行说明。

步骤202，在明文的值m中随机注入错误字段，得到错误明文的值m’＝m+r。

步骤203，使用所述RSA算法对所述错误明文进行加密，得到第二加密结果。

具体地，在对明文进行错误注入的情况下，RSA算法实际是对错误的明文m’进行了加密，得到错误的加密结果，即

c′＝(m′)³＝m³+3m²r+3mr²+r³(mod>

步骤204，当注入的错误字段未知时，根据所述明文的值、所述错误明文的值、所述第一加密结果、所述第二加密结果之间的加密关系建立结式。

步骤205，根据所述结式与模数N的模等关系式Resultant(m^e-c,(m+r)^e-c')＝0modN，求解所述错误字段的值r。

具体地，根据两次的加密结果c和c’，可以得到下式：

Resultant_m(m³-c,(m+r)³-c')

＝r⁹+(3c-3c')r⁶+(3c²+21cc'+3(c')²)r³+(c-c')³＝0(modN)>

上式(3)为模等式，且该模等式的度为9，则当注入的错误字段r满足|r|≤N^1/9时，利用数学中的格理论就可以解出r的值。当N为1024位的数，e＝3时，根据r和N的关系可知，r至少可以是113位的数，即错误注入攻击的对象可以是明文的低113位中的任意一位或者多位。

下面将推导r与N和e的具体关系：

首先，定义f(x)和g(x)分别如下：

f(x)＝a_ex^e+a_e-1x^e-1+a_e-2x^e-2+...+a₁x+a₀

g(x)＝b_ex^e+b_e-1x^e-1+b_e-2x^e-2+...+b₁x+b₀

则f(x)和g(x)的结式Resultant(f(x),g(x))为：

由结式的性质可知，f(x)＝0modN和g(x)＝0modN在整数域上有公共根的充分必要条件为结式Res(f(x),g(x))＝0modN。将x＝m带入f(x)和g(x)后，可以得到：

f(x)＝x^e-c＝m^e-c

则二者的结式为：

上式可以化为四个e*e大小的矩阵，即：

则：

则Resultant(f(x),g(x))的结果中，最高次项将会出现在下式中：

(r^e-c'+c)*(r^e-c'+c)^e*(r^e-c'+c)^e...*(r^e-c'+c)^e，

显然最高此项为

综上，可以看出Resultant(m^e-c,(m+r)^e-c')的结果是以为最高次项的单变元多项式，只有当错误字段满足时，即才可以利用格理论解出r。

步骤206，根据所述明文的值m、所述错误明文的值m’、所述错误字段的值r与所述第一加密结果c、所述第二加密结果c’之间的加密关系推导得到所述明文的值m关于所述错误字段的值r、所述第一加密结果c和所述第二加密结果c’的计算式。

步骤207，将所述错误字段的值r、所述第一加密结果c和所述第二加密结果c’代入所述计算式，求解所述明文的值m。

具体地，根据式(1)(2)中r、c和c'之间的关系，可通过下式计算出明文的值：

通过上面的破解过程可以看出，注入的错误字段r需要满足才能解出(3)式，在公钥e为3的情况下，r需满足|r|≤N^1/9，即对于1024位的RSA算法而言，只能在m的低113位中的任意一位或者多位注入错误。这个要求对于激光、重粒子这类常用的错误注入工具而言，是很容易实现的。

由上述内容可以看出，如果攻击者事先知道注入的错误r的大小，那么步骤204-205就可以省略，直接通过步骤206-207就可以解出明文m，进而根据m分析出明文的内容。

根据本申请的一个具体实施例，本申请的方法可以由Java语言实现，实验结果与理论分析一致，证明该方法可行。具体的实验步骤及方法如下：

表1

表1所示是RSA算法参数，下面以加密字符串“www.siat.ac.cn”为例说明攻击的过程：

1)字符串经Unicode编码后为m＝7777772e736961742e61632e636e；

2)加密m后得到密文c为：

c＝1a04660fdc343307f51e689e03f3db717d1d05c4f016d3462945b4c5c70476bd3f1a4097ee4df2ac3338；

3)随机生成一个值r，满足r＜|N|^1/9。将r与m相加得到新的明文m’＝7777772e736961742e61632f0f3b。在有选择的错误注入攻击中，随机值r与m的相加可以等效为错误注入攻击引起的m的位翻转。加密新的明文后得到密文c'：

c'＝1a04660fdc343307f51e689e74321bc2bd77cd655ed60668398ba0ea85d4220c2c87edf5094dad3d0743；

4)利用c与c'的结式关系：

Resultant_m(m³-c,(m+r)³-c')

＝r⁹+(3c-3c')r⁶+(3c²+21cc'+3(c')²)r³+(c-c')³＝0(modN)

将c和c'的值分别带入得到上述多项式的各个参数为：

(3c-3c')＝-150bac0f3c11056e14c3d996630d1c46e3c6f01ecc849081750ff2fb27c21，(3c+21cc'+3(c')²)与(c-c')³的值可类似推算，在此不再赘述。

5)将上述参数带入下式中：

r⁹+(3c-3c')r⁶+(3c+21cc'+3(c')²)r³+(c-c')³≡0(modN)

∵r＜|N|^1/9

至此，模等式的问题就可以归化为求解高次多项式问题。

6)在多项式时间内求解得到r＝“ABCD”(Hex)，将值带入式(4)中。

其中，多项式时间(Polynomial time)在计算复杂度理论中，指的是一个问题的计算时间m(n)不大于问题大小n的多项式倍数。

7)带入r后式(4)的结果是一个单变元的模等式。关于这种类型模等式求解方法的研究，目前已经比较成熟，一般是使用其等效多项式的系数构造一个格，利用格基约减的方法，在多项式的时间内得到满足等式的值，求解得到m＝www.siat.ac.cn。

8)至此，整个对公钥加密算法RSA的错误注入攻击过程完毕。

根据上述多项式时间以及复杂度理论可以计算得到，整个攻击过程的时间复杂度为O(n^k)。

本申请的实施例通过对RSA算法加密中的明文进行错误注入攻击，获取一个对正确明文的加密结果和一个队错误明文的加密结果，根据已知的RSA算法、公钥和注入的错误字段，即可通过现有的数学手段推导计算得到明文的值，进而破解RSA算法加密的明文；在注入的错误字段未知的情况下，可在一定条件下求解错误字段的值，进而计算得到明文。本方法对明文进行错误注入攻击，攻击范围的精度要求低，实现简单，且攻击过程的时间复杂度较低。

基于同一发明构思，本申请实施例还提供了一种对公钥加密算法RSA的错误注入攻击装置，可以用于实现上述实施例所描述的方法，如下面的实施例所述。由于对公钥加密算法RSA的错误注入攻击装置解决问题的原理与对公钥加密算法RSA的错误注入攻击方法相似，因此对公钥加密算法RSA的错误注入攻击装置的实施可以参见对公钥加密算法RSA的错误注入攻击方法的实施，重复之处不再赘述。以下所使用的，术语“单元”或者“模块”可以实现预定功能的软件和/或硬件的组合。尽管以下实施例所描述的方法较佳地以软件来实现，但是硬件，或者软件和硬件的组合的实现也是可能并被构想的。

图3是本申请一实施例的对公钥加密算法RSA的错误注入攻击装置的结构示意图。本实施例的装置可以为实现相应功能的逻辑部件构成，也可以为运行有相应功能软件的电子设备。如图3所示，该对公钥加密算法RSA的错误注入攻击装置包括获取模块10、攻击模块20、加密模块30和求解模块40。

获取模块10，用于获取RSA算法对明文的值进行加密运算得到的第一加密结果；

攻击模块20，用于对所述明文的值进行错误注入攻击，得到错误明文的值；

加密模块30，用于使用所述RSA算法对所述错误明文的值进行加密，得到第二加密结果；

求解模块40，用于根据所述明文的值、所述错误明文的值、所述第一加密结果、所述第二加密结果之间的运算关系，求解所述明文。

在本申请的一个实施例中，攻击模块20具体用于在所述明文的值m中随机注入错误字段，得到所述错误明文的值m’＝m+r，其中，r为错误字段的值。具体地，可利用激光、重粒子等常见的错误注入工具对明文进行错误注入攻击，实际是通过物理手段使特定位置的数字产生翻转或变化，得到错误明文的值，这一过程可以等效为随机生成一个值r，将r与m相加得到新的明文m’＝m+r。

本申请的实施例通过对RSA算法加密中的明文进行错误注入攻击，获取一个对正确明文的加密结果和一个队错误明文的加密结果，根据已知的RSA算法、公钥和注入的错误字段，即可通过现有的数学手段推导计算得到明文的值，进而破解RSA算法加密的明文，攻击范围的精度要求低，实现简单，且攻击过程的时间复杂度较低。

图4是本申请另一实施例的对公钥加密算法RSA的错误注入攻击装置的结构示意图。如图4所示，在图3的基础上，所述装置还包括推导单元41、求解单元42、建立模块50和计算模块60，其中，求解模块40包括推导单元41和求解单元42。

具体的，当所述错误字段r未知时，建立模块，用于根据所述明文的值、所述错误明文的值、所述第一加密结果、所述第二加密结果之间的加密关系建立结式Resultant(m^e-c,(m+r)^e-c')；

计算模块，用于根据所述结式与模数N的模等关系式

Resultant(m^e-c,(m+r)^e-c')＝0mod>

当所述错误字段r未知时，所述错误注入攻击满足利用数学中的格理论可以解出r的值。

当所述错误字段已知时，推导单元41用于根据所述明文的值m、所述错误明文的值m’、所述错误字段的值r与所述第一加密结果c、所述第二加密结果c’之间的加密关系推导得到所述明文的值m关于所述错误字段的值r、所述第一加密结果c和所述第二加密结果c’的计算式。当e＝3时，m的计算式为：

求解单元42用于将所述错误字段的值r、所述第一加密结果c和所述第二加密结果c’代入所述计算式，求解所述明文的值m。

本申请的实施例通过对RSA算法加密中的明文进行错误注入攻击，获取一个对正确明文的加密结果和一个队错误明文的加密结果，根据已知的RSA算法、公钥和注入的错误字段，即可通过现有的数学手段推导计算得到明文的值，进而破解RSA算法加密的明文；在注入的错误字段未知的情况下，可在一定条件下求解错误字段的值，进而计算得到明文。本方法对明文进行错误注入攻击，攻击范围的精度要求低，实现简单，且攻击过程的时间复杂度较低。

需要说明的是，在本申请的描述中，术语“第一”、“第二”等仅用于描述目的，而不能理解为指示或暗示相对重要性。此外，在本申请的描述中，除非另有说明，“多个”的含义是两个或两个以上。

流程图中或在此以其他方式描述的任何过程或方法描述可以被理解为，表示包括一个或更多个用于实现特定逻辑功能或过程的步骤的可执行指令的代码的模块、片段或部分，并且本申请的优选实施方式的范围包括另外的实现，其中可以不按所示出或讨论的顺序，包括根据所涉及的功能按基本同时的方式或按相反的顺序，来执行功能，这应被本申请的实施例所属技术领域的技术人员所理解。

应当理解，本申请的各部分可以用硬件、软件、固件或它们的组合来实现。在上述实施方式中，多个步骤或方法可以用存储在存储器中且由合适的指令执行系统执行的软件或固件来实现。例如，如果用硬件来实现，和在另一实施方式中一样，可用本领域公知的下列技术中的任一项或他们的组合来实现：具有用于对数据信号实现逻辑功能的逻辑门电路的离散逻辑电路，具有合适的组合逻辑门电路的专用集成电路，可编程门阵列(PGA)，现场可编程门阵列(FPGA)等。

本技术领域的普通技术人员可以理解实现上述实施例方法携带的全部或部分步骤是可以通过程序来指令相关的硬件完成，所述的程序可以存储于一种计算机可读存储介质中，该程序在执行时，包括方法实施例的步骤之一或其组合。

在本说明书的描述中，参考术语“一个实施例”、“一些实施例”、“示例”、“具体示例”、或“一些示例”等的描述意指结合该实施例或示例描述的具体特征、结构、材料或者特点包含于本申请的至少一个实施例或示例中。在本说明书中，对上述术语的示意性表述不一定指的是相同的实施例或示例。而且，描述的具体特征、结构、材料或者特点可以在任何的一个或多个实施例或示例中以合适的方式结合。

尽管上面已经示出和描述了本申请的实施例，可以理解的是，上述实施例是示例性的，不能理解为对本申请的限制，本领域的普通技术人员在本申请的范围内可以对上述实施例进行变化、修改、替换和变型。