Randomness

在密碼學領域中“真正的隨機性”究竟是如何定義的?

  • May 18, 2018

尤其是關於流密碼,我經常讀到(有時是理論上的,有時是實際的)能夠“將密文與真正的隨機流區分開來”的攻擊。

對我來說合乎邏輯的是——僅僅因為密文看起來是隨機的,它不一定是隨機的。環顧四周,普遍的共識是“密文需要與真正隨機的比特流無法區分”。

這讓我思考:究竟什麼是“真正的隨機性”?根據我發現的(與密碼相關的)定義,“真正的隨機性是不可預測的”。到目前為止,一切都很好……但這也標誌著我失去它的確切點。

“不可預測”實際上意味著我們沒有什麼可以與密文進行比較,因為我們無法預測“真正的隨機性”可能會產生什麼輸出。此外,“真正的隨機性”可能會輸出與密文完全相同的一系列位(最小)機會。含義:密文可能會被讀​​取63F1t49X43,並且“真正的隨機性”可能產生完全相同的輸出的(最小)機會63F1t49X43。沒有人能說出來,因為“真正的隨機性是不可預測的”

無法預測任何真正的隨機性,我們如何比較、區分甚至聲稱密文不是真正的隨機性?顯然不能將其與“真正的隨機性”進行比較,因為“真正的隨機性是不可預測的”,這是不可能的。

現在,我很確定密碼學不是哲學,因此我絕對確定我錯過了與“真正隨機性”的密碼學含義相關的一些明顯的東西。我猜細節可以在“真正隨機性”的密碼定義中找到,這導致了我的問題:

在密碼學領域中“真正的隨機性”究竟是如何定義的?

實際上,我想您可能會說我不確定我是否正確理解了當“真正的隨機性”被認為是不可預測的情況下,有人如何能夠提供(密碼健全的)證據來證明一系列位是真正隨機的。因此,如果您認為這不是可能讓我感到困惑的定義,請通過指出我可能解釋不正確的任何內容來讓我直截了當。

編輯

為避免誤解:在談論“真正的隨機性”時,我的構想是“真正的隨機數生成器”而不是“偽隨機數生成器”。這就是為什麼我要問“真正的隨機性”而不是偽隨機性。

隨機性不是位串(或任何類型的字元)的屬性。相反,它是生成這些字元串的過程的屬性。但是,將字元串與產生字元串的事物混為一談是很方便的,因此可以說字元串是*“隨機的”“非隨機的”*。

00000例如,如果它是*“隨機過程”的結果,則字元串是隨機的,例如硬幣被拋五次並連續五次落在尾巴上。1,2,3,4,5,6同樣,如果是擲骰子六次的結果,則該字元串是隨機的。請注意,隨機過程不一定要“公平”*才能成為隨機過程,儘管顯著偏離均勻分佈的過程對於加密目的沒有那麼有用。

什麼是*“隨機過程”*?在我看來,隨機過程要麼是不確定的過程(如果確實存在的話),要麼是我們不知道的熵(與結果密切相關)大於確定的過程的熵生成的字元串。關於翻轉硬幣的狀態,我們有很多不知道(而且永遠不可能知道)——例如硬幣中每個粒子的確切位置和動量、它周圍的空氣,以及拋硬幣的手。翻轉它(所有這些都是密切相關的,因為我們可能需要知道它們才能準確預測翻轉的結果)。

如果字元串00000是數字生成算法的結果,其中未知的和與算法密切相關的熵小於 5 位(例如,我們知道算法以及除了 4 位之外的所有關於種子的資訊),那麼字元串將是*“非隨機的”。充其量它可能是“偽隨機”*,這意味著在計算上難以與隨機區分開來。

引用自:https://crypto.stackexchange.com/questions/10776