CN103067164A - 使用rsa公开密钥加密算法的电子部件中的防攻击方法 - Google Patents

Abstract

本发明涉及一种使用RSA公开密钥加密算法的电子部件中的防攻击方法。所述方法包括：包括每次执行使用中国剩余定理的RSA解密算法时采用所述方法，所述方法将密文c、密钥d、n、p、q作为输入，所述方法包括：生成三个随机数：u、t、s；用c′＝c+u×n代替密文c；计算p′＝p×t，q′＝q×s；计算cp′=c′modp′和c q′＝c′m o d；计算

和

计算mp=cp′^dp′modp，mq=cq′^dq′modq′；计算m＝mq+q×[(mp-mq)(q^-1modp)(modp)]；用mmodn代替m；其中，p、q是两个位长相同但大小不等的素数，分别为n、p′、q′的欧拉函数。本发明可以有可能使得DPA攻击者不能有效地通过微处理器所处理的中间数据的外加信息得到解密算法的秘密参数，达到防御DPA攻击的效果。

Description

使用RSA公开密钥加密算法的电子部件中的防攻击方法

技术领域

本发明涉及防攻击领域，尤其涉及一种使用RSA公开密钥加密算法的电子部件中的防攻击方法。

背景技术

密码体制分为私钥密码体制和公钥密码体制，分别以1977年美国国家标准局与IBM公司研制的对称加密算法DES和1978年由R.Rivest、A.Shair和L.Adleman提出的公钥加密算法RSA为代表。私钥密码体制既不利于密钥管理也不利于数字签名，但速度高。公钥密码体制可用于密钥管理和数字签名，但速度较低。公钥密码体制的机制是：为每个用户产生一对密钥：一个公开的加密密钥和一个私密的解密密钥，要从公开的加密密钥（简称：公钥）利用计算找到私密的解密密钥（简称：私钥）必须是不可能的。例如：A、B双方通信时，A通过任何途径取得B的公钥，用B的公钥加密信息，加密后的信息通过任何不安全信道发送，B收到密文信息后，用自己的私钥解密恢复出明文。

采用RSA加密算法用在智能卡中，在访问数据库、金融应用、或远距离支付应用等方面有广泛的应用。RSA加密算法的原理可以分成如下三个不同的部分：

第一部分：生成一对RSA密钥；

第二部分：将一个明文加密成密文；以及

第三部分：将密文解密为明文。

其中，第一部分包括如下5个步骤：

步骤一、生成两个长度相同大小不等的大素数p和q；

步骤二、计算n＝p×q,

保密；

步骤三、随机选择整数e，满足

且

步骤四、计算d,满足

步骤五、其中公钥是(e,n),私钥是(d,P,q)。

第二部分按照如下公式计算：c＝m^emodn。

第三部分按照如下公式计算：m=c^d modn。

其中，m表示明文，c表示密文，1<m<n，1<c<n,e是加密指数，d是解密指数。

RSA加密算法的安全性是基于对由两个素数的乘积形成的大数进行因子分解的难度，换句话说，给定两个大素数p和q，要获得他们的乘积n很容易，但是给定n，找出素数p和q非常困难，基于此事实，一个安全的RSA系统必须满足n足够长，例如：512位、1024位、2048位等。

对于RSA加密算法，密钥越长，加密效果越好，但加密、解密的开销也就越大。使用中国剩余定理（Chinese Remainder Theorem，以下简称：CRT）的RSA加密算法可以使解密速度大约提高4倍左右，解密运算由计算模n的指数形式m=c^d modn转化为求同余方程组的情形，可以包括如下步骤：

步骤一、预计算：dp＝dmod(p-1),dp=dmod(q-1),invQ=q^-1modp；

步骤二、计算：cp=cm o d和cq=cmodq；

步骤三、计算：mp=cp^dpmodp,mq=cq^dq modq；

步骤四、计算：

其中，输入为：n,d,p,q,dp,dq,invQ,c；输出为m=c^d modn。

使用CRT的RSA算法在进行解密计算时，首先执行modp和modq运算，其中，两个质数p和q需要具有一样的位长但大小不等，然后执行两次模指数运算，即：cp^dpmodp和cq^dqmodq，再将模指数运算的计算结果利用CRT再结合得到明文m。

