在电子部件中实现用于寻找公共指数的加密算法的方法

摘要

本发明涉及一种在电子部件中使用计算装置来实现加密算法的方法。本发明的特征在于，它包括实施如下步骤：a)从具体数目的值ei中选择一个值，ei是整数，b)检测ei是否验证了预定的关系；如果验证了，则e＝ei，并且存储e，以供在计算所述加密算法过程中使用。

说明书

技术领域

本发明涉及在电子部件中实现加密算法的方法。

本发明也涉及对应的电子部件。

背景技术

这种部件是在对数据和服务的访问受到严格控制的应用中使用的。它们具有围绕微处理器和存储器构造的体系结构，所述存储器包括含有一个或多个秘密数字d的ROM(Read Only Memory)类型的程序存储器。

这些部件被用在计算机系统中，或者是板载(on board)或者不是；对于芯片卡的某些应用，它们尤其被用在芯片卡中。这些应用例如是访问某些数据库的应用、银行业应用、远程付款应用—例如针对电视费、汽车加油费、高速公路过路费的支付。

因此，这些部件或卡利用加密算法来确保在数据必须保持机密时对所发送数据的加密和/或对所接收数据的解密。

简要地概括来说，这些加密算法的功能具体在于对消息(message)的加密或数字签名。根据由主机系统(服务器、银行自动售货机等)施加的、作为卡的输入的这个消息和卡中含有的许多秘密，卡向主机系统提供加密的或签名的消息作为回复，其例如使主系统能鉴权要交换数据的部件或卡，等等。

加密算法的特点是已知的：所作的计算、所用的参数。唯一未知的是在程序存储器中含有的一个或多个秘密数字。这些加密算法的总体安全性与卡中含有的且为卡外的世界所不知的这个或这些秘密数字有关。仅仅根据对作为输入而施加的消息和作为回复而提供的加密的消息的了解，并不能推导出这种秘密数字。

然而，已经变得明显的是：外部攻击使恶意的第三方能找到在这种卡中含有的一个或多个秘密数字。在芯片卡领域中，存在几种潜在的攻击，其中的一种攻击被称作“故障攻击(fault attack)”。

在这类攻击中，攻击者在加密算法的计算期间注入任意错误(error)，目的是利用这种错误的存在来提取秘密信息。

该错误也可能会因执行加密算法的硬件所导致的计算错误而产生；不过无论认为是哪一种情况，这都是一例故障攻击。

尤其可以设想到使用在该应用领域中的加密中最常用RSA算法(源于其作者Rivest、Shami和Adleman的名字)的情况下有这类攻击。RSA的安全性的基础在于分解大数字的困难性。这些算法具体地使用对幂d的求幂运算，其中d是一个秘密数字。

简要介绍RSA算法的主要步骤。

形成数字N，它是两个素数p和q的乘积(N＝p·q)，一个公共指数或公共密钥e和一个私有指数或私有密钥d满足方程式：

e·d＝1(moduloλ(N))                           (1)

其中λ(·)是Carmichael(卡麦克)函数。

根据所谓的标准RSA算法的第一实施例，公共参数是(N，e)，私有参数是(N，d)。给定位于范围[O，N]内的x，对x进行公共操作，该操作例如可以是对消息x的加密或对签名x的检查，包括如下计算：

y＝x^e modulo N                                 (2)

对应的私有操作，该操作例如是对已加密的消息的解密或者是签名x的生成，包括：

y^d modulo N                                    (3)

其中x＝y^d modulo N，因为e·d＝1(moduloλ(N))。

现在将说明另一个称作CRT模式的操作模式，之所以称作CRT模式，是因为该模式根据的是中国剩余定理(英文“Chinese RemainderTheorem”，缩写CRT)。该模式比标准RSA算法快4倍。根据这个CRT模式的RSA，不是直接进行模N的计算，而是首先执行模p和模q的计算。

