用于RSA算法的素数生成的保护

摘要

本发明涉及一种用于RSA算法的素数生成的保护。一种由电子电路通过对连续候选数字的素数特征进行测试，以对至少一个素数的生成进行保护的方法，包括：对于每个候选数字：进行包括至少一个第一随机数的参考数字计算；基于模幂计算的至少一个素性测试；和对于已经成功通过所述素性测试的候选数字：进行所述候选数字和它的参考数字之间的一致性测试。

说明书

技术领域

本发明一般涉及电子电路，尤其涉及一种执行RSA类型非对称加密算法的电路。本发明尤其涉及电子电路中素数生成期间的保护，以防御旁路攻击，例如，通过对电路功耗进行统计分析(SPA-简单功耗分析)，或对电路的电磁签章进行统计分析，或防御故障植入攻击。

本发明应用于采用了使用素数因子分解的算法的任何电子电路，尤其是芯片卡。

背景技术

RSA算法是最常用的非对称加密算法(具有公钥)中的一种。该算法用于加密/解密数据或对数据签名以使它们能被认证。它基于一对密钥的使用，其中包括公钥和私钥。在加密/解密模式中，公钥由发送器使用以加密将被秘密发送到接收器的数据，后者使用它的私钥(或密钥)解密所述数据。为进行认证，所述私钥被所述发送器使用以签名所述数据，而所述公钥被所述接收器使用以认证所述签名。

所述公钥相对广泛的可被访问以使得所述加密数据的发送器或所述签名数据的接收器能使用这些数据。然而，所述私钥被保留在已经生成所述一对密钥的电路。所述一对密钥的持有者可能直接将所述公钥发送到对方以使得它能够处理所述数据。

所述一对公钥和私钥的生成需要两个相对不同的素数“p”和“q”，具有相对大的大小(一般地，1,024或2,048比特)。这些素数的乘积表示加密模数“n”。数字p和q被选择，所以数字p-1和q-1关于数字“e”互质，被称为公共指数，后者与乘积的欧拉指示器(n)互质。结果，存在一整数“d”满足乘积e*d与1相对于模(n)来说是同余的。对n和e表示公钥，而对n和d表示私钥。私秘指数d表示指数e的逆以(p-1)(q-1)为模。素数p和q仅仅存在于包含所述私钥的电路中。

RSA算法的鲁棒性依赖于素数p和q。为“破坏”基于公钥的RSA算法，必须能够对数字n进行分解，从而获得素数p和q。一旦这个分解被获知，私秘指数d能够被从公共指数e中计算出来(d是根据计算e的逆以(p-1)(q-1)为模而得到)。显然可以想到，通过使用足够大小的模数n(尤其是1500比特)，在合理的时间内，当前算法不能分解数字n。

然而，将数字p和q引进到电子电路或由该电路进行它们的生成对于安全性是至关重要的，因为黑客在该电路的活动时刻发现这些数则使得他能够分解数字n。

用于生成RSA密钥的第一种技术包括在所述电子电路的外部生成这些密钥。数字p和q被在用户化阶段被引进到电子电路中。这种技术不能响应于故障引入攻击，因为其所述密钥不是由真正的电子电路生成。

第二种已知技术包括使所述真正电子电路在安全环境(实际是在受保护的安装中，具有预定的访问)中生成所述素数。根据这种技术，在所述素数生成期间，攻击也不成为问题。

然而，更通常的情况是，电子电路被希望能够在这样的安全环境之外生成它们的RSA密钥。例如，在一先前密钥已经被抛弃(密钥可能被窃取)的情况下，这能够重新生成新的密钥。这种生成例如能被执行在处于非安全环境中的电子电路的用户化期间，或在第一次使用期间(例如，针对被用于签名计算或电子标识的电路)。根据电子证书的一个应用实例，一旦它在它的持有者手中时，密钥被希望能由所述证书中包含的电子芯片生成。因此，这个密钥不能在证书认证过程中已先被使用。

公共指数e可能是公钥基础结构(PKI)的参数，并且对于所有的密钥都是相同的。例如，在(ROM中的)电子电路的制造期间或是在(EEPROM中的)用户化阶段期间可以被引入进所述电子电路中。

公共指数e可能还被由电子电路生成，例如通过选择随机数，并且可能被发送到它必须与之进行通信的元件那里。

