Entropy

為什麼“我袖手旁觀的數字”的熵很低?

  • October 28, 2015

作為序言,請原諒我的一些連結來自維基百科。我意識到學術界對此不屑一顧。

我偶然發現了這篇關於“我的袖子號碼一無所有”的文章。其中,它說:

在密碼學中,我袖手旁觀的數字不是任何數字,根據它們的構造,它們是超越隱藏屬性的懷疑的。

$$ … $$ 這些數字可以看作是柴廷-科爾莫戈羅夫隨機數的相反極端,因為它們看起來是隨機的,但資訊熵非常低。

在尋找其中一個數字的範例時,我遇到了這個 Crypto Beta Q&A,其中回答者說:

$$ M $$可以使用諸如 2√(或其他數字的根)、e、π 等無理數的二進制展開之類的數學常數來表明沒有選擇這些數字來創建後門。

這就是維基百科關於資訊熵的說法:

熵通常以比特、nat 或禁令來衡量。香農熵是隨機變數中的平均不可預測性,相當於它的資訊量。香農熵為任何通信的最佳可能無損編碼或壓縮提供了絕對限制,假設通信可以表示為一系列獨立且同分佈的隨機變數。

基於此,我不明白為什麼這些數字(或任何可能的數字)可以具有低熵。只要該數字在生成的範圍內(例如,如果數字是 1564631

$$ assumed to be one of these kinds of numbers $$,並且我正在尋找介於 1 和 2000000 之間的數字,無論如何它都有相同的生成可能性)。 誰能解釋這個概念?我查看了 entropy 的定義,但我承認數學有點過頭了。我不確定有人會如何使用沒有這些屬性的數字來“創建後門”。

你是絕對正確的:數字(或給定的二進製字元串)沒有熵。但是,可以從具有熵的*分佈中採樣一個數字。*換句話說,熵是用於生成數字的過程的屬性,而不是數字本身的屬性。

因此,如果我只是給你數字 4,並向你保證我是從 1 到 6 之間隨機選擇這個數字,你就無法知道我說的是不是真的。根據情況,也許我選擇 4 是別有用心,而不是隨機選擇一個數字。

這個問題出現在密碼學中,因為當需要為算法選擇常量(例如 SHA1,或您連結的維基百科文章中的任何其他範例)時,可能會有數學論據表明,“如果選擇了常量隨機,那麼很有可能沒有攻擊者能夠破壞它。” 但是,作為一個偏執狂的密碼學家,當有人說“讓我們使用這組常量。我發誓我是隨機挑選的”時,他們會持懷疑態度。因此,作為一種折衷方案,他們將使用常數,例如 π 的二進制展開。雖然我們不再擁有從大量數字中隨機選擇它們的數學優勢,但我們至少可以更有信心沒有破壞。

這些nothing-up-my-sleeve 常數的熵很低,因為選擇它們的過程並不涉及很多隨機選擇——將“合理的”nothing-up-my-sleeve 數字的數量與比如說, 128 位字元串,它們用於生成。這是設計使然。如果有大量無用的數字可供選擇,那麼惡意算法設計者會更容易找到適合其議程的數字。

Dual EC DRBG 標準是用於生成隨機數的一個非常近期且非常令人震驚的案例,即有人不使用無名無實的數字來創建後門。這個算法包括兩個常數,P 和 Q,如果沒有人可以計算f(P, Q),對於一個特定的函式是安全的f。給定隨機選擇的 P 和 Q,這將很難。然而,如果你要選擇P 和 Q,那麼你可以選擇 P,決定你想要的 f(P, Q) 是什麼,然後相當容易地求解 Q。現在你有一個後門。

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