每周一篇paper赏析：Prime and Prejudice: 对抗环境下的素性检验

这次给大家带来的这篇论文是来自伦敦大学皇家霍洛威学院和德国波鸿鲁尔大学的研究者们的工作成果。

本文发表在CCS 2018上，进入了该会议最佳论文Finalist。其工作核心内容是对来自攻击者恶意输入数字的素性检验进行了系统的分析，并进行了广泛的实验，对OpenSSL、GNU GMP等库在这种场景下的可靠性进行了评估。

为什么我们需要素性检验呢？因为在密码学中，素数有着很重要的作用：

• 许多密码学体系是依赖与素数进行运算的，比如RSA、Diffie-Hellman密钥交换等；

• 在许多密码学体系中，使用素数参数可以避免一些攻击，如我们熟悉的Pohlig-Hellman算法中的分治方法或是Lim-Lee small subgroup confinement attack；

• 生成素数的过程往往都需要对随机选取的数字进行素性检验。

而素性检验的方法又主要可以分为两大类:

• 第一类是确定性的方法，这类方法可以确定性的证明输入的数字是否为素数，但这类方法往往运算效率较低，而不适用于大多数的密码学场景。这类方法的一个最简单的例子便是试除法，对于一个给定的数  ，我们可以用  到  之间的素数进行试除，如果都不能除尽，则说明  是一个素数。

• 另一类方法则是概率方法，这类方法往往运用素数的一些数学性质进行判断，只能证明输入的素数是否为合数，而不能保证一个数字一定是素数。一个最简单的例子就是费马素性检验，对于一个给定的数  ，我们随机选取在  到  之间的整数  ，计算  是否成立，如果不成立，则根据费马小定理，  不是一个素数；反之，  可能为素数。

一般我们使用素性检验时，往往是对一个随机生成的数字进行检验；而在一些特殊的情况下，我们也需要对用户输入的数字进行素性检验，在这种情况下，对于素性检验算法失败的概率，我们应该考虑其最差的情况，而不是平均的情况，本文关注的就是这一类问题。

目前，几乎所有工具使用的素性检验算法都是Miller-Rabin素性检验算法，只是在轮数和base的选取上略有差异，Miller-Rabin算法的简要原理如下：对于一个奇素数  ，我们将  写为  的形式，其中  为奇数且  ，所以根据费马小定理和二次探测定理，对于任意一个不是  倍数的自然数  ，以下两个条件必有一个成立：

1.   

2.   

这里的  就是用于Miller-Rabin素性检验的base。如果用一个base   对数字  进行Miller-Rabin素性检验时，以上两个条件都不满足，则  为合数，  被称为是一个witness；否则，则  可能为素数，  被称为是一个non-witness。

对于Miller-Rabin的正确性证明以及费马小定理、二次探测定理，网络上有许多详细的文章，此处不再赘述。

为了帮助读者更好的理解Miller-Rabin素性检验，这里引用一个文章作者在slides中使用的例子。作者用一个红蓝两色球的抽奖例子很好的演示了Miller-Rabin素性检验及其可能失效的情况。

作者用红色球表示non-witness，用蓝色球表示witness。对于素数  ，  的所有base都是non-witness，所以无论如何选取base，最后都可以得到  是素数的结论。

但当  时，假设我们进行7轮随机选取base的Millar-Rabin素性检验，当我们抽取2, 3, 13, 20, 30, 41, 45作为base时，其中存在witness，则可以得出结论：  为合数；但如果恰好我们抽取到8, 11, 20, 23, 24, 41, 47这7个non-witness作为base，则会错误得出  为素数的结论。

正如上文中所提到的，Millar-Rabin素性检验算法在不同工具的实现中使用了不同的base选取方式，选取方式主要分为两种：

• Fixed base Miller-Rabin：这一类实现在每次调用时使用相同的base，如t轮的Millar-Rabin就使用前t个素数作为base，或是从一个固定的列表中随机选取t个数字作为base。对于这一类实现，Arnault的95年的一篇论文中提出了一种构造伪素数的方式，可以使得固定的一系列base都是构造的数字的non-witness。

• Random base Miller-Rabin：顾名思义，这一类每轮实现会随机选取2到  之间的数字作为base。而根据Monier-Rabin bound，最多有  的non-witness。Monier在一篇80年的论文中也提出了一种构造方式，可以使得non-witness的数量达到这个上限。因此，对于t轮的Random base Millar-Rabin，我们大约有  的概率使其错误的认为输入的数字是素数。

在这篇论文中，作者结合了上述两篇论文的构造思路，对市面上常用的数学工具、库中实现的素性检验进行了测试，实验结果如下图所示。

从表中可以看出，OpenSSL这一知名密码学库，也是大量网站使用的TLS实现，采用了一个由输入数字bit-size决定轮数的Millar-Rabin算法（具体轮数选取方式见下图），其注明的失败率小于  ，但通过构造恶意输入却可以让这个失败率达到  。

因为对于bit-size超过1300的数字，OpenSSL只进行两轮Millar-Rabin，根据前文所述，这里攻击的成功率约为  。OpenSSL的这一素性检验函数也被用在了OpenSSL对Diffie-Hellman密钥交换实现中的参数验证步骤中，因此一旦这个2轮的Millar-Rabin被成功攻击，就会导致Diffie-Hellman因参数不是素数而计算离散对数变得更加容易而遭到攻击。

WolfSSL是一个常用于嵌入式系统里面的轻量级TLS库，它对于素性检验的实现直接调用了LibTomMath和LibTomCrypt这两个开源数学运算工具中的fixed base Millar-Rabin，并且它还硬编码了轮数  ，因此在实际运行过程中，WolfSSL的素性检验只使用了前8个素数作为base。利用Arnault在95年论文中提出的构造方式，我们可以很容易的构造出一个1024bit的合数，使得前40个素数都不是它的witness，从而使Millar-Rabin失效。事实上，我们可以进一步构造伪素数，使得前256个素数都不是它的witness（如之前表格所示，256是用户可以指定的轮数最大值），但这也会使得构造出来的伪素数变得很大（约7000bits）。

在文章最后，论文作者也给软件开发者、密码学研究员和数学研究员提出了一些建议。其中对于软件开发者的建议值得大家注意：作者建议开发者在使用素性检验函数前应考虑清楚使用的场景，即输入的数字是随机数还是用户输入的数字。因为这一区别会使得素性检验算法的失败率存在较大差异。作者也建议开发者尽可能采用Baillie-PSW素性检验或是相对安全的随机选取base的Miller-Rabin。Baillie-PSW素性检验算法是Miller-Rabin素性检验算法与Lucas素性检验算法的结合，目前还没有已知的伪素数。最后，作者也建议开发者在实现公钥加密时尽可能选用标准的参数，以提高安全性。

由于篇幅所限，笔者不在此展开讲解具体的攻击方式，读者可以自行点击阅读原文查看论文的附录部分。值得注意的是，在文章附录部分的攻击方法中，部分公式存在错误（如  与  的关系式前缺少负号），建议读者阅读Arnault的Constructing Carmichael numbers which are strong pseudoprimes to several bases。读者在实现攻击方法后也可以在密码学练习平台CryptoHack(https://cryptohack.org/)中MATHEMATICS分类下的同名题目中进行测试。

原文始发于微信公众号（上科大系统与软件安全实验室S3L）：每周一篇paper赏析：Prime and Prejudice: 对抗环境下的素性检验