随机数的生成

《随机数的生成》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、随机数的生成摘要：随机数在密码学中应用广泛，随机数产生的好与坏直接影响到对数据加密、数字签名、身份认证等运用的安全性，尤其是当用某一随机数作为密钥时，这一点更为明显。直接利用计算机中的伪随机序列发生器产生的随机数并不完全随机，在有限状态机中是周期的，而任何周期性的东西都是可预测的。真正的随机数是使用物理现象产生的，通常我们使用的随机数表其实是伪随机数。关键词：随机数；伪随机数；均匀分布；二项分布；正态分布。1.随机数的介绍1.1随机数的历史随机数的产生方法的研究已经有较长的历史.至今仍有统计学者继续研究随机数的产生的方法

2、和理论.随机数的产生,最早的方法称为手工方法.即采用抽签、掷骰子、抽牌、摇号或者从搅乱的罐子中取带数字的球等方法，许多彩票的发行仍采用这种方法。随着计算机和模拟方法的应用，计算机来产生随机数成为新的课题。利用计算机产生随机数有两种方法，在计算机内输入随机数表和把具有随机性质的物理过程变换为随机数，如粒子的辐射性，裂变等等。在数据结构、算法分析与设计、科学模拟等方面都需要用到随机数。由于在数学上，整数是离散型的，实数是连续型的，而在某一具体的工程技术应用中，可能还有数据值的范围性和是否可重复性的要求。在统计学的不同技术中需

3、要使用随机数，比如在从统计总体中抽取有代表性的样本的时候，或者在将实验动物分配到不同的试验组的过程中，或者在进行蒙特卡罗模拟法计算的时候等等。在用计算机编制程序时，经常需要用到随机数，尤其在仿真等领域，更对随机数的产生提出了较高的要求，仅仅使用C语言类库中的随机函数已难以胜任相应的工作。由具有已知分布的总体中抽取简单子样，在蒙特卡罗方法中占有非常重要的地位。总体和子样的关系，属于一般和个别的关系，或者说属于共性和个性的关系。由具有已知分布的总体中产生简单子样，就是由简单子样中若干个性近似地反映总体的共性。随机数是实现由已

4、知分布抽样的基本量，在由已知分布的抽样过程中，将随机数作为已知量，用适当的数学方法可以由它产生具有任意已知分布的简单子样。1.2随机数的定义随机数是专门的随机试验的结果。 在统计学的不同技术中需要使用随机数，比如在从统计总体中抽取有代表性的样本的时候，或者在将实验动物分配到不同的试验组的过程中，或者在进行蒙特卡罗模拟法计算的时候等等。1.3随机数在密码中的作用很多密码算法都需使用随机数，例如：相互认证。在密钥分配中需使用一次性随机数来防止重放攻击。会话密钥的产生。公钥密码算法中密钥的产生，用随机数作为公钥密码算法中的密钥

5、，或以随机数来产生公钥密码算法中的密钥。在随机数的上述应用中，都要求随机数序列满足随机性和不可预测性。（1）随机性以下两个准则常用来保障数列的随机性：①均匀分布:数列中每个数出现的频率应相等或近似相等。②独立性:数列中任意一数都不能由其他数推出。数列是否满足均匀分布可通过检测得出，而是否满足独立性则无法检测。有很多检测方法能证明数列不满足独立性，因此通常检测数列是否满足独立性的方法是在对数列进行了足够多次检测后都不能证明不满足独立性，就可比较有把握地相信该数列满足独立性。在设计密码算法时，经常使用似乎是随机的数列，称为伪

6、随机数列，例如RSA算法中素数的产生。一般来说，决定一个大数N是否为素数是很困难的。最原始的方法是用小于的每个数去除N，如果N很大，比如10150，这一方法则超出了人类的分析能力和计算能力。很多有效的算法是通过使用随机选择的整数序列作为相对简单计算的输入，可检测一个数的素性。如果随机选择的序列足够长（当然，远小于），就可比较肯定地得出这个数的素性。这种方法称为随机化，在设计密码算法时经常使用。（2）不可预测性在诸如相互认证和会话密钥的产生等应用中，不仅要求数列具有随机性而且要求对数列中以后的数是不可预测的。对于真随机数列

7、来说，数列中每个数都独立于其他数，因此是不可预测的。对于伪随机数来说，就需要特别注意防止敌手从数列前边的数预测出后边的数。1.4随机数产生的方法产生随机数有多种不同的方法。这些方法被称为随机数发生器。随机数最重要的特性是它在产生时后面的那个数与前面的那个数毫无关系。 真正的随机数是使用物理现象产生的：比如掷钱币、骰子、转轮、使用电子元件的噪音、核裂变等等。这样的随机数发生器叫做物理性随机数发生器，它们的缺点是技术要求比较高。 在实际应用中往往使用伪随机数就足够了。这些数列是“似乎”随机的数，实际上它们是通过一个固定的、可

8、以重复的计算方法产生的。它们不真正地随机，因为它们实际上是可以计算出来的，但是它们具有类似于随机数的统计特征。这样的发生器叫做伪随机数发生器。 在真正关键性的应用中，比如在密码学中，人们一般使用真正的随机数。1.5随机数生成的基本原理生成服从给定分布的随机数，需要首先生成服从均匀分布的随机数。常用的生成均匀分布随机数