在智能卡上实现使用CRT的RSA加密算法易受到如电力消耗、执行时间、故障时的输入和输出行为、辐射等攻击从而泄露密钥信息，其中，差分功率分析（Differential Power Analysis，简称：DPA）攻击是一种很有效的能量攻击方法。DPA攻击利用了这样一个事实：密码设备的瞬时能量消耗依赖于设备所处理的数据以及设备所进行的操作，其原理是智能卡在执行加密解密过程中会消耗能量，产生电磁辐射，通过使用特殊的电子测量仪和数学统计技术，就可以检测和分析这些变化，从而得到芯片中的特定关键信息。具体地，智能卡执行一条指令消耗的能量与指令的操作数相关，其中，当某一特定比特不变而其它比特变化时，则与该指令相关的电流消耗的分析表明，当某一特定比特取值为0或1时，该指令的平均消耗是不同的。因此DPA类型的攻击使得很有可能在执行加密算法期间得到由在卡上的微处理器所处理的中间数据的外加信息，这种外加信息在某些情况下使得有可能泄露解密算法的秘密参数，使得加密系统不安全。

发明内容

本发明提供一种使用RSA公开密钥加密算法的电子部件中的防攻击方法，用以实现有可能使得DPA攻击者不能有效地通过微处理器所处理的中间数据的外加信息得到解密算法的秘密参数，达到防御DPA攻击的效果。

本发明提供一种使用RSA公开密钥加密算法的电子部件中的防攻击方法，包括每次执行使用中国剩余定理的RSA解密算法时采用所述方法，所述方法将密文c、密钥d、n、p、q作为输入，所述方法包括：

生成三个随机数：u、t、s；

用c′＝c+u×n代替密文c；

计算p′=p×t,q′=q×s；

计算cp′=c′modp′和cq′=c′m o d；

计算

和

计算mp=cp′^dp′mod p′,mq=cq′^dq′mod q′；

计算m＝mq+q×[(mp-mq)(q^-1modp)(modp)]；

用mmodn代替m；

其中，p、q是两个位长相同但大小不等的素数，

分别为n、p′、q′的欧拉函数。

在本发明中，对每次使用CRT的解密算法使用随机化计算，通过随机化将使用CRT的模指数运算的p、q、dp、dq以及中间结果mp、mq进行掩盖，有可能使得DPA攻击者不能有效地通过微处理器所处理的中间数据的外加信息得到解密算法的秘密参数，达到防御DPA攻击的效果。

附图说明

图1为本发明使用RSA公开密钥加密算法的电子部件中的防差分功率分析攻击对策方法第一实施例的流程示意图；

图2为本发明使用RSA公开密钥加密算法的电子部件中的防差分功率分析攻击对策方法第二实施例的流程示意图；

图3为本发明使用RSA公开密钥加密算法的电子部件中的防差分功率分析攻击对策方法第三实施例的流程示意图。

具体实施方式

下面结合说明书附图和具体实施方式对本发明作进一步的描述。

如图1所示，为本发明使用RSA公开密钥加密算法的电子部件中的防差分功率分析攻击对策方法第一实施例的流程示意图，每次执行使用CRT的RSA解密算法时采用该方法，该方法将密文c、密钥d、n、p、q作为输入，该方法包括如下8个步骤：

步骤11、生成三个随机数：u、t、s；

具体地，随机数可以从预先存储的数据中选择产生；

步骤12、用c′＝c+u×n代替密文c；

步骤13、计算p′=p×t,q′＝q×s；

其中，p，q是两个位长相同但大小不等的素数；

步骤14、计算cp′=c′modp′和cq′=c′modq′；

步骤15、计算

和

步骤16、计算mp=cp′^dp′modp′,mq=cq′^dq′modq′；

步骤17、计算m＝mq+q×[(mp-mq)(q^-1modp)(modp)]；

步骤18、用mmodn代替m；

其中，p、q是两个位长相同但大小不等的素数，

分别为n、p′、q′的欧拉函数。

按照上述对策方法，使其可以保护使用CRT的模指数运算，如RSA算法的解密运算：

m=c^d modn

在本实施例中，对每次使用CRT的解密算法使用随机化计算，通过随机化将使用CRT的模指数运算的p、q、dp、dq以及中间结果mp、mq进行掩盖，有可能使得DPA攻击者不能有效地通过微处理器所处理的中间数据的外加信息得到解密算法的秘密参数，达到防御DPA攻击的效果。

如图2所示，为本发明使用RSA公开密钥加密算法的电子部件中的防差分功率分析攻击对策方法第二实施例的流程示意图，可以包括如下9个步骤：

步骤21、成四个随机数：u、r、t、s；

步骤22、用c′=c+u×n代替密文c；

