防止噪声影响随机数发生器的方法和设备

摘要

公开了一种防止噪声影响基于触发器的亚－稳定特性的随机数发生器的方法和设备。外部噪声将以相同方式影响较大的随机数发生器电路中的多个触发器，因为它们在物理上很接近。因而，通过在单个随机数发生器中引入多个触发器(称为核心随机元件)可以降低使用外部噪声来影响随机数发生器的操作的能力。如果随机数发生器中有一个核心随机元件受到了噪声影响，那么所有的核心随机元件都将受到噪声影响。因而，如果核心随机元件的全部(或大部)同时产生一个随机位，就存在随机数发生器受到噪声影响的可能性，并丢弃所有产生的位。在随机数发生器引入了一种或多种机制来确保当多个核心随机元件同时产生一个位时不产生随机位。

说明书

对相关申请的交叉引用

本发明与2000年3月6日提交的题为“使用触发器亚-稳态来产生随机数的方法和设备(Method and Apparatus for GeneratingRandom Numbers Using Flip-Flop Meta-Stability)”的美国专利申请序列号09/519,549以及2001年7月25日提交的题为“使用伪随机序列对随机数发生器解相关的方法和设备(Method andApparatus for Decorrelating a Random Number Generator Usinga Pseudo-Random Sequence)”的美国专利申请09/912,685有关，它们都被转让给了本发明的受让人并在这里引入作为参考。

技术领域

本发明涉及随机数产生，更准确地说，涉及使用触发器亚-稳态(meta-stability)来产生随机数的方法和设备。

技术背景

很多应用和电子设备需要随机数，包括机遇游戏，例如(扑克(poker)、轮盘赌和吃角子机)。特别地，大量的加密算法和协议依赖于不可预测的随机数来源，以实现安全的电子通信等等。随机数发生器应该在指定的数字范围内产生每个可能的排列。另外，随机数发生器不应该有偏移并且应该以和任意其它数字或任意其它数字序列相同的概率产生任意给定的数字和任意给定的数字序列。此外，随机数发生器应该产生不能预测的随机数，而不考虑先前的结果集合的大小。因而，随机数应该是完全不可预测的并且对外部影响不敏感。

2000年3月6日提交的题为“使用触发器亚-稳态来产生随机数的方法和设备”的美国专利申请序列号09/519,549以及2001年7月25日提交的题为“使用伪随机序列对随机数发生器解相关的方法和设备”的美国专利申请09/912,685，公开了使用触发器的亚-稳定特性来产生随机数的方法和设备。触发器由故意破坏触发器的建立时间或保持时间(或二者)的输入提供时钟以确保亚-稳定特性。当出现错误时收集到一个位。

尽管亚-稳态是随机发生的，但已经发现亚-稳态的持续时间和发生会受到外部噪声影响(通常随机部件的行为会受内部噪声控制，例如半导体设备中发现的热噪声)。因而，外部噪声可以用来影响随机数发生器并由此损害所产生的数字的随机特性。因而需要不受外部噪声影响、利用亚-稳态产生随机数的方法和设备。

发明内容

总的来说，公开了一种方法和设备，用于防止外部噪声影响基于触发器亚-稳定特性的随机数发生器。已经观察到外部噪声可以由攻击者用来影响使用触发器亚-稳定特性的随机数发生器的操作。本发明认识到外部噪声将以相同方式影响多个随机数发生器中的多个触发器，因为它们在物理上很接近。

因而，依照本发明的一个方面，通过在单个随机数发生器中引入多个触发器(这里称为核心随机元件)来降低使用外部噪声影响随机数发生器的操作的能力。更准确地说，本发明认识到如果随机数发生器中的核心随机元件的一个受到了噪声影响，则核心随机元件的所有(或大部分)都将受到噪声影响。因而，如果核心随机元件的全部(或大部)同时产生了一个位，就存在随机数发生器受噪声影响的可能，并丢弃所产生的位。因而在随机数发生器中引入了一种或多种机制以确保随机位不是在多个核心随机元件同时产生一个位时被产生的。偶尔，两个核心随机元件将同时产生一个随机位，这仅是简单的意外，但丢弃这些位对系统的整体效率所产生的影响是微不足道的。