公钥(公共指数和加密模数)因而被所述接收器(签名)获知，或被所述发送器(加密)获知，或被持有所述私钥的电子电路另外发送(对于每个事务一次全部完成)。所述公钥必须进一步被验证。

大素数的生成在时间和计算方面消耗很大。特别的，所谓的素性测试，能够证实数字的素数的特征有效或无效，其一般执行需要大量计算的模幂运算(例如，所说的Miller-Rabin素性测试)。这就是为什么它被希望仅仅为已经成功通过关于相对较小的素数的测试的候选数字进行这样的测试的原因。这样的测试相应于由相对较小的素数进行除法，或与素数表进行对比。例如，米勒-拉宾(Miller-Rabin)测试可能被通过一小基数执行(例如2)，或一最大公约数计算可能被执行(例如，增加字节模数255以获得比255小的结果，然后用255计算该结果的最大公约数-如果不是1，一单独的测试能告知所述数字对于255的3个因子是不可除的，即3。5和17)。

当所述素数由电子电路在非安全环境中生成时，所述电路可能遭受故障引入攻击(功耗供给干扰，激光攻击等)，所述攻击采用输入-输出或电路消耗分析的方式，或者遭受旁路攻击(SPA或DPA或电磁分析)。

由所述电子电路进行素数生成的另一危险是以修改最终被选择的数字为目的的攻击。在Miller-Rabin测试结束后的攻击可能被用来修改由算法考虑的数字。如果p或q中的一个不是素数，加密模数n更容易被分解，这就降低了RSA算法的安全性。

发明内容

因此，需要对素数的生成进行保护，以及当所述数是由采用了密钥的电子电路产生时，对利用素数分解的算法的这些密钥的生成进行保护。

进一步的，需要能够对由所述生成过程提供的素数的修改进行检测。

进一步的，需要能够对所述素数生成进行标记。

为达到所有这些或部分目的及其它目的，本发明提供一种由电子电路通过对连续候选数字的素数特征进行测试，以对至少一个素数的生成进行保护的方法，包括：

对于每个候选数字：

进行包括至少一个第一随机数的参考数字计算；

基于模幂计算的至少一个素性测试；和

对于已经成功通过所述素性测试的候选数字：

进行所述候选数字和它的参考数字之间的一致性测试。

根据本发明的一个实施例，所述参考数字通过从候选数字减去或在候选数字上增加依赖于所述第一随机数的一个量而得到。

根据本发明的一个实施例，在基于模幂计算的所述素性测试之前，每个候选数字被提交到基于过滤表的至少一个素性测试，所述过滤表中包括和第一阈值与第二阈值之间的素数一样多的元素，初始候选数字通过在小于所述第一阈值的所述素数的第一乘积上乘以一任意数字而得到。

根据本发明的一个实施例，从一个候选数字到下一个候这数字包括：增加所述第一乘积到当前候选数字和参考数字。

根据本发明的一个实施例，从一个候选数字到下一个候选数字包括：增加所述第一乘积的倍数到当前候选数字和参考数字，乘法器是至少一随机数和在所述第一阈值和第二阈值范围之间的素数的第二乘积的函数。

根据本发明的一个实施例，所述乘法器进一步是RSA算法的公共指数的函数。

根据本发明的一个实施例，所述过滤表基于所述参考数字。

根据本发明的一个实施例，所述过滤表通过为它的每个元素增加以相关元素为模的所述第一乘积而被更新，例如，新的候选数字。

根据本发明的一个实施例，在基于模幂计算的所述素性测试之前，每个候选数字被提交到与RSA算法的公共指数的一致性的测试。

根据本发明的一个实施例，基于模幂计算的所述素性测试是Miller-Rabin测试。

本发明还提供了一种包括用于执行所描述的方法的装置的电子电路。

本发明已述的目的，特点和优势将在下面特定实施例连同附图的非限制性描述中进行详细讨论。

附图说明

图1是作为一个例子应用在本发明类型的集成电路的实施例的框图；

图2A非常示意性的示出了由RSA算法的装置进行的加密；

图2B示意性的示出了由RSA算法的装置进行的解密；

图3是示出加密数据传输系统的框图；