步骤23、计算

步骤24、计算p′=p×t,q′＝q×s；

其中，p，q是两个位长相同但大小不等的素数；

步骤25、计算cp′=c′modp′和cq′=c′modq′；

步骤26、计算

和

步骤27、计算mp=cp′^dp′modp′,mq=cq′^dq′modq′；

步骤28、计算m＝mq+q×[(mp-mq)(q^-1modp)(modp)]；

步骤29、用mmodn代替m；

与上一实施例的不同之处在于，本实施例在生成u、t、s三个随机数的同时，还生成随机数r；除了对p、q、dp、dq以及中间结果mp、mq进行随机化处理外，还对密钥d进行了随机化处理。

如图3所示，为本发明使用RSA公开密钥加密算法的电子部件中的防差分功率分析攻击对策方法第三实施例的流程示意图，可以包括如下9个步骤：

步骤31、生成四个随机数：u、r、t、s，其中，t和s为小质数；

步骤32、用c′=c+u×n代替密文c；

步骤33、计算

步骤34、计算p′=p×t,q′＝q×s；

其中p、q是两个位长相同但大小不等的素数；

步骤35、计算cp′=c′modp′和cq′=c′modq′；

步骤36、计算dp′=d′mod(p-1)(t-1)和dp′=d′mod(q-1)(s-1)；

步骤37、计算mp=cp′^dp′modp′,mq=cq′^dq′modq′；

步骤38、计算m＝mq+q×[(mp-mq)(q^-1modp)(modp)]；

步骤39、用mmodn代替m；

与上一实施例的不同之处在于，在本实施例中，t、s为质数，

进一步地，可以从预先存储的质数中随机选择得到t、s。但是，当t、s的位长比较长时，可供选择的质数的数量就会非常多，导致该操作所需要的时间非常长，并且占用的存储空间比较大。为了解决这一问题，可以生成两个以上位长较小的随机质数，t等于这两个以上随机数的乘积，这样的话，由于位长较小的随机质数的数量相对于位长较长的随机质数的数量少得多，因此，可供选择的质数的数量就会少得多，该操作所需要的时间相对较少，并且占用的存储空间也较少；相应地，

等于这两个以上随机数分别减1后的乘积再乘上(p-1)。同理，先生成两个以上随机数，s等于这两个以上随机数的乘积；

等于所述两个以上随机数分别减1后的乘积再乘上(q-1)。

例如：t的长度为64位，可以随机选择4个长度在10位~16位的小质数：t1、t2、t3、t4，使得t＝t1×t2×t3×t4，此时，

同理，s的长度为64位，可以随机选择4个长度在10位~16位的小质数：s1、s2、s3、s4，使得s＝s1×s2×s3×s4，此时，

最后应说明的是：以上实施例仅用以说明本发明的技术方案而非限制，尽管参照较佳实施例对本发明进行了详细说明，本领域的普通技术人员应当理解，可以对本发明的技术方案进行修改或者等同替换，而不脱离本发明技术方案的精神和范围。

Claims (5)

1.一种使用RSA公开密钥加密算法的电子部件中的防攻击方法，包括每次执行使用中国剩余定理的RSA解密算法时采用所述方法，所述方法将密文c、密钥d、n、p、q作为输入，所述方法包括：

生成三个随机数：u、t、s；

用c′＝c+u×n代替密文c；

计算p′＝p×t,q′=q×s；

计算cp′=c′modp′和cq′=c′modq′；

计算

和

计算mp=cp′^dp′mod p′,mq=cq′^dq′mod q′；

计算m＝mq+q×[(mp-mq)(q^-1modp)(modp)]；

用mmodn代替m；

其中，p、q是两个位长相同但大小不等的素数，

分别为n、p′、q′的欧拉函数。

2.根据权利要求1所述的方法，其特征在于，在所述生成三个随机数的同时，还生成随机数r；

所述方法还包括：用

代替密钥d；

所述计算和

具体为：计算和

3.根据权利要求1或2所述的方法，其特征在于，t、s为质数，

4.根据权利要求3所述方法，其特征在于，生成t包括：选择两个以上随机质数，t等于所述两个以上随机质数的乘积；

等于所述两个以上随机质数分别减1后的乘积再乘上(p-1)。

5.根据权利要求3所述方法，其特征在于，生成s包括：生成两个以上随机质数，s等于所述两个以上随机质数的乘积；

等于所述两个以上随机质数分别减1后的乘积再乘上(q-1)。

Images