通过参考下面的详细描述和附图将获得本发明以及本发明进一步的特性和优势更完整的理解。

附图说明

图1A说明了依照2000年3月6日提交的题为“使用触发器亚-稳态来产生随机数的方法和设备”的美国专利申请序列号09/519,549的随机数发生器；

图1B说明了可以利用时钟源来同步图1A的随机数发生器的输出的同步电路；

图1C说明了由图1A和1B的电路所产生的一组波形；

图2说明了依照2001年7月25日提交的题为“使用伪随机序列对随机数发生器解相关的方法和设备”的美国专利申请09/912,685的另一种随机数发生器；

图3说明了由图2和图1B的电路所产生的一组波形；

图4说明了可以用上面结合图1A、1B和2所论述的随机数发生器的部件来实现的核心随机元件；以及

图5到8说明了依照本发明的随机数发生器的不同实施方案。

具体实施方式

本发明认识到外部噪声将以相同方式影响较大的随机数发生器中的多个触发器，因为它们在物理上很接近。因而，本发明通过引入多个触发器降低了利用外部噪声来影响随机数发生器的操作的能力，这些触发器被实现为核心随机元件的集合，每个核心随机元件400由几个触发器组成。下面结合图4进一步论述核心随机元件。

更准确地说，本发明认识到如果核心随机元件400中的一个受到噪声影响，核心随机元件400的全部(或大部)也将受到噪声影响。因而，如果多个核心随机元件400像(例如)由异或门(“XOR”)或检测所产生位的另一个门检测到的那样同时产生了一个位，就存在随机数发生器受噪声影响的可能，并且丢弃所产生的位。因而，本发明引入了一种或多种机制以确保随机位不是在核心随机元件400的全部(或大部)同时产生一个位时被产生的。

下面的论述被如下组织。首先，在题为“使用亚-稳定触发器的随机数发生器”一节论述多种合适的核心随机元件。随后，图4根据(如)结合图1到图3所论述的随机数发生器100、200来说明更通用概念的核心随机元件400。最后，在题为“防止随机数受外部噪声影响”一节论述本发明的噪声影响降低技术。

使用亚-稳定触发器的随机数发生器

图1A说明了依照2000年3月6日提交的题为“使用触发器亚-稳态来产生随机数的方法和设备”的美国专利申请序列号09/519,549的随机数发生器100。随机数发生器100通过标记一半的“0”为“1”、标记另一半的“0”为“0”来提供随机输出位的平均分布。另外，一半的“1”被标为“1”，另一半“1”被标为“0”。

如图1A所示，随机数发生器100包括触发器110、延迟115、120、D-型触发器125、132和时钟振荡器130。触发器110由故意破坏触发器的建立时间或保持时间(或二者)的输入提供时钟以确保亚-稳定特性。例如，可以用延迟115、120来破坏建立时间或保持时间。触发器110可以实现为D型、T型或JK型触发器。另外，触发器110可以实现为简单的锁存器以及略有不同的电路，这些对于本领域的技术人员都是很显然的。

时钟信号是由时钟振荡器130和D-型触发器125产生的，D-型触发器的Qbar输出被反馈回它的D输入以将时钟除以2。这样，D型触发器125使用和T型触发器相同的方式操作(双态输出)，以提供除2机制。因而，触发器110的D输入由交替的“1”和“0”驱动。附加的除2触发器132产生标记信号，如图1C所示，该信号标记波形输入中“0”的一半为“1”，标记另一半“0”为“0”。

在图1A和图1C中看得最清楚，由时钟振荡器130产生的波形时钟是在图1中标记为“时钟”的采样点获得的。由除2触发器125产生的波形输入是在图1A中标记为“输入”的采样点获得的。由延迟115产生的波形输入D(破坏了触发器的建立时间)和由延迟120产生的波形输入时钟是在图1A中对应的采样点获得的。由除2触发器132产生的波形标记是在图1A中标记为“标记”的采样点获得的。

