计算机科学

首页 > 计算机科学

随机数

2018-09-10 11:53:41

随机数英语:random number)这一概念在不同领域有着不同的含义。

密码学范畴的随机数

根据密码学原理,随机数的随机性检验可以分为三个标准:

  1. 统计学伪随机性。统计学伪随机性指的是在给定的随机比特流样本中,1的数量大致等于0的数量,同理,“10”“01”“00”“11”四者数量大致相等。类似的标准被称为统计学随机性。满足这类要求的数字在人类“一眼看上去”是随机的。
  2. 密码学安全伪随机性。其定义为,给定随机样本的一部分和随机算法,不能有效的演算出随机样本的剩余部分。
  3. 真随机性。其定义为随机样本不可重现。实际上衹要给定边界条件,真随机数并不存在,可是如果产生一个真随机数样本的边界条件十分复杂且难以捕捉(比如计算机当地的本底辐射波动值),可以认为用这个方法演算出来了真随机数。但实际上,这也只是非常接近真随机数的伪随机数,一般认为,无论是本地辐射、物理噪音、抛硬币……等都是可被观察了解的,任何基于经典力学产生的随机数,都只是伪随机数。

相应的,随机数也分为三类:

  1. 伪随机数:满足第一个条件的随机数。
  2. 密码学安全的伪随机数:同时满足前两个条件的随机数。可以通过密码学安全伪随机数生成器计算得出。
  3. 真随机数:同时满足三个条件的随机数。

随机数在密码学中非常重要,保密通信中大量运用的会话密钥的生成即需要真随机数的参与。如果一个随机数生成算法是有缺陷的,那么会话密钥可以直接被推算出来。若果真发生这种事故,那么任何加密算法都失去了意义。

密码学中大量利用伪随机数生成器的应用还有流密码。流密码的著名例子是RC4。流密码的原理是利用一个密码学安全的伪随机数生成器根据密钥产生一串密码学安全的伪随机比特列,再将消息与上述随机比特列按位异或运算。

目前没有数学证明表示密码学安全的伪随机数生成器是确实存在的。其存在性证明涉及到P和NP的数学难题。[1]

密码学以外的随机数

随机数是专门的随机试验的结果。

在统计学的不同技术中需要使用随机数,比如在从统计总体中抽取有代表性的样本的时候,或者在将实验动物分配到不同的试验组的过程中,或者在进行蒙特卡罗模拟法计算的时候等等。

产生随机数有多种不同的方法。这些方法被称为随机数生成器。随机数最重要的特性是它在产生时后面的那个数与前面的那个数毫无关系。

真正的随机数是使用物理现象产生的:比如掷钱币、骰子、转轮、使用电子组件的噪音、核裂变等等。这样的随机数生成器叫做物理性随机数生成器,它们的缺点是技术要求比较高。

在实际应用中往往使用伪随机数就足够了。这些数列是“似乎”随机的数,实际上它们是通过一个固定的、可以重复的计算方法产生的。它们不真正地随机,因为它们实际上是可以计算出来的,但是它们具有类似于随机数的统计特征。这样的生成器叫做伪随机数生成器英语pseudorandom number generator

在真正关键性的应用中,比如在密码学中,人们一般使用真正的随机数。

参考

  1. ^ Jonathan Katz; Yehuda Lindell. Introduction to Modern Cryptography: Principles and Protocols [现代密码学——原理与协议]. ISBN 9787118070651 (英语). [页码请求]
   2^量子真随机数-国家密码管理局 http://www.sca.gov.cn/sca/zxfw/2017-04/25/content_1011723.shtml

上一篇:通称号
下一篇:SM2
相关推荐