公共参数是(N，e)，而私有参数是(p，q，d)或(p，q，d_p，d_q，i_q)，其中

d_p＝d modulo  (p-1)，d_q＝d modulo  (q-1)

且i_q＝q^-1 modulo p。

通过方程(1)，获得

ed_q＝1 modulo  (p-1)和ed_q＝1 modulo  (q-1)         (4)

公共操作按照与标准操作模式相同的模式加以执行；另外，对于私有操作来说，首先计算：

$>>>x>p>>=>>y>>d>p>\; >mod>p>$>和 $>>>x>q>>=>>y>>d>q>\; >mod>q>$>

然后，通过应用中国剩余定理，由下式得到x＝y^d mod N：

x＝CRT(x_p，x_q)＝x_q+q[i_q(x_p-x_q)modulo p            (5)

为了简化本说明书，已经给出了使用两个素数因数p和q的RSA算法。可以将其扩展到N是两个整数p和q的乘积的情形，以便让hcf(p，q)＝1。在这种情形中，

d_p＝d(moduloλ(p))，d_q＝d(moduloλ(q))，

与前面的例子相比，i_q保持不变，

ed_p＝1(moduloλ(p))且ed_q＝1(moduloλ(q))，

且x_p，x_q和x的计算不变。

这种扩展既适用于标准模式又适用于CRT模式。

现在将给出一个故障攻击的例子，该故障攻击的基础是获得同一消息的两个签名，一个是正确的x，另一个不正确，记为^x。

不正确的签名例如曾是以下述方式获得的。攻击者通过任何方法在x_p的计算期间—而不是在x_q的计算期间—注入一个错误。于是值x_p是不正确的，记为^x_p。另一方面，值x_q是正确的。因此，当施用中国剩余定理将值^x_p和x_q重新组合时，作为结果的签名^x是不正确的。

对于当然也知道公共参数(N，e)的攻击者来说，这就足以用N计算最高的公因数(hcf)，也就是说：

hcf(^x-x，N)。

然而，hcf(^x-x，N)＝q。攻击者于是得到秘密因数q，因此得到p和d_p和d_q。因此，RSA码被有效地破坏。

换言之，如果有人能在模q计算期间注入任何错误，无论模q计算正确与否，他都能完全地破坏RSA码。

也可以用已知消息的不正确签名来破坏RSA码。在“On theImportance of Checking cryptographic Protocols for Faults”(D.Boneh，R.A.Demillo和R.J.Lipton著，Advances In Cryptology，EUROCRYPTO’97，pp37-51)一文给出了一些故障攻击的情形，可将该文作为参考。

避免这类情形的第一个对策包括重新计算整个算法。对在连续计算结束时所获得的值进行比较。如果它们是等同的，则假设没有故障被注入。使用这种方法的一个问题是它不检测持久性故障。例如，识别这样的一种攻击，在其中所注入的错误由总是固定在0或1的存储器位(英语称作“sticky bit(粘性位))”的值构成。

Shamir在专利文件WO 98 52319中描述了另一种防范故障攻击的对策。

按照这个对策，进行以下的算法：

1.选择一个低值的随机数r，

2.计算：

x_rp＝y^d modulo r·p，和

x_rq＝y^d modulo r·q；

3.如果x_rp≠x_rq(modulo r)，则有一个(也许由某个攻击引起的)故障，因此中断该算法，否则

4.对x_rp和x_rq应用中国剩余定理，以便将x作为输出而发出。

因此，分别执行模r·p和模r·q计算而不执行模p和模q计算。然后，检查由这些计算所获得的两个值x_rp和x_rq是否也是模r的。如果这两个值不同，则肯定有错误。另一方面，如果它们相等，则可以假设没有错误，在这种假设中错误的概率是1/r。

这个方法的一个缺点是：该方法是概率性的，就是说，错误被检测到的概率小于1，因此不是所有的错误都被检测到。此外，该方法耗费计算时间。Shamir方法的另一个缺点是它只对CRT模式起作用。然而，也可以设想使用RSA算法的标准模式。

对保护不受故障攻击的最可能的保护，包括检查在私有操作(3)或(5)期间(即在RSA算法的CRT模式下或标准模式下)获得的值x满足公共操作的方程(2)：y＝x^e modulo N。这是因为，当该方法被满足时，可以肯定在RSA算法的私有操作的执行期间没有错误。

然而，实现私有操作的部件或设备并非总是有可用的公共指数e，在其只执行私有操作时尤其如此。

发明内容

鉴于以上介绍，本发明提出一种利用事先未知的公共指数e来执行加密算法的一些步骤的方法。

具体而言，这个方法可以实现一种尤其是针对故障攻击的对策，即使在公共指数e是未知的时候也能提供最可能的保护。

本发明的目的是一种在电子部件中利用计算装置实现加密算法的方法，主要特征在于，它包括执行以下步骤：

a)从给定数量的值e_i中选择一个值e，e_i是整数；