如图1C所示，由延迟115、120对建立时间或保持时间(或二者)的破坏确保了触发器110将显示出亚-稳定特性，像波形亚稳定输出所示范的那样。下面将进一步论述触发器110的亚-稳定操作提供产生随机数的机制。

作为来自延迟115、120、触发器本身的内在延迟，以及(更重要的)来自亚-稳定特性的非统一延迟的延迟结果，波形亚稳定输出没有被同步到波形时钟。因而，为了使图1A的随机数发生器适合同步应用，就在图1B中提供了一种说明性的机制来用波形时钟同步波形亚稳定输出。注意图1A和图1B的电路是通过联结相似字母的圆圈而连接在一起的。

图1B中所示的同步电路135包括多个串联触发器140-142，选择它们以便轻易进入亚-稳定状态。另外，如果这些触发器140-142中的一个没有变成亚-稳定，时钟信号的周期应该足够长以使亚-稳定触发器将停留在固定的逻辑值(0或1)，这样当在下一个触发器140-142对信号采样时，触发器是稳定的。采用这种方式，每个触发器140-142增大了用波形时钟同步波形亚稳定输出的机会，而去掉了任何亚-稳态。实际上，这样的电路出错的机会约为数十年一次。

异或门(“XOR”)150比较波形亚稳定输出的同步版本(标记为稳定输出)以及指定为波形输入的稳定输出(在除2触发器125的输出上采样)。因为XOR门150的输出当且仅当两个输入不同时才为高电平，XOR门150的输出(“出错”)在波形稳定输出不匹配输入信号时为高电平。这个错误仅在触发器110、140、141、142中的一个已经出错(我们假定这作为亚-稳定特性的结果而发生)时才会发生。XOR门150(“出错“)的输出被施加到移位寄存器160的移位输入(Shift_in)，每发生一次错误移位寄存器将对标记信号移动一位。因而，每当出现错误时第一个实施方案收集一个位。

移位寄存器160的输入线被连接到标记信号。采用这种方式，每次有错误时，移位寄存器160将从标记信号移入一位。因而，如图1C所示，对错误0，将获得一个等于1(根据标记信号)的位。同样，对错误1，将获得一个等于1(根据标记信号)的位。

随机数发生器100还标记触发器110的“1”输入为“1”或“0”标记。因而，如果输入为“1”时发生错误，由于是“1”值导致的错误，将获得随机位的平均分布。因此，电路对发生在“1”或“0”输入值中的错误之间的偏移是敏感的。

如前所示，以上面结合图1A到图1C所论述的方式来标记输入位提供了随机输出位的平均分布。但已经发现噪声能够影响亚-稳态的持续和发生。因而，如果噪声和标记信号相关，那么随机数发生器的输出将不再是随机的。

因而，使用无偏移的(关于“0”和“1”的频率)信号源作为标记信号。标记信号与系统中任何噪声相关的概率都很低。采用长度足够的线性反馈移位寄存器(LFSR)来降低相关的机会并降低LFSR输出中的偏移。(如)在Bruce Schneier的“Applied Cryptography”第369-388页(Wiley，1994)中描述了合适的LFSR。

图2说明了随机数发生器200。如图2所示，随机数发生器200包括触发器110、延迟115、120、D-型触发器125和时钟振荡器130，它们以结合图1A所描述的相同方式操作。另外，随机数发生器200包括线性反馈移位寄存器210，它产生LFSR的标记信号(如图3所示)，该信号标记波形输入中略超过一半的“0”为“1”，标记几乎一半的“0”为“0”，这与任何噪声相关的概率都很低。该信号总是有轻微的偏移，因为对n位LFS R来说只有2ⁿ-1个模式(全“0”模式永远不会发生)。如果n很大这个偏移将变得无关紧要。