图4是示出在电子电路执行RSA类型算法中素数生成的一般步骤的框图；

图5是素数生成方法的一个实施例的步骤的框图；

图6特别的以框图的方式示出的素数生成方法的另一实施例。

具体实施方式

为清楚起见，相同的元件已经在不同的附图中被指定了相同的参考数字。进一步的，只有那些对于理解本发明有用的步骤和元件被表示出和进行描述。特别的，利用密钥的算法的电子电路基于素数采用了何种方式没有被描述，本发明与任何通常对于生成的素数的采用方式(加密，签名计算)是一致的。

本发明将随后关于在加密/解密中使用的RSA算法的一个应用实例进行描述。然而，本发明适用于基于被生成素数由所述RSA算法产生的任何使用，本发明特别适用于RSA签名。更一般的，本发明适用于使密钥依赖于素数分解的任何算法，例如，所称的Rabin加密系统。

图1非常示意性的以框图的方式示出了本发明使用的类型的电子电路1(例如智能卡)的一个实例。这样的电路包括处理单元11(PU)，可能通过一个或多个数据总线、地址总线和控制总线12与不同的元件通信，这些元件中包括一个或多个非易失性存储器13(NVM)，一般是包括全部或部分程序的ROM和意图包含所述RSA密钥的EEPROM，一个或多个易失性存储器14(典型的是RAM类型)，和使得电路1与外部通信的接口电路15(I/O)。在本申请中，本发明特别针对的是，电路1还包括可能与中央处理单元11一致的加密或签名计算处理器16(CP)。电路1可能执行由硬件和/或软件元件实施的不同功能，所述硬件和/或软件元件被符号化为点状线表示的框17(FCT)。其中的一个功能，由框18(PN GEN)表示，是将被应用为RSA类型算法的密钥的素数的生成。其它的元件和电路可能根据电子电路1的目的装配电子电路1。进一步的，可能提供电路的子装配部分之间的直接链接(未示出)，以交换数据、地址和/或控制信号。

图2A和2B示出了RSA类型算法的实施。所述RSA计算单元在图2A中被表示为框20(加密端)，在图2B中被表示为框21(解密端)。这些计算单元实际中可能是相同的，是软件或硬件单元。

表现为整数的数据消息M的加密被引入到所述RSA计算块中，进一步包括或接收加密模数n和公共密钥的加密指数e。整数M小于加密模数n。所述RSA块计算表示模幂M^e mod n的加密消息C。

关于由持有私钥(n，d)的电路进行的解密，消息C被提交给基于指数d和模数n的模幂，这是说，单元21提供消息M表示C^d mod n。

图3是示出表示从发送器22到接收器23的任意数字内容的数据DATA(块24)的传输的例子的框图。所述接收器具有RSA密钥并开始分解模数n和公共指数e，如果发送器不知道的话，发送所述公共密钥到那里。这使得发送器能够加密所述数据并以加密消息C的形式发送它们。接收器23使用它的私钥(n，d)解密所述消息并获得数据DATA(块25)。

该传输可能遭受到意图发现数字n的分解的拦截尝试。一旦所述密钥已经生成，本发明便不针对于这样的攻击，但是攻击可能发生在素数生成期间的情况，其仅仅发生一次(或者在新的一对密钥的每个生成时期)。

所述素数的生成包括修改候选数字直到它成为素数。如前面所示，简化的测试被执行以验证所述候选是否是具有相对小的数字的素数，所述验证是在将所述候选提交给适合于大数的素性测试之前进行。适合于大数的测试一般是基于Ferma t定理，根据它可知，如果“u”是素数，则对于任何整数“v”与1相对于模u来说是同余的，即除了1或u之外，没有整数对数字u进行可能的分解。现在最常使用的用于素数生成的素性测试是所说的Miller-Rabin测试。这个测试执行模幂计算以验证所述候选数字对于除1之外的其它数字是不可除的，并被描述在例如文章“Handbook of Applied Cryptography”中，由A.Menezes，P.vanOorshchot和S.Vanstone编写，1996年发行(CRC Press)，第4章，4.2.3节，138-140页。实际上，素性测试不是完美的，但是错误可能性足够低以便能够将所述候选数字考虑为素数。