b)测试所选择的值e_i是否满足一个预定的方程：

-如果满足，则e＝e_i，并存储e，以供在计算所述加密算法的过程中使用；

-如果不满足，则选择另一个值e_i重复前面的步骤，如果没有任何值e_i能被赋予给e，则记录不能用e值计算所述加密算法。

按照本发明一个实施例，在步骤b)之前，该方法包括：选择一个位于范围[0，N]内的值Y，并向一个值X分配Y^d模N操作的结果，d和N是给定整数，并且该方法还包括步骤b)的预定方程，为：

$>>>X>>e>i>\; >mod>uloN>=>Y>$>

优选地选择Y＝2。

加密算法可以以RSA类型的算法为基础，在标准模式或CRT模式下尤其如此。

按照本发明一个实施例，步骤b)的预定方程为：e_id_p＝1 (moduloλ(p))，p和d_p是给定的整数，λ(·)是Carmichael(卡麦克)函数。

数d_p可由d_p＝d(modulo λ(p))获得，d是一个预定的整数。

按照本发明的一个特征，d_q和q是给定的整数，其中hcf(p，q)＝1，步骤b)包括执行以下步骤：

测试是否e_id_p＝1(modulo λ(p))，

如果是，且e_i＜λ(p)，则e＝e_i，并存储e，以供在计算所述加密算法的过程中使用，

如果是，且e_i≥λ(p)，则测试是否e_id_q＝1 (modulo λ(q))；如果是，则e＝e_i，并存储e，以供在计算所述加密算法的过程中使用，

如果上面两个测试之一不被满足，则用另一个值e_i重复前面的步骤，如果没有任何值e_i能被赋予e，则记录不能用e值计算所述加密算法。

数d_q可通过d_q＝d(modulo λ(q))获得，d是一个预定的整数。

该加密算法最好以CRT模式下的RSA类型的算法为基础。

最好选择e_i＝2¹⁶+1或e_i＝3。

按照本发明的一个特征，在已经向e分配了一个值e_i的情况下，该方法包括在RSA算法的一个私有操作结束时根据一个值y求出一个值x，并且使用一个值e的所述计算包括检查是否y＝x^e modulo N，N是一个预定的整数。

本发明的另一个目的是一种电子安全部件，包含计算装置、程序存储器和工作存储器、以及数据通信装置，特征在于，它实现前面所述的方法。

本发明尤其涉及包含如上所述的电子部件的芯片卡。

附图说明

本发明的其它细节和优点，将清楚地反映在通过非限定的例子并结合以下附图所作的说明中：

图1示意性地表示能够实现本发明的芯片卡的元件。

具体实施方式

各实施例是就芯片卡而言作出说明的，不过当然能适用于任何其它具备加密计算装置的电子安全设备或部件。