因而，图2的随机数发生器200用线性反馈移位寄存器210代替了图1A的标记触发器132。线性反馈移位寄存器210可以被实现为在Bruce Schneier的“Applied Cryptography”第369-388页(Wiley，1994)中所描述的LFSR。图2的随机数发生器200只能由图1B的同步电路135来使用时钟源同步随机数发生器200的输出。

如前所示，线性反馈移位寄存器210应该提供足够数量的位以降低相关的机会并降低LFSR输出中的任何偏移。对由n个触发器组成的线性反馈移位寄存器210来说，在数字开始重复之前将有2ⁿ-1个二进制数字。因而，随着线性反馈移位寄存器210中的触发器个数增加，2ⁿ-1二进制表示中的“-1”将变得更不重要。无论如何，因为任何可归于“-1”项的偏移的方向都是已知的，可以用合适的电路去除或校正偏移。

因而，线性反馈移位寄存器200提供了标记输出、LFSR标记，它是伪随机的，一半输出位为“0”，另一半输出位为“1”。

已经观察到如果线性反馈移位寄存器210不可靠，一部分输出(甚至是一个随机部分)可能允许获知线性反馈移位寄存器210的状态。采用这种方式，能够预测随机数发生器200的输出。因而，应该利用线性反馈移位寄存器210，它没有任何可辨别的统计特性，由此使线性反馈移位寄存器210的输出无用。在更进一步的变化中，通过释放移位寄存器160的收集到的位输出并允许在每个收集间隔丢失一些收集到的位而实现了附加的安全性。

移位寄存器160在每次发生错误时从标记信号移动一位。采用这种方式，错误的到达时间是不可辩认的，而且任何人都无法预测将选择线性反馈移位寄存器210的哪些位。

防止随机数受外部噪声影响

如前所示，本发明认识到外部噪声将以相同方式影响板上或集成电路中的多个触发器，因为它们在物理上很接近。因而，依照本发明的一个特性，通过在随机数发生器中使用两个或多个触发器(在此称为核心随机元件400)降低了使用外部噪声来攻击随机数发生器的能力。更准确地说，本发明认识到如果核心随机元件400中有一个受到了噪声影响，它们都将受到噪声影响。因而，如果核心随机元件400的全部(或大部)同时产生位，像(例如)由异或门(或者检测发射出的位的另一个门)检测到的那样，就存在随机数发生器受噪声影响的可能，则所有产生的位都被丢弃。

例如，如果t是大于0的阈值，n是触发器的个数，那么当且仅当亚-稳定触发器产生(n/2+t)或更少的相同结果时才产生一个位。同样，如果亚-稳定触发器产生了超过(n/2+t)的相同结果就不产生位。因而，如果n等于10个触发器，t等于2，那么如果8个或更多触发器有相同的结果，就丢弃该位。另外，如果n等于2个触发器，那么如果所有触发器有相同结果(通过设置t大于0)就丢弃该位。采用这种方式，本发明即使在触发器没有产生“1”和“0”的平均分布时也能提供随机数发生器。如果亚-稳定触发器将产生“1”的概率是p，且相同的亚-稳定触发器将产生“0”的概率是1-p，那么如果产生了超过p*n+t或少于p*n-t个“1”就丢弃一个位。例如，如果n等于10，p等于0.7，并且t等于1，那么如果有9个或多于9个、或者5个或少于5个的“1”就丢弃该位。

图4说明了用(例如)上面结合图1A、1B和2论述的随机数发生器100、200的部件实现的核心随机元件400。如图4中所示，核心随机元件400包括触发器410、可变延迟415和420、以及同步电路430。时钟信号是由时钟源(未显示)产生的。如上所示，触发器410由故意破坏触发器410的建立时间或保持时间(或二者)的一个输入提供时钟，以确保亚-稳定特性。(例如)可以用可变延迟415和420来破坏建立时间或保持时间。触发器410可以用(例如)D、T或JK型触发器实现。

