我們如何在密碼學中選擇隨機元素？
在閱讀有關密碼學的論文時，我經常看到人們選擇隨機元素 $ x\in \mathbb{Z}^*_q $ 做某事（比如設置密鑰和所有）。如何在現實中隨機選擇元素。我的意思是在實際實施中，我們遵循什麼程序？我們使用一些 CSPRNG 嗎？
在實踐中，為了選擇一個均勻隨機的 $ x\in \mathbb{Z}^*_q $ ，我們將該任務簡化為選擇均勻隨機和獨立位的問題。在現代電腦系統上，將有一些作業系統服務提供這些位，例如在許多 Unix 衍生產品上的 /dev/urandom（我們將在第二部分回到如何獲得這些位的問題）。
選擇均勻隨機的最簡單方法 $ x\in \mathbb{Z}^*_q $ , 那是一個整數 $ [0,q) $ ，有時稱為拒絕抽樣，是：
- 作為預演無論多少次 $ x $ 我們想要生成：作為（確定性）函式 $ q $ , 選擇一些 $ k $ 和 $ 2^k\ge q $ ，例如 $ k $ 略高於二進製表達式中的位數 $ q $ .
- 畫 $ k $ 均勻隨機且獨立的位 $ b_i $ ， 為了 $ 0\le i<k $
- 組裝 $ k $ 位轉換為整數 $ y=\sum b_i,2^i $
- 如果 $ y<(2^k\bmod q) $ ，從 2 開始。
- 計算和輸出 $ x=y\bmod q $ .
的機率 $ x $ 是任何特定的整數 $ [0,q) $ 正是 $ 1/q $ 在假設下 $ b_i $ 是均勻隨機且獨立的。
常見變體：
- 生產比特 $ b_i $ 分組在一個電腦詞中，和/或 $ k $ 強制為某些單詞大小的倍數。
- 2 處的大字節序： $ y=\sum b_i,2^{k-i-1} $ ; 這也允許 $ y $ 在我們繪製 $ b_i $ 作為 $ y_0=0 $ , $ y_{i+1}=y_i+y_i+b_i $ 為了 $ 0\le i<k $ , $ y=y_k $ .
- 4 處的不同測試條件，例如 $ y\ge2^k-(2^k\bmod q) $ .
我們還可以刪除第 4 步（在這種情況下，該方法不再是拒絕抽樣）。除非 $ q $ 是二的冪，這留下整數 $ [0,2^k\bmod q) $ 比那些在 $ [(2^k\bmod q), q) $ , 有機率 $ \lceil 2^k/q\rceil/2^k $ 而不是 $ \lfloor 2^k/q\rfloor/2^k $ . 但如果 $ k $ 適當地大於中的位數 $ q $ （說， $ k>\lceil\log_2 q\rceil+64 $ )，或/和如果 $ \min(2^k\bmod q,-2^k\bmod q)/q $ 小於某個合適的限制（例如 $ 2^{-128} $ )，那麼這種偏差在實驗上是無法檢測到的。
（有更好的描述我們何時可以刪除步驟 4，以及更複雜的方法來最小化 $ b_i $ 製作很多時產生 $ x $ ，但它們的使用並不常見）。
我們回到了挑選均勻隨機和獨立位的問題，或者可能是由這些位組成的電腦字。
推薦的方法都使用相同的廣泛原則：不完美隨機性的來源被後處理成希望與所需的均勻隨機和獨立位無法區分的位（實際上，包括任意強大的對手；或作為備份，可計算地）。
範例來源：
- 輸入包括擊鍵、滑鼠位置、麥克風、攝像頭輸入。
- 發生擊鍵、滑鼠位置變化、磁碟塊或乙太網/Wifi/藍牙/USB 數據包到達主機板的時間，例如以電腦啟動後的時鐘週期來衡量
- 專用設備。一種方法是將齊納二極體上的瞬時電壓與其平均值進行比較，並定期對結果進行採樣。另一個使用另一個希望是獨立的振盪器來採樣一個有希望的混沌振盪器。
應該付出很多努力來監視源，以確保它/它們正常執行（或者如果我們將幾個結合起來，以估計我們可以確信它們共同提供的最小熵）。
最簡單有效的後處理方法之一是散列：對來自源的一些位進行散列，結果（或其一部分）形成條件輸出。這對於在計算上與隨機預言（對於使用的輸入長度）無法區分的散列以及散列輸入的足夠大（最小）熵是安全的。
如果我們需要許多隨機位，我們可以通過播種加密安全偽隨機數生成器來以低成本製造它們，該生成器具有如上一段中獲得的隨機性。但是，如果 CSPRNG 的狀態受到損害（例如，通過旁通道），則它的所有輸出都是。出於這個原因，有更複雜的方法可以以高速率獲得高度安全的隨機位，以一種可以很好地從其內部狀態的損害中恢復的方式。
另外：在現代 CPU 上，通常有一個片上源（有時在晶片組中）。通常，它的輸出無法以有據可查的方式訪問。這樣做的藉口是人們會直接使用它，或/並吹噓在其中檢測到一些偏見，即使這是預期的。程序員應該通過一些指令（例如RDRAND）使用神秘的條件輸出。如何監控源的健康狀況通常記錄不充分，和/或軟體/作業系統不支持。基於 CPU 的 RNG 的其他可能問題包括對其輸出的機密性保護不佳，請參見例如this。得出（雙關語）您自己的結論，即它們是否應該被信任為加密貨幣中的唯一來源或隨機性。