如图1中所示，芯片卡1包含与固定存储器(ROM)3和随机存取存储器(RAM)4相耦合的微处理器2，它们总体构成一个允许执行加密算法等功能的配件。更准确地说，微处理器2包含该算法所必要的算术运算装置、以及用于与存储器3和4传输数据的电路。固定存储器3含有执行加密算法的、源代码形式的程序，而随机存取存储器4包含能为存储计算结果而作更新的寄存器。

芯片卡1也包含与微处理器2相连的、允许与外部环境进行数据交换的通信接口5。通信接口5可以是“接触”式的和/或“无接触”式的，在前一种情况下，通信接口5是由一组用来连接诸如读卡器之类的外部设备的接触引脚构成的。在后一种情况下，通信接口5包含允许通过无线连接进行数据传送的天线和无线电通信电路。这种连接也能允许传输给卡1的电路供应的能量。

现在将给出一个用于确认事先未知的公共指数e的值的方法的说明。

该方法以下述观察结果为基础：在90％的情况中，e的值是e₀＝2¹⁶+1，在5％的情况下，e的值是e₁＝3，在其它情况中，e为其它值。

于是本方法包括：选择e₀并验证e＝e₀；如果e≠e₀，则用e₁尝试。

对于某个对应于5％的其它情况的应用，可能出现e既不等于e₀也不等于e₁的情形。因此，更一般地用e_i来表示e。本方法最终包括从设想的值e_i中选择一个值e_i并验证e＝e_i。

根据第一个实施例，对于RSA算法的标准模式或CRT模式有效：

任意选择一个位于范围[0，N]内的值Y，

选择一个值e_i，

在标准模式下按方程(3)计算X＝Y^d modulo N，或在CRT模式下按方程(5)计算

如果 $>>>X>>e>i>\; >mod>N>=>Y>$>则e＝e_i

并且存储e

否则为e_i选择另一个值。

选择Y＝2可能有利于加快方程(3)或(5)中出现的求幂计算Y^d的速度：这就相当于进行加法而不是乘法。

现在说明另一个基于方程(4)的实施例；它仅在CRT模式下有效，但此时比前一个实施例更有效；

选择一个值e_i，

测试是否e_id_p＝1 modulo (p-1)，(或者在一般情形下是否e_id_p＝1 (modulo λ(p)))

如果是，且如果e_i＜p，(或者在一般情形如果e_i＜λ(p))，则e＝e_i并存储e，

如果是，且如果e_i≥p，(或者在一般情形下如果e_i≥λ(p))，则e＝e_i具有1-2/p左右的非常高的概率。

在e_i≥p(或者在一般情形下e_i≥λ(p))的情况下，通过测试是否e_id_q＝1 modulo (q-1)，(或者在一般情形下是否e_id_q＝1 (moduloλ(q)))来消除二义性，使得概率为1。如果是这样，则e＝e_i并存储e。

然而，在多数情况下(e_i＝2¹⁶+1或e_i＝3)，e_i＜p(或者在一般情形下e_i＜λ(p))，因为p有512位或更多位的大小。

如果有一个测试得不到满足，则为e_i选择另一个值。

如果对于一个或另一个实施例来说，在各e_i值中不存在使得e＝e_i的e_i，则就不可能用e来进行计算。

如果e是已知的，通过这些实施例的一个或另一个，就有可能通过检查y＝x^e modulo N来验证每个私有操作(3)或(5)，或更一般地用已经存储的e值进行计算。

如上所述，该方法当然可被应用于一种对策。

它比所述的现有技术中包括重新计算整个算法的对策更快速—重新计算即至少进行第二次对幂d的求幂计算(d具有大小N)，并对在连续计算结束时所获得的各个值进行比较。按照本发明的方法还包括进行第二次求幂计算，但是是对e；然而，e值较小。

该方法也使得能够检测到一个永久性的故障。

该方法既适用于RSA算法的标准模式又适用于CRT模式，并且适用于这些方式的扩展。