如上所示，来自延迟415和420的延迟、触发器410本身的内在延迟、以及(更重要的)来自亚-稳定特性的非统一延迟，可能导致波形亚稳定输出不被波形时钟同步。因而，为了使图4的核心随机元件400适合同步应用，在图4中提供了说明性的机制以使用波形时钟来同步波形亚稳定输出。

图4中所示的同步电路430包括多个串联的触发器440-442，选择它们以使不轻易进入亚-稳定状态。另外，如果这些触发器440-442之一变成了亚-稳定，则时钟信号的周期应该足够长以使亚-稳定触发器的输出将设置为固定的逻辑值(0或1)，这样当在下一触发器440-442对信号采样时，触发器是稳定的。采用这种方式，每个触发器440-442增大了用波形时钟同步波形亚稳定输出的机会，而去除了任何亚-稳态。通过比较输出的亚稳定输出和输入信号，可以发现它们不一致的情况。这种不一致只在核心随机元件400中的触发器之一变为亚-稳定时才会发生。因而，用异或(XOR)门来检测核心随机元件400所产生的位，如第一个描述中的XOR门150所示。对核心随机元件400的操作的附加细节，可以参考上面提及的并引入作为参考的有关共同未决的申请。

图5依照本发明说明了一种随机数发生器500。如前所示，本发明通过在一个随机数发生器中使用多个触发器降低了随机数发生器对使用外部噪声攻击的敏感性。在图5中所示的说明性实施方案中，随机数发生器500包括两个串联的核心随机元件400-1，400-2，如上结合图4所示。

时钟源是由时钟振荡器530和D-型触发器525产生的，525的Qbar输出被反馈回它的D输入。采用这种方式，D-型触发器525以和T-型触发器(双态输出)相同的方式操作，以提供除2机制。因而，示例性核心随机元件400-1的输入由交替的1和0驱动。下面结合图8进一步论述另一种输入信号方案。

如图5所示，核心随机元件400-1的输出被施加为核心随机元件400-2的输入。如果核心随机元件400-1、400-2之一受到了噪声影响，它们都将受噪声影响。因而，如果核心随机元件400-1、400-2同时产生位，如异或(XOR)电路540、550所检测到的那样，就存在随机数发生器500受噪声影响的可能性，并且丢弃所有被产生的位。因而，随机数发生器500包括一组异或(XOR)电路540、550、560。

第一个异或门(“XOR”)540比较波形稳定输出的同步版本和波形输入(在除2触发器525的输出上采样)。因为XOR门540的输出当且仅当两个输入不同时才为高电平，所以当来自核心随机元件400-2的波形稳定输出与仅在核心随机元件中的触发器之一变成亚-稳定时才发生的输入信号不匹配时，XOR门540的输出为高电平。同样，因为XOR门550的输出当且仅当两个输入不同时才为高电平，所以当来自核心随机元件400-2的波形稳定输出不匹配来自核心随机元件400-1的波形稳定输出时XOR门550的输出才为高电平。

然后，两个XOR门540、550的输出被施加到XOR门560。由于当且仅当XOR门560的两个输入不同时，它的输出才为高电平，如果来自两个核心随机元件400-1、400-2的波形稳定输出都为高电平或者低电平，则XOR门560的输出也将为高。换言之，只有当两个核心随机元件400-1、400-2都有生成的位时，XOR门560才抑制位的生成。

XOR门560的输出被施加到移位寄存器570的使能输入。因而，在每次来自唯一的一个核心随机元件400的波形稳定输出不匹配相应的核心随机元件400的输入时(即，发生错误时)移位寄存器570将从LFSR210的标记信号(LFSR标记)移动一位。所产生的位随后被施加到计算机接口580(或其它应用)。

图6说明了依照本发明的一种随机数发生器600。在图6所示的说明性实施方案中，随机数发生器600包括两个并联的核心随机元件400-1、400-2，如上结合图4所论述的那样。图6中所示的实施方案可以防止攻击者利用图5的实施方案中的输入信号在不同时间通过两个触发器的事实。

