随机数

维基百科,自由的百科全书
跳转至: 导航搜索

隨機數這一概念在不同領域有著不同的含義。

密碼學範疇的隨機數[编辑]

根據密碼學原理,隨機數的隨機性檢驗可以分爲三個標準:

  1. 統計學隨機性。統計學隨機性指的是在給定隨即比特流樣本中,1的數量大致等於0的數量,同理,“10”“01”“00”“11”四者數量大致相等。類似的標準被稱爲統計學隨機性。滿足這類要求的數字在人類“一眼看上去”是隨機的。
  2. 密碼學安全僞隨機性。其定義爲,給定隨機樣本的一部分和隨機算法,不能有效的演算出隨機樣本的剩餘部分。
  3. 真隨機性。其定義爲隨機樣本不可重現。實際上衹要給定邊界條件,真隨機數并不存在,可是如果產生一個真隨機數樣本的邊界條件十分複雜且難以捕捉(比如計算機當地的本底輻射波動值),可以認爲用這個方法演算出來了真隨機數。

密碼學中,滿足第一個條件的隨機數稱爲僞隨機數,同時滿足前兩個條件的隨機數稱爲密碼學安全的僞隨機數,同時滿足三個條件的隨機數稱爲真隨機數。

隨機數在密碼學中非常重要,保密通信中大量運用的會話密鑰的生成即需要真隨機數的參與。如果一個隨機數生成演算法是有缺陷的,那麽會話密鑰可以直接被推算出來。若果真發生這種事故,那麽任何加密算法都失去了意義。

密碼學中大量利用僞隨機數生成器的應用還有流密碼。流密碼的著名例子是RC4。流密碼的原理是利用一個密碼學安全的僞隨機數生成器根據密鑰產生一串密碼學安全的偽隨機比特列,再將消息與上述隨機比特列按位異或運算。

目前沒有數學證明表示密碼學安全的僞隨機數生成器是確實存在的。其存在性證明涉及到P和NP的數學難題。[1]

密碼學以外的隨機數[编辑]

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

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

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

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

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

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

  1. ^ Jonathan Katz and Yehuda Lindell, 現代密碼學——原理與協議 (Introduction to Modern Cryptography: Principles and Protocols), ISBN 9787118070651