图4示出了用于生成素数(随意命名为p)的一般方法的步骤的框图，用于表示所述RSA分解模数的两个素数中的一个。图4的方法一般在一行上执行两次以便获得数字p和q。

一随意数字k首先被选择(块31，RANDOM)，例如，通过随机选择。随后，该数字被修改以便获取不被小于第一阈值n₁的素数可除的候选数字。

根据一个例子，数字k乘以乘积A₁(块32，X)，乘积A₁是小于阈值n₁的素数b_i的乘积(i在1和m₁之间，且m₁表示组[1，n₁]的素数的数目)。阈值n₁被选择的相对较小。例如，n₁＝3，A₁＝6(m₁＝3，且b₁＝1，b₂＝2，b₃＝3)。如果n₁＝5，则A₁＝30(m₁＝4，且b₁＝1，b₂＝2，b₃＝3，b₄＝5)。一个(1)被增加到或从计算的乘积中减去(块32’，±1)，由此，在n₁＝3的例子中，它既不被2可除，也不被3可除。获得第一候选数字a＝k.A₁±1，其与数字2和3互质。

数字p和q需要的大小被设置。相应的，候选数字a的大小必须相应于数字q和q所需要的大小。数字k的大小由此取决于数字A₁的大小。在上面的例子中，对于1024比特的数字a和30比特的数字A₁，数字k被选择为超过1019比特。

根据另一个例子，数字k通过执行操作k＝k-(k mod A₁)而被修改以便使得它被A₁可除。随后，一数字被增加，其随意选择自与A₁互质的数字的表。与小于n₁的素数互质的候选数字a随即被获得。在这个例子中，数字k具有与数字a所需的一样的大小。

下一个步骤(块33)包括构造过滤表ST(SIEVE TABLE)，使它的每个项目表示除运算的结果，所述除运算是候选数字a被包括在第一阈值n₁和第二较高阈值n₂之间的素数中的一个所除。这意味着用值a mod b_i填充所述表，b_i在n₁到n₂的范围内(由此i是在m₁到m₂的范围内)。这样的填充使用包含所述候选数字的除运算，所述除运算对于旁路攻击是敏感的。选择阈值n₂避免所述表太大，以使得对于每个候选数字将在随后进行的所述运算相比于在所述候选数字上进行的Miller-Rabin测试可以保持较少的消耗(在所述计算所需要的时间和功耗方面)。例如，阈值n₂等于128或256。为简化起见，阈值n₁被考虑作为组[1，n₁]和[n₁，n₂]的一部分，然而实际上，阈值n₁仅仅是这些组中一个组的一部分，以便节省重复测试，因为阈值n₁一般是素数。

一旦所述过滤表已经被初始化，只要候选数字a与能被所述RSA算法的执行来说是可接受的素数不对应，则实施下一个操作。

开始于验证所述候选数字对于包含在区间[n₁，n₂]中的所有数字都互质。这意味着验证(块35，0∈[ST]？)所述表包括非零值。零值的存在说明候选数字a是在所述表中的相对应素数的倍数。

如果测试35确认(块35的输出N)所述候选数字对于包含在区间[n₁，n₂]中的所有数字都互质，则证明(块37)所述候选数字对于RSA算法的执行是适合的。为此目的，必须证明数字a-1与e互质。实际中，检验值a mod e(a被e除时的余数)是否等于1。如果不相等，候选数字a适合于所述RSA，也就是说，将涉及指数e是与欧拉指示器(p-1)(q-1)互质的整数的情况。

一旦测试37已经通过(输出N)，所述候选数字最终被提交到Miller-Rabin素性测试(块38，MR测试好了吗？)的多个个执行处理(一般是几个执行处理到几十个执行处理)。如果成功通过所述测试(块38的输出Y)，候选数字a 被作为素数p提供(块39，输出p＝a)。

一旦测试35、37或38中的一个表示所述候选数字不适合(块35和37的输出Y，或块38的输出N)，新的候选数字被选择。为此目的，开始于(块36，a＝a+A₁)将值A₁与被拒绝的候选数字相加上。随后，过滤表[ST]被更新。这意味着增加A₁以b_i为模的量(块34，[ST]+A₁ mod b_i)到所述表的元素中的每一个(被i识别)，并且所述方法返回到步骤35。尽管没有被示出，将被用于测试37的包括值a mod e的变量也被更新。

