英语原文共 7 页，剩余内容已隐藏，支付完成后下载完整资料
快速素数生成算法的实现
Christophe Clavier和Jean-S#39;ebastien Coron
1金雅拓，安全实验室，
La Vigie，Avenue du Jujubier，ZI Ath#39;elia IV，
F-13705 La Ciotat Cedex，法国
christophe.clavier@gemalto.com
2卢森堡大学,
科学技术与传播学院，
理查德·库登霍夫 - 卡莱吉大街6号，
L-1359卢森堡
jean-sebastien.coron@uni.lu
摘要：密码算法的侧通道分析通常集中在加密或解密阶段，很少在密钥生成阶段。在本文中，我们表明，如果执行不当，由Joye和Paillier在CHES 2006上提出的快速素数生成算法易受侧向信道分析的影响;其主要应用是为智能卡等嵌入式平台生成RSA密钥对。我们的攻击假定当分支条件出现时，一些奇偶校验位可以通过SPA恢复。我们的攻击可以结合Coppersmith的定理来提高效率;我们显示对于1024位RSA模量，可以恢复大约 RSA模数的分解。
关键词：简单幂分析，Prime生成算法，Coppersmith定理
1 介绍
诸如简单功率分析（SPA）和差分功率分析（DPA）等侧通道分析一般集中在加密或解密阶段，很少在密钥生成阶段。即加密或解密为攻击者提供更多灵活性，攻击者可以提供各种消息作为输入，并且每次都记录侧通道泄漏。相比之下，密钥生成算法不会接受任何输入（超出安全参数），并且通常不会执行多次，因为每次执行都会获得不同的密钥。
在本文中，我们表明，如果执行不当，Joye和Paillier在CHES 2006 提出的快速素数生成算法之一容易受到侧通道分析的影响。Joye-Paillier算法的主要应用是在智能卡等嵌入式平台上生成RSA密钥，其效率至关重要。素数生成通常通过对随机生成的整数应用素数检验来起作用，直到找到素数。在[6]中描述的技术在于生成不能被第一个素数整除的随机整数; 那么素数出现的概率就越高，平均而言，就不会有素数测试被应用，从而提高了效率。
在中描述了一种更快的变体，其中从随机种子生成候选序列，并且在应用素数检验之前检验每个候选的奇偶性，直到找到素数。在本文中，我们专注于实现这个更快的变体; 我们证明如果已经应用了个素性测试，并且如果奇偶校验位可以通过SPA获得，那么我们可以恢复输出素数的个最低有效位。 Coppersmith定理表明RSA模数可以在多项式时间中给出，给定半数的最不显着（或最显着）位。因此，如果或的素性检验的数量大于的一半比特大小，那么可以有效地恢复因子分解。我们提供的分析显示，对于某些参数（）和1024位RSA模量，这发生在个生成的RSA模量中。
2 Joye-Paillier素数生成算法
Joye-Paillier算法包括生成一系列与第一个小素数共素数的候选项; 然后对每个候选人应用一个素性测试，直到找到一个素数。在这里，我们专注于更快的变体（来自[中的图3）。一个定义为第一个素数的乘积，不包括，所以是奇数：
令为必须生成素数的间隔。一个定义整数，和，使得：
, 且
素数整数实际上将在子区间中生成：
关于参数，和的选择，请参见。我们用表示一个素性检验（例如Miller-Rabin）。
快速素数生成算法：
参数：奇数 ，，,
输出：一个随机素数
1.计算；
2.随机选择；
3.随机选择并设置；
4.设置；
5.如果（偶）那么；
6.如果 然后
（a）设置；
（b）转到步骤4；
7.输出。
很容易看出，步骤6中的候选是奇数并且与中的所有素数共素。即，由于，我们有且始终保持在中。这意味着与中的所有素数共素。此外，如果在步骤4中是偶数，那么因为是奇数，所以必须是奇数，因此在步骤6是奇数。每个候选不能被第一个小素数整除，每个候选是质数较高的概率，所以可以得到一个更快的素数生成算法（参见进行完整分析）。
3 我们的侧通道攻击
我们的攻击是基于我们可以在步骤4恢复的奇偶性的假设，这是由于在步骤5在上执行奇偶校验测试。即，在实际实现中，分支条件通常根据结果产生不同的物理泄漏考试。事实上，通过测量功耗，攻击者可以确定是否已经执行了操作，这给出了的奇偶位。因此，我们的攻击是上奇偶位的简单动力攻击（SPA）。在实践中，这个假设可能是现实的或不现实的，这取决于所使用的微处理器，硬件对策的存在以及测试的实施方式。我们注意到，基于类似假设的SPA攻击已经在中进行了描述。
这里我们展示这个奇偶校验位序列使我们能够恢复作为输出返回的素数的最低有效位。我们的攻击基于以下简单的引理：
引理1.令是一个奇数整数，令。 定义和序列。 那么，对于。
证明: 根据定义，我们有。 因此，我们有，给出。 它遵循。
此外，我们有。采用关系模2，得到，因为Pi;是奇数，并且由于，所以有模2。这证明了结论。 □
命题1. 使用前面的符号并让 ，我们有
.。
证明：这通过观察立即从前面的引理得出。 □
我们假设参数Pi;，，和是公开的并且是攻击者已知的。对于，令表示在步骤4出现的整数的序列，其中是在步骤2中最初生成的整数。令表示在步骤 4.从步骤5测试的奇偶性可以得到的奇偶性; 这是通过对的奇偶性做一个假设来完成的，这个奇偶性在步骤4之后是恒定的。然后使用前面的引理，在个素性测试之后得到的值3。然后我们可以写出：
其中是已知的且是未知的。因此，生成的素数或可以写成：
其中和是攻击者未知的整数，整数，，和是已知的。
我们做出以下假设：我们假设，所以。我们注意到，在Joye-Paillier算法中，采用是一个有效的参数选择。在这种情况下，可以写入整数：
其中是已知常数，是未知整数。
定理1（Coppersmith [1]）. 给定和的高阶或低阶位的，可以恢复中时间多项式的的因式分解。
使用Coppersmith定理，如果素数检验的数目至少是的一半大小，那么可以在多项式时间内恢复的因式分解。令表示与的随机位奇数整数共素数为素数的概率。我们做出启发式逼近，候选人的行为就好像它们是一致且独立分布的。从的分析中，我们得到候选是概率为素数的：
其中且是欧拉函数。因此，让是给出素数测试数的随机变量，我们有：
3我们需要 个奇偶校验位，因为我们不使用第一个奇偶校验位。
这给出：
总而言之，如果攻击既适用于又适用于，则位RSA模数的分解可以在多项式时间内以分数恢复：
的生成模量。我们在表1中提供了各种模量大小的相应分数。对于位的主要大小，我们取最大的，使得：
那么我们取和，，其中; 这是Joye-Paillier算法的有效参数选择。表1显示，对于1024位RSA模量，我们的侧通道攻击能够将RSA模量的分数分解。如果算法仅在智能卡内部运行一次，这意味着在实践中，智能卡的一小部分可能会被破坏。
表1.素数和的RSA模型比特大小，比特大小，中素数的数量，素性测试的平均数量以及弱RSA模量的分数。
我们注意到假设可以放宽到和的小（已知）值; 在这种情况下，值将被彻底搜索4。
4 对策
在本节中，我们讨论三种可能的对策。我们的第一个对策是定期重新生成一个新的种子，以便攻击者不会获得有关素数的足够信息。令为给定种子
4或者，我们可以尝试推导出一个形式为q = 2n·x b·Pi; C的素数的Coppersmith定理的变体，它具有未知的x和b以及已知的常量Pi;和C.
进行的素性测试的最大次数。整数应该足够小以防止以前的攻击，但不能太小以保持相同的效率水平; 我们建议取，其中是主要的比特大小。我们得到修改后的算法：
修改的素数生成算法：
参数：，，，，
输出：一个随机素数
1.计算;
2.让;
3.随机选择;
4.随机选择并设置;
5.设置;
6.如果（偶）那么;
7.如果 ，那么
（a）设置;
（b）让;
（c）如果转到步骤5，否则转到步骤2;
8.输出。
我们的第二个对策在于用来替换指令，其中是一个小的随机整数。如果是在一定时间内实现的，那么攻击者得到奇偶校验位不知道哪个整数，这就防止了以前的攻击。第二个对策是有效的，因为与素数测试运行时间相比，额外的运行时间可能可以忽略不计。
我们的第三个对策是实施测试，使其不泄漏。标准的方法是计算分支的两侧并选择正确的结果。这种对策类似于RSA乘幂和ECC标量乘法中的平方和乘法总是和双加总是对抗（见）。 指令：
6.如果（偶）那么
然后换成：
6.（a）让;
（b）设置;
（c）设置;
（d）令.
在这种情况下，总是执行的计算，因此攻击者可能更难以恢复的奇偶性。
5 结论和开放问题
我们已经证明，Joye-Paillier素数生成算法的不当实现可能会屈服于侧通道分析。我们的攻击是基于这样的假设，即简单功耗分析可以给我们在分支条件下出现的奇偶位。我们已经表明，对于某些参数（）和1024位RSA模量，可以有效地分解这些模量的一部分。但实际上，通过SPA获得的一些奇偶校验位可能是错误的。因此，一个有趣的开放问题是发现一个有错误的攻击。正式：
开放问题：令，令是一个奇数整数，令。 对于，定义序列 和。假设具有概率，并且，否则独立于每个。对于 给定序列，找到中的时间多项式。
致谢：我们希望感谢Marc Joye和匿名审稿人的宝贵意见。
参考文献
1. D. Coppersmith, Small solutions to polynomial equations, and low exponent vulnerabilities. J. of Cryptology, 10(4)233-260, 1997. Revised version of two articles of Eurocrypt rsquo;96.
2. J.S. Coron, Resistance against Differential Power Analysis for Elliptic Curve Cryptosystems. Proceedings of CHES rsquo;99. LNCS, Springer-Verlag.
3. W. Dupuy and S. Kunz-Jacques, Resistance of Randomized Projective Coordinates Against Power Analysis, Proceedings of CHES 2005, LNCS.
4. P.A. Fouque, S. Kunz-Jacques, G. Martinet, F. Muller, and F. Valette. Power Attack on Small RSA Public Exponent. Proceedings of the 8th International Workshop on Cryptographic Hardware and Embedded Systems (CHES rsquo;06), LNCS 4249, Springer-Verlag, 2006.
5. M. Joye, P. Paillier and S. Vaudenay, Efficient Generation of Prime Numbers. Proceedings of CHESrsquo;00, Lecture Notes in Computer Science, Springer-Verlag No 1965, pp. 340-354.
6. M. Joye and P. Paillier, Fast Generation of Prime Numbers of Portable Devices: An Update. Proceedings of CHES 2006, LNCS 4249, pp. 160-173, 2006.
7. P. Kocher, J. Jaffe, and B. Jun, Differential power analysis, Advances in Cryptology - CRYPTO
全文共7341字，剩余内容已隐藏，支付完成后下载完整资料
资料编号：[11728]，资料为PDF文档或Word文档，PDF文档可免费转换为Word
以上是毕业论文外文翻译，课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。