时钟源是由时钟振荡器630和D-型触发器625产生的，625的Qbar输出被反馈回它的D输入。采用这种方式，D-型触发器625以和T-型触发器(双态输出)相同的方式操作，以提供除2机制。因而，并联实施方案中的核心随机元件400-1和400-2的输入是由交替的1和0驱动的。下面结合图8进一步论述另一种输入信号方案。

如图6所示，随机数发生器600包括一组异或(XOR)电路640、650、660。和图5的实施方案类似，第一个异或门(“XOR”)640比较波形的同步版本稳定输出和波形输入(在除2触发器625的输出上采样)。因为XOR门640的输出当且仅当两个输入不同时才为高电平，所以当来自核心随机元件400-1的波形稳定输出不匹配输入信号时XOR门640的输出才为高电平。同样，因为异或门650的输出当且仅当它的两个输入不同时才为高电平，所以当来自核心随机元件400-2的波形稳定输出不匹配输入信号时XOR门650的输出才为高电平。

XOR门640、650的输出随后被施加到异或门660。因为异或门660的输出当且仅当它的两个输入不同时才为高电平，所以当来自核心随机元件400-1和400-2的波形稳定输出都为高电平或低电平时XOR门660的输出不会是高电平。换句话说，仅当核心随机元件400-1和400-2都产生位时XOR门660抵制位的产生。

XOR门660的输出被施加到移位寄存器670的使能输入上。因而，每当来自唯一一个核心随机元件400的波形稳定输出与输入信号不匹配时(即出错时)，移位寄存器670从LFSR210的标记信号(LFSR标记)移动一位。所产生的位随后被施加到计算机接口680(或其它应用)。

图7描述了依照本发明的另一实施方案的一种随机数发生器700。在图7所示的说明性实施方案中，随机数发生器700包括两个并联的核心随机元件400-1、400-2，如上结合图4所示，它们使用反相器710来切换第二个核心随机元件400-2的输入信号。因而，核心随机元件400-2永远不会和核心随机元件400-1有相同的输入信号。图7中所示的实施方案还能进一步在随机数产生的每个步骤中阻止攻击者。

随机数发生器700以和上面结合图6所论述的随机数发生器600相同的方式操作，反相器710除外。

图8说明了依照本发明的另一实施方案的一种随机数发生器800。在图8所示的实施方案中，第一核心随机元件400-1用来触发来自另一随机部件400-2的随机位的产生。更准确地说，当在第一个核心随机元件400-1中检测到错误时，第二个核心随机元件400-2的稳定输出被用于输出流。错误的检测可以和上述相同的方式进行，即通过使用多个核心随机元件400。

如图8所示，随机数发生器800包括两个核心随机元件400-1、400-2，如上结合图4所论述的那样。另外，时钟源830产生时钟信号。D-型触发器825提供除2机制，它的Qbar输出被反馈回它的D输入。因而，核心随机元件400-1的输入是由交替的1和0驱动的。

使用异或(XOR)电路840在第一随机部件400-1中检测错误。异或门(XOR)840比较来自第一核心随机元件400-1的波形输出的同步版本稳定输出和波形输入(在除2触发器825的输出上采样)。因为XOR门840的输出当且仅当它的两个输入不同时才为高电平，所以当来自随机部件400-1的波形稳定输出因为亚-稳定特性而不匹配输入信号时XOR门840的输出才为高电平。

XOR门840的输出随后被施加到移位寄存器870的使能输入上。因而，每次来自核心随机元件400-1的波形稳定输出不匹配输入信号时(即出错时)，移位寄存器870将从输入信号(由核心随机元件400-2驱动)移动一位。所产生的位随后被施加到计算机接口880(或其它应用)。核心随机元件400-2以上面结合图4所描述的相同方式操作。

您将会了解到这里所展示和描述的实施方案和变化仅是出于对本发明的说明目的，本领域的技术人员在不偏离本发明的范围和精神的前提下可以进行不同的更改。