一旦第一素数p已经被获得，所述方法被再次执行以选择对于实施RSA算法来说必要的第二素数q。额外的步骤包括确保数字p和q是互质的(步骤未在图4中示出)。由于它们是素数，足够检验它们是不同的。

所述素数生成步骤的连续对于旁路攻击或故障植入攻击来说尤其是敏感的。这类攻击可能意图发现被生成的素数或强迫非素数数字的生成。两种情况中，这可能使得黑客能够发现私钥。

图5是示出了所述素数生成方法的一个实施例的框图，其能防御可能的旁路攻击(功耗分析或电磁响应分析)或故障植入攻击。这个框图应当与图4的框图进行比较。

如前面所述，开始于选择阈值n₁，该阈值决定使用在素性测试中的乘积A₁。例如，阈值n₁是3(m₁＝3)或5(m₁＝4)，且乘积A₁是6或30。n₁的其它值可能被选择。

随后(块31，a)，任意数字k被选择并修改以便不能被小于数字n₁的素数可除。如前所述，数字k的大小依赖于数字A₁的大小。例如，(块32，a＝k.A₁+1)，数字k乘以乘积A₁并加1(作为变化的，从这个结果中减去1)。可以使用生成第一候选数字a的其它方式。

下一步骤(块41，w＝a-e.r₂.A₂)包括生成参考数字w，其将被使用在所述生成过程的最后以确保候选数字a没有被干扰，并且能保护由小素数进行的分解免于旁路攻击。

例如通过从候选数字a中减去值e.r₂.A₂获得量w，其中e表示公共指数(例如，超过32或64比特)，r₂表示一随机数字，并且A₂表示在区间[n₁，n₂]中的素数的乘积。如前所述，阈值n₂表示随后用于创建过滤表的阈值。例如，阈值n₂被选择为等于128或256。n₂的其它值可能被选择。

随机数字r₂的大小减去公共指数e的大小和乘积A₂的大小等于候选数字a的大小。因此，减后的项具有和数字a一样的大小。

由此这个实施例应用于公共指数e的大小相对小(小于几百比特)的情况。然而当前发明还应用于大的数字e(例如，与将被生成的素数具有相同的大小)的情况。在这种情况下(未示出)，数字e在素性测试中不被考虑，所述素性测试先于Miller-Rabin测试，并且它的关于被选择的候选数字的素性在这个测试终止后由一特定测试进行验证(通过分解)。

之后，将假设数字e足够小以被考虑在数字p的q的生成中，这可避免在数字e上进行完全的素性测试。

生成数字w的下一步骤(块43)包括基于参考数字w生成过滤表[ST]。关于图6将被看到所述过滤表还可能基于候选数字a生成。

在图5的实施例中，表[ST]包括和在区间[n₁，n₂]中的素数b_i一样多的元素。每个元素对应于参考数字w除以相应的素数b_i，并等于a mod b_i。对于量w将被通过从数字a中减去量e和A₂的乘积这一事实，使得所述过滤表的值能表示w modb_i和a mod b_i的结果。

随后，只要一个可接受的候选数字没有被发现，后面的步骤就被反复执行。

开始于(块35)通过确保数字a和w与区间[n₁，n₂]中的所有素数b_i都互质。为此目的，需要验证表[ST]中的元素中的一个是零。如果不是这样，进行到下一个测试(块37，a mod e＝1？)以用公共指数e验证所述候选数字的兼容性。

如果候选数字已经通过前面的所有测试(块37的输出N)，其被提交到所述Miller-Rabin测试(块38)。

只要测试35、37或38中的一个表明所述候选数字是不符合条件的(块35、37的输出Y，或块38的N)，新的候选数字和新的参考数字通过在先前的值上增加A₁而被计算(块46，a＝a+A₁，w＝w+A₁)。随后(块34，[ST]+A₁ mod b_i)，过滤表[ST]通过在它所有的元素上增加值A₁后再以b_i为模的方式而被更新。实际中，包含值a mod e的变量(随后被用于测试37)也被更新到a mod e+A₁。

新的候选数字随后被提交到测试35和37、38(测试35和37的顺序不重要)。

