Pseudo-Random-Generator
為了具有競爭力，偽隨機數生成器必須有多快？
讓 $ {x_n}_{n} $ 是由密碼安全的偽隨機數生成器產生的偽隨機序列 $ G $ . 為競爭性偽隨機數生成器 (PRNG) 計算序列中的項的成本是多少？
讓我澄清一下：在加密安全的 PRNG 中，我想知道哪一個的計算成本最低。
在現代 CPU 上，快速加密安全偽隨機數生成器的執行速度比每字節一個週期快得多。我們正在談論> 40Gbit / s。見那裡的數字。最佳競爭者是由特殊指令輔助的AES - CTR ，以及像ChaCha這樣的ARX密碼。
使用專用硬體時，真正的限制是圍繞生成的隨機位移動。我們可以任意並行化 CSPRNG，並且我們有許多高效的設計。例如，據報導， Trivium使用 250nm 金屬 CMOS 技術達到 >120Gbit/s/mm 2，而當今最先進的技術大約是 10nm 技術，它速度更快，密度更高數百倍。
根據評論更新：所有現代 CSPRNG 都需要 $ O(n) $ 位操作產生 $ n $ 位，我們想要一個更精確的估計。恰恰與 $ r $ 輪次（參見原始碼）產生 $ 16 $ 每個 32 位的單詞，計算成本由 $ 16(r+1) $ 32 位加法和 $ 16r $ 32 位異或。使用 NAND 門，一個波紋進位加法器是 9 個門，XOR 是 4 個門，因此成本是 $ 13r+9 $ 產生的每個位的 NAND 位操作。對於 ChaCha8（希望至少具有 128 位安全性），成本為 $ \approx113n $ NAND位操作產生 $ n $ 位（不考慮電路深度）。
根據其他評論更新 ChaCha8 的安全性：我有理由相信 ChaCha8 至少是 128 位安全的，但不願說明更多，因為
- ChaCha 是 Salsa20 的演變，具有相同數量的 32 位加法和 XOR，並且傳播速度更快。雖然這可以使它更安全，但我將其用作安全邊際。
- 在Salsa 論文的摘要中，Daniel J. Bernstein 推薦 20 輪版本用於典型應用，並提出 12 輪和 8 輪變體作為推薦用於速度比信心更重要的應用的**縮減版本。
- Salsa20 是為 eSTREAM 提出的，屬於要求具有 128 位安全性的快速軟體密碼的類別。雖然 DJB 將 Salsa20/20、Salsa20/12 和 Salsa20/8 呈現為 256 位密碼（就密鑰大小而言，它們都是如此），但我並沒有將他解讀為聲稱 256 位安全性，尤其是對於減少輪次版本。
- 存在一種複雜的已知攻擊 $ \approx2^{249} $ 針對 Salsa20/8，因此它肯定沒有與其密鑰大小相匹配的安全性。同樣，ChaCha8 的不同之處僅在於其擴散模式。
- 存在一種複雜的已知攻擊 $ \approx2^{153} $ 對陣Salsa20/7，俗話說：攻擊只會越來越好；他們永遠不會變得更糟。