随机数

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

密碼學範疇的隨機數

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

  1. 統計學伪隨機性。統計學伪隨機性指的是在給定的随机比特流樣本中,1的數量大致等於0的數量,同理,“10”“01”“00”“11”四者數量大致相等。類似的標準被稱為統計學隨機性。滿足這類要求的數字在人類“一眼看上去”是隨機的。
  2. 密碼學安全偽隨機性。其定義為,給定隨機樣本的一部分和隨機算法,不能有效的演算出隨機樣本的剩餘部分。
  3. 真隨機性。其定義為隨機樣本不可重現。實際上只要給定邊界條件,真隨機數并不存在,可是如果產生一個真隨機數樣本的邊界條件十分複雜且難以捕捉(比如當地的本底輻射波動值),可以認為用這個方法演算出來了真隨機數。但實際上,這也只是非常接近真隨機數的偽隨機數,一般認為,無論是本底輻射、物理噪音、拋硬幣等等都是可被觀察了解的,任何基於經典力學產生的隨機數,都只是偽隨機數。

相應的,隨機數也分爲三類:

  1. 偽隨機數:滿足第一個條件的隨機數。
  2. 密碼學安全的偽隨機數:同時滿足前兩個條件的隨機數。可以通过密码学安全伪随机数生成器计算得出。
  3. 真隨機數:同時滿足三個條件的隨機數。

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

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

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

密碼學以外的隨機數

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

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

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

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

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

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

參考文獻

  1. Jonathan Katz; Yehuda Lindell. [現代密碼學——原理與協議]. ISBN 9787118070651 (英语).

外部連結

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.