如果所述候选数字是符合条件的(块38的输出Y)，另一步骤(块44，a＝w+e.r₂.A₂？)能够验证所述候选数字关于计算的开始的完整性，也就是说，它与参考数字w的一致性。例如，值e.r₂.A₂被增加到参考数字w，且它被验证其结果等于候选数字a。如果是这样(块44的输出Y)，候选数字a被作为素数p提供(块39，输出p＝a)。否则(块44的输出N)，这意味着在素数生成期间有干扰发生。所述电路随后进行错误处理(错误)。作为一种变化，块44的所述测试验证用量A₂分解值a-w。这种变化能够避免存储随机量r₂。根据另一个变化，步骤41被一加法运算代替，步骤44被一减法运算代替。

所述错误处理例如可以是所述被生成素数的取消(该处理从步骤31重新开始)或所述电路的中止使用。这些在已检测到有非法访问尝试的情况下将被进行的动作本身是常规的，并根据应用存在多种解决方案。

一致性或完整性测试44能够避免在Miller-Rabin测试之后的攻击，所述攻击强加了不同于数字a的数字。

一旦第一素数p已经被生成，所述处理重新开始以生成第二素数q，并验证数字p和q互质。最后，为执行所述RSA算法，分解模数n被计算(n＝p.q)并被提交(和指数e一起)以便为有可能需要其的任何实体形成公共密钥。数字p和q仅仅被存储在电子电路1中。

基于参考数字w(而非数字a)构造所述过滤表的行为能够标记这个构造。

图6是示出另一实施例的框图。只有相对于图5被修改的步骤被表示出。

与前面的实施例相比，所述过滤表是基于候选数字a。随后它被用项a mod b_i(区间[n₁，n₂]中)来初始化(块43’，过滤表，a mod b_i[n₁，n₂])。为通过量A₁的加法运算来保护所述过滤表的更新，构造将被从候选数字加到下一个候选数字和被从一个参考数字加到下一个参考数字(块46’)的一个量f，以使量f等于A₁ mod b_i和A₁ mod e。例如，独立于数字r₂的随机数字r₁被选择，并被乘上乘积e.A₂。数字r₁的大小满足乘积r₁.e.A₂小于将被生成的素数所需的长度(小几字节到几十字节)。这使得对于从一个候选数字到另一个候选数字的通过能够伴随有所述比特的大数字的修改。随后，1被增加到所述乘积。因此，如图6所示，新的候选数字和新的参考数字通过在先前的值上增加(块46)值f.A₁而得到，其中f＝e.r₁.A₂+1。所述新的候选数字和参考数字仍然与小于阈值n₁的素数互质。由于A₂等于0 mod b_i，乘积e.r₁.A₂+1等于1 mod b_i。通过A₁与表[ST]的元素中的每一个相加，再以相关元素的素数b_i为模的方式，所述表像在先前实施例中那样进行被更新(块34)。

在此之前描述了具有不同变化的各种实施例。应当注意本领域技术人员可能组合这些不同实施例和变化中的各种元素，而不花费创造性的劳动。进一步的，基于在此之前给出的功能性表示的本发明的实际实施方式，在本领域技术人员的能力范围内，其可以是硬件或软件实施。

特别的，用于在所述Miller-Rabin测试之前的测试的阈值n₁，n₂的选择，依赖于应用，及在所述素数生成期间被用于所述Miller-Rabin的时间。例如，尽管对于所述过滤表优选为不基于小于所述第一阈值的所述素数来免除计算，这仍是不可或缺的。

进一步的，根据素数p和q所需要的大小，所述随机量的大小的选择是合适的，对于所述RSA算法的模幂的模数n也是这样。

尤其的，尽管当前发明被描述为执行单独的过滤表的方法，可以想象的是使用多个过滤表，通过在下一个表之前插入每个表的素性测试(步骤34和35)，每个表具有验证所述候选数字相对于由连续阈值定义的临近范围内素数的素性。为优化的目的，如果基于先前表的素性测试是有效的，这种变化可能仅仅用于更新当前表。

当然，当前发明对于本领域技术人员可能进行各种变形、修改和改进。这些变形、修改和改进被认为是本公开的一部分，并被认为是包含在当前发明的精神和范围内。相应的，前述的描述仅仅是示例的方式，并且不被认为是进行限制。当前发明仅由定义在后面的权利要求和等同替换进行限定。