智能卡的测试随机数

　　实现了随机数发生器之后，对它所产生的数必须严格地测试，基本情况是在所产生的随机数中，1和0的数量应接近于相等。然而，简单地把少量数字打印出来并做一些比较检查是不够的，可以用标准统计方法从数学上测试随机数。不言而喻，有大量8位随机数需要这样的测试，应当有10 000到100 000的数字产生并分析以达到合理的可信结果。测试这样多的数字的惟一方法是使用计算机测试程序。

　　评估随机数的质量时，也必须研究所产生的数的分布，如果是非常不均匀的，特别偏爱某些数值，则这些区域可以准确地用于预测的目的。于是Bernoulli定理应当能被满足，这条定理指出，一个特定数字的出现和前面已出现的情况无关，它只依赖于该数字本身出现的概率。例如，投骰子时，4出现的概率永远是1/6，而和先前掷出的数字是什么无关，这也被称为事件的独立性。

　　随机数的周期，这是所产生的随机数在序列中开始重复其本身时的数目，也是很重要的。当然，它必须在任何情况下都要比随机数发生器的生命周期长。在这种情况下，就可以用十分简单和可靠的方式排除用记录所产生的随机数的整个周期来攻击系统的可能性。

　　有多种多样的统计测试可用来研究事件的随机性，但实际上，我们限于少量简单的测试，它们的结果比较易于解释。关于随机性测试这一课题已有很多的出版物，如［Knuth 97］，［Menezes 97］，以及相应的标准［FIFS 141-1，RFC 1750］。一个可很简单建立并很容易解释的测试是在大量的随机数中去计数每一字节值的出现次数，如果结果显示的图形如图1所示，则它们对数的分布给出了一个很好的指示。

　　图1  一序列5 000个单字节随机数的统计分布（这些数是由一个典型的智能卡伪随机数
　　发生器产生的，基于纯算术的考虑在0～255范围内每一可能之值应发生195次）

　　如果用这样的图解来研究8字节长的随机数，在水平轴上所绘的仍应为单个字节或至多二字节之数，否则需要统计分析的数的数值就变得太大了。一个很好的指导原则是每一个随机数应当对每一数值大约出现4～10次，以保证获得合理的可靠结果。这样，就能够很快地看到所产生的随机数是否完全利用了字节的可能带宽。如果不是这种情况而某些值得到了偏爱，它就为攻击者提供了一个可能的切入点。

　　遗憾地是，这一测试关于随机数的出现次序未做出任何说明，仅仅是些关于它们的分布。例如，对于一个“随机数”发生器有可能周期性地输出0～255，这将产生特别均匀的分布，但这些数完全是可预测的，必须有另外的测试用来判断随机数的这一质量准则。

　　另一个实际的测试能对一系列的随机数产生简单而快速的评估是用文件压缩程序压缩这一序列，按照Shann。h，可能压缩的程度是与所产生的这一组数的随机性成反比的。

　　一个显然更强有力的测试是非常有名的；r＇测试。虽然它和前述的图形测试一样是关于分布均匀性的，由于其执行使用了［Brostein 96］的数学方法，所以要显然比较精确。如果假定随机数是均匀分布的，则可算出其中位值和标准差。对正常分布的偏离则可基于γ2分布予以确定，由此可以给出随机数的分布的数字值。

　　然而，这一测试不能用来得出有关在序列中随机数的出现的任何结论，其他统计测试可用来检查随机数出现的随机性［Knuth 97］，诸如串列测试，它分析在随机数中模式产生的周期。类似地，间隙测试分析不出现模式的区间大小。扑克（Pokes）测试也可用来判断所出现的模式的，f分布，而Coupon采集器测试则判断不发生模式的t＇分布。表1给出了关于随机数统计测试标准的一览表。

　　表1  随机数统计测试标准一览表

　　谱分布研究每个随机数和下一个接着的数的关系，已有一定数量的实用性成果［Knuth97］。在这个测试的二维方案中，随机数和它们紧接的后继者被绘制在x-y坐标系统中，如图2所示。三维的方案中还需要后继的后继者和第3个坐标轴（z-轴）。Ⅳ维谱测试可以类似的方式执行，但为了理解的缘故，这些无需图解表示。

　　至少，上述测试必须执行并分析以达到可靠的和权威性的对随机数发生器的评估。另外的计算和测试可用来确认所获得的结果。只有这样才有可能对一组随机数的质量做出合理的正确判断。

　　当然，考虑到在智能卡应用中随机数的使目领域，一个过分完善的随机数发生器通常并不被认为是适当的。例如，当随机数在鉴别的情况下如能被预测，对安全性的影响将是很小的，这是因为没有任何攻击能离开加密随机数的秘密密钥。

　　无论如何一个比较严重的问题会在能够操纵随机数发生器时出现。例如，使之总产生同一序列的随机数。在这种情况下，一项基于把数字回送的攻击不仅是可能的，而且可能是成功的。如果随机数的周期很短时，这将也会成为现实。在每种单独的情况中，随机数所必须满足的条件应当仔细考虑，因为这些特点影响了随机数发生器。虽然，在这里的极大努力可以导致很高质量的随机数，但同时也经常会增加占用存储空间的结果，在智能卡中这是特别受限制的。

　　图2  5 000个单字节随机数的后继随机数之值的图形表示，相应于谱测试
　　（从规整的模式一眼就可看出后继的随机数的分布是接近于均
　　匀的，这些数是由一个典型的智能卡微随机数发生器产生的）